Many desirable properties make fractals a powerful mathematic model applied in several image processing and pattern recognition tasks: image coding, segmentation, feature extraction, and indexing, just to cite some of them. Unfortunately, they are based on a strong asymmetric scheme, consequently suffering from very high coding times. On the other side, linear transforms are quite time balanced, allowing them to be usefully exploited in realtime applications, but they do not provide comparable performances with respect to the image quality for high bit rates. In this paper, we investigate different levels of embedding orthogonal linear transforms in the fractal coding scheme. Experimental results show a clear improved quality for compression ratios up to 15？:？1. 1. Originality and Contribution The literature about both linear transform-based image compression (discrete cosine transform—DCT, Discrete Wavelet Transform—DWT) and fractal image coding is sizeable. Nevertheless, there are still few contributions exploring possible fusions of the two approaches. From a theoretic point of view, the novelty of the proposed paper is just to investigate several ways in which the former can embed, or even be embedded in, the latter. As pointed out by the experimental results, fusing these methodologies allows to significantly speed up the fractal coding process, while retaining most of the objective quality of the decoded image, even at high compression rate. This represents a highly desirable feature for image coders in all those applications managing high-resolution images (e.g., GIS, satellite image databases, and cultural heritage). 2. Introduction Fractal image compression is based on the self-similarity property of an image, and performs image compression by applying a series of transformations to the image. To perform image decompression, these transformations are applied iteratively until the system converges, a condition which may be assessed by using the Hutchinson metric. The main disadvantage of previous techniques for fractal image compression is the large amount of computation that they require. Several methods have been proposed in order to speed up fractal image coding [1, 2]. Speedup methods based on nearest neighbour search by feature vectors outperform all the others in terms of decoded image quality at a comparable compression rate [3], but they often suffer from the high dimensionality of the feature vector [4]; Saupe's operator represents a suitable example. To cope with this drawback, dimension reduction techniques are introduced. Saupe
References
[1]
C. He, S. X. Yang, and X. Huang, “Variance-based accelerating scheme for fractal image encoding,” Electronics Letters, vol. 40, no. 2, pp. 115–116, 2004.
[2]
C. M. Lai, K. M. Lam, and W. C. Siu, “Improved searching scheme for fractal image coding,” Electronics Letters, vol. 38, no. 25, pp. 1653–1654, 2002.
[3]
M. Polvere and M. Nappi, “Speed-up in fractal image coding: comparison of methods,” IEEE Transactions on Image Processing, vol. 9, no. 6, pp. 1002–1009, 2000.
[4]
C. Aggarwal, “On the effects of dimensionality reduction on high dimensional search,” in Proceedings of the ACMPODS Conference, pp. 1–11, IBM Thomas J. Watson Research Center, Yorktown, NY, USA, 2001.
[5]
B. E. Wohlberg and G. de Jager, “Fast image domain fractal compression by DCT domain block matching,” Electronics Letters, vol. 31, no. 11, pp. 869–870, 1995.
[6]
J. L. Wu and W. J. Duh, “Feature extraction capability of some discrete transforms,” in Proceedings of the IEEE International Symposium on Circuits and Systems, vol. 5, pp. 2649–2652, June 1991.
[7]
D. J. Duh, J. H. Jeng, and S. Y. Chen, “DCT based simple classification scheme for fractal image compression,” Image and Vision Computing, vol. 23, no. 13, pp. 1115–1121, 2005.
[8]
J. M. Mas Ribés, B. Simon, and B. Macq, “Combined Kohonen neural networks and discrete cosine transform method for iterated transformation theory,” Signal Processing: Image Communication, vol. 16, no. 7, pp. 643–656, 2001.
[9]
Y. Zhao and B. Yuan, “A hybrid image compression scheme combining block-based fractal coding and DCT,” Signal Processing: Image Communication, vol. 8, no. 2, pp. 73–78, 1996.
[10]
T. Kim, R. E. Van Dyck, and D. J. Miller, “Hybrid fractal zerotree wavelet image coding,” Signal Processing: Image Communication, vol. 17, no. 4, pp. 347–360, 2002.
[11]
Y. Zhang and L. M. Po, “Speeding up fractal image encoding by wavelet-based block classification,” Electronics Letters, vol. 32, no. 23, pp. 2140–2141, 1996.
[12]
R. Distasi, M. Nappi, and D. Riccio, “A range/domain approximation error-based approach for fractal image compression,” IEEE Transactions on Image Processing, vol. 15, no. 1, pp. 89–97, 2006.
[13]
J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, 1975.
[14]
J. Kominek, “Waterloo BragZone and Fractals Repository,” January 2007, http://links.uwaterloo.ca/Repository.html.
[15]
Y. Iano, F. S. da Silva, and A. L. M. Cruz, “A fast and efficient hybrid fractal-wavelet image coder,” IEEE Transactions on Image Processing, vol. 15, no. 1, pp. 98–105, 2006.
