Method and apparatus for compressing and decompressing three-dimensional digital data using fractal transform

• US 5,754,704 A
• Filed: 03/10/1995
• Issued: 05/19/1998
• Est. Priority Date: 03/10/1995
• Status: Expired due to Fees

• Current Assignee: MediaBin, Inc. (HP Inc.)
• Original Assignee: Integrated Systems Incorporated (Aptiv PLC)
• Inventors: Hurd, Lyman P., Demko, Stephen, Barnsley, Michael F.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US08/401,672
• Time in Patent Office: 1,166 Days
• Field of Search: 382/249, 382/154, 382/233, 382/232, 358/432, 358/433
• US Class Current: 382/249
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
• CPC Class Codes: H04N 19/99 involving fractal coding

Abstract

A method and apparatus are described for-encoding a three-dimensional array of data representing a physical entity, such as an image (or sequence of frames), by means of its local symmetries. This encoding yields both compression and a resolution-independent description which allows reconstruction of the image to an arbitrary scale. Spatial zooming and interframe interpolation can be achieved without significant loss of information.

Claims

1. A method for automatically compressing digital data representative of a physical entity existing in three dimensions, comprising the steps performed by a data processor of:

storing the digital data in a three-dimensional data set of predetermined size in the data processor;

generating a set of uniquely addressable three-dimensional domain boxes from the stored digital data, each of the domain boxes representing a different portion of the stored digital data such that all of the domain boxes together contain all of the stored digital data;

creating, from the stored digital data, a set of uniquely addressable three-dimensional mapped range boxes each corresponding to one of a plurality of three-dimensional subsets of the digital data, with each of the subsets having a unique address, the creating step for each mapped range box including the substep of shrinking the one of the subsets of the digital data which corresponds to the mapped range box such that there is a one-to-one correspondence between values of the domain boxes and values of the mapped range boxes;

assigning unique box identifiers to corresponding ones of the mapped range boxes, each of the box identifiers specifying for the corresponding mapped range box an address of the corresponding subset of digital data;

performing a first affine transformation on a first set of boxes of the stored-digital data comprising one of the domain box set and the mapped range box set, wherein a second set of boxes of the stored digital data comprises the other of the domain box set and the mapped range box set, and wherein the first affine transformation applied to each of the boxes of the first set has a corresponding transformation identifier;

forming, for each of the domain boxes, a selected pair of boxes, each box pair including one box from each of the first and second box sets, one of the boxes of each pair being the box of its corresponding set which most closely corresponds to the other box of the pair according to predetermined criteria; and

supplying a set of codewords each comprising an identifier pair as a compressed representation of the digital data in a data set of a size smaller than the predetermined size, each identifier pair corresponding to a different one of the formed selected box pairs, each of the identifier pairs comprising a box identifier associated with one of the boxes of the corresponding box pair and a transformation identifier associated with one of the boxes of the corresponding box pair.

2. A method as recited in claim 1 wherein:

the first set of boxes comprises the set of mapped range boxes;

each box pair comprises a domain box and a transformed mapped range box; and

each of the identifier pairs comprises a mapped range box identifier and a transformation identifier associated with a transformation applied to a mapped range box.

3. A method as recited in claim 1 wherein the step of creating mapped range boxes comprises the step of creating mapped range boxes including an escape box containing digital data in which all bits have the same value.

4. A method as recited in claim 1, wherein the predetermined criteria comprises selecting boxes of the first and second sets which are separated by the minimum distance.

5. A method as recited in claim 4, wherein the predetermined criteria comprises selecting boxes of the first and second sets which are separated by the minimum Hausdorf distance.

6. A method as recited in claim 1, wherein the step of creating mapped range boxes comprises changing the pixel values of at least one of the range boxes by a predetermined mapping function and wherein the step of supplying a set of codewords comprises supplying a set of codewords including a description of the predetermined mapping function.

7. A method as recited in claim 1 wherein the transformation identifiers comprise a symmetry operator associated with one of the boxes of the corresponding box pair.

8. A method as recited in claim 1 wherein the transformation identifiers comprise a pixel operator associated with one of the boxes of the corresponding box pair.

9. A method as recited in claim 8 wherein the pixel operator includes a multiplier and an additive term.

10. A method for processing digital data values representative of a physical entity existing three dimensions to produce a representation of an original data processor from a set of identifier pairs, the original data value set is represented in an array having three axes each with an upper limit, the data processor including a memory having a plurality of buffers each having a plurality of addressable areas specified by a buffer address and each of the identifier pairs corresponding to an addressable area in the buffers and including a buffer address and a procedure specification, at least one of the identifier pairs representing a first predetermined pattern of digital data, the method comprising the steps, performed by the data processor, of:

storing a second predetermined pattern of digital data values in one of the buffers designated as a source buffer;

determining, for each of the identifier pairs, a pattern of data values corresponding to each identifier pair by applying the procedure specified in that identifier pair to the portion of the source buffer indicated by the buffer address in that identifier pair;

storing the patterns of data into the addressable area of another one of the buffers, designated as a target buffer, indicated in the corresponding identifier pair;

repeating the determining and target buffer storing steps, with the target buffer being considered as the source buffer, until predetermined criteria are met; and

providing the contents of the target buffer as data values representative of the original data value set when the predetermined criteria are met;

the source and target buffers being arranged in an array having three axes, corresponding to the original data value set array axes, each source and target buffer array axis having an upper limit; and

at least one of the source and target buffer array axis upper limits differing from the corresponding original data value set array axis upper limit, whereby the representative data values constitute a representation of the original data value set at a resolution different than the original data value set.

11. A method as recited in claim 10 wherein only a portion of the original data value set is processed.

12. Apparatus for automatically compressing digital data representative of a physical entity existing in three dimensions, comprising:

an input device for supplying digital data;

a memory for storing the digital data in a three-dimensional data set of predetermined size in the data processor;

a data processor for generating a set of uniquely addressable three-dimensional domain boxes from the stored digital data, each of the domain boxes representing a different portion of the stored digital data such that all of the domain boxes together contain all of the stored digital data;

for creating, from the stored digital data, a set of uniquely addressable three-dimensional mapped range boxes each corresponding to one of a plurality of three-dimensional subsets of the digital data, with each of the subsets having a unique address such that each mapped range box comprises a shrunken version of the one of the subsets of the digital data which corresponds to the mapped range box such that there is a one-to-one correspondence between values of the domain boxes and values of the mapped range boxes;

for assigning unique box identifiers to corresponding ones of the mapped range boxes, each of the box identifiers specifying for the corresponding mapped range box an address of the corresponding subset of digital data; and

for performing a first affine transformation on a first set of boxes of the stored digital data comprising one of the domain box set and the mapped range box set, wherein a second set of boxes of the stored digital data comprises the other of the domain box set and the mapped range box set, and wherein the first affine transformation applied to each of the boxes of the first set has a corresponding transformation identifier;

a comparator for comparing boxes of the first and second sets and for selecting, for each of the domain boxes, a selected pair of boxes, each box pair including one box from each of the first and second box sets, one of the boxes of each pair being the box of its corresponding set which most closely corresponds to the other box of the pair according to predetermined criteria; and

an output device for supplying a set of codewords each comprising an identifier pair as a compressed representation of the digital data in a data set of a size smaller than the predetermined size, each identifier pair corresponding to a different one of the formed selected box pairs, each of the identifier pairs comprising a box identifier associated with one of the boxes of the corresponding box pair and a transformation identifier associated with one of the boxes of the corresponding box pair.

13. Apparatus for processing digital data values representative of a physical entity existing in three dimensions to produce a representation of an original data value set from a set of identifier pairs each including a buffer address and a procedure specification, the original data value set being represented in an array having three axes each with an upper limit, at least one of the identifier pairs representing a first predetermined pattern of digital data, the apparatus comprising:

a source buffer having a plurality of addressable areas specified by a buffer address for storing a second predetermined pattern of digital data values;

a target buffer having a plurality of addressable areas specified by a buffer address;

a processor for repeatedly determining, for each of the identifier pairs, a pattern of data values corresponding to each identifier pair by applying the procedure specified in that identifier pair to the portion of the source buffer indicated by the buffer address in that identifier pair;

for storing the patterns of data into the addressable area of the target buffer indicated in the corresponding identifier pair; and

for swapping data stored in the source and target buffers the target buffer being considered as the source buffer, until predetermined criteria are met; and

an output device coupled to the memory and the processor for providing the contents of the target buffer as data values representative of the original data value set when the predetermined criteria are met;

the source and target buffers being arranged in an array having three axes, corresponding to the original data value set array axes, each source and target buffer array axis having an upper limit and at least one of the source and target buffer array axis upper limits differing from the corresponding original data value set array axis upper limit, whereby the representative data values constitute a representation of the original data value set at a resolution different than the original data value set.