throbber
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 1004
`
`

`
`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 1004
`
`

`
`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 1004
`
`

`
`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 1004
`
`

`
`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 1004
`
`

`
`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 1004
`
`

`
`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 1004
`
`

`
`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 should be un

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket