US8,924,506 B2
`(10) Patent No.:
`a2) United States Patent
`Levanonet al.
`(45) Date of Patent:
`*Dec. 30, 2014
`
`
`US008924506B2
`
`(54) OPTIMIZED IMAGE DELIVERY OVER
`LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`(75)
`
`Inventors:
`
`Isaac Levanon, Raanana, IL (US);
`Yonatan Lavi, Roanana, IL (US)
`
`(73) Assignee: Bradium Technologies LLC, Suffern,
`NY (US)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`
`rec. Hsab)by86s.de under 35
`This patent is subject to a terminal dis-
`claimer.
`(21) Appl. No.: 13/027,929
`PPh’
`,
`Filed:
`Feb. 15, 2011
`
`(22)
`
`(52) U.S. CL
`CPC oe. G06F 3/1454 (2013.01); GO6T 3/4092
`(2013.01); GO9G 2340/02 (2013.01); GO9G
`2350/00 (2013.01)
`USPC on. 709/217; 709/203; 345/625; 382/232;
`382/305
`
`(58) Field of Classification Search
`CPC ..... GO6T 3/4092; GO9G 2340/02; GO6F 3/14
`USPC veces 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
`5,929,860 A
`7/1999 Hoppe
`6,182,114 Bl
`1/2001 Yapetal.
`(Continued)
`OTHER PUBLICATIONS
`
`(65)
`
`Hoppe,H. “Progressive Meshes”, SIGGRAPH ’96: Proceedings of
`Prior Publication Data
`the 23rd annual conference on Computer graphics and interactive
`techniques, 1996, pp. 99-108.
`US 2011/0175914 Al
`Jul. 21, 2011
`Primary Examiner — David Lazaro
`Related U.S. Application Data
`Coty LawGroup, Pc.
`(63) Continuation-in-part of application No. 12/619,643,
`74) Attorney, Agent, or Firm — Anatoly
`filed on Nov. 16, 2009, now Pat. No. 7,908,343, which
`(57)
`ABSTRACT
`is a continuation of application No. 10/035,987,filed
`Large-scale images are retrieved over network communica-
`on Dec. 24, 2001, now Pat. No. 7,644,131.
`tions channels for display on a client device by selecting an
`(60) Provisional application No. 60/258,488, filed on Dec.
`update imageparcel relative to an operator controlled image
`27. 2000.
`provisional a
`lication No. 60/258.489
`viewpoint to display via the client device. A request is pre-
`filed on he. 27. 2000 PPvisiomal application No.
`pared for the update image parcel and associated with a
`60/258.465 :filed on Dee
`07 5000.
`rovisional
`request queue for subsequent issuance over a communica-
`applicationNo 60/258.468. filed on Dec 27. 2000
`tions channel. The update image parcel is received from the
`provisionalapplication No. 60258.466. filed on Dec.
`communications channel and displayed as a discrete portion
`27. 2000.
`provisional a
`lication No. 60/258.467
`filed on Den 27. 2000
`PP
`, a of the predetermined image. The update image parcel opti-
`“ ,
`mally has a fixed pixel array size, is received ina single and or
`plurality of network data packets, and were the fixed pixel
`array may be constrainedto a resolution less than or equal to
`the resolution ofthe client device display.
`21 Claims, 5 Drawing Sheets
`
`y
`
`S. Weiser, Esq.;
`
`4
`
`(51)
`
`Int. Cl.
`GO6F 15/16
`GO6F 3/14
`GO6T 3/40
`
`(2006.01)
`(2006.01)
`(2006.01)
`
`NOR
`oe AS
`
`
`
`
`a
`he$
`geswenandinennnnnnnn
`\ Hepwoe
`'
`SEER
`ai
`&
`.
`aannennnnnnnannnnnsnnnnent
`Dats SE
`
`spooreenresecernthSeowsos
`
`AER
`™
`
`3
`
`Bagh
`DAA
`TORRE |
`
`enna a,
`
`
`SapFrecerg
`PancrihuseBaga
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`US 8,924,506 B2
` Page 2
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`6,212,301 Bl
`6,314,452 Bl
`6,326,965 Bl
`
`4/2001 Warneret al.
`11/2001 Dekeletal.
`12/2001 Castelli et al.
`
`6,345,279 Bl
`6,346,938 Bl
`6,397,259 Bl
`6,608,933 Bl
`6,704,024 B2
`6,711,297 Bl
`6,801,665 Bl
`
`2/2002 Li etal.
`2/2002 Chan etal.
`§/2002 Linckeetal.
`8/2003 Dowell et al.
`3/2004 Robotham etal.
`3/2004 Changetal.
`10/2004 Atsumiet al.
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 1 of 5
`
`US 8,924,506 B2
`
`QOS
`ed henry,=
`
`oa
`anna,
`ae
`
`eens
`
`:
`
`:
`y
`
`
`*, ueMifyeonerstettees
` o
`easavessvaodcecetdtttttin,
`
`nnn,
`sete,
`‘;;
`ww
`an AS
`er
`SSaS
`ppc
`3433
`avian &3
`awww wn F
`3:8
`vase
`§
`ann
`X
`oA
`i
`yas one
`
`:3yA
`
`a;
`
`cN
`
`
`
`yp
`
`oeeannnns
`hs
`
`oo
`
`HNYERNEY
`
`nowy
`
`es
`
`
`5
`:
`Ne i
`SPT
`~
`*s
`
`~
`i?f53
`
`=‘\A
`s
`ears)
`:
`wR
`referees)
`y: #
`
`, ao
`.
`s8
`St
`%
`Rall |
`8 i
`BS SES wer,
`
`ponnnenne
`Ranoarneee
`
`
`
`RAYS
`CORVERUN
`occenecnennrnnnnnnnd
`
`3B
`
`
`
`\:g
`:g:gggxgg
`
`
`3 %ede-
`reeebnnnnnny
`gg
`“
`S
`ONEF
`‘
`Crags
`F
`SAR
`
`{ Deis SRE
`
`°
`
`eeoeeceeieedeed: yg44qZzg
`
`Denetdenenedirs
`
`o x
`
`o
`eaé
`
`3 i
`
`e
`°sg
`
`“ a—
`se
`weeaoe
`peut
`.
`NO
`etl
`s ee al
`oe x
`
`on,ee
`pemeccnee
`
`
`
`‘ f
`
`¢a
`
`een
`ee~
`
`See.Paani
`PancennsdDa
`
`Microsoft Corp. Exhibit 1013
`
`j
`
` “Et
`
`PIVLLIELOAAAMARAAIAILIAIN
`
`
`YLPEELEELAOASESSADASSESEAES 3
`
`r
`
`“yy ties.
`
`taé Z
`
`SIRES
`Derek ay Mare
`OyenLay Dare
`
`38
`
`Oey = Sasee sn
`
`Se oe,
`en,
`
`oe
`Upeimee
`SE ae
`
`Microsoft Corp. Exhibit 1013
`
`

`

`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 2 of 5
`
`US 8,924,506 B2
`
`~ 8
`
`3
`
`§
`2
`
`:
`i
`eT boobs DISPEAS
`
` farae Beare;
`LEAL PARCEL
`My
`~
`Yon
`PAL3
`Daya Hae
`SANSA Sne
`|
`ponSAR
`
`feces OT gaan {
`Akeuena
`ome
`Smeg
`aorz
`snantoneen
`rem
`eonmnnndiernrnnne
`Pepin
`as
`Loner S&
`‘ PROMTY |
`wewth§Meneses
`Vinaiig FRasrin
`Rime 8
`a3 oy RSQUESY
`~
`i
`TONTROL
`33
`ANASAANASRNRAAne
`3US$8 Sa a
`May
`
`
`7 F
`
`R?
`ewke
`ak
`f
`eeeceeeneereeeruceetenreaternttt]
`
`‘
`
`veg
`
`Py
`
`
`
` aennndennnnennnny
`
`LeaneneenerIserangFOLELESSSIEIIEtA:
`
`.°— A
`
`PPPEeHOLs
`RNanalgesiaensnnnn
`
`::
`
`LY Daya CIN
`aasnnesnseesnnensennnennnnnennnnnnnd
`
`SAASRSASARIRANISRSAY
`
`PEPIIPPSISILPEPEEPPEPECLEEEEEEELED,
`
`bes
`
`ANANEARSNSN
`
`SHILEIODIIIIDIN,
`
`LPOTISPATEIIDA:
`
`“t
`MA
`
`rie,a)
`
`‘ :
`
`3}3gZ
`
`fé-f
`
`"4ANAAAS ARIA
`ag $3
`PIIIIIIDEYyw
`Nepwone DaePecan)
`:
`:
`Og
`Seswe
`NS
`
`:
`
`%
`
`‘s
`
`
`x /
`
`oog$
`
`3‘ARS“eh
`Ne
`s
`ARLES GayA
`<
`Lo
`yrARR
`
`msae~
`Sandy
`
`BiG
`
`ix
`
` - \6
`
`0
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 3 of 5
`
`US 8,924,506 B2
`
`NAVIGATION
`
`VIEWABLE PARCELS
`For UPDATE
`
`Fic. 5
`
`BA
`
`Issue PRIORITY
`REQUESTS
`
`NETworK
`
`88
`
`REQUEST PARCEL
`DOWNLOADS
`
`. . .
`
`EXAMINE
`QUADTREES
`
`
`
`86
`
`.
`
`.
`
` TRIM
`5*’. .
`
`
`QUADTREE NODES
`
`a
`94
`
`82
`DETERMINE _
`
`EVENTS
`
`
`
`
`
`
`STORE PARCEl To
`QuapTree Nove
`
`RECEIVE PARCEL
`
`90
`
`REQUEST THREAD
` Wart For
`SELecT HIGHEST
`PRIORITY REQUEST
`WAITING?
`
`
`
`WAITING
`
`
`
` REQUEST
` FREE
`
`Fic. 6
`
`oS
`
`100
`
`Priority QUEUE
`
`106
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`

`

`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 4 of 5
`
`US 8,924,506 B2
`
`we
`
`beehed
`
`
`xlage
`
`4Boer.
`
`feeews
`
`beeccececveecseecssteoceceessatestgomde44qf4;4;;;¢Z5Z$5ZZ;ij;iiji44£wet¢yreas54gBirptGorrcereeeee
`
`
`
`
`
`serietebttbtbnstPMPPMAAEsedéanbuocecenonenenenenectectttettiiiasinisiitietthLiYOMCHAPLAEADROLLEIDOOEIOLALLLLOLLELELLELLCLLLOLOLEOLLHLERED
`Sg*%PaKsaidoohfing
`neeae¢ae
`sagt,keBeketoaofZ$225BeeSheeZ4gh,BE$ag&,Z;fewegeeop$fee%%3eeeeasZtS.gtherer%$oitfsGSiat.Seok%zSoorg4Ws>i‘%35LeReReAMARAEELAELRPEAAELGIDEOODEDLeeeceeverarecracteetesessessstattfecenaracengenntensitl
`
`
`
`
`*aceonZ4%deegga>aeZLaosgle,he£6ee%SeesgazaongEDtwaOegagedaageat5%gse$gee,£fit,tedg4nn,TE4“bbetegboosORoegazEe:zSooneve,Shed
`’Nee.As,gweFEwnatqwerntSRae4rn%%coocncelteos.A7crnverentiggagePaPAPUPERey4he4Fetytaege4fee;mefk;ZBeeGeTreat
`
`
`
`
`
`idlejgSeenennaepnenenseeerssECePsHtassetoenstls
`
` itn,Seow4g%%woeoegHi,noe?‘iZ$gSth,ate¥;ghtbopee:3$,i}i5TOELSPPPPOCELAEEELLSEREEEREELCPIEPLIEIILESIIPLIIIDD
`
`
`
`ge,we;fgeepeebosemadioepe4BEoetpkm5od
`
`Zgg5%$g5sgregoof5%5SDg3jia:Bek;ante$ateei:weaitt4BRAeorsEabeefnntteObeeteejZ4wheehsOe“eah£Speeecececee4ewcoveredweiHBBeegen
`
`+igenwe,"FeLnee
`
`“es3g4ttxzgond‘gt3g;tyaehecanrtoonncescerseciaggsdebotpeaencescetecereceeet
`
`OPA,SOPLEEELi%3gouty24thi1#mtGoowy,wey,teEB$r5oE4ue4,wea”,i4hnkekGaggre%tebedwe&ths"4¢g4behefap4$teéCeBreae
`
`Cede%$88HotreekigttAa.3go
`
`Microsoft Corp. Exhibit 1013
`
`Microsoft Corp. Exhibit 1013
`
`
`
`

`

`U.S. Patent
`
`Dec. 30, 2014
`
`Sheet 5 of 5
`
`US 8,924,506 B2
`
`59:4:foe3$eSafifvtated55enneveelsnosonrerdliied,BE,Apeenennendlgpel?reeooth,bfrs$.
`
`
`
`ons‘ynoer%;Be;Bad%Gh"z5ae:GeOEAaeeconcsansasseavesvessesefegttsGaoefaeee;fehei.pions4“&.SslebenAL”toaTEED¢“4,nene,z,fnye,Bong;Ed$ftee"eragteoed.%freeePreeg¢the$germsBelen“nf
`
`at,aaahPreeanLt,
`Cnd§oe“eejz’3byt4a/.z,mn$$545”.éheehe$ithyaLeetiseeda:3ai;we“e$Btodi;&&beiit;nOge$mntte8;imole“BBedje,iyei,fefé,te@;,me3gi734;“eeZ£%,3waper’¢ZSote¥PPOOPOOELECADEECA¢wo5ahi;4ji$e::if$$3$$e,gg%gg*¢gs¢$zBoe;:leevececevevceceveceetes:
`YOOCTRLCOREELLLLELALAELELSESELELEBLODUBLOLEOELDODELDECEOLALADLEDDSIEDECLSIELYESSLELISSEDDADIDIEDLDSLEDOLOELDLDEDDECLEDEDLESEOLIDLTAIDELIEIELIELELELSESELESLELYELELSESELSESELAESDSIESOSESESOLYELIDSEFESSELELSESESSESELSEEELELEELELESSELSESEISESELSELELTASEIELSEDLSOEEOVALITTELODIOUITIEDICIDCODICLESPOLEESSsZ;34ii}4ii2rsa3wosood4iwe’Prey,
`
`
`
`
`
`
`boon\ecavececenpsteresessrevt
`‘yenr‘.zee3Airresdcseransevcesseseeey
`Lsthet‘aé£z*Beii;i;i3ieTiteiiiéia:ietaeigS;;i3:gPogfeed:3iZ¢iatis;;i;::hteie\eenanerivcnconnssriseisndl
`
`SepeetZah,geé5:4BoasxbatBS5;;;%,BHParpegnfii,Beoeevencvecetfel,iecrocké4Hventennhy“Epp
`edeWm,z$s£of;4/ee¢aezi68,“Zea7os5soos3$bhee£f$fbee:Be¢ineseedtTEoo#gti4we
`Fook$e‘,$4tinete%444vereladg+e3;La%ys%¢;vegbragh£3zeectgthLah43A‘nberd
`bevcecceccercenesasiatiole$eAGagePe,;jtea“ny,j$n,nyEo2;weBotsJ%,
`PORES,;beamenraneranproseassecel$¢aej5;$,3ti;POOPOLELTELELLELELLEEELEL
`tilt:iBae,
`ececrencen4‘odei4fe¢;ii$4¢4¢g%;‘4¢4DPPLLLEL
`
`SELELEASESPLESEEEEESEEESSSELSODUIPIDOVIDEDIELELIOTODEDIOLEDEELEDOOLELALMALALELPEEELEREDEASAEIEEIETobboESoOnoroooeTTE
`
`
`
`
`
`
`
`
`yeeffefefe;4?,éfe£ered.OALAALILLESLAYporenswessastaateePPOLLLLLLESSSSLLLSPSS
`
`/.gen**aeefwos4he¢fCO,or4:347%fzffonbéabweHt,
`;“i*Ay5fatogsaeio3goryBegiebes“erwy5iaaeeAtied
`OPELLOEESEEEELELEEEELLEEASLAIPLOEDEDDEDEEDDDIPLPODOPEPEEDELLOSEDOPELDDEEEEPLELEEPELLEREELELOPPPLELOLPELEOEEELEOLPLLEDEPLLEELELOLPEPPLLOLPLLLEEPLOLLLELELEEDLEEEEEEEEE
`
`nn:
`
`tee
`
`Microsoft Corp. Exhibit 1013
`
`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 120to U.S. patent application Ser. No.
`12/619,643 filed on Nov. 16, 2009 now U.S. Pat. No. 7,908,
`343 which in tum in a continuation of and claimspriority
`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 channels”
`(that now issued on Jan. 5, 2010 as U.S. Pat. No. 7,644,131)
`whichin turn claimsthe benefit under 35 USC 119(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. 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, Levanonetal., filed on Dec. 24, 2001
`(now USS. Pat. No. 7,139,794 issued on Nov. 21, 2006 and
`whichis assignedto the Assignee of the present Application.
`
`FIELD
`
`The disclosure is related to network based, imagedistribu-
`tion systems and,in particular, to a system and methodsfor
`efficiently selecting and distributing image parcels through a
`narrowbandor 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 mayprovide 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-neededbasis.
`In conventionalfixed-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 implementa local image navi-
`gation system to provide zoom andor pan functions based on
`user interaction. As well recognized problem with such con-
`ventional systems could bethat 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 imagetransfer function
`increasesthe 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
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`differential coefficients to represent an image. Subsequent
`transmitted coefficient sets are progressively accumulated
`with prior transmitted sets to provide a succeedingly refined
`image. The inverse-transform function performedbythecli-
`ent computeris, 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
`enablesthe 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 coefficient data sets as the detail level of
`the image increases. Consequently, there is an inherently
`increasing latency in resolvingfiner levels of detail.
`An imagevisualization system proposed byYapet al., U.S.
`Pat. No. 6,182,114, overcomes someof the foregoing prob-
`lems. The Yapet al. system also 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 coefficient data sets are, therefore, of con-
`stant size, which supports a modest improvementin the algo-
`rithmic performance of the inverse transform operation
`required on the client.
`Yap et al. adds utilization of client image panningor 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-
`mationis 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 imageblock as the center point
`of an orderedretrieval 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 manydifferent 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 ofimagevisualization would clearly be
`beneficial. Conventional approacheseffectively presume that
`client systems have an excess of computing performance,
`memory and storage. Small clients, however, typically have
`restricted performanceprocessors with possibly no dedicated
`floating-point support, little general purpose memory, and
`extremely limited persistent storage capabilities, particularly
`relative to common imagesizes. 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 systemsare 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
`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 imagedata. In general, these abstraction layers are con-
`ventionally considered required to handle the mapping of the
`imagedata resolutionto the display resolution capabilities of
`the client system. That is, resolution resolved image data
`providedto the client is unconstrained by anylimitation 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 cannotbe 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 webphonesare examples
`of small clients that are frequently constrained by limited
`bandwidth conditions. The conventionally realizable maxi-
`mum network transmission bandwidth for such small devices
`
`may range from below one kilobit per secondto several tens
`of kilobits per second. While Yap et al. states that
`the
`described system can work over low bandwidth lines, little
`more than utilizing wavelet-based data compression is
`advancedas permitting effective operation at low communi-
`cations bandwidths. While reducing the amountof data that
`mustbe carried from theserverto the client is significant, Yap
`et al. simply relies on the data packet transfer protocols to
`provideforanefficient 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 andthe 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 andsoft-
`ware resources, andefficiently utilize low to very low band-
`width network connections.
`
`SUMMARY
`
`Thus, a general purpose of the present inventionis to pro-
`vide an efficient system and methodsof optimally presenting
`imagedata 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 hasa fixed pixelarray size, is received in a single and or
`plurality of network data packets, and were the fixed pixel
`array may be constrainedto a resolution less than or equal to
`the resolution ofthe client device display.
`An advantage of the present invention is that both image
`parcel data requests and the rendering of image data are
`optimized to address the display based on the display resolu-
`tion of the client system.
`
`20
`
`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 minimalclient 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 wherethe rate of point-of-view navi-
`gation exceeds the data requestrate.
`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 embeddedor 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. Usingfixed size transmission data
`blocks enables image data parcelsto 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
`providedto 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
`imageparcel and overlay data set that are to be stored by and
`served from a network server system in accordance with a
`preferred embodimentofthe present invention;
`FIG.3 is a block diagram of a client system image presen-
`tation system constructed in accordance with a preferred
`embodimentof the present invention;
`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 implementedin a preferred embodimentof the
`present invention;
`FIG.7 provides a process flow diagram showinga display
`image rendering thread implementedin a preferred embodi-
`mentof the present invention;
`FIG.8 provides a process flow diagram showingthe parcel
`map processing performed preliminary to the rendering of
`image data parcels in accordance with a preferred embodi-
`mentof 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-
`mentof the present invention; and
`FIG. 10 provides a process flow diagram detailing the
`determination of an optimal detail level for image parcel
`presentationfor a current viewing frustum in accordance with
`a preferred embodimentof the present invention.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`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 imagedata 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-
`processedto obtain a series K.sub.1-N ofderivative images of
`progressively lower imageresolution. 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 coloror bit per pixel depth of 16
`bits, which represents a data parcel size of 8K bytes. The
`resolution of the series K.sub.1-N of derivative images is
`preferably related to that of the source image data 32 or
`predecessor image inthe series by a factor of four. The array
`subdivision is likewise related by a factor of four such that
`each imageparcelis of a fixed 8K byte size.
`In the preferred embodimentof the present invention, the
`imageparcels 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
`DETAILED DESCRIPTION OF ONE OR MORE
`such that each compressed and stored image parcel has a fixed
`EMBODIMENTS
`2K byte size. The imageparcels are preferably stored inafile
`of defined configuration such that any image parcel can be
`located by specification of a K.sub.D, X, Y value, represent-
`ing the imageset 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 mappingefficiently. 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, compressionratio
`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 oneserver 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/GMLrepresentationis
`Microsoft Corp. Exhibit 1013
`
`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 imagedata,
`is responsive to requests received through a communications
`network, such as the Internet 14 generally andvarioustiers 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
`networkserver 12, provide a client display and enable image
`navigational input by a userofthe 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 Webserver,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 thex, y lateral, rotational and z height positioning of
`the viewing frustum over the image as well as the camera
`angle of incidencerelative 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
`imageserver 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 andorsatellite
`imagery of geographic regions, which can be obtained from
`commercial suppliers. The overlay image data 34 is typically
`a discretedata file providing image annotation informationat
`
`50
`
`55
`
`60
`
`65
`
`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 andreadily 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, GMLorbinary overlay data may be compressedprior
`to storage on the network server 12, 22.
`Thepreferred architecture 40 of a client system 18, 20, for
`purposes of implementing the present invention, is shown in
`FIG.3. The architecture 40 is preferably implemented by a
`software plug-in or application executed by the client system
`18, 20 and that utilizes basic software and hardware services
`provided by the client system 18, 20. A parcel request client
`42 preferably implements an HTML client that supports
`HTML-based interactions with the server 12, 22 using the
`underlying network protocol stack and hardware network
`interface provided by the client systems 18, 20. A central
`parcel processing control block 44 preferably implements the
`client process and control algorithms. The control block 44
`directs the transfer of received image parcels and XML/
`GML/binary overlay data to