( 您好!臺灣時間:2021/04/12 05:25
字體大小: 字級放大   字級縮小   預設字形  


研究生(外文):Chao-Cheng Yang
論文名稱(外文):ST-ACO:Image Compression Using An Adaptive Self-Organizing Tree Approach
指導教授(外文):Cheng-Fa Tsai
外文關鍵詞:lossy image compressionACO algorithmdynamicdatadata clustering
  • 被引用被引用:0
  • 點閱點閱:200
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文與著名的TSVQ演算法、GLA/LBG演算法、S-TREE演算法、GATSM演算法比較“有損失式影像壓縮(Lossy Image Compression)”的壓縮品質(PSNR)及編碼訓練時間(Codebook Time)有效性,實驗結果顯示,本論文提出的方法在壓縮品質上比樹狀結構的TSVQ演算法、S-TREE演算法有較佳的PSNR值,訓練時間上則比LBG、GATSM所需的時間要短。
Multimedia data transmission and storage are very important topics in information technology applications nowadays. Data compression is the key element to achieve these goals. In this thesis, a modified self-organizing tree algorithm is proposed, which is a binary tree searching method. We embed not only the dynamic path selection method to reduce the tree searching bias, but also the concept of ACO algorithm to dynamically change the threshold value in the traversed nodes listed in the searching path, which is utilizing the searching appropriate centroid process performed via each training vector. Depicting the similarity between each inner node and its child nodes of the tree structure progressively. As a result, hierarchical clusters will be constructed and this clustering rule can be used in encoding step of vector quantization to achieve the image compression.
In addition, we compare the proposed method with TSVQ, GLA/LBG, S-TREE and GATSM algorithm in image quality and codebook training time. The simulation results show that the proposed method outperforms those tree-structed algorithms, such as TSVQ, S-TREE in reconstruction image quality and takes less training time than those in LBG algorithm and GATSM algorithm.
摘 要 I
Abstract II
誌 謝 IV
目 錄 V
圖索引 VII
表索引 X
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 研究範圍與限制 2
1.4 論文架構 3
第2章 文獻回顧 4
2.1 S-TREE演算法 7
2.2 螞蟻演算法 14
2.3 GLA與LBG演算法 17
2.4 GATSM演算法 20
2.5 樹狀結構向量量化演算法(TSVQ) 22
2.6 多路徑搜尋演算法(Multipath TSVQ) 25
2.7 快速搜尋及編碼演算法(EAWFC) 27
2.8 動態路徑選擇的演算法 29
2.9 資料量化壓縮的發展背景 31
2.9.1 向量量化Vector Quantization的介紹 31
2.9.2 影像壓縮品質衡量的常用方法 35
2.9.3 影像壓縮的常用方法 37
2.9.4 向量量化(Vector Quantization)的分類 38
第3章 研究方法 46
3.1 研究模式推導 46
3.2 本論文提出的ST-ACO演算法 48
第4章 實驗結果與討論 64
4.1 實驗環境 64
4.2 資料取得 65
4.3 實驗流程圖說明 66
4.4 實驗一 70
4.5 實驗二 96
4.6 實驗三 106
4.7 實驗四 110
第5章 結論與未來研究方向 122
5.1 結論 122
5.2 未來研究方向 127
參考文獻 130
附 錄 134
作者簡介 140
[1]陳順宇, 多變量分析第四版, 華泰文化, 2004.
[2]戴顯權, 資料壓縮第二版, 紳藍出版社, 2002.
[3]鍾國亮, 資料壓縮的原理與應用第二版, 全華科技圖書, 2004.
[4]Adriaans, Pieter and Zantinge, Dolf, “DATA MINING,” ADDISON– WESLEY, 1996.
[5]Blum, Christian, “Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling,”Computers & Operations Research, vol. 32, no. 6, pp. 1565-1591, 2005.
[6]Blum, Christian, “Ant colony optimizatioin:Introduction and recent trends,” Physics of Life Reviews, vol. 2, pp. 353-373, 2005.
[7]Buzo, A., Gray., Jr., H., Gray, R. M.,and Markel, J. D., “Speech coding based upon vector quantization,” IEEE Transactions on Acoustics, Speech, and Signal Processing, pp. 562-574, 1980.
[8]Campos, Marco M. and Carpenter, Gail A., “S-TREE: self-organizing trees for data clustering and online vector quantization,” Neural Network vol. 14, pp. 505-525, 2001.
[9]Chang, Chin-Chen, “Dynamic Path Tree Structured Vector Quantizatioin,” International Workshops, 1999.
[10]Chang, Chin-Chen and Chen, Tung-Shou and Xiao, Guang-Xue, “An Efficient and Effective Method for VQ Codebook Design,” IEEE, ICICS-PCM 2003 pp. 15-18, December, 2003.
[11]Chang, R. F., Chen, W. T., and Wang, J. S., “Image sequence coding using adaptive tree-structured vector quantization with multipath search,” IEE Proc., vol 139, pp. 9-14, February, 1992.
[12]Dorigo, M., and Gambardella, L. M., “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transaction on Evolutionary Computation, vol. 1, pp. 53-66, 1997.
[13]Dorigo, M., Maniezzo, V., and Colorni A., “The ant system: optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, vol. 1, pp. 29-41, 1996.
[14]Dorigo, M. and Caro, G. Di., “Ant Colony Optimization: A New Meta-Heuristic,” Proceedings of the Congress on Evolutionary Computation, pp. 1470-1477, 1999.
[15]Efford, Nick , “Digital image Processing a practical introduction using JAVA,” ADDISON-WESLEY, 2000.
[16]Gambardella, Luca Maria and Dorigo, Marco, “Solving Symmetric and Asymmetric TSPs by Ant Colony,” Proceedings of IEEE International Conference on Evolutionary Computation, IEEE-EC 96, IEEE Press, pp. 622–627, 1996.
[17]Guttman, Antom, “R-TREE:A DYNAMIC INDEX STRUCTURE FOR SPATIAL SERACHING,” ACM SIGMOD Conference on Management of Data, pp. 47–57, 1984.
[18]Gray, R. M., and Neuhoff, D. L., “Quantization,” IEEE Trans. Info. Theory vol. 44, no. 6, pp. 2325–2383, 1998.
[19]Lai, Z.C., “Fast encoding algorithms for tree-structured vector quantization,” Image and vision computing vol. 15, no. 11, pp. 867-871, 1997.
[20]Kantardzic, Memed, ”DATA MINING Concepts, Models, Methods, and Algorithm,” WILEY-INTER SCIENCE, 2001.
[21]Kohonen, T., Self-Organizing and Assocaitive Memory, 3d ed.(1st ed.1984), Springer Berlin-Heidelber-New York , 1989.
[22]Kunkle, Daniel R., “Self-organizing Computation and Information Systems: Ant Systems and Algorithms,” For: Introduction to Artificial Intelligence November, 2001.
[23]Lee R.C.T., Chang, R.C., Tseng, S. S., Tsai, Y. T., Introduction to the Design and analysis of Algorithm, 旗標出版社, pp. 253-261, 2002.
[24]Linde, Y., and Buzo, A., and Gray, R. M., “An Algorithm for Vector Quantizater Design,”IEEE Trans. Commun., vol. COM-28, pp. 84-95, Jan, 1980.
[25]Li Xia, Luo Xuehui and Zhang JiZhong, “Codebook Design by A Hybridization of ANT Colony with Improved LBG ALGORITHM,” IEEE Int, Conf. Neural Networks & Signal Processing, Nanjing, China, vol. 1, pp. 469 - 472, December, 2003.
[26]Maniezzo, V., and Colorni, A and Dorigo, M. ,“The Ant System Applied to the Quadratic Assignment Problem,” Technical Report IRIDIA /94-28, Universite Libre de Bruxelles, Belgium, EU, 1994.
[27]McMullen, Partic R., “An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives,” Artificial Intelligences in Engineering vol. 15, pp. 309-317, 2001.
[28]Parpinelli, Rafael S., and Lopes, Heitor S., and Freitas, Alex A. ,“An Ant Colony Algorithm for Classification Rule Discovery,” Idea Group publishing, 2002.
[29]Shannon, C. E., A mathematical theory of communication, Bell Syst.Tech. J., vol.27, pp. 623–656, 1948.
[30]Shelokar, P. S., and Jayaraman, V.K., and Kullarni, B. D., “An ant colony approach for clustering,”ANALYTICA CHIMICA ACTA, vol.509, pp. 187-195, 2004.
[31]Talbi, E.-G., Rouxb O., Fonlupt, C., and Robillard, D., “Parallel Ant Colonies for the quadratic assignment problem,”Science, 2001.
[32]Wang, W., and Yang, R. Muntz., “STING: A Statistical Information grid Approach to Spatial Data Mining,” In Proceedings 1997 International Conference Very Large Data Bases (VLDB’97), pp. 186-195, August, 1997.
[33]Yu, Yuan-Hui, Chang, Chin-Chen and Hu,Yu-Chen, “A genetic-based adaptive threshold selection method for dynamic path tree structed vector quantization,” Image and Vision Computing, vol. 23, no. 6, pp. 597-609, 2005.
[34]Zeger, Kenneth, Vaisey, Jacques and Gersho, Allen, “Globally Optimal Vector Quantizer Design by Stochastic Relaxation,” IEEE Transactions on Signal Processing, vol. 40, no. 2, February, 1992.
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔