`lntcmational Bureau
`
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(51) international Patent Classification 5 2
`G06F 15/00
`
`(11) lntemafloml pubfication Number,
`
`W0 99/41675
`
`(43) International Publication Date:
`
`19 August 1999 (1908.99)
`
`(21) International Application Number:
`
`PCT/US98/03017
`
`(22) International Filing Date:
`
`12 February 1998 (1202.98)
`
`(71) Applicant (far 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., lll [US/US]; 2032 Cranberry Isles Way, Apopka. FL
`32712 (US). CRONIN. John, C.
`[US/US]; Apartment 3.
`1804 Greene Street, Philadelphia. PA 19130 (US).
`
`-
`
`(74) Agents: FEIN, Michael, B. et aI.; Suite 3600, 1600 Market
`Street. Philadelphia, PA 19103 (US).
`
`(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, TI‘, 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, Fl, FR. GB, GR, IE, IT,
`LU, MC. NL, PT, SE), OAPI patent (BF, BJ, CF, CG, Cl,
`CM, GA, GN. ML, MR, NE, SN, TD, 'I'G).
`
`Published
`With international search report.
`
`(54) Title: NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT—SERVER, TILING AND CACHING ARCHITECTURE
`
`A"
`client
`i (magma
`.
`
`client
`workstation
`
`(57) Abstract
`
`A computer network server using 1-i'I'I'P
`(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 from the 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 problems that previously ex-
`isted when accessing large image files from a net-
`work file server are eliminated by tiling the image
`view so that computation and transmission of the
`view data can be done in an incremental fashion.
`The vied tiles are cached on the client worksta-
`tion to further reduce network traffic. View tiles
`are cached on the server to reduce the amount to
`view tile computation and to increase responsive-
`ness of the image view sewer.
`
`Network Image View Server
`
`Microsoft Corp. Exhibit 1003
`
`
`
`Albania
`
`Armenia
`
`Austria
`
`Australia
`
`Azerbaijan
`
`Bosnia and Herzegovina
`
`
`
`Barbados
`
`Belgium
`
`Burkina Faso
`
`
`Bulgaria
`
`Benin
`
`Brazil
`
`Belarus
`
`Canada
`
`Central African Republic
`
`
`
`Congo
`
`Switzerland
`
`Cote d‘Ivoire
`
`
`Cameroon
`
`China
`
`Cuba
`
`Czech Republic
`
`
`(‘xennany
`
`Denmark
`
`Estonia
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FOR THE PURPOSES OF INFORMATION ONLY
`
`
`
`
`
`
`
`
`Spain
`
`Finland
`
`France
`
`Gabon
`
`United Kingdom
`
`
`Georgia
`
`Ghana
`
`Guinea
`
`Greece
`
`Hungary
`
`Ireland
`
`Israel
`
`Iceland
`
`Italy
`
`Japan
`
`Kenya
`
`Kyrgyzstan
`
`Democratic Peoples
`
`Republic of Korea
`
`
`
`Republic of Korea
`
`
`
`Kazakstan
`
`Saint Lucia
`
`
`Liechtenstein
`
`Sri Lanka
`
`
`Liberia
`
`
`
`
`LS
`
`
`LU
`
`LV
`
`MC
`
`MD
`
`MG
`
`MK
`
`
`ML
`
`MN
`
`MR
`
`MW
`
`MX
`
`NE
`
`NL
`
`NO
`
`NZ
`
`PL
`
`PT
`
`R0
`
`RU
`
`SD
`
`SE
`
`SG
`
`
`Lesotho
`
`Lithuania
`
`Luxembourg
`
`Latvia
`
`Monaco
`
`Republic of Moldova
`
`
`
`Madagascar
`
`The former Yugoslav
`
`
`
`Republic of Macedonia
`
`
`
`Mali
`
`Mongolia
`
`Mauritania
`
`Malawi
`
`Mexico
`
`Niger
`
`Netherlands
`
`Norway
`
`New Zealand
`
`
`Poland
`
`Portugal
`
`Romania
`
`Russian Federation
`
`Sudan
`
`Sweden
`
`Singapore
`
`
`
`
`Codes used to identify States party to the PCT on the front pages of pamphlets publishing international applications under the PCT.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ES
`
`FI
`
`FR
`
`GA
`
`GB
`
`GE
`
`GH
`
`GN
`
`GR
`
`HU
`
`[E
`
`[L
`
`IS
`
`IT
`
`JP
`
`KE
`
`KG
`
`KP
`
`KR
`
`KZ
`
`LC
`
`
`LK
`
`LR
`
`
`
`
`SI
`
`SK
`
`SN
`
`SZ
`
`TD
`
`TG
`
`TJ
`
`TM
`
`TR
`
`TT
`
`UA
`
`UG
`
`US
`
`UZ
`
`VN
`
`YU
`
`ZW~
`
`
`Slovenia
`
`Slovakia
`
`Senegal
`
`Swaziland
`
`Chad
`
`Togo
`
`Tajikistan
`
`Turkmenistan
`
`Turkey
`
`Trinidad and Tobago
`
`
`
`Ukraine
`
`Uganda
`
`United States of America
`
`
`
`
`Uzbekistan
`
`Vict Nam
`
`
`Yugoslavia
`
`Zimbabwe
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`
`
`
`WO 99141675
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT-SERVER,
`
`
`
`
`TILING AND CACHING ARCHTECTURE
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`
`
`
`W0 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 makes efficient 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 time to 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
`
`
`
`
`WO 99/41675
`
`
`
`workstation.
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`SUMMARY OF 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 image files, 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 image files, 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 HTML code for the resultant
`
`
`
`
`
`
`
`
`
`
`
`view to the client Web browser to 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 image file stored in memory,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`retrieves the digital document image file, composes a grid of view tiles corresponding to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`requested view of the image, computes HTML code for the 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
`
`
`
`
`W0 99/41675
`
`
`
`PCT/U598/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—cornputed 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 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 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 browser is 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
`
`
`
`
`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 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 HTTP protocol 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 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 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 change the resolution of the image. The resultant HTML from this
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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/41575
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The foreground view composer is 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 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, 131, 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 of tiling enables effective
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`image data caching 60 at the image view server and by the browser 10at the client
`
`
`
`workstation.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 image file size. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GIF image file 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`compression ratios, color and grayscale support, and a relatively small image file 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 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 header
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`
`
`
`W0 99/41575
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`for 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 becomes common.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The 128 pixel view tile size is a good compromise between view tile 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 browser and level 2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`HTML formatting. This allows the adjustment of the view position on a 0.64 inch grid when
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Viewing a 200 pixe1—per—inch image at 1 to 1 scale. Reducing the size of the view tiles 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 image file. If
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the view being displayed 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 x 128 pixels. For each possible scale
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`factor there is an array of tiles to represent the view. Fixed size view tiling is beneficial
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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. Without tiling, this View is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`composed of a 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 available from the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Web browser cache. The use of tiling cuts the computation and data transmission in half for
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`composer can use the pre—computed view tiles and eliminate the time to compute new view
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`
`
`W0 99/41675
`
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 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 storage allocation or
`
`
`
`
`
`
`
`
`
`
`minimum storage free space limits are reached.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`
`
`
`10
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 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
`
`15
`
`
`
`
`
`
`
`
`
`
`
`
`
`smaller View tile size would slow the response to render a View.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The HTML output file produced by the foreground View composer is passed to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Web server software 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
`
`
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`data list the size, position and the hyperlink for each view tile to be displayed. The view 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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The request broker 40 takes the raw request from the network server interface 130,
`
`
`
`25
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 Web server.
`
`
`
`30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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/41575
`
`
`
`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 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
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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:
`
`
`
`
`
`
`
`
`
`
`
`
`TILEMNUMBER = TILEMROW * IMAGE_TILE_WIDTI-I + TILE_COLUMN
`
`
`
`
`
`
`
`
`
`
`
`
`
`The TILE_ROW and TILE_COLUMN values start at O for this computation. For
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`example the second tile 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 second tile of the first row for image number 22 on the
`
`
`
`
`
`image View server would be:
`
`
`
`
`
`http://hostname/view~tile—cache-pathMO0OO22/V3J00001 .GIF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 > < TILEMNUMBER > < VIEW_ANGLE > < X_MIRROR > < Y___
`
`
`
`
`
`MIRROR > < INVERT > .GIF
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VIEWMANGLE is of the form A < ANGLE >. X_MIRROR, Y_MIRROR, and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INVERT are encoded by the single characters X, Y, and I respectively. An example is:
`
`
`
`
`V3J00001A9OXYI.GIF
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`Microsoft Corp. Exhibit 1003
`
`Microsoft Corp. Exhibit 1003
`
`
`
`
`W0 99/41675
`
`
`
`
`
`PCT/US98/03017
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`broker 40. This is done by association of the request broker 40 with the URL path or with the
`
`
`
`document filename 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 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
`
`10
`
`
`
`
`
`
`
`
`
`
`
`
`
`generates the view tile 153, resulting in formatted view output 154.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The view tile generator routine 160 performs the actual creation of the View tiles
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`
`
`15
`
`
`
`
`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 document file
`
`
`
`
`
`
`
`
`
`
`
`
`
`formats including monochrome raster images, grayscale raster images, color raster images as
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`well as many content rich non—raster formats such as Adobe Portable Document Format
`
`
`
`
`
`
`
`