Time Optimization Of Fractal Image Compression By Using Genetic Algorithm

Time Optimization Of Fractal Image Compression By Using Genetic Algorithm

Mr. Vishvas V. Kalunge Prof. Varunakshi Bhojane

ME [Computer Engg.] Assistant Professor, Computer Dept. Pillai's Institute of Information Technology Pillais Institute of Information Technology

New Panvel, Navi Mumbai, India. New Panvel, Navi Mumbai, India.

Abstract

Compressing an image is nothing but storing that image in less number of bytes without degrading the quality of an image to an unaccepted level. Compressed image gives less data for the transmission, which results into fast transfer of data over limited bandwidth. Various techniques are available to compress the images. Fractal Image Compression (FIC) is the one which uses self similarity property of the image and compress the images compactly. But algorithm takes more time in order to find self similar parts within an image. This results into large amount of time to compress the image. The solution to this problem is to use of Genetic Algorithm (GA) to find similar parts in an image. With genetic algorithm the task of finding similar parts become very easy and can be completed in less time. So we are optimizing the time required to fractal image compression by using genetic algorithm.

Keywords: Fractals, Genetic algorithm, Image compression.

1. Introduction

   The aim of this work is image compression with fractals in less time requirement. Fractal Image Compression is a lossy compression technique introduced by Michael F Barnsley and Jacquin [1],[8]. This method is best suited for textures and natural images, relying on the fact that parts of an image often resembles other parts of the same image.

   The process of matching fractals does not involve looking for exact matches, but instead looking for

   "best fit" matches based on the compression parameters (encoding time, image quality, and size of output) [8]. But the encoding process can be controlled to the point where the image is "visually lossless." That is, one shouldn't be able to notice where the data was lost.

   Compression process is extremely computationally intensive [2] as Millions or billions of iterations are required to find the fractal patterns in an image. Depending upon the resolution and contents of the input bitmap data, and output quality, compression time, and file size parameters selected, compressing a single image could take anywhere from a few seconds to a few hours (or more) on even a very fast computer.

   Solution to this problem is use of genetic algorithm which speed up computation time. By using genetic algorithms to address the problem, we want to optimize the domain blocks search [3].

2. Fractal Image Compression without applying GA.

The basic scheme of the fractal image compression is to partion a given image into non overlapping blocks of size r*r , called range blocks and form a domain pool containing all of possible overlapped blocks of size 2r*2r , called domain blocks [7]. Means original image is divided into several blocks twice. One to form the set of range blocks and other to form the set of domain blocks. After dividing the image into set of range blocks and set of domain blocks, algorithm try to find the best possible domain block for each and every range blocks (as shown in fig 1). The range-

domain block matching process consists of searching the domain pool D for the Di, and an affine transformation wi, which minimizes the distance between the range block Ri and the transformed domain block wi*Di. It considers the first range block apply the various transformations on it and try to find best possible match for it from the domain pool. It continues the same process for the remaining range blocks. For one range block it apply around eight transformations separately and find the best possible match by comparing it with each and every domain blocks in domain pool. The domain and range matching is done based on the fitness function.

Fig 1:Domain range block transformation

2.1 Algorithm for FIC without applying GA

1. Input a square binary image.

2. Divide image with square range blocks. The total set of range blocks must cover image, without overlapping.

3. Introduce the domain blocks D; they must intersect with image.

4. Define a collection of transformations mapping domain block D to the range block Ri.

5. For each range block, choose a corresponding domain block and symmetry so that the domain block looks most like the part of the image in the range block.

6. Write the compressed data in the form of a local IFS code.

7. Apply a lossless data compression algorithm to obtain a compressed IFS code [2].

Normally the size of the domain block is double than the size of range block. While comparing the domain blocks with range block, we cannot compare it

directly because of size variation. In order to compare it, domain blocks must be compressed to 50% to make it similar to range block.

Easily we cannot find similar parts in any natural images, so algorithm complexity is very high, which leads to a very slow compression process [3].

1. Fractal Image Compression by applying GA

   1. Genetic Algorithm

      A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of evolutionary algorithms (EA), which generate solutions to optimization problems using techniques inspired by natural evolution, such as mutation, selection, and crossover.

      GA requires solutions in binary as strings of 0s and 1s. The evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.

   2. Parameters that affects the output

      There are so many parameters that affect the output. The parameters include parameters of fractal image compression and parameters of genetic algorithms. Few of them are as follows.

      1. Range and domain block size.

      2. Error limit.

      3. Number of transformations used.

      4. Fitness function.

      5. Population Size.

      6. Crossover rate.

      7. Mutation rate.

      8. Number of iterations.

   3. Creating Chromosomes

      Genetic algorithm works on the chromosomes. So creating chromosomes from the range blocks and domain blocks is the very critical step in applying genetic algorithm to fractal image compression. The transformation parameters obtained for each block coded on a fix number of bits. Such transformations are stored as chromosomes.

      These parameters and number of bits required to store that transformation are as follows:

      1. Xdom is the X coordinate of the domain block, which is coded by 8 bits

      2. Ydom is the Y coorinate of the domain block, which is coded by 8 bits

      3. S is scaling factor : which belong to [-1,+1] and coded by 5 bits.

      4. O is the contrast factor: which range from 0 to 255, code on only 7 bits.

      5. The isometric flip parameters: take its values between 0 and 7 for 8 possible flips and rotations. So it can be coded by 3 bits [3].

         With the help of above mentioned parameters we can create the chromosome for every domain block in 31 bits only. Once population of the chromosomes is created, genetic algorithm applies its crossover and mutation operators to create the new offsprings of better quality. It decides the quality of the offspring depend on its fitness function.

   4. Fitness Function

      In our implementation we used linear regression as a fitness function. Linear regression attempts to model the relationship between two variables by fitting a linear equation to observed data. In linear regression, data is modeled using linear predictor functions, and unknown model parameters are estimated from the data. Formula for linear regression is given below.

      c = (x-a*y-b)'*(x-a*y-b) where

      a = (x-meanx)'*(y-meany)/((y-meany)'*(y-meany))

      b = (meanx-a*meany); and

      meanx = mean(x); meany = mean(y);

   5. Applying Crossover operator

      Crossover operator selects the two parents depend upon their fitness and try to create new Childs of better quality. Higher the fitness value, greater is the chance of selection for crossover. Crossover operator may be single point crossover or two point crossover. Crossover alters the genes of the parent chromosome as shown in fig 2.

      Fig 2: Working of crossover operator

   6. Applying mutation operator

      Mutation is a genetic operator that alters one ore more gene values in a chromosome from its initial state. This can result in entirely new gene values being added to the gene pool. With these new gene values, the genetic algorithm may be able to arrive at better solution than was previously possible. Mutation operation is used to introduce the diversity in the chromosomes. Randomly it changes the piece of information depending upon the mutation rate.

      Wend

      Wend

      – write obtained transformation parameters to the Output Coefficient;

      Fig 3: Working of mutation Operator

   7. Algorithm for fractal image compression by applying Genetic Algorithm.

      Input: take a NxN square image

      Initialize FIC parameters like range block size, fitness function, error limit, no. of iterations.

      Initialize GA parameters like mutation rate, crossover rate;

      Divide the input image into set of range blocks;

      Divide the input image into set of domain blocks;

      Generate a random population of chromosomes from region blocks;

      While Loop (Number of iterations reached) While Loop (until all Regions not coded)

      -Select Region Blocks sequentially

      While Loop (until last generation reached)

      • Compute fitness for all regions;

      • Depending upon the fitness search the optimal domain block from domain pool;

      • When optimal domain block found

      -Generate new population {Apply Selection, Crossover and Mutation operators};

      Wend.

      In this algorithm the task of finding the best domain block for each and every range block is carried out by the Genetic Algorithm (GA), which results in to the fast compression of the image.

2. Fractal Image Decompression

   Fractal image decompression is quite faster than the compression. In our implementation we have taken random image as an input for decompression and generated the output image. Already IFS code prepared during compression contains the transformation and on which block that transformations are to be applied. At the time of decompression just apply that transformations iteratively to the respective block in reverse order [5]. After some iterations we get the decompressed image which is similar to the original image then the process should be stopped. The number of iterations required to decompress the image by using GA are less than the decompression done in normal way. Initial few iterations of decompression are as shown in fig 4.

   1st Iteration 2nd 3rd 4th

   Fig 4: Iterations of the decompression.

3. Results

   We carried out this work on intel i3 processor with 220 GHz and 3 GB of RAM. In our implementation we have taken image size as 128*128, range block size as 4*4 and domain block size as 8*8. We got the results shown in table 1. The compression ratio

   remains same for all same size images. Any change in range block size or domain block size or input image size, changes the output.

   Table 1: Time comparison of FIC by applying GA and without applying GA.

   Image	Input Image Size	Output Image Size	Time for Compressi on without GA	Time for Compres sion with GA
   Lena	48 KB	5120 Bytes	184 sec	67 sec
   Barbara	48 Kb	5120 Bytes	243 sec	66 sec
   Fruits	48 KB	5120 Bytes	245 sec	62 sec
   Apple	64 KB	5120 Bytes	196 sec	85 sec

4. Conclusion:

Fractal image compression is one of the best method to compress the image. But main drawback of FIC is, it takes more time to compress the image. In order to reduce the time required for the compression, we applied genetic algorithm. Experimental results show that GA achieves good optimization in time required for fractal image compression.

References

1. V. Chaurasia and Ajay , Review of novel techniques: Fractal image compression International journal on emerging technology, 2010.

2. Y. Chakrapani and K.Soundara Rajan,Genetic algorithm applied to fractal image compression, ARPN Journal of Engineering and Applied Sciences, VOL. 4, no. 1, february 2009

3. Aoued BOUKELIF] ,Optimization of Fractal Image Compression Based on Genetic Algorithms ,5th international conference: Sciences of Electronic,Technologies of Information Telecommunications March 22-26, 2009 TUNISIA

4. Y. Chakrapani and K. Soundera Rajan, Implementation of Fractal Image Compression Employing Hybrid Genetic-Neural Approach, international journal of computational cognition vol. 7, no. 3, September 2009.

5. Pou-Yah Wu, Fast Fractal Image Compression, Dept. of Mathematics Education, National Tainan Teachers College, Taiwan, 2006

6. Miroslav Galabov,Fractal Image Compression International Conference on Computer Systems and Technologies – CompSysTecp003.

7. Mohamcd Elsherif, Mohsen rashwan, Alaa Elsayad, Matching Criteria in Fractal Image Compression IEEE Midwest Symp. On Circuits and Systems, Aug 2000.

8. Hannes Hartenstein, Associate Member, IEEE, Matthias Ruhl, and Dietmar Saupe, Region-Based Fractal Image Compression, IEEE Trans. on image processing, vol. 9, no. 7, july 2000.

9. M. F. Barnsley, Fractal everywhere, Academic Press, New York, 1988.

10. Y. Fisher, Ed., Fractal Image CompressionTheory and Application.New York: Springer, 1994.

11. Y. Fisher, Fractal Image Compression-Theory and Application. New York: Springer-Verlag, 1994.

12. Martin V Sewell, Fractal Image Compression, MSc Computing Science project report, 1994.

13. http://seminarprojects.com/Thread-fractal- image- compression-seminar-report.