(12) Unlted States Patent
`(10) Patent No.:
`US 8,924,506 B2
`
`Levanon et al.
`(45) Date of Patent:
`*Dec. 30, 2014
`
`USOO8924506B2
`
`(54) OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(75)
`
`Inventors:
`
`Isaac Levanona Raananaa IL (US);
`Yonatan Lavi, Roanana, IL (US)
`
`(73) Assignee: Bradium Technologies LLC, Suffem,
`NY (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`3:116. 1155:331:36:6O;dig/Eyed under 35
`This patent is subject to a terminal dis-
`Clalmer'
`(21) A 1 NO. 13/027 929
`pp .
`N
`’
`Filed:
`Feb- 15, 2011
`
`(22)
`
`(52) US. Cl.
`CPC .......... .. G06F 3/1454 (2013.01); G06T 3/4092
`(2013.01); G09G 2340/02 (2013.01); G09G
`2350/00 (2013.01)
`USPC ......... .. 709/217; 709/203; 345/625; 382/232;
`382/305
`
`(56)
`
`(58) Field of Classification Search
`CPC
`G06T 3/4092; G09G 2340/02; G06F 3/ 14
`USPC ............... .. 709/202, 203, 217, 230, 246, 247;
`345/625; 382/232, 305
`See application file for complete search history.
`References Cited
`U'S' PATENT DOCUMENTS
`5,929,860 A
`7/1999 Hoppe
`6,182,114 B1
`1/2001 Yap et al.
`(Continued)
`OTHER PUBLICATIONS
`
`(65)
`
`Prior Publication Data
`
`US 2011/0175914 A1
`
`Jul. 21, 2011
`
`Hoppe, H. “Progressive Meshes”, SIGGRAPH ’96: Proceedings of
`the 23rd annual conference on Computer graphics and interactive
`techniques, 1996, PP 99-103
`
`Related US Application Data
`(63) Continuation-in-part of application No. 12/619,643,
`filed on Nov. 16, 2009, now Pat. No. 7,908,343, Wthh
`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 488 filed on Dec.
`27 2000
`revisional a
`licafion’ NO’ 60/258 489
`filéd on be: 27 2000 pliovisional a '
`lication’ NO’
`60/258 465 'fileé on 1320
`27
`2008p revisionai
`applica’tion’No 60/258 468' filea on D’ecp 27 2000
`provisional application ’NO ’60/258 466 filed 611 Dec?
`27 2000
`revisional a
`licafion’ NO’ 60/258 467
`filéd on D’ecp 27 2000
`'
`’
`pp
`’
`'
`’
`
`'
`
`(51)
`
`Int. Cl.
`G06F 15/16
`G06F 3/14
`G06T 3/40
`
`(2006.01)
`(200601)
`(2006.01)
`
`y
`
`S. Weiser, Es .;
`q
`
`Primary Examiner 7 David Lazaro
`74 Attorn , A 6111, or FirmiAnatol
`£03116, LaweyGrmi,a RC
`(57)
`ABSTRACT
`Large-scale images are retrieved 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
`lurali
`of network data
`ackets, and were the fixed ixel
`P
`P
`ty
`P
`array may be constrained to a resolution less than or equal to
`the resolution of the client device display.
`21 Claims, 5 Drawing Sheets
`
`fimfléfi “‘ ‘
`13m.
`
`
`
`exefimssm
`magma 91:;
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

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

`

`US. Patent
`
`Dec. 30, 2014
`
`Sheet 1 of5
`
`US 8,924,506 B2
`
`‘ ‘\.‘m\\,.
`e
`rfigfiw vfiiflmwwmm}
`S
`
`{\\\‘\
`
`13?";
`
`~
`w \ v‘
`.Q m
`N‘i‘ls- My
`
`‘
`
`fl
`Mp
`
`n
`..o"‘
`
`~
`
`,mmx‘m“
`s wwmm }
`s;
`\E
`‘3
`M
`ii
`9:
`:\\Nww~Ҥ
`mmx
`.
`sswmmm
`\
`.\ \\« \\<
`$§\\\\\\\i§l§\\\
`{k M-Mrm §
`R M-M-M .
`\A
`‘
`R u‘w\-\~\
`\
`{\M'nswim-‘9
`\\\\\\\\\\\\\-“
`3
`x
`.
`t"
`i
`‘>:‘\
`3
`
`§
`§
`\
`§
`§
`§
`‘
`x
`§
`$
`§
`3
`§
`
`§
`k
`
`1mm \m
`\
`§
`\
`§
`K‘
`\
`3
`s
`§
`%
`§
`g
`V M
`§
`
`w
`
`\
`\
`Q
`\
`g.
`\\
`\\
`§ \
`is
`‘
`§§
`§
`
`
`
`
`.W
`
`\
`
`x. ‘
`.
`W8
`
`“‘x»
`\\‘
`
`.
`
`V
`
`F
`.
`
`‘ “
`I'
`
`n“
`\\\\\\h\w~:~°“‘
`
`\\
`
`§
`
`~
`53‘ x
`
`is;
`i
`
`x.
`
`-"
`
`* _.
`§ \-
`‘1‘} M.
`
`\
`§
`\
`
`w-w‘
`
`.
`
`f;
`
`.
`
`'.
`
`_
`
`‘
`
`w“
`w
`\\v.\\ ‘
`€*
`k g
`5
`‘
`§§s§
`3
`
`\\
`\\\
`
`3
`3
`k;
`\~x-“~“§v§:
`W;
`
`‘
`\.-“\
`
`
`
`i’Ic51
`
`;g13
`
`rMWMM/xmta
`
`6'”
`
`
`
`Microsoft Corp. Exhibit 1013
`
`R\\\\\\\\\\\\\\\\\\\\\\\\~\
`‘
`'u\
`< “ .
`.
`\-
`-V
`mmsmi
`Y
`I
`figkg
`3% \P.
`.3}.
`Li. fi‘e 3:331:33 k
`§N‘www“wm~w$
`M
`mow“ “x
`m
`v7“
`_h
`5*
`-.
`“MM-"MM ~.-.M; \\\~,,.
`33..
`.
`
`w WN
`V
`-\ NM ‘
`«M»
`.
`‘ ‘0‘
`\‘ .«~“
`‘
`\..w-I-‘“
`~
`
`
`
`N,“
`
`NM
`Q
`
`{
`
`_
`
`
`~\
`
`\
`\
`_
`\
`3
`§ §
`i
`-~
`§
`3
`9“.
`\
`s
`s
`t:
`.3-
`‘
`‘x
`3
`
`A ‘
`‘ A
`e‘
`3 g:
`..o~
`
`‘~“\~~«~\\s§-»x»“\»~»~w\ ‘
`
`\
`§
`.
`-\-
`§
`~~~
`~
`g
`g“ MSSR g
`\
`
`\.~ ~
`~
`“.
`‘
`\§‘Q§}.§
`3
`“ “ ~
`“ ’
`‘
`‘ ‘\\\\\\ \ \\ §>
`k
`z
`\
`»
`\)
`3
`.
`: msmx
`S
`\*< Q'nvc k
`'
`Am ism-2 g
`\\\\\\\\\\\\\\\\\\\\v~\\\i‘
`
`,
`\x‘
`{0"
`
`“x
`\. «Mn».
`~¢x~m‘ \ w“ ‘
`V
`.\.
`*\‘\“\\-\\W\m~x
`A\~\‘\\\"“~ $§\\\\
`.\§\k\\
`‘0'}. 1 ‘N ‘ N
`n“
`N
`“.9
`\\ MNle
`‘6‘»
`. «N‘
`\\\\ “meow
`‘
`-
`~‘
`§
`-\:i'\'\"\'
`x
`0 mm“
`--~‘ *‘
`v M\
`z mm\ «
`
`
`x»
`
`éfimu i3§§x
`
`i
`f“
`
`x‘
`3
`\
`§
`\
`\
`3
`s
`§
`S
`*
`z
`5‘
`~‘v‘
`‘ w.»
`“‘Nx §"
`
`/,,,,,,,W,,M,,W,/
`
`.
`¢v~¢~
`\
`. \
`WW\
`‘Q. w“‘#\~§:\\ \\
`
`N.»-
`
`gI;A,'w mfir}
`
`4 -4(
`
`Microsoft Corp. Exhibit 1013
`
`

`

`US. Patent
`
`Dec. 30, 2014
`
`Sheet 2 of5
`
`US 8,924,506 B2
`
`§xxx\\\\\\\\\\\\\\v~\\\¥\\\\\\\i\
`§
`.
`‘
`s
`'N “M:
`\
`‘ u .h ‘
`\
`3mm Ex
`\\\\\\\“\\w~§~w\~~v~~s~\\s~’
`’i
`§
`
`.i V
`q ¢
`
`i .
`~
`N .N...
`xvii “em
`\‘ -\: -_-§---.\
`w
`$ Miami:
`
`i
`
`V:
`
`R \K\\\\v\
`5
`
`\
`\
`
`\
`\
`§
`
`S *3
`
`“w
`
`\hxm. ~\._‘v
`N. \x:
`w \
`~ «‘5.
`imimu
`
`s
`§
`\
`3‘
`s
`§
`‘
`summng¢ KR§S§§‘§¥
`\
`\
`3
`
`.3 "‘5‘
`.
`{
`‘3.- qi £1.
`“mm..mm\w«\
`\
`S
`‘
`i
`M av» % 5‘“
`3
`.6.
`km?»
`“Unfit”; '\- \“~~\5
`gmmmi
`§ “
`‘9
`\
`\
`§ mum n}\\z\“\§.;\3 ‘
`Si.“w...wi§fWWMNJ
`g
`s
`~< “ > v -
`§§ Ykii3§§§
`f;
`.x _
`\
`" =§ R§Q$§§i
`\ \
`. :
`x;
`§
`$\ 3 . 3i w
`f\§w3~;:§:;‘m\§
`
`§
`k
`
`.
`
`“
`
`
`
`~ _ s
`{:r‘x
`3’ -\
`
`\\“\~s-~ss~
`
`§
`§
`...m~m“$..mm~\m“
`w .h
`,
`mm: Rama»;
`-
`\_.\<
`\
`ii
`v.
`'.g
`??‘\*i-
`m\w\\\~\\\\\m\~v~m~m\x\x\x~r3
`
`2
`
`‘
`
`gs}
`
`i
`
`“ w . m u i
`Mfl xs‘m‘fi i§s§§s§< Es}
`
`
`
`A A
`A; {.3
`
`"N
`
`m m
`$23
`°
`
`~‘
`
`
`“mmmgwm“mm. ‘
`\
`i
`§
`3
`\
`x
`\
`\
`_
`§
`§
`§ mu -\
`R
`‘
`\~\~\.‘.‘\-
`\
`§---~m--~m§~§
`§
`§
`\\\\-.l.
`.
`5
`5
`\
`\
`S
`$
`t:
`§
`S
`S
`
`‘
`
`m».
`{8.2.-
`b
`\
`\x .. \ \-
`»
`i’fifiiii’fi‘ii‘k‘
`
`~
`g
`k
`‘
`
`i
`*~
`s
`\
`§
`a
`i
`:
`\
`§
`\
`3
`i
`$
`
`§
`‘
`k
`§
`WWW“Mgwwwmm“
`‘\
`\
`\
`.
`-
`\t
`.
`‘v
`_
`_
`“W. i
`is m, mm g x“ M ‘\
`immmmwwiwMM“
`23%;;
`
`.
`.~‘
`5 n »
`‘\
`3} G
`
`w~w.\.“\\
`\\\
`
`\
`\
`\
`3
`\
`
`
`
`‘
`.
`\x‘t“ ;\\u \"\ v 3 . .v .
`Sufi“ ssssni § m
`
`.
`
`2
`
`E
`\
`
`I
`
`"-
`
`\
`\
`‘
`
`
`.
`\
`\ x x \x: \ x
`_ \
`\
`_‘
`\
`‘
`\\
`» ~
`~
`
`g haw; 53§§§
`‘\
`As
`«Mm
`\\\
`N\\waw“
`
` \
`
`.‘o’
`°'
`
`<
`-\
`My
`\° \
`
`'w}
`
`figi 9::
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`US. Patent
`
`Dec. 30, 2014
`
`Sheet 3 of5
`
`US 8,924,506 B2
`
`82
`DETERMINE I
`
`
`VIEWABLE PAREEIs
`FOR UPDATE
`
`
`"memo"
`EVENTS
`
`EXAMINE
`OUADTREES
`
`
`
`
`86
`
`
`
`DOWNLOADS
`
` TRIM
`
`u.I'v n
`QUADTREE NOOE
`
`FIG . 5
`
`84
`
`ISSUE PRIORmr
`
`REDUESIS
`
`REQUEST PARCEL
`
`. . v
`
`o
`
`-
`
`NEIWORK
`
`88
`
`DOADTREE NOOEs
`
`-" "
`94
`
`SIORE PARCEL TO
`
`
`
`
`SEIECI HIGHEST
`REQUESI THREAD
`PRIORITY REOOESI
`
`
`FREE
`WAITING
`
`
`
`
`
`
`Wm FOR
`
`100 j
`
`105
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`U.S. Patent
`
`Sheet 4 of 5
`
`\.t!a.\x}.
`3..“
`
`
`“suavfixemm.\.\rxn..\“x“\3w“.5?~NMa9“.{Us““x“\Exn“xx}5K“m\.{xxkxxtxkxxxxxxxxxxxn.\>3\.....xE»R.\»cwx«a}“KT“ix.V‘x“K”“\e,“x:n».Rx“‘xm.3xx:.an‘‘..5miaxe‘“\.‘iYx.\xi{>3V‘“i9»x}\3.3.m«“{5‘“xx35m“.u3.‘vmkmm‘9.«RmatSK9mDmmmmmifixxsxssxxxxiw3\\\\\\\\\\\\\\\§§§§§oxx\xxx\\\\\\\\\\\\\\\\\>§§\{§“R\\\\\\\*\\\\x\x\\
`
`
`
`
`
`~sss~§§§§§3§x§§km\x.%wM“Mm«mx\\\x‘\\xx“v“mx““mw~x~~xx:~~~mmNvx\.xh,wp.‘
`
`Fs\sssx\xx§xkkxxxxxxxx\\\\\\\\\\\\\\\\\\§§xxxx\s\s\ssxsxxx‘~..xxs~s\\\\\\\\k‘kxxxxxixm.\xxx§xx\x\xxkx\x).\x2xtssssk5stt\\\\\\§\\\\§\\Q\\\\\\§
`
`0v‘m2N«m“é.a»;xv:w:\{K\v}.\an“3\x\~3‘\\Ks\9\~\>3.,3‘an“x51n.»xx\~‘)\\yK.0xvxxxx\33.i.x9“a«W“xn‘\5!v:m{k“in.x.3»Q.m“Aw.9..R.“VS,«a«.“«K\&wn,is..‘.aq‘\n~‘~\3.
`
`
`
`
`
`,.wo«\\§§\3§WXxx.x}N?‘35:?“«X\{m«$3\\\w§..\\“\k)
`
`\(»
`
`o.<»VJ.»S..E..X:..a“
`
`53
`
`iii-w i?
`
`.x:\S(hS“.‘“‘3vian»MR
`
`{3NAm“t.IS..Ya“a?ma«K.hi5%mffiRR.‘KRsVx}.é«Q..finn§§x§§Wv‘‘mun“My,fix<3«‘3
`
`
`
`33%E
`
`F\MS{xx
`
`mx‘
`
`S\u\x\§3\\\\\\\§\§§§k
`
`“wfi\\\\\\-\\«\
`
`l}\4Wm“X2k
`Uwmmy.»1‘x.WEN«ximm.z
`x..m\mv?9m3g“\uw3»v.\\\\
` (4KA\..¢.8,g1as.ov»“5w“\xwe;fixs:“mm“.{8¢\\.\\§S.5\NRaw39..{Ruv{n“N.
`
`:v\§\Eé‘
`
`\§\.
`
`
`,3“:N:3A..\o‘N‘xsstsis‘sktki
`
` .{\xC\x\‘o“o.‘»\
`
`“m“\:u
`
`Microsoft Corp. Exhi
`
`it 1013
`
`Microsoft Corp. Exhibit 1013
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sheet 5 of 5
`
`~\\~\\~~\\\~\mx\s~v~v.\v~v~v~s~\vv~vs‘
`
`
`.3}\{x0{aEv.3;.1.am«8a...“9X,s.K4.\.\
`3*\»““m..abmmmSN.\.u.mUS““..as...x_......x:..or.{xv«wtax“.9.mR?u.“Mn.mit.“Mii\\an,“.mm.<2«avk.«nw...“.r:k.“...\.gS.Ru“M«a»“3\s.“no\««\I»“.3PM“NH.
`
`.2...as\\\s\\32..Kxx,...i\\.v.\\sx.V.»0/\\\\\x\\....\\$\\....89..w.
`
`
`
`.3:(t.33%?wE..A...“W.“é3.wWa“m....Q1fl“..a.»x.a.3iWVa$3..“E...S:$5u:3.x3we33..Mme\v»S....«...ex.9E....SSx.\.a“.s\e..‘Ah.»““NV.<72..\~or?“{\xu»““..SA\Ro..{3~V.w.““mm<2V».3:\\mNa...z.....~x}.“.~~~\.K.\m\.Vs}«.33\~...~339w...
`
`
`
`
`.faiS§$§z§riiéit:.§..§.i§zz....xxiz§3§§§\m.x:
`
`.3~.as....w...w...,s“.x.c;v.....n...s._w.3.»«x.W!3%.«E««R.«{oxxxxxxi“.9“.
`..~..<3\\\\“Q\\\X\\\\3§\\.\§.\\.\\\\\\\§§\§§.E§$
`
`
`.95...w...mWW3“
`
`
`is:\R\\«t,
`.,m.-\x\x\m“
`
`~m0
`
`x
`
`§\s~s\s\\xxx§\\\\\\\\\\\\\\\i\\\\\§\\\\\§\\\\\\\)§\3:“xii)...3553!;E55~525i§5§§§~§§§5§§§§§
`
`\
`
`Microsoft Corp. Exhi
`
`it 1013
`
`k$33s....kx:\KxSSS$$§Sx.z§i§§§3s§§§§§...$233?§§R§§\3§§§§§§;§§E§§S§§§§§§§§§S:§S§§§§3§53§33§w
`
`..m“\u..
`
`
`{$333.33.$.33§S§§.1.x..t:\‘\xC.:....3..xi.“auSm“.“1Qeflu.“wuw“\.Kbu§.«x:\D.S.33::amy.“22.:\“K3is:m3:32\\“R“.1.“.黓a:3v..._Q..
`$§§§€§s§E...3*.mm.w“.ux\u>A.\“m«Tm$\(AvmmMu.»ma:a:......4mx“m..mu:..01“.2.y““K..m...».,“R.wm“$“mu2“xx~\Nrt“he.“.z§§§\x“m.a.0.,“.x.“““m“»..\........“9.»wMNmmN:91»u.x\a\..xM.»vNNf§§$§t§k
`.u.s3....mmw...““..x>.»ss3~sxxsxxxxxxxxxxxxxxxxxx\\\\\\\\\\\\\\\\\\\\\\§xxxxxxssxsssssss>2§i§§<5§§\§\\\\§\i‘-\\\\\\\\\\\\\\s\{\gsgfissssssssss
`k§\\\\\\\\\\§§§\§\skkxsxx\\\\\\\\\\\\\\\\“yin\.m\x.é.....n.I....s.m.mw\»v».x\«I\\.\mua;mix....xx.““.S.nmnt:wrx\\v.e.\.Nm‘0‘“m“xvNu“(\hw\\\\>v“N.R“Mi3.333..\.\\\\\\\!§§§§S
`.«2.:\lx‘m.3....Na...SN.x.“s§§§§fic...L.“m““ax...Qs....R.s.“..3.i;v3..m““Wu“.3a?5...“ix,..wn...“wm“......«...,.\SQ5...A3.““aw....«\.\\..\‘«‘{\v2Nn..xxm“\..\xc\eS!l§§§x§§§s§§x
`...x“it\3.
`
`..
`
`.:
`
`Microsoft Corp. Exhibit 1013
`
`
`
`
`

`

`US 8,924,506 B2
`
`1
`OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`PRIORITY CLAIMS/RELATED APPLICATIONS
`
`This application is a continuation in part of and claims
`priority under 35 USC 120 to US. patent application Ser. No.
`12/619,643 filed on Nov. 16, 2009 now US. Pat. No. 7,908,
`343 which in turn in a continuation of and claims priority
`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 channels”
`(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(6) 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. The present application is also related to the co-
`pending application Ser. No. 10/035,981 entitled “System
`and Methods for Network Image Delivery with Dynamic
`Viewing Frustum Optimized for Limited Bandwidth Com-
`munication Channels, Levanon et al., filed on Dec. 24, 2001
`(now US. Pat. No. 7,139,794 issued on Nov. 21, 2006 and
`which is assigned to the Assignee of the present Application.
`
`FIELD
`
`The disclosure is related to network based, image distribu-
`tion systems and, in particular, to a system and methods for
`efiiciently 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 functions based on
`user interaction. As well recognized problem with such con-
`ventional systems could be that full resolution image presen-
`tation may be subject to the inherent transfer 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
`
`2
`
`differential coefficients to represent an image. Subsequent
`transmitted coefiicient sets are progressively accumulated
`with prior transmitted sets to provide a succeedingly refined
`image. The inverse-transform function performed 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 sub-divided into a regular array. This
`enables the inverse-transform function on the 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 coefiicient data sets as the detail level of
`the image increases. Consequently, there is an inherently
`increasing latency in resolving finer levels of detail.
`An image visualization system proposed byYap et al., US.
`Pat. No. 6,182,114, overcomes some of the foregoing prob-
`lems. TheYap et al. system also employs a progressive encod-
`ing transform to compress the image transfer stream. The
`transform also operates on a subdivided image, but the divi-
`sion is indexed to the encoding level of the transform. The
`encoded transform coefiicient 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 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/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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`US 8,924,506 B2
`
`3
`an extensive set of graphics abstraction layers to be provided
`by the client system to support the presentation of the deliv-
`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 5
`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,
`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 webphones are examples
`of small clients that are frequently constrained by limited
`bandwidth conditions. The conventionally realizable maxi-
`mum network transmission bandwidth for such small devices
`
`10
`
`15
`
`20
`
`may 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
`more than utilizing wavelet-based data compression is
`advanced as permitting effective operation at low communi-
`cations bandwidths. While reducing the amount of data that
`must be carried from the server to the client is significant, Yap
`et al. simply relies on the data packet transfer protocols to
`provide 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.
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`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
`numerical calculations are minimally required and image
`parcel data is compactly stored in efficient data structures.
`The client software system is very small and easily down-
`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 subsystem.
`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 on
`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 numerals 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;
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`US 8,924,506 B2
`
`5
`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;
`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 in a preferred embodiment of the
`present invention;
`FIG. 7 provides a process flow diagram showing a display
`image rendering thread implemented in a preferred embodi-
`ment of the present invention;
`FIG. 8 provides a process flow diagram showing the parcel
`map processing performed preliminary to the rendering of
`image data parcels in accordance with a preferred embodi-
`ment of the present invention;
`FIG. 9 provides a process flow diagram detailing the ren-
`dering and progressive prioritization of image parcel data
`download requests in accordance with a preferred embodi-
`ment of the present invention; and
`FIG. 10 provides a process flow diagram detailing the
`determination of an optimal detail level for image parcel
`presentation for a current viewing frustum in accordance with
`a preferred embodiment of the present invention.
`
`DETAILED DESCRIPTION OF ONE OR MORE
`EMBODIMENTS
`
`The preferred operational environment 10 of the present
`invention is generally shown in FIG. 1. A network server
`system 12, operating as a data store and server of image data,
`is responsive to requests received through a communications
`network, such as the Internet 14 generally and various tiers of
`internet service providers (ISPs) including a wireless connec-
`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 connected
`through a separate or plug-in local network server 22, pref-
`erably implementing a small, embedded Web server, to a fixed
`or removable storage local image repository 24. Characteris-
`tically, the client system 18, 20 displays are operated at some
`fixed resolution generally dependent on the underlying dis-
`play hardware of the client systems 18, 20.
`The image navigation capability supported by the present
`invention encompasses a viewing frustum placed within a
`three-dimensional space over the imaged displayed on the
`client 18, 20. Client user navigational inputs are supported to
`control the x, y lateral, rotational and Z height positioning of
`the viewing frustum over the image as well as the camera
`angle of incidence relative to the plane of the image. To effect
`these controls, the software implemented on the client sys-
`tems 18, 20 supports a three-dimensional transform of the
`image data provided from the server 12, 22.
`In accordance with the preferred embodiments of the
`present invention, as generally illustrated in FIG. 2, a network
`image server system 30 stores a combination of source image
`data 32 and source overlay data 34. The source image data 32
`is typically high-resolution bit-map raster map and or satellite
`imagery of geographic regions, which can be obtained from
`commercial suppliers. The overlay image data 34 is typically
`a discrete data file providing image annotation information at
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`defined coordinates relative to the source image data 32. In
`the preferred embodiments of the present invention, image
`annotations include, for example, street, building and land-
`mark names, as well as representative 2 and 3D objects,
`graphical icons, decals, line segments, and or text and or other
`characters, graphics and or other media.
`The network image server system 30 preferably pre-pro-
`cesses the source image data 32 and or source overlay data 34
`to forms preferred for storage and serving by the network
`server 12, 22. The source image data 32 is preferably pre-
`processed to obtain a series K.sub. l -N of derivative images of
`progressively lower image resolution. The source image data
`32, corresponding to the series image K.sub.0, is also subdi-
`vided into a regular array such that each resulting image
`parcel ofthe array has for example a 64 by 64 pixel resolution
`where the image data has a color or bit per pixel depth of 16
`bits, which represents a data parcel size of 8K bytes. The
`resolution of the series K.sub.l-N of derivative images is
`preferably related to that of the source image data 32 or
`predecessor image in the series by a factor of four. The array
`subdivision is likewise related by a factor of four such that
`each image parcel is of a fixed 8K byte size.
`In the preferred embodiment of the present invention, the
`image parcels are further compressed and stored by the net-
`work server 12, 22. The preferred compression algorithm
`may implements for example a fixed 4:1 compression ratio
`such that each compressed and stored image parcel has a fixed
`2K byte size. The image parcels are preferably stored in a file
`of defined configuration such that any image parcel can be
`located by specification of a K.sub.D, X, Y value, represent-
`ing the image set resolution index D and corresponding image
`array coordinate.
`the image array dimensions
`In other implementations,
`(which as 64x64 above) may be powers of two so that the
`image array can be used in texture mapping efficiently. To
`accommodate different data parcel size than the 2 KByte
`associated with 64x64 pixel parcel dimension described
`above and other communication protocol and overhead
`requirements, to accommodate transmission through other
`than a 3 KByte per second transmission channel, the present
`invention may use larger compression ratios that takes, for
`example, a 128x128 or 256x256 pixel parcel dimension and
`compresses it to meet the 3 KByte per second transmission
`channel, or other communication bandwidth used to stream
`the parcel.
`The system may also accommodate different and larger
`data parcel sizes as transmission protocols, compression ratio
`achieved and micro-architectures of the client computers
`change. For purposes above, the data content was a pixel array
`representing image data. Where the data parcel content is
`vector, text or other data that may subject to different client
`system design 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 may create 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 from one server to
`another and from the client side rendering. In the system, each
`grid is treated as a sparse data array that can be progressively
`revised to increase the resolution of the grid and thereby the
`level of detail presented by the grid.
`The source overlay data 34 is preferably pre-processed 36
`into either an open XML format, such as the Geography
`Markup Language (GML), which is an XML based encoding
`standard for geographic information developed by the
`OpenGIS Consortium (OGC; www.opengis.org), or a propri-
`etary binary representation. The XML/GML representation is
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`US 8,924,506 B2
`
`7
`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. In both cases, the source overlay data 34 is
`pre-processed to contain the annotation data preferably in a
`resolution independent form associated with a display coor-
`dinate specification relative to the source image data 32. The
`XML, GML or binary overlay data may be compressed prior
`to storage on the network server 12, 22.