PCT
`
`WORLD INTELLECTUAL PROPERTY ORGANIZATION
`International Bureau
`
`
`
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`(51) International PatentClassification © :
`(11) International Publication Number:
`WO 99/41675
`GO06F 15/00
`
`(43) International Publication Date:
`
`19 August 1999 (19.08.99)
`
`
`
`(21) International Application Number: PCT/US98/03017|(81) Designated States: AL, AM, AT, AU, AZ, BA, BB, BG, BR,
`BY, CA, CH, CN, CU, CZ, DE, DK, EE, ES, FI, GB, GE,
`GH, GM, GW, HU,ID,IL, IS, JP, KE, KG, KP, KR, KZ,
`LC, LK, LR, LS, LT, LU, LV, MD, MG, MK, MN, MW,
`Mx, NO, NZ, PL, PT, RO, RU, SD, SE, SG, SI, SK, SL,
`TJ, TM, TR, TT, UA, UG, US, UZ, VN, YU, ZW, ARIPO
`patent (GH, GM,KE, LS, MW,SD, SZ, UG, ZW), Eurasian
`patent (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM), European
`patent (AT, BE, CH, DE, DK, ES, FI, FR, GB, GR,IE,IT,
`LU, MC, NL, PT, SE), OAPI patent (BF, BJ, CF, CG, CI,
`CM, GA, GN, ML, MR, NE, SN, TD, TG).
`
`Network Image View Server
`
`A computer network server using HTTP
`(Web)server software combined with foreground
`view composer software (50), background view
`composer software (80), view tile cache (60),
`view tile cache garbage collector (70) and im-
`age files (90) provides image view data to client
`workstations (20) using graphical web browsers
`to display the view of an image fromthe server.
`Problems with specialized client workstation im-
`age view software are eliminated by using the in-
`ternet and industry standards based graphical web
`browsers for the client software. Network and
`system performance problemsthat previously ex-
`isted when accessing large image files froma net-
`workfile server are eliminated bytiling the image
`view so that computation and transmission of the
`view data can be done in an incremental fashion.
`The vicd tiles are cached on the client worksta-
`tion to further reduce networktraffic. View tiles
`are cached on the server to reduce the amount to
`view tile computation and to increase responsive-
`ness of the image view server.
`
`(22) International Filing Date:
`
`12 February 1998 (12.02.98)
`
`(71) Applicant (for all designated States except US): DIGITAL
`PAPER LLC [US/US]; Suite 100, 211 North Union Street,
`Alexandria, VA 22314 (US).
`
`(72) Inventors; and
`(75) Inventors/Applicants (for US only)} HORNBACKER, Cecil,
`V., Il [US/US]; 2032 Cranberry Isles Way, Apopka, FL
`32712 (US). CRONIN, John, C.
`[US/US]; Apartment 3,
`1804 Greene Street, Philadelphia, PA 19130 (US).
`
`Published
`With international search report.
`
`(74) Agents: FEIN, Michael, B. et al.; Suite 3600, 1600 Market
`Street, Philadelphia, PA 19103 (US).
`
`(54) Title) NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT-SERVER, TILING AND CACHING ARCHITECTURE
`
`(57) Abstract
`
`Client
`j caebbrowser)
`.
`40
`:
`ry
`
`Client
`Workstation
`
`Document
`Repository
`90
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`
`
`
`
`FOR THE PURPOSES OF INFORMATION ONLY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Codes used to identify States party to the PCT on the front pages of pamphlets publishing international applications under the PCT.
`
`
`
`
`
`
`
`
`
`
`
`
`ES
`Slovenia
`SI
`Lesotho
`Spain
`Albania
`AL
`FI
`Slovakia
`SK
`Lithuania
`Finland
`Armenia
`AM
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FR
`Senegal
`SN
`Luxembourg,
`France
`Austria
`AT
`
`Swaziland
`SZ
`Latvia
`Gabon
`GA
`Australia
`AU
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Chad
`TD
`Monaco
`United Kingdom
`GB
`Azerbaijan
`AZ
`
`
`
`
`
`
`
`
`
`
`
`Togo
`TG
`Republic of Moldova
`Georgia
`GE
`Bosnia and Herzegovina
`BA
`
`
`
`
`
`
`
`Tajikistan
`Madagascar
`Ghana
`GH
`Barbados
`BB
`TI
`
`
`
`
`
`
`
`
`
`Turkmenistan
`T™
`The former Yugoslay
`Guinea
`GN
`Belgium
`BE
`
`
`
`
`
`
`
`
`
`
`Turkey
`Republic of Macedonia
`Greece
`GR
`Burkina Faso
`BF
`TR
`
`
`
`
`
`
`
`
`
`
`Trinidad and Tobago
`Mali
`ML
`Hungary
`HU
`Bulgaria
`BG
`TT
`
`
`
`
`
`
`
`
`Ukraine
`UA
`Mongolia
`MN
`Treland
`Benin
`BJ
`TE
`
`
`
`
`
`
`
`
`Uganda
`UG
`Mauritania
`MR
`Israel
`IL
`Brazil
`BR
`
`United States of America
`US
`Malawi
`MW
`Iceland
`IS
`Belarus
`BY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Usbekistan
`UZ
`Mexico
`Mx
`Ttaly
`IT
`Canada
`CA
`
`
`
`
`
`
`
`
`
`
`
`Viet Nam
`VN
`Niger
`NE
`Japan
`Je
`Central African Republic
`CF
`
`
`
`
`
`
`
`
`Yugoslavia
`YU
`Netherlands
`NL
`Kenya
`KE
`Congo
`CG
`
`
`
`
`
`
`
`
`
`
`
`
`
`CH ZW.=ZimbabweSwitzerland KG Kyrgyzstan NO Norway
`
`
`
`
`
`
`
`
`
`
`Céte d'Ivoire
`Democratic People’s
`New Zealand
`KP
`NZ
`cI
`
`
`
`
`
`
`
`CM
`Cameroon
`Republic of Korea
`Poland
`PL
`
`
`
`
`
`
`
`Republic of Korea
`Portugal
`CN
`China
`PT
`
`Kazakstan
`RO
`Romania
`cu
`Cuba
`
`
`
`
`
`
`
`CZ
`Czech Republic
`Saint Lucia
`Russian Federation
`RU
`
`
`
`
`
`
`DE
`Germany
`Liechtenstein
`sD
`Sudan
`
`
`
`DK
`Sweden
`Denmark
`Sri Lanka
`SE
`
`
`
`
`
`
`
`
`
`
`
`Liberia
`SG
`Singapore
`EE
`Estonia
`
`
`
`Microsoft Corp. Exhibit 1003
`
`
`LS
`LT
`
`
`LU
`LV
`
`
`MC
`
`MD
`
`MG
`
`MK
`
`
`KR
`KZ
`
`LC
`
`
`LI
`LK
`
`
`LR
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`WO 99/41675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT-SERVER,
`
`
`
`
`TILING AND CACHING ARCHTECTURE
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`
`
`
`
`
`
`
`
`25
`
`
`
`30
`
`
`WO 99/41675
`
`
`
`
`
`
`
`PCT/US98/03017
`
`
`
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`1.
`
`
`
`
`Field of the Invention
`
`
`
`
`
`
`
`
`
`
`
`
`This invention relates to workstation viewing images of digital documents stored on a
`
`
`
`
`
`
`
`
`
`
`
`
`
`network server and in particular to viewing large digital document images using a client-server
`
`
`
`
`architecture.
`
`
`2.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Description of the Prior Art
`
`
`
`
`
`
`
`
`
`
`Current methods for viewing digital document images for workstations in a networked
`
`
`
`
`
`
`
`
`
`
`
`
`environment use proprietary workstation application software to access a network image file
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`server. To view an image, the application software transfers a copy of the whole image file
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from the image file server to the networked client workstation 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 limited workstation types. Some
`
`
`
`
`
`
`
`
`
`
`
`other network image viewers may provide viewing using more optimized image transmission
`
`
`
`
`
`
`
`
`
`
`protocols but only with proprietary protocols and proprietary workstation software.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`It is an object of the invention to provide a method of obtaining graphical images from
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a network server for viewing at a computer workstation which does not require proprietary
`
`
`workstation software.
`
`
`
`
`
`
`
`
`
`
`
`
`
`It is another object to provide such a method which makesefficient use of the network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and results in greater speed of image display in response to requests from the workstations.
`
`
`
`
`
`
`
`
`
`
`
`
`It is another object to provide such a method which makes use of caching mechanisms
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`resulting in a balanced load on the network file server and a faster response timeto a single
`
`
`
`
`
`
`
`
`
`client when many clients are accessing the server simultaneously.
`
`
`
`
`
`
`
`
`
`
`
`It is another object to minimize the computing resources required by a client
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`
`
`
`
`
`
`20
`
`
`25
`
`
`30
`
`
`WO 99/41675
`
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`workstation.
`
`
`
`
`
`
`
`
`
`
`
`A further object is to provide apparatus for storing graphical images, requesting
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`portions of the stored graphical images from storage, and quickly and efficiently displaying the
`
`
`
`images on a workstation.
`
`
`
`
`
`
`
`
`
`
`
`
`A still further object is to provide a computer program which facilitates requesting
`
`
`
`
`
`
`
`
`
`
`
`
`
`portions of graphical images stored on a network server and displaying those portions on a
`
`
`workstation.
`
`
`
`
`
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`These objects, and others which will become apparent from the following disclosure,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`are achieved by this invention which comprises in one aspect method of identifying and
`
`
`
`
`
`
`
`
`
`
`
`
`delivering a graphical image from a computer network file server comprising providing a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network file server on which are stored digital document imagefiles, said server adapted to
`
`
`
`
`
`
`
`
`
`
`
`
`
`receive requests from a Web browser in Uniform Resource Locator (URL) code, to identify
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the image file and format selections being requested, to compose the requested view into a grid
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`of view tiles, and to transmit HTML code for view tiles to the requesting Web browser.
`
`
`
`
`
`
`
`
`
`Another aspect of the invention comprises apparatus comprising a computer
`
`
`
`
`
`
`
`
`
`
`
`
`network server adapted to store digital document imagefiles, programmed to recieve requests
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from a client Web browser in URL code, the URL specifying a view which identifies an image
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`file and format, to compose the requested view, and to transmit HTMLcode for the resultant
`
`
`
`
`
`
`
`
`view to the client Web browserto display.
`
`
`
`
`
`
`
`
`
`
`
`
`
`A further aspect of the invention is the computer program recorded on magnetic or
`
`
`
`
`
`
`
`
`
`
`
`
`optical media for use on a network server comprising code which interprets HTTP requests
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from a workstation for a particular view of a digital document imagefile stored in memory,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`retrieves the digital document image file, composesa grid of view tiles corresponding to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`requested view of the image, computes HTMLcodeforthe grid of view tiles in a form which
`
`
`
`
`
`
`
`
`
`can be transmitted from the server to the workstation.
`
`
`
`
`
`
`
`
`
`
`
`
`
`The accompanying drawings, which are incorporated in and constitute a part of the
`
`
`
`
`
`
`
`
`
`
`
`
`specification, illustrate an embodiment of the invention and together with the general
`
`
`
`
`
`
`
`
`
`description, serve to explain the principles of the invention.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`
`
`
`
`
`
`
`20
`
`
`25
`
`
`
`30
`
`
`WO 99/41675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 1 is a diagram of the system architecture showing 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 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 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 component of the view composer.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 9 is a flow diagram for the data output component of 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`References will now be made in detail to the presently preferred embodiment of the
`
`
`
`
`
`
`
`
`
`
`
`invention, an example of which is illustrated in the accompanying drawings.
`
`
`
`
`
`
`
`
`
`
`
`
`
`The preferred embodimentis 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
`
`
`
`
`
`
`
`
`
`
`
`
`4GBof hard disk space, and LAN/WAN/Internet network interface controllers. The server
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`runs the Windows NT Server Version 4 operating system with NT File System, Microsoft
`
`
`
`
`
`
`
`
`
`
`
`
`Internet Information Server Version 3, and the network image server software. The server
`
`
`
`
`
`
`
`
`
`
`
`
`
`and client are configured with TCP/IP network protocols to support the HTTP (Web) protocol.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`WO 99/41675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`No software other than a Web browseris required on the client. The preferred Web browser
`
`
`
`
`
`
`
`
`
`
`
`is Internet Explorer 3.0 or Netscape 3.0 or higher.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Referring first to FIG. 1, a network comprising client workstations 10 and 20 are
`
`
`
`
`
`
`
`
`
`
`
`
`
`connected through network connections 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 having
`
`
`
`
`
`imagefiles.
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 processor,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`I/O, memory, disk storage, and a network interface. The network image view server 100 is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`configured with a network server operating system and Web server software 30 to provide the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network HTTPprotocol link with the client workstations 10 and 20. Typical networks include
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`many workstations served by one, and sometimes more than one, network server, the server
`
`
`
`15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`functioning as a library to maintain files which can be accessed 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 by meansof a specially formatted Uniformed Resource Locator
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(URL) code using HTTP language which the Web server can decode as a request to be passed
`
`
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to the image view composition software and that identifies the imagefile to be viewed, the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`scale of the view and the region of the image to view. The network image server sends
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`HTMLdata to 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 different
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`area of the drawing or to changethe resolution of the image. The resultant HTML from this
`
`25
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`request will 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 requests external to the Web server software, and thereby instructs the request broker
`
`
`
`30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`130 to get the particular requested view, having the scale and region called for by the URL.
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`WO 99/41675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The foreground view composeris initialized 140 and composes the requested view 150 after
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`recovering it from memory on the network server. The foreground view composer software
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`interprets the view request, computes 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 describe 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 workstation,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in which case the already-computed tiles are recovered by the Web browser.
`
`
`
`
`
`In either case,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the foreground view composer formats the output 170 and then intitializes backgound view
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`composer 180 which passes the formatted output to the Web server, which in turn transmits
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The generation of the view tiles 160 is handled by an imagetiling routine which divides
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a given page, rendered as an image, into a grid of smaller images (FIG 3A)called view tiles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Al, A2, B1, etc. (or just tiles in the image view server context). These tiles are computed for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`distinct resolutions (FIG 3B) of a given image at the server according to the URL request
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`received from the browser software on the workstation. The use oftiling enables effective
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`image data caching 60 at the image view server and by the browser 10at the client
`
`
`
`workstation.
`
`
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The preferred view tile format is 128 pixel by 128 pixel GIF imagefiles. The GIF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`image file format is preferred because of Web browser compatibility and image file size. The
`
`
`
`GIF imagefile format is the most widely supported format for graphical Web browsers and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`therefore gives the maximum client compatibility for the image view server. The GIF image
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`format has the desirable properties of loss-less image data compression, reasonable data
`
`25
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`compression ratios, color and grayscale support, and a relatively small imagefile header,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`which relates to the selection of view tile size. With a raw image data size for monochrome
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`view tiles of 2,048 bytes and a typical GIF compression of 4 to 1, the compressed data for a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`view tile is approximately 512 bytes. With many imagefile formats, such as TIFF and JPEG,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the image file header (and other overhead information such as data indexes) can be as large or
`
`
`
`30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`larger than the image data itself for small images such as the view tiles; whereas a GIF header
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`WO 99/41675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for a monochrome image addsaslittle as 31 bytes to the GIF imagefile. Alternate view tile
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`formats such as Portable Network Graphics (PNG) maybe used, especially as native browser
`
`
`
`
`
`
`
`
`support for the format becomes common.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The 128 pixel view tile size is a good compromise between viewtile granularity and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`view tile overhead. The view tile granularity of 128 pixels determines the minimum view shift
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`distance (pan distance) that can be achieved with standard graphical Web browserand level 2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`HTMLformatting. 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 allows
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`finer grid for view positioning, but has the problem that the view tile overhead becomes
`
`
`
`
`
`excessive.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A view tile typically represents more or less than 128 x 128 pixels of the imagefile. If
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the view being displayed is reduced 2 to 1, then each viewtile will represent a 256 x 256 pixel
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`area of the image file that has been scaled down to 128 x 128 pixels. For each possible scale
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`factor there is an array oftiles to represent the view. Fixed size view tiling is beneficial
`
`
`
`15
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`because it allows more effective use of the caching mechanism at the server and at the client.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`For example, consider a view of 512 pixels by 512 pixels. Withouttiling, this view is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`composed ofa single GIF file that is displayed by the Web browser, and so if the user asks for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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. With tiling, the first view would cause 16 view
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 browsersince the shifted view will reuse 8 viewtiles that are available from the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Web browser cache. The use oftiling cuts the computation and data transmission in half for
`
`25
`
`
`
`this example.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The use of view tiling 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 surround the most recent view request in anticipation
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a request for a shifted view. When the shifted view is requested, the foreground view
`
`30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`composer can use the pre-computed view tiles and eliminate the time to compute new view
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`
`
`
`
`
`20
`
`
`25
`
`
`30
`
`
`
`WO 99/41675
`
`
`
`
`.
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tiles for the view. For frequently accessed images there is a good chancethat the view tiles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for a view mayalready exist in the view tile cache since the view tile cache maintains the most
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`recently accessed view tiles. 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 accessed view tiles in the case where the maximum storageallocation or
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`minimum storage free space limits are reached.
`
`
`
`
`
`
`
`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 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 comesfrom the imagefile header size as a proportion of the total image file size as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`described above and as data needed to make the viewtile references in the HTMLtextfile.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The network transaction overhead increases with smaller view tiles since each of the view tiles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`requires a network transaction. The increased number of network transactions required with a
`
`
`
`
`
`
`
`
`
`
`
`
`smaller view tile size would slow the response to render a view.
`
`
`
`
`
`
`
`
`
`
`
`The HTMLoutputfile produced by the foreground view composeris passed to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Webserver software to be transmitted to the Web browser. The graphical Web browser
`
`
`
`
`
`
`
`
`
`
`
`
`
`serves as the image viewerby utilizing the HTMLoutput 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 hyperlink for each view tile to be displayed. The viewtiles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`are stored in the GIF imagefile format that can be displayed by all common graphical Web
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`browsers. The Web browserwill retrieve each view tile to be displayed from a local cache if
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the view tile is present, otherwise from the image view server.
`
`
`
`
`
`
`
`
`
`
`
`The request broker 40 takes the raw request from the network server interface 130,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`interprets the request, 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 implemented with the Web server Common
`
`
`
`
`
`
`
`
`
`
`
`
`Gateway Interface (CGI). Options exist to use other direct Application Program Interfaces
`
`
`
`
`
`
`
`
`
`
`
`(API) to the Webserver.
`
`
`
`
`
`To support the tiling and caching of many images on the same image view server, each
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`WO 99/41675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 viewtile
`
`
`
`
`
`
`
`
`
`
`
`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> <TILENUMBER > .GIF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The <SCALE> valueis a 2 character string formed from the base 36 encoding of the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`view scale numberas expressed in parts per 256. The <TILENUMBER> valueis a 5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`character string formed from the base 36 encoding of the tile number as determined by the
`
`
`
`
`formula:
`
`
`
`TILE_NUMBER = TILE_ROW * IMAGETILEWIDTH + TILE_COLUMN
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The TILE_ROW and TILE_COLUMNvaluesstart at 0 for this computation. For
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`example the secondtile of the first row for a view scaled 2:1 would be named under the
`
`
`
`
`preferred protocol:
`
`
`
`V3J00001.GIF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The full URL reference for the secondtile of the first row for image number 22 on the
`
`
`
`
`
`image view server would be:
`
`
`
`
`
`http://hostname/view-tile-cache-path/000022/V3J00001.GIF
`
`
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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> <XMIRROR> <Y_
`
`25
`
`
`
`
`MIRROR> <INVERT > .GIF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VIEW_ANGLEisof the form A< ANGLE>. XMIRROR, Y_MIRROR,and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INVERTare encoded by the single characters X, Y, and I respectively. An example is:
`
`
`
`
`V3J00001A90XYI.GIF
`
`
`
`
`
`
`
`
`
`
`
`
`The Web server 30 is configured to recognize the above-described specially formatted
`
`
`
`30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`request Uniform Resource Locators (URL) to be handled by the image view server request
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`

`

`
`
`
`
`
`
`20
`
`
`25
`
`
`30
`
`
`
`WO 99/41675
`
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`broker 40. This is done by association of the request broker 40 with the URL path or with the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`documentfilename extension.
`
`
`
`The foreground view composer 50 interprets the view request command 140 to
`
`
`
`
`
`
`
`
`
`
`
`
`determine what view needs to be composed. The view request may be absolute 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.
`
`
`
`
`
`
`
`
`
`
`View computation software routine 150 is illustrated in FIG 7 wherein the command
`
`
`
`
`
`
`
`
`
`
`
`
`
`interpreter 151 takes the view request and determines 152 whatscale 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.
`
`
`
`
`
`
`
`
`
`
`
`The view tile generator routine 160 performs the actual creation of the viewtiles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`according to the preferred steps shown in FIG 8. The view tile generator receives information
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`from the view computation as to what view tiles are needed for the view.
`It has access to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`records in the cache 80 that determine which tiles have already been created and are resident
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in the cache.
`If a needed view tile is in the cache then its last access time is updated to prevent
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the cache garbage collector from deleting the view tile. If a needed view tile is not in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cache, then the view tile generator creates the view tile from the image file 90. The view tile
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`generator uses a software imaging library that supports rendering many digital documentfile
`
`
`
`
`
`
`
`
`
`
`
`
`
`formats including monochromeraster images, grayscale raster images, color raster images as
`
`
`
`
`
`
`
`
`
`
`
`
`well as many content rich non-raster formats such as Adobe Portable Document Format
`
`
`
`
`
`
`
`
`
`
`
`
`
`(PDF), PostScript, HPGL, etc. When rendering monochromeimage data the imaging libr