Fractal image compression device and method

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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

Claim 8

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.

Claim 9

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.

Claim 10

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

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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

Claim 17

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.

Claim 18

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

Claim 19

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.

Claim 20

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

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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

Claim 26

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.

Claim 27

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.

Claim 28

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

Claim 29

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.

Claim 30

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

Claim 31

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.

Claim 32

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

Claim 33

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.

Claim 34

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.

Claim 35

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

Claim 36

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.

Claim 37

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.

Claim 38

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.

Claim 39

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.

Claim 40

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.

Claim 41

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.

Claim 42

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.