throbber
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 1001
`
`

`
`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 1001
`
`

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

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

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

`
`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 1001
`
`

`
`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 1001
`
`

`
`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 1001
`
`

`
`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 1001
`
`

`
`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 location and
`

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket