Further investigation on adaptive search

Ming Hong Pi; Jun Ma; Anup Basu; Mrinal Mandal

Further investigation on adaptive search

View Fulltext

Author(s): Ming Hong Pi¹ ; Jun Ma¹ ; Anup Basu² ; Mrinal Mandal²
- Affiliations: 1: School of Computer Science , Wuhan Textile University , 1 Fangzhi Road , Wuhan 430073 , Hubei , People's Republic of China ;
  2: Department of Computing Science and Department of Electrical and Computer Engineering , University of Alberta , Edmonton , AB , Canada , T6G 2E8
Source: Volume 2014, Issue 5, May 2014, p. 238 – 247
DOI: 10.1049/joe.2014.0037 , Online ISSN 2051-3305

This is an open access article published by the IET under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/)

Received 04/02/2014, Accepted 24/04/2014, Published 01/05/2014

Adaptive search is one of the fastest fractal compression algorithms and has gained great success in many industrial applications. By substituting the luminance offset by the range block mean, the authors create a completely new version for both the encoding and decoding algorithms. In this paper, theoretically, they prove that the proposed decoding algorithm converges at least as fast as the existing decoding algorithms using the luminance offset. In addition, they prove that the attractor of the decoding algorithm can be represented by a linear combination of range-averaged images. These theorems are very important contributions to the theory and applications of fractal image compression. As a result, the decoding image can be represented as the sum of the DC and AC component images, which is similar with discrete cosine transform or wavelet transform. To further speed up this algorithm and reduce the complexity of range and domain blocks matching, they propose two improvements in this paper, that is, employing the post-quantisation and geometric neighbouring local search to replace the currently used pre-quantisation and the global search, respectively. The corresponding experimental results show the proposed encoding and decoding algorithms can provide a better performance compared with the existing algorithms.

References

1. 1)
  - 10. Arya, S., Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.: ‘An optimal algorithm for approximate nearest neighbor searching’, J. ACM, 1998, 45, (6), pp. 891–923 (doi: 10.1145/293347.293348).
2. 2)
  - 16. Kang, H.S., Kim, S.D.: ‘A fractal decoding algorithm for fast convergence’, Opt. Eng., 1996, 35, pp. 3191–3198 (doi: 10.1117/1.601058).
3. 3)
  - 15. Øien, G.E., Lepsøy, S.: ‘Fractal-based image coding with fast decoder convergence’, Signal Process., 1994, 40, pp. 105–117 (doi: 10.1016/0165-1684(94)90024-8).
4. 4)
  - 18. Monro, D.M., Dudbridge, F.: ‘Fractal block coding of images’, Electron. Lett., 1992, 28, (11), pp. 1053–1055 (doi: 10.1049/el:19920667).
5. 5)
  - 22. Wang, X.-Y., Wang, Y.-X., Yun, J.J.: ‘An improved no-search fractal image coding method based on a fitting plane’, Image Vis. Comput., 2010, 28, (8), pp. 1303–1308 (doi: 10.1016/j.imavis.2010.01.008).
6. 6)
  - 4. Fisher, Y.: ‘Fractal image compression: theory and application’ (Springer-Verlag, 1995).
7. 7)
  - 20. Davis, G.M.: ‘A wavelet-based analysis of fractal image compression’, IEEE Trans. IP, 1998, 7, (2), pp. 141–154.
8. 8)
  - X. Wang , Y. Wang , J. JiaoYun . An improved no-search fractal image coding method based on a fitting plane. Image Vis. Comput. , 1303 - 1308
9. 9)
  - 2. Jacquin, A.E.: ‘Image coding based on a fractal theory of iterated contractive image transform’, IEEE Trans. IP, 1992, 1, (1), pp. 18–30.
10. 10)
  - 6. Thomas, L., Deravi, F.: ‘Region-based fractal image compression using heuristic search’, IEEE Trans. IP, 1995, 4, (6), pp. 823–838.
11. 11)
  - E.W. Jacobs , Y. Fisher , R.D. Boss . Image compression: a study of iterated transform method. Signal Process. , 251 - 263
12. 12)
  - 14. Chaurasia, V., Somkuwar, A.: ‘Approximation error based suitable domain search for fractal image compression’, Int. J. Eng. Sci. Technol., 2010, 2, (2), pp. 104–108.
13. 13)
  - 19. Alkhansari, G., Huang, T.S.: ‘Fractal image coding using rate-distortion optimized matching pursuit’. SPIE Proc. Visual Communications and Image Processing, 1996, vol. 2727, pp. 265–304.
14. 14)
  - 11. Bani-eqbal, B.: ‘Enhancing the speed of fractal image compression’, Opt. Eng., 1995, 34, (6), pp. 1705–1710 (doi: 10.1117/12.203134).
15. 15)
  - 15. Øien, G.E., Lepsøy, S.: ‘Fractal-based image coding with fast decoder convergence’, Signal Process., 1994, 40, pp. 105–117 (doi: 10.1016/0165-1684(94)90024-8).
16. 16)
  - 18. Monro, D.M., Dudbridge, F.: ‘Fractal block coding of images’, Electron. Lett., 1992, 28, (11), pp. 1053–1055 (doi: 10.1049/el:19920667).
17. 17)
  - S. Arya , D.M. Mount , N.S. Netanyahu , R. Silverman , A.Y. Wu . An optimal algorithm for approximate nearest neighbor searching fixed dimensions. JACM. , 6 , 891 - 923
18. 18)
  - 17. Moon, Y.H., Kim, H.S., Kim, J.H.: ‘A fast fractal decoding algorithm based on the selection of an initial image’, IEEE Trans. IP, 2000, 9, (5), pp. 941–945.
19. 19)
  - 7. Gartenstein, H., Ruhl, M., Saupe, D.: ‘Region-based fractal image compression’, IEEE Trans. IP, 2000, 9, (7), pp. 1171–1184.
20. 20)
  - 23. Wohlberg, B., Jager, G.: ‘A review of the fractal image coding literature’, IEEE Trans. IP, 1999, 8, (12), pp. 1716–1729.
21. 21)
  - 13. Truong, K., Jeng, J.H., Reed, I.S., Lee, P.C., Li, A.Q.: ‘A fast encoding algorithm for fractal image compression using the DCT inner product’, IEEE Trans. IP, 2000, 9, (4), pp. 529–535.
22. 22)
  - 12. Tong, C., Pi, M.: ‘Fast fractal image compression using adaptive search’, IEEE Trans. IP, 2001, 10, (9), pp. 1269–1277.
23. 23)
  - S. Furao , O. Hasegawa . A fast no search fractal image coding method. Signal Process. Image Commun. , 5 , 393 - 404
24. 24)
  - 24. FracCompress. Available at http://www.inls.ucsd.edu/~fisher/Fractals/.
25. 25)
  - 1. Barnsley, M., Sloan, A.D.: ‘A better way to compress images’, Byte, 1988, 13, pp. 215–233.
26. 26)
  - 5. Davoine, F., Antonini, M., Chassery, J.-M., Barlaud, M.: ‘Fractal image compression based on Delaunay triangulation and vector quantization’, IEEE Trans. IP, 1996, 5, (2), pp. 338–346.
27. 27)
  - 9. Saupe, D.: ‘Fractal image compression via nearest neighbor search’. Conf. Proc. NATO ASI Fractal Image Encoding and Analysis, Trondheim, July 1995.
28. 28)
  - 16. Kang, H.S., Kim, S.D.: ‘A fractal decoding algorithm for fast convergence’, Opt. Eng., 1996, 35, pp. 3191–3198 (doi: 10.1117/1.601058).
29. 29)
  - 8. Belloulata, K., Konrad, J.: ‘Fractal image compression with region-based functionality’, IEEE Trans. IP, 2002, 11, (4), pp. 351–362.
30. 30)
  - 21. Furao, S., Hasegawa, O.: ‘A fast no search fractal image coding method’, Signal Process., Image Commun., 2004, 19, (5), pp. 393–404 (doi: 10.1016/j.image.2004.02.002).
31. 31)
  - 11. Bani-eqbal, B.: ‘Enhancing the speed of fractal image compression’, Opt. Eng., 1995, 34, (6), pp. 1705–1710 (doi: 10.1117/12.203134).
32. 32)
  - 3. Jacobs, E.W., Fisher, Y., Boss, R.D.: ‘Image compression: a study of iterated transform method’, Signal Process., 1992, 29, (3), pp. 251–263 (doi: 10.1016/0165-1684(92)90085-B).

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Further investigation on adaptive search

References

Related content