### Paper Menu >>

### Journal Menu >>

Journal of Signal and Information Processing, 2013, 4, 176-181 doi:10.4236/jsip.2013.43B032 Published Online August 2013 (http://www.scirp.org/journal/jsip) Study of Symmetry Process Behavior in Fractal Gray Image Compression by Traditional Method Eman A. Al-Hilo, Kawther H. Al-Khafaji College of Education for Girls, Physics Departments, Kufa University, Najaf, Iraq. Email: emanalhilo@yahoo.com Received June, 2013 ABSTRACT This paper studies the effect of symmetry process on the compression parameters of the fractal image compression tech- nique proposed by Jacquin. Two kinds of tests have been conducted. The first all kind of the symmetry operations [0-7] were taken; while the second tests were concentrated on studying the effect of the following parameters Block Size, Step Size, Domain Size on the probability distribution of symmetry operation. The results show that the higher value of PSNR and the lower value of ET occur at even symmetry operation only, but compression ratio is not affected with symmetry process. Also the occurrence probability of even symmetry is more than odd symmetry for all compression parameters. This behaviour can be utilized to reduce the encoding time to 50% with preserving PSNR. Keywords: Image Compression; Zero-Mean; Fractal Image Compression; Symmetry process 1. Introduction Image coding through fractal geometry has proven to be very effective, and fractal image compression is a prom- ising field that has gained efficiency in both memory consumption and high speed transmission. Fractal image coding introduced by Barnsley and Jacquin is the out- come of the study of the iterated function system devel- oped in the last decade [1]. By using IFS techniques and simple deterministic algorithms, images with spatial complexity can be encoded through certain fractal rela- tionships that describe mapping of blocks of images within themselves. This fractal image technique finds similar patterns that exist on different scales/orientations, and at different places in an image. Hence, it allows en- coding of an image file by systematically analyzing it and saving a much smaller set of instructions that can be used to iteratively reconstruct the entire image from those patterns. In fact, this compression technique can be thought of a method eliminating as much redundancy as possible. [2-3] Saup [4] represents selected studies about the influ- ence of symmetry on the quality of fractal codes. After- wards an empirically comparison of the efficiency of domain pools with same size with or without using symmetry blocks follows. The presented results show that the using of symmetry doesn't increase the efficiency of codes. The aim of our project is studding the behavior of symmetry process in the fractal gray image compression. 2. Fractal Image Coding The basic idea of fractal image compression is partition- ing the image into non overlapping range blocks. For every range block a similar but larger domain block is found. There are many ways to partition images. The fixed size partitioning are used in this research because it requires less computational time than the other.[5] For a range block with pixel values (ro,r1,…,rm-1), and the domain block (do,d1…,dm-1) the contractive affine approximation is [6]: osdr ii , (1) where, i r is the optimally approximated ith pixel value in the range block. di is the corresponding pixel value in the domain block. The symbols s,o represent the scaling and offset coefficients, respectively. The scale (s) and offset (o) coefficients are determined by applying the least mean square difference (χ2) criteria between ( r r ) and () values [7]. 12 2 11 0 1m i rr m , (2) 22 0, 0, so (3) The straightforward manipulation of the above equa- tion leads to: Copyright © 2013 SciRes. JSIP Study of Symmetry Process Behavior in Fractal Gray Image Compression by Traditional Method 177 1 0 2 1 0 2 1 0 1 0 1 0 n i n i ii n i n i i n i iii ddn drdrn s, (4) 1 0 2 1 0 2 1 0 1 0 1 0 1 0 2 n i n i ii n i n i ii n i i n i ii ddn ddrdr o, (5) 1111 22 2 0000 1 0 22 2 nnnn iiii iiii n i i rssdrd od ono r i (6) 3. Symmetry Process In order to increase the size of domain pool and, conse- quently, to increase the probability of finding the best (near optimal) approximations for the range blocks, each domain block is transformed by using a set of symmetry transforms (i.e., rotation and flipping), such that eight versions (blocks) are produced for each domain block [8]. The eight symmetry mappings are (identity, rotation 90, rotation 180, rotation 270, reflection-x, reflection with rotation 90, reflection with rotation 180, reflection with rotation 270), (see Table 1). The number of bits required to represent the eight symmetry mapping cases is (3) bits. Table 1. The eight symmetry transformations. Sym Equations Results 0. Identity 0sin0cos yxx 0cos0sin yxy xx yy 1. Rot.(+90) 90sin90cos yxx 90cos90sin yxy yx xy 2. Rot.(+180) 180sin180cos yxx 180cos180sin yxy xx yy 3. Rot.(+270) 270sin270cos yxx 270cos270sin yxy yx xy 4. Ref. at x-axis 0sin0cos yxx 0cos0sin yxy xx yy 5. Ref.& Rot. (90) 90sin90cos yxx 90cos90sin yxy yx xy 6. Ref.& Rot. (180) 180sin180cos yxx 180cos180sin yxy xx yy 7. Ref & Rot. (270) 270sin270cos yxx 270cos270sin yxy yx xy The main disadvantage of using the symmetry map- pings in the encoding process is that more computational time will be required to perform the extra matching processes. 4. Encoding Process The encoding method could be summarized by the fol- lowing steps: 1) Load BMP image and put it in (2D arrays). 2) Establish the range image (array). 3) Down sample the range image to produce the do- main array. 4) Great range and domain pool by partitioning: a) The range array must be partitioned into non-over- lapping fixed blocks, to generate the range blocks (r1,….,rn). b) The domain must be partitioned into overlapping blocks, using specific step size, to generate the domain blocks (d1,…,dn). They should have the same size of range blocks. 5) Searching: For each range block do the following: a) Pick up a domain block from the domain pool. b) Perform one of the symmetry mappings that men- tioned in table (1). c) Calculate the scale (s) and offset (o) coefficient us- ing equations (4) and (5). d) Apply the following condition to bound the value of (s) and offset (o) coefficient: If s< s min then s=smin Else if s >smax then s=smax If o< o min then o=omin Else if o >omax then o=omax e) Quantize the value (s) and offset (o) using equations that referred in [9]. f) Compute the approximation error (χ2) using equa- tion (6). g) After the computation of IFS code and the sum of error (χ2) of the matching between the range and the tested domain block, the (χ2) is compared with registered minimum error (χ2 min); such that: If χ2< (χ2 min) then sopt=is; oopt=io, χ2 min= χ2 PosI=domain block index Sym=symmetry index End if h) If χ2 min < then the search across the domain blocks is stopped, and the registered domain block is considered as the best matched block. i) Repeat steps (4) to (10) for all symmetry states of the tested domain block. j) Repeat steps (3) to (11) for all the domain blocks listed in the domain pool. k) The output is the set of IFS parameters Copyright © 2013 SciRes. JSIP Study of Symmetry Process Behavior in Fractal Gray Image Compression by Traditional Method 178 SymposIiiei os ,,,.,. which should be registered as a set of fractal coding parameters for the tested range block. l) Repeat steps (1) to (12) for all range blocks listed in the range pool m) Store all IFS mapping parameters as an array of record. The length of this array is equal to the number of range blocks in the range pool. 5. Decoding Process The decoding process can be summarized by the follow- ing steps: 1) Generate arbitrary the domain pool, the domain pool could be initialized as a blank image or a piece of image extracted from any available image. 2) The values of the indices of (is) and (io) for each range block should be mapped to reconstruct the quan- tized values of the scale (sq) and offset (oq) coefficients. 3) Choose the number of possible iterations, and the threshold value of the mean square error (TMSE). At each iteration, do the following steps: a) For each range block determine the coordinates (xd,yd), of the best matched domain, from the IFS pa- rameters (posI), in order to extract the domain block (d) from the arbitrary domain image. b) For each range block, its approximation i r is ob- tained by multiplying the corresponding best matched domain block (d) by the scale value (sq) and adding to the result the offset value (oq), according to equation (1). c) The generated i block is transformed (rotated, reflected, or both) according to its corresponding IFS symmetry parameter value (Iso). r d) Put the generated iblock in its position in the de- coded image array (i.e., range image). r e) Check whether there is another range block, if yes then repeat steps (b,c,d) f) Down sample the reconstructed image (range pool) in order to produce the domain pool using the averaging sampling. g) Calculate the mean square error MSE between the reconstructed range and the previous reconstructed range image. If the MSE is greater than TMSE value then the iteration continues and the above steps (a-f) should re- peated; this iteration is continued till reaching the attrac- tor state (i.e., the newly reconstructed range image is very similar to the previous reconstructed image). Oth- erwise the iteration continues till reaching the predefined maximum number of iterations. 6. Tests Results The proposed system was established using Visual Basic (Ver.6.0) and tested on Aser laptop with (2.20GHZ, RMA 956MB) The proposed system had been tested on Lena image (256x256 pixels, 8 bits). The value of the parameters MaxOffset and MinOffset were fixed in all these tests at (255) and (-256) respectively but the other coding pa- rameters were taken as: BlockSize=(4x4), StepSize=2, DomSize= (128x128), ScaleBits=6, OffsetBits=6, Min- Scale=-1.5, MaxScale=3, =0.4,TMSE=0.05. These tests were taking two aspects: 6.1. Symmetry Tests These tests were conducted to investigate the effect of each symmetry operation, subset [0-3], subset [4-7], and full symmetry [0-7], on compression performance pa- rameters. Table 1 shows these effects on the compres- sion parameters MSE, RMSE, PSNR, CR and ET. Table 1. Effect of each, subsets, and full Symmetry on the compression performance parameters. Sym MSE RMSE PSNR CR ET(sec) 0 31.73 5.63 33.12 4.741 11.97 1 40.60 6.37 32.05 4.741 12.38 2 31.71 5.63 33.12 4.741 12.14 3 39.21 6.26 32.19 4.741 12.37 4 33.09 5.75 32.93 4.741 12.03 5 38.60 6.21 32.26 4.741 12.38 6 32.73 5.72 32.98 4.741 12.01 7 38.39 6.19 32.29 4.741 12.38 Subsets and Full Symmetry Operation (0-3) 25.16 5.02 34.12 4.741 45.42 (4-7) 24.39 4.94 34.26 4.741 45.49 (0-7) 21.79 4.67 34.75 4.741 89.67 The results show that best PSNR occur when all sym- metry operations are used. The symmetry (0) appears higher PSNR and lower ET among (8) symmetry opera- tion. CR is not affected by symmetry operation. Figure 1 shows the effects of each symmetry opera- tion alone on the compression performance parameters MSE, RMSE, PSNR, and ET respectively. The results show that the value of MSE, RMSE and ET appear lower at symmetry operations (0,2,4,6) with respect to their values at symmetry (1,3,5,7), But PSNR appears higher at symmetry operations (0,2,4,6) with respect to their values at symmetry operations (1,3,5,7). This indicate that PSNR is behaves inversely with ET. Figure 2 shows a set of the reconstructed images when no symmetry (identical) and full symmetry operations were applied. Copyright © 2013 SciRes. JSIP Study of Symmetry Process Behavior in Fractal Gray Image Compression by Traditional Method 179 Figure 1. Effect of each Symmetry operation on MSE, RMSE, PSNR and ET respectively. Original No Symmetry Full (0-7) PSNR 33.12 34.75 ET 12.36 89.67 Figure 2. Effects of different symmetry on the compression performance parameters. 6.2. Symmetry Distribution Tests In these tests, the numbers of blocks that have the same Symmetry status from [0-7] were counted. The results of these tests are useful to know the most redundant sym- metry case, which is useful to reduce the consumed en- coding time. These tests were concentrated on studying the effect of the following parameters: 1) Block Size: In this test set different BlockSize val- ues (i.e., 2x2, 4x4, 8x8, 16x16) were taken into consid- eration, while the values of the StepSize = 2, DomSize = (128x128) were kept fixed. Table 2 shows the effect of BlockSize parameter on symmetry distribution. The results show that the occurrence probability of even symmetry increases with the increase of BlockSize value. The highest probability is (76%) at BlockSize (16x16) Figure 3 shows the effect of BlockSize on the sym- metry distribution. The results show that the even states (0,2,4,6) have the highest populations of symmetry. 2) Step Size: This subset of tests investigates the effect of different StepSize on symmetry distribution. In this test, different values of StepSize (1,2,3,4) were taken and the values of other coding parameters were fixed at BlockSize = (4x4), DomSize = (128x128). Table 3 illus- trates the effect of StepSize on symmetry distribution. Figure 3. BlockSize effect on the symmetry distribution. Table 2. Effect of BlockSize on the Sym distribution. (BlockSize) Sym 2x2 4x4 8x8 16x16 0 3369 689 236 74 1 2209 366 65 15 2 2792 685 183 45 3 2125 371 66 11 4 1735 648 154 45 5 1210 404 75 17 6 1698 568 156 32 7 1246 365 89 17 Tot 16384 4096 1024 256 Even% 58.56% 63.23% 71.19% 76.56% Odd% 41.44% 36.77% 28.8% 23.44% Table 3. Effect of StepSize on the symmetry distri bution. (StepSize) Sym 1 2 3 4 0 735 689 725 686 1 365 366 368 380 2 665 685 674 674 3 369 371 371 366 4 620 648 578 598 5 401 404 405 399 6 589 568 602 623 7 352 365 373 370 Tot 4096 4096 4096 4096 Even% 63.69% 63.23% 62.96% 63.01% Odd% 36.3% 36.76% 37.04% 36.99% Copyright © 2013 SciRes. JSIP Study of Symmetry Process Behavior in Fractal Gray Image Compression by Traditional Method 180 The results show that the probability of occurrence of even and odd symmetry is not affected by the variation of StepSize value. The highest probability at even sym- metry is (63.69%) at StepSize (1) and at odd symmetry is (37.04) at StepSize (3). Figure 4 shows the effect of StepSize on symmetry distribution. Figure 4. StepSize effect on the Symme try distribution. 3) Domain Size: This subset of tests was conducted to investigate the effect of DomSize on the symmetry dis- tribution. The value of DomSize was varied to (128x128, 64x64, 32x32, 16x16), while the values of other coding parameters were taken at BlockSize = (4x4), StepSize = (2). Table 4 shows the effect of DomSize on symmetry distribution. Table 4. Effect of DomSize on the Symmetry distribution. (DomSize) Sym 128 64 32 16 0 689 676 697 855 1 366 353 333 312 2 685 693 728 720 3 371 355 337 300 4 648 624 639 617 5 404 359 346 315 6 568 679 639 622 7 365 357 377 355 Tot 4096 4096 4096 4096 Even% 63.23% 65.23% 65.99% 68.70% Odd% 36.77% 34.77% 34.01% 31.29% The results show that the probability of occurrence of even symmetry increases with the increase of DomSize value, but at odd symmetry decrease with the increase of DomSize value. The highest probability is (68%) at DomSize (16x16) at even symmetry and (36.77%) at DomSize (128x128) at odd symmetry. Figure 5 shows the effect of DomSize on symmetry distribution. Figure 5. DomSize effect on the symmetry distribution. 7. Conclusions From the above listed results could be concluding the following: 1) The higher value of PSNR at even symmetry and the lower value of ET at even symmetry also, but CR is not affected with symmetry process. 2) The Most probable symmetry state is (0: identical symmetry) for all compression parameters (BlockSize, StepSize and DomSize). 3) The occurrence probability of even symmetry (0,2,4, 6) is more than odd symmetry The high probability of occurrence of even symmetry could be utilized as an efficient way to reduce the en- coding time in matching process. So, instead of using (8) symmetry operations one can use only the even symme- try operations (2,4,6,8). In such a case, the expected re- duction in encoding time will be around 50%. REFERENCES [1] A. Jacquin, “Fractal Image Coding a Review,” Process ding of the IEEE, Vol. 81, 1993, pp. 1451-1465. [2] M. F. Barnsley, “Fractals Everywhere,” New York Aca- demic, second edition. [3] A. Kapoor, K. Arora, A. Jain and G. P. Kapoor, “Stochas- tic Image Compression Using Fractals,” International conference on Information Technology: Coding and Computing (ITCC 2003) Las Vegas, Nevada, Pg. 574-579, 28-30 April 2003. [4] D. Saupe, “The Futility of Square Isometries in Fractal Image Compression,” IEEE Int. Conf. On Image Proc- essing (ICIP96), Lausanne, Sept. 1996. [5] M. Schebe, “Square Isometries as Integer Part of Fractal Transformation- An Analysis ,” FREQENZ,12 De,1996. [6] Y. Fisher, “Fractal Image Compression Theory and Ap- plication,” University of California, Institute for Nonlin- ear Science, Springer-Verlay, New York, Inc, 1995. [7] Y. Fisher, “Fractal Image Compression,” SIGARAPH 92 Course Notes, the San Diego Super Computer Center, Copyright © 2013 SciRes. JSIP Study of Symmetry Process Behavior in Fractal Gray Image Compression by Traditional Method Copyright © 2013 SciRes. JSIP 181 University of California, an Diego, 1992 [8] C. Frigaard, “Fast Fractal 2D/3D Image Compression, Report,” Institute of Electronic Systems, Alborg Univer- sity, Laboratory of Image Analysis, 1995. [9] E. A. Al-Hilo, “Loay E. George, "Fractal Color Image Compression,” 4th International Conference on Nov. 2008 (ICIMU’ 2008), Malaysia. |