United States Patent [19]
`Ligtenberg et al.
`
`1111111111111111~1111111111111111111111111111111111111111111111
`US005682441A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,682,441
`Oct. 28, 1997
`
`[54] METHOD AND FORMAT FOR STORING
`AND SELECTIVELY RETRIEVING IMAGE
`DATA
`
`[75]
`
`Inventors: Adrianus Ligtenberg, Palo Alto; Adolf
`Gerard Starreveld; William John
`Gulland, both of Mountain View, all of
`Calif.
`
`[73] Assignee: Storm Tecbnology, Inc., Mountain
`View, Calif.
`
`[21] Appl. No.: 554,384
`
`Nov. 8, 1995
`
`[22] Filed:
`Int. CI.6
`•••••••••••••••••••••••••••••••• G06K 9/36; G06K 9/46
`[51]
`[52] U.S. CI ............................ 382/232; 382/240; 382/264
`[58] Field of Search ..................................... 382/240, 232,
`382/264
`
`[56]
`
`References Cited
`
`U.S. PATENf DOCUMENTS
`
`4,943,855
`5,048,111
`5,333,212
`5,384,869
`5,434,953
`
`7/1990 Bheda et al ............................. 358/133
`9/1991 Jones et al ................................ 382/56
`7/1994 Iigtenberg ................................ 382/56
`1/1995 Wilkinson et al. . ....................•. 382/56
`7/1995 Bloomberg .............................. 3821298
`
`Primary Examiner-Andrew Johns
`Assistant Examiner-Monica S. Davis
`Attome)\ Agent, or Firm-Townsend and Townsend and
`Crew LLP
`
`[57]
`
`ABSTRACT
`
`A method of processing an input image for storage includes
`decomposing the input image into a number of images at
`various resolutions, subdividing at least some of these
`images into tiles (rectangular arrays) and storing a block
`(referred to as the "tile block") representing each of the tiles,
`along with an index that specifies the respective locations of
`the tile blocks. In speciiic embodiments, the tiles are 64x64
`pixels or 128x128 pixels. The representations of the tiles are
`typically compressed versions of the tiles. In a specific
`embodiment, JPEG compression is used. In a specific
`embodiment, an operand image is recursively decomposed
`to produce a reduced image and a set of additional (or
`complementary) pixel data. At the first stage, the operand
`image is normally the input image, and, for each subsequent
`stage, the operand image is the reduced image from the
`previous stage. At each stage, the reduced image is at a
`characteristic resolution that is lower than the resolution of
`the operand image. The processing is typically carried out
`until the resulting reduced image is of a desired small size.
`
`34 Claims, 3 Drawing Sheets
`
`SUBSEQUENT PASSES:
`REDUCED I MAGE IN
`
`FIRST PASS:
`INPUT IMAGE IN
`
`50
`
`IMAGE DECOMPOSITION:
`PRODUCE REDUCED LOW(cid:173)
`PASS FILTERED IMAGE AND
`COMPLEMENTARY IMAGE(S)
`
`COMPLEMENTARY
`IMAGE(S) OUT
`
`65
`
`YES
`
`DIVIDE FINAL REDUCED
`IMAGE (THUMBNAIL)
`AND COMPLEMENTARY
`IMAGES INTO TILES
`
`60
`COMMUNICATE REDUCED
`IMAGE FOR FURTHER
`DECOMPOSITION
`
`COMPRESS TILES
`
`BUILD LOSSLESS COMPONENT
`
`BUILD INDEX AND STORE FILE
`
`72
`
`75
`
`Microsoft Corp. Exhibit 1005
`
`

`

`U.S. Patent
`
`Oct. 28, 1997
`
`Sheet 1 of 3
`
`5,682,441
`
`r _____________________________________ c2~1
`
`I
`
`46
`
`47
`
`48
`
`I
`I
`I
`
`CD-ROM
`~------ ------------ -------------------~
`
`I
`
`~--- --
`
`I
`
`·------------- _,
`
`I ----------------------- -----------1
`
`1
`
`'-10
`
`FIG. 1 (PRIOR ART)
`
`SUBSEQUENT PASSES:
`REDUCED IMAGE IN
`
`FIRST PASS:
`INPUT IMAGE IN
`
`50
`
`IMAGE DECOMPOSITION:
`PRODUCE REDUCED LOW(cid:173)
`PASS FILTERED IMAGE AND
`COMPLEMENTARY IMAGE(S)
`
`COMPLEMENTARY
`IMAGE(S) OUT
`
`65
`
`YES
`
`DIVIDE FINAL REDUCED
`IMAGE (THUMBNAIL)
`AND COMPLEMENTARY
`IMAGES INTO TILES
`
`60
`COMMUNICATE REDUCED
`IMAGE FOR FURTHER
`DECOMPOSITION
`
`COMPRESS TILES
`
`BUILD LOSSLESS COMPONENT
`
`BUILD INDEX AND STORE FILE
`
`FIG. 2
`
`Microsoft Corp. Exhibit 1005
`
`

`

`U.S. Patent
`
`Oct. 28, 1997
`
`Sheet 2 of 3
`
`5,682,441
`
`OPERAND
`IMAGE IN - - - - , . - - - - - - - - - - - - - - ,
`
`REDUCED
`IMAGE OUT
`50/
`
`"'.(
`COMPLEMENTARY IMAGES OUT
`FIG. 3
`
`SUBSEQUENT PASSES:
`EXPANDED IMAGE IN
`
`FIRST PASS:
`THUMBNAIL IMAGE IN
`
`120
`IMAGE RECONSTRUCTION:
`PRODUCE EXPANDED
`IMAGE
`
`COMPLEMENTARY
`IMAGE(S) IN
`
`FINAL EXPANDED
`YES
`IMAGE OUT
`>--__.;._~
`
`NO
`
`130
`COMMUNICATE EXPANDED
`IMAGE FOR FURTHER
`RECONSTRUCTION
`
`FIG. 4
`
`Microsoft Corp. Exhibit 1005
`
`

`

`U.S. Patent
`
`Oct. 28, 1997
`
`Sheet 3 of 3
`
`5,682,441
`
`OPERAND
`IMAGE IN
`
`COMPLEMENTARY IMAGES IN
`--------------~--------------
`
`EXPANDED
`r--~ IMAGE OUT
`
`120_/
`
`FIG. 5
`
`Microsoft Corp. Exhibit 1005
`
`

`

`5,682,441
`
`1
`METHODANDFORMATFORSTOmNG
`AND SELECTIVELY RETRIEVING IMAGE
`DATA
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`2
`different resolutions. The pyramid allows the user to select
`an image resolution that is the most effective for a certain
`task For example, to browse a number of images, one views
`the thumbnail images (highly reduced images that are on the
`5 order of an inch or two on a side when displayed). The basic
`features of the image can be discerned, and a selected image
`can then be retrieved at a screen resolution for viewing or at
`a higher print resolution suitable for printing.
`Although the above solutions have been successful in
`10 addressing . some of the obstacles standing in the way of
`using images on the computer, the solutions are not without
`their drawbacks. For example, JPEG compression, while it
`reduces the file size, does not allow selective reconstruction
`of a desired portion of the image. Rather, it is necessary to
`15 reconstruct all portions of the image between the top left of
`the image and the bottom right of the desired portion.
`Furthermore, while the tilebased virtual memory schemes
`alleviate the memory requirements, they do not reduce the
`file size. Additionally, an image stored in the PhotoCD
`format is so large that it is only used on PhotoCDs. The
`format is not practical as a format for on-line storage and
`retrieval or for storage on a local hard disk
`
`35
`
`40
`
`The present invention relates generally to storing and
`retrieving image data, and more specifically to a file format
`that provides selective retrieval for display, printing, or
`communication purposes.
`It is said that a picture is worth a thousand words, and 20
`history bears this out. From cave men drawing pictures on
`the walls of their caves to modern-day students accessing
`multimedia encyclopedias, people have always considered
`SUMMARY OF THE INVENTION
`pictorial information an essential communication tool.
`Recent advances in· computer technology have made it 25
`The present invention provides an effective and flexible
`possible to create and exchange elaborate documents in
`image data format and techniques for selectively storing and
`retrieving image data. A storage format according to the
`electronic form. Text and graphics (line art) are easily
`invention allows desired portions of the image data to be
`formatted and manipulated, allowing an amateur computer
`retrieved at desired resolution.
`user to create highly professional documents. The logical
`next step is the incorporation of photographs and other 30
`In brief, a method of processing an input image for
`storage includes decomposing the input image into a number
`bitmap images into documents.
`of images at various resolutions, subdividing at least some
`While the technology exists to digitize and edit
`photographs, a persistent problem is that bitmap images are
`of these images into tiles (rectangular arrays) and storing a
`block (referred to as the "tile block") representing each of
`very large. For example, an 8x10 inch color photograph
`the tiles, along with an index that specifies the respective
`scanned at 300 dpi (dots/inch) at 24 bits/pixel represents
`over 20 megabytes of data, and this is hardly an extreme
`locations of the tile blocks. The representations of the tiles
`example. Thus, in the context of a local computer, acquiring,
`are typically compressed versions of the tiles. In a specific
`embodiment, JPEG compression is used.
`viewing, manipulating, and printing such images are pain-
`fully slow processes, even with state-of-the-art computer
`In a specific embodiment, an operand image is iteratively
`decomposed to produce a reduced image at a lower resolu-
`equipment. The problem is aggravated when it is desired to
`tion and a set of additional (or complementary) pixel data
`transfer these images over a network.
`At the first stage, the operand image is normally the input
`Fortunately, the bitmap representation of most photo-
`graphs includes a large amount of repetitive information
`image, and, for each subsequent stage, the operand image is
`making the images amenable to image compression 45 the reduced image from the previous stage. The additional
`schemes. An international compression standard called
`pixel data produced at a given stage can be considered to
`JPEG, which allows pictures to be stored in about Vlo the
`have the same characteristic resolution as the reduced image
`space with high quality, has been developed and adopted.
`produced at that stage. The reduced image and the additional
`Greater levels of compression can be achieved, but the
`pixel data at a given resolution are sometimes referred to as
`quality of the reconstructed image is lower. While it is 50 a layer.
`possible to achieve lossless compression, the compression
`The processing is typically carried out until the resulting
`factor would only be on the order of 4x. A discussion of the
`reduced image is of a desired small size. This is typically a
`JPEG compression, as well as a number of enhancements
`size that represents the smallest image that is useful for
`thereto, can be found in U.S. Pat. No. 5,333,212 to
`display. In a specific embodiment, this is an image between
`ligtenberg, the entire disclosure (including appendices) of 55 80 and 160 pixels on a side, referred to as a thumbnail.
`The reduction performed at each stage is of a type that
`which is incorporated by reference for all purposes.
`retains the basic appearance of the operand image. In a
`There have been developed image editing programs that
`incorporate virtual memory schemes specially tailored to
`specific embodiment, the reduced image is obtained by
`images. In these schemes, the images are divided into tiles
`subjecting the operand image to horizontal and vertical
`(rectangular image regions). The advantage of tiles is that 60 low-pass filters followed by decimation. In a specific
`embodiment, the reduction is by a factor of 2 in each
`image data can be retrieved for only those tiles that will be
`displayed, and operations can be performed locally.
`dimension.
`Another problem is where an image needs to be accessed
`The additional pixel data contains at least some of the
`at different resolutions. For example, an image might be
`information lost in the reduction of the operand image. This
`displayed actual size at 72 dpi but printed at 300 or 600 dpi. 65 allows the operand image to be reconstructed to a desired
`degree by suitably combining the reduced image and the
`A solution to this problem is known as pyramid coding, such
`as in Kodak's PhotoCD format. where the image is stored at
`additional pixel data. If the additional pixel data allows
`
`Microsoft Corp. Exhibit 1005
`
`

`

`5,682,441
`
`3
`faithful reconstruction of the operand image, the reduced
`images (other than the thumbnail) are redundant, and it is not
`necessary to store them in the file. That is, a given layer may
`only need to contain the additional pixel data at that layer's
`resolution. However, in some embodiments, the reduced 5
`images are included in the file to allow direct access and to
`eliminate or reduce the computational resource needed to
`reconstruct the reduced image.
`In a specific embodiment, the additional pixel data com(cid:173)
`prises a set of complementary images, which are produced 10
`by subjecting the operand image to each of three series of
`filtering operations: a horizontal low-pass filter and a verti-
`cal high-pass filter; a horizontal high-pass filter and a
`vertical low-pass filter; and a horizontal high-pass filter and
`a vertical high-pass filter. Each of the three resulting filtered 15
`images is decimated.
`Any desired portion of the image file, can be retrieved and
`reconstructed at a desired one of the resolutions that char(cid:173)
`acterize the reduced images that were generated during the
`decomposition process. If a particular reduced image is
`stored in the file. its relevant tile blocks can be retrieved
`directly. If the final reduced image is the only reduced image
`actually stored in the file, the reduced image will typically
`need to be reconstructed. This is done, in essence, by
`reversing the decomposition process used to create the file.
`In a specific embodiment, the relevant tile blocks of the
`final reduced image and of the complementary images at the
`final stage are retrieved, decompressed (if necessary),
`upsampled, and combined. This produces an expanded
`image that is an approximation to the reduced (operand)
`image that was input to the last stage of the decomposition
`process. The faithfulness of the reconstruction depends on
`the lossiness of the compression that was done on the tiles,
`and on the degree to which the complementary image
`process preserves pixel values.
`This process is iterated by combining the reconstructed
`image with the relevant portions of the complementary
`images having the same resolution as the reconstructed
`image. The iterations stop when an image of the desired
`resolution is achieved. This may be the original input image,
`or an image at some intermediate resolution. If a lossy
`compression scheme is used, it is also possible to store in the
`file additional tiled information that represents the difference
`between the input image, and the reconstructed image at the
`input image's resolution. This information could be loss(cid:173)
`lessly compressed.
`The present invention also provides efficient techniques
`for modifying images in memory and updating the file to
`incorporate the modifications. When a portion of the image 50
`is retrieved from the file and brought into memory, a table
`is created in memory containing index information regard(cid:173)
`ing the tile blocks in the file. The table includes a ''valid" bit
`for each tile block. The valid bit is initially set to a state
`designating that the tile has not been modified in memory 55
`and therefore corresponds to what is currently in the file.
`If a portion of the image is modified, the tile blocks that
`include the modified portion are marked "invalid," signify(cid:173)
`ing that the mapped tiles stored in the disk file no longer
`correspond to what is in memory. When it is desired to save 60
`the modification, the tile blocks for the modified tiles are
`written to the file, preferably at the end of the file, and the
`index in the file is modified to reflect the new locations of the
`modified tile blocks.
`A further understanding of the nature and advantages of 65
`the present invention may be realized by reference to the
`remaining portions of the specification and the drawings.
`
`4
`BRIEF DESCRIPTION OF THE DRAWINGS
`.FIG. 1 is a block diagram of a system in which the present
`invention may be embodied;
`FIG. 2 is a high-level flow diagram showing the conver(cid:173)
`sion of an input image to a file according to the present
`invention;
`FIG. 3 is an expanded flow diagram illustrating steps
`iteratively performed during image decomposition;
`FIG. 4 is a is a high-level flow diagram showing the
`retrieval and reconstruction of an image stored in a file
`according to the present invention; and
`FIG. 5 is an expanded flow diagram illustrating steps
`iteratively performed during image reconstruction.
`SYSTEM OVERVIEW
`FIG. 1 is a simplified block diagram of a computer system
`10 in which the present invention may be embodied. The
`computer system configuration illustrated at this high level
`is standard, and as such, FIG. 1 is labeled ''Prior Art". A
`20 computer system such as system 10, suitably programmed to
`embody the present invention, however, is not prior art. The
`specific embodiments of the invention are embodied in a
`general purpose computer system such as shown in FIG. 1,
`and the remaining description will generally assume that
`25 environment. However, the invention may be embodied in
`dedicated photo input and output devices such as digital
`cameras, set-top boxes, and printers.
`In accordance with known practice, the computer system
`30 includes a processor 12 that communicates with a number of
`peripheral devices via a bus subsystem 15. These peripheral
`devices typically include a memory subsystem 17, a user
`input facility 20, a display subsystem 22, output devices
`such as a printer 23, and a file storage system 25.
`In this context, the term "bus subsystem" is used generi-
`cally so as to include any mechanism for letting the various
`components of the system communicate with each other as
`intended. With the exception of the input devices and the
`display, the other components need not be at the same
`40 physical location. Thus, for example, portions of the file
`storage system could be connected via various local-area or
`wide-area network media, including telephone lines.
`Similarly, the input devices and display need not be at the
`same location as the processor, although it is anticipated that
`45 the present invention will most often be implemented in the
`context of PCs and workstations.
`Bus subsystem 15 is shown schematically as a single bus,
`but a typical system has a number of buses such as a local
`bus and one or more expansion buses (e.g., ADB, SCSI, ISA,
`EISA, MCA, NuSus, or PCI), as well as serial and parallel
`ports. Network connections are usually established through
`a device such as a network adapter on one of these expansion
`buses or a modem on a serial port. The computer system may
`be a desktop system or a portable system.
`Memory subsystem 17 includes a number of memories
`including a main random access memory (RAM) 30 and a
`read only memory (ROM) 32 in which fixed instructions are
`stored. In the case of Macintosh-compatible personal com(cid:173)
`puters this would include portions of the operating system;
`in the case of IBM-compatible personal computers, this
`would include the BIOS (basic input/output system).
`User input facility 20 typically includes a keyboard 40
`and may further include a pointing device 42 and a scanner
`43. The pointing device may be an indirect pointing device
`such as a mouse, trackball, touchpad, or graphics tablet, or
`a direct pointing device such as a touchscreen incorporated
`into the display.
`
`35
`
`Microsoft Corp. Exhibit 1005
`
`

`

`5,682,441
`
`5
`Display subsystem 22 typically includes a display con(cid:173)
`troller 44 and a display device 45 coupled to the controller.
`The display device may be a cathode ray tube (CRT), a
`fiat-panel device such as a liquid crystal display (LCD), or
`a projection device. Display controller provides control
`signals to the display device and normally includes a display
`memory (not shown in the figure) for storing the pixels that
`appear on the display device.
`The file storage system provides persistent (non-volatile)
`storage for program and data files, and typically includes at
`one hard disk drive 46 and at least one floppy disk drive 47.
`There may also be other devices such as a CD-ROM drive
`48 and optical drives. Additionally, the system may include
`hard drives of the type with removable media cartridges. As
`noted above, one or more of the drives may be located at a
`remote location, such as in a server on a local area network
`or at a site on the Internet's World Wide Web.
`
`File Creation and Format
`FIG. 2 is an overall flow diagram showing the conversion
`of an input image to a file having the file format according
`to an embodiment of the present invention. The file format
`stores sufficient information to allow access to desired
`portions of an original bitmap input image at a variety of
`resolutions, depending on the task at hand. The file format
`is referred to as an active file format since the user can
`interact with the file and the file provides what the user
`needs.
`In the specific embodiment described below, the file is
`constructed with a view to eliminating redundant informa(cid:173)
`tion so as to produce a smaller file. The trade-off is that it is
`necessary to reconstruct the image at a given resolution on
`the basis of information retrieved from the file.
`The process of constructing the file is iterative in the sense
`that in a first pass the input image is subjected to an image
`decomposition stage 50, and in subsequent passes, a portion
`of the data resulting from stage 50 is again input to stage 50.
`The input image to stage 50 is referred to generically as the
`operand image. The operation of stage 50 is to produce a
`reduced image at a lower resolution than the operand image,
`and additional image components containing a desired level
`of the information that was discarded in producing the
`reduced image. These additional image components are
`referred to as additional pixel data or as the "complementary
`images". In a specific embodiment. the operations in stage
`50 include filtering and decimation by a factor of two.
`The reduced image and complementary images produced
`at each stage have a characteristic resolution and can be
`thought of as a layer of the image. In the specific
`embodiment, the reduced image is not stored as part of the
`file since it can be reconstructed from information in sub(cid:173)
`sequently generated layers.
`When the operand image has been processed, resulting in
`a reduced image and complementary images, the comple(cid:173)
`mentary images are output from stage 50 for further pro(cid:173)
`cessing and storage as will be described below. The system
`tests (step 55) whether there is need for another iteration.
`The method can be iterated any desired number of times, but
`in a specific embodiment, the test is whether the reduced
`image has a size below a threshold, which in the specific
`embodiment is that each dimension of the reduced image be
`between 80 and 160 pixels. Clearly, the necessary number of
`iterations can be readily determined ahead of time from the
`size of the input image.
`If the reduced image is not sufficiently small, the reduced
`image is communicated to stage 50 as the operand image
`
`30
`
`6
`(step 60). If the reduced image is sufficiently small, further
`processing by stage 50 is not required. At this point, the
`reduced image, referred to as the "final reduced image" or
`the ''thumbnail" is output for further processing and storage
`5 along with the complementary images, which were output at
`each stage.
`The thumbnail and the complementary images (and the
`other reduced images if they are to be stored as part of the
`file) are divided into tiles (step 65) to allow subsequent
`10 retrieval and reconstruction of desired portions of the image
`at desired resolutions. The individual tiles are compressed
`(step 70), although compression is not a necessary part of the
`invention. Compression, if it is used, is one possible mecha(cid:173)
`nism that can cause loss of information. Although there are
`15 lossless compression techniques, the specific embodiment
`uses JPEG compression, which is a lossy technique.
`Another possible source of information loss is the pro(cid:173)
`cessing within stage 50. The reduced image output from
`stage 50, by definition, contains only a portion of the
`20 operand image that was input to stage 50. The degree to
`which the operand image can be reconstructed depends on
`the nature of the complementary image generation. The
`complementary images may contain all the information to
`allow such reconstruction if desired, but there may be some
`25 applications where there is no need to reconstruct any of the
`intermediate resolution images losslessly. It may, however,
`be desired to be able to reconstruct the original input image
`losslessly.
`If it is required to provide lossless reconstruction, the
`compressed tiles are subjected to processing (step 72) to
`build a lossless component for storage in the file. This may
`entail reconstruction of the image at full resolution, subtrac(cid:173)
`tion from the original input image, and generation of data
`35 representing the difference image. The latter would be tiled
`and losslessly compressed.
`The file comprises individual blocks for each of the tiles
`produced at tiling step 65, as well as an index to all these
`blocks. If compression is used, the block would store the
`40 compressed data produced at compression step 70. These
`blocks are sometimes referred to as ''tile blocks". If step 72
`is performed, the index would also refer to the lossless
`information component. The construction of the index and
`storing of the file is shown as step 75,-performed after all the
`45 processing described above.
`As mentioned above, the file includes an index that
`contains the locations (offsets in file) of all the tile blocks.
`In embodiments where each tile is compressed, the tile
`blocks are of unequal length, and so it is also necessary to
`so store the length of each tile block as well as the tile block's
`offset in the file. The lengths of the tile blocks can be stored
`in the index or as part of the tile blocks themselves. Where
`compression is not used, or where a compression regime that
`compresses to a fixed size is used (see, for example, the
`55 above mentioned U.S. Pat. No. 5,333,212), the tile blocks
`are all of equal length in a given layer, and there is no need
`to store the individual lengths of the tile blocks. If, as in
`some alternative embodiments, it is desired to store one or
`more of the intermediate reduced images themselves, the
`60 index would need to store the locations of the tile blocks for
`these reduced images.
`The choice of tile size is subject to a number of design
`considerations. Since a given image is unlikely to have
`dimensions that are exact multiples of the tile dimension,
`65 smaller tiles will reduce wasted storage of blank space along
`the bottom and right edges of the image. Further, since users
`will generally be unaware of tile boundaries when specify-
`
`Microsoft Corp. Exhibit 1005
`
`

`

`5,682,441
`
`25
`
`30
`
`20
`
`7
`ing regions for reconstruction, smaller tiles will reduce the
`amount of unwanted image portions that are reconstructed.
`On the other hand, larger tiles reduce the number of J/0
`operations for retrieval and storage. Larger tiles also result
`in a smaller index, which is not a major issue for storage, but 5
`can be significant for memory since the entire index is likely
`to be in memory.
`In general, the number of pixels on a side should be a
`power of 2 for ease in computing and associating corre(cid:173)
`sponding tiles in different layers (assuming a 2xreduction at 10
`each stage), and square tiles are generally preferred. There
`is no fundamental reason why the tile size should be the
`same for all layers, and in some embodiments it may be
`advantageous to have the tiles progressively smaller so that
`a single tile in one layer will correspond to a single (smaller)
`tile in the next reduced layer. Furthermore, a particular size 15
`may optimize J/0 or memory operations for a frequently
`used layer. However in most of the discussion that follows,
`a fixed tile size will be assumed. In a current
`implementation, a tile size of 128xl28 pixels is used, but a
`tile size of 64x64 pixels is another likely choice.
`Depending on the tile size and the number of stages of
`reduction, the reduced image and its complementary images
`at some stage (for example, the thumbnail stage) may fit
`within a single tile. In such a case, reference to dividing a
`particular image into tiles should be interpreted to include
`the possibility that the image has been sufficiently reduced
`so that it fits within a single tile. The benefits of tiling will
`be realized, however. as long as at least some of the layers
`are divided into a plurality of tiles.
`The above description of the method of processing oper(cid:173)
`and images in terms of producing a number of resulting
`images. tiling and compressing the resulting images, build(cid:173)
`ing the index of tile blocks, and storing the file accurately
`represents the operations that are performed. It should be 35
`realized, however, that this is a high-level view of the
`method. In actual implementations, the steps are likely to be
`subdivided and interleaved, producing compressed tiles and
`corresponding index information incrementally as process(cid:173)
`ing proceeds.
`One possible approach is to process portions of the input
`image to completion before processing other portions. For
`example. if there are to be two levels of reduction. 16 tiles
`of the input image map to a single tile of the thumbnail and
`each group of 16 tiles would be processed fully as follows. 45
`In the first stage. each of four subgroups of four tiles from
`the input image produces a single reduced tile and three
`complementary tiles, the latter of which can be compressed,
`indexed. and stored immediately. The four tiles of the
`reduced image produce a single tile of the thumbnail and 50
`three complementary tiles, all of which can be compressed,
`indexed. and stored immediately. At this point, the com(cid:173)
`pressed tiles from the two stages of processing can be used
`to reconstruct 16 tiles at the resolution of the input image,
`and the lossless component for the 16 input tiles can be 55
`constructed, compressed losslessly, indexed, and stored.
`FIG. 3 is an expanded flow diagram illustrating steps
`performed in a specific embodiment of image decomposition
`stage 50. In brief, the reduced image and the three comple(cid:173)
`mentary images are obtained by subjecting the operand 60
`image to four combinations of filtering and decimation
`operations. The technique, outlined below, is described for
`use in a different context in U.S. Pat No. 4,943,855 to Bheda
`et al., the entire disclosure of which is incorporated by
`reference for all purposes.
`In the specific embodiment. the operand image is sub(cid:173)
`jected to a horizontal low-pass filter applied to each row
`
`8
`(step 80) followed by a decimation of every other column
`(step 82), to produce a first intermediate image. The operand
`image is separately subjected to a horizontal high-pass filter
`applied to each row (step 85) followed by a decimation of
`every other column (step 87), to produce a second interme(cid:173)
`diate image. Each intermediate image is then subjected
`separately to two additional sets of operations. In the specific
`embodiment, the filters are finite impulse response (FIR)
`filters. For example, the low-pass filters may have coeffi(cid:173)
`cients (1, 1) or (1, 3, 3, 1) while the high-pass filters may
`have coefficients (1, -1) or (1, 3, -3, -1)
`The first intermediate image is subjected to a vertical
`low-pass filter applied to each column (step 90) followed by
`a decimation of every other row (step 92), to produce the
`reduced image, also referred to as the low-low image. The
`first intermediate image is separately subjected to a vertical
`high-pass filter applied to each column (step 95) followed by
`a decimation of every other row (step 97), to produce a first
`complementary image, also referred to as the low-high
`image.
`The second intermediate image is subjected to a vertical
`low-pass filter applied to each column (step 100) followed
`by a decimation of every other row (step 102), to produce a
`second complementary image, also referred to as the high(cid:173)
`low image. The second intermediate image is separately
`subjected to a vertical high-pass filter applied to each
`column (step 105) followed by a decimation of every other
`row (step 107), to produce a third complementary image.
`also referred to as the high-high image.
`
`40
`
`Image Reconstruction
`FIG. 4 is an overall flow diagram showing the retrieval
`and reconstruction of an image from a file having the file
`format described above. Since the thumbnail and the
`complementary images at each stage in the image decom-
`position were tiled, it is possible to selectively reconstruct a
`desired portion of the image. While the discussion that
`follows will typically refer to retrieving a particular image,
`it shoul