Patentamt
`Europilsthes
`European
`Patent om"
`
`Office euvopéen MW
`
`(1
`
`(12)
`
`EUROPEAN PATENT SPECIFICATION
`
`(11)
`
`EP 1 070 290 B1
`
`(45) Date of publication and mention
`of the grant of the patent:
`07.01.2015 Bulletin 2015/02
`
`(21) Application number: 989064845
`
`(22) Date of filing: 12.02.1998
`
`(51) Int CI.:
`GOGF 17l30”°"°-°’}
`
`(86)
`
`International application number:
`PCT/US1993/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-NETZWERKSERVER MIT 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
`
`(56) References cited:
`EP-A- 0 967 556
`US-A- 5 615 325
`US-A- 5 701451
`US-A- 5 740 425
`
`US-A- 5 555 101
`US-A- 5 666 490
`US-A- 5 708 825
`
`US-A- 5 745 109
`
`- MEYER E A ET AL: "Borealls 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
`- CURRY C: "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
`
`(84) Designated Contracting States:
`AT BE CH DE DK ES FI FR GB GR IE IT LI LU MC
`NL PT SE
`
`(43) Date of publication of application:
`24.01.2001 Bulletin 2001/04
`
`(73) Proprietor: E-Plus Capital Inc.
`Herndon VA 20170 (US)
`
`(72) Inventors:
`‘ HORNBACKER, Cecil, V., III
`Apopka, FL 32712 (US)
`- CRONIN, John, C.
`Alexandria,
`Vlrglnla 22314 (US)
`
`(74) Representative: Hertz. Oliver et al
`v. Bezold & Partner
`Patentanwalte
`Akademiestrasse 7
`
`80799 Miinchen (DE)
`
`
`
`Note: Within nine months of the publication of the mention of the grant of the European patent in 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 ofopposition shall not be deemed to have been filed until the opposition fee has been
`paid. (Art. 99(1) European Patent Convention).
`
`Pnnted by Jeuve 75001 PARIS (FR)
`
`Microsoft Corp- Exhibit 1006
`
`EP1070290B1
`
`

`

`1
`
`EP1 070 290 B1
`
`
`
`
`
`
`2
`
`
`
`Descfipfion
`
`
`1. Field of the Invention
`
`
`
`
`
`
`
`[0001] This invention relates to workstation viewing im-
`
`
`
`
`
`
`
`ages ofdigital 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
`
`
`
`
`
`
`
`tion and texture tiles of fixed size. A low—end client com—
`
`
`
`
`
`
`
`
`
`
`puter loads only those texture tiles ofthe appropriate res-
`
`
`
`
`
`
`
`
`
`olution which intersect the view footprint, if they are not
`
`
`
`
`
`
`
`
`
`
`yet loaded.
`
`
`[0007]
`POTMESIL M.: "Maps Alive: viewing geospatial
`
`
`
`
`
`
`
`information on the WWW", Computer Networks and IS-
`
`
`
`
`
`
`
`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 anchors in 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 ofan URL encoding an image name,
`
`
`
`
`
`
`
`
`
`
`
`output style such as thumb nail orfull size, and optionally
`
`
`
`
`
`
`
`
`
`
`
`a graphic format. Upon receipt of a request, the server
`
`
`
`
`
`
`
`
`
`
`loads the file into memory, processes it, 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 code is returned to the browser defining a full
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`HTML page consisting of the title ofthe 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 not specify a view of the image file
`
`
`
`
`
`
`
`
`
`
`
`
`in terms of scale and region. Further, it is not disclosed
`
`
`
`
`
`
`
`
`
`
`
`that the web server determines an array of view tiles that
`
`
`
`
`
`
`
`
`
`
`
`corresponds to the requested view and creates the view
`
`
`
`
`
`
`
`
`
`tile images. Finally, it is not disclosed that the web server
`
`
`
`
`
`
`
`
`
`
`creates an HTML output file including appropriate for-
`
`
`
`
`
`
`
`matting and references to the created view tile images.
`
`
`
`
`
`
`
`
`
`[0009] Therefore, the system as disclosed in "Borealis
`
`
`
`
`
`
`
`
`Image Server" is not sufficiently efficient, which is espe-
`
`
`
`
`
`
`
`
`cially importantfor viewing large images, is. images that
`
`
`
`
`
`
`
`
`
`cannot be displayed in full.
`
`
`
`
`
`[0010] Therefore, it is an objectofthe invention to adapt
`
`
`
`
`
`
`
`
`
`
`the systems as disclosed in "Borealis Image Server" to
`
`
`
`
`
`
`
`
`
`allow efficient viewing of large images.
`
`
`
`
`
`
`
`SUMMARY OF THE INVENTION
`
`
`
`
`
`
`[0011] This object is achieved by a computer network
`
`
`
`
`
`
`
`
`
`server according to claim 1.
`
`
`
`
`
`[0012] The invention comprises a computer network
`
`
`
`
`
`
`
`server adapted to store digital document image files, pro-
`
`
`
`
`
`
`
`
`grammed to receive requests from a clientWeb browser
`
`
`
`
`
`
`
`
`
`in URL code, the URL specifying a view which identifies
`
`
`
`
`
`
`
`
`
`
`an image file and format, to compose the requested View,
`
`
`
`
`
`
`
`
`
`
`and to transmit HTML code for the resultant view to the
`
`
`
`
`
`
`
`
`
`
`
`client Web browser to display.
`
`
`
`
`
`
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`35
`
`
`
`40
`
`
`45
`
`
`
`
`55
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`
`
`[0002] Current methods for viewing digital document
`
`
`
`
`
`
`
`images forworkstations in a networked environment use
`
`
`
`
`
`
`
`
`proprietary workstation application software to access a
`
`
`
`
`
`
`
`network image file 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 number limitations 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 presentsaway
`
`
`
`
`
`
`
`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 user to 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 priorart reference fails to disclose a grid ofview
`
`
`
`
`
`
`
`
`
`
`
`tiles.
`
`re~
`PERRY, H.: "Spaces between tiled gifs",
`[0004]
`
`
`
`
`
`
`
`trieved from the
`internet: URL:http://groups.goog—
`
`
`
`
`le.com/groups/ comp.infosystems.www.authoring.imag-
`
`es/browse_thread/23b0acO47
`
`
`
`
`b8740e8/6cfcf0bc11b29e0b, 18 March 1997 discusses
`
`
`
`
`
`
`the so-called tiling of graphics files.
`
`
`
`
`
`
`[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.infosystems.www.authoring.imag~
`
`es/msg/0651277ebbf968077h| =en&dmode=source, 18
`
`
`March 1997.
`
`
`[0006] RABINOVICH B. et al.: "Visualization of Large
`
`
`
`
`
`
`
`
`Terrains in Resource—Limited Computing Environments",
`
`
`
`
`
`Proceedings Visualization ’97, 24 October 1997 disclos-
`
`
`
`
`
`
`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-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`

`

`3
`
`
`
`EP1 070 290 B1
`
`
`
`
`
`
`4
`
`
`
`[0013] The accompanying drawings, which are incor—
`
`
`
`
`
`
`porated in and constitute a part ofthe 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. 1 is a diagram of the system architecture show
`
`
`
`
`
`
`
`
`ing the relationship of the components ofthe 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 BB 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 composed for 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 48.
`
`
`
`
`
`FIGS. 6A and BB 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—
`
`
`
`
`
`
`
`
`
`
`nent of the view composer.
`
`
`
`
`
`FIGS. 10A, 108, 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 made in detail to the
`
`
`
`
`
`
`
`
`
`
`presently preferred embodiment of the invention, an ex-
`
`
`
`
`
`
`
`ample ofwhich 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 SCSI disk controller
`
`
`
`
`
`
`
`
`
`with at least 4GB of hard disk space, and LANNVAN/In—
`
`
`
`
`
`
`
`
`
`ternet network interface controllers. The server runs the
`
`
`
`
`
`
`
`
`Windows NT 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 firstto FIG. 1 , a network comprising clientwork-
`
`
`
`
`
`
`
`
`stations 10 and 20 are connected through network con-
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`35
`
`
`
`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 a document repository 90 hav-
`
`
`
`
`
`
`
`
`ing image files.
`
`
`
`The network image view server, i.e., client workstation,
`
`
`
`
`
`
`
`
`or"workstation," 100 can be implemented on a computer,
`
`
`
`
`
`
`
`
`
`for example a personal computer configured with a proc-
`
`
`
`
`
`
`
`essor, |/O, memory, disk storage, and a network inter-
`
`
`
`
`
`
`
`
`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 embodiment of the method
`
`
`
`
`
`
`
`
`
`of the invention, using the Web browser software 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 passed to the image view
`
`
`
`
`
`
`
`
`
`
`
`
`composition software and that identifies 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`data to the clientwith 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 to change the resolution of
`
`
`
`
`
`
`
`
`
`
`
`the image. The resultant HTMLfrom 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
`
`
`
`
`
`
`
`
`
`
`composer software through a common gateway interface
`
`
`
`
`
`
`
`(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 composer is initialized 140 and
`
`
`
`
`
`
`
`
`composes the 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 view tiles 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 view tiles to fulfill the request are already
`
`
`
`
`
`
`
`
`
`
`computed and stored in cache memory of 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
`
`
`
`EP1 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 view tiles
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`distinct resolutions (FIG 3B) ofa given image atthe server
`
`
`
`
`
`
`
`
`
`
`according to the URL request received from the browser
`
`
`
`
`
`
`
`
`
`software on the workstation. The use of tiling enables
`
`
`
`
`
`
`
`
`
`effective image data caching 60 atthe image view server
`
`
`
`
`
`
`
`
`
`
`and by the browser 10st the client workstation.
`
`
`
`
`
`
`
`
`
`[0017] The preferred view tile format is 128 pixel by
`
`
`
`
`
`
`
`
`
`
`128 pixel GIF image files. The GIF image file format is
`
`
`
`
`
`
`
`
`
`
`
`preferred because of Web browser compatibility and im-
`
`
`
`
`
`
`
`age file size. The GIF image file format is the mostwidely
`
`
`
`
`
`
`
`
`
`
`
`
`supported formatfor 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 loss-less image data com pression. 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 view tiles of 2048 bytes and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a typical GIF compression of4 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 information 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 headerfor a monochrome image adds as little as 31
`
`
`
`
`
`
`
`
`
`
`
`bytes to the GIF image file. 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 View tile size is a good compro-
`
`
`
`
`
`
`
`
`
`
`mise between view tile granularity and viewtile overhead.
`
`
`
`
`
`
`
`
`
`The viewtile granularity of 128 pixels determines the min-
`
`
`
`
`
`
`
`
`
`imum View shift distance (pan distance) that can be
`
`
`
`
`
`
`
`
`
`achieved with standard graphical Web browser and level
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`
`ofthe view tiles allows finer grid for view positioning, but
`
`
`
`
`
`
`
`
`
`
`
`has the problem that the view tile overhead becomes
`
`
`
`
`
`
`
`
`
`excessive.
`
`[0019] Aview tile typically represents more or less than
`
`
`
`
`
`
`
`
`
`
`128 x128 pixels of the image file. If the View being dis-
`
`
`
`
`
`
`
`
`
`
`
`played is reduced 2 to 1 , then each view tile will represent
`
`
`
`
`
`
`
`
`
`
`
`
`a 256 x 256 pixel area of the image file that has been
`
`
`
`
`
`
`
`
`
`
`
`
`
`scaled down to 128 x128 pixels. For each possible scale
`
`
`
`
`
`
`
`
`
`
`factor there is an array oftiles to representthe view. Fixed
`
`
`
`
`
`
`
`
`
`
`size view tiling is beneficial because it allows more ef-
`
`
`
`
`
`
`
`
`
`
`5
`
`
`10
`
`
`15
`
`
`20
`
`
`25
`
`
`
`30
`
`
`35
`
`
`
`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 composed of a
`
`
`
`
`
`
`
`
`
`
`
`single GIF file that is displayed by the Web browser, and
`
`
`
`
`
`
`
`
`
`
`
`so ifthe user asks forthe 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. 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 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 frorn the Web browser cache. The use of tiling cuts
`
`
`
`
`
`
`
`
`
`
`
`the computation and data transmission in half for this
`
`
`
`
`
`
`
`
`
`example.
`
`[0020] The use ofviewtiling 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 computes view tiles that sur-
`
`
`
`
`
`
`
`round the most recent View request in anticipation a re—
`
`
`
`
`
`
`
`
`
`questfor a shifted view. When the 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 chance that the view tiles for a view may
`
`
`
`
`
`
`
`
`
`
`
`
`
`already exist in the view tile cache since the view tile
`
`
`
`
`
`
`
`
`
`
`
`cache maintains the most recently accessed view tiles.
`
`
`
`
`
`
`
`
`Since millions ofview 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 accessed view tiles in the case where the max-
`
`
`
`
`
`
`
`
`
`imum storage allocation or minimum storage free space
`
`
`
`
`
`
`
`
`limits are reached.
`
`
`
`[0021] The number of 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 view tiles to render the same
`
`
`
`
`
`
`
`
`
`
`
`view area, and so is less preferred. The view tile overhead
`
`
`
`
`
`
`
`
`
`
`
`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 text file.
`
`
`
`
`
`
`
`
`
`
`
`The networktransaction overhead increases 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 view tile size would slow the
`
`
`
`
`
`
`
`
`
`
`
`response to render a view.
`
`
`
`
`
`[0022] The HTML output file produced by the fore—
`
`
`
`
`
`
`
`
`ground view composer is passed to the Web server soft-
`
`
`
`
`
`
`
`
`
`ware to be transmitted to the Web browser. The graphical
`
`
`
`
`
`
`
`
`
`
`Web browser serves as the image viewer by utilizing 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 data list the size, position and
`
`
`
`
`
`
`
`
`
`
`the hyperlinkfor each view tile to be displayed. The view
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1006
`
`Microsoft Corp. Exhibit 1006
`
`

`

`7
`
`
`
`EP1 070 290 B1
`
`
`
`
`
`
`8
`
`
`
`tiles are stored in the GIF image file format that can be
`
`
`
`
`
`
`
`
`
`
`
`
`displayed by all common graphical Web browsers. The
`
`
`
`
`
`
`
`
`Web browser will retrieve each view tile 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, communicates with 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 Gateway Interface
`
`
`
`
`
`
`
`(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 view tile must
`
`
`
`
`
`
`
`
`
`
`
`be uniquely identified for reference by the Web browser
`
`
`
`
`
`
`
`
`
`with a view tile URL. This uniqueness is accomplished
`
`
`
`
`
`
`
`
`
`through a combination of storage location and view tile
`
`
`
`
`
`
`
`
`
`naming. Uniqueness between images is accomplished
`
`
`
`
`
`
`by having a separate storage subdirectory in the view tile
`
`
`
`
`
`
`
`
`
`
`cache for each image. Uniqueness of 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 of the tile number as determined by
`
`
`
`
`
`
`
`
`
`
`the formula:
`
`
`
`=
`TILEWROW
`TILEWNUMBER
`
`
`
`
`IMAG E_T| LE_WlDTH + TILE_COLU MN
`
`
`
`
`
`
`*
`
`
`
`
`
`
`[0026] The TILEUROW and TILE_COLUMN values
`
`start at 0 for this computation. For example the second
`
`
`
`
`
`
`
`
`
`
`tile ofthe first row for a View scaled 2:1 would be named
`
`
`
`
`
`
`
`
`
`
`
`
`
`under the preferred protocol:
`
`
`
`
`
`V3J00001.G|F
`
`
`[0027] The full URL reference for the second tile of the
`
`
`
`
`
`
`
`
`
`
`
`first row for image number 22 on the image view server
`
`
`
`
`
`
`
`
`
`
`
`would be:
`
`
`
`http://hostname/view-tlIe—cache-
`path/000022/V3J00001. GIF
`
`
`
`[0028]
`in addition to the view tile position and view
`
`
`
`
`
`
`
`
`
`
`scale, other view attributes that may be encoded in 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 encoded as:
`
`
`
`
`
`
`V < SCALE > < TILE...,NUMBER > < VIEW...ANGLE
`
`
`
`
`
`> < X_M|RROR > s Y_ MIRROR > < lNVERT >. GIF
`
`
`
`
`
`
`
`[0029] ViEW_ANGLE is of the form A < ANGLE >.
`
`
`
`
`
`
`
`
`
`
`X_MIRROR, Y_MIRROR, and lNVERT are encoded by
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the single characters X, Y, and l respectively. An example
`is:
`
`
`V3J00001A90XYLG|F
`
`
`
`
`[0030] The Web server 30 is configured to recognize
`
`
`
`
`
`
`
`
`
`the above—described speciallyformatted 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 document filename extension.
`
`
`
`
`[0031] The foreground view composer 5O 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 as a delta to a previous view, or implied
`
`
`
`
`
`
`
`
`
`
`by relying on system defaults to select the view.
`
`
`
`
`
`
`
`
`
`[0032] View computation software routine 150 is illus—
`
`
`
`
`
`
`
`trated in FIG 7 wherein the command interpreter 151
`
`
`
`
`
`
`
`
`
`takes the view request and determines 152 what scale
`
`
`
`
`
`
`
`
`
`view tile grid is needed for the view and what view tiles
`
`
`
`
`
`
`
`
`
`
`
`
`within the grid are needed for 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 files according to the pre-
`
`
`
`
`
`
`
`
`
`
`ferred steps shown in FIG 8. The view tile generator re—
`
`
`
`
`
`
`
`
`
`
`ceives information from the view computation as to what
`
`
`
`
`
`
`
`
`
`view tiles are needed forthe view. it has access to records
`
`
`
`
`
`
`
`
`
`
`
`in the cache 60 that determine which tiles have already
`
`
`
`
`
`
`
`
`
`
`been created and are resident in the cache. lfa needed
`
`
`
`
`
`
`
`
`
`
`view tile is in the cache then its lastaccesstime is updated
`
`
`
`
`
`
`
`
`
`
`
`
`
`to prevent the cache garbage collector from deleting the
`
`
`
`
`
`
`
`
`
`view tile.
`If a needed view tile is not in the cache, then
`
`
`
`
`
`
`
`
`
`
`
`
`
`theviewtilegeneratorcreatesthe viewtilefromtheimage
`
`
`
`
`
`
`
`
`
`
`
`file 90. The view tile generator uses a software imaging
`
`
`
`
`
`
`
`
`
`
`library that supports rendering many digital documentfile
`
`
`
`
`
`
`
`
`formats including monochrome raster images, gray scale
`
`
`
`
`
`
`
`raster images, color raster images as well as many con-
`
`
`
`
`
`
`
`
`
`tentrich non-rasterformats 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.
`
`
`
`
`
`
`[0034]
`For example, a specific view request might in-
`
`
`
`
`
`
`
`
`clude tiles 82, CZ, BS, and C3 (FIG 4A and FIG 5A). If,
`
`
`
`
`
`
`
`
`
`
`
`
`
`after viewing those tiles, 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. lfthe client
`
`
`
`
`
`
`
`
`
`
`
`
`does not cache then tiles A2, A3, BZ, and BS are sent.
`
`
`
`
`
`
`
`
`
`
`
`
`[0035]
`Formatted output is created 170 to reference
`
`
`
`
`
`
`
`
`t