Fractal image compression device and method
First Claim
1. A fractal image compression method, comprising the steps of:
- dividing image data representative of a composite image into a plurality of range blocks each having a first predetermined size;
designating, for each one of said plurality of range blocks, a plurality of domain blocks each having a second predetermined size larger than said first predetermined size, each one of said plurality of domain blocks having a subportion that includes an entire portion of a corresponding range block;
calculating, for each one of said plurality of range blocks, coefficients of a contractive transformation function to match each one of said plurality of domain blocks to said corresponding range block;
calculating, for each one of said plurality of range blocks, errors between each one of said plurality of domain blocks and said corresponding range block;
selecting, for each one of said plurality of range blocks, one of said plurality of domain blocks having a minimum error as a maximum similarity block for said corresponding range block; and
storing, for each one of said plurality of range blocks, a location index and said coefficients of said contractive transformation function for said one of said plurality of domain blocks selected as said maximum similarity block for said corresponding range block.
1 Assignment
0 Petitions
Accused Products
Abstract
A fractal image compression method performed in a digital image processing device includes the steps of: dividing image data representative of a composite image into a plurality of range blocks each having a first predetermined size; designating, for each of the range blocks, a plurality of domain blocks each having a second predetermined size, wherein each one of the plurality of domain blocks has a subportion that includes an entire portion of the corresponding range block; calculating coefficients of a contractive transformation function to match a plurality of spacially transformed domain blocks to each range block; calculating distortion errors between the range blocks and their corresponding pluralities of spacially transformed domain blocks; comparing the distortion errors among the spacially transformed domain blocks for each corresponding range block, and selecting a spacially transformed domain block having a minimum distortion error as a maximum similarity block for each corresponding range block; and storing, as a fractal code, a location index and coefficients of the contractive transformation function for each of the maximum similarity blocks.
-
Citations
36 Claims
-
1. A fractal image compression method, comprising the steps of:
-
dividing image data representative of a composite image into a plurality of range blocks each having a first predetermined size; designating, for each one of said plurality of range blocks, a plurality of domain blocks each having a second predetermined size larger than said first predetermined size, each one of said plurality of domain blocks having a subportion that includes an entire portion of a corresponding range block; calculating, for each one of said plurality of range blocks, coefficients of a contractive transformation function to match each one of said plurality of domain blocks to said corresponding range block; calculating, for each one of said plurality of range blocks, errors between each one of said plurality of domain blocks and said corresponding range block; selecting, for each one of said plurality of range blocks, one of said plurality of domain blocks having a minimum error as a maximum similarity block for said corresponding range block; and storing, for each one of said plurality of range blocks, a location index and said coefficients of said contractive transformation function for said one of said plurality of domain blocks selected as said maximum similarity block for said corresponding range block. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 31)
-
-
10. A fractal image compression method, comprising the steps of:
-
storing image data representative of a composite image to be compressed in a memory; dividing said image data into a plurality of range block each having a first predetermined size; designating, for each one of said plurality of range blocks, a plurality of domain blocks each having a second predetermined size that is an integer multiple larger than said first predetermined size, each one of said plurality of domain blocks having a subportion that includes an entire portion of a corresponding range block; spacially-transforming, for each one of said plurality of range blocks, each one of said plurality of domain blocks to contain a same amount of said image data as said corresponding range block; calculating, for each one of said plurality of range blocks, coefficients of a contractive transformation function to match each one of said plurality of domain blocks to said corresponding range block; calculating, for each one of said plurality of range blocks, mean square errors between each one of said plurality of domain blocks and said corresponding range block; selecting, for each one of said plurality of range blocks, one of said plurality of domain blocks having a minimum error as a maximum similarity block for said corresponding range block; and storing, for each one of said plurality of range blocks, a location index and said coefficients of said contractive transformation function for said one of said plurality of domain blocks selected as said maximum similarity block for said corresponding range block. - View Dependent Claims (11)
-
-
12. A fractal image compression device, comprising:
-
first storing means for storing pixel data to be compressed, said pixel data representative of a composite image; second storing means for receiving from said first storing means portions of said pixel data corresponding to a range block divided from said composite image, and for storing said portions of said pixel data corresponding to said range block; third storing means for receiving from said first storing means portions of said pixel data corresponding to a plurality of domain blocks assigned to said range block, and for storing said portions of said pixel data corresponding to said plurality of domain blocks; means for calculating and outputting coefficients of a contractive transformation function between said range block and each one of said plurality of domain blocks, and for calculating and outputting mean square errors between said portions of said pixel data corresponding to said range block and said portions of said pixel data corresponding to each one of said plurality of domain blocks; control means for assigning said plurality of domain blocks from said composite image to said range block so that each one of said plurality of domain blocks has a subportion that includes an entire portion of said range block, generating a plurality of spacially transformed domain blocks by transforming each one of said plurality of domain blocks to spacially correspond to said range block, receiving said mean square errors, selecting one of said plurality of domain blocks having a minimum mean square error as a most similar domain block, and then enabling output of a location index and said coefficients of said contractive transformation function corresponding to said most similar domain block; and fourth storing means for storing as a fractal code, said location index and said coefficients of said contractive transformation function corresponding to said most similar domain block. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
18. A fractal image compression method, comprising the steps of:
-
dividing image data representative of a composite image into a plurality of range blocks each having a first predetermined size; selecting, for each one of said plurality of range blocks, nine overlapping domain blocks each having a second predetermined size, each one of said nine domain blocks having a subportion that encompasses an entire portion of a corresponding range block, transforming, for each one of said plurality of range blocks, each one of said plurality of domain blocks to correspond spacially with said corresponding range block; calculating, for each one of said plurality of range blocks, coefficients of a contractive transformation function to match each one of said plurality of domain blocks to said corresponding range block; calculating, for each one of said plurality of range blocks, mean square errors between each one of said plurality of domain blocks and said corresponding range block; selecting, for each one of said plurality of range blocks, one of said plurality of domain blocks having a minimum error as a maximum similarity block for said corresponding range block; and storing, for each one of said plurality of range blocks, a location index and said coefficients of said contractive transformation function for said one of said plurality of domain blocks selected as said maximum similarity block for said corresponding range block. - View Dependent Claims (19, 20, 21)
-
-
22. An image compression device, comprising:
-
first means for storing pixel data to be compressed, said pixel data representative of a composite image, said pixel data comprising portions of said pixel data corresponding to a range block divided from said composite image and portions of said pixel data corresponding to a plurality of domain blocks assigned to said range block; means for calculating and outputting coefficients of a contractive transformation function between said range block and each one of said plurality of domain blocks, and for calculating and outputting mean square errors between said portions of said pixel data corresponding to said range block and said portions of said pixel data corresponding to each one of said plurality of domain blocks; control means for assigning said plurality of domain blocks from said composite image to said range block so that each one of said plurality of domain blocks has a subportion that includes an entire portion of said range block, generating a plurality of transformed domain blocks by transforming each one of said plurality of domain blocks to spacially correspond to said range block, receiving said mean square errors, selecting one of said plurality of domain blocks having a minimum mean square error as a most similar domain block, and then enabling output of a location index and said coefficients of said contractive transformation function corresponding to said most similar domain block; and said first means for storing said location index and said coefficients of said contractive transformation function corresponding to said most similar domain block. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30)
-
-
32. A fractal image compression method, comprising the steps of:
-
obtaining a contractive transformation function for each one of a plurality of range blocks, wherein said plurality of range blocks is a partition of an image represented by image data to be compressed, each one of said plurality of range blocks has corresponding thereto a plurality of domain blocks with each one of said plurality of domain blocks having a subportion that includes an entirety of said range block, and said obtaining step includes for each one of said plurality of range blocks spacially transforming a portion of said image data into a portion of pixel data for each one of said plurality of domain blocks, with said portion of said image data representing said domain block, calculating a slope and an offset for each one of said plurality of domain blocks, with said slope and said offset defining a contractive transformation function mapping said portion of said image data onto said portion of pixel data, calculating a mean square error between said portion of pixel data and said portion of said image data for each one of said plurality of domain blocks, and selecting one of said plurality of domain blocks as a maximum-similarity domain block for said range block, with said mean square error for said maximum-similarity domain block constituting a minimum among said mean square errors for said plurality of domain blocks; and storing physical quantities representative of a location index corresponding to said maximum-similarity domain block and of said slope and said offset for said maximum-similarity block in an image compression memory for each one of said plurality of range blocks. - View Dependent Claims (33, 34, 35, 36)
-
Specification