此篇論文提出了一個新的混合式碎形影像壓縮法植基於S樹資料結構。輸入的影像將會先被分解至一個二分樹，且利用修改後的S樹表示法來表示，其樹葉節點將被區分為兩種型態：利用同次樹葉來表示同次區塊，非同次樹葉來表示非同次區塊。每一個非同次樹葉所表示的區塊將會利用碎形影像壓縮技術進行編碼；而每一個同次樹葉所表示的區塊則只儲存其四個角點像素之值。一個同次樹葉編碼時所需要的位元數小於非同次樹葉編碼時所需要的位元數，因此我們提出的混合式碎形影像壓縮將具有節省空間與編/解碼時間的優點。在實驗結果中，針對四張知名的測試影像，比較近年來提出的植基於空間關聯性的碎形影像壓縮法、植基於預測與分級區塊的碎形影像壓縮法，我們的混合式碎形影像壓縮法擁有最好的編/解碼時間、影像品質與壓縮比表現；比較傳統的全搜尋碎形影像壓縮則擁有更好的編/解碼時間與壓縮比表現，且只有些許的影像品質下降。實驗結果更比較了其他植基於S樹的影像壓縮法：傳統的S樹表示法與植基於空間與DCT域的影像壓縮法，在相同的壓縮比下，我們的方法擁有最好的影像品質。

In this thesis, a novel S–tree–based hybrid fractal image compression is presented. The input image is first decomposed into a binary tree and then it is represented by a modified S–tree representation where the leaves are partitioned into two types, the homogeneous leaves for representing homogeneous blocks and the nonhomogeneous leaves for representing nonhomogeneous blocks. For each nonhomogeneous leaf, it is encoded by using the fractal coding approach; for each homogeneous leaf, it is encoded by saving the four corners of the corresponding block. Because the number of bits required to encode one
homogeneous leaf is less than that with the same size required to encode one nonhomogeneous leaf, our proposed hybrid fractal image compression method has the compression–saving and encoding/decoding time–saving benefits. Based on four well known testing images, experimental results show that our proposed hybrid fractal image compression method has the best encoding/decoding–time, image quality, and compression performance when compared with the recently published spatial–correlation–based algorithm and the prediction– and subblock–based algorithm; has better encoding/decoding–time and compression performance when compared with the conventional full search method, and just has little image quality degradation. In addition, experimental results also show that with the same average bit rate, the decoded image quality performance of our proposed method outperforms previous two S–tree based methods, the traditional S–tree method and the spatial– and DCT–based method.

[1] Barnsley, M. F., 1988. Fractal everywhere. New York: Academic.
[2] Jacquin, A. E., 1992. Image coding based on a fractal theory of iterated contractive image transformations. IEEE Trans Image Process 1, 18–30.
[3] Chung, K. L., Hsu, C. H., 2006. Novel prediction– and subblock–based algorithm for fractal image compression. Chaos, Solitons & Fractals 29, 215–222.
[4] Davoine, F., Chassery, J. M., 1994. Adaptive delaunay triangulation for attractor image coding. In: The 12th international conference on pattern recognition, 801–803.
[5] Davoine, F., Svensson, J., Chassery, J.M., 1995. A mixed triangular and quadrilateral partition for fractal image coding. In: Proceedings of international conference on image Processing 3, 284–287.
[6] Davoine, F., Antonini, M., Chassery, J. M., Barlaud, M., 1996. Fractal image compression based on delaunay triangulation and vector quantization. IEEE Trans Image Process 2, 338–346.
[7] Fisher, Y., 1994. Fractal image compression: theory and application. New York: Springer–Verlag.
[8] Saupe, D., Jacob, S., 1997. Variance–based quadtrees in fractal image compression. Electron Lett 1, 46–48.
[9] Jackson, D. J., Mahmoud, W., W. A. Stapleton, P. G., 1997. Faster fractal image compression using quadtree recomposition. Image and Vision Computing 15, 759–767.
[10] Sze, C. J., Liao, H. Y., Fan, K. C., Chern, M. Y., Tsao, C. K., 1996. Fractal image coding system based on an adaptive side-coupling quadtree structure. Image and Vision Computing 14, 401–415.
[11] Barthel, K. U., Voye, T., 1994. Adaptive fractal image coding in the frequency domain. In: Proceedings of international workshop on image processing, 33–38.
[12] Duh, D. J., Jeng, J. H., Chen, S. Y., 2005. Dct based simple classification scheme for fractal image compression. Image and Vision Computing 23, 1115–1121.
[13] Furao, S., Hasegawa, O., 2004. A fast no search fractal image coding method. Signal Process Image Commun 5, 393–404.
[14] Kominek, J., 1995. Algorithm for fast fractal image compression. In: Processings of SPIE 2419, 296–305.
[15] Kov′acs, T., 2008. A fast classification based method for fractal image encoding. Image and Vision Computing 26, 1129–1136.
[16] Truong, T. K., Jeng, J. H., Reed, I. S., Lee, P. C., Li, A. Q., 2000. A fast encoding algorithm for fractal image compression using the dct inner product. IEEE Trans Image Process 4, 529–535.
[17] Truong, T. K., Kung, C. M., Jeng, J. H., Hsieh, M. L., 2004. Fast fractal image compression using spatial correlation. Chaos, Solitons & Fractals 22, 1071–1076.
[18] Wang, X. Y., Wang, S. G., 2008. An improved no–search fractal image coding method based on a modified gray–level transform. Computers and Graphics 32, 445–450.
[19] Wu, M. S., Teng, W. C., Jeng, J. H., Hsieh, J. G., 2006. Spatial correlation genetic algorithm for fractal image compression. Chaos, Solitons & Fractals 28, 497–510.
[20] Wu, X., Jackson, D. J., Chen, H. C., 2005. A fast fractal image encoding method based on intelligent search of standard deviation. Computers and Electrical Engineering 31, 402–421.
[21] Tseng, C. C., Hsieh, J. G., Jeng, J. H., 2008. Fractal image compression using visualbased particle swarm optimization. Image and Vision Computing 26, 1154–1162.
[22] Cardinal, J., 2001. Fast fractal compression of greyscale images. IEEE Trans Image Process 10, 159–163.
[23] Wang, Z., Zhang, D., Yu, Y., 2000. Hybrid image coding based on partial fractal mapping. Signal Process Image Commun 15, 767–779.
[24] Distasi, R., Nappi, M., Riccio, D., 2006. A range/domain approximation error–based approach for fractal image compression. IEEE Trans Image Process 15, 89–97.
[25] He, C., Xu, X., Yang, J., 2006. Fast fractal image encoding using one–norm of normalised block. Chaos, Solitons & Fractals 27, 1178–1186.
[26] Lai, C. M., Lam, K. M., Siu, W. C., 2003. A fast fractal image coding based on kick–out and zero contrast conditions. IEEE Trans Image Process 11, 1398–1403.
[27] Wang, C. T., Chen, T. S., He, S. H., 2003. Detecting and restoring the tampered images based on iteration-free fractal compression. Journal of Systems and Software 67, 131–140.
[28] Chang, C. C., Chiang, C. L., Hsiao, J. Y., 2005. A dct-domain system for hiding fractal compressed images. Proceedings of The First International Workshop on Information Networking and Applications 2, 83–86.
[29] Chung, K. L., Wu, J. G., 2000. Improved image compression using s–tree and shading approach. IEEE Trans Commun 5, 748–751.
[30] Chung, K. L., Liu, Y. W., Yan, W. M., 2006. A hybrid gray image representation using spatial- and dct-based approach with application to moment computation. J. of Visual Communication and Image Representation 17, 1209–1226.