`
`mci
`Patentamt
`European
`Patent Office
`deste
`
`|llll|lll||i|||||||
`EP 1 070 290 B1
`
`(11)
`
`(12)
`
`EUROPEAN PATENT SPECIFICATION
`
`(45) Date of publication and mention
`of the grantof the patent:
`07.01.2015 Bulletin 2015/02
`
`(21) Application number: 98906484.5
`
`(22) Date offiling: 12.02.1998
`
`(51) Int Cl:
`GO6F 17/30 (2996.01)
`
`(86)
`
`International application number:
`PCT/US1998/003017
`
`(87) International publication number:
`WO 1999/041675 (19.08.1999 Gazette 1999/33)
`
`(54) NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT-SERVER,TILING AND CACHING
`ARCHITECTURE
`
`BILDBETRACHTUNGS-NETZWERKSERVERMIT EFFIZIENTEN KUNDENSERVER,
`DATENSEITEN UND CACHEARCHITEKTUR
`
`SERVEUR DE VISUALISATION D’IMAGES EN RESEAU UTILISANT UN SERVEUR CLIENT
`EFFICACE, UNE ARCHITECTURE EN MOSAIQUE ET A CONCEPT D’ANTEMEMOIRE
`
`(84) Designated Contracting States:
`AT BE CH DE DK ES FIFR GB GRIE IT LILU MC
`NL PT SE
`
`(43) Date of publication of application:
`24.01.2001 Bulletin 2001/04
`
`(73) Proprietor: E-Plus CapitalInc.
`Herndon VA 20170 (US)
`
`(72) Inventors:
`¢ HORNBACKER, Cecil, V., Ill
`Apopka, FL 32712 (US)
`CRONIN, John, C.
`Alexandria,
`Virginia 22314 (US)
`
`(74— Representative: Hertz, Oliver et al
`v. Bezold & Partner
`Patentanwalte
`Akademiestrasse 7
`
`80799 Munchen (DE)
`
`(56) Referencescited:
`EP-A-0967556
`US-A-5615325
`US-A-5 701451
`US-A-5 740425
`
`US-A- 5555 101
`US-A- 5 666 490
`US-A-5 708 825
`US-A- 5745 109
`
`MEYER E AET AL: "Borealis Image Server"
`COMPUTER NETWORKSAND ISDN SYSTEMS,
`NORTH HOLLAND PUBLISHING. AMSTERDAM,
`NL, vol. 28, no. 11, May 1996 (1996-05), pages
`1123-1137, XP004018214 ISSN: 0169-7552
`CURRYC: "Making A Clickable Image Map" N.A.,
`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
`
`
`
`EP1070290B1
`
`Note: Within nine months of the publication of the mention of the grant of the European patentin the European Patent
`Bulletin, any person may give notice to the European Patent Office of opposition to that patent, in accordance with the
`Implementing Regulations. Notice of opposition shall not be deemed to have been filed until the opposition fee has been
`paid. (Art. 99(1) European Patent Convention).
`
`Printed by Jouve, 75001 PARIS (FR)
`
`Microsoft Corp. Exhibit 1006
`
`

`

`1
`
`EP 1 070 290 B1
`
`
`
`
`
`
`2
`
`
`
`Description
`
`
`1. Field of the Invention
`
`
`
`
`
`
`
`[0001] Thisinvention relates to workstation viewing im-
`
`
`
`
`
`
`
`agesof digital documents stored on a network server and
`
`
`
`
`
`
`
`
`
`
`in particular to viewing large digital document images us-
`
`
`
`
`
`
`
`
`ing a client-server architecture.
`
`
`
`
`
`2. Description of the Prior Art
`
`
`
`
`
`
`
`
`
`[0002] Current methods for viewing digital document
`
`
`
`
`
`
`
`imagesfor workstations in a networked environment use
`
`
`
`
`
`
`
`
`proprietary workstation application software to access a
`
`
`
`
`
`
`
`network imagefile server. To view an image, the appli-
`
`
`
`
`
`
`
`
`
`cation software transfers a copy of the whole image file
`
`
`
`
`
`
`
`
`
`
`from the image file server to the networked client work-
`
`
`
`
`
`
`
`
`
`station This method has a numberlimitations including:
`
`
`
`
`
`
`
`
`inefficient use of the network; high software purchase
`
`
`
`
`
`
`
`
`cost per workstation; high software administrative cost
`
`
`
`
`
`
`
`per workstation; high computational demands on the
`
`
`
`
`
`
`
`workstation; proprietary software available only for limit-
`
`
`
`
`
`
`ed workstation types. Some other network image viewers
`
`
`
`
`
`
`
`
`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 Image Map"
`
`
`
`
`
`
`
`
`N.A., May 1995 (1995-05), XP0022351 12 presents away
`
`
`
`
`
`
`
`to use a visual directory as a means for accessing un-
`
`
`
`
`
`
`
`
`
`
`derlying files or documents or images that relate to a
`
`
`
`
`
`
`
`
`
`place on the top level visual directory. The user is re-
`
`
`
`
`
`
`
`
`
`
`quired to create a file that links areas on the initial image
`
`
`
`
`
`
`
`
`
`
`
`
`to the underlying files or documents. A clickable image
`
`
`
`
`
`
`
`
`
`map allows a userto click on any location 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 referencefails to disclose a grid of view
`
`
`
`
`
`
`
`
`
`
`
`tiles.
`
`PERRY, H.: "Spaces between tiled gifs", re-
`[0004]
`
`
`
`
`
`
`
`trieved from the
`internet: URL:http://groups.goaog-
`
`
`
`
`le.com/groups/ comp.infasystems.www.authoring.imag-
`
`es/browse_thread/23b0ac047
`
`
`
`
`68740e88/6cfcfObc11b29e0b, 18 March 1997 discusses
`
`
`
`
`
`
`the so-called tiling of graphicsfiles.
`
`
`
`
`
`
`[0005]
`Further, the tiling of graphics files is also dis-
`
`
`
`
`
`
`
`
`
`cussed in PERRY, H.: "Spaces between tiled gifs", re-
`
`
`
`
`
`
`
`
`trieved from the
`internet: URL:http://groups.goog-
`
`
`
`
`le.com/group/ comp.infasystems.www.authoring.imag-
`
`es/msg/c651277ebbf96807 ?hl =en&dmode=source, 18
`
`
`March 1997.
`
`
`RABINOVICH B. et al.: "Visualization of Large
`[0006]
`
`
`
`
`
`
`
`
`Terrains in Resource-Limited Computing Environments",
`
`
`
`
`
`Proceedings Visualization '97, 24 October 1997 disclas-
`
`
`
`
`
`
`es a software system supporting interactive visualisation
`
`
`
`
`
`
`
`of large terrains in an environment comprising a low-end
`
`
`
`
`
`
`
`
`
`client computer accessing a large terrain database server
`
`
`
`
`
`
`
`through a low-bandwidth network. The large terrain
`
`
`
`
`
`
`
`scene is stored on disk in the form of geometry informa-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion and texture tiles of fixed size. A low-end client com-
`
`
`
`
`
`
`
`
`
`
`puterloads onlythosetexturetiles of the appropriate res-
`
`
`
`
`
`
`
`
`
`olution which intersect the view footprint, if they are not
`
`
`
`
`
`
`
`
`
`
`yet loaded.
`
`
`[0007]
`POTMESILM.:"MapsAlive: viewing geospatial
`
`
`
`
`
`
`
`information on the WWW", Computer Networks and |S-
`
`
`
`
`
`
`
`DN Systems 29 (1997) 1327-1342 discloses a WWW-
`
`
`
`
`
`
`
`based system for viewing geospatial information. The
`
`
`
`
`
`
`
`system comprises a 2D map browser capable of contin-
`
`
`
`
`
`
`
`
`uous scroll and zoom of an arbitrarily large sheet, which
`
`
`
`
`
`
`
`
`
`
`downloads and caches geographical information, geo-
`
`
`
`
`
`metrical models and URL anchorsin small regions called
`
`
`
`
`
`
`
`
`
`tiles.
`
`[0008] MEYER E. et al.: "Borealis Image 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 watermarked images to client web
`
`
`
`
`
`
`
`
`browsers. The server is programmed with web server
`
`
`
`
`
`
`
`
`software. The server receives requests from a client web
`
`
`
`
`
`
`
`
`
`browser in the form of an URL encoding an image name,
`
`
`
`
`
`
`
`
`
`
`
`output style such as thumb nail or full size, and optionally
`
`
`
`
`
`
`
`
`
`
`
`a graphic format. Upon receipt of a request, the server
`
`
`
`
`
`
`
`
`
`
`loads the file into memory, processesit, and delivers the
`
`
`
`
`
`
`
`
`
`
`resulting image to the browser. One of the output styles
`
`
`
`
`
`
`
`
`
`
`supported by the image server is the "info" output style.
`
`
`
`
`
`
`
`
`
`
`When an image is requested with output style "info",
`
`
`
`
`
`
`
`
`
`HTML cade is returned to the browser defining a full
`
`
`
`
`
`
`
`
`
`
`HTML page consisting of thetitle of the image,an inlined
`
`
`
`
`
`
`
`
`
`
`
`thumbnail of the image which is a link to the full-sized
`
`
`
`
`
`
`
`
`
`
`
`image, and copyright and author/title information. How-
`
`
`
`
`
`
`ever, the URL does notspecify a view of the image file
`
`
`
`
`
`
`
`
`
`
`
`
`in terms of scale and region. Further,it is not disclosed
`
`
`
`
`
`
`
`
`
`
`
`that the web server determines an arrayof view tiles that
`
`
`
`
`
`
`
`
`
`
`
`correspondsto the requested view and creates the view
`
`
`
`
`
`
`
`
`
`tile images. Finally, itis not disclosed that the web server
`
`
`
`
`
`
`
`
`
`
`creates an HTML outputfile including appropriate for-
`
`
`
`
`
`
`
`matting and references to the created viewtile images.
`
`
`
`
`
`
`
`
`
`[0009] Therefore, the system as disclosed in "Borealis
`
`
`
`
`
`
`
`
`Image Server" is not sufficiently efficient, which is espe-
`
`
`
`
`
`
`
`
`cially important for viewing large images, i.e. images that
`
`
`
`
`
`
`
`
`
`cannot be displayed in full.
`
`
`
`
`
`[0010] Therefore, itis an object ofthe invention to adapt
`
`
`
`
`
`
`
`
`
`
`the systems as disclosed in “Borealis Image Server" to
`
`
`
`
`
`
`
`
`
`allow efficient viewing of large images.
`
`
`
`
`
`
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`[0011] This object is achieved by a computer network
`
`
`
`
`
`
`
`
`
`server according to claim 1.
`
`
`
`
`
`[0012] The invention comprises a computer network
`
`
`
`
`
`
`
`server adaptedto store digital document image files, pro-
`
`
`
`
`
`
`
`
`grammedto receive requests from a client Web browser
`
`
`
`
`
`
`
`
`
`in URL code, the URL specifying a view whichidentifies
`
`
`
`
`
`
`
`
`
`
`an imagefile and format, to compose the requested view,
`
`
`
`
`
`
`
`
`
`
`and to transmit HTML code for the resultant view to the
`
`
`
`
`
`
`
`
`
`
`
`client Web browserto display.
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`38
`
`
`
`40
`
`
`45
`
`
`
`
`55
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`

`

`3
`
`
`
`EP 1 070 290 B1
`
`
`
`
`
`
`4
`
`
`
`[0013] The accompanying drawings, which are incor-
`
`
`
`
`
`
`porated in and constitute a part of the specification, illus-
`
`
`
`
`
`
`
`
`
`trate an embodiment of the invention and together with
`
`
`
`
`
`
`
`
`
`the general description, serve to explain the principles of
`
`
`
`
`
`
`
`
`
`the invention.
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`[0014]
`
`
`FIG. 1is a diagram of the system architecture show-
`
`
`
`
`
`
`
`
`ing the relationship of the components of the system
`
`
`
`
`
`
`
`
`
`and the image view server.
`
`
`
`
`
`FIG. 2 is a flow diagram of the steps performed by
`
`
`
`
`
`
`
`
`
`
`
`the system to request, compose and display a view
`
`
`
`
`
`
`
`
`
`of an image.
`
`
`
`FIGS. 3A and 3B are diagrams that show the view
`
`
`
`
`
`
`
`
`
`
`tile grid as determined by the view scale.
`
`
`
`
`
`
`
`
`FIGS. 4A and 4B are diagrams that show the grid
`
`
`
`
`
`
`
`
`
`
`view tiles composedfor an initial image viewS and
`
`
`
`
`
`
`
`
`
`then for a shifted view of the image.
`
`
`
`
`
`
`
`
`FIGS. 5A and 5B are diagrams that show the web
`
`
`
`
`
`
`
`
`
`
`browser display of view tiles for an initial view and
`
`
`
`
`
`
`
`
`
`
`then for a shifted view of the image that correspond
`
`
`
`
`
`
`
`
`
`
`to FIGS. 4A and 4B.
`
`
`
`
`
`FIGS. 6A and 6B are diagrams that show view tiles
`
`
`
`
`
`
`
`
`
`
`pre-computed by the background view composer.
`
`
`
`
`
`
`FIG. 7 is a high-level flow diagram of the foreground
`
`
`
`
`
`
`
`
`
`view composer.
`
`
`FIG. 8 is a flow diagram for the view generator com-
`
`
`
`
`
`
`
`
`
`ponent of the view composer.
`
`
`
`
`
`FIG. 9 is a flow diagram for the data output compo-
`
`
`
`
`
`
`
`
`
`
`nentof the view composer.
`
`
`
`
`
`FIGS. 10A, 10B, and 10C together constitute a flow
`
`
`
`
`
`
`
`
`
`
`
`diagram for the view tile cache garbage collector.
`
`
`
`
`
`
`
`
`
`DETAILED DESCRIPTION OF THE INVENTION AND
`
`
`
`
`
`
`THE PREFERRED EMBODIMENTS
`
`
`
`
`[0015] References will now be madein detail to the
`
`
`
`
`
`
`
`
`
`
`presently preferred embodimentof the invention, an ex-
`
`
`
`
`
`
`
`ample of which is illustrated in the accompanying draw-
`
`
`
`
`
`
`
`
`ings.
`
`The preferred embodiment is a server PC consisting of
`
`
`
`
`
`
`
`
`
`an Intel Pentium Pro 200MHz processor, with at least
`
`
`
`
`
`
`
`
`
`128MB of RAM, an Ultra-wide Fast SCS] disk controller
`
`
`
`
`
`
`
`
`
`with at least 4GB of hard disk space, and LAN/WAN/In-
`
`
`
`
`
`
`
`
`
`ternet network interface controllers. The server runs the
`
`
`
`
`
`
`
`
`WindowsNT Server Version 4 operating system with NT
`
`
`
`
`
`
`
`
`
`File System, Microsoft Internet Information Server Ver-
`
`
`
`
`
`
`sion 3, and the network image server software. The serv-
`
`
`
`
`
`
`
`
`
`er and client are configured with TCP/IP network proto-
`
`
`
`
`
`
`
`
`cols to support the HTTP (Web) protocol. No software
`
`
`
`
`
`
`
`
`
`other than a Web browser is required on the client. The
`
`
`
`
`
`
`
`
`
`
`
`preferred Web browser is Internet Explorer 3.0 or Net-
`
`
`
`
`
`
`
`
`scape 3.0 or higher.
`
`
`
`
`Referring first ta FIG. 1, anetwork comprising client work-
`
`
`
`
`
`
`
`
`stations 10 and 20 are connected through network con-
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`38
`
`
`
`40
`
`
`45
`
`
`
`
`55
`
`
`
`
`
`nections to a network image view server 100 comprising
`
`
`
`
`
`
`
`
`
`a network server interface, preferably a web server 30
`
`
`
`
`
`
`
`
`
`which uses the Hypertext Transfer Protocol (HTTP), a
`
`
`
`
`
`
`
`
`request broker 40, a foreground view composer 50, a
`
`
`
`
`
`
`
`
`
`view tile cache 60, a background view composer 80, a
`
`
`
`
`
`
`
`
`
`
`garbage collector 70, and adocument repository 90 hav-
`
`
`
`
`
`
`
`
`ing imagefiles.
`
`
`
`The network image view server,i.e., client workstation,
`
`
`
`
`
`
`
`
`or "workstation," 100 can be implemented on acomputer,
`
`
`
`
`
`
`
`
`
`for example a personal computer configured with a proc-
`
`
`
`
`
`
`
`essor, I/O, memory, disk storage, and a networkinter-
`
`
`
`
`
`
`
`
`face. The network image view server 100 is configured
`
`
`
`
`
`
`
`
`
`with a network server operating system and Web server
`
`
`
`
`
`
`
`
`
`software 30 to provide the network HTTP protocol link
`
`
`
`
`
`
`
`
`
`with the client workstations 10 and 20. Typical networks
`
`
`
`
`
`
`
`
`
`include many workstations served by one, and some-
`
`
`
`
`
`
`
`times more than one, network server, the server func-
`
`
`
`
`
`
`
`
`tioning as a library to maintain files which can be ac-
`
`
`
`
`
`
`
`
`
`
`cessed by the workstations.
`
`
`
`
`In operation according to an embodimentof the method
`
`
`
`
`
`
`
`
`
`of the invention, using the Web browsersoftware on the
`
`
`
`
`
`
`
`
`
`
`client workstation, a user requests an image view 110
`
`
`
`
`
`
`
`
`
`(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 decode as a request to be passedto the image view
`
`
`
`
`
`
`
`
`
`
`
`
`composition software and thatidentifies the image file to
`
`
`
`
`
`
`
`
`
`be viewed, the scale of the view and the region of the
`
`
`
`
`
`
`
`
`
`
`
`
`image to view. The network image server sends HTML
`
`
`
`
`
`
`
`
`
`datato the client with pre-computed 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-
`
`
`
`
`
`
`
`
`
`
`ferent area of the drawing or ta change the resolution of
`
`
`
`
`
`
`
`
`
`
`
`the image. The resultant HTML fram this requestwill also
`
`
`
`
`
`
`
`
`
`
`contain pre-computed hyperlinks for other options the
`
`
`
`
`
`
`
`user may exercise.
`
`
`
`The code is sent over the network to the network server
`
`
`
`
`
`
`
`
`
`
`
`where the web server software interprets the request
`
`
`
`
`
`
`
`
`120, passes the view request URL to the foreground view
`
`
`
`
`
`
`
`
`
`
`composersoftware through a common gatewayinterface
`
`
`
`
`
`
`
`(CGI) that is designed to allow processing of HTTP re-
`
`
`
`
`
`
`
`
`
`quests external to the Web server software, and thereby
`
`
`
`
`
`
`
`
`
`instructs the request broker 130 to get the particular re-
`
`
`
`
`
`
`
`
`
`quested view, having the scale and region called for by
`
`
`
`
`
`
`
`
`
`
`the URL.
`
`
`The foreground view composeris initialized 140 and
`
`
`
`
`
`
`
`
`composesthe requested view 150 after recovering itfrom
`
`
`
`
`
`
`
`
`memory on the network server. The foreground view
`
`
`
`
`
`
`
`
`composer software interprets the view request, com-
`
`
`
`
`
`
`putes which view tiles are needed for the view, creates
`
`
`
`
`
`
`
`
`
`
`the viewtiles 160 needed for the view, and then creates
`
`
`
`
`
`
`
`
`
`
`
`Hypertext Markup Language (HTML) output file to de-
`
`
`
`
`
`
`
`scribe the view composition to the Web browser, unless
`
`
`
`
`
`
`
`
`
`the necessary viewtiles to fulfill the request are already
`
`
`
`
`
`
`
`
`
`
`computed and stored in cache memoryof the worksta-
`
`
`
`
`
`
`
`
`tion, in which case the already-computed tiles are recov-
`
`
`
`
`
`
`
`
`ered by the Web browser. In either case, the foreground
`
`
`
`
`
`
`
`
`
`
`view composer formats the output 170 and then intitial-
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`5
`
`
`
`EP 1 070 290 B1
`
`
`
`
`
`
`6
`
`
`
`izes backgound view composer 180 which passes the
`
`
`
`
`
`
`
`
`formatted output to the Web server, which in turn trans-
`
`
`
`
`
`
`
`
`
`mits the formatted output over the network to the Web
`
`
`
`
`
`
`
`
`
`
`browser 200 on the requesting workstation 10, where the
`
`
`
`
`
`
`
`
`
`requesting browser displays any view tiles already
`
`
`
`
`
`
`
`cached 210, combined with newly computed viewtiles
`
`
`
`
`
`
`
`
`220 which are fetched from the server.
`
`
`
`
`
`
`
`[0016] The generation of the view tiles 160 is handled
`
`
`
`
`
`
`
`
`
`
`by an image tiling routine which divides a given page,
`
`
`
`
`
`
`
`
`
`
`rendered as an image, into a grid of smaller images (FIG
`
`
`
`
`
`
`
`
`
`
`
`3A) called view tiles A1, A2, B1, etc. (or just tiles in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`image view server context). These tiles are computed for
`
`
`
`
`
`
`
`
`
`distinctresolutions (FIG 3B) of a given image at the server
`
`
`
`
`
`
`
`
`
`
`according to the URL request received from the browser
`
`
`
`
`
`
`
`
`
`software on the workstation. The use of tiling enables
`
`
`
`
`
`
`
`
`
`effective image data caching 60 at the image view server
`
`
`
`
`
`
`
`
`
`
`and by the browser 10atthe client workstation.
`
`
`
`
`
`
`
`
`
`[0017] The preferred view tile format is 128 pixel by
`
`
`
`
`
`
`
`
`
`
`128 pixel GIF imagefiles. The GIF image file formatis
`
`
`
`
`
`
`
`
`
`
`
`preferred because of Web browser compatibility and im-
`
`
`
`
`
`
`
`age file size. The GIF image file formatis the most widely
`
`
`
`
`
`
`
`
`
`
`
`
`supported format for graphical Web browsers and there-
`
`
`
`
`
`
`
`fore gives the maximum client compatibility for the image
`
`
`
`
`
`
`
`
`
`view server. The GIF image format has the desirable
`
`
`
`
`
`
`
`
`
`properties of lass-less image data compression, reason-
`
`
`
`
`
`
`able data compression ratios, color and grayscale sup-
`
`
`
`
`
`
`
`port, and a relatively small image file header, which re-
`
`
`
`
`
`
`
`
`
`lates to the selection of view tile size. With a raw image
`
`
`
`
`
`
`
`
`
`
`
`
`data size for monochrome viewtiles of 2,048 bytes and
`
`
`
`
`
`
`
`
`
`
`atypical GIF compression of 4 to 1, the compressed data
`
`
`
`
`
`
`
`
`
`
`for a view tile is approximately 512 bytes. With many
`
`
`
`
`
`
`
`
`
`
`image file formats, such as TIFF and JPEG, the image
`
`
`
`
`
`
`
`
`
`
`file header (and other overhead infarmation such as data
`
`
`
`
`
`
`
`
`
`indexes) can be as large or larger than the image data
`
`
`
`
`
`
`
`
`
`
`
`itself for small images such as the view tiles; whereas a
`
`
`
`
`
`
`
`
`
`
`
`GIF header for a monochrome image adds aslittle as 31
`
`
`
`
`
`
`
`
`
`
`
`bytes to the GIF imagefile. Alternate view tile formats
`
`
`
`
`
`
`
`
`
`
`such as Portable Network Graphics (PNG) may be used,
`
`
`
`
`
`
`
`
`
`especially as native browser support for the format be-
`
`
`
`
`
`
`
`
`comes common.
`
`
`[0018] The 128 pixel viewtile size is a good compro-
`
`
`
`
`
`
`
`
`
`
`mise between viewtile granularity and viewtile overhead.
`
`
`
`
`
`
`
`
`
`The view tile granularity of 128 pixels determines the min-
`
`
`
`
`
`
`
`
`
`imum view shift distance (pan distance) that can be
`
`
`
`
`
`
`
`
`
`achieved with standard graphical Web browserandlevel
`
`
`
`
`
`
`
`
`2 HTML formatting. This allows the adjustment of the
`
`
`
`
`
`
`
`
`
`view position on a 0.64 inch grid when viewing a 200
`
`
`
`
`
`
`
`
`
`
`
`pixel-per-inch image at 1 to 1 scale. Reducing the size
`
`
`
`
`
`
`
`
`
`
`of the viewtiles allowsfiner grid for view positioning, but
`
`
`
`
`
`
`
`
`
`
`
`has the problem that the view tile overhead becomes
`
`
`
`
`
`
`
`
`
`excessive.
`
`[0019]
`Aviewtile typically represents moreorless than
`
`
`
`
`
`
`
`
`
`
`128 x 128 pixels of the image file. If the view being dis-
`
`
`
`
`
`
`
`
`
`
`
`played is reduced 2 to 1, then each viewtile will represent
`
`
`
`
`
`
`
`
`
`
`
`
`a 256 x 256 pixel area of the imagefile that has been
`
`
`
`
`
`
`
`
`
`
`
`
`
`scaled down to 128 x 128 pixels. For each possible scale
`
`
`
`
`
`
`
`
`
`
`factor there is an arrayoftiles to represent the view. Fixed
`
`
`
`
`
`
`
`
`
`
`size view tiling is beneficial because it allows more ef-
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`38
`
`
`
`40
`
`
`45
`
`
`
`
`55
`
`
`
`
`
`fective use of the caching mechanism at the server and
`
`
`
`
`
`
`
`
`
`
`at the client. For example, consider a view of 512 pixels
`
`
`
`
`
`
`
`
`
`
`
`by 512 pixels. Without tiling, this view is composedof a
`
`
`
`
`
`
`
`
`
`
`
`single GIF file that is displayed by the Web browser, and
`
`
`
`
`
`
`
`
`
`
`
`so if the user asksfor the view to be shifted by 256 pixels,
`
`
`
`
`
`
`
`
`
`
`
`
`
`then a new GIF image of 512 x 512 pixels needs to be
`
`
`
`
`
`
`
`
`
`
`
`
`
`created and transmitted to the Web browser. Withtiling,
`
`
`
`
`
`
`
`
`
`the first view would cause 16 viewtiles to be computed
`
`
`
`
`
`
`
`
`
`
`
`and transmitted for display by the Web browser. When
`
`
`
`
`
`
`
`
`
`the request for the view to be shifted by 256 pixels is
`
`
`
`
`
`
`
`
`
`
`
`
`made, only 8 view tiles representing an area of 256 by
`
`
`
`
`
`
`
`
`
`
`
`512 pixels need to be computed. In addition only the 8
`
`
`
`
`
`
`
`
`
`
`
`new view tiles need to be transmitted to the Web browser
`
`
`
`
`
`
`
`
`
`
`
`since the shifted view will reuse 8 view tiles that are avail-
`
`
`
`
`
`
`
`
`
`
`
`able from the Web browsercache. The useoftiling cuts
`
`
`
`
`
`
`
`
`
`
`
`the computation and data transmission in half for this
`
`
`
`
`
`
`
`
`
`example.
`
`[0020] Theuseofviewtiling also allows the image view
`
`
`
`
`
`
`
`
`
`
`
`server to effectively pre-compute view tiles that may be
`
`
`
`
`
`
`
`
`
`required by the next view request. The image view server
`
`
`
`
`
`
`
`
`
`
`background view composer computesviewtiles that sur-
`
`
`
`
`
`
`
`round the mostrecent view requestin anticipation a re-
`
`
`
`
`
`
`
`
`
`questfor a shifted view. Whenthe shifted view is request-
`
`
`
`
`
`
`
`
`
`ed, the foreground view composer can use the pre-com-
`
`
`
`
`
`
`
`
`puted view tiles and eliminate the time to compute new
`
`
`
`
`
`
`
`
`
`
`view tiles for the view. For frequently accessed images
`
`
`
`
`
`
`
`
`
`there is a good chancethat the viewtiles for a view may
`
`
`
`
`
`
`
`
`
`
`
`
`
`already exist in the view tile cache since the view tile
`
`
`
`
`
`
`
`
`
`
`
`cache maintains the most recently accessed viewtiles.
`
`
`
`
`
`
`
`
`Since millions of view tiles may be created and eventually
`
`
`
`
`
`
`
`
`
`
`
`exceed the storage capacity of the image view server,
`
`
`
`
`
`
`
`
`
`the view tile cache garbage collector removes the least
`
`
`
`
`
`
`
`
`
`recently accessedviewtiles in the case where the max-
`
`
`
`
`
`
`
`
`
`imum storage allocation or minimum storage free space
`
`
`
`
`
`
`
`
`limits are reached.
`
`
`
`[0021] The numberof view tiles needed to render a
`
`
`
`
`
`
`
`
`
`
`given view size increases in inverse proportion to the
`
`
`
`
`
`
`
`
`
`square of the view tile size. A 64 pixel view tile would
`
`
`
`
`
`
`
`
`
`
`
`
`require 4 times as many viewtiles to render the same
`
`
`
`
`
`
`
`
`
`
`
`view area, and so is less preferred. The view tileoverhead
`
`
`
`
`
`
`
`
`
`
`
`exists as quantity of data and as the number of network
`
`
`
`
`
`
`
`
`
`
`
`transactions. The data quantity overhead comes from
`
`
`
`
`
`
`
`the image file header size as a proportion of the total
`
`
`
`
`
`
`
`
`
`
`
`image file size as described above and as data needed
`
`
`
`
`
`
`
`
`
`
`to make the view tile references in the HTML textfile.
`
`
`
`
`
`
`
`
`
`
`
`The network transaction overheadincreases with smaller
`
`
`
`
`
`
`
`view tiles since each of the view tiles requires a network
`
`
`
`
`
`
`
`
`
`
`
`transaction. The increased number of network transac-
`
`
`
`
`
`
`tions required with a smaller viewtile size would slow the
`
`
`
`
`
`
`
`
`
`
`
`response to render a view.
`
`
`
`
`
`[0022] The HTML output file produced by the fore-
`
`
`
`
`
`
`
`
`ground view composeris passed to the Web serversoft-
`
`
`
`
`
`
`
`
`
`ware to be transmitted to the Web browser. The graphical
`
`
`
`
`
`
`
`
`
`
`Web browser serves as the image viewerbyutilizing the
`
`
`
`
`
`
`
`
`
`
`HTML output from the image view server to compose
`
`
`
`
`
`
`
`
`
`and display the array of view tiles that form a view of an
`
`
`
`
`
`
`
`
`
`
`
`
`
`image. The HTML page datalist the size, positian and
`
`
`
`
`
`
`
`
`
`
`the hyperlink for each viewtile to be displayed. The view
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`7
`
`
`
`EP 1 070 290 B1
`
`
`
`
`
`
`8
`
`
`
`tiles are stored in the GIF imagefile format that can be
`
`
`
`
`
`
`
`
`
`
`
`
`displayed by all common graphical Web browsers. The
`
`
`
`
`
`
`
`
`Web browserwill retrieve each viewtile to be displayed
`
`
`
`
`
`
`
`
`
`
`from a local cache if the view tile is present, otherwise
`
`
`
`
`
`
`
`
`
`
`
`from the image view server.
`
`
`
`
`
`[0023] The request broker 40 takes the raw request
`
`
`
`
`
`
`
`
`
`from the network server interface 130, interprets the re-
`
`
`
`
`
`
`
`
`quest, communicateswith the other system components
`
`
`
`
`
`
`
`and determines what the appropriate response should
`
`
`
`
`
`
`
`be. It also determines when the response is returned. In
`
`
`
`
`
`
`
`
`
`
`the preferred embodiment the request broker is imple-
`
`
`
`
`
`
`
`mented with the Web server Common GatewayInterface
`
`
`
`
`
`
`
`(CGI). Options exist to use other direct Application Pro-
`
`
`
`
`
`
`
`
`gram Interfaces (API) to the Web server.
`
`
`
`
`
`
`
`[0024] To support the tiling and caching of many im-
`
`
`
`
`
`
`
`
`
`ages on the same image view server, each viewtile must
`
`
`
`
`
`
`
`
`
`
`
`be uniquely identified for reference by the Web browser
`
`
`
`
`
`
`
`
`
`with a view tile URL. This uniqueness is accomplished
`
`
`
`
`
`
`
`
`
`through a cambination of storage location and viewtile
`
`
`
`
`
`
`
`
`
`naming. Uniqueness between images is accomplished
`
`
`
`
`
`
`by having a separate storage subdirectory in the view tile
`
`
`
`
`
`
`
`
`
`
`cache for each image. Uniquenessof view tiles for each
`
`
`
`
`
`
`
`
`
`
`scale of view is accomplished through the file name for
`
`
`
`
`
`
`
`
`
`
`each view tile. The view tile name is preferably of the
`
`
`
`
`
`
`
`
`
`
`
`following form:
`
`
`
`
`
`V < SCALE > < TILE_NUMBER >. GIF
`
`
`
`
`
`
`[0025] The < SCALE > value is a 2 character string
`
`
`
`
`
`
`
`
`
`
`
`formed from the 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 ofthe tile number as determined by
`
`
`
`
`
`
`
`
`
`
`the formula:
`
`
`
`=
`TILE ROW
`TILE_NUMBER
`
`
`
`
`IMAGE_TILE_WIDTH + TILE_COLUMN
`
`
`
`
`
`
`‘
`
`[0026] The TILE_ROW and TILE_COLUMN values
`
`
`
`
`
`
`start at 0 for this computation. For example the second
`
`
`
`
`
`
`
`
`
`
`tile of the first row for a view scaled 2:1 would be named
`
`
`
`
`
`
`
`
`
`
`
`
`
`underthe preferred protocol:
`
`
`
`
`
`V3J00001.GIF
`
`
`[0027] The full URL referencefor the second tile of the
`
`
`
`
`
`
`
`
`
`
`
`first row for image number 22 on the image view server
`
`
`
`
`
`
`
`
`
`
`
`would be:
`
`
`
`http://hostname/view-tile-cache-
`path/000022/V3J00001. GIF
`
`
`
`[0028]
`In addition to the viewtile position and view
`
`
`
`
`
`
`
`
`
`
`scale, other view attributes that may be encodedin the
`
`
`
`
`
`
`
`
`
`
`view tile storage location or in the view tile name. These
`
`
`
`
`
`
`
`
`
`
`
`attributes are view rotation angle, view x-mirror, view y-
`
`
`
`
`
`
`
`mirror, invert view. A view tile name with these extra view
`
`
`
`
`
`
`
`
`
`
`
`attributes can be encodedas:
`
`
`
`
`
`
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`38
`
`
`
`40
`
`
`45
`
`
`
`
`55
`
`
`
`
`
`V <SCALE > < TILE. NUMBER > < VIEW_ANGLE
`
`
`
`
`
`><X_MIRROR><Y_MIRROR> <INVERT >. GIF
`
`
`
`
`
`
`
`[0029] VIEW_ANGLE is of the form A < ANGLE >.
`
`
`
`
`
`
`
`
`
`
`X_ MIRROR, Y_MIRROR, and INVERTare encoded by
`
`
`
`
`
`
`
`
`the single characters X, Y, and lrespectively. Anexample
`
`
`
`
`
`
`
`
`
`is:
`
`
`V3J00001A90XYI.GIF
`
`
`
`
`[0030] The Web server 30 is configured to recognize
`
`
`
`
`
`
`
`
`
`the above-described specially formatted request Uniform
`
`
`
`
`
`
`Resource Locators (URL) to be handled by the image
`
`
`
`
`
`
`
`
`
`view server request broker 40. This is done by associa-
`
`
`
`
`
`
`
`
`
`tion of the request broker 40 with the URL path or with
`
`
`
`
`
`
`
`
`
`
`
`
`the documentfilename extension.
`
`
`
`
`[0031] The foreground view composer 50 interprets
`
`
`
`
`
`
`
`the view request command 140 to determine what view
`
`
`
`
`
`
`
`
`
`needs to be composed. The view request may be abso-
`
`
`
`
`
`
`
`
`
`lute by defining scale and position, relative by defining
`
`
`
`
`
`
`
`
`
`scale and position asa delta to a previous view, or implied
`
`
`
`
`
`
`
`
`
`
`by relying on system defaults to select the view.
`
`
`
`
`
`
`
`
`
`[0032] View computation software routine 150is illus-
`
`
`
`
`
`
`
`trated in FIG 7 wherein the commandinterpreter 151
`
`
`
`
`
`
`
`
`
`takes the view request and determines 152 what scale
`
`
`
`
`
`
`
`
`
`view tile grid is needed for the view and whatviewliles
`
`
`
`
`
`
`
`
`
`
`
`
`within the grid are neededfor the view 150 (FIG. 2), and
`
`
`
`
`
`
`
`
`
`
`
`
`generates the view tile 153, resulting in formatted view
`
`
`
`
`
`
`
`
`
`output 154.
`
`
`[0033] The view tile generator routine 160 performs
`
`
`
`
`
`
`
`
`the actual creation of the view tiles according to the pre-
`
`
`
`
`
`
`
`
`
`
`ferred steps shown in FIG 8. The viewtile generator re-
`
`
`
`
`
`
`
`
`
`
`ceives information from the view computation as to what
`
`
`
`
`
`
`
`
`
`view tiles are needed for the view. Ithas access torecords
`
`
`
`
`
`
`
`
`
`
`
`in the cache 60 that determine whichtiles have already
`
`
`
`
`
`
`
`
`
`
`been created and are resident in the cache. If a needed
`
`
`
`
`
`
`
`
`
`
`view tile is in the cache then its lastaccesstime is updated
`
`
`
`
`
`
`
`
`
`
`
`
`
`to prevent the cache garbagecollector from deleting the
`
`
`
`
`
`
`
`
`
`view tile.
`If a needed view tile is not in the cache, then
`
`
`
`
`
`
`
`
`
`
`
`
`
`the view tile generator creates the viewtile from the image
`
`
`
`
`
`
`
`
`
`
`
`file 90. The view tile generator uses a software imaging
`
`
`
`
`
`
`
`
`
`
`library that supports rendering manydigital document file
`
`
`
`
`
`
`
`
`formats including monochrome raster images, gray scale
`
`
`
`
`
`
`
`raster images, color raster images as well as many con-
`
`
`
`
`
`
`
`
`
`tentrich non-raster formats such as Adobe Portable Doc-
`
`
`
`
`
`
`
`
`ument Format (PDF), PostScript, HPGL, etc. When ren-
`
`
`
`
`
`
`
`dering monochrome image data the imaging library
`
`
`
`
`
`
`
`scale-to-gray scaling is used to provide a more visually
`
`
`
`
`
`
`
`
`
`appealing rendition of the reduced image.
`
`
`
`
`
`
`For example, a specific view request might in-
`[0034]
`
`
`
`
`
`
`
`
`clude tiles B2, C2, B3, and C3 (FIG 4A and FIG 5A). If,
`
`
`
`
`
`
`
`
`
`
`
`
`
`after viewing thosetiles, the client decides that the view
`
`
`
`
`
`
`
`
`
`
`to the immediate left is desired, then the server would
`
`
`
`
`
`
`
`
`
`
`send tiles A2 and A3 (FIG 4B and FIG 5B). This assumes
`
`
`
`
`
`
`
`
`
`
`
`
`thatthe client retains in a cache the other tiles. If the client
`
`
`
`
`
`
`
`
`
`
`
`
`does not cache then tiles A2, A3, B2, and B3 are sent.
`
`
`
`
`
`
`
`
`
`
`
`
`[0035]
`Formatted output is created 170 to reference
`
`
`
`
`
`
`
`
`the viewtiles neededto display the completed view. The
`
`
`
`
`