Electronic Acknowledgement Receipt
`
`EFSID:
`
`Application Number:
`
`24787792
`
`14547148
`
`International Application Number:
`
`Confirmation Number:
`
`5188
`
`Title of Invention:
`
`OPTIMIZED IMAGE DELIVERY OVER LIMITED BANDWIDTH COMMUNICATION
`CHANNELS
`
`First Named Inventor/Applicant Name:
`
`Isaac Levanon
`
`Customer Number:
`
`35070
`
`Filer:
`
`Anatoly Weiser.
`
`Filer Authorized By:
`
`Attorney Docket Number:
`
`AP026CON1
`
`Receipt Date:
`
`Filing Date:
`
`Time Stamp:
`
`01-FEB-2016
`
`19-NOV-2014
`
`20:01:14
`
`Application Type:
`
`Utility under 35 USC 111 (a)
`
`Payment information:
`
`Submitted with Payment
`
`I no
`
`File Listing:
`
`Document
`Number
`
`Document Description
`
`File Name
`
`File Size(Bytes}/
`Message Digest
`
`Multi
`Part /.zip
`
`Pages
`(if appl.)
`
`1
`
`Non Patent Literature
`
`Doc03-
`MichalsonDecl_IPRl 5-1434-
`Pat343-lmage-Partl .pdf
`
`21736815
`
`07 e 7c2bc5 5 9e 5 1 bd4483 ed 72 794a834ed 5
`850bf
`
`no
`
`90
`
`Warnings:
`
`Information:
`
`Microsoft Corp. Exhibit 1013
`
`1 of 589
`
`

`

`2
`
`Non Patent Literature
`
`Doc03-
`MichalsonDecl_IPRl 5-1434-
`Pat343-lmage-Part2.pdf
`
`10586890
`
`e552b 1506d980df8df60aa 1461 b84af8086
`9477
`
`no
`
`42
`
`Warnings:
`
`Information:
`
`3
`
`Non Patent Literature
`
`Doc04-
`MichalsonDecl_IPRl 5-1435-
`Pat506-lmage-Partl .pdf
`
`22761994
`
`902 4684e85 Sd bb6a5 6aa0c20d c2a97 64 7 4d
`d84cf
`
`no
`
`90
`
`Warnings:
`
`Information:
`
`4
`
`Non Patent Literature
`
`Doc04-
`MichalsonDecl_IPRl 5-1435-
`Pat506-lmage-Part2.pdf
`
`10521129
`
`ad8a60c 714 9 bd d4c2e64e01 5 8f24 9e64c5 b
`1d184
`
`no
`
`40
`
`Warnings:
`
`Information:
`
`Total Files Size (in bytes)
`
`65606828
`
`This Acknowledgement Receipt evidences receipt on the noted date by the USPTO of the indicated documents,
`characterized by the applicant, and including page counts, where applicable. It serves as evidence of receipt similar to a
`Post Card, as described in MPEP 503.
`
`New Agglications Under 35 U.S.C. 111
`If a new application is being filed and the application includes the necessary components for a filing date (see 37 CFR
`1.53(b)-(d) and MPEP 506), a Filing Receipt (37 CFR 1.54) will be issued in due course and the date shown on this
`Acknowledgement Receipt will establish the filing date of the application.
`
`National Stage of an International Agglication under 35 U.S.C. 371
`If a timely submission to enter the national stage of an international application is compliant with the conditions of 35
`U.S.C. 371 and other applicable requirements a Form PCT /DO/E0/903 indicating acceptance of the application as a
`national stage submission under 35 U.S.C. 371 will be issued in addition to the Filing Receipt, in due course.
`
`New International Agglication Filed with the USPTO as a Receiving Office
`If a new international application is being filed and the international application includes the necessary components for
`an international filing date (see PCT Article 11 and MPEP 181 O), a Notification of the International Application Number
`and of the International Filing Date (Form PCT/R0/1 OS) will be issued in due course, subject to prescriptions concerning
`national security, and the date shown on this Acknowledgement Receipt will establish the international filing date of
`the application.
`
`Microsoft Corp. Exhibit 1013
`
`2 of 589
`
`

`

`E:ttf.Cli;illi}~>(:~.SO:
`~~ur~illml
`
`ttU•:O~l~3fl.
`~~~!~ ():ft;~:if;'
`
`O:fflc~ -ti.l~Ctf)~~n
`d~:s bH~\'t::l:S
`
`(19)
`
`{12)
`
`1111~11 ~111111111~1 ~11111111 ~11111~ 1~11111~ l~I ~11111111111111
`EP 1 070 290 B1
`
`c11)
`
`EUROPEAN PATENT SPECIFICATION
`
`(45) Date of publk."fltion and mentlon
`of the grant of the patent
`07.01.2015 Bulletin 2015!02
`
`(21) Application number: 98906484.S
`
`(22) Date of filing: 12.02.1998
`
`(51) lnt Cl.:
`GOGF 17130 1=·01.i
`
`(86} International application number:
`PCT/US1900./003017
`
`{87} International publication number:
`WO 199G/041675 {19.0S.19G9 Gazette 1999/33)
`
`(54) NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT-SERVER, TILING AND CACHING
`ARCHITECTURE
`
`B!LDBETRACHTUNGS-NETZWERKSERVER MIT EFF!Z!ENTEN KUNDENSERVER,
`OATENSEITEN UND CACHEARCHITEKTUR
`
`SERVEUR DE VISUALISATION D'IMAGES EN RESEAU UT!L!SANT UN SERVEUR CLIENT
`EFFICACE, UNE ARCHITECTURE EN MOSAIQUE ET A CONCEPT D'ANTEMEMOIRE
`
`(84) Designated Contracting States:
`ATBE CH OE OK ESFI FRGB GR IE ITU LU MC
`NL PT SE
`
`(43) Date of publication of application:
`24.01.2001 Bulletin 2001/04
`
`(73} Proprietor: E-PhJs Capita! Inc,
`Herndon VA 20170 {US}
`
`(72) Inventors:
`• HORNBACKER, Cecil, V., Ill
`Apopka, FL 32712 {US)
`• CRONIN, John, C.
`Al&xandr!a,
`Virginia 22314 {US)
`
`(7 4) Representative: Hertz, Olivar et al
`v. Bezold & Partner
`Patentanwfllte
`Akademlestrasse 7
`80799 Mtinchen {DE}
`
`(56} References cited;
`EP·A· 0 967 556 US-A· 5 555 101
`US·A· 5 615 325 US·A· 5 666 490
`US·A· 5 701 451 US·A· 5 708 825
`US·A· 5 740 425 US-A· 5 745 109
`
`• MEYER E A ET AL: "Borealis Ima~ Server"
`COMPUTER NETWORKS ANO !SON SYSTEMS,
`NORTH HOLLAND PUBLISHING. AMSTERDAM,
`NL, vol. 28, no. 11, May 1996 (1996·05}, pages
`1123·1137, XP004018214 ISSN: 0169·7552
`• CURRY C: "Making A Cllckable Image Map" NA,
`May 1995 (1995-05), XP002235112
`• "VIRTUAL IMAGE EDITING" IBM TECHNICAL
`DISCLOSURE BULLETIN, IBM CORP. NEW
`YORK, US, vol. 39, no. 8, August 1996 {1996-08),
`pages 93-96, XP000638148 ISSN: 0018-8689
`
`Note: W!lh!n nine months of the publication of the mention of the grant of the European patent in the Eurnpean Patent
`Bw!letln, any person may give notice to the European Paten! Office of opposition to that patent in accordance with the
`Implementing Regulations. Noticeot opposition shall not be deemed to have been filed until the opposition fee has been
`paid. {Art. 99(1) El!topean Patent Convention).
`
`0.. w
`
`1\;f ic.rei~nft f"eim Fx hi hit 1 fH)fi
`
`Microsoft Corp. Exhibit 1013
`
`3 of 589
`
`

`

`EP 1 070 290 81
`
`2
`
`Description
`
`1. Field of the lnv0n!ion
`
`[0001 J This invention relates !o workstation viewing im(cid:173)
`ages of digital documents stored on a network server and
`in particular to viewing large digital document images us(cid:173)
`ing a client-server architecture.
`
`2, Description of the Prior Art
`
`5
`
`1i5
`
`25
`
`:w
`
`tion and texture tiles of fixed size. A low-end client com(cid:173)
`puter !oads only those texture tiles of the appropriate res(cid:173)
`oluilon which inter.s.f:ct the view foo!print if they Me not
`yet loaded,
`[0(}07] PO TM ESIL M.: "Maps Alive: viewing geospatial
`information on the IN\ft/W", Compu!er Networks and IS(cid:173)
`DN Systems 29 (1997) 1327-1342 disc!m;es a WWVV(cid:173)
`based S)'Stem for viewing geospatlal information_ The
`system oomprises a 20 map browser capable of contin-
`10 uous scroli and mom of an arbitrarily large sheet. which
`downloads and c<iches geographical information, goo.
`metrical models and URL anchors in small regions called
`tiles.
`[0008] MEYER E et a! .. "Borealis !mage Server"
`(COMPUTER NETWORKS AND
`iSDN SYSTEMS,
`NORTH HOLLAND PUBLISHING. AMSTERDAM, NL,
`vol. 28, no. 11, May 1996 ( 1996-05), pages 1123·1137,
`XP004018214 ISSN: 0169-7552.) discloses an image
`server for serving watermarkerj images to c!lenl web
`browsers. The oorver is programmed with web server
`soft.vare. The server receives requests from a client web
`browser ln the form of an URL encoding an Image name,
`output st~' le such as thumb nail or full size, and opliona!!y
`a graphic format. Upon receipt of a request, the server
`loads the file into memory, processes it and delivers the
`resulting image lo the brow$er. One or the Qut}.iut styles
`supported by the image server Is the "!11fo" output style.
`Wh~m an imagl~ is rl~qUe$ted with <iutput style ''info",
`HTML cMe is returned to the bmwser defini!1g a ful!
`HTML page c:onsis!in@of the title of the irmi~g~, an in lined
`thumbnail of !he image which is a link. to the fu!!-s,ize<l
`image, and copyright and authorltitle information, How(cid:173)
`ever, the URL does not specify a view of the image file
`in terms of scale and region, Further, it ls no! disclosed
`that the web server determines an array ol view tiles that
`corresponds to !he requested view and creates the view
`tile lmages. Finally, n is not disclosed that the web server
`creates an HTML output me including appropriate for,
`matting and references to the created view tile images.
`[0009] Therefore, the system as disclosed !n "Borealis
`Image Server" is not sufficiently efficient, which is espe(cid:173)
`ci<llly irnportantforv!ewing large images, I.e. images !hat
`cannot be displayed in full.
`[OIH OJ Therefore, i! is an objed of the invention ta adapt
`the systems as disclosed in "Borealis Image Server'' to
`allow efficient viewing of large images.
`
`[0002] Current methods for view1119 digital document
`images for workstations in a networked emtironment use
`propriet;:iry workstation application software !o access a
`net\1>1ork image file server. To view an image, the appli(cid:173)
`cation software transfers a copy of the whole image file
`from the image file server lo \he networked client work(cid:173)
`station This method has a number limitations including:
`inefficient «se of the nel'Nclrk; high sofawire purchase
`cost per workstation; high soft»"/are administrative cost w
`per vrorkstatkm; high computational demands on the
`workstation: proprietary softi.vare available only for limit-
`ed workstation types. Some other nehvork image vlew·ers
`may provide viewing using more optimized image trans·
`mission protocols but only with proprietary protocols and
`proprietary workstation software.
`[0003] CURRY C: "Making A Clickable !ma9e Map"
`N.A., M~w 1995(1995-05), XP002235112 pre$ent~Hl WHY
`to use a visual direct<iry as a means for accessing 1.m(cid:173)
`derlyill{l flies or t1m:uments or images that r<:i!ale to a
`p!a.ce 011 the top level visual directory. Ttie user is re(cid:173)
`quired to create a file that links areas on the initial image
`lo the tmderlying files or documents. A clickab!e image
`map a!lov~1s a user to cllc~. on any loc.ation of a graphic
`and receive more information in the form of an enlarged
`picture or a link to a uniform resource locator {URL). How-
`ever. this prior art reference fails to dlsciose a gl'id of view
`tiles.
`[0004] PERRY, H. · "Spaces beU.veen !iled gifrl", re ..
`the
`i11tetne!: URLhttp:l!gmups,goog(cid:173)
`from
`triaved
`!e.corn/groupsl comp.infosystems.www,authoring.imag(cid:173)
`es/brov1se _ threeidl23b0ac04 7
`b8740e8/6cfc:ffibc11 b29e0b, 18 March 1997 discusses
`the so-ca!!ed tiling of graphics files.
`[0005] Further, the tiling of graphics files is also dis(cid:173)
`cussed in PERRY, H.: "Spaces between Wed gifs", re(cid:173)
`trieved
`from
`the
`internet: URL:http:/fgroups.goog(cid:173)
`le.com/group! comp.infos·;'stems.www.autl'1oring.imag(cid:173)
`es/msg/c65127lebbf96807?hl "'en&dmode,,,source. '18
`March 1997.
`[0006] RABINOVICH 8, et at: 'ViSW~llzation of Large
`Terrains in Resource-limited Computing Environments",
`Proceedings ViSlialization '97, 24 October 1997 disclos·
`es a software system supporting Interactive vlst.1alisation
`of large terrains i11 an environment wm prising a !ow-end
`client computer acc:essing a large terrain database server
`through a !ow,bandwidth network. The large !errnin
`scene is slored on disk in the form of geometry informa-
`
`:m
`
`40
`
`45
`
`.so
`
`&5
`
`SUMMARY OF THE INVENTION
`
`[0011] This object is acl1ievoo by a computer network
`server according to claim 1,
`[0012] The inventiOn comprises a computer networ~:
`server adapted to storn digital document Image files, pro(cid:173)
`grammed to receive requests from a client Web browser
`in URL c:ode, the URL specifying a v!ew which identifies
`an image file and formal, t(1 com pose the requested view,
`a11d to transmit HT!v1l code for the resultant view to the
`cl.ientWeb browser to display.
`
`2
`
`1\Jf ic.rei~nft f"eim Fx hi hit 1 fH)fi
`
`Microsoft Corp. Exhibit 1013
`
`4 of 589
`
`

`

`3
`
`EP 1 070 290 81
`
`4
`
`5
`
`10
`
`[0013] The acrompanyi11g drnwings, which are incor(cid:173)
`porated in and constitute a part ofthe specification, illus(cid:173)
`trate An ernbot)im~~nt of the invention and together with
`the general description, serve lo explaln the principles of
`the invention.
`
`BRIEF DESCRIPTION OF THE DRA\NINGS
`
`[0014]
`
`OETtllLED DESCRIPTION OF THE INVENTION ANO
`THE PREFERRED EMBODIMENTS
`
`1i5
`
`FIG. 1 is a diagram of the system architecture show(cid:173)
`ing the relationship of lhe components of the system
`and the image view server.
`FIG. 2 ls a flow diagram of the steps performed by
`tl!e system to request, c:ompose and display a viE!lt>'
`of an Image.
`FIGS. 3A ;md 38 are dlagrams ttmt show the vJew
`tile grid as determined by the view scale.
`FIGS. 4A and 48 are diagrams that show !he grid
`view tiles cornposed for an initial image views and w
`then for a shifted view of the image.
`FIGS, SA and 58 are diagrams that show· the web
`browser display of view tiles for an initial view anct
`then for a shifted view of the image that correspond
`to FIGS. 4A a11d 4B.
`FIGR GA ancj 6B are diagrams that show view tiles
`pm-computed by the back.ground view composer
`FIG. 7 is a riigh-lev~~l flow diagrnm Clfthe for·Eigrmmi:!
`view composer.
`FIG. 8 is a f!ow di~~;Jr<w1 for trm viE!W gEmerator com(cid:173)
`ponent of the view composer.
`FIG. 9 is a flow diagmrn for the data output cornpo(cid:173)
`nent of the 11iew romposeJ.
`FIGS. 1 OA 1 OB, and ·1 OC together constitute a tlow
`diagram for the view tile c.ache garbage collector,
`
`25
`
`nections to a netVv'Ork image view server "100 o.:imprising
`a network server interface, prefernb!y a web senrer 30
`which uses the Hypertext Transfor Pmtoco! {HTTP}, .a
`request broker 40, a foreground view comp(lser 50, a
`view tile cache 60, a background view composer 80, a
`garbage co!lect0t 70, and a document repository 90 hav(cid:173)
`ing image files.
`The network image '>'iew setvet, Le., client workstation,
`or '\vorkstation. H ·100 c~n be implemented on a computer,
`for example a personal computer configured with a proc(cid:173)
`essor, l!O, memory, disk storage, and a network inter·
`face. The nel:<Nork image view server 100 is configured
`with a neti,vork server operating system and Web server
`~-0ftware 30 to provide the network HTTP protocol link
`1Nith tt1e client W1)rkstatk:ins 'l\J and 20, Typical networ~.s
`include many workstations sen11K! t:•y one, and some·
`times more t~mn one, riet\vork server, the server fum)·
`tioning as a library to maintain fi!es which can be ac-
`cessed by the worksta!lons,
`In operation according to an embodiment of the method
`of the irwer:tion, using the Web browser software on the
`dient workstation, a user reque;:;.ts an image view ·1 W
`(FIG_ 2) having a scale and region specified by means
`of a specially formatted Uniformed Resource Locator
`(URL) code using HTTP language which the Web server
`can i:lt~code as a request tQ be passed to tht> image view
`oompositlon software and that identifies the image file ta
`be viewed, lhE~ scale <if the viEiw mid tfH> region of the
`image to view. The net\vork im<>ge server sends HTML
`:w da!a to th€! die rit with pre-com pul€!tl hyperlinks, such that
`following a hyperlink by clicking on an area of an image
`will send a specific request to the server to deliver a dif(cid:173)
`ferent area of the drawing or to change the resolu!ion of
`the image. The resliltant HTML from this request will a!so
`:m contain pre-computed hyperHnks for other options lhe
`user may exercise.
`The code is sent over the network to the network server
`where tfle web server software interprets !he request
`120. passes the view request URL to lhe foreground view
`corn poser soft\vare through a common gateway Interface
`(CGI} that is designed to allow processing of HTTP re-
`quests external to !he Web server software, and thereby
`instructs the request broker 130 to gel the particular re(cid:173)
`quested view, having !he scale and region called for by
`the URL
`The foreground view composer is initialized 140 and
`corn poses the requested view 150 af!errecovering itfrom
`memory on the network server. The foreground view
`composer software interprets !he vie\"<' request. com~
`putes whicl1 view tiles are needed for the view, creates
`the view tiles 150 needed for the view, and then creates
`Hypertext Markup Language (HTML} output flle to de(cid:173)
`scribe ihe view composition to the VVeb browser, unless
`the necessary view tiles to fulflll the request are already
`oomputed and stored in cache memory of the worl<sta(cid:173)
`tion, in wf1lch case ll"le already-oornplited tiles are recov-
`ered by the Web browser, In either case, the foregrollnd
`view composer formals the output 170 and then intitial-
`
`10
`
`[0015] References will now be made In detail to the
`presently preferred embodiment of the invention, an ex(cid:173)
`ample of which Is illustrated in the accompanying draw(cid:173)
`ings.
`The preferred embodiment is s ssrvsr PC consisting of
`an Intel Pentium Pro 200MHz processor, wl!h at least 45
`128MB of RAM, an Ultra-wide Fast SCS! disk controller
`with at leas! 4GB of hard disk spat.e, and LAN1WANiln(cid:173)
`temet network interface controilers. The server nms the
`Windows NT Server Version 4 operating system wilh NT
`File System. Microsoft !ntemet Information Server Ver-
`sion 3, and the network image server software .. The serv--
`er and client are configured with TCPllP network proto-
`cols to supper! the HTTP (Web} pra!ocol. No software
`other than a Web l:lrowser is required on ll1e client. The
`preferred Web browser is Internet Explorer 3.0 or Net-
`scape 3,0 or higher.
`Referringflrstto FIG. 1, a network comprising client 1.vork(cid:173)
`s!ations 10 and 20 are connected tt1rough network con-
`
`-%'
`
`&5
`
`1\Jf ic.rei~nft f"eim F-x hi hit 1 fH)fi
`
`Microsoft Corp. Exhibit 1013
`
`5 of 589
`
`

`

`5
`
`EP 1 070 290 81
`
`5
`
`10
`
`:w
`
`izes backgound view composer 180 Which passes the
`formatted output to the Web server, whlch in tum trans(cid:173)
`mits Um forma!ted output aw~r ttie network to the Web
`browser 200 on the r equesling workstaUori 1 O, where the
`requesting browser displays any view tiles already
`cached 210, combined with newly computed view tiles
`220 which are fetche·d fmrn the server.
`[0016] The generation of the view tiles 160 ls har!dled
`by an image tiling rowtme which divides a given page,
`re11dered as an image, into a grid ofsmailer images {FIG
`3A) called view tiles A1, A2, B1, etc. {or just tiles in the
`image view server context). These tiles are computed for
`distinct resolutions {FIG 38} of a given image at the server
`according to !he URL request received from the browser
`soinvare on the workstation, The use of ll!lng enables
`effective image data caching 60 at the image view server
`and by the browser 1 Oat the client workstation.
`[0017] The preforred view tile format is 128 pixel by
`128 pixel G IF image flies. The GI F image flle !orm<lt is
`preferred becaus.e ofWeb browser compatibility and im- w
`age me size. The G IF image fil.e format is the most widely
`supported format for graphical Web browsers and there-
`fore gives the maximum client compatibility for the image
`view ser11er. The GIF irnage format has the desirable
`properties of loss-less image data compression, rea&,)n·
`ab!e data compression rnti<is. <:olor arnj gmy-scale sup·
`port,. and a relatively small image file header, which re·
`!ates t<i the selection of view tile size. With a rnw irn;3ge
`datH size for m(>nochrome view mes of 2,048 bytes and
`a lypit~31 G!F comprnssion of 4to1, the c.mnprnssed tfata
`for a 11iew tile is approximately 512 bytes. With many
`image file formats, such as TlFF and JPEG, !he image
`fi!e header (and other overhead information such as data
`indexes) can be as large or larger than the lmage data
`itself lor small images such as the view tiles; whereas a :m
`G!F header for a monochrome irnage adds as little as 3·1
`bytes to the G!F image file. Alternate view tile formats
`such as Portable Network Graphics (PNG) may be used,
`especially as native browser support for the formal be ..
`comes common.
`[0018] The 128 pixel view tile size Is a good compro(cid:173)
`mise between view tile granularity and view tlie overhead.
`The view rne granularity of i 28 pixels determines the min-
`imum view shift di.stanrn (pan dislance) ttiat can he
`achieved wllh standard graphical Web browser and level
`2 HTML formatting, This al!ow.s the adjustment of the
`view position on a 0,64 inch grid when viewing a 200
`pb<el-per-inch image at 1 to ·1 scale. Re<.lucing the size
`of the view t!les allows finer grid for view positioning, but
`has the problem lhat lhe view tile overhead beccmes
`excessive.
`f0019J Aviewtlle typically represents more or less lhan
`128x128 pixels of the ima>;Je file. If ihe view being dis·
`played is reduced 2to1. then each v1ewtile w!ll represent
`a 256 x 256 pixel area of !he image file that has been
`scaled down to ·128 x 128 pixels, For each possible s<:ale
`factor them is an array of Hies to represent the view. Fixed
`size view tiling is beneficial because it allows more ef-
`
`fectlve use of the cachin9 mechanism at the server and
`at !he client For example, consider a view of 512 pixels
`by 512 pixels. \Nittiou! tiliflg, this view !s composed <if .a
`single G!F me that is displayed by the Web brow~ser,. and
`so if the user asks for the view to be shifted by 256 pixels,
`then a new G!F image of 512 >: 512 pixels needs to be
`cniate<.l anct trnnsmitted to the Web browser, With tiling,
`the first view would cause 16 view tiles to be computed
`and transmitted for display by the Web browser. When
`the request for the view to l>e shifteo by 256 pixels is
`made, only B view tiles representing an area of 2% by
`512 pixels need to be ccmputed. In addition only the 8
`new view tiles need to be transmitted to the Web browser
`since the shifted view•Nill reuse 8 view liles that are avail·
`1i5 able n·om the Web bmwser cache. The l1se of tiling cuts
`the computation and data transmission in haff for this
`example.
`[OQ20] The use of view tiling also allows the image view
`server !o effeGtively pre-compute view tiles that may be
`required by the next view request. The image view server
`background view composer computes vlew !iles thatsur-
`rouoo the most recent view request in anticipation a re(cid:173)
`quest for a shifted view, When the shifted view is request(cid:173)
`ed, the foreground view G'Omposer can use the pre-com-
`25 pu!ed view Wes and eHmina!e !he t!me to compute new
`vi.;iw tiles for the view. For frequently acc:esse\:i lnrnges
`there ls a good chance Iha! the view tiles for a view may
`already eidsl in the vlew ti!€~ c;3<:t1e slnc1~ !hE~ vi;~w me
`cache maintains the mosi recently ac:cessed view !iles.
`Siric:e mi ii ions of view Illes may be creatE!1) and eventually
`e.xceed the storage capacity of the image view server,
`the vlew tile cache garbage coilector removes the !east
`recently accessed view tiles in the case where the max(cid:173)
`imum storage a!!ocatlon or minimum storage free space
`limits are reached.
`[0021] The number of view tiles needed to render a
`given view size increases in inverse proporlitm to the
`square of the view tile size, A 64 pixel vrew tile would
`require 4 times as many view tiles to render the same
`40 view area. and so is less prefen-ed. T!1e view tile overhead
`exists as quantity of dala and as the number of network
`transacilons, The data 1.wantity overhead comes from
`the image me header size as a proportion of the tota!
`image file size as descrlbed above and as data neE:<!'.led
`to make the view tile references in the HTML text file.
`The network transaction over head lncreases with srna lier
`view tlles since each of !he view Wes requires a network
`transaction, The increased number of network transac(cid:173)
`tions required with a smaller view tile size would slow the
`response to render a view.
`[0022] Trie HTML output file produced by the fore-·
`ground view composer is passed to thl':! Web server soft(cid:173)
`ware to be transmitted to the Web browser. The graphical
`\Neb browser serves as the image viewer by utilizing the
`&5 HTML outptJt from the image view server to compose
`arid clisp!ay me army of view tiles that form a view af an
`image. The HTML page data list lha size, posit.ion and
`the hyperllnk for each view tile to be displayed .. The view
`
`45
`
`.so
`
`4
`
`1\Jf ic.rei~nft f""'eim Fx hi hit 1 fH)fi
`
`Microsoft Corp. Exhibit 1013
`
`6 of 589
`
`

`

`7
`
`EP 1 070 290 81
`
`8
`
`V <SCALE ,, < TlLE .. NUMBER :• < VIEW ... ANGLE
`> < X_J,1 IRROR > < Y"' Ml RROR ,, < INVERT>. G IF
`
`[O!l29] V!EW .. ANGLE is of the form A < ANGLE .,, .
`5 X_MIRROR, Y _MIRROR, and INVERT are encoded by
`the slng!e characters X, Y, and I respectively, An example
`ls:
`
`!i!es ;m~ st<.:ired in the G!F image me format that can be
`displayed by all common graphical Web browsers, The
`Web hmwser will retrieve eac:h vi€!W tile lo be displ<lyer1
`from a local c.ache if the view tile is pres.ant, otheriNise
`from the image view server.
`[0023] The request broker 40 takes the raw request
`from the network server interface 130, interprets the re(cid:173)
`que$t, communicates with the olher S)'Stem compo11e1)t$
`and determines what the appropriate response should
`be. !t also detern1ines when the response is returned. In
`the preferred embOdiment the request broker is imple(cid:173)
`mented with the Web server Cornman Gateway Interface
`{CGI). Options exist to use ot!1er direct Application Pro(cid:173)
`gram Interfaces (AP!) to the Web server.
`[0024] To support tile tiling and caching of rmmy im(cid:173)
`ages on tr1e same image view si~rver, each vlew Iii!~ must
`be uniquely !denti!1ed for reference by !he Web browser
`with a view tile URL, This uniqueness is accomplished
`through a oombination of storage loc:<i!.ion and view tile
`naming, Uniqueness between images is ace-0mplished
`by having a separate storage subdirectory in the view tile
`cache for each image. Uniqueness of view mes for each
`scale of view is accomplished through the rne name for
`each vimv tile. The view tile name ls preferably of the
`following form:
`
`V <SCALE > < T!LE __ .NUMBER >. G!F
`
`[0025] The < SCALE > value is a 2 character siring
`formerj from !he.: base 36 encoding of the view scale
`number as expressed in parts per 256, The < TILE
`NUMBER > value is a 5 character string formed from the
`base 36 encoding of the me number as determined by
`the formula;
`
`TILE ROW
`:::
`TllE ... NllMBER
`IMAGE__T!LE __ WIDTH t TILE .. COL.UMN
`
`[0026] The TILE .. ROW and TILE .. COLUMN values
`start at 0 for this computation, For example the second
`rne of the first row for ;:i view scaled 2:1 would be named
`under the preferred protocol:
`
`V3.J00001.GIF
`
`[0027] The Ml URL reference for the second tile of the
`firs! row for image number 22 on the lrnage view server
`would be:
`
`hl!p:l/hoslnarneNiew-ti!e--cache(cid:173)
`pathi000022/V3J00001 .. GIF
`
`10
`
`1i5
`
`w
`
`25
`
`:w
`
`:m
`
`40
`
`45
`
`-SO
`
`V3JOOOO 1 A90XYLG IF
`
`[0030] The Web server 30 is configl!red to recognize
`the abova--describoo spedallyfcrma!ted request Uniform
`Resource Locators {URL) to be handled by the image
`view server reqliest broker 40. This is done b}' associ<1-
`lion of the req1Jesl broKer 40 with the URL pattl or w!th
`the document filename extension.
`[0031] The foreground view composer 50 lnterpre!s
`the view request command 140 to determine 1..vhat view
`needs to be composed, The view request may be abso-
`lute by defining scale and position, relative by defining
`scale and position as a delta to a previous view, or imp lied
`by relying on system defaults to select the view,
`[0032] View computation software routine 150 is illus·
`ti·ated in FlG i' wherein the command interpreter "1:51
`takes !he view request and determines 152 whal scale
`vi.;iw tile grid is needed for the view and wtl;•t view tiles
`within the grid are needed for trie view 150 {FIG. 2), and
`gen~irates !he view tile 153, n%m!ting in fotrnatti~d view
`!)Utpll! '154.
`[0!}33] The view ti!<~ gm1erator routine 160 p1~rfonns
`the actual creation of the view tiles ac.'COrding to the pre(cid:173)
`ferred steps shown in FlG 8. The vie»¥ tile generator re·
`r:-eives information frorn the view computation as to what
`view tiles are needed for the view, It has access to rec-0rds
`in the cache 60 that determine which tiles have already
`been created and are resident in the cache, !f a needed
`view tile is in the cache then Its l<isl access time is updated
`to prevent tt"1e cache garbage co!leclor frr.:irn deleting the
`view tile. lf a needed view tile ls not in lhe cache, then
`the view tile generator creates the view tile from the irrmge
`file 90, The view tile genernlor uses a s<:ifl.\¥are imaging
`librnryth;:it supports rendering rnany digital document me
`formats Including monochrome raster images, gray scale
`raster images, color raster images as 1.vell as many con-
`tent rich non-raster formats such as ,6-dobe Portable Doc(cid:173)
`ument Format (PDF), Postscript, HPGL, etc. When ren(cid:173)
`dering monochrome image data !he imaging library
`scale-to-gray scaUng is used to provide a more visua!!y
`appealing rendition of the reduced image,
`[0034] Far example, a specific view request might in(cid:173)
`clude mes 82, C2, B3, arid C3 {FIG 4A and FlG 5A}, !(
`after viewing those tiles, the clienl decides that the view
`ta the immediate left is desired, tr1e11 the server would
`send tiles A2 andA3 (FiG 48 and FIG 58), This assumes
`that lhe cllen! retains in a cache the other Hies. If lhe client
`does not i~ct1e then tiles A2, A3, 82, and BJ are sent.
`[0!}35] Formatted output ls created 170 lo referenoo
`the view tiles needed to dis~ilay the completed view. The
`
`5
`
`1\;f ic.rei~nft f"eim Fx hi hit 1 fH)fi
`
`In addilicn to the view me position and view
`[0028]
`scale, other view attribules that may be encoded in the
`view tile storage locatbn or in the view tile name. These &5
`attributes are view rota!lon angle, view x-mim:ir. view y(cid:173)
`mirror, lnvert view, A view tile name wiLl-i these e.l(tra view
`attribt<les can be ernxKled as:
`
`Microsoft Corp. Exhibit 1013
`
`7 of 589
`
`

`

`9
`
`EP 1 070 290 81
`
`10
`
`5
`
`10
`
`at a low priority to mlnimize interference with more ctitical
`system tasks. The storage free space limit is designed
`as a fai! .. ;~afe limit !n prevM! !he system from running out
`of storage, The free space limit is checked on a periodic
`basis and lf ii is exceeded th<:i gmbage collector becomes
`a critical system task and runs at a high priority w1tH lhe
`storage free space ls greater than the free space limit.
`[0040] Digita I document files may be stored on the web
`server or on a no th er server within the net.vorl<, The image
`files are typically managed as digital documents with at(cid:173)
`tribute information that is stored with the documents in
`the document repos1t01y 90. A d1giial document manage,
`merit system can run 111dependently or in conjunction with
`the image view server software, The digital document file
`1i5 may be a raster !mage flle ma non-raster document file.
`If th1~ digital document file is a non-raster format then it
`is rendered as 1~ mo11ochrome, grayscale, or color raster
`image for viewing.
`[0041] The grnphit:a! V</eb browser on ihe client work(cid:173)
`station 1 O receives HTML data from the image view serv(cid:173)
`er 210 that contains hyperlin~;s to the view tiles within the
`view tile cache 60 to oo displayed and formatting that
`ctescribes the layout of the of the tiles to form the image
`view. The Web browser initially must fetch each view tile
`25 220 for a vlew from the view seNer. After the initial view,
`w~ienEwer a view cwerl~3PS with a previous view at the
`same scale, the Web browser preferably retrieves view
`til.;is Hiat have bem1 previously (jlsplayed from the Web
`browser's local cache 210 rnthet than from !he server.
`[0042] PE;rformance and usabili!y of dowment viewing
`can be increased by using progressive display of li!e<l
`images, By using an image me format that allows a rollgh
`view of the image to be displayed while the remainder of
`the image content is downloaded, a rough view of the
`document can be seen more quickly,
`[OG43] Since most Web browsers can only trans.fer 1
`to 4 GJF lmages at a time, usually not all o·f the view tiles
`in U1e vlew army can be progressively displayed at the
`same !line. Therefore, it is preferred that lo Implement
`40 pro9ress!ve display, algorithms at the client are provided
`to accept an ;;ilternate data format th<lt woukj allow the
`whole document vie1Ning t~rea screen to t;1ke ;1dwmt;1ge
`of the progressive display while still taking advantage of
`the benefits of llllng and caching at the client. This can
`45 be accomplished in a Web browser e