PCT
`INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`wo 99/41675
`
`(51) International Patent Classification 6 :
`G06F 15/00
`
`Al
`
`(11) International Publication Number:
`
`(43) International Publication Date:
`
`19 August 1999 (19.08.99)
`
`WORLD INTELLECTUAL PROPERTY ORGANIZATION
`International Bureau
`
`(21) International Application Number:
`
`PCT/US98/030 17
`
`(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., III [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 al.; Suite 3600, 1600 Market
`Street, Philadelphia, P A 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, 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).
`
`Published
`With international search report.
`
`(54) Title: NETWORK IMAGE VIEW SERVER USING EFFICIENT CLIENT-SERVER, TILING AND CACHING ARCHITECTURE
`
`··-ciliiiit-(cid:173)
`. Workstation
`I (Web browser)
`10
`·~ L~~;J..'.U
`
`Client
`Workstation
`(Web browser)
`20
`
`Network
`. - - - - ~-_::_::_::]-- - - - - - - - - - - -
`Network Interface
`(Web server)
`30
`
`--------~
`I
`I
`I
`I
`I
`I
`I
`I
`
`(57) Abstract
`
`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(cid:173)
`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(cid:173)
`age view software are eliminated by using the in(cid:173)
`ternet and industry standards based graphical web
`browsers for the client software. Network and
`system performance problems that previously ex(cid:173)
`isted when accessing large image files from a net(cid:173)
`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(cid:173)
`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(cid:173)
`ness of the image view server.
`
`.. _ ~~:~!
`:
`
`Collector
`70
`
`:
`I
`I
`
`' I
`
`I
`I
`
`;-1.00
`
`I
`
`L-~-· '-•---:
`
`I lcorgt Lt1--~ "''"'::. ""'"'
`View Tile Cache I
`L1
`I
`I
`
`Composer
`60
`
`"
`.
`
`80
`
`-
`
`Background 1
`-~View Composer
`
`,__
`
`80
`
`Document
`Repository
`90
`
`i [
`:. ~ ~··--·-·· :1_ ·-•. ""'· -~ ..... - -.
`
`Network Image View Server
`
`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.
`
`AL
`AM
`AT
`AU
`AZ
`BA
`BB
`BE
`BF
`BG
`BJ
`BR
`BY
`CA
`CF
`CG
`CH
`CI
`CM
`CN
`cu
`cz
`DE
`DK
`EE
`
`Albania
`Annenia
`Austria
`Australia
`Azerbaijan
`Bosnia and Herzegovina
`Barbados
`Belgium
`Burkina Paso
`Bulgaria
`Benin
`Brazil
`Belarus
`Canada
`Central African Republic
`Congo
`Switzerland
`Cbte d'Ivoire
`Cameroon
`China
`Cuba
`Czech Republic
`Gennany
`Denmark
`Estonia
`
`ES
`FI
`FR
`GA
`GB
`GE
`GH
`GN
`GR
`HU
`IE
`IL
`IS
`IT
`JP
`KE
`KG
`KP
`
`KR
`KZ
`LC
`LI
`LK
`LR
`
`Spain
`Finland
`France
`Gabon
`United Kingdom
`Georgia
`Ghana
`Guinea
`Greece
`Hungary
`Ireland
`Israel
`Iceland
`Italy
`Japan
`Kenya
`Kyrgyzstan
`Democratic People's
`Republic of Korea
`Republic of Korea
`Kazakstan
`Saint Lucia
`Liechtenstein
`Sri Lanka
`Liberia
`
`LS
`LT
`LU
`LV
`MC
`MD
`MG
`MK
`
`ML
`MN
`MR
`MW
`MX
`NE
`NL
`NO
`NZ
`PL
`PT
`RO
`RU
`SD
`SE
`SG
`
`Lesotho
`Lithuania
`Luxembourg
`Latvia
`Monaco
`Republic of Moldova
`Madagascar
`The fanner Yugoslav
`Republic of Macedonia
`Mali
`Mongolia
`Mauritania
`Malawi
`Mexico
`Niger
`Netherlands
`Norway
`New Zealand
`Poland
`Portugal
`Romania
`Russian Federation
`Sudan
`Sweden
`Singapore
`
`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
`Viet Narn
`Yugoslavia
`Zimbabwe
`
`Microsoft Corp. Exhibit 1003
`
`

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

`
`wo 99/41675
`
`PCT /US98/03017
`
`5
`
`10
`
`1.
`
`Field of the Invention
`
`BACKGROUND 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
`
`15
`
`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
`
`20 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
`
`25
`
`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
`
`30
`
`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
`
`2
`
`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.
`
`5
`
`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
`
`10
`
`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
`
`15
`
`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
`
`20
`
`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,
`
`25
`
`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
`
`30
`
`description, serve to explain the principles of the invention.
`
`3
`
`Microsoft Corp. Exhibit 1003
`
`

`
`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.
`
`5
`
`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
`
`10
`
`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.
`
`15
`
`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. lOA, lOB, and lOC together constitute a flow diagram for the view tile cache
`
`garbage collector.
`
`20
`
`DETAILED DESCRIPTION OF THE INVENTION AND THE PREFERRED
`EMBODIMENTS
`
`References will now be made in detail to the presently preferred embodiment of the
`
`25
`
`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
`
`30
`
`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.
`
`4
`
`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
`
`5
`
`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
`
`1 o
`
`implemented on a computer, for example a personal computer configured with a processor,
`
`110, 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
`
`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 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
`
`20
`
`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
`
`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.
`
`5
`
`Microsoft Corp. Exhibit 1003
`
`

`
`wo 99/41675
`
`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)
`
`5
`
`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
`
`I o
`
`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
`
`15 A1, 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 of tiling enables effective
`
`image data caching 60 at the image view server and by the browser 1 Oat the client
`
`workstation.
`
`20
`
`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
`
`25
`
`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
`
`30
`
`larger than the image data itself for small images such as the view tiles; whereas a GIF header
`
`6
`
`Microsoft Corp. Exhibit 1003
`
`

`
`wo 99/41675
`
`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
`
`5
`
`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 pixel-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
`
`10
`
`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
`
`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. 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
`
`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 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
`
`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
`
`7
`
`Microsoft Corp. Exhibit 1003
`
`

`
`WO 99/41675
`
`PCTIUS98/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
`
`5
`
`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
`
`1 o
`
`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
`
`8
`
`Microsoft Corp. Exhibit 1003
`
`

`
`wo 99/41675
`
`PCTIUS98/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
`
`5
`
`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
`
`1 o
`
`character string formed from the base 36 encoding of the tile number as determined by the
`
`formula:
`TILE NUMBER = TILE ROW * IMAGE TILE WIDTH + TILE COLUMN
`-
`-
`-
`-
`-
`The TILE_ ROW and TILE_ COLUMN values start at 0 for this computation. For
`
`example the second tile of the first row for a view scaled 2: 1 would be named under the
`
`15
`
`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: I /hostname/view-tile-cache-path/000022/V3JOOOO 1. 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, viewy-mirror, invert view. A view tile name with these extra
`
`view attributes can be encoded as:
`
`V <SCALE> <TILE NUMBER> <VIEW ANGLE> <X MIRROR> < Y
`-
`-
`
`25 MIRROR> <INVERT> .GIF
`
`VIEW ANGLE 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:
`
`V3JOOOO 1A90XYI. 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
`
`9
`
`Microsoft Corp. Exhibit 1003
`
`

`
`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
`
`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
`
`5
`
`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
`
`(PDF), PostScript, HPGL, etc. When rendering monochrome image data the imaging library
`
`scale-to-gray scaling is used to provide a more visually appealing rendition of the reduced
`
`image.
`
`For example, a specific view request might include tiles B2, C2, B3, and C3 (FIG 4A
`
`25
`
`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 that the client retains in a cache the other tiles. If the client does not cache then tiles
`
`A2, A3, B2, and B3 are sent.
`
`Formatted output is created 170 to reference the view tiles needed to display the
`
`30
`
`completed view. The formatted output uses HTML to describe the order, position and
`
`10
`
`Microsoft Corp. Exhibit 1003
`
`

`
`wo 99/41675
`
`PCT/US98/0301 7
`
`hyperlink for each view tile to be displayed. The output formatter applies another
`
`optimization by detecting white view tiles and replacing the hyperlink for the image specific
`
`white tile with a common white tile reference. This eliminates transmission of all but one
`
`white tile and eliminates the need to transmit any white tiles once the common white tile is
`
`5
`
`cached by the Web browser.
`
`The foreground view composer 50 controls the background view composer 80 by
`
`stopping it when a foreground view is being composed and then starting it with information
`
`about the newest view, once the new view has been composed 180.
`
`Preferably, the background view composer 80 is programmed to optimize performance
`
`10
`
`of the system by pre-computing, i.e., composing, view tiles that may be needed between view
`
`requests to the server. The tiles to be pre-computed are the tiles surrounding the most recent
`
`view and with the same scale as the most recent view. The order of view tile pre-computation
`
`is a clock-wise spiral out from the most recent view. The number of view tiles pre-computed
`
`around a view are preferably limited by a system configuration parameter to prevent useless
`
`15
`
`creation of view tiles that may never be needed. Once the maximum number of pre-computed
`
`view tiles is reached for the most recent view scale, the pre-computation can proceed for
`
`alternate view scales. The background view composer preferably is programmed to work at a
`
`low priority to minimize interference with more critical system tasks.
`
`FIG 6A illustrates how the background view composer algorithm works. Assuming
`
`20
`
`that for a given view requested by the client, tiles C3, C4, D3 and D4 are delivered, after
`
`those tile are delivered to the Web browser, the background view composer routine within the
`
`server program creates the tiles around these tiles, starting at E4, by composing or computing
`
`such surrounding tiles. As long as the client continues to view this page at this scale factor,
`
`the server will compute view tiles expanding outward from the tiles requested last. FIG 6B
`
`25
`
`illustrates another request made by a client, after the two rotations of tiles were generated.
`
`The request asked for tiles G3, G4, H3, and H4. When the tile pre-computation begins for
`
`this request it will create tiles G5, H5, 15, 14, 13, 12, H2, and G2 in the first rotation, but it
`
`will not attempt to create tiles in the F column.
`
`Preferably a view tile cache garbage collector algorithm 70 manages the use of the
`
`30
`
`storage for view tiles (FIGS lOA, lOB, lOC). The garbage collector maintains the view tile
`
`11
`
`Microsoft Corp. Exhibit 1003
`
`

`
`wo 99/41675
`
`PCT/US98/03017
`
`cache 60 (FIG. 1) to keep the view tile cache storage usage below a storage limit and to keep
`
`the storage free space above a free space limit. The garbage collector constantly scans the
`
`cache to accumulate size and age statistics for the view tiles. When the cache size needs to be
`
`reduced, the garbage collector selects the least recently accessed view tiles for deletion until
`
`5
`
`the cache size is within limits. The garbage collector runs at a low priority to minimize
`
`interference with more critical system tasks. The storage free space limit is designed as a fail(cid:173)
`
`safe limit to prevent the system from running out of storage. The free space limit is checked
`
`on a periodic basis and if it is exceeded the garbage collector becomes a critical system task
`
`and runs at a high priority until the storage free space is greater than the free space limit.
`
`1 o
`
`Digital document files may be stored on the web server or on another server within the
`
`network. The image files are typically managed as digital documents with attribute
`
`information that is stored with the documents in the document repository 90. A digital
`
`document management system can run independently or in conjunction with the image view
`
`server software. The digital document file may be a raster image file or a non-raster document
`
`15
`
`file. If the digital document file is a non-raster format then it is rendered as a monochrome,
`
`grayscale, or color raster image for viewing.
`
`The graphical Web browser on the client workstation 10 receives HTML data from the
`
`image view server 210 that contains hyper links to the view tiles within the view tile cache 60
`
`to be displayed and formatting that describes the layout of the of the tiles to form the image
`
`20
`
`view. The Web browser initially must fetch each view tile 220 for a view from the view
`
`server. After the initial view, whenever a view overlaps with a previous view at the same
`
`scale, the Web browser preferably retrieves view tiles that have been previously displayed
`
`from the Web browser's local cache 210 rather than from the server.
`
`Performance and usability of document viewing can be increased by using progressive
`
`25
`
`display of tiled images. By using an image file format that allows a rough view of the image
`
`to be displayed while the remainder of the image content is downloaded, a rough view of the
`
`document can be seen more quickly.
`
`Since most Web browsers can only transfer 1 to 4 GIF images at a time, usually not all
`
`of the view tiles in the view array can be progressively displayed at the same time. Therefore,
`
`30
`
`it is preferred that to implement progressive display, algorithms at the client are provided to
`
`12
`
`Microsoft Corp. Exhibit 1003
`
`

`
`wo 99/41675
`
`PCT/US98/0301 7
`
`accept an alternate data format that would allow the whole document viewing area screen to
`
`take advantage of the progressive display while still taking advantage of the benefits o