Electrical computers and digital processing systems: multicomput – Distributed data processing – Client/server
Reexamination Certificate
1998-01-09
2001-01-30
Maung, Zarni (Department: 2758)
Electrical computers and digital processing systems: multicomput
Distributed data processing
Client/server
C709S246000
Reexamination Certificate
active
06182114
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for serving images, even very large images, over a “thinwire” (e.g., over the Internet or any other network or application having bandwidth limitations).
BACKGROUND INFORMATION
The Internet, including the World Wide Web, has gained in popularity in recent years. The Internet enables clients/users to access information in ways never before possible over existing communications lines.
Often, a client/viewer desires to view and have access to relatively large images. For example, a client/viewer may wish to explore a map of a particular geographic location. The whole map, at highest (full) level of resolution will likely require a pixel representation beyond the size of the viewer screen in highest resolution mode.
One response to this restriction is for an Internet server to pre-compute many smaller images of the original image. The smaller images may be lower resolution (zoomed-out) views and/or portions of the original image. Most image archives use this approach. Clearly this is a sub-optimal approach since no preselected set of views can anticipate the needs of all users.
Some map servers (see, e.g., URLs http://www.mapquest.com and http://www.MapOnUs.com) use an improved approach in which the user may zoom and pan over a large image. However, transmission over the Internet involves significant bandwidth limitations (i.e transmission is relatively slow). Accordingly, such map servers suffer from at least three problems:
Since a brand new image is served up for each zoom or pan request, visual discontinuities in the zooming and panning result. Another reason for this is the discrete nature of the zoom/pan interface controls.
Significantly less than realtime response.
The necessarily small fixed size of the viewing window (typically about 3″×4.5″). This does not allow much of a perspective.
To generalize, what is needed is an apparatus and method which allows realtime visualization of large scale images over a “thinwire” model of computation. To put it another way, it is desirable to optimize the model which comprises an image server and a client viewer connected by a low bandwidth line.
One approach to the problem is by means of progressive transmission. Progressive transmission involves sending a relatively low resolution version of an image and then successively transmitting better resolution versions. Because the first, low resolution version of the image requires far less data than the full resolution version, it can be viewed quickly upon transmission. In this way, the viewer is allowed to see lower resolution versions of the image while waiting for the desired resolution version. This gives the transmission the appearance of continuity. In addition, in some instances, the lower resolution version may be sufficient or may in any event exhaust the display capabilities of the viewer display device (e.g., monitor).
Thus, R. L. White and J. W. Percival, “Compression and Progressive Transmission of Astronomical Images,”
SPIE Technical Conference
2199, 1994, describes a progressive transmission technique based on bit planes that is effective for astronomical data.
However, utilizing progressive transmission barely begins to solve the “thinwire” problem. A viewer zooming or panning over a large image (e.g., map) desires realtime response. This of course is not achieved if the viewer must wait for display of the desired resolution of a new quadrant or view of the map each time a zoom and pan is initiated. Progressive transmission does not achieve this realtime response when it is the higher resolution versions of the image which are desired or needed, as these are transmitted later.
The problem could be effectively solved, if, in addition to variable resolution over time (i.e, progressive transmission), resolution is also varied over the physical extent of the image.
Specifically, using foveation techniques, high resolution data is transmitted at the user's gaze point but with lower resolution as one moves away from that point. The very simple rationale underlying these foveation techniques is that the human field of vision (centered at the gaze point) is limited. Most of the pixels rendered at uniform resolution are wasted for visualization purposes. In fact, it has been shown that the spatial resolution of the human eye decreases exponentially away from the center gaze point. E. L. Schwartz, “The Development of Specific Visual Projections in the Monkey and the Goldfish: Outline of a Geometric Theory of Receptotopic Structure,”
Journal of Theoretical Biology,
69:655-685, 1977
The key then is to mimic the movements and spatial resolution of the eye. If the user's gaze point can be tracked in realtime and a truly multi-foveated image transmitted (i.e., a variable resolution image mimicking the spatial resolution of the user's eye from the gaze point), all data necessary or useful to the user would be sent, and nothing more. In this way, the “thinwire” model is optimized, whatever the associated transmission capabilities and bandwidth limitations.
In practice, in part because eye tracking is imperfect, using multi-foveated images is superior to atempting display of an image portion of uniform resolution at the gaze point.
There have in fact been attempts to achieve multifoveated images in a “thinwire” environment.
F. S. Hill Jr., Sheldon Walker Jr. and Fuwen Gao, “Interactive Image Query System Using Progressive Transmission,”
Computer Graphics,
17(3), 1983, describes progressive transmission and a form of foveation for a browser of images in an archive. The realtime requirement does not appear to be a concern.
T. H. Reeves and J. A. Robinson, “Adaptive Foveation of MPEG Video,”
Proceedings of the
4
th
ACM International Multimedia Conference,
1996, gives a method to foveate MPEG-standard video in a thin-wire environment. MPEG-standard could provide a few levels of resolution but they consider only a 2-level foveation. The client/viewer can interactively specify the region of interest to the server/sender.
R. S. Wallace and P. W. Ong and B. B. Bederson and E. L. Schwartz, “Space-variant image processing”. Intl. J. Of Computer Vision, 13:1 (1994) 71-90 discusses space-variant images in computer vision. “Space-Variant” may be regarded as synonymous with the term “multifoveated” used above. A biological motivation for such images is the complex logmap model of the transformation from the retina to the visual cortex (E. L. Schwartz, “A quantitative model of the functional architecture of human striate cortex with application to visual illusion and cortical texture analysis”, Biological Cybernetics, 37(1980) 63-76).
Philip Kortum and Wilson S. Geisler, “Implementation of a Foveated Image Coding System For Image Bandwidth Reduction,”
Human Vision and Electronic Imaging, SPIE Proceedings Vol.
2657, 350-360, 1996, implement a real time system for foveation-based visualization. They also noted the possibility of using foveated images to reduce bandwidth of transmission.
M. H. Gross, O. G. Staadt and R. Gatti, “Efficient triangular surface approximations using wavelets and quadtree data structures”, IEEE Trans, On Visualization and Computer Graphics, 2(2), 1996, uses wavelets to produce multifoveated images.
Unfortunately, each of the above attempts are essentially based upon fixed super-pixel geometries, which amount to partitioning the visual field into regions of varying (pre-determined) sizes called super-pixels, and assigning the average value of the color in the region to the super-pixel. The smaller pixels (higher resolution) are of course intended to be at the gaze point, with progressively larger super-pixels (lower resolution) about the gaze point.
However, effective real-time visulization over a “thin wire” requires precision and flexibility. This cannot be achieved with a geometry of predetermined pixel size. What is needed is a flexible foveation technique which allows one to modify the position and shape of the basic foveal regions, the maximum resolution
Chang Ee-Chien
Yap Chee K.
Yen Ting-Jen
Baker & Botts L.L.P.
Maung Zarni
New York University
Winder Patrice
LandOfFree
Apparatus and method for realtime visualization using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for realtime visualization using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for realtime visualization using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441830