形編碼在碎形壓縮的工程是最消耗性的一部份。在這份報告中，將發表一項新的預測和子區塊的碎形壓縮演算法。剛開始，根據S樹和內插法的分離原理，原始的圖片被分離成一套不同形狀的區塊。第一個階段，每個不同形狀的值域區塊試著要找出最相符的定義區塊，根據剛剛發表的預測方法的尋找方法，這項方法是作用於相關且相鄰的不同形狀的定義區塊，第一階段導致一項重要的計算減少效果，如果這個在所預測尋找空間內被發現的定義區塊不能被接受，在第二個階段中，一個子區塊方法就會被使用來把目前的不同形狀的值域區塊分割成小區塊來增加圖片的品質。實驗結果顯示出我們這預測和子區塊的碎形壓縮演算法表現比傳統的完整找尋演算法和最近由Truong等人發表的以編碼化的時間及圖片品質組成的空間域相關演算法來的要好。另外，由我們所發表的演算法和其他兩個演算法，不使用尋找演算法和四分樹演算法的表現結果比較也會被調查出來。

Fractal encoding is the most consuming part in fractal image compression. In this paper, a novel two-phase prediction- and subblock-based fractal encoding algorithm is presented. Initially the original gray image is partitioned into a set of variable-size blocks according to the S-tree- and interpolation--based decomposition principle. In the first phase, each current block of variable-size range block tries to find the best matched domain block based on the proposed prediction-based search strategy which utilizes the relevant neighboring variable-size domain blocks. The first phase leads to a significant computation-saving effect. If the domain block found within the predicted search space is nacceptable, in the second phase, a subblock strategy is employed to partition the current variable-size range block into smaller blocks to improve the image quality. Experimental results show that our proposed prediction- and subblock-based fractal encoding algorithm outperforms the conventional full search algorithm and the recently published spatial- correlation-based algorithm by Truong et al. in terms of encoding time and image quality. In addition, the performance comparison among our proposed algorithm and the other two
algorithms, the no search-based algorithm and the quadtree-based algorithm, are also investigated.

M. F. Barnsley, Fractals everywhere, Academic Press, San Diego, 1993.

M. F. Barnsley, Fractal image compression, in: Blackledge J.M. (Ed.), Image Processing: Mathematical Methods and Applications, Clarendon ,Oxford, 1997, pp. 183-210.

K. U. Barthel and T. Voy'e, Adaptive fractal image coding in the frequency domain, Proc. Image Processing, 2, June 1994, pp. 33-38.

K. L. Chung and J. G. Wu, Improved image compression using s-tree and shading approachn, IEEE Trans. Communications, 5, 2000, pp. 748-751.

G. M. Davis, A wavelet-based analysis of fractal image compressionn, IEEE Trans. on Image Processing, 2, 1998, pp. 141-154.

F. Davoine and J. M. Chassery, Adaptive Delaunay triangulation for attractor image coding, Pattern Recognition Conf.}, Oct 1994, pp. 801-803.

F. Davoine, J. Svensson, and J. M. Chassery, A mixed triangular and quadrilateral partition for fractal image coding, Proc. Image Processing Conf., 3, Oct 1995, pp. 284-287.

F. Davoine, M. Antonini, J. M. Chassery JM, and M. Barlaud, Fractal image compression based on Delaunay triangulation and vector quantizationn, IEEE Trans. on Image Processing, 2, 1996, pp. 338-346.

Y. Fisher, Fractal image compression, Theory and Application, Springer-Verlag, New York, 1994.

S. Furao and O, Hasegawa, A fast no search fractal image coding method, Signal Processing Image Communication, 5, 2004, pp. 393-404.

P. Fu, X Tang, Y. Zhu, and X Wu, A new fractal block coding scheme based on classification in the wavelet domain, Proc. Vehicle Electronics Conf., 1, 1999, pp. 315-318.

A. E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformn, IEEE Trans. on Image Processing, 1, 1992, pp. 18-30.

A. E. Jacquin, Fractal image coding: a review, Proc. IEEE, 10, Oct 1993, pp. 1451-1465.

J. Kominek, Algorithm for fast fractal image compression, Proc. SPIE, 2419, Feb 1995, pp. 296-305.

J. Li and C. J. Kuo, Image compression with a hybrid wavelet-fractal codern, IEEE Trans. on Image Processing, 6, 1999, pp. 868-874.

M. Nappi, G. Polese, and G. Tortora, FIRST: Fractal Indexing and Retrieval SysTem for image databases, Image Vis. Comput., 14, 1998, pp. 1019-1031.

R. Distasi, M. Nappi, and M. Tucci, FIRE: Fractal indexing with robust extensions for image databasesn, IEEE Trans. on Image Processing, 3, 2003, pp. 373-384.

M. H. Pi and C. H. Li, A novel fractal watermarking technique, Proc. Acoustics, Speech, and Signal Processing Conf., 5, May 2004, pp. 369-372.

D. Saupe and S. Jacob, Variance-based quadtrees in fractal image compression, Electronics Letters, 1, 1997, pp. 46-48.

Saupe and H. Hartenstein, Lossless acceleration of fractal image compression by fast convolution, Proc. Image Processing Conf., 1, Sept. 1996, pp. 185-188.

C. S. Tong and M. Wong, Adaptive approximate nearest neighbor search for fractal image compressionn, IEEE Trans. on Image Processing, 6, 2002, pp. 605-614.

T. K. Truong, J. Jeng, I. S. Reed, P. C. Lee, and A. Q. Li, A fast encoding algorithm for fractal image compression using the DCT inner productn, IEEE Trans. on Image Processing, 4, 2000, pp. 529-535.

T. K. Truong, C.M. Kung, J. H. Jeng, and M. L. Hsieh, Fast fractal image compression using spatial correlation, Chaos, Solitons and Fractals, 3, 2004, pp. 1071-1076.

B. Wohlberg and D. J. Gerhard, A review of the fractal image coding literaturen, IEEE Trans. on Image Processing, 12, 1999, pp. 1716-1729.

Z. Yao, Fixed point in fractal image compression as watermarking, Proc. Image Processing Conf., 2, Sept. 2003, pp. 475-478.