`
`(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-40a: 5”“ 3’2‘
`. ”Mag
`3i {filii’fififiia
`
`\\ “meg,
`
`§¥§r~§§$§§3§§§
`Magma“ 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 Warneretal,
`,,,,,,,,,,,,,,,,, 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 Castellietal.
`................ 345/420
`2/2002 Li etal.
`6,345,279 31 *
`.................... 345/419
`2/2002 Chanetal.
`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 etal.
`......................... 382/173
`6,650,998 31
`11/2003 Rutledge etal.
`............ 345/581
`6,704,024 32*
`3/2004 Robothametal.
`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 Silverstein etal.
`........... 382/282
`6,882,755 32*
`.. 382/166
`6,898,311 32*
`5/2005 Whitehead ......
`.
`
`6,970,604 31* 11/2005 Chai
`...........
`382/240
`7,908,343 32*
`3/2011 Levanon et a1.
`709/217
`
`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
`
`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, N0. 2. Apr. 1992 (all pages).
`Lance Williams, Pyramidal Parametrics, Computer Graphics, v01.
`17, N0. 3, Jul. 1983, (all pages).
`OpenGL Smndard Version 1.1, Mar. 1997, available: https://www.
`0peng1.0rg/documentation/spec s/Versionl .1/glspec1.1/n0de84.
`html#SECTION00681100000000000000 , (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/0peng11.2.1.pdf
`,
`(all
`pages).
`George H. Forman and John Zahorjan. “The challenges ofmobile
`computing,” Computer v01. 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, N0. 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).
`Numberng 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
`
`$I§w§ ‘Qmmww‘
`an!“
`«.3
`\
`\y‘
`”H;
`‘9
`
`\
`
`.I
`9‘
`«"3”
`X
`¢~Mfism\\.w¥
`w»
`w“
`
`°1v>
`{.x‘
`
`9'6
`a"
`
`““6.“
`o M‘
`
`\x mm“ «NW
`
`
`..
`.
`g
`§ :
`\-
`§
`
`:2
`3
`E
`
`v
`
`:
`\
`3
`3
`
`§
`
`ri’mmmumufl
`
`’11
`L\s\\\\\i“
`\\u\\\~\-\\\”.4:~14”
`izmtmmx
`i m
`3 M’
`
`\m‘“\m‘\.«
`3
`i
`
`m
`NN
`
`f“.m.w..._....
`
`‘\ c N‘; 3X3;
`mififiim § a;
`
`3““ Sis
`"‘
`
`SH.
`
`.
`
`mama i
`k“...«u.mmm..m$
`
`‘
`
`-\
`
`
`f,aw,wa”’wwl
`'~»»WWMz/zrm%
`
`'9
`
`i
`
`I
`mmzkau 23m
`
`A,
`
`’s.
`
`Q A
`,a“ ‘3 at":
`{Mfg“““““““~Mg
`‘ ~
`u.
`\
`§
`Ré‘i‘z‘éfifik‘
`g
`§ Sim g
`i
`W
`\ ..
`‘.
`E
`*i‘
`{mm mm
`W
`
`‘
`
`\..w“..w_;§\
`§§N§§§
`
`\\‘\\\\\W-\\v~\\\\\~\¢erllwlzg'
`
`/
`
`4:2
`
`ii iii E
`
`Microsoft Corp. Exhibit 1002
`
`Microsoft Corp. Exhibit 1002
`
`
`
`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 2 of 5
`
`US 9,253,239 B2
`
`2E
`
`‘
`
`E
`.
`nx\\\n-\\-u\1vv.\\\\n\“\\\\\\‘\2
`EEEEEE EEEEEE
`\
`EEEE EEEEE- Ex
`E \\\\\\\M\\M§\v\\\~mvfi\v§
`n-
`\-E\\E\~\»~\w§\\wNEW“?
`EEEEEE EEEEE
`
`E E
`
`““w.
`
`,....”.u7,..,....,
`
`EEEEEEEEEEE
`
`ium
`\Av»\~s\v«‘\
`§
`M\Wk
`5
`
`“ gfikmm.“ _
`
`.Er‘:
`‘" N‘EL
`“u-m\\\-IWAKEM
`anEMF: :9;
`.1"
`SE43
`\\
`”5‘
`EEEE'E‘E‘EE‘I‘
`‘EE
`S???
`:22:
`
`71mm?“-
`§\~\\\\\\\\\\\m§1\smmn\\n$
`
`\Q
`.
`3‘
`ES
`EN“:
`_
`i
`R" u!"
`v“
`i
`3\
`E3“
`
`i
`
` 33m “awn”?
`
`.
`
`E.
`
`“mm“?
`
`
`
`vl
`\3 3
`5: .\
`“M“gE.“
`ENE“ EEK:
`‘EEEEEE EEEEEEE ‘
`“W” SEESEVE‘SENECSSE‘E‘S‘E
`
`\
`
`iu
`E
`
`WWW
`
`ESEEEEEE.
`«svwviwnmx“mmwmw.
`u».-
`
`35
`ESE EE
`
`E:
`
`vaw.\\\\\
`
`\\
`
`-\.-\
`.-‘“ 5Q}
`___...\\.N‘E¢\EN““WW
`
`\swwswss“smss\m
`
` I.”,4”,”4”,”,nunnuux
`r/r/rzxy/””IZ””M”r”,u4V““uuuvnwu‘»m
`
`f\
`
`a: E
`t\
`. {E
`
`3
`
`W u
`
`mr/I/d/flu/r
`
`WWIWW’W
`
`.~SEEEZEE}
`
`SS?;%S$\T§.
`
`
`
`Microsoft Corp. Exhibit 1002
`
`\\\\\\\\\\\\\\\\\u\&w\v‘
`
`E E
`
`
`
`2:?1:1"
`
`”(1,111”I
`E‘EE“EEEE‘ EEEEE E‘EE‘EEE
`“mm“m.\EH‘E.“ ME“mm
`3
`.
`.E
`\
`K ‘
`\\\\\\\\\‘W\‘VV‘V\
`\Wv»
`E
`
`E2
`
`E E
`
`E
`
`E‘EEEEE E}
`RN
`
`ENE
`
`:i‘\}-§i
`
`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 Palonmr
`
`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
`
`SELECI HIGHEST
`
`
`
`REQUEST IHREAD
`FREE
`
`PRIORITY REQUEST
`
`
`WAITING
`
`
`
`
`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§-»~\V\\\M\v\
`
`WWW3§§8§§WW
`
`WW»
`
`x»:
`
`.,.,M
`
`as.»
`
`Rik T?”
`
`Ax.
`
`“WM-“MM““MM
`
`
`
`
`«5....\\\\\\\\\\W\\%W\\\\W\§\¥W§“v\\W.W.xW..\..\\W\\\\\\\\\\\%i\\\\.:bAw}<\\\i\m.\\\\\\\\».s5~§§ss§s§sx§§s§k
`WW,WSWWW.W»WA.".v.MWW.WWWM“WWMWMm».
`
`is:kmEMMRMMuWn:mMkm«aWor
`
`
`.WWWWWWWVM“\X.my“.v<.3W"?3%in
`
`inMN.mMmi»2_.\M:Wa»MWmm,{WWWr.W.W“WV,WWanmMn.»mMWWW{wWWQRn?W
`33W4...43mMW\,g\‘\\ix\S\\W..W52.23332.W.{km.“Sx\.w.W3.WW.WN:M{WEaM“S.L:mV«WM241.WSW.3MM“w\n\{gk\m331‘3.}w.333nW“.\{AW:51V!nW..u\\xx.
`
`.L\V.3xwWW!{xv:wanMUM.‘W\.»wW“WVMWWWWW
`
` WMWWWWWW.WM“H.wRWM\3.Mm“MWW“D:M.WW.~1;‘«c»mi.Y:mmmmww.Nno“M.mWSW9“,r:“MW;MaxW.«8,,W2“.WW(umW.MV0...
`
`
`...43”“wk{WWWWWSmaWMMu:RRwitszsa53.3vammWea:MWWWw»RN“3?43WWonM\G:MWY“M..Mk0WWManSowM.32(zW{Wst“VWMR»W$33m...\WWWWW.nWcvxmM{WWQM\SA{WW\Mit\W3‘W\WWnu».\xkAx\xMM1,1mNa}NY.“MWWW“SEWWWSSWWSWWWN
`“3.33!3WWWWWWWWWWWWWWWW
`
`WEE
`
`.W..WWW.W,WW.M“\a»«WMoo\»W.
`9M.33Many“.9:.
`
`n3:.M:W§WWWW§W§WW$WM~W
`
`
`Saw.mr\..$&
`
`4.3»m{KW.WWW.WW.R«A.3..\3WWW“wmNW“3;\v\{\“Vi\
`
`«\ex«as..\x\3%ixW”.3a»
`
`M
`
`W.W.W3“
`
`
`
`igsgoosg;§9§998\
`
`W.Mn3.m.§\}W\§\}W\\\\W\a\§\§§
`swxWM3.
`
`WWR“.$WWfix3WWW.
`
`X
`
`Microsoft Corp. Exhi
`
`it 1002
`
`M{txWE‘x\\\\\\\\W\W\\\\\\\\W\\\\\\\\\\\\\§W§x~§§§»\\\\‘\xx\\x‘\§\\\§\\\\\\\\\\\§\\\.\
`WWW!\WW\\\\)§2\\WW>W\\\\\s~\\§\s\\\\\\W\\\\»\~\W\\\\x\\\x\\\\W
`
`MMMMMNMM-Mm
`
`\\\V~\\\\\\\\\\\\\\\X\V¢\\\'\X\\\\\\\\\
`
`Microsoft Corp. Exhibit 1002
`
`
`
`
`
`U.S. Patent
`
`Feb. 2, 2016
`
`Sheet 5 of 5
`
`US 9,253,239 B2
`
`‘u‘A\u\\\v~\m\\\nu~“v‘
`
`‘32,,
`
`«9%
`
`uuu~u‘umm‘w‘ww»\\un\5\v«\u
`
`\3.
`{xx33
`
`uman
`“SuI\u
` c::L“s,xuuu“u“
`
`.i:
`
`
`
`Q:
`Ewmmw‘mm:
`2>3 3?
`
`{:i
`
`E §
`
`ti
`
`
`mm"
`
`)1\§\e.Ahwyam»
`
`.ix\xx\PxxnVo‘
`xx}.\\N¢
`
`at}\E...
`..{1.
`
`Microsoft Corp. Exhi
`
`it 1002
`
`\wi\-sv~ss~vw«~«~\s~wvn~n
`
`0mmw
`
`“A
`
`mm
`
`:e.$§\$§$§é§$§§§§§i§§i§§§§§..aéixtiixzziiiiw
`
`nun
`
`“fir
`
`.wk»
`
`Nu...
`
`“xm\5m
`
`
`
` \\\.\\§\§\S€=\§y§2.“us
`
`\\m\\\wx-\V<\M\x\m\\
`\
`‘x. -§
`
`.......x
`
`Ad
`
`33.:
`
`§s~§§\xksxixiixixxkixgxiégi
`
`
`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
`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, 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 U.S. Pat. No. 4,698,689, describes a two-dimen-
`sional data transform system that supports transmission of
`differential coefficients to represent an image. Subsequent
`transmitted coefficient sets are progressively accumulated
`
`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 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.
`Animage visualization system proposed byYap et a1.,L..S
`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 011 a relatively compute intensive function.
`Shifts in the gaze point can be responded to with relative
`speed by preferentially retrieving coefficient sets at and near
`the new foveal region.
`Significant problems remain in permitting the convenient
`and effective use of complex images by many different types
`of client systems, even with the improvements provided by
`the various conventional systems. In particular, the imple-
`mentation of conventional image visualization systems is
`generally unworkable for smaller, often dedicated or embed-
`ded, clients where use 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