臺灣博碩士論文加值系統

隨著電腦科技與網際網路的蓬勃發展，多媒體資訊的需求量也越益增加。然而不論是聲音、影像、視訊等各種類型的多媒體資訊皆包含了龐大的資訊量，在不進行壓縮的情況下，對有限的儲存空間及傳輸頻寬來說都是極大的負擔。因此要如何減少不必要的資訊量便成了很重要的研究課題。就影像壓縮技術而言，碎形影像壓縮技術(fractal image compression)具有高壓縮率、解析度獨立(resolution independence)及快速解壓縮的優點，但由於它在編碼時所進行的窮舉搜尋法(exhaustive search)需要花費大量的計算時間，因此限制住了它的適用範圍。
在本研究中，主要探討蟻群最佳化演算法(ant colony optimization, ACO)與碎形影像壓縮技術的結合，藉由ACO利用費洛蒙(pheromone)快速搜尋最短路徑的特性，期望能減少碎行影像壓縮編碼過程中尋找最契合區塊的運算複雜度以達到加快編碼的速度。此外，在提升壓縮速度的同時，也會探討ACO各種參數對壓縮速度與影像品質的影響。

Due to the growth of computer science and internet, the information capacity of multimedia data is getting larger. We need a lot of storage space to store all kind of multimedia data, like audio, video, and image. If we don’t compress these multimedia data, it will be a serious load of the storage space and the transmission bandwidth. Therefore, it is an important topic to reduce the redundancy of multimedia data. Fractal Image Compression (FIC) is a kind of image compression technology. FIC possesses the advantages of resolution independence, high compression ratio, and fast decompression process. But, the use of exhaustive search in the encoding process results in a long encoding time and restrict its application.
In this thesis, we propose a method to combine the Ant Colony Optimization (ACO) with FIC. In ACO, the ants can find the shortest path between the nest and food by the pheromone they secreted. We will use this characteristic to reduce the search time in FIC. We will also analyze the affection of all parameters in ACO.

第1章 緒論 1
第2章 碎形影像壓縮 3
2.1. 碎形影像壓縮概念 3
2.2. 碎形影像壓縮編碼流程 4
2.3. 碎形影像壓縮解碼流程 8
第3章 蟻群最佳化演算法 10
3.1. 蟻群最佳化演算法概念 10
3.2. 蟻群最佳化演算法流程 12
3.3. 蟻群最佳化演算法應用於TSP範例 14
3.3.1 使用不同的費洛蒙揮發量 15
3.3.2 使用不同的參數 、 16
3.3.3 改變螞蟻數量以及疊代次數 16
3.3.4 ACO-TSP結論 17
第4章 蟻群最佳化演算法應用於 碎形影像壓縮 19
4.1. 演算法概念與流程 19
4.2. 實驗結果與參數分析 22
4.2.1 改變疊代次數 23
4.2.2 改變 、 25
4.2.3 改變累積量及揮發量 25
4.2.4 改變權重值 26
4.2.5 實驗結果 26
第5章 結論 29
參考文獻 30

[1]M. F. Barnsley and A. D. Sloan, “A better way to compress images”, BYTE magazine, pp. 215-233, Jan. 1988.
[2]A. E. Jacquin, “Image coding based on a fractal theory of iterated contractive image transformations”, IEEE Trans. on image processing, vol. 1, No. 1, pp. 18-30, Jan. 1992.
[3]A. E. Jacquin, “Fractal image coding: A review”, Proc. IEEE, vol. 81, pp. 1451-1465, Oct. 1993.
[4]G. Farhadi, “An Enhanced Fractal Image Compression Based on Quadtree Partition,” Proc. Int. Symp. Image and Signal Processing and Analysis, pp. 213-216, 2003.
[5]D. J. Jackson, W. Mahmound, W. A. Stapleton, and P. T. Gaugan, “Fast Fractal Image Compression Using Quadtree Recomposition,” Image and Vision Computing, Vol. 15, pp. 759-767, 1997.
[6]C. J. Sze, H. Y. Mark Liao, K. C. Fan, M. Y. Chern, and C. K. Tsao, “Fractal Image Coding System Based on an Adaptive Side-coupling Quadtree Structure,” Image and Vision Computing, Vol. 14, No. 6, pp. 401-415, 1996.
[7]D. Saupe and S. Jacob, “Variance-based Quadtree in Fractal Image Compression,” Electronic Letters, Vol. 33, No. 1, pp. 46-48,1997.
[8]D.saupe et al., “Optimal Hierarchical Partitions for Fractal Image Compressopn,” Proc. IEEE Int. Conf. Image Processing, Chicago, IL., Vol. 1, pp. 737-741, Oct. 1998.
[9]N. Ponomatenko, K. Egiazarian, V. Lukin, and J. Astola, “Compression of Image Block Means for Non-equal Block Partition Schemes Using Delaunay Triangulation and Prediction,” IEE Proc. Vision Image Signal Processing, Vol. 150, No. 4, pp. 239-243, 2003.
[10]D. J. Hebert and E. Soundararajan, “Fast Fractal Image Compression with Triangular Multiresolution Block Matching,” Proc. IEEE Int. Conf. Image Processing, pp. 747-750, 1998
[11]J. Signes, “Geometrical Interpretation of IFS based Image Coding,” Fractal, Vol. 5, Suppl., pp. 133-143, July 1997.
[12]R. V. Lototskiy, “Images Fractal Compression Optimization by Means of Artificial Kohonen Neural Networks,” Journal of Automation and Information Sciences, Vol. 35, pp. 50-61, 2003.
[13]R. Hamzaoui, “Codebook Clustering by Self-Organizing Maps for Fractal Image Compression,” Fractals, Vol. 5, Suppl., pp. 27-38, Apr. 1997.
[14]G. Caso, P. Obrador, and C.-C. J. Kuo, “Fast Methods for Fractal Image Encoding,” Proc. SPIE VCIP: Vis. Common Image Process., Vol. 2501, pp. 583-594, May 1996.
[15]B. Bani-Eqbal, “Speeding up Fractal Image Compression,” Proc. SPIE: Still-Image Compression, Vol. 2418, pp. 67-74, Feb. 1995.
[16]B. E. Behnam, “Enhancing the Speed of Fractal Image Compression,” Opt. Eng., Vol. 34, pp. 1705-1710, June 1995.
[17]A Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” Proceedings of the 1st European Conference on Artificial Life, pp.134-142, Paris, 1991.
[18]M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theoretical Computer Science, vol. 344, no. 2-3, pp. 243-278, Nov. 2005.
[19]Gong Daoxiong and Ruan Xiaogang, “A hybrid approach of GA and ACO for TSP,” Proceedings of the World Congress on Intelligent Control and Automation (WCICA), vol. 3, pp. 2068-2072, Jun. 2004.
[20]Jenn-Long Liu, “Rank-based ant colony optimization applied to dynamic traveling salesman problem,” Engineering Optimization, vol. 37, no 8, pp 831-847, DEC, 2005.
[21]Dorigo, M., and Stutzle, T., “Ant Colony Optimization,” MIT Press, 2004, pp, 12-117