US009253239B2
`
`a2) United States Patent
`US9,253,239 B2
`(10) Patent No.:
`*Feb. 2, 2016
`(45) Date of Patent:
`Levanon etal.
`
`(54)
`
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(71)
`
`Applicant: BRADIUM TECHNOLOGIESLLC,
`Suffern, NY (US)
`
`(72)
`
`Inventors:
`
`Isaac Levanon, Raanana (IL); Yonatan
`Lavi, Raanana (IL)
`
`(73)
`
`Assignee: BRADIUM TECHNOLOGIESLLC,
`Suffern, NY (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`US.C. 154(b) by 0 days.
`
`This patent is subject to a terminal dis-
`claimer.
`
`(21)
`
`Appl. No.: 14/547,148
`
`(22)
`
`Filed:
`
`Nov. 19, 2014
`
`(65)
`
`(63)
`
`Prior Publication Data
`
`US 2015/0180928 Al
`
`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)
`
`(2006.01)
`(2006.01)
`(Continued)
`
`(51)
`
`Int. Cl.
`GO6F 15/16
`HOAL 29/06
`
`(52)
`
`U.S. CL
`
`CPC oe HO4L 65/602 (2013.01); GO6F 3/1454
`(2013.01); GO6T 3/4092 (2013.01); HO4E
`67/42 (2013.01); GO9G 2340/02 (2013.01);
`G09G 2350/00 (2013.01)
`
`(58) Field of Classification Search
`CPC..... GO6T 3/4092; GO9G 2340/02; GO6F 3/14
`USPC we 709/202, 203, 217, 230, 246, 247;
`345/625; 382/232, 305
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,682,869 A *
`4,972,319 A
`
`7/1987 Itohetal. ow 358/426.12
`11/1990 Delorme
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`WO
`
`1070290 BL
`99/41675
`
`1/2001
`8/1999
`
`OTHER PUBLICATIONS
`
`Potmesil Maps Alive with dArmaud 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 communica-
`tions channels for display on a client device by selecting an
`update imageparcel 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 imageparcelis received from the
`communications channel and displayed as a discrete portion
`of the predetermined image. The update image parcel opti-
`mally hasa fixed pixelarray size,is received in a single and or
`plurality of network data packets, and were the fixed pixel
`array may be constrainedto a resolution less than or equal to
`the resolution of the client devicedisplay.
`
`25 Claims, 5 Drawing Sheets
`
`
`
`BF
`Panceuiaer Dark
`
`sosnen
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`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.
`
`(60) 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 on 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.
`
`(51)
`
`(56)
`
`Int. Cl.
`GO6F 3/14
`GO6T 3/40
`
`(2006.01)
`(2006.01)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1/1993 Dawsonetal.
`5,179,638 A
`11/1993 DeAguiar etal.
`5,263,136 A
`6/1994 Ingaetal.
`5,321,520 A
`9/1996 Poulter et al. oe. 345/428
`5,559,936 A *
`
`3/1997 Todiceetal. owe 345/428
`5,613,051 A *
`10/1997 Ligtenberg etal.
`5,682,441 A
`6/1998 Migdal
`5,760,783 A
`8/1998 Baldwin
`5,798,770 A
`8/1999 Hassan et al.
`5,940,117 A
`11/1999 Wuetal.
`5,987,256 A
`5,995,903 A * 11/1999 Smithetal. wwe. 701/470
`6,118,456 A
`9/2000 Cooper
`6,167,442 A * 12/2000 Sutherland et al... 709/217
`6,182,114 Bl
`1/2001 Yap et al.
`6,212,301 BL*
`4/2001 Wamner et al. uu. 382/232
`w. 382/232
`6,246,797 BL*
`6/2001 Castoretal.
`
`9/2001 Ong woe 342/357.57
`6,285,317 BL*
`6,314,452 BL* 11/2001 Dekel etal. oe. 709/203
`6,326,965 BL* 12/2001 Castellietal. o.. 345/420
`2/2002 Lietal.
`6,345,279 BI*
`2/2002 Chan etal. wo. 345/419
`6,346,938 BI *
`6,397,259 BL*
`5/2002 Linckeetal.
`.. 709/236
`6,449,639 BL*
`9/2002 Blumberg...
`we 709/217
`6,496,189 BL* 12/2002 Yaron etal. .
`.. 345/428
`6,525,732 BL*
`2/2003 Gadhetal. ..
`.. 345/428
`6,608,628 BL*
`8/2003 Rossetal.
`..
`.. 345/619
`6,608,933 BL*
`8/2003 Dowelletal.
`w 382/232
`6,625,309 BL*
`9/2003 Lietal. wee 382/173
`6,650,998 BL
`11/2003 Rutledgeetal.
`............ 345/581
`6,704,024 B2*
`3/2004 Robotham etal.
`6,704,791 BL*
`3/2004 Harris woe 709/231
`. 382/240
`6,711,297 BL*
`3/2004 Changetal.
`
`. 382/100
`6,754,365 BL*
`6/2004 Wenetal.
`...
`6,801,665 BL* 10/2004 Atsumiet al. oo... 382/239
`4/2005 Silverstein et al.
`........... 382/282
`6,882,755 B2*
`.. 382/166
`6,898,311 B2*
`5/2005 Whitehead......
`.
`
`6,970,604 BL* 11/2005 Chai ou...
`.. 382/240
`
`7,908,343 B2*
`3/2011 Levanon etal.
`ve 109/217
`8,924,506 B2* 12/2014 Levanonetal. 0. 709/217
`
`
`
`
`
`OTHER PUBLICATIONS
`Michalson Declaration Appendices P-EE(all pages).
`Michalson Declaration with Appendices A-O (all pages).
`Michael Potmesil, “Maps Alive: Viewing Geospatial Information on
`the WWW”, Computer Networks and ISDN Systemsvol. 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
`
`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 Standard Version 1.1, Mar. 1997, available: https://www.
`opengl.org/documentation/specs/version|.1/glspec!.1/node84.
`html#SECTION0068 1 100000000000000, (all pages).
`H. Hoppe, Progressive Meshes, SIGGRAPH 96: Proceedingsofthe
`23rd annual 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://msdnsmicrosoft.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/specs/version| .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 796, Fifteenth Annual Joint Conference of the
`IEEE Computer Societies, Networking the Next Generation, Pro-
`ceedings IEFE 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. Hansenetal, “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 Toolfor 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 claimspriority (all
`pages).
`Numbering of Claim Elements of Challenged Claims of the 506
`Patent, (all pages).
`(Ex. 1002) and
`Claim chart
`illustrating teachings of Potmesil
`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 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 1 of 5
`
`US 9,253,239 B2
`
`QTY
`horroroinya
`Ses
`\
`Aan,
`Ba
`_s _ ge
`we
`a
`anne
`a
`*
`le ao
`ope
`SN
`
`ery
`oe
`
`en,
`ws
`x
`\
`x
`x
`\
`xwS
`
`
`
`
`%
`
`
`SoooBitesRoetboreecuttin,—we
`ee“oweaseey
`pysteetityB3
`
`SRE
`Boag
`SESS
`oN
`-
`
`4,rat
`gE
`
`SE
`{
`eyate
`
`
`
`sees
`a
`
`PIG.
`
`4]
`
`‘
`‘
`
`Pe
`
`
`
`
`a
`
`\
`
`pevennnncnancnunnnnnny
`
`.
`
`Banari, (38
`
`Datsa8
`;
`.
`
`.
`CNTR{
`o 43
`Beanenceaanannnannannal
`
`sqesannnndnnnnnnnnennny
`os a
`PaSee N
`‘ RERIRE i
`
`: oseS>
`§
`:
`Ns aan
`i
`i Se
`Ae x
`‘
`R
`Das SON
`
`ae
`
`enhOonnnnnyg
`
`
`vg—
`Rerayx
`seemed SANs
`WenetnPEPPLLPLLLDLEE
`
`ey,in
`
`ByeProres
`Panease?
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 2 of 5
`
`US 9,253,239 B2
`
`\ P
`
`z3
`
`:
`gestern
`
`moons BRBLAY
`
`a Bamamnnpin
`
`RecaanQenueeyi “ éAAAAASAAMANNNS
`
`
`Tig aseevcenreretrarensnenaofesowi
`
`gz.ioe2
`
`alone ay
` {SNR
`eoceeensanty
`‘pag Frese fRtsoon
`asewers
`tans
`
`LOMf~xe
`‘
`PA
`Ost8 Qeee
`m
`;oo REY
`ae
`qmoneaaacenny
`Save.
`sa
`Fan8s
`
`wa
`
`| PRESSSanaaano
`A aRe.
`
`3:
`
`spaaanntannannnnannennnniinnins
`
`eas
`$wee—NCARAARAAAARE
`-Daaeer Rave
`PANE. ESYS
`
`t&
`
`NWSE ah.wget
`
`ii
`
`an #st
`
`fo
`
`sm
`Na
`
`poneNe cosennnnena
`SOLIOSEIIC4x
`
`
`Avywane Bata Bacery
`Sasmonnnensnnnnanathatinanggaennanqnnnsenasnaasinaanagianssaneaa
`2
`‘
`-ao
`4
`
`\
`
`XK
`
`i[ FAREDAA K
`——an
`
`6
`
`Moaaiesnnntioy
`
`sf
`
`rnin%
`
`oY
`
`FIG. 4
`
`@ 8s
`casiennendionmnnnSS
`\
`
`:
`g
`3
`3
`
`3
`
`MRED
`x
`eA y
`Pex
`x
`PROEEER
`\
`:
`:
`;
`
`pornowmnmnrinny
`:;
`‘
`s
`‘
`i
`:
`sosenenennanie) SERS |
`t Sasac
`‘
`
`g
`runny
`:
`5
`t Newey
`|
`\
`:
`x
`y
`:
`‘
`Reannapgrrnnnnrcint
`‘
`i
`
`£s
`£0
`
`es hoe,
`eedtrs
`nthe
`wr ae
`
`»
`Saswrarrennanrnnnnnennsnint
`
`|
`
`2
`8S
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb.2, 2016
`
`Sheet 3 of 5
`
`US 9,253,239 B2
`
`82
`DETERMINE _
`
`VIEWABLE PARCELS
`
`
`
`For Upoate
`
`
`
`
`
`
`REQUEST PARCEL
` Issue PRIORITY
`DOWNLOADS
`
`REQUESTS
`
`QuadTREE NODE
`
`90
`92
`
`NAVIGATION
`
`EVENTS
`
`go” ~
`
`Fic. 5
`
`NETWORK
`
`88
`
`RECEIVE PARCEL
`
`STORE PARCEL TO
`
`EXAMINE
`QUADTREES
`
`.
`
`...*‘GO
`
`
` TRIM
`
`
`QUADTREE NODES
`1
`
`94
`
`
`
`REQUEST
`WAITING?
`
`
`SELECT HIGHEST
`WAM FOR
`
`
`
`Priority REQUEST
`REQUEST THREAD
`
`
`
`WAITING
`FREE
`
`102
`
`
`
` EXAMINE
`Fic. 6 400 J
`106
`
`Priority QUEUE
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 4 of 5
`
`US 9,253,239 B2
`
`AAASAAASSEN
`
`Ns,3|~x
`
`ye
`eYee
`
`wy‘Es
`oe2osms
`
`,“peerbee?wttfoshoetn,Chak7Rez“eCbpeneaahbeSeOS‘5ebZoyBS4hghtSen.a£3hed%%getogZeedé$anZgGe,en5sas4,4gLone5Z“ft4bee433gZ3we%POPPER
`
`
`
`APEESSSAADESISESESFrecererenes:teLAMPAAOALEPOEDOELIE
`veamnsnonercayZeevecoliohDeny34eoreee,4+%$eee.oogtGag“gifFOmkegtan$2,;t;Weegehakg4BesIEZ1fee,BE%h5;CA,Wis.53HeieeG;&whé$4."3ona$Sipifs“iji&4|eey|&|iVROREEEELEAAEMOPURPUBEREDIIDIPODED.Leceneneranrersrectesrossrerestte
`
`
`precxiiwej6%ieHeioifratagZnniZfon5¢y4weer;3%Eegne$aOEA1
`
`
` LPIPRIPPLIFISLPLECLELLLSSDASLLEES ogee%ooffESSgetoe:
`brcerarenenpenttethéserceverseresvacessecceceeteneéD4ai4j;i45;£zs$Lg34:3iZiZZ;ii3iyGARR
`
`
`i33g5%Z<3eetEe:febon3teitahen$eee.tte,fee.£weerarwetya}6%etebee.ZweHEzie,we4teEeaeOdwae4tfegetZ4ZaHSSevrte.WREDneaPhnarensnaitgerlKou,2552evcnooenees4waSefnaefoehetenngen
`4,}%eeeeeeeestttIOAISSEPPEBPPIEOSS|ce
`
`PLOLORERLELEECUOTITTEETEESESEEPEELEDIEDIODOPODEDELEDEDODOVOOTELELEEASNIOUUIDSEEDIIEBi
`ogee:j34,¢vr‘,f;1%,-provnnenctennannnnnnnngsportbernennnsansditiy
`
`
`ing“ySA3Zae“Grag“erectmnnmenreigséheggrcerreeccrrcet?
`
`POLEOLIETEPIEPSPLPOPIEPIOPLOPLOPELPLTTTOLTEBELLLELLETUESCOLESGEGTE:
`hspUEeeki4FeteZ$Zatts$y,HE5oy4Mh,Btn3os,,Ble.
`
`
`thg4,4weEGZun54EGbh GOLILLILLLPLLISSEPPPOPPLG,iZ%Zoyeimg,Be7%4¢4geBeqoadage4caZeAtheToeadganiMthhet
`
`
`
`roe
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 5 of 5
`
`US 9,253,239 B2
`
`peeweereneancanna
`
`Sx
`4a
`
`nf
`
`i¥
`
`
`
`‘”LPLOPIEULOPIRTLEDSSSi5£Bothei5iZ7:“ezwsii,otfiwg;ToezSannnrnelbanaCnnmnnnaganannnntannicd
`cenereclgfeds/&Swestionthe,fe?igthepfore
`
`noiteez54}$.BF;5;i;Oe
`
`
`
`SCceceeeceCLRETELRAELELIALELLPAISLAALAALIEADOOOODNCLOROOODDPAPOSILOSIAHESIEEAIELTAODOABCCOOOCOOECOCOCOEDOOPUDCCCOPCDIOODUPCDISLICSOELONLEELTEAILOLOBLSBEESOOELAPACORLELLOEAECCEOACLIECIEEASCURSIOLEBETLELIECUECODESCECILICELOALOALIDICGLEEITCLOTORErEICOELCCLALORCTCCCCCROCCRCCCTECCtttty5ziZindaiipomesmecesensasesfefAfperritecresrccreeceererseyjZ;g?7ice¢?iH;3Ziii3zEg:Zi4cranseaseaitasIETHER:BOCA
`
`
`°F,
`.&aa3tieeBeg5SeokEeweee:%afieeetee¢xOnAANTURIRAIASEtssrronvononsossarsosedttwaneaoe£i3é飣rhe
`
`
`seedbengeeeZ
`encenasnectnnnnrtonenesecensscctetdnetttintinterussetinssatacrsscerternancetcrrecteecasseeceesstoobanssoorssmerransserenserverserveetesseteecenseees
`4:.orZcaeEote
`iaEi”err
`feheedneaf
`eonsgenvsfCoot
`
`fste,$£e4%
`
`
`fdBBounjeevicaifoodsae
`
`J2©mina‘Bs
`
`z4
`
`
`
`vy
`
`4
`poy
`Seay
`
`a
`
`a‘2
`
`Seb
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`
`
`
`

`

`US 9,253,239 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`wm
`
`This application is a continuation of and claimspriority to
`US. 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
`claimspriority 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 whichin turn is a continuation of and claimspri-
`ority under 35 USC 120 to US. patent application Ser. No.
`10/035,987 filed on Dec. 24, 2001 and entitled “Optimized
`imagedelivery over limited bandwidth communication chan-
`nels”(that now issued on Jan. 5, 2010 as U.S. Pat. No. 7,644,
`131) which in turn claimsthe benefit under 35 USC 119(e) of
`USS. 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.
`
`2
`with prior transmitted sets to provide a succeedinglyrefined
`image. The inverse-transform function performedbythecli-
`ent computer is, however, highly compute intensive. In order
`to simplifythe transform implementation andfurther reduce
`the latency of presenting any portion of an approximate
`image,
`images are subdivided into a regular array. This
`—
`enables the inverse-transform function onthe 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 resolvingfiner levels of detail.
`An imagevisualization system proposed byYapet al., U.S.
`Pat. No. 6,182,114, overcomes someof the foregoing prob-
`lems. The Yapet al. system also employsa 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
`encodedtransform coefficient data sets are, therefore, of con-
`stant size, which supports a modest improvementin the algo-
`rithmic performance of the inverse transform operation
`required ontheclient.
`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 imageblockrepresents
`the area of highest image resolution, with resolution reduc-
`tion as a function ofdistance fromthe gaze point determined
`bythe foveation operator. This technique thus progressively
`builds image resolution at the gaze point and succeedingly
`The Internet and or other network systems may provide a outward based onarelatively compute intensive function.
`
`unique opportunity to transmit for example complex images,
`Shifts in the gaze point can be responded to with relative
`typically large scale bit-maps,particularly those approaching
`speed by preferentiallyretrieving coefficient sets at and near
`photo-realistic levels, over large area and or distances. In
`the new foveal region.
`common application, the images may be geographic, topo-
`Significant problems remain in permitting the convenient
`graphic, and or other highly detailed maps. Thedata storage
`and effective use of complex images by manydifferent types
`requirements and often proprietary nature of such images
`of client systems, even with the improvements provided by
`could be such that conventional interests maybeto transfer
`the various conventional systems. In particular, the imple-
`the images on an as-neededbasis.
`mentation of conventional image visualization systems 1s
`In conventionalfixed-site applications, the image data may
`generally unworkable for smaller, often dedicated or embed-
`be transferred over a relatively high-bandwidth network to
`ded, clients where use ofimage visualization would clearly be
`client computer systems that in turn, may render the image.
`beneficial. Conventional approacheseffectively presume that
`Client systems maytypically implement a local image navi-
`client systems have an excess of computing performance,
`gation system to provide zoom andor pan functions based on
`memoryand storage. Small clients, however, typically have
`userinteraction. As well recognized problem with such con-
`restricted performanceprocessorswith possibly no dedicated
`ventional systems could be that full resolution image presen-
`floating-point support, little general purpose memory, and
`tation may be subject to the inherent transfer latency of the
`extremely limited persistent storage capabilities, particularly
`network. Different conventional systems have been proposed
`relative to common image sizes. A mobile computing device
`to reduce the latency affect by transmitting the image in
`such as mobile phone, smart phone, tablet and or personal
`highly compressed formats that support progressive resolu-
`digital assistant
`(PDA)
`is a characteristic small client.
`tion build-up of the image within the currentclient field of
`Embedded, low-cost kiosk, automobile navigation systems
`view. Using a transform compressed imagetransfer function
`and or Internet enabled I connected TVare other typical
`increasesthe field of the image that can be transferred over a
`examples. Such systems are not readily capable,if at all, of
`fixed bandwidth network in unit time. Progressive image
`performing complex, compute-intensive Fourier or wavelet
`resolution transmission, typically using a differential resolu-
`transforms, particularly within a highly restricted memory
`tion method, permits an approximate image to be quickly
`address space.
`presented with image details being continuously added over
`As a consequence of the presumption that the client is a
`time.
`substantial computing system, conventional imagevisualiza-
`tion systems also presume that the client is supported by a
`Tzou, in U.S. Pat. No. 4,698,689, describes a two-dimen-
`sional data transform system that supports transmission of
`complete operating system. Indeed, many expect and require
`differential coefficients to represent an image. Subsequent
`an extensive set of graphics abstraction layers to be provided
`transmitted coefficient sets are progressively accumulated
`bythe client system to support the presentation ofthe deliv-
`
`
`
`FIELD
`
`25
`
`The disclosureis related to network based, imagedistribu-
`tion systems and, in particular, to a system and methods for
`efficiently selecting anddistributing imageparcels through a
`narrowbandorotherwise limited bandwidth communications
`channel to support presentation of high-resolution images
`subject to dynamic viewing frustums.
`
`BACKGROUND
`
`35
`
`40
`
`45
`
`
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`US 9,253,239 B2
`
`3
`ered imagedata. In general, these abstraction layers are con-
`ventionally considered required to handle the mappingof the
`image data resolutionto the display resolution capabilities of
`the client system. That is, resolution resolved image data
`provided to the client is unconstrained byany 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 bedisplayed.
`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 webphonesare examples
`of small clients that are frequently constrained bylimited
`bandwidth conditions. The conventionally realizable maxi-
`mum network transmission bandwidth for such small devices
`may range from below one kilobit per secondto 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 ofdata that
`must be carried from the serverto the client is significant, Yap
`et al. simply relies on the data packet transfer protocols to
`provide for an efficient transfer ofthe compressed imagedata.
`Reliable transport protocols, however, merely mask packet
`losses andthe resultant, sometimes extended recovery laten-
`cies. When such covered errors occur, however, the aggregate
`bandwidthof the connection is reduced and the client system
`can stall waiting for further image data to process.
`Consequently, there remains a need for an imagevisual-
`ization system that can support small client systems, place
`few requirements on the supporting client hardware andsoft-
`ware resources, andefficiently utilize low to very low band-
`width network connections.
`
`
`
`SUMMARY
`
`Thus, a general purposeofthe present inventionis to pro-
`vide anefficient system and methods ofoptimally 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 imageparcel 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 asa discrete portion
`of the predetermined image. The update imageparcel opti-
`mally hasa fixed pixelarray size, is recetved ina single and or
`plurality of network data packets, and were the fixed pixel
`array may be constrainedto a resolution less than or equal to
`the resolution ofthe 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 onthe display resolu-
`tion of the client system.
`Another advantage ofthe present invention is that the pri-
`oritization of image parcel requests is based on an adaptable
`parameter that minimizes the computational complexity of
`
`40
`
`45
`
`60
`
`4
`determining request prioritization and, in turn, the progres-
`sive improvement in display resolution within the field of
`viewpresented on a client display.
`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.
`Theclient 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
`optimizedto 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 therate of point-of-view navi-
`gation exceedsthe data requestrate.
`Yet another advantage ofthe present inventionis that image
`parcel data rendering is performed without requiring any
`complex underlying hardwareor softwaredisplay subsystem.
`Theclient software system ofthe present invention includes a
`bit-map rendering engine that draws directly to the video
`memoryofthe display, thus placing minimal requirements on
`any underlying embeddedordisk operating system and dis-
`play drivers. Complex graphics and animation abstraction
`layers are not required.
`Still another advantage of the present invention is that
`imageparcel block compressionis used to obtain fixed size
`transmission data blocks. Image parcel data is recoverable
`from transmission data using a relatively simple client
`decompression algorithm. Usingfixed size transmission data
`blocks enables imagedata 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 betransferred to the client software
`system for concurrent display. Array overlay data, correlated
`positionally to the imageparcel data and generallyinsensitive
`to imageparcel resolution, can beinitially or progressively
`providedto the client for parsing andparallel presentation on
`a client display image view.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These and other advantages and features of the present
`invention will becomebetter understood upon consideration
`of the following detailed description of the invention when
`considered in connection with the accompanying drawings,
`in whichlike reference numerals designatelike parts through-
`out the figures thereof, and wherein:
`FIG. 1 depicts a preferred system environment within
`which various embodimentsofthe present invention can be
`utilized:
`FIG. 2 is a block diagram illustrating the preparation of
`image parceland overlay data set that are to be stored by and
`served from a network server system in accordance with a
`preferred embodimentof the present invention;
`FIG.3 is a block diagram of a client system image presen-
`tation system constructed in accordance with a preferred
`embodimentof 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 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`US 9,253,239 B2
`
`
`
`6
`5
`graphical icons, decals, line segments, and or text and or other
`FIG.5 is a process flow diagram showing a main process-
`characters, graphics andor other media.
`ing thread implemented in a preferred embodiment of the
`The network image server system 30 preferably pre-pro-
`present invention;
`cesses the source image data 32 and or sourceoverlay data 34
`FIG.6 provides a process flow diagram showing a network
`to forms preferred for storage and serving by the network
`request thread implemented ina preferred embodimentof the
`server 12, 22. The source image data 32 is preferably pre-
`present invention;
`processed to obtain a series K.sub.1-N ofderivative images of
`FIG. 7 provides a process flow diagram showingadisplay
`progressively lower image resolution. The source image data
`image rendering thread implementedin a preferred embodi-
`32, corresponding to the series image K.sub.O,is also subdi-
`mentof the present invention;
`vided into a regular array such that each resulting image
`FIG.8 provides a processflow diagram showingthe parcel
`parcel ofthe array has for example a 64 by 64 pixel resolution
`map processing performed preliminary to the rendering of
`where the imagedata has a colororbit per pixel depth of 16
`image data parcels in accordance with a preferred embodi-
`bits, which represents a data parcel size of 8K bytes. The
`mentof the present invention;
`resolution of the series K.sub.1-N of derivative images is
`FIG.9 provides a process flow diagram detailing the ren-
`preferably related to that of the source image data 32 or
`dering and progressive prioritization of image parcel data
`predecessor imagein the series by a factor of four. The array
`download requests in accordance with a preferred embodi-
`subdivision is likewise related by a factor of four such that
`mentof the present invention; and
`each imageparcelis ofa fixed 8K byte size.
`FIG. 10 provides a process flow diagram detailing the
`In the preferred embodimentof the present invention, the
`determination of an optimal detail level for image parcel
`imageparcels are further compressed and stored by thenet-
`presentation for a current viewing frustum in accordance with
`work server 12, 22. The preferred compression algorithm
`a preferred embodimentofthe present invention.
`may implements for example a fixed 4:1 compression ratio
`suchthat each compressed and stored image parcelhasa fixed
`2K byte size. The imageparcels are preferably stored ina 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 imagesetresolution 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 mayuse 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 parcelsizes as transmission protocols, compressionratio
`achieved and micro-architectures of the client computers
`change. For purposesabove, the data content wasa pixel array
`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-
`thermore, the parcel sizes can be different between the server
`and the client. For example the server maycreate parcels or
`hold parcels, for streaming with 256x256 pixel parcel dimen-
`sion and the client my render them as 64x64. In addition,
`parcels sizes on different servers may vary fromoneserverto
`another and from the client side rendering. In the system, each
`grid is treated as a sparse data array that can be progressively
`revised to increase the resolution of the grid and thereby the
`level of detail presented by the grid.
`The source overlaydata 34 is preferably pre-processed 36
`into either an open XML format, such as the Geography
`Markup Language (GML), which is an XMLbased encoding
`standard for geographic information developed by the
`OpenGIS Consortium (OGC; www.opengis.org), or a propri-
`etary binary representation. The XML/GMLrepresentation is
`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