throbber
111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US008924506B2
`
`c12) United States Patent
`Levanon et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 8,924,506 B2
`*Dec. 30, 2014
`
`(54) OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(75)
`
`Inventors: Isaac Levanon, Raanana, IL (US);
`Yonatan Lavi, Roanana, IL (US)
`
`(73) Assignee: Bradium Technologies LLC, Suffern,
`NY (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 865 days.
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`(21) Appl. No.: 13/027,929
`
`(22) Filed:
`
`Feb.15,2011
`
`(65)
`
`Prior Publication Data
`
`US 2011/0175914 Al
`
`Jul. 21, 2011
`
`(63)
`
`(60)
`
`Related U.S. Application Data
`
`Continuation-in-part of application No. 12/619,643,
`filed on Nov. 16,2009, now Pat. No. 7,908,343, which
`is a 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)
`
`Int. Cl.
`G06F 15116
`G06F 3114
`G06T 3140
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`(52) U.S. Cl.
`CPC
`
`G06F 311454 (2013.01); G06T 314092
`(2013.01); G09G 2340/02 (2013.01); G09G
`2350/00 (2013.01)
`........... 709/217; 709/203; 345/625; 382/232;
`382/305
`
`USPC
`
`(58) Field of Classification Search
`CPC ..... G06T 3/4092; G09G 2340/02; G06F 3/14
`USPC ................. 709/202,203,217,230,246, 247;
`345/625; 382/232, 305
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`5,929,860 A
`6,182,114 B1
`
`7/1999 Hoppe
`112001 Yap et al.
`(Continued)
`
`OTHER PUBLICATIONS
`
`Hoppe, H. "Progressive Meshes", SIGGRAPH '96: Proceedings of
`the 23rd annual conference on Computer graphics and interactive
`techniques, 1996, pp. 99-108.
`Primary Examiner- David Lazaro
`(74) Attorney, Agent, or Firm- Anatoly S. Weiser, Esq.;
`Acuity Law Group, P.C.
`ABSTRACT
`(57)
`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 were the fixed pixel
`array may be constrained to a resolution less than or equal to
`the resolution of the client device display.
`21 Claims, 5 Drawing Sheets
`
`f'~r·l'hlUSSW
`hwn.!wn:Dw
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6,212,301 B1
`6,314,452 B1
`6,326,965 B1
`
`4/2001 Warner et a!.
`1112001 Dekel et a!.
`12/2001 Castelli eta!.
`
`6,345,279 B1
`6,346,938 B1
`6,397,259 B1
`6,608,933 B1
`6,704,024 B2
`6,711,297 B1
`6,801,665 B1
`
`212002 Li eta!.
`212002 Chan eta!.
`5/2002 Lincke et al.
`8/2003 Dowell et al.
`3/2004 Robotharn eta!.
`3/2004 Chang eta!.
`10/2004 Atsumi et al.
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 1 of 5
`
`US 8,924,506 B2
`
`·~~~w~~,:s::;:::::s:::..~~~:'"''·
`'~"<:~::~~-----"~-~>
`34
`
`$(ltWU
`
`StJ~l~f}
`!#..~}~ tht>\
`
`:i2
`
`A
`/
`
`/
`l
`/
`
`P!lr"Pwuss~:o
`f'iWOJlMAH UiHA
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 2 of 5
`
`US 8,924,506 B2
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 3 of 5
`
`US 8,924,506 B2
`
`82
`
`NAVIGATION __ ._.
`EVENlS
`80~
`
`FIG. 5
`
`84
`
`NE1WORK
`
`88
`
`REQUEST PARCEL
`DOWNLOADS
`
`·····
`
`..
`
`STORE PARCEL TO
`QUAD TREE NODE
`
`.. •
`
`92
`
`90
`
`94
`
`WAIT fOR
`SELEG HIGHEST
`REQUEST THREAD 1--_.. PRIORITY REOUEST
`fREE
`WAITING
`
`102
`
`104
`
`110
`
`fiG. 6
`
`100_}
`
`106
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 4 of 5
`
`US 8,924,506 B2
`
`?l\l!:ll\Hl'
`Sm:mu~of
`
`Microsoft Corp. Exhibit 1002
`
`

`
`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 5 of 5
`
`US 8,924,506 B2
`
`-~ '
`•'1 f~J'\ _______ ,,,-----·'/
`
`:.: · .. ..> ...... ~~
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`This application is a continuation in part of and claims
`priority under 35 USC 120 to U.S. patent application Ser. No.
`12/619,643 filed on Nov. 16, 2009 now U.S. Pat. No. 7,908,
`343 which in tum in 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"
`(that now issued on Jan. 5, 2010 as U.S. Pat. No. 7,644,131)
`which in tum claims the benefitnnder35 USC 119(e) ofU.S. 15
`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. 25
`
`2
`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(cid:173)
`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
`10 time-critical, to deal with substantially smaller coefficient
`data sets. The array size in Tzou is fixed, which leads to
`progressively larger coefficient data sets as the detail level of
`the image increases. Consequently, there is an inherently
`increasing latency in resolving finer levels of detail.
`An image visualization system proposed by Yap 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
`transform also operates on a subdivided image, but the divi-
`20 sian 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
`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(cid:173)
`mation is used to identifY a foveal region that is presumed to
`30 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
`the area of highest image resolution, with resolution reduc-
`35 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
`40 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
`45 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
`beneficial. Conventional approaches effectively presume that
`50 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
`55 relative to common image sizes. A mobile computing device
`such as mobile phone, smart phone, tablet and or personal
`digital assistant (PDA) is a characteristic small client.
`Embedded, low-cost kiosk, automobile navigation systems
`and or Internet enabled/connected TV are other typical
`60 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
`65 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
`
`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
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`3
`an extensive set of graphics abstraction layers to be provided
`by the client system to support the presentation of the deliv(cid:173)
`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
`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 10
`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 15
`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 20
`of small clients that are frequently constrained by limited
`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(cid:173)
`width network connections.
`
`SUMMARY
`
`4
`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 tum, the progres(cid:173)
`sive improvement in display resolution within the field of
`view presented on a client display.
`A further advantage of the present invention is that the
`client software system requires relatively minimal client 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, tablets 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-
`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
`25 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
`30 any underlying embedded or disk operating system and dis(cid:173)
`play drivers. Complex graphics and animation abstraction
`layers are not required.
`Still another advantage of the present invention is that
`35 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
`40 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. Array overlay data, correlated
`positionally to the image parcel data and generally insensitive
`45 to image parcel resolution, can be initially or 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 50
`the retrieval oflarge-scale images 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 55
`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 60
`plurality of network data packets, and were the fixed pixel
`array 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 65
`optimized to address the display based on the display resolu(cid:173)
`tion of the client system.
`
`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;
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`5
`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;
`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
`
`6
`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,
`graphical icons, decals, line segments, and or text and or other
`characters, graphics and or other media.
`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
`10 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
`15 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 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
`20 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 SK byte size.
`In the preferred embodiment of the present invention, the
`image parcels are further compressed and stored by the net-
`25 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
`30 located by specification of a K.sub.D, X, Y value, represent(cid:173)
`ing the image set resolution index D and corresponding image
`array coordinate.
`In other implementations, the image array dimensions
`(which as 64x64 above) may be powers of two so that the
`35 image array can be used in texture mapping efficiently. To
`accommodate different data parcel size than the 2 KByte
`associated with 64x64 pixel parcel dimension described
`above and other communication protocol and overhead
`requirements, to accommodate transmission through other
`40 than a 3 KByte per second transmission channel, the present
`invention may use larger compression ratios that takes, for
`example, a 128x128 or 256x256 pixel parcel dimension and
`compresses it to meet the 3 KByte per second transmission
`channel, or other communication bandwidth used to stream
`45 the parcel.
`The system may also accommodate different and larger
`data parcel sizes as transmission protocols, compression ratio
`achieved and micro-architectures of the client computers
`change. For purposes above, the data content was a pixel array
`50 representing image data. Where the data parcel content is
`vector, text or other data that may subject to different client
`system design factors, other parcel sizes may be used. Fur(cid:173)
`thermore, the parcel sizes can be different between the server
`and the client. For example the server may create parcels or
`55 hold parcels, for streaming with 256x256 pixel parcel dimen(cid:173)
`sion and the client my render them as 64x64. In addition,
`parcels sizes on different servers may vary from one server to
`another and from the client side rendering. In the system, each
`grid is treated as a sparse data array that can be progressively
`60 revised to increase the resolution of the grid and thereby the
`level of detail presented by the grid.
`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
`65 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
`
`Microsoft Corp. Exhibit 1002
`
`

`
`US 8,924,506 B2
`
`7
`preferred as permitting easier interchange between different
`commercial entities, while the binary representation is pre(cid:173)
`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(cid:173)
`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 XMLI
`GML!binary overlay data to a local parcel data store 46. Local
`parcel data store 46 may also act for example as local cache
`weather the entire data or part of it is in dynamic and/or static
`cache. Preferably image data parcels are stored in conven(cid:173)
`tional quad-tree data structures, where tree nodes of depth D
`correspond to the stored image parcels of a derivative image
`of resolution KD. The XMLIGML!binary overlay data is
`preferably stored as a data object that can be subsequently
`read by an XMLIGML/binary parser implemented as part of
`the control 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(cid:173)
`ware capabilities and may take advantage of more advanced
`graphics acceleration hardware when available in the client
`system 18, 20. 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. The rendering
`engine 48 may take advantage of floating point operations
`when available in the client system 18, 20.
`Changes in the viewing frustum are determined from user 50
`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, 55
`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 60
`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 65
`reflecting changes in the viewing frustum with minimum
`latency.
`
`8
`In various implementations of the parcel processing, each
`data parcel is independently processable by the client system
`18,20, which is enabled by the selection and server-side pro(cid:173)
`cessing used to prepare a parcel for transmission, thus pro(cid:173)
`viding for on-demand real-time parcel processing and cre(cid:173)
`ation on the server side for streaming based on the client
`request and not only for pre-processed parcel creation for
`retrieval for streaming from the server. Thus, the system can
`use both pre-processed parcels on the server and on-demand
`10 real-time creation of such parcels on the server side for
`streaming to the client.
`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
`15 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-
`20 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 parcel62 is r

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