USOO7139794B2
`
`(12) United States Patent
`US 7,139,794 B2
`(10) Patent N0.:
`
`Levanon et al.
`(45) Date of Patent:
`Nov. 21, 2006
`
`(54) SYSTEM AND METHODS FOR NETWORK
`IMAGE DELIVERY WITH DYNAMIC
`VIEWING FRUSTUM OPTIMIZED FOR
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(58) Field of Classification Search ................ 709/203,
`709/2467247, 2177219; 345/4187420, 581,
`345/619; 382/103, 2325 2355 240
`See application file for complete search history.
`
`(75)
`
`Inventors:
`
`Isaac Levanon, Ramat Hasharn (IL);
`Yoni Lavi, Raanana (IL)
`
`(73) Assignee: 3-D-V-U Israel (2000) Ltd., Rannana
`(IL)
`
`*
`
`~
`.
`) Nome“
`
`(
`
`~
`~
`~
`~
`:22???goeilgfisgiffliifeffigrflélg
`U.S.C. 154(b) by 918 days.
`
`(21) Appl. No.: 10/035,981
`
`(22)
`
`Filed:
`
`Dec. 24, 2001
`
`(65)
`
`Prior Publication Data
`
`US 2002/0118224 A1
`
`A118 29, 2002
`
`Related U'S' Application Data
`(60) Provisional application No. 60/258,488, filed on Dec.
`273 20003 provisional application No. 60/258,489,
`filed on Dec. 273 20003 provisional application No.
`60/258,465, filed on Dec. 27, 2000, provisional appli-
`cation No. 60/258,468, filed on Dec. 27, 2000, prO-
`visional application No. 60/258,466, filed on Dec. 27,
`2000, provisional application No. 60/258,467, filed
`on Dec. 27, 2000.
`
`Int. Cl,
`(51)
`(2006.01)
`G06F 15/16
`(52) US. Cl.
`...................... 709/203; 709/246; 709/217;
`709/219; 345/420; 345/581; 382/232; 382/235
`
`(56)
`
`References Cited
`
`US. PATENT DOCUMENTS
`
`4,698,689 A * 10/1987 Tzou ..................... 358/42614
`
`10/ 1999 KnuPP -------------- 702/16
`5,966,672 A *
`
`1/2001 Yap et al. ............ 709/203
`6,182,114 B1*
`
`...... 709/236
`6,397,259 B1*
`5/2002 Lincke et al.
`..
`................. 382/305
`6,671,424 B1* 12/2003 Skoll et al.
`6,704,024 B1*
`3/2004 Robotham et al.
`.......... 345/581
`6 874 012 B1*
`3/2005 St. P'
`................... 709/207
`’
`’
`me
`* cited by examiner
`
`.
`.
`Primary ExamineriPhlllp B. Tran
`
`(57)
`
`ABSTRACT
`.
`.
`.
`.
`.
`.
`Dynamlc Vlsuallzatlon of lmage data prov1ded through a
`network communications channel is performed by a client
`system including a parcel request subsystem and a parcel
`rendering subsystem. The parcel request subsystem includes
`a parcel request queue and is operative to request discrete
`image data parcels in a priority order and to store received
`image data parcels in a parcel data store. The parcel request
`subsystem is responsive to an image parcel request 0f
`assigned priority to place the image parcel requestin the
`parcel request queue ordered 1n correspondence Wlth the
`assigned priority. The parcel rendering subsystemis COUPled
`to the parcel data store to selectively retrieve and render
`received image data parcels to a display memory. The parcel
`rfindering systenll provides tthehparcel reqiilestsubsystem with
`t e lmage parce request 0 t e aSSlgne prlorlty.
`
`2 Claims, 5 Drawing Sheets
`
`
`
`
`LOCAL PARCEL
`DATA STORE
`
`NETWORK
`
`PARCEL DATA
`
`
`PARCEL DATA
`
`PARCEL DATA
`PROCESSING
`RECEIVE/REQUEST
`RENDERING
`
`
`
`
`
`50
`
`VIEWING FRUSTUM
`
`
`NAVIGATION COMMANDS
`CONTROL
`
`
`
`52
`
`DISPLAY
`
`\40
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 1 of 5
`
`US 7,139,794 B2
`
`
`
`
`BINARY/XML
`DATA
`
`35
`
`CONVERSION
`
`
`
`12
`
`NETWORK
`
`SERVER
`
`
`
`8'
`NETWORK
`® DATASIORE
`
`
`K
`
`K-1
`
`.
`
`0 O
`
`K-N
`
`PRE-PRocEssm
`PARCELIMAGE DATA
`
`\
`
`30
`
`FIG. 2
`
`Microsoft Corp. Exhibit 1001
`
`SOURCE
`OVERLAY DATA
`
`34
`
`/V
`
`IMAGE DAIA
`
`Microsoft Corp. Exhibit 1001
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 2 of 5
`
`US 7,139,794 B2
`
`LOCAL PARCEL
`
`
`
`DATA STORE
`
`42
`
`NETWORK
`
`PARCEL DATA
`
`RECEIVE/REQUEST
`
`
`
`52
`
`DISPLAY
`
`
`
`
`
`MICRO
`GRAPHICS
`PROCESSOR
`MEMORY
`
` 64
`
`
`
`
`
`
`
`PARCEL DATA
`
`LI DATA CACHE
`
`66
`
`60
`
`FIG. 4
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 3 of 5
`
`US 7,139,794 B2
`
`NAVIGATION
`
`EVENTS
`
`m
`
`80
`
`FIG. 5
`
`
`
`
`NEIWORK
`
`ISSUE PRIORITT
`
`REQUESTS
`
`88
`
`90
`
`VIEWABLE PARCELS
`
`FOR UPDATE
`
`EXAMINE
`
`GUADTREES
`
`82
`DETERMINE I
`
`
`
`
`
`
`
`84
`
`
`
`
`REQUEST PARCEL
`
`DOWNLOADS
`
`STORE PARCEL To
`
`QUADTREE NODE
`
`
`
`..
`
`TRIM
`
`QUADTREE NODES
`
`
`
`94
`
`1".
`
`
`
`92
`
`
`WAIT FOR
`REQUEST THREAD
`
`FREE
`
`
`
`SELECT HIGHEST
`
`PIIIOIIm REQUEST
`WAITING
`
`
`
`
`100 j
`
`106
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 4 of 5
`
`US 7,139,794 B2
`
`ADJUST VIEWING
`
`
`
`FRUSTUM
`
`EVENTS
`
`NAVIGATION
`
`LOCATION AND
`
`ORIENTATION
`
`
`
`NEXT PARCEL
` 126
`
` PRIORITY
`
`SELECTION OF
`
`
`
`
`
`
`RENDER IMAGE
`PARCEL To
`
`DISPLAY MEMORY
`
`IF OVERLAY DATA
`
`(OOROs MATCH P
`
`128
`
`RENOER OVERLAY
`
`DATA To
`
`
`
`
`
`
`DISPLAY MEMORY
`
`130
`
`122
`
`124
`
`FIG. 7
`
`f 120
`
`START
`
`
`OUEUE
`
`
` CLEAR PRIORITY
` 142
`
`
`DETERMINE
`OPTIMAl DETAIL
`
`LEVEL L
`
`
`144
`
`146
`
`SPLIT MAP INTO
`POLYGONS P
`
`
`ASSIGN EXISTING
`PARCELS 0F MAX
`
`
`
`LEVEL D
`
`
`
` TRACE THROUGH
`
`OUAOTREE
`
`PARCELS
`
`FIG. 8
`
`140 /
`
`ASSIGN EXISTING
`
`PARCELS or
`
`148
`LEVEL L
`
`
`150
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`U.S. Patent
`
`Nov. 21, 2006
`
`Sheet 5 of 5
`
`US 7,139,794 B2
`
`FOR EACH
`POLYGDN P
`
`DETERMINE
`
`OPTIMAL DETAIL LEVEL L
`
`SKIP P OUTSIDE 0E
`VIEWING FRUSTUM
`
`PARCEL To P
`
`CLIP P To
`
`VIEWING FRUSTUM
`
`Bouuos
`
`TEXTURE MAP
`
`162
`
`164
`
`166
`
`If PARCEL
`
`LEVELD >= L
`
`IF PARCEL
`
`LEVELD <L
`
`168
`
`170
`
`160/
`
`FIG. 9
`
`176
`
`178
`
`CREATE CHILD
`
`NODE C
`
`172
`
`ADD PARCEL
`
`REQUEST
`
`DOWNLOAD
`
`174
`
`DETERMINE
`
`
`
`REQUEST PRIORIIY
`
`ASSIGN REQUEST
`
`PRIORITY
`
`DETERMINE CAMERA
`
`POSITION
`
`
`
`
`NEAREST
`
`
`DETERMINE
`
`
`POLYGON P
`
`
`
`184
`
`182
`
`
`
` DETERMINE
`NEAREST POINT A
`
`
`UN POLIGON P
`
` COMPUIE
`
`OPTIMAL DETAIL
`
`
`186
`
`188
`
`
`
`LEVEL L FOR A
`
` 192
`
`
`IFPOLYGONP
`D > L
`
`
`
`
`190
`
`DONE
`
` SRLIT
`
`Pouson P
`
`
`X180
`
`FIG. 10
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`US 7,139,794 B2
`
`1
`SYSTEM AND METHODS FOR NETWORK
`IMAGE DELIVERY WITH DYNAMIC
`VIEWING FRUSTUM OPTIMIZED FOR
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`This application claims the benefit of US. Provisional
`Application Nos. 60/258,488, 60/258,485, 60/258,465,
`60/258,468, 60/258,466, and 60/258,467, all filed Dec. 27,
`2000.
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`The present application is related to the co-pending appli-
`cation Optimized Image Delivery over Limited Bandwidth
`Communication Channels, Levanon et al., filed concurrently
`herewith and which is assigned to the Assignee of the
`present Application.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention is related to network based, image
`distribution systems and,
`in particular,
`to a system and
`methods for efficiently selecting and distributing image
`parcels through a narrowband or otherwise limited band-
`width communications channel to support presentation of
`high-resolution images subject to dynamic viewing frus-
`tums.
`
`2. Description of the Related Art
`The Internet and other network systems provide a unique
`opportunity to transmit complex images,
`typically large
`scale bit-maps, particularly those approaching photo-realis-
`tic levels, over large distances. In common application, the
`images are geographic,
`topographic, and other highly
`detailed maps. The data storage requirements and often
`proprietary nature of such images are such that conventional
`interests are to transfer the images on an as needed basis.
`In conventional fixed-site applications, the image data is
`transferred over a relatively high-bandwidth network to
`client computer systems that,
`in turn, render the image.
`Client systems typically implement a local image navigation
`system to provide zoom and pan functions based on user
`interaction. As well recognized problem with such conven-
`tional systems is that full resolution image presentation is
`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 resolution
`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 reso-
`lution method, permits an approximate image to be quickly
`presented with image details being continuously added over
`time.
`
`Tzou, in US. Pat. No. 4,698,689, describes a two-dimen-
`sional data transform system that supports transmission of
`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
`client computer is, however, highly compute intensive. In
`order to simplify the transform implementation and further
`reduce the latency of presenting any portion of an approxi-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`mate image, images are sub-divided into a regular array.
`This enables the inverse-transform function on the client,
`which is 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 et al.,
`US. Pat. No. 6,182,114, overcomes some of the foregoing
`problems. The Yap et al. system also employs a progressive
`encoding transform to compress the image transfer stream.
`The transform also operates on a subdivided image, but the
`division is indexed to the encoding level of the transform.
`The encoded transform coefficient data sets are, therefore, of
`constant size, which supports a modest improvement in the
`algorithmic performance of the inverse transform operation
`required on the client.
`Yap et al. adds utilization of client image panning or other
`image pointing input information to support a foveation-
`based operator to influence the retrieval order of the subdi-
`vided image blocks. This two-dimensional navigation infor-
`mation is used to identify a foveal region that is presumed
`to be the gaze point of a client system user. The foveation
`operator defines the corresponding image block as the center
`point of an ordered retrieval of coefficient sets representing
`a variable resolution image. The gaze point image block
`represents the area of highest image resolution, with reso-
`lution reduction 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 inten-
`sive function. Shifts in the gaze point can be responded to
`with relative 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
`the various conventional systems. In particular, the imple-
`mentation of conventional image visualization systems is
`generally unworkable for smaller, often dedicated or embed-
`ded, clients where use of image visualization would clearly
`be beneficial. Conventional approaches effectively presume
`that client systems have an excess of computing perfor-
`mance, memory and storage. Small clients, however, typi-
`cally have restricted performance processors with no dedi-
`cated floating-point support, little general purpose memory,
`and extremely limited persistent storage capabilities, par-
`ticularly relative to common image sizes. A personal digital
`assistant (PDA) is a characteristic small client. Embedded,
`low-cost kiosk and automobile navigation systems are other
`typical 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
`substantial computing system, conventional image visual-
`ization systems also presume that the client is supported by
`a complete operating system.
`Indeed, many expect and
`require an extensive set of graphics abstraction layers to be
`provided by the client system to support the presentation of
`the delivered image data. In general, these abstraction layers
`are conventionally considered required to handle the map-
`ping 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 corre-
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`US 7,139,794 B2
`
`3
`sponding image. Consequently, substantial processor per-
`formance and memory can be conventionally devoted to
`handling image data that is not or cannot be displayed.
`Another problem is that small clients are generally con-
`strained to generally to very limited network bandwidths,
`particularly when operating under wireless conditions. Such
`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 of small clients that are frequently constrained by
`limited bandwidth conditions. The conventionally realizable
`maximum 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 al. states
`that the described system can work over low bandwidth
`lines, little more than utilizing wavelet-based data compres-
`sion is advanced as permitting effective operation at low
`communications bandwidths. While reducing the amount of
`data that must be carried from the server to the client is
`
`significant, Yap et al. simply relies on the data packet
`transfer protocols to provide for an efficient transfer of the
`compressed image data. Reliable transport protocols, how-
`ever, merely mask packet losses and the resultant, some-
`times extended, recovery latencies. When such covered
`errors occur, however, the aggregate bandwidth of the con-
`nection is reduced and the client system can stall waiting for
`further image data to process.
`Consequently, there remains a need for an image visual-
`ization system that can support small client systems, place
`few requirements on the supporting client hardware and
`software resources, and efficiently utilize low to very low
`bandwidth network connections.
`
`SUMMARY OF THE INVENTION
`
`Thus, a general purpose of the present invention is to
`provide an efficient system and methods of optimally pre-
`senting image data on client systems with potentially limited
`processing performance, resources, and communications
`bandwidth.
`
`This is achieved in the present invention by providing for
`the dynamic visualization of image data provided through a
`network communications channel by a client system includ-
`ing a parcel request subsystem and a parcel rendering
`subsystem. The parcel request subsystem includes a parcel
`request queue and is operative to request discrete image data
`parcels in a priority order and to store received image data
`parcels in a parcel data store. The parcel request subsystem
`is responsive to an image parcel request of assigned priority
`to place the image parcel request in the parcel request queue
`ordered in correspondence with the assigned priority. The
`parcel rendering subsystem is coupled to the parcel data
`store to selectively retrieve and render received image data
`parcels to a display memory. The parcel rendering system
`provides the parcel request subsystem with the image parcel
`request of the assigned priority.
`An advantage of the present invention is that both image
`parcel data requests and the rendering of image data are
`optimized to address the display based on the display
`resolution of the client system.
`Another advantage of the present invention is that the
`prioritization of image parcel requests is based on an adapt-
`able parameter that minimizes the computational complexity
`of determining request prioritization and, in turn, the pro-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`gressive 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
`processing 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-
`loaded to conventional computer systems or embedded in
`conventional dedicated function devices, including portable
`devices, such as PDAs 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 con-
`nections. The software system of the present
`invention
`provides for re-prioritization of image parcel data requests
`and presentation in circumstances where the rate of point-
`of-view navigation exceeds the data request rate.
`Yet another advantage of the present invention is that
`image parcel data rendering is performed without requiring
`any complex underlying hardware or software display sub-
`system. 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 any underlying embedded or disk operating
`system and display drivers. Complex graphics and anima-
`tion abstraction layers are not required.
`Still another advantage of the present invention is that
`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 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. Sparse array overlay data,
`correlated positionally to the image parcel data and gener-
`ally insensitive to image parcel resolution, can be initially or
`progressively provided to the client for parsing and parallel
`presentation on a client display image view.
`
`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
`throughout 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
`presentation system constructed in accordance with a pre-
`ferred embodiment of the present invention;
`FIG. 4 provides a data block diagram illustrating an
`optimized 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 pro-
`cessing thread implemented in a preferred embodiment of
`the present invention;
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`US 7,139,794 B2
`
`5
`FIG. 6 provides a process flow diagram showing a net-
`work 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-
`ment of the present invention;
`FIG. 8 provides a process flow diagram showing the
`parcel map processing performed preliminary to the render-
`ing of image data parcels in accordance with a preferred
`embodiment of the present invention;
`FIG. 9 provides a process flow diagram detailing the
`rendering and progressive prioritization of image parcel data
`download requests in accordance with a preferred embodi-
`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 THE
`INVENTION
`
`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 intemet service providers (ISPs)z including a wireless
`connectivity provider 16. Client systems, including conven-
`tional workstations and personal computers 18 and smaller,
`typically dedicated function devices often linked through
`wireless 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, preferably implementing a small, embed-
`ded Web server, to a fixed or removable storage local image
`repository 24. Characteristically, the client system 18, 20
`displays are operated at some fixed resolution generally
`dependent on the underlying display 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 frustum 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
`systems 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 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 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
`landmark names, as well as representative 2 and 3D objects,
`graphical icons, decals, line segments, and text and other
`characters.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`The network image server system 30 preferably pre-
`processes the source image data 32 and source overlay data
`34 to forms preferred for storage and serving by the network
`server 12, 22. The source image data 32 is preferably
`pre-processed to obtain a series K1_N of derivative images of
`progressively lower image resolution. The source image
`data 32, corresponding to the series image K0,
`is also
`subdivided into a regular array such that each resulting
`image parcel of the array has 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 8K bytes. The
`resolution of the series K1_N of derivative images is prefer-
`ably related to that of the source image data 32 or prede-
`cessor 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 8K byte size.
`In the preferred embodiment of the present invention, the
`image parcels are further compressed and stored by the
`network server 12, 22. The preferred compression algorithm
`implements 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
`located by specification of a KD, X, Y value, representing the
`image set resolution index D and corresponding image array
`coordinate.
`
`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 encod-
`ing standard for geographic information developed by the
`OpenGIS Consortium (OGC; www.opengis.org), or a pro-
`prietary binary representation. The XML/GML representa-
`tion is preferred as permitting easier interchange between
`different commercial entities, while the binary representa-
`tion is preferred 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
`coordinate 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. Aparcel 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 XML/
`GML/binary overlay data to a local parcel data store 46.
`Preferably image data parcels are stored in conventional
`quad-tree data structures, where tree nodes of depth D
`correspond to the stored image parcels of a derivative image
`of resolution KB. The XML/GML/binary overlay data is
`preferably stored as a data object that can be subsequently
`read by a n XML/GML/binary parser implemented as part of
`the control block 44.
`
`The control block 44 is also responsible for decompress-
`ing 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
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`

`

`US 7,139,794 B2
`
`7
`acceleration hardware capabilities. In general, the relied on
`capabilities include bit-bit and related bit-oriented functions
`that are readily supported 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.
`
`Changes in the viewing frustum are determined from user
`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-dimen-
`sional fly-over navigation of the displayed image. The
`navigation controls support point-of-view rotation, transla-
`tion, attitude, 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
`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
`reflecting changes in the viewing frustum with minimum
`latency.
`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 used to deliver image parcels to the clients 18, 20. For the
`preferred embodiment., 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
`processing 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 parcel 62 is
`recognized as part of the present invention as being within
`the nominally smallest L1 data cache 66 size of conventional
`microprocessors 68. By ensuring that an uncompressed
`image parcel
`fits within the L1 cache,
`the texture map
`rendering algorithm can execute with minimum memory
`management overhead, thus optimally utilizing the process-
`ing capability of the microprocessor 68. Additionally, the
`writing of video data as a product of the rendering algorithm
`is uniform, thereby improving the apparent video stability of
`the display to the user.
`The client architecture 40 preferably executes in multiple
`process threads, with additional threads being utilized for
`individual network data request transactions. As shown in
`FIG. 5, an image parcel management process 80 implements
`a loop that determines image parcels subject to update 82
`and creates corresponding image parcel download requests
`84. Navigation events that alter the viewing frustum are
`considered in part to determine the current field of view. The
`quad-tree data structures are examined 86 to identify view-
`able image parcels of higher resolution than currently avail-
`able in the parcel data store 46.
`A pool of image request threads is preferably utilized to
`manage the image parcel download operations. In the pre-
`ferred embodiments of the present invention, a pool of four
`network request threads is utilized. The number of pool
`threads is determined as a balance between the available
`
`system resources and the network response latency, given
`the available bandwidth of the network connection. Empiri-
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`cally, for many wireless devices, four concurrent threads are
`able to support a relatively continuous delivery of image
`data parcels to the client 20 for display processing. As image
`parcels are progressively identified for download, a free
`request thread is employed to issue 88 a corresponding
`network request
`to the server 12, 22. When a network
`response is received, the corresponding thread recovers 90
`the image parcel data. The received image parcel is then
`stored 92 in a corresponding quad-tree data structure node.
`For small clients 20, the available memory for the parcel
`data store 46 is generally quite restricted. In order to make
`optimal use of the available memory, only currently view-
`able image parcels are subject to download. Where the size
`of the parcel data store 46 is not so restricted, this constraint
`can be relaxed.
`In either case, a memory management
`process 94 runs to monitor use of the parcel data store 46 and
`selectively remove image parcels to free memory for newly
`requested image parcels. Preferably, the memory manage-
`ment process 94 operates to preferentially remove image
`parcels that are the furthest from the current viewing frustum
`and that have the highest data structure depth. Child node
`image parcels are always removed before a parent node
`parcel is removed.
`A preferred network request management process 100 is
`shown in FIG. 6. The process 100 waits 102 on the existence
`of a download request in the priority request queue 52. The
`process 100 then waits on a network request pool thread to
`become free 104. When a network request thread becomes
`available, the process 100 examines 106 all of the pending
`requests in the prio