碎形影像壓縮(Fractal Image Compression)是基於自然影像的自我相似性(Self-similarity)與部分迭代函數系統(Partitioned Iterated Function System, PIFS)的一種失真壓縮技術，其優點在於解壓縮後能保有良好的影像品質、高壓縮率、解壓縮速度快及可調整解析度的特性。
影像重新取樣(Image Resampling)可以將影像調整成不同解析度的大小，本文使用碎形影像壓縮對影像進行編碼並製造碎形碼(Fractal Code)，運用超取樣(Super-sampling)並根據碎形碼來進行解碼，使用該碎形碼將其解碼成比原始影像高解析度的重建影像且確保其影像結構與編碼影像一致，並與其它常見的影像重新取樣法比較差異性。
基於訊號的稀疏性，壓縮感測(Compressed Sensing)能藉由一些求解演算法，利用少數的取樣訊號，重建回原始訊號。本文使用正交匹配追蹤(Orthogonal Matching Pursuit)演算法及LS-OMP演算法架構於碎形影像壓縮，編碼時增加一項對比調整量於碎形碼，解碼後的重建影像能夠達到提昇影像品質的目的。後續使用OMP及LS-OMP編碼結果於解碼時作影像超取樣，將重建影像與其它方法比較。

Fractal image compression (FIC) is a lossy compression technique based on the self-similarity of natural images and partitioned iterated function system (PIFS). It possesses the advantages of high retrieved image quality, high compression ratio, decompression speed quickly, and zoom invariant.
Image resampling can resize images to another resolution. In this thesis, adopt FIC to perform image resampling. In the decoding process, we take the image of higher resolution as the initial image to obtain super-sampled image in which the partition structure is consistent with the original image. The results are compared with other common image resizing methods.
Based on sparse presentation of signals, compressed sensing (CS) uses a few sampling signal to retrieve the original signal via some solving algorithm. In this thesis, we use orthogonal matching pursuit (OMP) and LS-OMP to implement FIC. In encoder, we add one more contrast adjustment term to fractal code. The proposed method increases the image quality. The results are compared with the traditional fractal image compression.

圖目錄II
表目錄IV
致謝V
摘要VII
Abstract VIII
第1章 研究動機與文獻探討1
第2章 碎形影像壓縮3
2.1 碎形影像壓縮編碼3
2.2 碎形影像壓縮解碼7
2.3 解碼影像9
第3章 影像重新取樣11
3.1 鄰近內插法11
3.2 線性內插法12
3.3 立方內插法13
第4章 使用碎形影像壓縮之影像超取樣14
4.1 使用碎形影像解碼之影像超取樣14
4.2 實驗方法與結果比較20
第5章 使用壓縮感測之碎形影像壓縮29
5.1 OMP演算法架構於碎形影像壓縮編碼30
5.2 LS-OMP演算法架構於碎形影像壓縮編碼31
5.3 編碼結果分析32
5.4 實驗結果37
第6章 結論46
參考文獻47
圖目錄
圖2.1 碎形影像壓縮的自我相似性3
圖2.2 定義域與值域集合4
圖2.3 定義域的翻轉型態4
圖2.4 針對字母F的影像做八種翻轉方向5
圖2.5 碎形影像壓縮編碼流程圖6
圖2.6 碎形影像壓縮編碼架構7
圖2.7 碎形影像壓縮解碼架構8
圖2.8 碎形影像解壓縮迭代過程8
圖2.9 四張不同初始影像10
圖3.1 鄰近內插法示意圖11
圖3.2 線性內插法示意圖12
圖3.3 立方內插法示意圖13
圖4.1 傳統碎形影像壓縮解碼示意圖14
圖4.2 使用碎形影像解碼之影像超取樣示意圖15
圖4.3 使用碎形影像解碼之影像超取樣迭代過程16
圖4.4 不同解析度的初始影像解碼測試結果19
圖4.5 不同編碼單位使用碎形影像解碼之影像超取樣22
圖4.6 常見的影像超取樣法放大結果24
圖4.7 影像中不同特徵的區塊24
圖4.8 帽子邊緣區塊使用600%檢視25
圖4.9 眼睛周邊區塊使用600%檢視26
圖4.10 毛髮區塊使用600%檢視27
圖5.1 y=Φx矩陣型態31
圖5.2 分析區塊所屬位置表示圖33
圖5.3 四張不同編碼影像37
圖5.4 Lena影像使用不同編碼方法之重建影像結果38
圖5.5 Lena影像使用不同編碼方法，解壓縮迭代過程趨勢圖38
圖5.6 Baboon影像使用不同編碼方法之重建影像結果39
圖5.7 Baboon影像使用不同編碼方法，解壓縮迭代過程趨勢圖40
圖5.8 F16影像使用不同編碼方法之重建影像結果41
圖5.9 F16影像使用不同編碼方法，解壓縮迭代過程趨勢圖41
圖5.10 Pepper影像使用不同編碼方法之重建影像結果42
圖5.11 Pepper影像使用不同編碼方法，解壓縮迭代過程趨勢圖43
圖5.12 帽子邊緣區塊44
圖5.13 眼睛周邊區塊44
圖5.14 毛髮區塊45
表目錄
表2.1 使用編碼影像Lena對不同初始影像作解碼之測試結果(PSNR)10
表4.1 使用不同編碼單位相關實驗數據20
表5.1 Lena影像區塊位置(128,128)編碼之實驗結果33
表5.2 Lena影像區塊位置(144,176)編碼之實驗結果34
表5.3 Lena影像區塊位置(32,192)編碼之實驗結果34
表5.4 Lena影像區塊位置(232,176)編碼之實驗結果35
表5.5 Lena影像區塊位置(128,24)編碼之實驗結果35
表5.6 Lena影像區塊位置(96,80)編碼之實驗結果36
表5.7 不同方法編碼所需時間(sec.)43

[1]A. Bogdan and H. E. Meadows, “Kohonen Neural Network for Image Coding Based on Iteration Transformation Theory,” Proceedings of SPIE, Vol. 1766, pp. 425-436, 1992.
[2]A. E. Jacquin, “Fractal Image Coding: A Review,” Proceedings of the IEEE, Vol. 81, No. 10, pp. 1451-1465, 1993.
[3]A. E. Jacquin, “Image Coding Based on A Fractal Theory of Iterated Contractive Image Transformations,” IEEE Transactions on Image Processing, Vol. 1, No. 1, pp. 18-30, 1992.
[4]C. L. Chen, S. D. Wang, and B. G. Shan, “A Fractal Image Coding Base on The Quadtree,” International Conference of Signal Processing, 1998.
[5]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.
[6]J. H. Jeng and J. R. Sheu, “Fractal Image Compression with Simple Classification Scheme in Frequency Domain,” Electronics Letters, Vol. 36, No. 8, pp. 716-717, 2000.
[7]J. H. Jeng, C. M. Kung, M. L. Hsieh, and T. K. Truong, “Fast Fractal Image Compression Using Spatial Correlation,” Chaos, Solitons & Fractals, Vol. 22, NO. 5, pp. 1071-1076, 2004.
[8]J. Stark, “A Neural Network to Compute The Hutchinson Metric in Fractal Image Processing,” IEEE Transactions on Neural Network, Vol. 2, No. 1, pp. 156-158, 1991.
[9]J. Stark, “Iterated Function Systems as Neural Network,” Neural Networks, Vol. 4, No. 5, pp. 679-690, 1991.
[10]K. T. Sun, S. J. Lee, and P. Y. Wu, “Neural Network Approaches to Fractal Image Compression and Decompression,” Neurocomputing, Vol. 41, No. 1, pp. 91-107, 2001.
[11]M. F. Barnsley and A. D. Sloan, “A Better Way to Compress Images,” BYTE, Vol. 13, No.1, pp. 215-233, 1988.
[12]M. F. Barnsley and S. Demko, “Iterated Function Systems and the Global Construction of Fractals,” Proceedings of the Royal Society of London, Vol. 399, No. 1817, pp. 243-275, 1985.
[13]M. S. Takruri and D. I. Abu-Al-Nadi, “Fractal Image Compression Using Competitive Neural Network in Frequency Domain,” The 2003 10th IEEE International Conference on Electronics, Circuits and Systems (ICECS-2003), Vol. 1, pp. 96-99, 2003.
[14]M. S. Wu, J. H. Jeng, and J. G. Hsieh, “Schema Genetic Algorithm for Fractal Image Compression,” Engineering Applications of Artificial Intelligence, Vol. 20, No. 4, pp. 531-538, 2007.
[15]M. S. Wu, W. C. Teng, J. H. Jeng, and J. G. Hsieh, “Spatial Correlation Genetic Algorithm for Fractal Image Compression,” Chaos, Solitons and Fractals, Vol. 28, No. 2, pp. 497-510, 2006.
[16]R. Hamzaoui, “Codebook Clustering by Self-Organizing Map for Fractal Image Compression,” Fractals, Vol. 5, No. 1, pp. 27-38, 1997.
[17]S. K. Mitra, C. A. Murthy, and M. K. Kundu, “Technique for Fractal Image Compression Using Genetic Algorithm,” IEEE Transactions on Image Processing, Vol. 7, No. 4, pp. 586-593, 1998.
[18]T. K. Truong, J. H. Jeng, I. S. Reed, P. C. Lee, and A. Q. Li “A Fast Encoding Algorithm for Fractal Image Compression Using the DCT Inner Product,” IEEE Transactions on Image Processing, Vol. 9, No. 4, pp. 529-535, 2000.