Fractal image compression device and method

• US 5,701,369 A
• Filed: 08/31/1995
• Issued: 12/23/1997
• Est. Priority Date: 04/19/1995
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Moon, Yong-Ho, Kim, Jae-ho, Park, Dong-Seek
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/521,809
• Time in Patent Office: 845 Days
• Field of Search: 382/249, 382/248, 382/250, 358/432, 358/433, 358/235
• 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

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.

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.

2. The fractal image compression method as claimed in claim 1, wherein said step of calculating said coefficients of said contractive transformation function further comprises 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.

3. The fractal image compression method as claimed in claim 1, wherein said step of calculating said errors comprises calculating mean square errors between each of said plurality of domain blocks and said corresponding range block.

4. The fractal image compression method as claimed in claim 1, wherein nine domain blocks are designated for each one of said plurality of range blocks in said designating step.

5. The fractal image compression method as claimed in claim 1, wherein said second predetermined size is an integer multiple larger than said first predetermined size.

6. The fractal image compression method as claimed in claim 5, wherein said integer multiple equals four.

7. The fractal image compression method as claimed in claim 2, wherein nine domain blocks are designated for each one of said plurality of range blocks in said designating step.

8. The fractal image compression method as claimed in claim 2, wherein said second predetermined size is an integer multiple larger than said first predetermined size.

9. The fractal image compression method as claimed in claim 8, wherein said integer multiple equals four.

31. The fractal image compression method of claim 1, wherein:

for each one of said plurality of range blocks, said first predetermined size is equal to said first predetermined size for every other one of said plurality of range blocks; and

for each one of said plurality of domain blocks, said second predetermined size is equal to said second predetermined size for every other one of said plurality of domain blocks.

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.

11. The fractal image compression method as claimed in claim 10, wherein nine domain blocks are designated for each one of said plurality of range blocks in said designating step.

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.

13. The fractal image compression device as claimed in claim 12, wherein said plurality of domain blocks comprises nine domain blocks.

14. The fractal image compression device as claimed in claim 13, wherein said range block has a first predetermined size and each one of said plurality of domain blocks has a second predetermined size, said second predetermined size being an integer multiple larger than said first predetermined size.

15. The fractal image compression device as claimed in claim 14, wherein said integer multiple equals four.

16. The fractal image compression device as claimed in claim 12, wherein said range block has a first predetermined size and each one of said plurality of domain blocks has a second predetermined size, said second predetermined size being an integer multiple larger than said first predetermined size.

17. The fractal image compression device as claimed in claim 16, wherein said integer multiple equals four.

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.

19. The fractal image compression method as defined in claim 18, wherein a first of said nine domain blocks has a lower right subportion that encompasses said corresponding range block, a second of said nine domain blocks has a lower center subportion that encompasses said corresponding range block, a third of said nine domain blocks has a lower left subportion that encompasses said corresponding range block, a fourth of said nine domain blocks has a central right subportion that encompasses said corresponding range block, a fifth of said nine domain blocks has a center subportion that encompasses said corresponding range block, a sixth of said nine domain blocks has a central left subportion that encompasses said corresponding range block, a seventh of said nine domain blocks has a upper right subportion that encompasses said corresponding range block, an eighth of said nine domain blocks has an upper center subportion that encompasses said corresponding range block, and a ninth of said nine domain blocks has an upper left subportion that encompasses said corresponding range block.

20. The fractal image compression method as defined in claim 19, wherein said second predetermined size is an integer multiple larger than said first predetermined size.

21. The fractal image compression method as defined in claim 20, wherein said integer multiple equals four.

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.

23. The image compression device as claimed in claim 22, wherein said plurality of domain blocks comprises nine domain blocks.

24. The image compression device as claimed in claim 23, wherein said range block has a first predetermined size and each one of said plurality of domain blocks has a second predetermined size, said second predetermined size being an integer multiple larger than said first predetermined size.

25. The image compression device as claimed in claim 24, wherein said integer multiple equals four.

26. The image compression device as claimed in claim 22, wherein said range block has a first predetermined size and each one of said plurality of domain blocks has a second predetermined size, said second predetermined size being an integer multiple larger than said first predetermined size.

27. The image compression device as claimed in claim 26, wherein said integer multiple equals four.

28. The image compression device as claimed in claim 22, wherein said means for calculating comprises a slope and offset detector for detecting slopes and offsets.

29. The image compression device as claimed in claim 22, wherein said means for calculating obtains slope values of said pixel data before obtaining offset values of said pixel data.

30. The image compression device as claimed in claim 22, wherein said means for calculating detects slope and offset values of said pixel data.

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.

33. The fractal image compression method of claim 32, further comprising the steps of:

storing said image data in a page memory; and

dividing said image into said plurality of range blocks.

34. The fractal image compression method of claim 32, wherein said obtaining step further includes designating said plurality of domain blocks corresponding to said range block.

35. The fractal image compression method of claim 33, wherein said obtaining step further includes:

loading said portion of said image data into a range block memory;

loading said portion of pixel data into a domain block memory for each one of said plurality of domain blocks; and

outputting said physical quantities representative of said location and said slope and said offset for said maximum-similarity block.

36. The fractal image compression method of claim 35, wherein said obtaining step further includes:

outputting said slope and said offset for each one of said plurality of domain blocks; and

outputting said 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.