Fast Search Strategies using Optimization Techniques for Fractal Image Compression

Fast Search Strategies using Optimization Techniques for Fractal Image Compression

Proceedings of International Conference ICSEM13

B.PARTHIBAN

M.E Student Department Of CSE Annamalai University

Parthi.it089@gmail.com

A.KRISHNAMOORTHY

Visiting faculty Department Of ECE University College of Engineering

panruti krishpci89@gmail.com

E.SOPHIYA

M.E Student Department Of CSE Annamalai University

V enus.sophiya@gmail.com

ABSTRACT

In this paper fractal image compression encoding procedure is time-consuming due to on full search mechanism. In order to speedup the encoder, it adopts particle swarm optimization method performed under classification and Dihedral transformation to reduce the encoding time. This PSO based proposed technique is used for the mean square error (MSE) based on the stopping criterion between range block and domain block. Dihedral transformation, only four transformations for each domain block are considered so as to reduce the encoding time. An experimental result on encoding time of the proposed method is faster than that of the conventional methods on good image quality.

Keywords

Fractal image compression, particle swarm optimization, Dihedral transformation, discrete wavelet transform, Encoding time.

1. INTRODUCTION

   The idea of the image redundancies can be efficiently exploited by means of block self-affine transformations may call the fractal image compression (FIC). based on the partitioned iteration function system (PIFS) which utilized the self-similarity on first practical fractal image compression scheme was introduced in 1992 by Jacquin[1]. The fractal transform for image compression was introduced in 1985 by Barnsley and Demko. The very high encoding time is the main disadvantages because of exhaustive search strategy. Therefore, decreasing the encoding time is an interesting research topic for FIC.

   One way of decreasing the encoding time is by using stochastic optimization methods using Genetic Algorithm (GA) this recent topics of GA-based methods are proposed to improve the efficiency [2].

   The idea of special correlation of an image is used in these methods while the chromosomes in GA consist of all range blocks which leads to high encoding speed[3].

   Other researchers focused on improvements by tree structure search methods of the search process and parallel search methods [4, 5] or quad tree partitioning of range blocks to make it faster.

   Wavelet transform is used to decompose the original image to various frequency sub bands in which the attributes can be extracted from the wavelet coefficients belonging to different sub-bands. The distribution of wavelet coefficients can be used in context based multiscale classification of document image[6]. The fast and efficient algorithm[7] was applied to triangular mesh to approximate surface data using wavelet transform coefficients. It directly determined local area complexity in an image and divides square cells depending on complexity. In implemented a hybrid image classification method combining wavelet transform, rough set approach, and artificial neural network. Zou and Li have proposed image classification using wavelet coefficients in low-pass bands [8]. This approach was based on the distribution of histograms of the wavelet coefficients.

   In this paper, it use particle swarm optimization method to reduce the search space for FIC. If the two blocks are not of the same type no similarity will not be calculated. The classification method is to partition all of the blocks in domain pool and range pool into three classes according to third level wavelet coefficients. Each range block calculates the similarity measure only with the domain block from the same class. In the meanwhile, we consider the special property of the Dihedral transformation so that only four transformations are required to calculate the similarity. Therefore the encoding time can be further reduced. Experiments are

   761

   B.Parthiban,A.Krishnamoorthy,E.Sophiya

   conducted on 1 image using 4 methods including the full search method, discrete wavelet transform (DWT), PSO, and the proposed method. Experimental results show that the proposed method outperform all the other 3 methods. In average, the proposed method is about 178 times faster in comparison to the full search method with only 1.46 dB decay in image quality. Comparing to Wus schema genetic algorithm (SGA) [2], the proposed method is better than the performance of SGA

   method. Moreover, the encoding speed of the proposed

   additional flip along the main diagonal line, respectively.

   The fractal coder also allows the adjustment of the contrast scaling p and the brightness offset q on the block u. Thus the similarity is to minimize the quantity e = || p uk + q v||, where uk = Tk(u), 0 k 7, are the 8 orientations of u. By direct computation, p and q can be computed by

   2

   method is about 174 times faster than that of the full

   p n

   uk , v

   uk , I v, I

   search method, while the penalty of 0.9 dB decays for retrieved image quality.

   2

   2

   n uk ,uk uk , I

2. FRACTAL IMAGE COMPRESSION

   In local self-similarity property in a nature images. The fundamental idea is coming from the Partitioned Iterated Function System (PIFS). Suppose the original gray level image f is of size m × m. Let the range pool R be defined as the set of all non-overlapping blocks of size n × n of the image f, which makes up (m/n) 2 blocks. For obeying the Contractive Mapping Fixed- Point the domain block must exceed the range block in length. Let the domain pool D be defined as the set of all possible blocks of size 2n × 2n of the image f, which makes up (m 2n + 1)2 blocks. For m is 256 and n is 8, the range pool R is composed of (256/8) × (256/8) = 1024 blocks of size 8 × 8 and the domain pool D is composed of (256 16 + 1) × (256 16 + 1) = 58081

   blocks of size 16 × 16. For each range block v from the R, in the fractal affine transformation is constructed by searching all of the domain blocks in the D to find the most similar one and the parameters representing the fractal affine transformation will form the fractal compression code for v.

   To execute the similarity measure between range block and domain block, In the size of the domain block must be first sub-sampled to 8 × 8 such that its size is the same as the range block v. Let u denote a sub-sampled domain block. The similarity of two image blocks u and v of size n × n is measured by mean square error (MSE) define

   q v , I puk , I

   L 2

   where L2 is the number of pixels in the block of the range pool 8 × 8 vector with all entries being 1, and the Euclidean inner product of two vectors. Finally, the position (i, j) of the domain block (after sub-sampled, it is denoted by u), the contrast scaling p, the brightness offset q, and the orientation k constitute the fractal code of the given range block v. For each range block v, it will make up a fractal code of i, j, k, p and q.

   Table 1.The 8 transformations in the Dihedral group

   T0		T1		T2	T3
   1 0	0 1	1 0	0 1	1 0 0 1	1 0	0 1
   T4		T5		T6	T7
   0 1	1 0	0 1	1 0	0 1 1 0	0 1	1 0

   In the decoding process, In first make up the 1024 affine transformations from the compression codes. We choose one arbitrary image as the initial image and then perform the 1024 affine transformations on the image to obtain a new one. The transformation is proceeded

   S(u, v) 1 n1 n1

   n n j 0 i0

   (u(i, j) v(i, j))2 .

   (1)

   recursively.

   According to Contractive Mapping Fixed-Point sequence of image will converge. The stopping criterion

   The fractal transformation allows the eight Dihedral transformations in Table 1, Tk: k = 0, , 7, of the domain blocks. If the coordinate origin is assumed to locate at the center of the block, the transformations T1 and T2 correspond to flip the block along horizontal and vertical line, respectively. T3 is the flip along both horizontal and vertical lines. T4, T5, T6 and T7 are the transformations of T0, T1, T2 and T3 performed by an

   of the recursion is designed according to users application and the converged image is the retrieved image of fractal coding.

3. FAST FRACTAL IMAGE ENCODING

   1. Particle Swarm Optimization (PSO)

      A population-based algorithm is PSO for searching global optimum. To simulate a simplified social

      762

      B.Parthiban,A.Krishnamoorthy,E.Sophiya

      behavior is the way of original idea of PSO[9]. Similar to the crossover operation of the GA, in PSO the particles are adjusted toward the best individual experience (PBEST) and the best social or global experience (GBEST). However, PSO is unlike a GA, why because in that each potential solution, particle is flying through hyperspace with a velocity, the particles and the swarm have memory for process; in the population of the GA memory does not exist.

      Let xj,d(t) and vj,d(t) denote the dth dimensional value of the vector of position and velocity of jth particle in the swarm, respectively, at time t. The PSO model can be expressed as

      2 are random numbers, and c1 and c2 represent the individuality and sociality coefficients, respectively.

      The steps involved here is the population size is first determined, and the velocity and position of each particle are initialized. Each particle moves according to fitness is then calculated. Meanwhile, the best positions of each swarm and particles are recorded. Finally, as the stopping criterion is satisfied, the best position of the swarm is the final solution. The block diagram of PSO is displayed in and the main steps are given as follows:

      • Set the swarm size. Initialize the velocity and the position of each particle randomly.

      * # For each j, evaluate the fitness value of xj and

      x

      vj,d (t)vj,d (t 1)c1.1.(xj,d xj,d (t 1))c2.2.(xd xj,d (t 1))

      xj,d (t)xj,d (t 1)vj,d (t),

      update the individual best position fitness is found.

      *

      j ,d

      if better

      x

      *

      Where j,d (PBEST) denotes the best position of jth

      x#

      • Find the new best position of the whole swarm. Update the swarm best position x# if the fitness of the new best position is better than that of the previous swarm.

        particle up to time t-1 and

        d (GBEST) denotes the

      • If the stopping criterion is satisfied, then stop.

      best position of the whole swarm up to time t-1, 1 and

      Fig 1.(a) Orignal image of Lena Fig 1. (b) Full Search Fig 1. (c)Wavelet Classification

      Fig 1. (d) PSO Fig 1. (e) SGA Fig 1. (f) Proposed method

   2. Dihedral Transformation

      To each range block, we must calculate the similarity measure with all eight transformed blocks of domain block according to the Dihedral transformations find the best match. The relations of F10 and F01 after applying Dihedral transformations, It is clear that all items are ± F10 or ± F01. This fact can be utilized to further reduce the encoding time. For example, the transformation T1 is to flip the block along the horizontal line. relations between the coefficients of the T1 transformed block to the original block f can be easily calculated as it

      separate the unit circle in the first quadrant into two regions 1 and 2 according to the line = 45°. For a given range block v, we pick a domain block u. If u and v are located in the same region, say 1, then we need only four Dihedral transformations, Tk: k = 0~3 performed on u because the transformations Tk: k = 4~7 will move u another region i.e., 2. The 4 transforms Tk: k = 0~3 or Tk: k = 4~7 have the same edge directions since their |F10| and |F01| are the same. Therefore, there are only four MSE computations required. On the other hand, if u and v are located in the different region, then

      763

      B.Parthiban,A.Krishnamoorthy,E.Sophiya

      we need only four Dihedral transformations, i.e., Tk: k = 4~7. From the argument above, the amount of MSE computations will be reduced two times.

4. PROPOSED METHOD

   In the proposed fast fractal encoding using PSO, reduce the encoding time by reducing the searching time to find a best match domain block for the given range block from all domain blocks.

   1. Set the swarm size must be proportional to (N- 2L+1)2/(maximum no. of iterations for PSO) and initialize the each particle velocity and the position randomly

   2. The fitness value includes finding , MSE between domain block specified by the particles position and given range block

   3. Update swarm best position if the fitness of the new best position is better than that of the previous swarm.

   4. If swarm best position is not changed for some percentage of maximum iteration for PSO, then stop

   5. The best position of the particles is updated

5. EXPERIMENTAL RESULTS

   The results have been compared to the full search FIC mentioned in the previous sections in terms of encoding time and PSNR of fast fractal encoding using PSO.

   The distortion or error between the original image f and the decoded image g caused by lossy compression process is measured in peak signal to noise ratio (PSNR) defined by

   2552

   PSNR 10 log10 MSE( f , g)

   Table 3. Simulation results for CPU time(s) and comparison.

   Image	Lena
   Full search	1433. 260
   Wavelet Classification	482. 945
   PSO	41. 267
   SGA	14. 600
   Proposed Method	8. 520

   Table 4. Simulation results for MSE Computation and comparison.

   Image	Lena
   Full search	475,799,542
   Wavelet Classification	158,664,808
   PSO	10,166,262
   SGA	2,835,477
   Proposed Method	2,114,244

   see Figure . 1 (a) show the original image for decoding, see Figures. 1(b)- (c) (d) (e) (f) show retrieved images of Full Search, Wavelet Classification, PSO,SGA and proposed methods have PSNR 26.910 dB, 26.812 dB 25.643 dB, 25.338 dB, 9.2150 dB respectively. executing times, The results of the proposed method is listed in the tabular column. Compared to the Full search method, the speedup ratio is about three times faster. The detailed results of PSNR, executing time, and the amount of MSE computations and CPU time of

   the image listed in Tables (2-3-4) respetively. The retrieved image qualities are very close. The CPU time

   of the proposed method is 8.520 seconds, which is the

   where MSE is defined (1) in The tested image on Lena in which each is a gray scale image of size 256 × 256 selected from the CVG-UGR image database[10] The related PSO parameters swarm size, number of clusters, and inertial weight, are set as 40, 4 and 0.9, respectively. The velocity in is limited in and the maximal number of iterations is set as 30.

   Table 2. Simulation results for PSNR and comparison.

   Image	Lena
   Full search	26. 910
   Wavelet Classification	26. 812
   PSO	25. 643
   SGA	25. 338
   Proposed Method	9. 2150

   least. The speedup ratio with respect to the full search method shown in that is low. Under the condition of similar quality of decoded images, the encoding time of the proposed method reduces about 1.78 times which is better than that of the SGA method. As an complexity analysis, the amount of MSE computations in of the proposed method for lena image is 2,114,244 which is

   225 times of the amount of the full search method, which is shown in the last column. As demonstrated, the proposed method has better performance that that of other methods.

6. CONCLUSION

   In this paper, particle swarm optimization method is adopted with classification and Dihedral transformation in order to speedup the fractal image encoder. By using particle swarm optimization (PSO) based proposed method for fractal coding can reduce CPU time, PSNR and MSE Values and produces better compression ratio

   764

   B.Parthiban,A.Krishnamoorthy,E.Sophiya

   at acceptable quality, when comparing with existing full search, wavelet classification and SGA methods.

7. REFERENCES

1. E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Transactions on Image Processing, Vol. 1, 1992, pp. 18-30.

2. M. S. Wu, J. H. Jeng, and J. G. Hsieh, Schema genetic algorithm for fractal image compression, Engineering Applications of Artificial Intelligence, Vol. 20, 2007, pp. 531-538.

3. T. K. Truong, C. M. Kung, J. H. Jeng, and M. L. Hsieh, Fast fractal image compression using spatial correlation, Chaos, Solitons and Fractals, Vol. 22, 2004, pp. 1071-1076.

4. C. Hufnagl, A. Uhl, Algorithms for fractal image compression on massively parallel SIMD arrays, Real-Time Imaging 6 (2000) 267281.

5. D. Vidya, R. Parthasarathy, T.C. Bina, N.G. Swaroopa, Architecture for fractal image compression, J. Syst. Archit. 46 (2000) 12751291.

6. J. Li and R. M. Gray, Context-based multiscale classification of document images using wavelet coefficient distributions, IEEE Transactions on Image Processing, Vol. 9, 2000, pp. 1604-1616.

7. H. J. Yu and J. B. Ra, Fast triangular mesh approximation of surface data using wavelet coefficients, The Visual Computer, Vol. 15, 1999, pp. 1432-2315.

8. W. Zou and Y. Li, Image classification using wavelet coefficients in low-pass bands, in Proceedings of International Joint Conference on Neural Networks, 2007, pp. 114-118.

9. M.S. Wu, W.C. Teng, J.H. Jeng, J.G. Hsieh, Spatial correlation genetic algorithm for fractal image compression, Chaos Solitons & Fractals 28 (2) (2006) 497510.

10. CVG-

UG Image Database,2007, http://decsai.ugr.es/cvg/ dbimagenes/index.php.

B.Parthiban received the B.E degree from the Department of Information Technology, Annamalai University, Chidambaram, in 2009 and Currently, he is doing ME degree from the Department of Computer Science and Engineering in 2013, Annamalai University, Chidambaram, current research interests is an image processing.

A.Krishnamoorthy received the B.E degree from the Department of Electronics and Communication Engineering, IFET college of Engineering, Villupurm in 2009 and ME degrees from the Department of Process Control And Instrumentation Engineering in Annamalai University, Chidambaram in 2011, Currently, he is working as a Visiting Faculty(Teaching Fellow) in university college of Engineering pantruti, pantruti from the Department of Electranics and Communication Engineering. current research interests is an Optimization Techniques.

E.sophiya received the B.E degree from the Department of Computer Science and Engineering, Ponnaiyah Ramajayam College of Engineering Technology, Vallam,Thanjavur in 2011 Currently, she is doing ME degree from the Department of Computer Science and Engineering, Annamalai University,Chidambaram, current research interests is an image processing.

765

B.Parthiban,A.Krishnamoorthy,E.Sophiya