`
`(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
`
`
`
`§§§§§§§§
`§§§§§§§
`
`Microsoft Corp. Exhibit 1012
`
`
`
`U.S. Patent
`
`Mar. 15, 2011
`
`Sheet 1 of 5
`
`US 7,908,343 B2
`
`
`
`
`
`
`
`|
`
`Sºssºssssssssssssss
`
`****** §§§
`
`§
`
`i §
`§
`
`
`
`Microsoft Corp. 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
`
`Microsoft Corp. Exhibit 1012
`
`
`
`O
`
`U.
`
`US 7,908,343 B2
`
`P.....
`
` N..iH\sN«NNe..=\Nmu.»mN...wN+3RamtN“«uh.xxufl.\
`.....\\..t..xxN»!mew»u.\\
`tzzzsksieNwwwmmmNNNN.3E.N.eNf.«xx:2...»NSNNhN{LNis.NNN,3._ham\.SN...u..N.N.NMu\\
`
`Niexw.\\\\\\\\x“Mus»:«tNC..NN..
`a...x
`xx:.n.\.xMwx\.V...m5NN.N.»NYmmW.N.\...........:fNN$1NA..\.NNNWm..&N0NNK.N1.».§N\N3N..:.<.NNamas.N.as3.mNNE.mm.a.,..NN\N...
`33:..rN..N?N%a.NMN»N«N\.N\N...N\\....N.N.N}.Ngas.
`\.K—av¢sss:.$.m..§\\\§§
`x...N.N«S.“usN.3‘N\x.KA1«M»M.\..\\..mNN“NM3%..»::.$.1NN:2N:NaNu.“0....3;.
`
`...Sn,.Nm.»4.1K
`N.3..\.“:R..NV»!2kn«m1.s\>.<sx
`
`.5»GunN.....N‘?\».\\\u\1ENas
`\\\.\\u..9nuW3Mm§Nu“NH;5.\.z.|.\\.wu.\\3\
`
`
`.we.E...“N.N3...\:3S....$...3x
`\..N.in.\NN$$§.N.§MxN.€.wuw».NN\NN.\\Nwm.
`\»\\EWNNE:NNNNN9.»
`
`\\\‘\..\\a.\\\\\\\\\\»\\\5.\\v§.I.32.55.5..w.
`...-\\\\
`
`n.o.\D..o
`
`..3.\
`
`.....
`.$x\\
`
`
`...1N...,:.MN.‘N..N».\scxx\N,xatR.\«Nw.N...NWN.,\!\\\\)a\<.\\...«~\...m.W».3.\so..
`
`N\§>..s.s\<sE.»3%\x\\\\\\\\.\\\\sxnIQ.s\s\<~..-\uuxQua...i\\\\\\\\\\\\\\\snv\ss§ws\ssss\s\<x3xss\u.aw?\«..
`.a.\N‘N\..
`.xW\..xN\.\¢c\.£.\
`.,.\xx:\
`...€~\\\«.ux\
`
`\.NN.NN
`.a-“N‘
`0‘5‘
`‘K. ~
`\
`$3
`
`'
`
`3
`
`N \7\\
`
`\‘\- .
`~
`
`.
`
`.
`\\uIN&§PQN§*
`
` 3<3e\\.1
`
`3\\\-«
`
`Microsoft Corp. Exhibit 1012
`
`Microsoft Corp. Exhibit 1012
`
`
`
`
`
`
`U.S. Patent
`
`Mar. 15, 2011
`
`Sheet 4 0f5
`
`US 7,908,343 B2
`
`1.s\»»\.11.1§s)\
`
`\\1.x1.1.x\§\n\\\\\\\\\\\\>\\\\\\1
`
`: %
`
`
`
` «.6.ma»\\1
`
`.1111»
`
`3“.
`
`$3“
`
`Run...
`
`~<\~ow«w1
`
`1M11111111111
`
`»-1-11111111111111
`
`111\11111,....\1.1
`
`1111-1-111111.1111.1.
`
`§111\1}1.1.111\\1x\x\
`
`111111s\\\\xx\»\\«\\s\\\\\\\\\\..\\\\\\\\\\§\\111111.1s1\11\11111sx1.\\s\1.\\\\\\1\\\\\\\\\\\1\\x.\
`\\\\\\\\\\\\\\\\\)\\\)\\\\\\\\\15\\\NS\\\\\\1\\\\\\\\\\\\\\\\\\\\\.
`
`\\\\\\\\\\\\\\\\\\\x\\(\Vz\\\\\\\\\\\\\\
`
`§:§§1 L?
`
`1\w1
`P..\.1
`
`591
`
`“Ru
`
`vs!
`
`1111111111111111s1.1111111111111
`
`..§1\\§\%%
`
`»ss.1\s\\\\\\\\\\\\\\\K\\\
`
`E
`
`111111-1x11“111~zx111111111111
`
`11
`
`x\..\\\\\\\\¥.\\\\\\\x\x\\xu\\xxx\\sv\i\\\&
`
`\\\\\\\\\\\n
`
`§~‘=*‘§$. 3
`
`1111
`1.11N1
`
`1
`
`1
`11.11.
`
`1
`
`1v.\\\>ai\\\\)\)1i\\\
`
`~ §\
`~\‘
`\11~ 5 x1 :11
`1-‘
`-‘I
`\\\\\\\\\\'~\\\\\\\\\\\\\\\\\\\\\ \_
`1
`
`{1
`
`1:33;
`
`\\\\\\\\\..&§\\\x\\
`
`\ -
`-1
`\'1
`1 1
`111-11111111111‘ 111111111111111§
`. .
`\
`\
`.
`\ ..*.\
`E1? 1?“
`'
`‘~}- 1? \
`5.3%
`‘1 13x33‘;
`
`\I‘‘‘‘‘
`“.1
`
`§
`xxxxxmmxwuumwwmwmm
`~ 1
`
`§
`
`$11.
`
`.5.
`».1\R1.1.i\Q3
`Ann1
`
`1
`
`\
`111
`\.
`
`...§111111§11111§1111\
`
`N
`\1ao33s
`
`1M1511.511.
`
`11sk
`
`111m.1?1%\11.1».\\\1.1511N11PK1.5:1Mm«.111N111111we.11111.1%man.11411»\1
`.\\..11mm“1»111111{111%..
`
`Microsoft Corp. Exhi
`
`it 1012
`
`Microsoft Corp. Exhibit 1012
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Sheet 5 of 5
`
`US 7,908,343 B2
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. 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
`
`Microsoft Corp. 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;
`
`Microsoft Corp. 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
`
`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
`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. 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
`
`40
`
`45
`
`8
`progressively identified for download, a free request thread is
`employed to issue 88 a corresponding network request