碎形影像壓縮具有高壓縮比又可維持一定程度的影像品質優點，但其壓縮時間的長久一直是研究碎形壓縮的重要議題之一。本篇論文提出利用像素區塊的二維空間轉換成一維空間方式及利用一維空間鄰近像素關係比較來做為預篩選可能成為最佳匹配的定義域區塊(Domain Block)方法。首先對值域區塊(Range Block)及定義域區塊的像素區塊採用Zig-Zag區塊掃描，將區塊的二維空間轉換為一維空間再對每一個像素減去區塊像素平均數後，所求出的數值再利用鄰近的上下數值做除法運算來消除收斂係數，最後求取一維空間數值的平均值當作該區塊一維空間的特徵值。當值域區塊與定義域區塊相似時，其一維空間數值分佈狀況會呈現相似狀態，所以可以比對其一維空間特徵值來預篩選出可能的最佳匹配組合，最後用完全搜尋(Full Search)來尋找最佳定義域區塊。依據本論文方法與完全搜尋，壓縮時間加快了8至15倍，PSNR(Peak Signal-to-Noise Ratio)只損失0.5至1.2。

Fractal image compression has the advantage of high compression ratio and keeping high image quality. However, the long encoding time is one of the major issues of fractal compression.
In this paper, we propose the method that transforms the two-dimensional space of pixel block to the one-dimensional space, and using the relationship of the one-dimensional space between the neighboring pixels as a pre-screening may be the best way to match the domain block
In the first phase, we use the Zig-Zag scanning to the range blocks and domain blocks to transform the two-dimensional space to the one-dimensional space, Each pixel subtracts the mean of the block, and then divides the near value up and down to eliminate the S coefficient to get the final one-dimensional space. The mean of the one-dimensional space is the characteristic value of the block.
When the range block and domain block are similar, the distribution of the one-dimensional space will be similar. Therefore, the characteristic value can be used to pre-select the best match domain block. Finally, the best matching domain block will be found by using the Full Search method. The encoding time improvement ratio of our proposed over the Full Search method is 8-15 times, and there is just 0.5 to 1.2 db image quality degradation.

[1] M.F. Barnsley, Fractal everywhere, New York, Academic, 1988.
[2] A.E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Trans Image Process 1992, 1, 18–30.
[3] Y. Fisher, Fractal Image Compression, Theory and Application, New York, Springer-Verlag, Berlin 1995.
[4] S.K. Ghosh, J. Mukherjee, PP. Das, Fractal image compression, a randomized approach, Pattern Recognition Lett, 2004, 25, 1013–24.
[5] T.K. Truong, C.M. Kung, J.H. Jeng, M.L. Hsieh, Fast fractal image compression using spatial correlation, Chaos, Solitons & Fractals, 2004, 22, 1071–6.
[6] S. Furao, O. Hasegawa, A fast no search fractal image coding method, Signal Processing, Image Communication, 2004, 19, 393-404.
[7] Y. Zhou, C. Zhang, Z. Zhang, Fast Fractal Image Encoding Using an Improved Search Scheme, Tsinghua Science and Technology, 2007, 12, 602-606.
[8] C.K. Lee, W.K. Lee, Fast fractal image block coding based on local variances, IEEE Trans. Image Process., 1998, 7, 888–891.
[9] C. He, S.X. Yang, X. Huang, Variance-based accelerating scheme for fractal image encoding, Electronics Letters, 2004, 40, 115-116.
[10] Y.G. Wu, M.Z. Huang, Y.L. Wen, Fractal image compression with variance and mean, IEEE ICME. Maryland, USA, 2003, 353-356.
[11] D. Saupe, S. Jacob, Variance-based quadtrees in fractal image compression, Electronics Letters, 1997, 33, 46-48.
[12] S.M. Lee, A fast variance-ordered Domain Block search algorithm for fractal encoding, IEEE Trans. Consumer Electronics, 1999, 45, 275-277.
[13] T.K. Truong, J.H. Jeng, I.S. Reed, P.C. Lee, A.Q. Li, A fast encoding algorithm for fractal image compression using the DCT inner product, IEEE Trans Image Process 2000, 4, 529–35.
[14] C.M. Lai, K.M. Lam, W.C. Siu, A fast fractal image coding based on kick-out and zero contrast conditions., IEEE Trans Image Process 2003, 11, 1398–403.
[15] D.J. Duh, J.H. Jeng, S.Y. Chen, DCT based simple classification scheme for fractal image compression, Image and Vision Computing, 2005, 23, 1115-21.
[16] J.J. Kang, Fast fractal image encoding based on contrast pattern classification, NTUST, Dept. of Computer Science and Information Engineering, 2008.