Method and format for storing and selectively retrieving image data

• US 6,137,914 A
• Filed: 08/06/1997
• Issued: 10/24/2000
• Est. Priority Date: 11/08/1995
• Status: Expired due to Term

• Current Assignee: Lite-On Technology Corporation
• Original Assignee: Storm Software, Inc.
• Inventors: Ligtenberg, Adrianus, Starreveld, Adolf Gerard, Gulland, William John
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/908,152
• Time in Patent Office: 1,175 Days
• Field of Search: 382/232, 382/240, 382/305, 382/306
• US Class Current: 382/240
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/162 User input
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/186 the unit being a colour or a chrominance component
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/30 using hierarchical techniques, e.g. scalability H04N19/63 takes precedence
• CPC Class Codes: H04N 19/36 Scalability techniques involving formatting the layers as a function of picture distortion after decoding, e.g. signal-to-noise [SNR] scalability
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/63 using sub-band based transform, e.g. wavelets

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 specific embodiments, the tiles are 64×64 pixels or 128×128 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.

Claims

1. A method of converting a bitmap input image into an image storage format, the method comprising:

at each of a plurality of stages including a first stage and a last stage, subjecting an operand image to a reduction operation to produce a reduced image and complementary image data, the reduced image including low-frequency information from the operand image and having fewer pixels than the operand image, the complementary image data including a portion of data from the operand image not included in the reduced image by the reduction operation;

in the first stage, using the input image as the operand image;

in each stage but the first stage, using the reduced image produced in the previous stage as the operand image, the reduced image produced by the last stage being referred to as the final reduced image;

subdividing at least some of the operand images, the reduced images, and the complementary image data into tiles; and

creating the image storage format, the image storage format comprising a collection of representations of each of the tiles of the operand images and the complementary image data, and an index that enables determination of the respective locations of the representations in the collection.

2. The method of claim 1 wherein:

the reduced image at any given stage has half as many pixels in each dimension as the operand image communicated to the given stage.

3. The method of claim 1 wherein the representation of each of the tiles of the final reduced image is a compressed version of the tile.

4. The method of claim 1, wherein the representation of at least one tile is a version of the tile that has been compressed by a lossy compression technique, and further comprising:

reconstructing the input image tile using the index and at least one tile representation that is a version of the tile that has been compressed by a lossy compression technique to provide a lossy reconstructed input image;

comparing the lossy reconstructed input image with the input image;

determining the complementary image data that, when combined with the lossy reconstructed input image, provides the input image substantially without loss;

compressing the complementary image data; and

including the compressed complementary image date as part of the image storage format.

5. The method of claim 1, wherein subjecting the operand image to a reduction operation comprises:

subjecting the operand image to a low-pass filter in a first direction followed by decimation to provide a first resultant image; and

subjecting the first resultant image to a second low-pass filter in a second direction perpendicular to the first direction followed by decimation to provide the reduced image.

6. The method of claim 1, and further comprising:

for at least a given stage, the reduced image generated at the given stage and the complementary image data are sufficient to reconstruct the operand image to a desired degree of accuracy.

7. The method of claim 6 wherein:

the complementary image data at the given stage includes three pixel arrays commensurate in size with the reduced image generated at the given stage.

8. The method of claim 6 wherein the representation of each of the tiles of the complementary image data is a compressed version of the tile.

9. The method of claim 6 wherein the tiles of the complementary image data are all the same size.

10. The method of claim 6 wherein the tiles of the complementary image data at a given stage are a different size from the tiles of the complementary image data at another stage.

11. The method of claim 6, wherein subjecting the operand image to at least one operation that is different from the low-pass reduction operation comprises:

subjecting the operand image to a low-pass filter in a first direction followed by decimation to provide a first resultant image; and

subjecting the first resultant image to a high-pass filter in a second direction perpendicular to the first direction followed by decimation to provide a portion of the complementary image data.

12. A method of retrieving, at a desired resolution, a desired portion of a bitmap image, the method comprising:

storing the bitmap image in an image storage format, the image storage format including representations of the bitmap image subdivided into tiles at each of a plurality of resolution levels, the image storage format including an index for determining locations of the tile representations at the plurality of resolutions;

accessing the index to determine locations of tile representations of the bitmap image corresponding to the desired portion of the bitmap image at the desired resolution, the tile representations of the bitmap image including a reduced image representation of the bitmap image and at least one complementary image representation of the bitmap image;

retrieving the tile representations from locations determined from the index;

combining the tile representations retrieved to generate the desired portion of the image at the desired resolution.

13. A method of manipulating a bitmap image in a memory of a computer, the image being divided into tiles, the image being available in the form of an image storage format, said image storage format comprising separable information for each tile and an index enabling determination of the location of the separable information for each of the tiles in the image, the method comprising:

(a) loading the index from the image storage format into the memory to create an in-memory version of the index;

(b) creating a data structure in the memory, the data structure having an entry for each tile in the image, the entry for each tile including a valid bit, the valid bits of all tiles initially having a first state;

(c) loading into the memory at least a portion of the image storage format, said portion corresponding to a selected plurality of tiles;

(d) in response to user input specifying the modification of one or more particular tiles in the image, setting the valid bit of each of said one or more particular tiles to a second state different from the first state; and

(e) in response to signals specifying a save operation, determining from the data structure those tiles for which the valid bit is in the second state, and for each such tile for which the valid bit is in the second state,

(i) updating the image storage format to include the separable information of said such tile, and

(ii) updating the index in the image storage format to reflect the new location for the separable information of said such tile;

wherein the separable file information for a given tile includes a thumbnail version of the given tile and one or more high-pass filtered complementary images of the given tile, said complementary images being at different resolutions of said plurality of resolutions so that the given tile can be reconstructed at said any resolution by combining the thumbnail version and at least a selected one of the complementary images.

14. The method of claim 13 wherein:

the separable information for a given tile includes sufficient information to enable the given tile to be reconstructed at any resolution of a plurality of resolutions.