Fractal transform compression board

• US 5,384,867 A
• Filed: 10/23/1991
• Issued: 01/24/1995
• Est. Priority Date: 10/23/1991
• Status: Expired due to Fees

• Current Assignee: MediaBin, Inc. (HP Inc.)
• Original Assignee: MediaBin, Inc. (HP Inc.)
• Inventors: Primiano, Guy A., Elton, John H., Moreman, Charles S., Sloan, Alan D., Barnsley, Michael F.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US07/781,587
• Time in Patent Office: 1,189 Days
• Field of Search: 382/56, 382/27, 382/30, 382/41, 382/34, 382/14, 382/15, 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: H04N 19/99 involving fractal coding

Abstract

Digital image data compression apparatus includes a controller circuit for receiving digital image data and for processing the image data into blocks. The controller circuit supplies processed image data to a plurality of transform circuits and to a feeder circuit. The transform circuits receive data from the controller circuit and the feeder circuit, and provide parallel processing to compare blocks of image data and generate fractal transform values representing the image data in a compressed form.

Claims

1. Apparatus for generating signals representing an image in compressed digital form, comprising:

a memory for storing digital signals comprising digital image data representative of the image and for storing transformed data;

a control circuit coupled to the memory for receiving the digital image data, for subdividing the digital image data into a set of domain blocks and a set of range blocks each comprising pixel brightness data, for creating sets of multiple orientation blocks for the domain blocks each comprising pixel brightness data, for determining average brightness values for the domain and range blocks, for receiving transformed data corresponding to the domain blocks, for accumulating the transformed data in the memory, and for supplying the accumulated transformed data as output signals comprising a compressed digital representation of the image;

a data feeder circuit coupled to the control circuit for receiving the range block pixel brightness data and the range block average brightness values, and for creating intermediate range block values from the range block pixel brightness data and the range block average brightness values; and

a plurality of fractal transform circuits coupled to the control circuit and the data feeder circuit, for individually receiving at least one set of orientation blocks and the intermediate range block values, for simultaneously determining for each domain block corresponding to the received set of orientation blocks a block pair including a selected orientation block and a selected range block which have the greatest similarity of all possible block pairs, for simultaneously generating transformed data for each domain block, the transformed data representing the selected orientation block and range block for each domain block, and for supplying the transformed data to the control circuit.

2. Apparatus as recited in claim 1, wherein the control circuit comprises means for creating orientation blocks which comprise blocks of pixel brightness data representative of the domain blocks after rotation and inversion.

3. Apparatus as recited in claim 2, wherein the control circuit comprises means for creating sets of orientation blocks which each comprise a set of eight pixel brightness data blocks, each set corresponding to a domain block, the eight orientation blocks consisting of blocks of pixel brightness data representative of the corresponding domain block rotated by 90°

, 180°

, 270°

, and 360°

, and the inversion of each rotated domain block.

4. Apparatus as recited in claim 3, wherein each fractal transform circuit comprises a circuit having four channels, each channel comprising means for processing a separate rotation orientation block and the inversion of the corresponding rotation orientation block.

5. Apparatus as recited in claim 2, wherein each fractal transform circuit comprises means for simultaneously generating transformed data for all orientation blocks corresponding to a domain block.

6. Apparatus as recited in claim 1, wherein each fractal transform circuit comprises means for determining for each domain block the selected orientation block and the selected range block which are separated by a least image distance.

7. Apparatus as recited in claim 6, wherein each fractal transform circuit comprises means for determining for each domain block the selected orientation block and the selected range block which are separated by a least L2 distance.

8. Apparatus as recited in claim 7 wherein each fractal transform circuit comprises means for calculating an L2 distance according to the following formula:

##EQU3## where <

i<

number of pixels per block

0<

j<

number of blocks in range

z=domain block pixel value

pw=range block pixel value

9. Apparatus as recited in claim 7, wherein each fractal transform circuit comprises an L2 register for storing a running lowest L2 value, and each fractal transform circuit comprises means for updating the L2 register if the L2 value calculated for the current range block is less than the value stored in the register.

10. Apparatus as recited in claim 1, wherein the data feeder circuit comprises means for creating an intermediate range block brightness value equal to the difference between the pixel brightness value of a selected range pixel and the average pixel brightness value for the range block containing the selected range pixel.

11. Apparatus as recited in claim 1, wherein the data feeder circuit comprises a range pattern memory circuit.

12. Apparatus as recited in claim 1, wherein the data feeder circuit comprises a range pixel memory circuit.

13. Apparatus as recited in claim 1, wherein the data feeder circuit comprises a range average memory circuit.

14. Apparatus as recited in claim 1, wherein the data feeder circuit comprises a range address controller circuit.

15. Apparatus as recited in claim 1, wherein the data feeder circuit comprises a range subtraction circuit for creating an intermediate range value equal to the difference between a selected range block pixel brightness value and a range block average pixel brightness value for the range block containing the selected range pixel.

16. Apparatus as recited in claim 1, wherein the control circuit comprises means for storing a list of domain blocks and range blocks which have been sent to the plurality of fractal transform circuit and data feeder Circuit, respectively.

17. Apparatus as recited in claim 1, wherein the control circuit comprises means for generating a set of domain blocks and a set of range blocks each comprising pixel brightness data processed by contraction parameter values and shade offset difference values.

18. Apparatus as recited in claim 1, comprising means for removably connecting said apparatus to an associated host computer.

19. Apparatus for generating signals representing an image in compressed digital form, comprising:

a memory for storing digital signals comprising digital image data representative of the image and for storing transformed data;

a control circuit coupled to the memory for processing the digital image data into domain block data and range block data, the domain block data comprising a set of domain blocks and the range block data comprising a set of range blocks, the set of domain blocks comprising a set of non-overlapping uniquely addressable blocks of pixel brightness data which collectively contain all of the digital image data, and the set of range blocks comprising a set of uniquely addressable blocks of pixel brightness data of the digital image data which have been subjected to a contractive process;

for accumulating transformed data in the memory; and

for supplying the accumulated transformed data as output signals comprising a compressed digital representation of the image;

a data feeder circuit coupled to the control circuit for receiving the range block data, and for creating intermediate range block values from the range block data; and

a plurality of fractal transform circuits coupled to the control circuit and the data feeder circuit for receiving domain block data for a plurality of domain blocks and the intermediate range block values;

for simultaneously determining, for each domain block corresponding to the received domain block data, a selected range block which has the greatest similarity;

for generating transformed data, for each domain block corresponding to the received domain block data, which is representative of the selected range block; and

for supplying the transformed data to the control circuit.

20. Apparatus for generating signals representing an image in compressed digital form, comprising:

a memory for storing digital image data representative of the image and transformed data;

a control circuit coupled to the memory for receiving the digital image data, for dividing the digital image data into a first group of subsets and a second group of subsets, each of the subsets comprising pixel brightness data, for accumulating transformed data in the memory, and for supplying the accumulated transformed data as output signals comprising a compressed digital representation of the image;

the control circuit comprising

means for receiving digital image data comprising a set of pixel brightness values, and

means for generating a set of range pixel brightness values each formed as the average of a plurality of pixel brightness values of the digital image data, for generating a plurality of subdivision values specifying the order in which the range pixel brightness values are to be arranged into the second group of subsets, and for supplying the range pixel brightness values and the subdivision values to the data feeder circuit;

a data feeder circuit coupled to the control circuit for receiving the second group of subsets and for generating data representative of the second group of subsets, the data feeder circuit comprising

a first memory circuit for storing the range pixel brightness values, a plurality of storage locations for storing the subdivision values, and

a feeder control circuit for supplying intermediate values representative of brightness values of range pixels arranged in the order specified by the subdivision values; and

a plurality of fractal transform circuits coupled to the control circuit and the data feeder circuit, for receiving the first group of subsets and the representative data, for determining for each of the first group of subsets a selected one of the second group of subsets which has the greatest similarity, for generating transformed data for each of the first group of subsets which is representative of the selected one of the second group of subsets, and for supplying the transformed data to the control circuit.