Method and apparatus for compression and decompression of digital image data

• US 5,347,600 A
• Filed: 10/23/1991
• Issued: 09/13/1994
• Est. Priority Date: 07/05/1989
• Status: Expired due to Term

• Current Assignee: MediaBin, Inc. (HP Inc.)
• Original Assignee: Integrated Systems Incorporated
• Inventors: Sloan, Alan D., Barnsley, Michael F.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US07/781,586
• Time in Patent Office: 1,056 Days
• Field of Search: 382/56, 382/30, 382/27, 358/432, 358/433, 358/467
• US Class Current: 382/249
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G10L 25/36 using chaos theory
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

Digital image data is automatically processed by dividing stored image data into domain blocks and range blocks. The range blocks are subjected to processes such as a shrinking process to obtain mapped range blocks. The range blocks or domain blocks may also be processed by processes such as affine transforms. Then, for each domain block, the mapped range block which is most similar to the domain block is determined, and the address of that range block and the processes the blocks were subjected to are combined as an identifier which is appended to a list of identifiers for other domain blocks. The list of identifiers for all domain blocks is called a fractal transform and constitutes a compressed representation of the input image. To decompress the fractal transform and recover the input image, an arbitrary input image is formed into range blocks and the range blocks processed in a manner specified by the identifiers to form a representation of the original input image.

Claims

1. A method for automatically processing digital image data consisting of image information, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the domain blocks together contain all of the stored image information, and at least two of the domain blocks being unequal in shape;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of image data;

selecting, for each of the domain blocks, the one of the mapped range blocks which most closely corresponds to the domain block, according to predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

2. A method as recited in claim 1, wherein the step of creating a plurality of uniquely addressable mapped range blocks includes the substep of creating range blocks to have sizes different from the domain blocks.

3. A method as recited in claim 1 wherein the step of creating a plurality of uniquely addressable mapped range blocks includes the substep of:

creating sets of uniquely addressable mapped range blocks, all of the mapped range blocks of each set having the same shape as one of the domain blocks.

4. A method as recited in claim 2 wherein the step of selecting the mapped range blocks which most closely corresponds comprises the substep of selecting the range blocks from one of the sets of range blocks having the same shape as the domain blocks.

5. A method for automatically processing digital image data consisting of image information, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the domain blocks together contain all of the stored image information;

creating, from the stored image data, a plurality of uniquely addressable mapped range blocks corresponding to different subsets of the image data with each of the subsets having a unique address;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of image data;

performing a transform process on each domain block to create, for each domain block, a set of transformed domain blocks;

selecting, for each of the domain blocks, the one of the associated set of transformed domain blocks and the one of the mapped range blocks which most closely correspond, according to predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

6. A method as recited in claim 5 wherein the step of performing a transform process on each domain block includes the substep of rotating the domain block.

7. A method as recited in claim 5 wherein the step of performing a transform process on each domain block comprises the substep of inverting the domain block.

8. A method for automatically processing digital image data consisting of image information, the method comprising the steps performed by a data processor of:

storing the image data in the data processor;

generating a plurality of uniquely addressable domain blocks from the stored image data, each of the domain blocks representing a different portion of the image information such that all of the domain blocks together contain all of the stored image information;

creating, from the stored image data, a plurality of uniquely addressable overlapping mapped range blocks corresponding to different subsets of the image data with each of the subsets having a unique address, the creating step including the substep of

executing, for each of the mapped range blocks, a corresponding procedure upon the one of the subsets of the image data which corresponds to the mapped range block;

assigning unique identifiers to corresponding ones of the mapped range blocks, each of the identifiers specifying for the corresponding mapped range block a procedure and an address of the corresponding subset of image data;

selecting, for each of the domain blocks, the one of the mapped range blocks which most closely corresponds according to predetermined criteria; and

representing the image information as a set of the identifiers of the selected mapped range blocks.

9. A method for automatically generating a decoded image by a data processor from a set of identifiers, the data processor including a memory, the memory having a plurality of domain blocks each corresponding to a portion of an encoded image and each comprising locations specified by a memory address, each of the identifiers including an identifier address and each of the identifiers corresponding to a portion of the encoded image and to a domain block in the memory, the method comprising the steps, performed by a data processor, of:

a) storing a predetermined pattern of digital data in the memory;

b) choosing a location as a selected location;

c) storing the memory address of the selected location in a table;

d) finding a next identifier corresponding to a determined domain block containing the selected location;

e) determining, from the next identifier, a specified area of memory constituting a shrunken range block;

f) finding a target location in the shrunken range block having a position in the shrunken range block which corresponds to the position of the selected location in the determined domain block;

g) storing the memory address of the target location in the table and designating the memory address of the target location as the selected location;

h) repeating steps (c) through (g) until predetermined criteria are met;

i) determining decoded pixel values for locations of the table; and

j) repeating steps (c) through (i) until a desired portion of the encoded image is decoded.

10. A method as recited in claim 9 wherein step (h) comprises the substep of repeating steps (c) through (g) until the target address is equal to a memory address of a location stored in the table.

11. A method as recited in claim 9 wherein step (h) comprises the substep of repeating steps (c) through (g) a predetermined number of times.

12. A method as recited in claim 9 wherein step (h) comprises the substep of repeating steps (c) through (g) until decoded pixel values have been determined for all locations of all domain blocks have been determined.

13. Apparatus for automatically generating a decoded image from a set of identifiers each including an identifier address and each of the identifiers corresponding to a portion of the encoded image, the apparatus comprising:

input means for receiving data representative of the identifiers;

a memory having a plurality of domain blocks each corresponding to a portion of an encoded image and to one of the identifiers, and each comprising locations specified by a memory address;

processor means for;

a) storing a predetermined pattern of digital data in the memory;

b) choosing a location as a selected location;

c) storing the memory address of the selected location in a table;

d) finding a next identifier corresponding to a determined domain block containing the selected location;

e) determining, from the next identifier, a specified area of memory constituting a shrunken range block;

f) finding a target location in the shrunken range block having a position in the shrunken range block which corresponds to the position of the selected location in the determined domain block;

g) storing the memory address of the target location in the table and designating the memory address of the target location as the selected location;

h) repeating steps (c) through (g) until predetermined criteria are met;

i) determining decoded pixel values for locations of the table; and

j) repeating steps (b) through (i) until a desired portion of the encoded image is decoded; and

output means coupled to the processor means for supplying an output signal representative of the decoded image.