a2, United States Patent
`US 6,182,114 Bl
`(10) Patent No.:
`Jan. 30, 2001
`(45) Date of Patent:
`Yap etal.
`
`US006182114B1
`
`(54) APPARATUS AND METHOD FOR
`REALTIME VISUALIZATION USING
`USER-DEFINED DYNAMIC, MULTI-
`FOVEATED IMAGES
`
`(75)
`
`Inventors: Chee K. Yap; Ee-Chien Chang, both
`of New York, NY (US); Ting-Jen Yen,
`Jersey City, NJ (US)
`
`(73) Assignee: New York University, New York, NY
`(US)
`
`(*) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(21) Appl. No.: 09/005,174
`
`(22)
`
`Filed:
`
`Jan. 9, 1998
`
`eves GO6F 15/16
`Int. Cl.’ .
`(51)
`
`(52) U.S. Ch oo.
`709/203; 709/246
`
`(58) Field of Search 0... 709/217, 219,
`709/246, 247, 203; 707/10; 382/103, 233,
`235, 232, 240, 302
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`11/1986 Tanimoto .
`4,622,632
`8/1994 Perlin .
`5,341,466
`1/1996 Gerhardtet al. oe 382/103
`5,481,622 *
`
`« 382/302 X
`5,568,598 * 10/1996 Macket al.
`.
`
`1/1998 Bradley oo...
`cece 382/233
`5,710,835 *
`
`3/1998 Denninghoff etal
`« 382/235 K
`5,724,070 *
`
`1/1999 Meadetal. .........
`« 382/232 X
`5,861,920 *
`
`« 382/240 X
`5,880,856 *
`3/1999 Ferriere .......
`7/1999 ATiga woes secesesceeseseeees 707/10
`5,920,865 *
`OTHER PUBLICATIONS
`
`Tams Frajka et al., Progressive Image Coding with Spatially
`Variable Resolution, IEEE, Proceedings International Con-
`ference on Image Processing 1997, Oct. 1997, vol. 1, pp.
`53-56.*
`
`2
`
`E. C. Chang et al., “Realtime Visualization of Large .. .
`Mar. 31, 11997,pp. 1-9, Courant Institute of Mathematical
`Sciences, New York University, N.Y. U.S.A.
`
`E. C. Chang et al., “A Wavelet Approach to Foveating
`Images”, Jan. 10, 1997,pp. 1-11, Courant Institute of Math-
`ematical Sciences, New York University, N.Y. U.S.A.
`
`S.G. Mallat, “A Theory for Multiresolutional Signal Decom-
`position... ”, IEEE Transactions on Pattern Analysis and
`Machine Intelligence,pp. 3-23, Jul. 1989, vol. 11, No. 7,
`IEEE Computer Society.
`
`NewsRelease, “Wavelet Image Features”,Summus’ Wavelet
`Image Compression,Summus 14 pages.
`
`R.L. White et al., “Compression and Progressive Transmis-
`sion of Astronomical Images”, SPIE Technical Conference
`2199, 1994.
`
`(List continued on next page.)
`
`Primary Examiner—Zarmi Maung
`Assistant Examiner—Patrice Winder
`
`(74) Attorney, Agent, or Firm—Baker Botts, L.L.P.
`
`(57)
`
`ABSTRACT
`
`Aclient apparatus which enables a realtime visualization of
`at least one image. The client apparatus includes a storage
`device whichstores first data corresponding to a multifove-
`ated representation of an original image, and a user input
`device which providing second data corresponding to at
`least one visualization command of at least one user. In
`
`addition, the client apparatus includes a processing arrange-
`ment which generates third data corresponding to a multi-
`foveated image using the first data, the second data and a
`foveation operator.
`
`8 Claims, 6 Drawing Sheets
`
`CONVERT USERINPUT
`
`(FOVEAL REGION} TO
`(MULTI RESOLUTION)
`
`
`REQUEST FOR
`COEFFICIENTS.
`
`
`
`SEND (MULTI
`DETERMINE FOVEAL
`
`RESOLUTION) REQUEST
`REGION FROM USER
`TO SERVER FOR
`
` INPUT,
`COEFFICIENTS
`
`
`
`UPDATE DISPLAY
`WINDOWS
`(PROGRESSIVELY)
`BASED ON PYRAMID
`REPRESENTATION
`
`RECEIVE COEFFICIENTS.
`FROM SERVER
`
`
`
`
`
`
`
`
`20
`
`Google 1022
`U.S. Patent No. 9,445,251
`
`i—__¥
`WAVELET TRANSFORM
`PERFORM INVERSE
`ON COEFFICIENTS
`(IF NECESSARY)
`AND STORE
`(PROGRESSIVELY)IN
`PYRAMID
`
`c j
`
`Google 1022
`U.S. Patent No. 9,445,251
`
`

`

`US 6,182,114 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`E.L. Schwartz, “The Development of Specific Visual...”
`Journal of Theoretical Biology, 69:655—-685, 1977.
`FS. Hill Jr. et al.,“Interactive Image Query ... ” Computer
`Graphics, 17(3), 1983.
`T.H. Reeveset al., “Adaptive Foveation of MPEG Video”,
`Proceedings of the 4th ACM International Multimedia Con-
`ference, 1996.
`R.S. Wallaceet al., “Space—variant image processing”. Int’].
`J. of Computer Vision, 13:1(1994) 71-90.
`
`E.L. Schwartz A quantitative model of the functional archi-
`tecture: Biological cybernetics, 37(1980) 63-76.
`
`P. Kortum et al., “Implementation of a Foveated Image .. .
`” Human Vision and Electronic Imagining, SPIE Proceed-
`ings vol. 2657, 350-360, 1996.
`
`M.H. Grosset al., “Efficient triangular surface ...”, IEEE
`Trans on Visualization and Computer Graphics, 2(2) 1996.
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 1 of 6
`
`US 6,182,114 B1
`
`. Ch
`
`N+-z~
`
`16
`
`WwAWwHq)
`
`
`
`oOooNo2fF+o28
`
`vToOWwW~
`
`—
`
`oY—
`
`-
`
`TALErffiUsinN
`cna)epTey
`
`om©mNt
`
`co—
`
`wv
`
`t—
`
`FIG. 1
`
`
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 2 of 6
`
`US 6,182,114 B1
`
`N>
`
`(a-b+c-d)
`
`a= (at+b+c+d)
`5
`
`10
`
`_
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 3 of 6
`
`US 6,182,114 B1
`
`2
`
`3 = (a+b+c+td)
`
`ai'+b'+c' +d’
`
`2
`
`FIG. 2B
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 4 of 6
`
`US 6,182,114 B1
`
`
`
`
`LET N = NUMBER OF ROWS AND COLUMNSOF PIXELS IN THE (SQUARE) IMAGE
`
`LET X = THE NEXT OF THE THREE COLOR COMPONENTSOF THE IMAGE (R, G OR B)
`
`
`LET M,(X) = BE THE NxN MATRIX WHOSE COEFFICIENTS EQUAL THE NUMERIC
`VALUE OF THE X COMPONENT OF THE CORRESPONDING PIXEL OF THE IMAGE
`
`
`LET M,, ,(X) = BE THE N/2xN/2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`
`"AVERAGE" OF THE CORRESPONDING 2x2 BLOCK OF FOUR COEFFICIENTSIN M,(X)
`
`
`
`
`
`COEFFICIENTS IN M, (X)
`
`LET H,, ,(X) = BE THE Ni2xni2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`"HORIZONTAL DIFFERENCE” OF THE CORRESPONDING 2x2 BLOCK OF FOUR
`
`LET V,, ,(X) = BE THE Ni2xN/2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`"VERTICAL DIFFERENCE" OF THE CORRESPONDING 2x2 BLOCK OF FOUR
`COEFFICIENTS IN M,(X)
`
`
`LET D,, ,(X) = BE THE N/2xM/2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`"DIAGONAL DIFFERENCE” OF THE CORRESPONDING 2x2 BLOCK OF FOUR
`COEFFICIENTS IN M,{X)
`
`STORE H,, ,(X), V(X), Dy, ,(X)
`
`cre
`
`ISN < 256?
`
`YES
`
`STORE M,(X)
`
`
`
`
`
`
`
`
`FIG. 3
`
`YES
`ARE THERE
`MORE COLOR COMPONENTIS) CO
`LEFT?
`NO
`
`END
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 5 of 6
`
`US 6,182,114 B1
`
`CONVERT USER INPUT |
`(FOVEAL REGION) TO
`(MULTI RESOLUTION)
`REQUEST FOR
`
`42
`
`COEFFICIENTS
`INPUT
`REPRESENTATION
`
`SEND (MULTI
`RESOLUTION) REQUEST
`TO SERVER FOR
`COEFFICIENTS
`
`DETERMINE FOVEAL
`REGION FROM USER
`
`RECEIVE COEFFICIENTS|
`FROM SERVER
`
`UPDATE DISPLAY
`WINDOWS
`(PROGRESSIVELY)
`BASED ON PYRAMID
`
`20
`
`PERFORM INVERSE
`WAVELET TRANSFORM |
`ON COEFFICIENTS
`(IF NECESSARY)
`AND STORE
`(PROGRESSIVELY)IN
`PYRAMID
`
`19
`
`FIG.4
`
`

`

`U.S. Patent
`
`Jan. 30, 2001
`
`Sheet 6 of 6
`
`US 6,182,114 B1
`
`LET L = LEVEL OF RESOLUTION SUCH
`THAT THE SIZE OF IMAGE M, IS 128 x128
`MATRIX. THE LOWEST LEVEL OF
`RESOLUTION SUPPORTED
`
`200
`
`NO
`
`260
`
`220
`
`
`
`HAVE THE
`
`COEFFICIENTS
`OF M,(R), M,(G) AND
`M,(B) CORRESPONDING \YES
`
`YES
`
`,
`
`210
`
`IS
`
`
`L = THE LEVEL OF LOWEST
`
`RESOLUTION?
`
`
`YES
`
`HAVE THE
`
`
`HORIZONTAL,
`VERTICAL AND
`
`
`
`DIAGONAL DIFFERENCE
`COEFFICIENTS NECESSARY
`
`
`TO RECONSTRUCT THE
`
`
`
`COEFFICIENTSIN M,(R),M,(G)
`ANDM,(B) CORRESPONDING
`TO THE PIXELSIN
`
`
`THE FOVEAL
`REGION BEEN
`
`
`REQUESTED?
`
`
`
`TOTHEPIXELS
`IN THE FOVEAL
`REGION BEEN
`REQUESTED
`?
`
`
`
`
`
`
`
`NO
`
`
`
`230
`
`MASK
`
`REQUEST THE
`COEFFICIENTS
`ACCORDING TO THE
`
`REQUEST THE
`DIFFERENCE
`COEFFICIENTS
`ACCORDING TO THE
`MASK
`
`240<Ei>> YES
`
`280
`
`270
`
`L<L-1
`
`NO
`RETURN TO
`MANAGER THREAD
`
`250
`
`FIG.5
`
`

`

`US 6,182,114 B1
`
`1
`APPARATUS AND METHOD FOR
`REALTIME VISUALIZATION USING USER-
`DEFINED DYNAMIC, MULTI-FOVEATED
`IMAGES
`
`FIELD OF THE INVENTION
`
`The present invention relates to a method and apparatus
`for serving images, even very large images, over a “thin-
`wire” (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 communicationslines.
`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 responseto 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
`approachsince no preselected set of views can anticipate the
`needs ofall 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"x4.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 meansofprogressive
`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 suffi-
`cient 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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 panis 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 overtime(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 humanfield 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
`shownthat the spatial resolution of the human eye decreases
`exponentially away from the center gaze point. E. L.
`Schwartz, “The Developmentof 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
`(ie., 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 band-
`width limitations.
`In practice, in part because eye tracking is imperfect,
`using multi-foveated imagesis superior to atempting display
`of an imageportion 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, “Inter-
`active 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
`MPEGVideo,” Proceedings of the 4 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 synonymouswith the term “multifoveated” used
`above. A biological motivation for such images is the
`complex logmap modelof the transformation from the retina
`to the visual cortex (E. L. Schwartz, “A quantitative model
`of the functional architecture of human striate cortex with
`
`

`

`US 6,182,114 B1
`
`3
`application to visual illusion and cortical texture analysis”,
`Biological Cybernetics, 37(1980) 63-76).
`Philip Kortum and WilsonS. 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 trian-
`gular surface approximations using wavelets and quadtree
`data structures”, IEEE Trans, On Visualization and Com-
`puter Graphics, 2(2), 1996, uses wavelets to produce mul-
`tifoveated images.
`Unfortunately, each of the above attempts are essentially
`based upon fixed super-pixel geometries, which amountto
`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 neededis a flexible foveation technique which allows one
`to modify the position and shapeofthe basic foveal regions,
`the maximum resolution at the foveal region andtherate at
`which the resolution falls away. This will allow the “thin-
`wire” model to be optimized.
`In addition, none of the above noted references addresses
`the issue of providing multifoveated images that can be
`dynamically (incrementally) updated as a function of user
`input. This property is crucial to the solution of the thinwire
`problem,since it is essential that information be “streamed”
`at a rate that optimally matches the bandwidth of the
`network with the human capacity to absorb the visual
`information.
`
`SUMMARYOF THE INVENTION
`
`The present invention overcomesthe disadvantagesof the
`prior art by utilizing means for tracking or approximating
`the user’s gaze point
`in realtime and, based on the
`approximation, transmitting dynamic multifoveated image
`(s) (ie., a variable resolution image overits physical extent
`mimicking the spatial resolution of the user’s eye about the
`approximated gaze point) updated in realtime.
`“Dynamic” meansthat the image resolution is also vary-
`ing over time. The user interface component of the present
`invention may provide a variety of means for the user to
`direct this multifoveation process in real time.
`Thus, the invention addresses the model which comprises
`an image server and a client viewer connected by a low
`bandwidth line. In effect, the invention reduces the band-
`width from server to client, in exchange for a very modest
`increase of bandwidth from the client to the server
`
`Another object of the invention is that it allows realtime
`visualization of large scale images over a “thinwire” model
`of computation.
`An additional advantage is the new degree of user control
`provided for realtime, active, visualization of images
`(mainly by way of foveation techniques). The invention
`allows the user to determine and change in realtime, via
`input means (for example, without
`limitation, a mouse
`pointer or eye tracking technology), the variable resolution
`over the space of the served up image(s).
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`4
`An additional advantage is that the invention demon-
`strates a new standard of performance that can be achieved
`by large-scale image servers on the World Wide Web at
`current bandwidth or even in the near future.
`
`Note also, the invention has advantages over the tradi-
`tional notion of progressive transmission, which has no
`interactivity. Instead,
`the progressive transmission of an
`image has beentraditionally predetermined when the image
`file is prepared. The invention’s use of dynamic (constantly
`changing in realtime based on the user’s input) multifove-
`ated images allows the user to determine how the data are
`progressively transmitted.
`Other advantages of the invention include that it allows
`the creation of the first dynamic and a more general class of
`multifoveated images. The present invention can use wave-
`let technology. The flexibility of the foveation approach
`based on wavelets allows oneto easily modify the following
`parameters of a multifoveated image: the position and shape
`of the basic foveal region(s), the maximum resolution at the
`foveal region(s), and the rate at which the resolution falls
`away. Wavelets can be replaced by any multi resolution
`pyramid schemes. But
`it seems that wavelet-based
`approachesare preferred as they are more flexible and have
`the best compression properties.
`invention’s use of
`Another advantage is the present
`dynamic data structures and associated algorithms. This
`helps optimize the “effective real time behavior” of the
`system. The dynamic data structures allow the use of “partial
`information” effectively. Here information is partial in the
`sense that
`the resolution at each pixel
`is only partially
`known. But as additional information is streamed in, the
`partial information can be augmented. Of course, this prin-
`ciple is a corollary to progressive transmission.
`Another advantage is that the dynamic data structures
`may be well exploited by the special architecture of the
`client program. For example, the client program may be
`multi-threaded with one thread (the “manager thread”)
`designed to manage resources (especially bandwidth
`resources). This manager
`is able to assess network
`congestion, and other relevant parameters, and translate any
`literal user request into the appropriate level of demand for
`the network. For example, when the user’s gaze point is
`focused on a region of an image, this may betranslated into
`requesting a certain amount, say, X bytes of data. But the
`manager can reduce this to a request over the network of
`(say) X/2 bytes of data if the traffic is congested, or if the
`user is panning very quickly.
`Another advantage of the present invention is that the
`server need send only that information which has not yet
`been served. This has the advantage of reducing communi-
`cationtraffic.
`
`Further objects and advantages of the invention will
`become apparent from a consideration of the drawings and
`ensuing description.
`BRIEF DESRIPTION OF DRAWINGS
`
`FIG. 1 shows an embodiment of the present invention
`including a server, and client(s) as well as their respective
`components.
`FIG. 2a illustrates one level of a particular wavelet
`transform, the Haar wavelet transform, which the server may
`execute in one embodiment of the present invention.
`FIG. 2b illustrates one level of the Haar inverse wavelet
`transform.
`
`FIG. 3 is a flowchart showing an algorithm the server may
`execute to perform a Haar wavelet transform in one embodi-
`ment of the present invention.
`
`

`

`US 6,182,114 B1
`
`5
`FIG. 4 shows Manager, Display and Network threads,
`which the client(s) may execute in one embodimentofthe
`present invention.
`FIG. 5 is a more detailed illustration of a portion of the
`Manager thread depicted in FIG. 4.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`FIG. 1 depicts an overview of the components in an
`exemplary embodimentof the present invention. A server 1
`is comprised of a storage device 3, a memory device 7 and
`a computer processing device 4. The storage device 3 can be
`implemented as, for example, an internal hard disk, Tape
`Cartridge, or CD-ROM. Thefaster access and greater stor-
`age capacity the storage device 3 provides, the more pref-
`erable the embodiment of the present
`invention. The
`memory device 7 can be implemented as, for example, a
`collection of RAM chips.
`The processing device 4 on the server 1 has network
`protocol processing element 12 and wavelet transform ele-
`ment 13 running off it. The processing device 4 can be
`implemented with a single microprocessor chip (such as an
`Intel Pentium chip), printed circuit board, several boards or
`other device. Again, the faster the speed of the processing
`device 4, the more preferable the embodiment. The network
`protocol processing element 12 can be implemented as a
`separate “software” (i.c., a program, sub-process) whose
`instructions are executed by the processing device 4. Typical
`examples of such protocols include TCP/IP (the Internet
`Protocol) or UDP (User Datagram Protocol). The wavelet
`transform element 13 can also be implemented as separate
`“software”(i.e., a program, sub-process) whoseinstructions
`are executed by the processing device 4.
`In a preferred embodimentof the present invention, the
`server 1 is a standard workstation or Pentium class system.
`Also, TCP/IP processing may be used to implement the
`network protocol processing element 12 because it reduces
`complexity of implementation. Although a TCP/IP imple-
`mentation is simplest, it is possible to use the UDPprotocol
`subject to some basic design changes. The relative advan-
`tage of using TCP/IP as against UDP is to be determined
`empirically. An additional advantage of using modern,stan-
`dard network protocols is that the server 1 can be con-
`structed without knowing anything aboutthe construction of
`its client(s) 2.
`According to the common design of modern computer
`systems,
`the most common embodiments of the present
`invention will also include an operating system running off
`the processing means device 4 of the server 1. Examples of
`operating systems include, without limitation, Windows 95,
`Unix and Windows NT. However,
`there is no reason a
`processing device 4 could not provide the functions of an
`“operating system”itself.
`The server 1 is connected to a client(s) 2 in a network.
`Typical examples of such servers 1 include image archive
`servers and map servers on the World Wide Web.
`The client(s) 2 is comprised of a storage device 3,
`memory device 7, display 5, user input device 6 and pro-
`cessing device 4. The storage device 3 can be implemented
`as, for example, an internal hard disks, Tape Cartridge, or
`CD-ROM. Thefaster access and greater storage capacity the
`storage device 3 provides, the more preferable the embodi-
`mentof the present invention. The memory device 7 can be
`implemented as, for example, a collection of RAM chips.
`The display 5 can be implemented as, for example, any
`monitor, whether analog or digital. The user input device 6
`
`10
`
`15
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`can be implemented as, for example, a keyboard, mouse,
`scanner or eye-tracking device.
`The client 2 also includes a processing device 4 with
`network protocol processing element 12 and inverse wavelet
`transform element means 14 runningoff it. The processing
`device 4 can be implemented as, for example, a single
`microprocessorchip (such as an Intel Pentium chip),printed
`circuit board, several boards or other device. Again, the
`faster the run time of the processing device 4, the more
`preferable the embodiment. The network protocol process-
`ing element 12 again can be implemented as a separate
`“software” (i.e., a program, sub-process) whoseinstructions
`are executed by the processing device 4. Again, TCP/IP
`processing may be used to implement the network protocol
`processing element 12. The inverse wavelet transform ele-
`ment 14 also may be implemented as separate “software.”
`Also running off the processing device 4 is a user input
`conversion mechanism 16, which also can be implemented
`as “software.”
`
`As with the server 1, according to the common design of
`modern computer systems, the most common embodiments
`of the present
`invention will also include an operating
`system running off the processing device 4 of the client(s) 2.
`In addition, if the server 1 is connected to the client(s) 2
`via a telephone system line or other systems/lines not
`carrying digital pulses, the server 1 and client(s) 2 both also
`include a communications converter device 15. A commu-
`
`nications converter device 15 can be implemented as, for
`example, a modem. The communications converter device
`15 converts digital pulses into the frequency/signals carried
`by the line and also converts the frequency/signals back into
`digital pulses, allowing digital communication.
`In the operation of the present invention, the extent of
`computational resources (e.g., storage capacity, speed) is a
`more important consideration for the server 1, which is
`generally shared by more than one client 2, than for the
`client(s) 2.
`In typical practice of the present invention, the storage
`device 3 of the server 1 holds an imagefile, even a very large
`imagefile. A numberof client 2 users will want to view the
`image.
`Prior to any communication in this regard between the
`server 1 and client(s) 2, the wavelet transform element 13 on
`the server 1 obtains a wavelet transform on the image and
`stores it in the storage device 3.
`There has been extensive research in the area of wavelet
`
`theory. However, briefly, to illustrate, “wavelets” are defined
`by a group of basis functions which, together with coeffi-
`cients dependant on an input function, can be used to
`approximate that function over varying scales, as well as
`represent the function exactly in the limit. Accordingly,
`wavelet coefficients can be categorized as “average” or
`“approximating coefficients’
`(which approximate the
`function) and “difference coefficients” (which can be used to
`reconstruct the original function exactly). The particular
`approximation used as well as the scale of approximation
`depend upon the wavelet bases chosen. Once a group of
`basis functions is chosen,
`the process of obtaining the
`relevant wavelet coefficients is called a wavelet transform.
`
`the Haar wavelet basis
`In the preferred embodiment,
`functions are used. Accordingly,
`in the preferred
`embodiment, the wavelet transform element 13 on the server
`1 performs a Haar wavelet transform ona file representation
`of the image stored in the storage device 3, and then stores
`the transform on the storage device 3. However,it is readily
`apparent to anyone skilled in the art that any of the wavelet
`
`

`

`US 6,182,114 B1
`
`the
`
`10
`
`15
`
`20
`
`25
`
`7
`family of transforms may be chosen to implement
`present invention.
`Note that once the wavelet transform is stored, the origi-
`nal image file need not be kept, as it can be reconstructed
`exactly from the transform.
`FIG. 2 illustrates one step of the Haar wavelet transform.
`Start with an n by n matrix of coefficients 17 whoseentries
`correspond to the numeric value of a color component(say,
`Red, Green or Blue) of a square screen image of n by n
`pixels. Divide the original matrix 17 into 2 by 2 blocks of
`four coefficients, and for each 2x2 block, label the coeffi-
`cient in the first column,first row “a,”; second column,first
`row “b”; second row, first column “c”; and second row,
`second column “d.”
`
`8
`matrix 17 image representation. (However, the number of
`bits in all the coefficients may differ from the numberofbits
`in the pixels. Applying data compressionto coefficients turns
`out to be generally more effective on coefficients.) If we
`assume the imageis very large, the transform matrices must
`be further decomposed into blocks when stored on the
`storage means3.
`FIG. 3 is a flowchart showing one possible implementa-
`tion of the wavelet transform element 13 which performs a
`wavelet transform on each color componentof the original
`image. As can be seen from the flowchart, the transform is
`halted when the size of the approximation matrix is 256x
`256, as this may be considered the lowest useful level of
`resolution.
`Once the wavelet transform element 13 stores a transform
`Then one step of the Haar wavelet transform creates four
`of the image(s) in the storage means 3 of the server 1, the
`n/2 by n/2 matrices. Thefirst is an n/2 by n/2 approximation
`server 1 is ready to communicate with client(s) 2.
`matrix 8 whose entries equal the “average” of the corre-
`In typical practice of the invention the client 2 user
`sponding 2 by 2 block of four coefficients in the original
`matrix 17. As is illustrated in FIG. 2, the coefficient entries
`initiates a session with an image server 1 and indicates an
`image the user wishes to view via user input means 6. The
`in the approximation matrix 8 are not necessarily equal to
`client 2 initiates a request for the 256 by 256 approximation
`the average of the corresponding fourcoefficients a, b, c and
`matrix 8 for each color component of the image and sends
`d (i.e., a'=(at+b+c+d)/4) in the original matrix 17. Instead,
`the request to the server 1 via network protocol processing
`here, the “average” is defined as (at+b+c+d)/2.
`element 12. The server 1 receives and processes the request
`The second is an n/2 by n/2 horizontal difference matrix
`via network protocol processing element 12. The server 1
`10 whose entries equal b'=(a+b-—c-d)/2, where a, b, c and d
`sends the 256 by 256 approximation matrices 8 for each
`are, respectively, the corresponding 2x2 block of four coef-
`color component of the image, whichthe client 2 receives in
`ficients in the original matrix 17. The third is an n/2 by n/2
`similar fashion. The processing device4 ofthe client 2 stores
`vertical difference matrix 9 whose entries equal c'=(a-—b+c-
`30
`the matrices in the storage device 3 and causes a display of
`d)/2, wherea, b, c anddare, respectively, the corresponding
`the 256 by 256 version of the image on the display 5. It
`2x2 block of four coefficients in the original matrix 17. The
`should be appreciated that the this low level of resolution
`fourth is an n/2 by n/2 diagonal difference matrix 11 whose
`requires little data and can be displayed quickly. In a map
`entries equal d'=(a-b-c+d)/2, where a, b, c and d are,
`server application, the 256 by 256, coarse resolution version
`respectively,
`the corresponding 2x2 block of four coeffi-
`of the image may be useful in a navigation window of the
`cients in the original matrix 17.
`display 5, as it can provide the user with a position indicator
`A few notes are worthy of consideration. First, the entries
`with respect to the overall image.
`a’, b', c', d' are the wavelet coefficients. The approximation
`A more detailed understanding of the operation of the
`matrix 8 is an approximationof the original matrix 17 (using
`client 2 will become apparent from the discussion of the
`the “average” of each 2x2 group of 4 pixels) and is one
`further, continuous operation of the client 2 below.
`fourth the size of the original matrix 17.
`Continuousoperation ofthe client(s) 2 is depicted in FIG.
`Second, each of the 2x2 blocks of four entries in the
`4. In the preferred embodiment, the client(s) 2 processing
`original matrix 17 has one corresponding entry in each of the
`device may be constructed using three “threads,” the Man-
`four n/2 by n/2 matrices. Accordingly, it can readily be seen
`ager thread 18,
`the Network Thread 19 and the Display
`from FIG. 2 that each of the 2x2 blocks of four entries in the
`Thread 20. Thread p