`Levanon et al.
`
`(10) Patent N0.:
`
`(45) Date of Patent:
`
`US 9,253,239 B2
`*Feb. 2, 2016
`
`US009253239B2
`
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`Applicant: BRADIUM TECHNOLOGIES LLC,
`Suffem, NY (US)
`
`Inventors:
`
`Isaac Levanon, Raanana (IL); Yonatan
`Lavi, Raanana (IL)
`
`Assignee: BRADIUM TECHNOLOGIES LLC,
`Suffem, NY (US)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. l54(b) by 0 days.
`
`This patent is subject to a terminal dis-
`claimer.
`
`14/547,148
`
`Nov. 19, 2014
`
`Prior Publication Data
`
`US 2015/0180928A1
`
`Jun. 25, 2015
`
`Related U.S. Application Data
`
`Continuation of application No. 13/027,929, filed on
`Feb. 15, 2011, now Pat. No. 8,924,506, which is a
`continuation-in-part of application No. 12/619,643,
`filed on Nov. 16, 2009, now Pat. No. 7,908,343, which
`
`(Continued)
`
`(2005.01)
`(2006.01)
`(Continued)
`
`Int. Cl.
`G06F 15/16
`H04L 29/06
`
`U.S. Cl.
`
`CPC .......... .. H04L 65/602 (2013.01); G06F 3/1454
`(2013.01); G06T3/4092 (2013.01); H04L
`67/42 (2013.01); G09G 2340/02 (2013.01);
`G09G 2350/00 (2013.01)
`
`(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
`
`U.S. PATENT DOCUMENTS
`
`4,682,869 A *
`4,972,319 A
`
`7/1987 Itoh etal.
`11/1990 Delorme
`
`............... .. 358/426.12
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`1070290 B1
`99/41675
`
`1/2001
`8/1999
`
`OTHER PUBLICATIONS
`
`Potmesil Maps Alive with dAmaud Declaration (all pages).
`
`(Continued)
`
`Primary Examiner — David Lazaro
`(74) Attorney, Agent, or Firm —Anatoly S. Weiser, Esq.;
`Techlaw LLP
`
`(57)
`
`ABSTRACT
`
`Large-scale images are retrieved over network comm1mica-
`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 comm1mica-
`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 were the fixed pixel
`array may be constrained to a resolution less than or equal to
`the resolution of the client device display.
`
`25 Claims, 5 Drawing Sheets
`
`?a»~§’.::s{:*.<.:a§
`?azesrs.3msa= ms
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`
`
`US 9,253,239 B2
`Page 2
`
`Related U.S. Application Data
`
`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,465, 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, provisional appli-
`cation No. 60/258,468, filed 011 Dec. 27, 2000, provi-
`sional application No. 60/258,488, filed on Dec. 27,
`2000, provisional application No. 60/258,489, filed on
`Dec. 27, 2000.
`
`Int. Cl.
`G06F 3/14
`G06T 3/40
`
`(2006.01)
`(2006.01)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`Visual Simulation System” by P. Lindstrom et al., Tech. Rep. GIT-
`GVU-97-07, Mar. 1997 (all pages).
`Curriculum Vitae of William R. Michalson (all pages).
`Hanan Samet, The Design and Analysis of Spatial Data Structures,
`University of Maryland (1989) (all pages).
`B. Fuller and I. Richer, The Magic Project: From Vision to Reality,
`IEEE Network May/Jun. 1996, pp. 15-25.
`International Telegraph and Telephone Consultative Committee
`(“CCITT”) Recommendation T.81, Sep. 1992 (all pages).
`Ken Cabeen & Peter Gent, Image Compression and the Discrete
`Cosine Transform (all pages).
`M. Antonini, Image Coding Using Wavelet Transform , IEEE Trans-
`actions on Image Processing, vol. 1. No. 2. Apr. 1992 (all pages).
`Lance Williams, Pyramidal Parametrics, Computer Graphics, vol.
`17, No. 3, Jul. 1983, (all pages).
`OpenGL Smndard Version 1.1, Mar. 1997, available: https://www.
`opengl.org/documentation/spec s/versionl . 1/glspec 1 . 1/node84.
`html#SECTION00681100000000000000 , (all pages).
`H. Hoppe, Progressive Meshes, SIGGRAPH ’96: Proceedings of the
`23rd armual conference on computer graphics and interactive tech-
`niques, pp. 99-108.
`Boris Rabinovich and Craig Gotsman, Visualization of Large Ter-
`rains in Resource-Limited Computing Environments (1997) (all
`pages).
`User Datagram Protocol (UDP) (Windows CE 5.0, Microsoft, Avail-
`able:
`https://msdn.microsofi.com/enus/library/ms885773.aspx
`[Accessed Apr. 28, 2015] (all pages).
`OpenGL Standard Version 1.2.1, Apr. 1999, available: https://www.
`opengl.org/documentation/spec s/versionl .2/opengl1.2.1.pdf
`,
`(all
`pages).
`George H. Forman and John Zahorjan. “The challenges ofmobile
`computing,” Computer vol. 27, No.4, pp. 38, 47 (Apr. 1994).
`K. Brown and S. Singh, A Network Architecture for Mobile Com-
`puting, INFOCOM ’96, Fifteenth Annual Joint Conference of the
`IEEE Computer Societies, Networking the Next Generation, Pro-
`ceedings IEEE Vol.3, pp. 1388-139.
`B. Kreller et al “UMTS: a middleware architecture and mobile API
`approach,” Personal Communications, IEEE, vol. 5, No. 2. pp. 32-38
`(Apr. 1998).
`J. Hansen et al, “Real-time synthetic vision cockpit display for gen-
`eral aviation,” AeroSense ’99, International Society for Optics and
`Photonics, 1999, (all pages).
`Theresa-Marie Rhyne, A Commentary on GeoVRML: A Tool for 3D
`Representation of GeoReferenced Data on the Web, International
`Journal ofGeographic Information Sciences. issue 4 ofvol. 13, 1999,
`(all pages).
`Declaration of Prof. William R. Michalson (all pages).
`Provisional Applications to which the 506 Patent claims priority (all
`pages).
`Numbering of Claim Elements of Challenged Claims of the 506
`Patent, (all pages).
`(Ex. 1002) and
`Claim chart
`illustrating teachings of Potrnesil
`Hornbacker (Ex. 1003) pertinent to elements of Challenged Claims
`(all pages).
`Claim chart illustrating teachings ofRutledge (Ex. 1006). Ligtenberg
`(Ex. 1005), and Cooper (Ex. 1007) pertinent to elements of Chal-
`lenged Claims (all pages).
`Claim chart illustrating teachings ofRutledge (Ex. 1006). Ligtenberg
`(Ex. 1005), Cooper (Ex. 1007), and Hassan (Ex. 1008) pertinent to
`elements of Challenged Claims (all pages).
`Claim chart illustrating teachings of Fuller (App. E) and Hornbacker
`(Ex. 1003) pertinent to elements of Challenged Claims (all pages).
`Claim chart illustrating teachings of Yap (App. J) and Rabinovich
`(App. R) pertinent to elements of Challenged Claims (all pages).
`
`* cited by examiner
`
`Microsoft Corp. Exhibit 1001
`
`................. .. 701/470
`
`......... .. 709/217
`
`*
`*
`
`*
`
`*
`
`%*%*%*%*%***%*
`
`AAAAAAAAAAAAA
`
`UJUJUJUJLMUJLMUJUJUJUJUJUJUJUJUJ
`
`>->->->->->->->->->->->->->->->—
`
`1/1993 Dawson et al.
`5,179,638
`5,263,136
`11/1993 DeAguiar etal.
`5,321,520
`6/1994 Inga et al.
`............... .. 345/428
`9/1996 Poulter etal.
`5,559,936
`. . . .
`. . . . . .. 345/428
`3/1997 Iodice et al.
`5,613,051
`5,682,441
`10/1997 Ligtenberg et al.
`5,760,783
`6/1998 Migdal
`8/1998 Baldwin
`5,798,770
`8/1999 Hassanetal.
`5,940,117
`11/1999 Wuetal.
`5,987,256
`11/1999 Smith etal.
`5,995,903
`6,118,456
`9/2000 Cooper
`12/2000 Sutherland et al.
`6,167,442
`6,182,114
`1/2001 Yapetal.
`4/2001 Warner etal. ............... .. 382/232
`6,212,301
`6/2001 Castoretal.
`382/232
`6,246,797
`6,285,317
`9/2001 Orig ....................... .. 342/357.57
`11/2001 Dekeletal.
`................. .. 709/203
`6,314,452
`12/2001 Castellietal.
`.............. .. 345/420
`6,326,965
`2/2002 Li etal.
`6,345,279
`.................. .. 345/419
`2/2002 Chan et al.
`6,346,938
`5/2002 Lincke et al.
`6,397,259
`6,449,639
`9/2002 Blumberg
`.
`12/2002 Yaron et al.
`6,496,189
`..
`2/2003 Gadhet al.
`6,525,732
`..
`8/2003 Rossetal.
`6,608,628
`8/2003 Dowelletal.
`6,608,933
`9/2003 Li etal.
`....................... ..
`6,625,309
`6,650,998
`11/2003 Rutledge etal.
`.......... ..
`3/2004 Robothametal.
`6,704,024 32 =1
`3/2004 Harris ......................... ..
`6,704,791 31*
`3/2004 Changetal.
`6,711,297 31*
`6/2004 Wen etal.
`6,754,365 31*
`.............. ..
`6,801,665 31* 10/2004 Atsumietal.
`6,882,755 32*
`4/2005 Silverstein etal.
`......... ..
`6,898,311 32*
`5/2005 Whitehead .... ..
`6,970,604 31* 11/2005 Chai
`......... ..
`7,908,343 32*
`3/2011 Levanon etal.
`8,924,506 32* 12/2014 Levanon etal.
`
`............ .. 709/217
`
`OTHER PUBLICATIONS
`Michalson Declaration Appendices P-EE (all pages).
`Michalson Declaration with Appendices A-O (all pages).
`Michael Potrnesil, “Maps Alive: Viewing Geospatial Information on
`the WWW”, Computer Networks and ISDN Systems vol. 29. issues
`8-13, pp. 1327-1342.
`Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges,
`Augusto OP den Bosch, Nickk Faust, “An Integrated Global GIS and
`
`Microsoft Corp. Exhibit 1001
`
`
`
`U.S. Patent
`
`Feb. 2,2016
`
`Sheet 1 of5
`
`US 9,253,239 B2
`
`.v;au-rwvnuovrttnrtr
`
`N‘;
`\\~\\\§\\.\.\¢
`.3
`i
`“N‘\
`{ix\3
`
`“
`,&,.“.....»«..~..‘,}
`
`33$
`
`\ 2
`
`ma
`
`§5~
`
`.
`
`.
`
`.}
`.
`. ,3
`_.,.»~
`\ .,.,.,..:,,,,,,,,\\§\\
`E
`%~é§.‘:s<::3§:<
`uh‘ .
`\\.
`§§.2‘§i~R
`:
`
`§ §
`
`»~“»“-..~.».sw.»m»“¢
`
`.mwz.auu.w§:«.~z.u;.wa”5
`
`‘.-N»...-.\.§\
`
`§s§§as2:_,~s::\
`
`‘\_\.....\.\..,........._....
`,_
`“_H..
`mm.-akisii
`3:313.
`
`‘.«-\“':--L
`9*»
`
`,
`
`\
`»
`,
`........_........,.........2
`
`._
`
`_
`
`3%‘
`‘3
`.5"
`,3e’
`
`ru;.v-«Amway/rrrAo*o¢r///ra.,.“’i9,.—4ttrr/at4w¢rt//rr.r.a»r1A’//
`
`4\v
`
`§::>:,a
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`
`
`U.S. Patent
`
`Feb. 2,2016
`
`Sheet 2 of5
`
`US 9,253,239 B2
`
`2
`§.::<.s.,:§’m§;
`~\
`M.,..
`\\\\\\vvs\\v\M V\\h\\~vn\N\\\\‘
`§.:::a§2:s.«§-
`
`gA
`
`‘
`
`\\\-\\\\\\I\\\\\\\\«\s\\\\tAK&4A
`}
`
`‘C
`
`\
`
`\-u-»~.\\~»\s\\\s\\\§\\\\-.\.\.«.\\\§
`n
`
`.....,,.,.f,.w,...-w
`
`“um.
`
`,
`
`.
`
`\I\\'»\V$\\\\\\
`§
`.....................
`
`Ru
`i
`
`\‘ _
`5: -\
`........g...\.
`‘§...-;,\.-~ \v.3§-‘
`§‘§§.‘駒?\$§§ msxssaé ~
`~“““““““‘
`..
`-J\\vw\v~\\\~4\r»\»-u~.v.»vu\-ur.-xxx-n
`
`5‘, WWW g. gm?‘
`.~ é)‘.
`I g,
`\n_ ,3’: ,2‘.
`t
`2
`°
`"
`‘
`
`.-~. .--.
`F, }\
`\__....\\.....~..\..\.,,.‘,,,.,,\...,,§
`~\.
`§§;**3
`LMW
`2.-‘
`Pass. 5.:
`i
`V ..,,,,,,,..
`W.
`§
`i,::'}é§;§s§z.?f§, W
`-«u«»«wmw.~w.s.w..,.».m\e
`
`\svv\ssVV\s\\\sVsss\Vs
`
`xx,/r///W/rr,/1%,,’/,”«nun
`
`‘I :33v(,1?‘' W.’/A
`
`,-
`x
`(.
`
`{,
`
`£3“.
`
`§§§ §
`
`.7
`
`»
`
`i E
`
`a,
`
`Microsoft Corp. Exhibit 1001
`
`:4gpa/nwrwav/7rv.oa¢
`7.”.-..n..yrr-w.a
`
`i
`
`-mm
`
`....-m.\\
`
`\\,\_\
`‘N
`
`\u\\\'~\\I\\\\\\\\\\V.\\\\~\s\V\s\s\svusx
`
`\\\\\\\\\\\\\n\\n-A-nswsvg
`
`,,.,,.,,,,,
`
`. -suvsvuus-xx-v\\\s\'\\'vI~\\\\\\\\»\\s\\vL\\»\\\\\«~\s\«\»\s4.-‘vs,-
`
`.~'
`3‘ ‘«
`..~~
`#3
`
`
`.“m~...‘\...\._\\...
`.
`
`.
`K x
`
`.
`\
`_.-.
`~;
`\
`§usm:§sas§
`§
`\
`L.........mm.
`...~....\.
`KN
`‘\"““'~nr\\\..gw,.,
`
`\ _
`
`Microsoft Corp. Exhibit 1001
`
`
`
`U.S. Patent
`
`Feb. 2,2016
`
`Sheet 3 of5
`
`US 9,253,239 B2
`
`"“'°‘“°"
`
`so/\‘
`
`DETERMINE l
`
`VIEWABLE PARCELS
`fog upum
`
`EXAMINE
`QUADTREES
`
`REQUEST PARCEL
`
`Dowmoms
`
`Smut PARCEL To
`
`Dumas: Nun:
`
`TRIM
`
`UUADTREE Nooss
`
`REQUEST
`
`Wunus?
`
`Sam HtGHEST
`
`Pmomv Rsoussr
`Wamms
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`
`
`U.S. Patent
`
`Feb. 2,2016
`
`eehS
`
`5fl.04
`
`US 9,253,239 B2
`
`3- u ‘
`. -~- ~‘\~..\.\..m\
`.»“.s\..:ea‘s.:~s
`
`\\\\\\\~\\\\\ssImus-\»s\»\\\-v~s\-v\
`
`i“ “s
`
`t35%;.3333
`
`M“
`
`>n(\I(\\\\\\K\\\.\\\\.A\\\\h\.A\.A\.a\
`
`Microsoft Corp. Exhibit 1001
`
`
`
`
`
`\\i.\\\\\\\\\\\\\%\\\\\\\\\\\\\\xxs....\xx..\..\\\\\s\\\\\§.<\\\\§\§\\\\i\§\\\\\\\M
`
`\\\\\\\\.\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\VV\VV\\»\\\\\\\\\\\\\\\.\\\\\\\\\\\\\\\\\\\\\.\\\\\\\\\\\\\\V\\\\\\\>\\\\\\\.\\\\\\\\\\\\\\\\\\s.\\\\\\\\\.\\\\¢.\\\\
`
`\3§
`
`,~~m“.\n\“~.~E',\x\~.\\\\
`
`3
`W
`......“.....~.§\mW.,.(.\
`
`\
`m“......\..\..
`
`«chm.
`
`ss=3§:3533ss»..§\\§§.u
`
`“m.‘.“.._\\m;.m..\m\..\
`
`Microsoft Corp. Exhibit 1001
`
`
`
`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 5 of 5
`
`US 9,253,239 B2
`
`\\\\u-sA\\\\A\A\\\\x\\\u\\\n
`
`5%,
`
`»W.NNmM.NNNn
`
`..:.t\t2.z\.\..\.i3i.. :....$:».tE=..:.t2zz..:..:.5.k
`
`
`
` \\\.\\§\\x\:..!»\§u>.2.«u.
`
`\\,1\\\\‘(\)-‘(K-\V£(\V.i€'€\\7(\‘<i\Y\\\
`\
`., .\
`
`'
`
`R»
`
`V»
`
`.aw»
`
`5....
`
`.\
`
`\r:.&
`
`$1
`§W.MMM.mw.%
`E
`S-‘as?
`:3
`§
`
`i\..x..l..
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`
`
`US 9,253,239 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`'
`
`This application is a continuatio11 of and claims priority to
`U.S. patent application Ser. No. 13/027,929, entitled OPTI-
`MIZED IMAGE DELIVERY OVER LIMITED BAND-
`
`WIDTH COMMUNICATION CHANNELS, filed on 15 Feb.
`2011, now allowed; which is a continuation in part of and
`claims priority under 35 USC 120 to U.S. paten application
`Ser. No. 12/619,643 filed on Nov. 16, 2009, now U.S. Pat. No.
`7,908,343 which in turn is a continuation of and claims pri-
`ority 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 chan-
`nels” (that now issued on Jan. 5, 2010 as U.S. Pat. No. 7,644,
`131) which in turn claims the benefit under 35 USC 1 19(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.
`
`FIELD
`
`The disclosure is related to network based, image distribu-
`tion systems and, i11 particular, to a system and methods for
`efficiently selecting a11d 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-
`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 higl1-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 late11cy 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- 55
`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 65
`differential coefficients to represent an image. Subsequent
`transmitted coefiicient sets are progressively accumulated
`
`2
`
`with prior transmitted sets to provide a succeedingly refined
`image. The inverse-transform function perfomied by the cli-
`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 subdivided into a regular array. This
`enables the inverse-transform function 011 the client, whic 1 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 leve 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., L .S.
`Pat. No. 6,182,114, overcomes some of the foregoing prob-
`lems. TheYap 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 d'vi-
`sion is indexed to the encoding level of the transform. "he
`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 fron1 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 i11 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 ofimage visualizationwould 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, tablet and or personal
`digital assistant
`(PDA)
`is a characteristic small client.
`Embedded, low-cost kiosk, automobile navigation systems
`and or Internet enabled I connected TV are other typical
`examples. Such systems are not readily capable, if at all, of
`performing complex, compute-intensive Fourier or wavelet
`transforms, particularly within a highly restricted memory
`address space.
`As a consequence of the presumption that the client is a
`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-
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`
`
`US 9,253,239 B2
`
`3
`
`4
`
`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 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,
`oarticularly 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
`Jandwidth data chamiel or indirect constraints imposed on
`‘elatively high-bandwidth charmels by high concurrent user
`loads. Cellular connected PDAs and webphones are examples
`of small clients that are frequently constrained by limited
`oandwidth conditions. The conventionally realizable maxi-
`num network transmission bandwidth for such small devices
`
`nay 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
`nore than utilizing wavelet-based data compression is
`advanced as permitting effective operation at low communi-
`cations bandwidths. While reducing the amount of data that
`nust be carried from the server to the client is significant, Yap
`et al. simply relies on the data packet transfer protocols to
`orovide for an efficient transfer ofthe 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 efiiciently utilize low to very low band-
`width network connections.
`
`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 charmels 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 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
`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.
`A fiirther advantage of the present invention is that the
`client software system requires relatively minimal client pro-
`cessing power and storage capacity. Compute intensive
`munerical 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, 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-
`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 ofthe present invention is that image
`parcel data rendering is performed without requiring any
`complex underlying hardware or software display sub system.
`The client software system ofthe present invention includes a
`bit-map rendering engine that draws directly to the video
`memory ofthe 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. 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 011
`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 i11 connection with the accompanying drawings,
`in which like reference ntunerals 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;
`
`Microsoft Corp. Exhibit 1001
`
`Microsoft Corp. Exhibit 1001
`
`
`
`US 9,253,239 B2
`
`5
`
`6
`
`'
`
`FIG. 5 is a process flow diagram showing a mai11 process-
`ing thread implemented in a preferred embodiment of the
`present invention;
`FIG. 6 provides a process flow diagram showing a network
`request thread implemented i 1 a preferred embodiment of the
`present invention;
`FIG. 7 provides a process 1ow diagram showing a display
`image rendering thread implemented in a preferred embodi-
`ment of the present inventior;
`FIG. 8 provides a process flow diagram showing the parcel
`map processing performed preliminary to the rendering of
`image data parcels in accorc ance with a preferred embodi-
`ment of the present inventior;
`FIG. 9 provides a process flow diagram detailing the ren-
`dering and progressive prio‘itization of image parcel data
`download requests in accorcance with a preferred embodi-
`ment of the present invention; and
`FIG. 10 provides a process flow diagram detailing the
`determination of an optima 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-
`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 coimected
`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.
`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 ofderivative images of
`progressively lower image resolution. The source image data
`32, corresponding to the series image K.sub.O, is also subdi-
`vided into a regular array such that each resulting image
`parcel ofthe 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.l-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 image array dimensions
`In other implementations,
`(which as 64x64 above) may be powers of two so that the
`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
`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
`the parcel.
`The system may also accommodate different and larger
`data parcel sizes as transmission protocols, compression ratio
`achieved a11d micro-architectures of the client computers
`change. Forpurposes above, the data content was a pixel array
`representing image data. Where the data parcel content is
`vector, text or other data that may subject to different client
`system design fact