111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007908343B2
`
`c12) United States Patent
`Levanon et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,908,343 B2
`*Mar. 15, 2011
`
`(54) OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(75)
`
`Inventors: Isaac Levanon, Ramat Hasham (IL);
`Yoni Lavi, Raanana (IL)
`
`(73) Assignee: Inovo Limited, The Valley Anguilla
`(VG)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`(21) Appl. No.: 12/619,643
`
`(22) Filed:
`
`Nov. 16, 2009
`
`(65)
`
`Prior Publication Data
`
`US 2010/0064002 AI
`
`Mar. 11, 2010
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,929,860 A
`7/1999 Hoppe
`112001 Yap et al.
`6,182,114 B1
`4/2001 Warner et al.
`6,212,301 B1
`1112001 Dekel et al.
`6,314,452 B1
`6,326,965 B1
`12/2001 Castelli eta!.
`6,345,279 B1
`212002 Li eta!.
`6,346,938 B1
`212002 Chan et a!.
`5/2002 Lincke et al.
`6,397,259 B1
`8/2003 Dowell et al.
`6,608,933 B1
`6,704,024 B2
`3/2004 Robotham eta!.
`6,711,297 B1
`3/2004 Chang eta!.
`10/2004 Atsumi et al.
`6,801,665 B1
`7,644,131 B2 *
`112010 Levanon eta!. .............. 709/217
`
`OTHER PUBLICATIONS
`
`Hoppe, H. "Progressive Meshes", SIGGRAPH '96: Proceedings of
`the 23rd annual conference on Computer graphics and interactive
`techniques, 1996, pp. 99-108.
`* cited by examiner
`
`Related U.S. Application Data
`
`Primary Examiner- David Lazaro
`
`(63) Continuation of application No. 10/035,987, filed on
`Dec. 24, 2001, now Pat. No. 7,644,131.
`
`(60) 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
`(2006.01)
`(52) U.S. Cl. ......... 709/217; 709/230; 345/625; 382/232;
`382/305
`(58) Field of Classification Search . ... ... ... ... .. ... 709/202,
`709/203, 217, 230, 246, 247; 345/625; 382/232,
`382/305
`See application file for complete search history.
`
`(57)
`
`ABSTRACT
`
`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 is constrained to a
`resolution less than or equal to the resolution of the client
`device display.
`
`20 Claims, 5 Drawing Sheets
`
`$titMJ
`D<tHLM DHA
`
`34
`
`St>!ih!
`I'"''" lhF
`
`32
`
`PH·rmmsw
`?~~W.i!MR !MlA
`
`Microsoft Corp. Exhibit 1012
`
`

`

`U.S. Patent
`
`Mar.15,2011
`
`Sheet 1 of 5
`
`US 7,908,343 B2
`
`;(
`/
`
`/
`l
`/
`
`St~~}~f}
`!#..~}~thg
`
`:i~:
`
`f'llr"P!mtfSSH}
`P.wm.lMAH DATA
`
`~-- §
`
`~-§G~ .·>
`
`..
`
`,t;$
`
`Microsoft Corp. Exhibit 1012
`
`

`

`U.S. Patent
`
`Mar.15,2011
`
`Sheet 2 of 5
`
`US 7,908,343 B2
`
`Microsoft Corp. Exhibit 1012
`
`

`

`U.S. Patent
`
`Mar.15,2011
`
`Sheet 3 of 5
`
`US 7,908,343 B2
`
`Microsoft Corp. Exhibit 1012
`
`

`

`U.S. Patent
`
`Mar.15,2011
`
`Sheet 4 of 5
`
`US 7,908,343 B2
`
`Microsoft Corp. Exhibit 1012
`
`

`

`U.S. Patent
`
`Mar.15,2011
`
`Sheet 5 of 5
`
`US 7,908,343 B2
`
`(Rt.Mt nm.o
`~Mf.(
`
`I ! I
`_j
`
`Microsoft Corp. Exhibit 1012
`
`

`

`US 7,908,343 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`This application is 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"
`which in tum claims the benefit nnder 35 USC 119( e) ofU.S.
`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.
`
`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
`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 eli-
`
`2
`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
`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
`10 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
`15 transform also operates on a subdivided image, but the divi(cid:173)
`sion 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
`20 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-
`25 mation is used to identifY a foveal region that is presumed to
`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
`30 the area of highest image resolution, with resolution reduc(cid:173)
`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.
`35 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
`40 of client systems, even with the improvements provided by
`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
`45 beneficial. Conventional approaches effectively presume that
`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
`50 extremely limited persistent storage capabilities, particularly
`relative to common image sizes. A mobile computing device
`such as mobile phone, smart phone, and or personal digital
`assistant (PDA) is a characteristic small client. Embedded,
`low-cost kiosk and or automobile navigation systems are
`55 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
`60 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
`an extensive set of graphics abstraction layers to be provided
`by the client system to support the presentation of the deliv-
`65 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
`
`Microsoft Corp. Exhibit 1012
`
`

`

`US 7,908,343 B2
`
`3
`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
`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
`limited bandwidth conditions may exist due to either the 10
`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 15
`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- 35
`width network connections.
`
`SUMMARY
`
`4
`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 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(cid:173)
`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
`parcel data rendering is performed without requiring any
`20 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
`any underlying embedded or disk operating system and dis-
`25 play drivers. Complex graphics and animation 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
`30 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 generally
`insensitive to image parcel resolution, can be initially or
`40 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
`the retrieval oflarge-scale images over network communica- 45
`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- 50
`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 may be constrained to 55
`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
`optimized to address the display based on the display resolu- 60
`tion of the client system.
`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 turn, the progres- 65
`sive improvement in display resolution within the field of
`view presented on a client display.
`
`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;
`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;
`
`Microsoft Corp. Exhibit 1012
`
`

`

`US 7,908,343 B2
`
`5
`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
`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, 65
`graphical icons, decals, line segments, and or text and or other
`characters, graphics and or other media.
`
`6
`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
`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
`parcel of the array has for example a 64 by 64 pixel resolution
`10 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
`predecessor image in the series by a factor of four. The array
`15 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(cid:173)
`work server 12, 22. The preferred compression algorithm
`20 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
`located by specification of a K.sub.D, X, Y value, represent-
`25 ing 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 encoding
`30 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
`preferred as permitting easier interchange between different
`commercial entities, while the binary representation is pre-
`35 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 armotation data preferably in a
`resolution independent form associated with a display coor(cid:173)
`dinate specification relative to the source image data 32. The
`40 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
`45 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
`50 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
`55 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 corre(cid:173)
`spond to the stored image parcels of a derivative image of
`resolution KD. The XMLIGML/binary overlay data is pref-
`60 erably stored as a data object that can be subsequently read by
`an XMLIGML/binary parser implemented as part of the con(cid:173)
`trol 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-
`
`Microsoft Corp. Exhibit 1012
`
`

`

`US 7,908,343 B2
`
`7
`ware capabilities. 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.
`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-dimensional
`fly-over navigation of the displayed image. The navigation
`controls support point-of-view rotation, translation, 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 20
`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 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(cid:173)
`cessing overhead of managing image parcel data split over
`multiple network packets. Thus, a 2K byte compressed image 35
`parcel 62 is delivered as the data payload of a TCP/IP packet
`64. Uncompressed, the SK byte imageparcel62 is recognized
`as part of the present invention as being within the nominally
`smallest Ll data cache 66 size of conventional microproces(cid:173)
`sors 68. By ensuring that an uncompressed image parcel fits 40
`within the Ll cache, the texture map rendering algorithm can
`execute with minimum memory management overhead, thus
`optimally utilizing the processing capability of the micropro(cid:173)
`cessor 68. Additionally, the writing of video data as a product
`of the rendering algorithm is uniform, thereby improving the 45
`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 50
`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 consid(cid:173)
`ered in part to determine the current field of view. The quad(cid:173)
`tree data structures are examined 86 to identify viewable 55
`image parcels of higher resolution than currently available 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(cid:173)
`ferred embodiments of the present invention, a pool of four 60
`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. Empirically,
`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
`
`8
`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 viewable
`10 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
`15 image parcels. Preferably, the memory management 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
`25 available, the process 100 examines 106 all of the pending
`requests in the priority request queue 52 and selects 108 the
`request with the highest assigned priority. Thus, sequentially
`enqueued requests can be selectively issued out of order
`based on an independently assigned request priority. The
`30 request is then issued 110 and the request management pro(cid:173)
`cess 100 leaves the request thread waiting on a network
`response.
`FIG. 7 presents a preferred display management process
`120. Event driven user navigation information is evaluated
`122 to determine a current viewing frustum locat