Digital Image Processing - Open Project

Fractal Image Compression


Ashish Gupta


What is Fractal Compression ( the main idea )?

Concept of Self Similarity

Example

1


One can see the self similiar regions ( the inverted ones ) in the image above. Fractal compression stores this type of information to achieve compression.

To do fractal compression , the image is divided into sub-blocks. Then for each block , the most similiar block if found in a half size version of the image and stored. This is done for each block.
Then during decompression, the opposite is done iteratively to recover the original image.

Links


Fractal Image Compression

Waterloo Fractal Compression Project

Hitchhiker's Guide to Fractal Compression

Yuval Fisher's Home Page ( Lots of links ! )

What it is not ?

It is not a compression technique for compressing fractals ( e.g. a Mandlebrot set ) as it is commonly misunderstood but is a compression technique which can be used for any digital image.

A Unique Feature

Fractal Image Decoding is resolution independent. That is , if you compress a 64x64 image , you can decompress it to any size ( say 128x128) without as much loss in quality as you would have for normal zoom. ( see below for examples )



Examples of Fractal Compression


Note : Fidelity Criterian used for image quality here are the eyes of the user.

Version 1


In this version , gamma was kept constant at 0.7 and beta was calculated as the difference in the mean of the range and the mean of the corresponding domain block.
This means that only the differences in intensity were stored ( brightness factor ) and no factor for change in contrast was stored.
This version will be compared with  version 2 which handles both parameters and computes them using Least Square minimization technique.


The code size for each range block was very small and produced very good compression , comparable to JPEG.

Here size of each fractal code per domain block is:

  1. Location of Range block for each domain block ( x,y ) = 16 bits
  2. Orientation of each range block -  8 bits ( actually only 3 bits in size )
  3. Value of beta ( from 0 to 255 ) -  8 bits
Total : 32 bits per domain block.

Analysis for a 16 bit image

For a panel size of 4 ,
bits in original image : 4x4x16
bits in compressed image : 32
Compression Ratio : 8



Example 1:


Monkey ( 64x64 )

Original Image

1

BMP size : 9098 bytes

JPEG File ( ImageMagick )

1

JPEG Size : 1080 bytes
Time taken : about 0.5 secs

Fractal Compression


Compression at Panel Size 4


FIF file size : 1036 bytes  , zipped : 996
Time taken : about 5 seconds

The FIF-ZIP file is smaller compared to
the JPEG file !


Decoded at

Panel Size 4
1

Panel Size 8
1


















Original Images

1


1

Compression at Panel Size 2

FIF size : 4108 bytes , zipped : 3449
Time taken : about 8 secs

Decoded at

Panel Size 2
1

Panel Size 4
1

Panel Size 8
1



One can observe the difference between the
Fractal Decoded images and the zoomed images.
Fractal decoded images appear to show much
detail then their corresponding zoomed
counterparts.
Original Images






1


1



1
Zoomed Images ( using ImageMagick )












1



1

Iterations step by step ( for panel size 2 -> 4 )

Initial Image
(any random image can be taken ! )

1

Iteration 1
( after transformation from Initial Image )

1

Iteration 2

1
Iteration 3

1
Iteration 4

1

Iteration 5

1
Iteration 6

1


Version 2


In this version , optimal values of gamma and beta were chosen using Least square minimization technique to yield the best decoded image quality.

Compared to Version 1 , this method yields more quality ( see below ) but takes more time to compress and results in  a larger file size.



Example :
Monkey ( 64 x 64 )

Original Image

1

BMP size : 9098 bytes

JPEG File ( ImageMagick )

1

JPEG Size : 1080 bytes
Time taken : about 0.5 secs

Fractal Compression


Compression at Panel Size 4


FIF file size : 1292 bytes  , zipped : 1302
Time taken : about 12 seconds

Here we see that time taken is more compared
to version 1 and file size is slightly more due
to the contrast factor ( gamma )


Decoded at

Panel Size 4

1

Panel Size 8
1

Panel Size 16
1



Original Images

1


1


1

Compression at Panel Size 2

FIF size : 6156 bytes , zipped : 5076
Time taken : about  17 secs


Panel Size 2
1

Panel Size 4

1

Panel Size 8

1

Original Images






1



1



1

Zoomed Images ( using ImageMagick )












1




1

Error report ( Average Error ) with original

Intensity Range : 0-256

Comparison of Panel Sizes

t2-2.gif ( 64)  = 3.17598
t4-4.gif ( 64 ) = 5.41374

t2-4.gif ( 128 ) =  7.0992
t4-8.gif ( 128 ) = 7.74945

t2-8.gif  ( 256 ) = 9.1733
t4-16.gif ( 256 ) = 9.3771



Fractal Zoom vs Ordinary Zoom

2x zoom (128)

Fractal ( 2->4) :7.0992
Normal : 12.3635

4x zoom ( 256 )

Fractal ( 2-> 8) : 9.1733
Normal : 13.3033
Graph #1

1

Iterations step by step ( for panel size 2 -> 4 )

Initial Image
(any random image can be taken ! )

1

Avg. Error : 109.435
Iteration 1
1

Avg. Error : 52.3372

 Iteration 2
1

Avg. Error : 29.2551
 Iteration 3
1

Avg. Error : 17.785
Iteration 4
1

Avg. Error : 8.96379
 Iteration 5
1

Avg. Error : 7.36661
 Iteration 6
1

Avg. Error : 7.1383
Iteration 7

Avg. Error : 7.10098
 Iteration 8

Avg. Error : 7.09743
 Iteration 9

Avg. Error : 7.09902
Graph #2

1




Comparison Between the 2 versions


Version 1 Image ( gamma is constant )

Version 2 Image ( both gamma and beta computed )
Compression at Panel Size 4

1


1
Compression at Panel Size 4
1



1

One can note the better constrast when both gamma and beta are variable,

Compression at Panel Size 2

Compression at Panel Size 2
1


1

1

1


1

1

Here the difference in contrast is less obvious ( look at the nose )


Original Image ( for reference )

1

                                                   

Comparison Between panel size

The quality in Fractal Image Compression is affected by the panel size. Smaller the panel size , more accurate will be the encoding of the image and better will be the quality of the decoded image.
The differences can be seen below

This images are from Version 2


Panel Size 4

Panel Size 2
Panel Size 4 Size : 1292

1
Avg. Error :  5.41374

Panel Size 8
1

Panel Size 16
1
Panel Size 2 Size : 6156
1
Avg. Error : 3.17598

Panel Size 4

1

Panel Size 8

1

Observation
Here one can see the difference in the quality of the decoded images. The images on the right have more detail than the images on the left.

Panel Size 8  Size : 396 bytes

Time : about 11 secs

At 8
1
Avg. Error : 9.55711

At 16
1


At 32
1

Panel Size 16 Size : 108 bytes

Time : about 4 secs

At 16

1
Avg. Error : 22.1591

At 32 !

1


Graph #3

1



Applications


Resolution Independent Decoding


One can use this feature to see more detail in an image at higher magnification than is otherwise allowed by ordinary zoom.


Zoom Using Fractal Decoding

Zoom Using ImageMagick
2x

1
2x

1
4x

1
4x

1
8x

1
8x

1





THE END