111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US008924506B2
`
`c12) United States Patent
`Levanon et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,924,506 B2
`*Dec. 30, 2014
`
`(54) OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(75)
`
`Inventors: Isaac Levanon, Raanana, IL (US);
`Yonatan Lavi, Roanana, IL (US)
`
`(73) Assignee: Bradium Technologies LLC, Suffern,
`NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 865 days.
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`(21) Appl. No.: 13/027,929
`
`(22) Filed:
`
`Feb.15,2011
`
`(65)
`
`Prior Publication Data
`
`US 2011/0175914 Al
`
`Jul. 21, 2011
`
`(63)
`
`(60)
`
`Related U.S. Application Data
`
`Continuation-in-part of application No. 12/619,643,
`filed on Nov. 16,2009, now Pat. No. 7,908,343, which
`is a continuation of application No. 10/035,987, filed
`on Dec. 24, 2001, now Pat. No. 7,644,131.
`
`Provisional application No. 60/258,488, filed on Dec.
`27, 2000, provisional application No. 60/258,489,
`filed on Dec. 27, 2000, provisional application No.
`60/258,465, filed on Dec. 27, 2000, provisional
`application No. 60/258,468, filed on Dec. 27, 2000,
`provisional application No. 60/258,466, filed on Dec.
`27, 2000, provisional application No. 60/258,467,
`filed on Dec. 27, 2000.
`
`(51)
`
`Int. Cl.
`G06F 15116
`G06F 3114
`G06T 3140
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`(52) U.S. Cl.
`CPC
`
`G06F 311454 (2013.01); G06T 314092
`(2013.01); G09G 2340/02 (2013.01); G09G
`2350/00 (2013.01)
`........... 709/217; 709/203; 345/625; 382/232;
`382/305
`
`USPC
`
`(58) Field of Classification Search
`CPC ..... G06T 3/4092; G09G 2340/02; G06F 3/14
`USPC ................. 709/202,203,217,230,246, 247;
`345/625; 382/232, 305
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`5,929,860 A
`6,182,114 B1
`
`7/1999 Hoppe
`112001 Yap et al.
`(Continued)
`
`OTHER PUBLICATIONS
`
`Hoppe, H. "Progressive Meshes", SIGGRAPH '96: Proceedings of
`the 23rd annual conference on Computer graphics and interactive
`techniques, 1996, pp. 99-108.
`Primary Examiner- David Lazaro
`(74) Attorney, Agent, or Firm- Anatoly S. Weiser, Esq.;
`Acuity Law Group, P.C.
`ABSTRACT
`(57)
`Large-scale images are retrieved over network communica(cid:173)
`tions channels for display on a client device by selecting an
`update image parcel relative to an operator controlled image
`viewpoint to display via the client device. A request is pre(cid:173)
`pared for the update image parcel and associated with a
`request queue for subsequent issuance over a communica(cid:173)
`tions channel. The update image parcel is received from the
`communications channel and displayed as a discrete portion
`of the predetermined image. The update image parcel opti(cid:173)
`mally has a fixed pixel array size, is received in a single and or
`plurality of network data packets, and were the fixed pixel
`array may be constrained to a resolution less than or equal to
`the resolution of the client device display.
`21 Claims, 5 Drawing Sheets
`
`f'~r·l'hlUSSW
`hwn.!wn:Dw
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6,212,301 B1
`6,314,452 B1
`6,326,965 B1
`
`4/2001 Warner et a!.
`1112001 Dekel et a!.
`12/2001 Castelli eta!.
`
`6,345,279 B1
`6,346,938 B1
`6,397,259 B1
`6,608,933 B1
`6,704,024 B2
`6,711,297 B1
`6,801,665 B1
`
`212002 Li eta!.
`212002 Chan eta!.
`5/2002 Lincke et al.
`8/2003 Dowell et al.
`3/2004 Robotharn eta!.
`3/2004 Chang eta!.
`10/2004 Atsumi et al.
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 1 of 5
`
`US 8,924,506 B2
`
`·~~~w~~,:s::;:::::s:::..~~~:'"''·
`'~"<:~::~~-----"~-~>
`34
`
`$(ltWU
`
`StJ~l~f}
`!#..~}~ tht>\
`
`:i2
`
`A
`/
`
`/
`l
`/
`
`P!lr"Pwuss~:o
`f'iWOJlMAH UiHA
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 2 of 5
`
`US 8,924,506 B2
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 3 of 5
`
`US 8,924,506 B2
`
`82
`
`NAVIGATION __ ._.
`EVENlS
`80~
`
`FIG. 5
`
`84
`
`NE1WORK
`
`88
`
`REQUEST PARCEL
`DOWNLOADS
`
`·····
`
`..
`
`STORE PARCEL TO
`QUAD TREE NODE
`
`.. •
`
`92
`
`90
`
`94
`
`WAIT fOR
`SELEG HIGHEST
`REQUEST THREAD 1--_.. PRIORITY REOUEST
`fREE
`WAITING
`
`102
`
`104
`
`110
`
`fiG. 6
`
`100_}
`
`106
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 4 of 5
`
`US 8,924,506 B2
`
`?l\l!:ll\Hl'
`Sm:mu~of
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 5 of 5
`
`US 8,924,506 B2
`
`-~ '
`•'1 f~J'\ _______ ,,,-----·'/
`
`:.: · .. ..> ...... ~~
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`This application is a continuation in part of and claims
`priority under 35 USC 120 to U.S. patent application Ser. No.
`12/619,643 filed on Nov. 16, 2009 now U.S. Pat. No. 7,908,
`343 which in tum in a continuation of and claims priority
`under 35 USC 120 to U.S. patent application Ser. No. 10/035,
`987 filed on Dec. 24, 2001 and entitled "Optimized image
`delivery over limited bandwidth communication channels"
`(that now issued on Jan. 5, 2010 as U.S. Pat. No. 7,644,131)
`which in tum claims the benefitnnder35 USC 119(e) ofU.S. 15
`Provisional Application Nos. 60/258,488, 60/258,489,
`60/258,465, 60/258,468, 60/258,466, and 60/258,467, all
`filed Dec. 27, 2000, all of which are incorporated herein by
`reference. The present application is also related to the co(cid:173)
`pending application Ser. No. 10/035,981 entitled "System
`and Methods for Network Image Delivery with Dynamic
`Viewing Frustum Optimized for Limited Bandwidth Com(cid:173)
`munication Channels, Levanon eta!., filed on Dec. 24, 2001
`(now U.S. Pat. No. 7,139,794 issued on Nov. 21, 2006 and
`which is assigned to the Assignee of the present Application. 25
`
`2
`differential coefficients to represent an image. Subsequent
`transmitted coefficient sets are progressively accumulated
`with prior transmitted sets to provide a succeedingly refined
`image. The inverse-transform function performed by the cli(cid:173)
`ent computer is, however, highly compute intensive. In order
`to simplifY the transform implementation and further reduce
`the latency of presenting any portion of an approximate
`image, images are sub-divided into a regular array. This
`enables the inverse-transform function on the client, which is
`10 time-critical, to deal with substantially smaller coefficient
`data sets. The array size in Tzou is fixed, which leads to
`progressively larger coefficient data sets as the detail level of
`the image increases. Consequently, there is an inherently
`increasing latency in resolving finer levels of detail.
`An image visualization system proposed by Yap eta!., U.S.
`Pat. No. 6,182,114, overcomes some of the foregoing prob(cid:173)
`lems. The Yap eta!. system also employs a progressive encod(cid:173)
`ing transform to compress the image transfer stream. The
`transform also operates on a subdivided image, but the divi-
`20 sian is indexed to the encoding level of the transform. The
`encoded transform coefficient data sets are, therefore, of con(cid:173)
`stant size, which supports a modest improvement in the algo(cid:173)
`rithmic performance of the inverse transform operation
`required on the client.
`Yap eta!. adds utilization of client image panning or other
`image pointing input information to support a foveation(cid:173)
`based operator to influence the retrieval order of the subdi(cid:173)
`vided image blocks. This two-dimensional navigation infor(cid:173)
`mation is used to identifY a foveal region that is presumed to
`30 be the gaze point of a client system user. The foveation opera(cid:173)
`tor defines the corresponding image block as the center point
`of an ordered retrieval of coefficient sets representing a vari(cid:173)
`able resolution image. The gaze point image block represents
`the area of highest image resolution, with resolution reduc-
`35 tion as a function of distance from the gaze point determined
`by the foveation operator. This technique thus progressively
`builds image resolution at the gaze point and succeedingly
`outward based on a relatively compute intensive function.
`Shifts in the gaze point can be responded to with relative
`40 speed by preferentially retrieving coefficient sets at and near
`the new foveal region.
`Significant problems remain in permitting the convenient
`and effective use of complex images by many different types
`of client systems, even with the improvements provided by
`45 the various conventional systems. In particular, the imple(cid:173)
`mentation of conventional image visualization systems is
`generally unworkable for smaller, often dedicated or embed(cid:173)
`ded, clients where use of image visualization would clearly be
`beneficial. Conventional approaches effectively presume that
`50 client systems have an excess of computing performance,
`memory and storage. Small clients, however, typically have
`restricted performance processors with possibly no dedicated
`floating-point support, little general purpose memory, and
`extremely limited persistent storage capabilities, particularly
`55 relative to common image sizes. A mobile computing device
`such as mobile phone, smart phone, tablet and or personal
`digital assistant (PDA) is a characteristic small client.
`Embedded, low-cost kiosk, automobile navigation systems
`and or Internet enabled/connected TV are other typical
`60 examples. Such systems are not readily capable, if at all, of
`performing complex, compute-intensive Fourier or wavelet
`transforms, particularly within a highly restricted memory
`address space.
`As a consequence of the presumption that the client is a
`65 substantial computing system, conventional image visualiza(cid:173)
`tion systems also presume that the client is supported by a
`complete operating system. Indeed, many expect and require
`
`FIELD
`
`The disclosure is related to network based, image distribu(cid:173)
`tion systems and, in particular, to a system and methods for
`efficiently selecting and distributing image parcels through a
`narrowband or otherwise limited bandwidth communications
`channel to support presentation of high-resolution images
`subject to dynamic viewing frustums.
`
`BACKGROUND
`
`The Internet and or other network systems may provide a
`unique opportunity to transmit for example complex images,
`typically large scale bit-maps, particularly those approaching
`photo-realistic levels, over large area and or distances. In
`common application, the images may be geographic, topo(cid:173)
`graphic, and or other highly detailed maps. The data storage
`requirements and often proprietary nature of such images
`could be such that conventional interests may be to transfer
`the images on an as-needed basis.
`In conventional fixed-site applications, the image data may
`be transferred over a relatively high-bandwidth network to
`client computer systems that in tum, may render the image.
`Client systems may typically implement a local image navi(cid:173)
`gation system to provide zoom and or pan functions based on
`user interaction. As well recognized problem with such con(cid:173)
`ventional systems could be that full resolution image presen(cid:173)
`tation may be subject to the inherent transfer latency of the
`network. Different conventional systems have been proposed
`to reduce the latency affect by transmitting the image in
`highly compressed formats that support progressive resolu(cid:173)
`tion build-up of the image within the current client field of
`view. Using a transform compressed image transfer function
`increases the field of the image that can be transferred over a
`fixed bandwidth network in unit time. Progressive image
`resolution transmission, typically using a differential resolu(cid:173)
`tion method, permits an approximate image to be quickly
`presented with image details being continuously added over
`time.
`Tzou, in U.S. Pat. No. 4,698,689, describes a two-dimen(cid:173)
`sional data transform system that supports transmission of
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`3
`an extensive set of graphics abstraction layers to be provided
`by the client system to support the presentation of the deliv(cid:173)
`ered image data. In general, these abstraction layers are con(cid:173)
`ventionally considered required to handle the mapping of the
`image data resolution to the display resolution capabilities of
`the client system. That is, resolution resolved image data
`provided to the client is unconstrained by any limitation in the
`client system to actually display the corresponding image.
`Consequently,
`substantial processor performance and
`memory can be conventionally devoted to handling image 10
`data that is not or cannot be displayed.
`Another problem is that small clients are generally con(cid:173)
`strained to generally to very limited network bandwidths,
`particularly when operating nnder wireless conditions. Such 15
`limited bandwidth conditions may exist due to either the
`direct technological constraints dictated by the use of a low
`bandwidth data channel or indirect constraints imposed on
`relatively high-bandwidth channels by high concurrent user
`loads. Cellular connected PDAs and webphones are examples 20
`of small clients that are frequently constrained by limited
`bandwidth conditions. The conventionally realizable maxi(cid:173)
`mum network transmission bandwidth for such small devices
`may range from below one kilobit per second to several tens
`of kilobits per second. While Yap et a!. states that the
`described system can work over low bandwidth lines, little
`more than utilizing wavelet-based data compression is
`advanced as permitting effective operation at low communi(cid:173)
`cations bandwidths. While reducing the amount of data that
`must be carried from the server to the client is significant, Yap
`et a!. simply relies on the data packet transfer protocols to
`provide for an efficient transfer of the compressed image data.
`Reliable transport protocols, however, merely mask packet
`losses and the resultant, sometimes extended, recovery laten(cid:173)
`cies. When such covered errors occur, however, the aggregate
`bandwidth of the connection is reduced and the client system
`can stall waiting for further image data to process.
`Consequently, there remains a need for an image visual(cid:173)
`ization system that can support small client systems, place
`few requirements on the supporting client hardware and soft(cid:173)
`ware resources, and efficiently utilize low to very low band(cid:173)
`width network connections.
`
`SUMMARY
`
`4
`Another advantage of the present invention is that the pri(cid:173)
`oritization of image parcel requests is based on an adaptable
`parameter that minimizes the computational complexity of
`determining request prioritization and, in tum, the progres(cid:173)
`sive improvement in display resolution within the field of
`view presented on a client display.
`A further advantage of the present invention is that the
`client software system requires relatively minimal client pro(cid:173)
`cessing power and storage capacity. Compute intensive
`numerical calculations are minimally required and image
`parcel data is compactly stored in efficient data structures.
`The client software system is very small and easily down(cid:173)
`loaded to conventional computer systems or embedded in
`conventional dedicated function devices, including portable
`devices, such as PDAs, tablets and webphones.
`Still another advantage of the present invention is that
`image parcel data requests and presentation can be readily
`optimized to use low to very low bandwidth network connec(cid:173)
`tions. The software system of the present invention provides
`for re-prioritization of image parcel data requests and presen-
`tation in circumstances where the rate of point-of-view navi(cid:173)
`gation exceeds the data request rate.
`Yet another advantage of the present invention is that image
`25 parcel data rendering is performed without requiring any
`complex underlying hardware or software display subsystem.
`The client software system of the present invention includes a
`bit-map rendering engine that draws directly to the video
`memory of the display, thus placing minimal requirements on
`30 any underlying embedded or disk operating system and dis(cid:173)
`play drivers. Complex graphics and animation abstraction
`layers are not required.
`Still another advantage of the present invention is that
`35 image parcel block compression is used to obtain fixed size
`transmission data blocks. Image parcel data is recoverable
`from transmission data using a relatively simple client
`decompression algorithm. Using fixed size transmission data
`blocks enables image data parcels to be delivered to the client
`40 in bounded time frames.
`A yet further advantage of the present invention is that
`multiple data forms can be transferred to the client software
`system for concurrent display. Array overlay data, correlated
`positionally to the image parcel data and generally insensitive
`45 to image parcel resolution, can be initially or progressively
`provided to the client for parsing and parallel presentation on
`a client display image view.
`
`Thus, a general purpose of the present invention is to pro(cid:173)
`vide an efficient system and methods of optimally presenting
`image data on client systems with potentially limited process(cid:173)
`ing performance, resources, and communications bandwidth.
`This is achieved in the present invention by providing for 50
`the retrieval oflarge-scale images over network communica(cid:173)
`tions channels for display on a client device by selecting an
`update image parcel relative to an operator controlled image
`viewpoint to display via the client device. A request is pre(cid:173)
`pared for the update image parcel and associated with a 55
`request queue for subsequent issuance over a communica(cid:173)
`tions channel. The update image parcel is received from the
`communications channel and displayed as a discrete portion
`of the predetermined image. The update image parcel opti(cid:173)
`mally has a fixed pixel array size, is received in a single and or 60
`plurality of network data packets, and were the fixed pixel
`array may be constrained to a resolution less than or equal to
`the resolution of the client device display.
`An advantage of the present invention is that both image
`parcel data requests and the rendering of image data are 65
`optimized to address the display based on the display resolu(cid:173)
`tion of the client system.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other advantages and features of the present
`invention will become better understood upon consideration
`of the following detailed description of the invention when
`considered in connection with the accompanying drawings,
`in which like reference numerals designate like parts through(cid:173)
`out the figures thereof, and wherein:
`FIG. 1 depicts a preferred system environment within
`which various embodiments of the present invention can be
`utilized;
`FIG. 2 is a block diagram illustrating the preparation of
`image parcel and overlay data set that are to be stored by and
`served from a network server system in accordance with a
`preferred embodiment of the present invention;
`FIG. 3 is a block diagram of a client system image presen(cid:173)
`tation system constructed in accordance with a preferred
`embodiment of the present invention;
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`5
`FIG. 4 provides a data block diagram illustrating an opti(cid:173)
`mized client image block processing path constructed in
`accordance with a preferred embodiment of the present
`invention;
`FIG. 5 is a process flow diagram showing a main process(cid:173)
`ing thread implemented in a preferred embodiment of the
`present invention;
`FIG. 6 provides a process flow diagram showing a network
`request thread implemented in a preferred embodiment of the
`present invention;
`FIG. 7 provides a process flow diagram showing a display
`image rendering thread implemented in a preferred embodi(cid:173)
`ment of the present invention;
`FIG. 8 provides a process flow diagram showing the parcel
`map processing performed preliminary to the rendering of
`image data parcels in accordance with a preferred embodi(cid:173)
`ment of the present invention;
`FIG. 9 provides a process flow diagram detailing the ren(cid:173)
`dering and progressive prioritization of image parcel data
`download requests in accordance with a preferred embodi(cid:173)
`ment of the present invention; and
`FIG. 10 provides a process flow diagram detailing the
`determination of an optimal detail level for image parcel
`presentation for a current viewing frustum in accordance with
`a preferred embodiment of the present invention.
`
`DETAILED DESCRIPTION OF ONE OR MORE
`EMBODIMENTS
`
`The preferred operational environment 10 of the present
`invention is generally shown in FIG. 1. A network server
`system 12, operating as a data store and server of image data,
`is responsive to requests received through a communications
`network, such as the Internet 14 generally and various tiers of
`internet service providers (ISPs) including a wireless connec(cid:173)
`tivity provider 16. Client systems, including conventional
`workstations and personal computers 18 and smaller, typi(cid:173)
`cally dedicated function devices often linked through wire(cid:173)
`less network connections, such as PDAs, webphones 20, and
`automobile navigation systems, source image requests to the
`network server 12, provide a client display and enable image
`navigational input by a user of the client system. Alternately,
`a dedicated function client system 20 may be connected
`through a separate or plug-in local network server 22, pref(cid:173)
`erably implementing a small, embedded Web server, to a fixed
`or removable storage local image repository 24. Characteris(cid:173)
`tically, the client system 18, 20 displays are operated at some
`fixed resolution generally dependent on the underlying dis(cid:173)
`play hardware of the client systems 18, 20.
`The image navigation capability supported by the present
`invention encompasses a viewing frustum placed within a
`three-dimensional space over the imaged displayed on the
`client 18, 20. Client user navigational inputs are supported to
`control the x, y lateral, rotational and z height positioning of
`the viewing frustnm over the image as well as the camera
`angle of incidence relative to the plane of the image. To effect
`these controls, the software implemented on the client sys(cid:173)
`tems 18, 20 supports a three-dimensional transform of the
`image data provided from the server 12, 22.
`In accordance with the preferred embodiments of the
`present invention, as generally illustrated in FIG. 2, a network
`image server system 30 stores a combination of source image
`data 32 and source overlay data 34. The source image data 32
`is typically high-resolution bit-map raster map and or satellite
`imagery of geographic regions, which can be obtained from
`commercial suppliers. The overlay image data 34 is typically
`a discrete data file providing image annotation information at
`
`6
`defined coordinates relative to the source image data 32. In
`the preferred embodiments of the present invention, image
`annotations include, for example, street, building and land(cid:173)
`mark names, as well as representative 2 and 3D objects,
`graphical icons, decals, line segments, and or text and or other
`characters, graphics and or other media.
`The network image server system 30 preferably pre-pro(cid:173)
`cesses the source image data 32 and or source overlay data 34
`to forms preferred for storage and serving by the network
`10 server 12, 22. The source image data 32 is preferably pre(cid:173)
`processed to obtain a series K.sub.1-N of derivative images of
`progressively lower image resolution. The source image data
`32, corresponding to the series image K.sub.O, is also subdi(cid:173)
`vided into a regular array such that each resulting image
`15 parcel of the array has for example a 64 by 64 pixel resolution
`where the image data has a color or bit per pixel depth of 16
`bits, which represents a data parcel size of SK bytes. The
`resolution of the series K.sub.1-N of derivative images is
`preferably related to that of the source image data 32 or
`20 predecessor image in the series by a factor of four. The array
`subdivision is likewise related by a factor of four such that
`each image parcel is of a fixed SK byte size.
`In the preferred embodiment of the present invention, the
`image parcels are further compressed and stored by the net-
`25 work server 12, 22. The preferred compression algorithm
`may implements for example a fixed 4:1 compression ratio
`such that each compressed and stored image parcel has a fixed
`2K byte size. The image parcels are preferably stored in a file
`of defined configuration such that any image parcel can be
`30 located by specification of a K.sub.D, X, Y value, represent(cid:173)
`ing the image set resolution index D and corresponding image
`array coordinate.
`In other implementations, the image array dimensions
`(which as 64x64 above) may be powers of two so that the
`35 image array can be used in texture mapping efficiently. To
`accommodate different data parcel size than the 2 KByte
`associated with 64x64 pixel parcel dimension described
`above and other communication protocol and overhead
`requirements, to accommodate transmission through other
`40 than a 3 KByte per second transmission channel, the present
`invention may use larger compression ratios that takes, for
`example, a 128x128 or 256x256 pixel parcel dimension and
`compresses it to meet the 3 KByte per second transmission
`channel, or other communication bandwidth used to stream
`45 the parcel.
`The system may also accommodate different and larger
`data parcel sizes as transmission protocols, compression ratio
`achieved and micro-architectures of the client computers
`change. For purposes above, the data content was a pixel array
`50 representing image data. Where the data parcel content is
`vector, text or other data that may subject to different client
`system design factors, other parcel sizes may be used. Fur(cid:173)
`thermore, the parcel sizes can be different between the server
`and the client. For example the server may create parcels or
`55 hold parcels, for streaming with 256x256 pixel parcel dimen(cid:173)
`sion and the client my render them as 64x64. In addition,
`parcels sizes on different servers may vary from one server to
`another and from the client side rendering. In the system, each
`grid is treated as a sparse data array that can be progressively
`60 revised to increase the resolution of the grid and thereby the
`level of detail presented by the grid.
`The source overlay data 34 is preferably pre-processed 36
`into either an open XML format, such as the Geography
`Markup Language (GML ), which is an XML based encoding
`65 standard for geographic information developed by the
`OpenGIS Consortium (OGC; www.opengis.org), or a propri(cid:173)
`etary binary representation. The XMLIGML representation is
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`7
`preferred as permitting easier interchange between different
`commercial entities, while the binary representation is pre(cid:173)
`ferred as more compact and readily transferable to a client
`system 18, 20. In both cases, the source overlay data 34 is
`pre-processed to contain the annotation data preferably in a
`resolution independent form associated with a display coor(cid:173)
`dinate specification relative to the source image data 32. The
`XML, GML or binary overlay data may be compressed prior
`to storage on the network server 12, 22.
`The preferred architecture 40 of a client system 18, 20, for
`purposes of implementing the present invention, is shown in
`FIG. 3. The architecture 40 is preferably implemented by a
`software plug-in or application executed by the client system
`18, 20 and that utilizes basic software and hardware services
`provided by the client system 18, 20. A parcel request client
`42 preferably implements an HTML client that supports
`HTML-based interactions with the server 12, 22 using the
`underlying network protocol stack and hardware network
`interface provided by the client systems 18, 20. A central
`parcel processing control block 44 preferably implements the
`client process and control algorithms. The control block 44
`directs the transfer of received image parcels and XMLI
`GML!binary overlay data to a local parcel data store 46. Local
`parcel data store 46 may also act for example as local cache
`weather the entire data or part of it is in dynamic and/or static
`cache. Preferably image data parcels are stored in conven(cid:173)
`tional quad-tree data structures, where tree nodes of depth D
`correspond to the stored image parcels of a derivative image
`of resolution KD. The XMLIGML!binary overlay data is
`preferably stored as a data object that can be subsequently
`read by an XMLIGML/binary parser implemented as part of
`the control block 44.
`The control block 44 is also responsible for decompressing
`and directing the rendering of image parcels to a local display
`by a rendering engine 48. Preferably, the rendering engine 48
`writes to the video memory of the underlying client display
`hardware relying on only generic graphics acceleration hard(cid:173)
`ware capabilities and may take advantage of more advanced
`graphics acceleration hardware when available in the client
`system 18, 20. In general, the relied on capabilities include
`bit-bit and related bit-oriented functions that are readily sup(cid:173)
`ported by current conventional display controller hardware.
`The rendering engine 48 is optimized to perform image parcel
`texture mapping without reliance on complex floating point
`operations, permitting even relatively simple processors to
`efficiently execute the rendering engine 48. The rendering
`engine 48 may take advantage of floating point operations
`when available in the client system 18, 20.
`Changes in the viewing frustum are determined from user 50
`input navigation commands by a frustum navigation block
`50. In the preferred embodiments of the present invention, the
`input navigation controls are modeled for three-dimensional
`fly-over navigation of the displayed image. The navigation
`controls support point-of-view rotation, translation, attitude, 55
`and altitude over the displayed image. The effective change in
`viewing frustum as determined by the frustum navigation
`block 50 is provided to the control block 44.
`The control block 44, based in part on changes in the
`viewing frustum, determines the ordered priority of image 60
`parcels to be requested from the server 12, 22 to support the
`progressive rendering of the displayed image. The image
`parcel requests are placed in a request queue 52 for issuance
`by the parcel request client 42. Preferably, the pending
`requests are issued in priority order, thereby dynamically 65
`reflecting changes in the viewing frustum with minimum
`latency.
`
`8
`In various implementations of the parcel processing, each
`data parcel is independently processable by the client system
`18,20, which is enabled by the selection and server-side pro(cid:173)
`cessing used to prepare a parcel for transmission, thus pro(cid:173)
`viding for on-demand real-time parcel processing and cre(cid:173)
`ation on the server side for streaming based on the client
`request and not only for pre-processed parcel creation for
`retrieval for streaming from the server. Thus, the system can
`use both pre-processed parcels on the server and on-demand
`10 real-time creation of such parcels on the server side for
`streaming to the client.
`An optimal image parcel data flow 60, as configured for use
`in the preferred embodiments of the present invention, is
`shown in FIG. 4. Preferably, the TCP/IP network protocol is
`15 used to deliver image parcels to the clients 18, 20. For the
`preferred embodiments, where network bandwidth is limited
`or very limited, entire image parcels are preferably delivered
`in corresponding data packets. This preference maximizes
`data delivery while avoiding the substantial latency and pro-
`20 cessing overhead of managing image parcel data split over
`multiple network packets. Thus, a 2K byte compressed image
`parcel 62 is delivered as the data payload of a TCP/IP packet
`64. Uncompressed, the 8K byte image parcel62 is r