USOO9253239B2
`
`(12) United States Patent
`US 9,253,239 B2
`(10) Patent N0.:
`Levanon et a1.
`
`(45) Date of Patent: *Feb. 2, 2016
`
`(54)
`
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(71)
`
`Applicant: BRADIUM TECHNOLOGIES LLC,
`Suffem, NY (US)
`
`(72)
`
`Inventors:
`
`Isaac Levanon, Raanana (IL); Yonatan
`Lavi, Raanana (IL)
`
`(73)
`
`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. 154(b) by 0 days.
`
`This patent is subject to a terminal dis-
`claimer.
`
`(21)
`
`Appl. N0.: 14/547,148
`
`(22)
`
`Filed:
`
`Nov. 19, 2014
`
`(65)
`
`(63)
`
`Prior Publication Data
`
`US 2015/0180928 A1
`
`Jun. 25, 2015
`
`Related US. 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)
`
`Int. Cl.
`
`(51)
`
`G06F 15/16
`H04L 29/06
`
`US. Cl.
`
`(52)
`
`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.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,682,869 A *
`4,972,319 A
`
`7/1987 Itoh et a1.
`11/1990 Delorme
`
`............... .. 358/42612
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`WO
`
`1070290 B1
`99/41675
`
`1/2001
`8/1999
`
`OTHER PUBLICATIONS
`
`Potmesil Maps Alive with dArnaud Declaration (all pages).
`
`(Continued)
`
`Primary Examiner — David Lazaro
`(74) Attorney, Agent, or Firm iAnatoly S. Weiser, Esq.;
`Techlaw LLP
`
`(57)
`
`ABSTRACT
`
`Large-scale images are retrieved over network commtmica-
`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 commtmica-
`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
`
`
`
`3
`ism-300a ’“
`. “Mag
`3 {arias-sea
`
`\\ “meg,
`
`§¥§ ~§§$§§3§§§
`333mm; 0m
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`US 9,253,239 B2
`
`Page 2
`
`Related US. 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.
`G06F 3/14
`G06T 3/40
`
`(2006.01)
`(2006.01)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`................. .. 701/470
`
`......... .. 709/217
`
`1/1993 Dawson etal.
`5,179,638 A
`11/1993 DeAguiar et a1.
`5,263,136 A
`6/1994 Ingaetal.
`5,321,520 A
`9/1996 Poulter et a1.
`............... .. 345/428
`5,559,936 A *
`
`3/1997 Iodice et a1.
`. . . .
`. . . . . .. 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 a1.
`5,940,117 A
`11/1999 Wuetal.
`5,987,256 A
`5,995,903 A * 11/1999 Smith et a1.
`6,118,456 A
`9/2000 Cooper
`6,167,442 A * 12/2000 Sutherland et a1.
`6,182,114 31
`1/2001 Yapetal.
`6,212,301 31*
`4/2001 Warner et a1,
`111111111111111 ,, 382/232
`6,246,797 31*
`6/2001 Castoretal.
`382/232
`
`6,285,317 31*
`9/2001 Ong ....................... .. 342/35757
`6,314,452 31* 11/2001 Dekel et a1.
`................. .. 709/203
`6,326,965 31* 12/2001 Castelli et a1.
`.............. .. 345/420
`2/2002 Li etal.
`6,345,279 31 *
`.................. .. 345/419
`2/2002 Chan et a1.
`6,346,938 31 *
`6,397,259 31 *
`5/2002 Lincke et a1.
`709/236
`6,449,639 31*
`9/2002 Blumberg
`709/217
`6,496,189 31 * 12/2002 Yaron etal. .
`345/428
`6,525,732 31 *
`2/2003 Gadh et a1.
`..
`345/428
`6,608,628 31*
`8/2003 Rossetal.
`..
`345/619
`6,608,933 31*
`8/2003 Dowell et a1.
`382/232
`6,625,309 31*
`9/2003 Li et a1.
`....................... .. 382/173
`6,650,998 31
`11/2003 Rutledge etal.
`.......... .. 345/581
`6,704,024 32*
`3/2004 Robotham et a1.
`6,704,791 31*
`3/2004 Harris ......................... .. 709/231
`6,711,297 31*
`3/2004 Chang etal.
`382/240
`
`6,754,365 31*
`6/2004 Wen et a1.
`382/100
`6,801,665 31* 10/2004 Atsumietal.
`.............. .. 382/239
`4/2005 Silversteinetal.
`......... .. 382/282
`6,882,755 32*
`382/166
`
`6,898,31132*
`5/2005 Whitehead .... ..
`382/240
`6,970,604 31* 11/2005 Chai
`......... ..
`
`.. 709/217
`7,908,343 32*
`3/2011 Levanon et a1.
`.
`............ .. 709/217
`8,924,506 32 * 12/2014 Levanon et a1.
`
`
`
`
`
`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
`
`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.
`openg1.org/documentation/spec s/Versionl .1/glspec1.1/node84.
`htm1#SECTION0068 1 100000000000000 , (all pages).
`H. Hoppe, Progressive Meshes, SIGGRAPH ’96: Proceedings of the
`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://msdn.microsofi.com/enus/library/ms885773.aspx
`[Accessed Apr. 28, 2015] (all pages).
`OpenGL Standard Version 1.2.1, Apr. 1999, available: https://www.
`openg1.org/documentation/spec s/versionl .2/openg11.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 a1 i‘UMTS: a middleware architecture and mobile API
`approach,” Personal Communications, IEEE, vol. 5, No. 2. pp. 32-38
`(Apr. 1998).
`J. Hansen et a1, “Real-time synthetic vision cockpit display for gen-
`eral aviation,” AeroSense ’99, Intemational 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 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 1 of5
`
`US 9,253,239 B2
`
`\
`K;
`
`N“
`
`s.
`
`A.
`
`“is
`
`my" ri’mmmumufl K
`
`"JIM/I/IW/l/WM/Il"-
`
`
`
`mazzuly/uxr-..'-:
`
`\\~\\\\““\ue
`,5,
`.3
`i
`“P:‘\«ms
`
`‘\\\n“§\t\\wsss\s\\nxnl\l
`.
`.
`,-
`.
`X.“ ":1?
`fififififii E N
`\\A‘x-I‘m-A-A\\~\-A-\\n\k ",1.
`
`{Jar/WMIMWM
`'~»»WWMz/zr%
`
`§ §
`
`,
`
`/,
`
`m‘
`
`,
`
`‘3
`f.
`Ke’
`
`-".'~
`f“ all
`\ “Md,,,,,,,,M
`E
`fié‘maa
`4“ ~
`u.
`§§F§i~§
`:
`
`s1:
`
`(IwIWrtzr/r‘
`Marlin/22'
`
`mwxmw§x
`.
`
`\‘\\\\\Wv~\\v~\\\\\~\¢
`
`/
`
`4:2
`
`§3§§E~§3§$£E$I§§
`23m
`
`,
`
`R3, g
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 2 of5
`
`US 9,253,239 B2
`
`‘
`
`2
`igiimmii
`\
`“.n‘
`i
`§$§§§§ii§§<§c gx
`\\\\\\\M\\V\M mysxwmvn‘m‘
`
`.
`q }
`
`3 9‘?
`“we
`v‘
`in».
`a.
`\\\-\I\\\\I\\\\\\\\«\«\\\~A\«A
`.~
`A.
`}
`
`i
`
`-
`
`MS‘
`‘.
`\
`,
`
`:
`{RM
`
`§
`i Ei . 5 , ,
`a:
`§§
`m»
`*E A
`g,
`ii“
`
`
`
`.
`
`“
`
`W
`
`i n
`‘\
`‘
`‘5 m5.
`NWwiwfiwwmww
`,
`1
`“r I];A7.ta"
`Zane-'1
`.,/$7
`22’}
`yr"
`
`
`{}§S§‘§,§Y
`
`g
`h
`\~\~.\\\\\\\\s\\\\ “\‘w‘w‘x‘
`fir
`
`,....,,.,.7,,,,,,..,
`
`\
`
`-
`
`i
`
`\‘x‘
`i
`
`S‘s‘étiifi,
`$3§€ES§§§§§
`‘x ‘-
`§
`(
`Mska‘vw‘x
`{w
`.ngw.“
`“M‘W;
`_
`firmwsis
`_
`V
`‘
`fl
`‘
`“I
`wmagmssxsm‘
`WW» Mumsi
`.
`:fififis‘fii
`,
`3;
`mmwmmmmms
`
`,«I-““\\\\
`
`“K
`
`\\
`\.
`
`‘}
`‘
`n r\
`mé
`
`, iE
`
`a,
`
`\\\\'~\V~n\\\\\\\\\m
`.
`
`‘
`
`g
`
`.
`
`‘ ~
`
`I
`
`v
`H»
`i
`.\\mm\\-~\n\\~l~\\\\\\\\»\\¢\\“\\\\\\\\«~\s~«smM5“
`.\‘
`.v'
`.,
`\“ ,.-
`,.
`9%
`
`s§§s§§m§¥
`
`k3
`
`‘
`\
`91‘.“
`\
`g mmmm }\
`/ ~
`.
`1
`L“uwmmm «WWW
`’If
`,2.
`K A.
`“W‘kw‘ .Mum»,
`
`-
`
`.
`
`\§
`I;
`
`My.»
`“WM
`
`Y WW,
`V
`'-
`\“
`.
`.
`\
`‘i
`,
`s x,
`is mm mm.
`‘
`g
`\~s\~\‘s\s\~a\~\\sw~\m\wmvuwé
`
`«--~\»-«\\~\»\-\\~vpmw~§
`,,,
`2.}
`
`m l
`M. :1:
`g3
`i
`
`
`
`'
`
`‘
`S
`§
`
`\smsswsskusws
`«3: 7
`.4.d4;;.7
`
`if
`mm:
`
`I.",4",m,,,,”””””””u¢
`
`\\“\v~\\v«\~w\\~wu
`
`,,,,,,,,,M,Z,.,,,,,my.
`
`4V
`
`{
`\
`3‘
`
`{,
`
`.~
`
`,\
`.
`fig}
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 3 of5
`
`US 9,253,239 B2
`
`NAVIGATION
`
`Evans
`
`m
`
`80
`
`FIG. 5
`
`82
`DETERMINE I
`
`
`VIEWABLE PARCELS
`
`Fox UPuAIE
`
`
`
`
`
`
`
`ISSUE PRIORITY
`
`REQUESTS
`
`
`REQUEST PARCEL
`DOWNLOADS
`
`
`88
`
`90
`
`
`
`SIORE PARCEL To
`QUADTREE NUDE
`
`
`92
`
`EXAMINE
`
`QUADTREES
`
`
`
`
`.
`
`n
`
`.__‘.-
`
`
` TRIM
`OUADTREE Nooss
`a
`
`94
`
`NETWORK
`
`
`
`
`REQUEST
`
`WAITING?
`
`
`102 FIG. 6
`
`
`
`WAIT FOR
`
`
`REQUEST IHREAD
`
`FREE
`
`
`PRIORITY REQUEST
`
`
`WAITING
`
`
`SELECI HIGHEST
`
`100 j
`
`106
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 4 of 5
`
`US 9,253,239 B2
`
`“M.Sc“
`
`\N\.(i.
`
`‘5‘i..z\“3“x.a“i},“A,\h.L“axw,»,.“uN:‘.“i?.8.3.;u“>3i.“D.m\R«aior“»A:ii“«\\»t!_i“¢\\5Ru,z}x«t!Nx‘MN)“uhV,»\\“W,nxv\\».3“mm{RmmmSmmm“9&3\wW“(R\3,“mi,iii:Vises:
`
`\x‘xgx8533\u.gMRh»m.vmS\\»mJ.a..5sxiit~“V\Nmiii“.§wv}.nm,xm«um«mnu«s.we»‘w.wi“a.N““aaninm3,3m.»“,§§“ix.in».w\.:\x83\~‘3.x“\\\\\‘(kxKl.:u~a»!w:.‘x,{zin?“an,\a»i,mAé,.33$xxx.wK.:.z»}$inin~.3.ix‘.x.3»“K.bi»“N.”“\v.ue.\e\\ean.,“\:Ln,
`
`,.Esazaassasianm..m“m“*w_.i,i\“ii.i“““““mNvvii\u\““N,.mmMin\«mmwhy“t:\.\k\k\3‘33“$§§§§x§§§$33!»:$3xxx\xx:53:=§5§§§k.\
`\f»‘«ax‘3»éx.».£.Ave...Sw3fix3Ei,xisvi4...«3,nx.\x,gi\i\x.3\\S\\\fink
`:3$33.33$33.353§\éxkakkkxi‘xxx‘ki
`QX
`
`figi,
`
`\xv.m.wi.ii§3§§§§x§$§§5*!>§x...
`
`um,“Wm,.F3man“new“.iw“ummWVa.Nu»ii4‘sgmmxiwm“re9:3“mA!“mNe}we»wiNi336*fi§‘3\\‘\‘\\r‘\§\\\E3“
`
`6,5.mamisiiifiwm3...Wmthgx?§§§§va.msaw«aEwas:.ln\81v‘y.mix.i,mmumax.Nnomm»mi_,m“K,..
`
`
`x3wM““§.
`
`
`“w.
`.,wx:““H.wski,a.
`
`i..\\“Sma».xm,..
`Ash3m‘3‘,N:{xiii
`..3vas“.9:.
`
`Saw.mr\..$&
`
`m
`
`4.3.mEiv\\.ii.R.“\x,
`M3.»mV!.nC\$3..«I~3,\k.i\““.3«be
`
`‘»WM““mu
`.32\iti“wmr:\v\{\“V5
`..x.“mi,WM,
`
`ESE
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`
`

`

`U.S. Patent
`
`Feb.2,2016
`
`Sheet50f5
`
`B9
`
`\3.
`{xx33
`
`uuu~u‘umm‘w‘ww»\\un\5\v«\u
`
`‘Q
`
`nfi
`amas...
`
`“xm\5m
`
`
`
`PSE§$§$$§3333:3..\...........‘..53131;:Ni...$§Et.$>:3§23533
`
`m%vm.
`An~‘\\“hms45‘».\»mmmxf““ml\x0..““wmwxnmw\\.+WminNu.“mF.33§%:§EK{S.83mw33.mmNM..
`a‘..kfiwGNK
`
`fi
`
`‘xrx.
`
`§s~§§\xksxixiixixxkixgxiégi
`
`
`Ad
`
`3u\\\v2Em"
`\:9SS;L3whyan?_v4:.nun.
`0‘anNgu9\1.\V0/3»\\“mmxi
`“8ul\‘V
`{\wwe“.wm\fi&W\
`.it..
`
`
`é
`YMMMMMMWWE
`23w
`
`x?
`
`E §
`
`Eas:$13
`
`«&w
`
`“A
`
`mw
`
`bdkmoafliCknp. ExhflfithOZ
`
`\wi\-sv~ss~vw«~«~\s~wvn~n
`
`Microsoft Corp. Exhibit 1002
`
`
`
`
`
`
`

`

`US 9,253,239 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`This application is a continuation of and claims priority 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
`claims priority under 35 USC 120 to US. paten application
`Ser. No. 12/619,643 filed on Nov. 16, 2009, now US. Pat. No.
`7,908,343 which in turn is a continuation of and claims pri-
`ority under 35 USC 120 to US. 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 US. Pat. No. 7,644,
`131) which in turn claims the benefit under 35 USC 1 19(e) of
`US. 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, 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-
`graphic, and or other highly detailed maps. The data storage
`requirements and often proprietary nature of such images
`could be such that conventional interests may be to transfer
`the images on an as-needed basis.
`In conventional fixed-site applications, the image data may
`be transferred over a relatively high-bandwidth network to
`client computer systems that in turn, may render the image.
`Client systems may typically implement a local image navi-
`gation system to provide zoom and or pan firnctions based on
`user interaction. As well recognized problem with such con-
`ventional systems could be that full resolution image presen-
`tation may be subject to the inherent transfer latency of the
`network. Different conventional systems have been proposed
`to reduce the latency affect by transmitting the image in
`highly compressed formats that support progressive resolu-
`tion build-up of the image within the current client field of
`view. Using a transform compressed image transfer function
`increases the field of the image that can be transferred over a
`fixed bandwidth network in unit time. Progressive image
`resolution transmission, typically using a differential resolu-
`tion method, permits an approximate image to be quickly
`presented with image details being continuously added over
`time.
`
`Tzou, in US. Pat. No. 4,698,689, describes a two-dimen-
`sional data transform system that supports transmission of
`differential coefficients to represent an image. Subsequent
`transmitted coefficient sets are progressively accumulated
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`
`
`with prior transmitted sets to provide a succeedingly refined
`image. The inverse-transform function perfomred 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 a1., L .8.
`Pat. No. 6,182,114, overcomes some of the foregoing prob-
`lems. TheYap et a1. 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. The
`encoded transform coefficient data sets are, therefore, of con-
`stant size, which supports a modest improvement in the algo-
`rithmic performance of the inverse transform operation
`required on the client.
`Yap et al. adds utilization of client image panning or other
`image pointing input information to support a foveation-
`based operator to influence the retrieval order of the subdi-
`vided image blocks. This two-dimensional navigation infor-
`mation is used to identify a foveal region that is presumed to
`be the gaze point of a client system user. The foveation opera-
`tor defines the corresponding image block as the center point
`of an ordered retrieval of coefficient sets representing a vari-
`able resolution image. The gaze point image block represents
`the area of highest image resolution, with resolution reduc-
`tion as a function of distance from the gaze point determined
`by the foveation operator. This technique thus progressively
`builds image resolution at the gaze point and succeedingly
`outward based on a relatively compute intensive function.
`Shifts in the gaze point can be responded to with relative
`speed by preferentially retrieving coefficient sets at and near
`the ner 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 visualization would clearly be
`beneficial. Conventional approaches effectively presume that
`client systems have an excess of computing performance,
`memory and storage. Small clients, however, typically have
`restricted performance processors with possibly no dedicated
`floating-point support, little general purpose memory, and
`extremely limited persistent storage capabilities, particularly
`relative to common image sizes. A mobile computing device
`such as mobile phone, smart phone, 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 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`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 teclmological constraints dictated by the use of a low
`Jandwidth data chamiel or indirect constraints imposed on
`‘elatively high-bandwidth channels by high concurrent user
`loads. Cellular connected PDAs and webphones are examples
`of small clients that are frequently constrained by limited
`3andwidth 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
`3rovide 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 efficiently 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 channels for display on a client device by selecting an
`update image parcel relative to an operator controlled image
`viewpoint to display via the client device. A request is pre-
`pared for the update image parcel and associated with a
`request queue for subsequent issuance over a communica-
`tions channel. The update image parcel is received from the
`communications channel and displayed as a discrete portion
`of the predetermined image. The update image parcel opti-
`mally has a fixed pixel array size, is received in a single and or
`plurality of network data packets, and 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 further advantage of the present invention is that the
`client software system requires relatively minimal client pro-
`cessing power and storage capacity. Compute intensive
`ntunerical 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 in 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;
`
`v.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`

`

`US 9,253,239 B2
`
`5
`
`6
`
`FIG. 5 is a process flow diagram showing a main 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 2low 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 cmmected
`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 2 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,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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. l -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. T