2010 International Conference on Computer Applications and Industrial Electronics (ICCAIE 2010), December 5-7, 2010, Kuala Lumpur, Malaysia
Speeding up Fractal Image De-Compression S. Abolfazl Hosseini
[email protected]
Besharat Rezaei Shookooh
Shahriar Beizaee
Dept. Communication Electrical Engineering Islamic Azad University Shahr-e-Rey branch, Tehran, Iran
[email protected] [email protected] [email protected] In this paper, first we propose two algorithms that can obtain more accurate de-compressed image in less iteration by using an initial image which has correlation with the original image. Finally we propose third algorithm that use a highpass filter in coding process. II. SIMULATION ALGORITHM
Abstract- In this paper, we propose three algorithms for fractal image decoding in which the decoding will be done in less iteration, so it would be faster. The first two algorithms are based on using an initial image which has coloration with the original image. In the first algorithm, we save the average of the original image along with the fractal codes, and we use the average image as the initial image. The second algorithm is the same as the first one except that we save the average of each domain. Then in decompression, we substitute the pixels of each range with the average of their corresponding domain, and we use this image as initial image. As the simulation results illustrate, these two algorithms especially the second algorithm accelerate decoding, but at the price of less compression ratio. In the third algorithm, we use the image resulted from a high-pass filter for finding match domains, which astoundingly provides a very high quality image at almost one iteration without any change in compression ratio.
In this algorithm we are using Quadtree partitioning for coding the picture. At first we partition the image into nonoverlapping sections; we call these Ranges. For example we are dealing with an 8-bit image of the size 256 x 256, and the ranges will be the 8 x 8 pixel non-overlapping sub-squares of the image. Therefore we will have 1024 ranges of the size 8 x8. Now we start selecting parts of image that are larger than the ranges, overlapping each other. We call them Domains. So, we have the collection of all (overlapping) sub-squares of the image which here are of the size 16 x 16, and contains 58,081 squares. Now we start searching through all domains for each range to find the one that most looks like the selected range. Beside each square can be mapped in 8 ways to another square therefore for each range we have to search between 8 x 58,081(equal to 464648) domains. Also (1) shows the locative part of transformation. a,b,c,d,e,f can be calculated from the way a matchable domain being mapped on a range. In (2) you can see the general transformation of domain to range which s controls the contrast and o controls the brightness. The transformation has shown with W [1]:
Keywords- Fractal; Compression; De-compression; Iterated Function System; highpass filter
I.
Saeid Shahhosseini
INTRODUCTION
F
RACTAL image compression has excellent characteristics in terms of high compression ratio; however, its compression and decompression processes are time consuming. Some new fast decoding methods have been studied by researchers [2]-[4]. Oien [3] introduced a particular type of contractive transform, and proposed a fast decoding algorithm. Bahara [2] proposed a hierarchical decoding algorithm, where the decoding is started from a low-resolutions initial image. Yan-Min He [5] proposed an algorithm based on extended Fixed-Point Theorem. Pi [6] proposed a new fractal decoding algorithm based on range block mean and contrast scaling. Wang [7] introduced a novel interactive progressive fractal decoding method, with which the compressed file can be transmitted incrementally and reconstructed progressively at users' side. Although these methods are useful, they have restrictions on searching for the matching blocks in the encoding procedure.
978-1-4244-9053-0/10/$26.00 ©2010 IEEE
, x w y z
(1) a c 0
b 0 x d 0 y 0 s z
e f o
(2)
Since the domain’s coordinates are twice the ranges, they have 4 sub-squares, each equal to the size of a range. After that either we have to chose between these 4 sub-squares or take an average between them before starting the comparison.
519
There are three transformation functions in this receiver. In every transformation the initial image will scale down in to half the size and will be mapped in to three side by side locations. The corresponding fractal with this transformation is image (c), and with two selective images (a & b), it was able to reach a good approximation of image (c) after three iteration. But when we give the receiver the exact corresponding fractal with its transformation function, as you can see in Fig.1, in the first iteration the coded image with less MSE will be de-compressed. In this paper we give the receiver two new initial images which have correlations with the original image, so in less iteration we get better results with less MSE. By this, we get less decompressing time while losing a little compression ratio. A. Sending the average of the original image to the receiver By sending the average of the original image to the receiver, 1 Byte will be added to the content of transmitting data which in our example will be increased from 3968 to 3969 Bytes. Practically the compression ratio will not change while in the receiver if we use an initial image with the received average, in less iteration we will achieve a good result and this will speed up our decompression. B. Sending the average of matched domains
To find o & s for any transformation we use this concept that the matched domain should be similar to its comparable range. For that reason, we differentiate (3) according to o & s parameters and put it equal to zero. Results will be (4) & (5). In these equations n is equal to the number of pixels in either domain or range (they are equal now) and a indicate pixel brightness in domain and b for pixel brightness in range [1]: ∑
.
∑
(3) ∑
∑
∑
∑ ∑
∑
(4) (5)
Hence, what we had to do in coding an image, by finding 1024 transformations for the ranges, is done. Now we send the matched domain’s coordinates and their transformation function which inclusive locative mapping and o & s coefficients, to the receiver. The original image needed 65,538 Bytes for the storage while by using this compression it only needs 3,968 Bytes. 8 bits for each direction of x & y to determine the position of domains, 7 bits for o, 5 bits for s to determine a rotation and flip operation for mapping domains to ranges[1] which has 8 ways. Hence, for every transformation we need 31 bits, and to store the whole image we need 3,968 Bytes which means the compression ratio of 16.5:1. What the receiver gets are transformation functions and domain’s coordinates. So, it starts with an arbitrary initial image and after each decompression it uses the decompressed image as initial image to run the process again. We need at least 10 iterations to get an image with small mean square error (MSE) in respect to the original image. Because of too many repetitions in this process it is a big time consumer. In this paper we propose three algorithms that can reduce the number of repetitions for decompressing an image, and the results are significant.
In this method when for each range a matched domain has been found we will send the average of that to the receiver. Therefore in our example 1 byte for each of the 1024 matched domains will be added to transmitting data. Moreover, we will also send the average of the original image to the receiver. The bulk needed for the storage of this image will be 4993 Bytes, and the compression ratio will be 13.12:1 which is a little less than 16.5:1. Therefore, this has a better result in less iteration than the first method. C. Using highpass filter We know that the edges are fractal because they are similar at every scale. In this method we use highpass filter before searching domains for each range in coding process. The result is an image that has high frequency information or edges. The final image which is resulted from using three highpass filters, and it has been shown in Fig.2. We use this final image in the rest of procedures that have been mentioned in other methods. Consider that we do not add anything to the content of transmitting data, so the compression ratio will be the same. Also in the receiver we can use an arbitrary initial image. These are two important advantages of using highpass filter at the price of an additional process in coding.
III.
THREE SUGGESTIONS FOR FAST DECOMPRESSION The major goal in the receiver is that by every time repeating the process over the domains, using transformation functions, it will get us closer approximation of the original image. In the beginning it seems that the initial image does have nothing to do with outcome. The transformation function is unique, and by applying it on any arbitrary initial image it will result in its own fractal, but what will happen if it uses an initial image similar to its fractal. The difference has shown in Fig.1.
520
IV.
Also, we will have better results with less MSE in second proposed algorithm; however, in the method (b), it will cost us a little compression ratio but better speed, and result is worthwhile. Finally in third proposed algorithm we will have decoding as fast as the method (b), while in the method (c), we do not increase compression ratio, and the decoded image is more sharper than the decoded image in method (b), and also the initial image is arbitrary. REFERENCES
SIMULATION RESULTS
We use the standard Lena image of the size 64 x 64 for simulations. Let the ranges be 1 x 1 pixel non-overlapping sub-squares of the image and let domains be the collection of all 4 x 4 pixel (overlapping) sub-squares of the image. By running the simulation algorithm we get the result of Fig.3 after 9 iterations. The initial image is in the upper left side, and after that every iteration result from 1 to 9 with their MSE. The receiver will attain an image with MSE of 112 in respect of the original image after 9 iterations. The initial image in this simulation is arbitrary. Now we assume that the average of the original image has been sent to the receiver, and the receiver will use an initial image with that average. The result is in Fig.4, and it is clear that the receiver has attained the MSE of 111 in 5th iteration which is 4 iterations faster than the general simulation. As you can see in Fig.4, regardless of its speed at 9th iteration it has gotten a better result. The MSE in the general mode at 9th iteration is 112 while in the method (a) it is 92. In the simulation of method (b) while sending the average of the original image, we also send the average of each of the matched domains to the receiver; therefore, got a better initial image. The simulation result is illustrated in Fig.5. In this method the receiver was able to achieve MSE of 85. Therefore not only we got faster results, but also with less MSE. In the simulation of method (c), the receiver was able to achieve MSE of 85 like the second method but the compression ratio didn’t increase, and initial image was the arbitrary image that we used in Fig.3. The simulation result is in Fig.6. Also the decoded image in this method has a better sharpness than the second method caused by better reconstruction in edges. Fig.7 shows convergence graphs of the three methods. Each curve represents MSE between the decoded output image in each iteration and the original image. Moreover, Fig.8 is the same as Fig.7 except that it is the average results for 5 images. Finally, Table 1 provides a comparison between the general algorithm and the three proposed algorithms by providing the results for MSE, Compression Ratio as well as the number of iteration needed to get the MSE=85. V.
CONCLUSION
By sending the average of the original image, which has a small effect on compression ratio, we will have a faster decompression than the time we use arbitrary initial image.
521
[1]
Yoval Fisher. Fractal Image compression Theory and Application. Springer Verlag. New York. 1995.
[2]
Z.Baharav,D.Malah,and E.Karnin , “Hierchical interpretation of fractal image coding and its application to fast decoding ”.in proc. Digital signal processing , july 1993,pp.190-195.
[3]
G.E.Oien and S.lepsoy , “Fractal-based image coding with fast decoder convergence”,signal processing,vol.40,pp.105-117,1994.
[4]
Y.H.Moon,K.R.Baek,Y.S.Kim,and J.H.Kim,”A fast fractal decoding algorithm with convergence criteria”,Opt.Eng.,vol.36,pp.1992-1999,july 1997.
[5]
Yan-Min He; Hou-Jun Wang; , "Fractal Image Decoding Based on Extended Fixed-Point Theorem," Machine Learning and Cybernetics, 2006 International Conference on , vol., no., pp.4160-4163, 13-16 Aug. 2006
[6]
Pi, M.; Basu, A.; Mandal, M.; , "A new decoding algorithm based on range block mean and contrast scaling," Image Processing, 2003. ICIP 2003. Proceedings. 2003 International Conference on , vol.2, no., pp. II271-4 vol.3, 14-17 Sept. 2003
[7]
Huaqing Wang; Qiang Wu; Xiangjian He; Tom Hintz; , "A Novel Interactive Progressive Decoding Method for Fractal Image Compression," Innovative Computing, Information and Control, 2006. ICICIC '06. First International Conference on , vol.3, no., pp.613-617, Aug. 30 2006-Sept. 1 2006
Figure 1– Decompressed images after 3 iterations in the receiver for 3 different initial images [1]. Figure 3 -9 iterations with arbitrary initial image.MSE for initial image and each iteration respectively is : (a)115, (b)153, (c)146, (d)146, (e)146, (f)141, (g)123, (h)119, ( i)116, (j)112.
Figure 2 –final images after three highpass filter :(a)vertical edges (b)horizontal edges (c)inclined edges (d)sum of edges Figure 4– 9 iterations with average of the original image as initial image. MSE for initial image and each iteration respectively is : (a)146, (b)145, (c)129, (d)122, (e)118, (f)111, (g)105, (h)98, ( i)94, (j)92.
522
Figure 5– 9 iterations with initial image that does have the average of the original image & the average of the matched domains. MSE for initial image and each iteration respectively is : (a)146, (b)86, (c)85, (d)85, (e)85, (f)85, (g)85, (h)85, ( i)85, (j)85.
Figure 6-9 iterations with arbitrary initial image that highpass filter is used in coding process. MSE for initial image and each iteration respectively is : (a)115,(b)85,(c)85,(d)85,(e)85,(f)85,(g)85,(h)85,(i)85,(j)85.
Figure 7– convergence graphs of the four methods. Each curve represents MSE between decoded output image in each iteration and the original image.
523
Figure 8- convergence graphs of the four methods which is the average results of five images. Each curve represents MSE between decoded output image in each iteration and the original image.
TABLE 1- compares general and three proposed algorithms by providing MSE, compression ratio and the number iteration needed to get MSE=85. MSE for 9th iteration
Number of iteration for MSE=85
compression ratio
General algorithm
112
15
16.52:1
1-Initial image is arbitrary 2- big time consumer
First suggested algorithm
92
12
16.51:1
Second suggested algorithm
85
2
13.12:1
Third suggested algorithm
85
1
16.52:1
1- Initial image is the average of the original image 2-faster than general algorithm 3-compression ratio doesn’t change 1- initial image that does have the average of the original image & the average of the matched domains 2-more faster than first algorithm 3- compression ratio decreased 1- Initial image is arbitrary 2- more faster than first algorithm 3- compression ratio doesn’t change
algorithms
524
compare
