`
`(12) United States Patent
`Levanon et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,908,343 B2
`*Mar. 15, 2011
`
`(54)
`
`(75)
`
`(73)
`
`(*)
`
`(21)
`(22)
`(65)
`
`(63)
`
`(60)
`
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`Inventors: Isaac Levanon, Ramat Hasharn (IL);
`Yoni Lavi, Raanana (IL)
`Assignee: Inovo Limited, The Valley Anguilla
`(VG)
`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
`claimer.
`
`Notice:
`
`Appl. No.: 12/619,643
`
`Filed:
`
`Nov. 16, 2009
`
`Prior Publication Data
`|US 2010/0064002 A1
`Mar 11, 2010
`
`Related U.S. Application Data
`Continuation of application No. 10/035,987, filed on
`Dec. 24, 2001, now Pat. No. 7,644,131.
`Provisional application No. 60/258,488, filed on Dec.
`27, 2000, provisional application No. 60/258,489,
`filed on Dec. 27, 2000, provisional application No.
`60/258,465, filed on Dec. 27, 2000, provisional
`application No. 60/258,468, filed on Dec. 27, 2000,
`provisional application No. 60/258,466, filed on Dec.
`27, 2000, provisional application No. 60/258,467,
`filed on Dec. 27, 2000.
`
`(51)
`
`(52)
`
`(58)
`
`Int. Cl.
`(2006.01)
`G{}6F 15/16
`U.S. Cl. ......... 709/217: 709/230: 345/625; 38.2/232:
`382/305
`Field of Classification Search .................. 709/202,
`709/203, 217, 230, 246, 247; 345/625; 38.2/232,
`382/305
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`|U.S. PATENT DOCUMENTS
`5,929,860 A
`7/1999 Hoppe
`6,182,114 B1
`1/2001 Yap et al.
`6,212,301 B1
`4/2001 Warner et al.
`6,314,452 B1 11/2001 Dekel et al.
`6,326,965 B1 12/2001 Castelli et al.
`6,345,279 B1
`2/2002 Li et al.
`6,346,938 B1
`2/2002 Chan et al.
`6,397.259 B1
`5/2002 Lincke et al.
`6,608.933 B1
`8/2003 Dowell et al.
`6,704,024 B2
`3/2004 Robotham et al.
`6,711,297 B1
`3/2004 Chang et al.
`6,801,665 B1 10/2004 Atsumi et al.
`7,644,131 B2 *
`1/2010 Levanon et al. .............. 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
`
`Primary Examiner – David Lazaro
`
`(57)
`
`ABSTRACT
`
`Large-scale images are retrieved over network communica
`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
`pared for the update image parcel and associated with a
`request queue for subsequent issuance over a communica
`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
`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
`
`
`
`§§§§§§§§
`§§§§§§§
`
`Page 1 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`U.S. Patent
`
`Mar. 15, 2011
`
`Sheet 1 of 5
`
`US 7,908,343 B2
`
`
`
`
`
`
`
`|
`
`Sºssºssssssssssssss
`
`****** §§§
`
`§
`
`i §
`§
`
`
`
`Page 2 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`U.S. Patent
`
`Mar. 15, 2011
`
`Sheet 2 of 5
`
`US 7,908,343 B2
`
`s sº
`--~ & Cº
`sº $$..
`s
`------~~~~~~~~~~~~~~~~~~
`§
`§
`
`–F– §§
`
`& &
`
`§
`
`---
`
`-
`
`---
`
`~e
`~$3
`| §§§§ i
`
`§§§§§ {{#$$.
`
`-
`
`- -
`
`s
`
`s
`
`-- § § §: - § §
`
`
`
`
`
`--~~~~~~~~~~~~~~~~~~~
`
`w
`
`N--~~~~~~~~~~--------~
`
`-
`
`
`
`&
`
`*** ~~
`s
`^s
`§
`$$$$$$$ $$$$.
`# 8888.933
`– §§
`
`**~~~~~~~~~~~~~~~~~~~~~~~
`
`i
`i
`
`&xº~~~~~~~~~~~~~~
`
`fig. 4
`
`
`
`Page 3 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`US 7,908,343 B2
`
`DMioe3ébene
`
`rorgpecerenesecttriele4.
`;eegfrst,
`
`
`
`U.S. Patent
`
`Mar. 15, 2011
`
`“onaoe
`
`oeNAY
`
`“i
`
`oe3i2m4whae4iBa2:ith,%atChee3a7Biener‘ecneoeledtagnookcesnssrerpyweeOEESeasseael*e,7-ZSassateeed4teBEtregapl
`
`mMgi;Ews54febeZ:tagiawee£4RLoe:iiias4:tattke¢4hd
`3greBe3bdoEETeeYegeeAEgteatEYoZBeigefet‘ByeeiLEthee.4Beoe=3aed‘tang
`
`
`Porerorrrcoerronulgeenanacniettttrerseripeccececceraceccocwcspssiasdtiaiissefganseroveccccercranttedséfond33*;ayng4He3og34}.3on¢34f:5;4::5fsus3%:;?
`i:zgo35i5coedéLBea
`;nOALA7Fp.yfseenwot£?374,4,§fat4.a:;uy3,4octiOnt4hey5444%4434,3
`aeeefnaeees
`ahlageZmed
`BaxiSZ4,Derrevevercacsrsorertcenpssspciaede,Zziathe
`were4ges*44:‘5-%,#4neetee,4%Kt%g/44g/4,ee%,ZZ*,a£:i“hae,oO%,‘4EA£Cerone3feug%54“agf
`%°4,Hi2.tet,4«Ae4-vn
`f“oehdioo
`,‘5fSiert
`‘,,+,“er
`
`_
`
`tl”ser
`
`on
`
`ood
`
`Lee,
`
`Page 4 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`Page 4 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`
`
`
`
`Mar. 15, 2011
`
`Sheet 4 of 5
`
`US 7,908,343 B2
`
`U.S. Patent
`
`an
`
`onaebbe
`
`bbb
`
`o
`
`prmen”45$gre.rth,be,“sager.
`
`/yeanef¢ORTLIEEREEAPO
`5ttae:dobhegooey7;5teenoah
`aoeoefetheewo“éisia;;aoeotPa$teMaaeicmtA¢4:-*BRnej,fegeBeaon:,below;nefthzweatepegioh.i5ercronsoncedtief,
`
`
`tnKEheeerencelifeson.oe‘meoetenareseacneuaanss
`
`
`
`
`
`eeePtOTERAALEDDLEAELIDONDDEEDD,rokCkg;nikegeBSg4hete$ieg¢tilegeesg;rege3SadeeBay4sees.a¢2Onrt:t.%fs+raCeeéSaratita4iwatiheae;tea3ue&raeos34,;;fortwaeangfFis.teh4g%:‘4g:$lcorsencsnrrencoggvocseesececeeeel"errcrrrgentcnncerVevenacerengentantid
`;eg:BeAyee3seGe{felge3;ae4éFEtaoe:tet,“Ge0,bkitchte,605eek3jSefie.;her
`brovvcenccnneerrceccbueeverseesteddZqjs4¢Z4q3i4;fZ4$44;;;;$43t;i3itij5544z244giéjoeGarocecececccerecencevecesecetccradenssestessevessererseseasestoccccvecccececstensisigsiacettl
`PNGpesas”%%*,reiSwab%okroea4oohoyLS”4penao44ae.4fid
`
`AgrriteneteresnesbnbetTIOLOCOEPELECILLLCLctepestettleteisipesegtie:
`
`
`edodsenerncneligytfbneeGeowcoreed4esrecanceniti“aiycoelihGynEyNgtypesPagf;Bt4WeKeta,OEOE,hs$eGok§:,te1teBhtetyeOetdfe:
`:4,4$:Zj‘ae‘Laenerrrrennnnstedti‘nenasenonenton54,;boni%y»
`te}tOié$getfegateeet4ivotZ4iCopthineaSes:Hs,4as340OKfpaen
`rsi&5$ret2thBpwy&%oetee.,feBe¢ie,iPexe-
`
`ongaayPafejetFfwtieeees1oeMeae*4fs“s,PAAL‘.aaess
`Seervceensapestinbstinssdadisdettteterieesa,
`c‘25fiae4isiioeit4$few$forety5bee
`.itte:4Be.3catbe
`
`ed.a84,’f-5%iai,/£4%Z4‘,4,Zé
`
`ing“ye3%ieH.oeenceiircael
`aewwAg1£6wneezg4ae,
`“4yeeOeeee%egpee¥Eons,eeEnteineNaememed4.“ae44£lL.“&wp.eedFEBonpee“a,4ThtTEEtae4meBeoefeteyer
`feefHasarr$75EEtheGee4erpyootat4OEoh54eeevot&load
`Z%t:atoutharsBe21B£eS4ny4OHBE4emSk4Gee“ARE4few|GT
`echA,YENDES08Ohveoh4beetetenedGZ4Sage70%4Fethezg%tAthe
`gLEEALILEL,SOPPELEED
`
`
`fees,
`
`Page 5 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`Page 5 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`
`U.S. Patent
`
`Sheet 5 of 5
`
`US 7,908,343 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 6 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`US 7,908,343 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`5
`
`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 turn claims the benefit under 35 USC 119(e) of U.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
`pending application Ser. No. 10/035,981 entitled “System
`and Methods for Network Image Delivery with Dynamic
`Viewing Frustum Optimized for Limited Bandwidth Com
`munication Channels, Levanon et al., 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.
`
`10
`
`15
`
`20
`
`FIELD
`
`The disclosure is related to network based, image distribu
`tion systems and, in particular, to a system and methods for
`efficiently selecting and distributing image parcels through a
`narrowbandor otherwise limited bandwidth communications
`channel to support presentation of high-resolution images
`subject to dynamic viewing frustums.
`
`25
`
`30
`
`BACKGROUND
`
`2
`ent computeris, 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
`increasing latency in resolving finer levels of detail.
`An image visualization system proposed byYap et al., U.S.
`Pat. No. 6,182,114, overcomes some of the foregoing prob
`lems. The Yap et al. system also employs a progressive encod
`ing transform to compress the image transfer stream. The
`transform also operates on a subdivided image, but the divi
`sion is indexed to the encoding level of the transform. The
`encoded transform coefficient data sets are, therefore, of con
`stant size, which supports a modest improvement in the algo
`rithmic 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 opera
`tor defines the corresponding image block as the center point
`of an ordered retrieval of coefficient sets representing a vari
`able resolution image. The gaze point image block represents
`the area of highest image resolution, with resolution reduc
`tion as a function of distance from the gaze point determined
`by the foveation operator. This technique thus progressively
`builds image resolution at the gaze point and succeedingly
`outward based on a relatively compute intensive function.
`Shifts in the gaze point can be responded to with relative
`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 performance,
`memory and storage. Small clients, however, typically have
`restricted performance processors with possibly no dedicated
`floating-point support, little general purpose memory, and
`extremely limited persistent storage capabilities, particularly
`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
`other typical examples. Such systems are not readily capable,
`ifatall, of performing complex, compute-intensive Fourieror
`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 visualiza
`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
`ered image data. In general, these abstraction layers are con
`ventionally considered required to handle the mapping of the
`image data resolution to the display resolution capabilities of
`
`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
`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 turn, may render the image.
`Client systems may typically implement a local image navi
`gation system to provide zoom and or pan functions based on
`user interaction. As well recognized problem with such con
`ventional systems could be that full resolution image presen
`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
`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
`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
`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 cli
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`Page 7 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`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
`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 maxi
`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 al. 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
`cations 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, however, merely mask packet
`losses and the resultant, sometimes extended, recovery laten
`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
`ization system that can support small client systems, place
`few requirements on the supporting client hardware and soft
`ware resources, and efficiently utilize low to very low band
`width network connections.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`SUMMARY
`
`Thus, a general purpose of the present invention is to pro
`vide an efficient system and methods of optimally presenting
`image data on client systems with potentially limited process
`ing performance, resources, and communications bandwidth.
`This is achieved in the present invention by providing for
`the retrieval of large-scale images over network communica
`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
`pared for the update image parcel and associated with a
`request queue for subsequent issuance over a communica
`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
`mally has a fixed pixel array size, is received in a single and or
`plurality of network data packets, and may be constrained to
`a resolution less than or equal to the resolution of the client
`device display.
`An advantage of the present invention is that both image
`parcel data requests and the rendering of image data are
`optimized to address the display based on the display resolu
`tion of the client system.
`Another advantage of the present invention is that the pri
`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
`sive improvement in display resolution within the field of
`view presented on a client display.
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,908,343 B2
`
`4
`A further advantage of the present invention is that the
`client software system requires relatively minimal client pro
`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
`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
`tions. The software system of the present invention provides
`for re-prioritization of image parcel data requests and presen
`tation in circumstances where the rate of point-of-view navi
`gation 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 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
`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
`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
`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 through
`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
`tation system constructed in accordance with a preferred
`embodiment of the present invention;
`FIG. 4 provides a data block diagram illustrating an opti
`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
`ing thread implemented in a preferred embodiment of the
`present invention;
`
`
`
`Page 8 of 13
`
`Unified Patents Exhibit 1012
`
`
`
`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
`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
`ment of the present invention;
`FIG. 9 provides a process flow diagram detailing the ren
`dering 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 frustuminaccordance 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
`tivity provider 16. Client systems, including conventional
`workstations and personal computers 18 and smaller, typi
`cally dedicated function devices often linked through wire
`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
`erably implementing a small, embedded Web server, to a fixed
`or removable storage local image repository 24. Characteris
`tically, the client system 18, 20 displays are operated at some
`fixed resolution generally dependent on the underlying dis
`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 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 sys
`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
`mark names, as well as representative 2 and 3D objects,
`graphical icons, decals, line segments, and or text and or other
`characters, graphics and or other media.
`
`6
`The network image server system 30 preferably pre-pro
`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
`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.0, is also subdi
`vided into a regular array such that each resulting image
`parcel of the array has for example a 64 by 64 pixel resolution
`where the image data has a color or bit per pixel depth of 16
`bits, which represents a data parcel size of 8K 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
`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 net
`work server 12, 22. The preferred compression algorithm
`may implements for example a fixed 4:1 compression ratio
`such that each compressed and stored image parcel has a fixed
`2K byte size. The image parcels are preferably stored in a file
`of defined configuration such that any image parcel can be
`located by specification of a K.sub.D., X, Y value, represent
`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
`standard for geographic information developed by the
`OpenGIS Consortium (OGC: www.opengis.org), or a propri
`etary binary representation. The XML/GML representationis
`preferred as permitting easier interchange between different
`commercial entities, while the binary representation is pre
`ferred as more compact and readily transferable to a client
`system 18, 20. In both cases, the source overlay data 34 is
`pre-processed to contain the annotation data preferably in a
`resolution independent form associated with a display coor
`dinate specification relative to the source image data 32. The
`XML, GML or binary overlay data may be compressed prior
`to storage on the network server 12, 22.
`The preferred architecture 40 of a client system 18, 20, for
`purposes of implementing the present invention, is shown in
`FIG. 3. The architecture 40 is preferably implemented by a
`software plug-in or application executed by the client system
`18, 20 and that utilizes basic software and hardware services
`provided by the client system 18, 20. A parcel request client
`42 preferably implements an HTML client that supports
`HTML-based interactions with the server 12, 22 using the
`underlying network protocol stack and hardware network
`interface provided by the client systems 18, 20. A central
`parcel processing control block 44 preferably implements the
`client process and control algorithms. The control block 44
`directs the transfer of received image parcels and 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 corre
`spond to the stored image parcels of a derivative image of
`resolution KD. The XML/GML/binary overlay data is pref
`erably stored as a data object that can be subsequently read by
`an XML/GML/binary parser implemented as part of the con
`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
`
`US 7,908,343 B2
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`
`
`Page 9 of 13
`
`Unified Patents 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
`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
`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 foruse
`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
`cessing overhead of managing image parcel data split over
`multiple network packets. Thus, a 2K byte compressed image
`parcel 62 is delivered as the data payload of a TCP/IP packet
`64. Uncompressed, the 8K byte image parcel 62 is recognized
`as part of the present invention as being within the nominally
`smallest L1 data cache 66 size of conventional microproces
`sors 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 processing capability of the micropro
`cessor 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 consid
`ered in part to determine the current field of view. The quad
`tree data structures are examined 86 to identify viewable
`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
`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