Method and apparatus for compression and decompression of digital image data
First Claim
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 ofexecuting, 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7)
-
-
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. - View Dependent Claims (10, 11, 12)
-
-
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.
-
Specification