(12) United States Patent
`Yap et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006182114Bl
`US 6,182,114 B1
`Jan.30,2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) APPARATUS AND METHOD FOR
`REALTIME VISUALIZATION USING
`USER-DEFINED DYNAMIC, MULTI(cid:173)
`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
`
`Int. Cl? ...................................................... G06F 15/16
`(51)
`(52) U.S. Cl. ............................................. 709/203; 709/246
`(58) Field of Search ..................................... 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
`5,481,622 * 1!1996 Gerhardt et a!. ..................... 382/103
`5,568,598 * 10/1996 Mack et a!. ...................... 382/302 X
`5,710,835 * 1!1998 Bradley ................................ 382/233
`5,724,070 * 3/1998 Denninghoff eta!. ........... 382/235 X
`5,861,920 * 1!1999 Mead et a!. ...................... 382/232 X
`5,880,856 * 3/1999 Ferriere ............................ 382/240 X
`5,920,865 * 7/1999 Ariga ..................................... 707/10
`
`01HER PUBLICATIONS
`
`Tams Frajka et al., Progressive Image Coding with Spatially
`Variable Resolution, IEEE, Proceedings International Con(cid:173)
`ference on Image Processing 1997, Oct. 1997, vol. 1, pp.
`53-56.*
`
`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(cid:173)
`ematical Sciences, New York University, N.Y. U.S.A
`
`S.G. Mallat, "A Theory for Multiresolutional Signal Decom(cid:173)
`position ... ", IEEE Transactions on Pattern Analysis and
`Machine Intelligence,pp. 3-23, Jul. 1989, vol. 11, No. 7,
`IEEE Computer Society.
`
`News Release, "Wavelet Image Features",Summus'Wavelet
`Image Compression,Summus 14 pages.
`
`R.L. White et al., "Compression and Progressive Transmis(cid:173)
`sion of Astronomical Images", SPIE Technical Conference
`2199, 1994.
`
`(List continued on next page.)
`
`Primary Examiner-Zarni Maung
`Assistant Examiner-Patrice Winder
`(74) Attorney, Agent, or Firm-Baker Botts, L.L.P.
`
`(57)
`
`ABSTRACT
`
`A client apparatus which enables a realtime visualization of
`at least one image. The client apparatus includes a storage
`device which stores first data corresponding to a multifove(cid:173)
`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(cid:173)
`ment which generates third data corresponding to a multi(cid:173)
`foveated image using the first data, the second data and a
`foveation operator.
`
`8 Claims, 6 Drawing Sheets
`
`CONVERT USER INPUT /18
`
`(FOVEAL REGION) TO
`(MUL Tl RESOLUTION)
`REQUEST FOR
`COEFFICIENTS
`
`~
`
`DETERMINE FOVEAL
`REGION FROM USER
`INPUT
`
`1
`
`UPDATE DISPLAY
`WINDOWS
`(PROGRESSIVELY)
`BASED ON PYRAMID
`REPRESENTATION
`
`';a
`
`rj
`
`I
`
`SEND {MULTI
`RESOLUTION) REQUEST
`TO SERVER FOR
`COEFFICIENTS
`
`1
`
`II<ECEIVE COEFFICIENTS
`FROM SERVER
`
`I
`
`l
`
`r
`I w~~~~~~~~~~~~~~M
`
`ON COEFFICIENTS
`(IF NECESSARY)
`AND STORE
`(PROGRESSIVELY) IN
`PYAAMID
`
`~
`
`19
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`US 6,182,114 Bl
`Page 2
`
`01HER PUBLICATIONS
`
`E.L. Schwartz, "The Development of Specific Visual ... "
`Journal of Theoretical Biology, 69:655-685, 1977.
`F.S. Hill Jr. et al.,"Interactive Image Query ... " Computer
`Graphics, 17(3), 1983.
`T.H. Reeves et al., "Adaptive Foveation of MPEG Video",
`Proceedings of the 4th ACM International Multimedia Con(cid:173)
`ference, 1996.
`R.S. Wallace et al., "Space-variant image processing". Int'l.
`J. of Computer Vision, 13:1(1994) 71-90.
`
`E.L. Schwartz A quantitative model of the functional archi(cid:173)
`tecture: Biological cybernetics, 37(1980) 63-76.
`
`P. Kortum et al., "Implementation of a Foveated Image ...
`" Human Vision and Electronic Imagining, SPIE Proceed(cid:173)
`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
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`U.S. Patent
`
`Jan.30,2001
`
`Sheet 1 of 6
`
`US 6,182,114 B1
`
`[OJ
`
`(
`
`1
`
`16
`
`4
`
`FIG. 1
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`U.S. Patent
`
`Jan.30,2001
`
`Sheet 2 of 6
`
`US 6,182,114 B1
`
`N --------------~------------~
`
`a
`
`c
`
`17
`
`/
`
`b
`
`d
`
`1ir
`
`N/2
`
`L
`
`' "
`
`-+ N/2
`
`~
`
`8
`a' =
`\,.__
`~
`
`(a+ b + c +d)
`2
`
`b'=
`
`(a+ b- c- d)
`2
`
`v-
`
`1
`0
`
`..
`·~
`9
`\,.__
`~
`
`c' =
`
`(a- b + c- d)
`2
`
`d'=
`
`(a - b - c + d)
`2
`
`~
`
`11
`
`~~ v
`
`N/2 --------------.
`
`N/2
`
`FIG. 2A
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`U.S. Patent
`
`Jan.30,2001
`
`Sheet 3 of 6
`
`US 6,182,114 B1
`
`8=
`
`a' + b' + c' + d' b= a' + b' - c' - d'
`2
`2
`
`l---)7
`
`C=
`
`a' - b' + ci - d'
`2
`
`d= a' - b' - c' + d'
`2
`
`71\
`
`8
`
`~ a' =
`
`(a+ b + c +d)
`2
`
`b' = (a + b - c- d)
`2
`
`10
`~
`
`9
`~
`c' = (a - b + c -d)
`2
`
`d' = (a-b-c+ d)
`2
`
`11
`
`v
`
`FIG. 28
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`U.S. Patent
`
`Jan.30,2001
`
`Sheet 4 of 6
`
`US 6,182,114 B1
`
`I LET l=O t
`
`j
`LET N = NUMBER OF ROWS AND COLUMNS OF PIXELS IN THE (SQUARE) IMAGE
`~
`LET X = THE NEXT OF THE THREE COLOR COMPONENTS OF THE IMAGE (R, G OR B)
`~
`LET ML (X) = BE THE NxN MATRIX WHOSE COEFFICIENTS EQUAL THE NUMERIC
`VALUE OF THE X COMPONENT OF THE CORRESPONDING PIXEL OF THE IMAGE
`j
`
`LET ML+l(X) = BE THE N/2xN/2 MATRIX WHOSE COEFFICIENTS EQUAL THE -
`
`"AVERAGE" OF THE CORRESPONDING 2x2 BLOCK OF FOUR COEFFICIENTS IN ML(X)
`
`~
`LET HL+l(X) = BE THE N/2xN/2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`"HORIZONTAL DIFFERENCE" OF THE CORRESPONDING 2x2 BLOCK OF FOUR
`COEFFICIENTS IN ML{X)
`~
`LET VL+ 1(X) = BE THE N/2xN/2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`"VERTICAL DIFFERENCE" OF THE CORRESPONDING 2x2 BLOCK OF FOUR
`COEFFICIENTS IN ML(X)
`l
`LET DL+ 1{X) =BE THE N/2xN/2 MATRIX WHOSE COEFFICIENTS EQUAL THE
`"DIAGONAL DIFFERENCE" OF THE CORRESPONDING 2x2 BLOCK OF FOUR
`COEFFICIENTS iN ML{X)
`~
`
`l STORE HL+1(X), VL+1(X), DL+1(X) I
`j._
`1 L~l+1 I
`•
`I N~N/2 I
`~NO .
`s
`I STORE ML (X) I
`
`F I G. 3
`
`ARE THERE
`MORE COLOR COMPONENT(S)
`LEFT?
`
`YES
`
`NO
`
`I END I
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`U.S. Patent
`
`Jan.30,2001
`
`Sheet 5 of 6
`
`US 6,182,114 B1
`
`CONVERT USER INPUT v18
`(FOVEAL REGION) TO
`(MUL Tl RESOLUTION)
`REQUEST FOR
`COEFFICIENTS
`
`SEND (MULTI
`RESOLUTION) REQUEST
`TO SERVER FOR
`COEFFICIENTS
`
`DETERMINE FOVEAL
`REGION FROM USER ~
`INPUT
`
`UPDATE DISPLAY
`WINDOWS
`(PROGRESSIVELY)
`BASED ON PYRAMID
`REPRESENTATION
`
`I (cid:173)
`
`'\
`
`20
`
`HECEIVE COEFFICIENTS
`FROM SERVER
`
`PERFORM INVERSE
`WAVELET TRANSFORM
`ON COEFFICIENTS
`(IF NECESSARY)
`AND STORE
`(PROGRESSIVELY) IN
`PYRAMID
`
`~
`
`19
`
`FIG. 4
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`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 ML IS 128 x128
`MATRIX. THE LOWEST LEVEL OF
`RESOLUTION SUPPORTED
`
`200
`
`260
`
`/
`
`HAVETHE
`HORIZONTAL,
`VERTICAL AND
`DIAGONAL DIFFERENCE
`COEFFICIENTS NECESSARY
`TO RECONSTRUCT THE
`COEFFICIENTS IN ML(R),ML(G)
`ANDML(B) CORRESPONDING
`TO THE PIXELS IN
`THE FOVEAL
`REGION BEEN
`REQUESTED?
`
`HAVE THE
`COEFFICIENTS
`OF ML(R), MdG) AND
`ML(B) CORRESPONDING
`TO THE PIXELS
`IN THE FOVEAL
`REGION BEEN
`REQUESTED
`
`REQUEST THE
`COEFFICIENTS
`ACCORDING TO THE
`MASK
`
`REQUEST THE
`DIFFERENCE
`COEFFICIENTS
`ACCORDING TO THE
`MASK
`
`240
`
`280
`YES
`
`270
`
`RETURN TO
`MANAGER THREAD
`
`250
`
`FIG. 5
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`US 6,182,114 Bl
`
`1
`APPARATUS AND METHOD FOR
`REALTIME VISUALIZATION USING USER(cid:173)
`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(cid:173)
`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/ 15
`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. 20
`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 40
`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 45
`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 55
`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 60
`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(cid:173)
`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
`
`5
`
`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 pan is initiated.
`10 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
`25 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
`30 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
`35 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 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, "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
`50 does not appear to be a concern.
`T. H. Reeves and J. A. Robinson, "Adaptive Foveation of
`MPEG Video," Proceedings of the 4'h 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(cid:173)
`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
`65 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
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`US 6,182,114 Bl
`
`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 5
`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, 0. G. Staadt and R. Gatti, "Efficient trian(cid:173)
`gular surface approximations using wavelets and quadtree
`data structures", IEEE Trans, On Visualization and Com(cid:173)
`puter Graphics, 2(2), 1996, uses wavelets to produce mul(cid:173)
`tifoveated 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(cid:173)
`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 25
`is needed is a flexible foveation technique which allows one
`to modify the position and shape of the basic foveal regions,
`the maximum resolution at the foveal region and the rate at
`which the resolution falls away. This will allow the "thin(cid:173)
`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.
`
`SUMMARY OF THE INVENTION
`
`The present invention overcomes the disadvantages of 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) (i.e., a variable resolution image over its physical extent
`mimicking the spatial resolution of the user's eye about the
`approximated gaze point) updated in realtime.
`"Dynamic" means that the image resolution is also vary(cid:173)
`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- 55
`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 65
`pointer or eye tracking technology), the variable resolution
`over the space of the served up image(s).
`
`60
`
`20
`
`15
`
`4
`An additional advantage is that the invention demon(cid:173)
`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 been traditionally predetermined when the image
`file is prepared. The invention's use of dynamic (constantly
`10 changing in realtime based on the user's input) multifove(cid:173)
`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(cid:173)
`let technology. The flexibility of the foveation approach
`based on wavelets allows one to 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
`approaches are preferred as they are more flexible and have
`the best compression properties.
`Another advantage is the present invention's use of
`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
`30 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(cid:173)
`ciple is a corollary to progressive transmission.
`Another advantage is that the dynamic data structures
`35 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
`40 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 be translated into
`requesting a certain amount, say, X bytes of data. But the
`45 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
`50 been served. This has the advantage of reducing communi(cid:173)
`cation traffic.
`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(cid:173)
`ment of the present invention.
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`US 6,182,114 Bl
`
`5
`FIG. 4 shows Manager, Display and Network threads,
`which the client(s) may execute in one embodiment of the
`present invention.
`FIG. 5 is a more detailed illustration of a portion of the
`Manager thread depicted in FIG. 4.
`
`DETAILED DESCRIPTION OF 1HE
`INVENTION
`
`FIG. 1 depicts an overview of the components in an
`exemplary embodiment of 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. The faster access and greater stor(cid:173)
`age capacity the storage device 3 provides, the more pref(cid:173)
`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- 20
`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 25
`protocol processing element 12 can be implemented as a
`separate "software" (i.e., 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 30
`transform element 13 can also be implemented as separate
`"software" (i.e., a program, sub-process) whose instructions
`are executed by the processing device 4.
`In a preferred embodiment of 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(cid:173)
`mentation is simplest, it is possible to use the UDP protocol 40
`subject to some basic design changes. The relative advan(cid:173)
`tage of using TCP/IP as against UDP is to be determined
`empirically. An additional advantage of using modern, stan(cid:173)
`dard network protocols is that the server 1 can be con(cid:173)
`structed without knowing anything about the construction of 45
`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 50
`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. 55
`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(cid:173)
`cessing device 4. The storage device 3 can be implemented 60
`as, for example, an internal hard disks, Tape Cartridge, or
`CD-ROM. The faster access and greater storage capacity the
`storage device 3 provides, the more preferable the embodi(cid:173)
`ment of the present invention. The memory device 7 can be
`implemented as, for example, a collection of RAM chips. 65
`The display 5 can be implemented as, for example, any
`monitor, whether analog or digital. The user input device 6
`
`5
`
`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 running off it. The processing
`device 4 can be implemented as, for example, a single
`microprocessor chip (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
`10 preferable the embodiment. The network protocol process(cid:173)
`ing element 12 again can be implemented as a separate
`"software" (i.e., a program, sub-process) whose instructions
`are executed by the processing device 4. Again, TCP!IP
`processing may be used to implement the network protocol
`15 processing element 12. The inverse wavelet transform ele(cid:173)
`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(cid:173)
`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
`35 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 image file, even a very large
`image file. A number of 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(cid:173)
`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.
`In the preferred embodiment, the Haar wavelet basis
`functions are used. Accordingly, in the preferred
`embodiment, the wavelet transform element 13 on the server
`1 performs a Haar wavelet transform on a 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
`
`APPENDIX J
`
`Microsoft et al. Exhibit 1005
`
`

`
`7
`family of transforms may be chosen to implement the
`present invention.
`Note that once the wavelet transform is stored, the origi(cid:173)
`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 whose entries
`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(cid:173)
`cient in the first column, first row "a,"; second column, first
`row "b"; second row, first column "c"; and second row,
`second column "d."
`Then one step of the Haar wavelet transform creates four
`n/2 by n/2 matrices. The first is an n/2 by n/2 approximation
`matrix 8 whose entries equal the "average" of the corre(cid:173)
`sponding 2 by 2 block of four coefficients in the original
`matrix 17. As is illustrated in FIG. 2, the coefficient entries
`in the approximation matrix 8 are not necessarily equal to
`the average of the corresponding four coefficients a, b, c and
`d (i.e., a'=(a+b+c+d)/4) in the original matrix 17. Instead,
`here, the "average" is defined as (a+b+c+d)/2.
`The second is an n/2 by n/2 horizontal difference matrix
`10 whose entries equal b'=(a+b-c-d)/2, where a, b, c and d
`are, respectively, the corresponding 2x2 block of four coef(cid:173)
`ficients in the original matrix 17. The third is an n/2 by n/2
`vertical difference matrix 9 whose entries equal c'=(a-b+c(cid:173)
`d)/2, where a, b, c and dare, respectively, the corresponding
`2x2 block of four coefficients in the original matrix 17. The
`fourth is an n/2 by n/2 diagonal difference matrix 11 whose
`entries equal d'=(a-b-c+d)/2, where a, b, c and d are,
`respectively, the corresponding 2x2 block of four coeffi(cid:173)
`cients in the original matrix 17.
`A few notes are worthy of consideration. First, the entries
`a', b', c', d' are the wavelet coefficients. The approximation
`matrix 8 is an approximation of the original matrix 17 (using
`the "average" of each 2x2 group of 4 pixels) and is one
`fourth the size of the original matrix 17.
`Second, each of the 2x2 blocks of four entries in the
`original matrix 17 has one corresponding entry in each of the
`four n/2 by n/2 matrices. Accordingly, it can readily be seen
`from FIG. 2 that each of the 2x2 blocks of four entries in the
`original matrix 17 can be reconstructed exactly, and the
`transformation is invertible. Therefore, the original matrix
`17 representation of an image can be discarded during
`processing once the transform is obtained.
`Third, the transform can be repeated, each time starting
`with the last approximation matrix 8 obtained, and then
`discarding that approximation matrix 8 (which can be
`reconstructed) once the next wavelet step is obtained. Each
`step of th