一個改良LBG初始編碼簿與收斂方法之影像壓縮技術

An Image Compression Technique Based on Initial Codebook Improvement and Convergence Improvement of LBG

吳冠賦

影像壓縮 ； 分群技術 ； 自動化方法 ； image compression ； clustering technique ； automated method

屏東科技大學資訊管理系所學位論文

2016年

碩士

蔡正發

繁體中文

本論文將進行「影像壓縮」之研究，影像壓縮簡略的定義即是減少一張影像所需要的訊號空間數量，進而使傳遞變得迅速，而能夠達到影像壓縮的方法眾多，概括可分類為「頻率領域」及「空間領域」，而這兩個領域又可再分為「失真性」與「無失真性」壓縮，本研究基於「空間領域」中「失真性」影像壓縮的LBG演算法，進行改良，並命名為AICT。 　　AICT有五個重要部分：(1)擷取影像有用之數據(2)利用影像特徵產生較好的初始編碼簿(3)根據影像類型自動產生參數(4)減少重複顏色進而使執行時間減少(5)改善收斂方法進而加速演算法運行。 　　AICT有以下優點：(1)無須自行輸入參數即可執行(2)程式操作容易(3)壓縮品質優異且執行時間良好(4)演算法效能實驗中，展現良好競爭力。

This thesis performs the research in image compression. Image compression means to reduce the storage for saving images and even make sending data more quickly. There are many ways to conduct image compression. It can be classified into two categories which are frequency domain and spatial domain. Moreover, they are subdivided into lossy compression and lossless compression. This thesis mainly discusses the LBG algorithm in lossy image compression of spatial domain and improve it with good performance. The new technique was named AICT. 　　There are five important parts in AICT: (1) Deal with image to obtain useful information before executing algorithm. (2) Use image’s feature to produce the better initial codebook. (3) Get the parameters by automation methods from image’s types. (4) Reduce repeating color to decrease the time. (5) Ameliorate the convergence method to accelerate algorithm. 　　This thesis includes following advantages: (1) AICT can implement without keying in parameters. (2) Work is simple and easy to understand (3) The quality in compression is excellent and has good execution time. (4) Finally, the experiments show the comparison among LBG, SOM, and LazySOM. AICT expresses the nice competitiveness in each test.

1. [3] Ray-I. Chang, Chung-Yuan Su, “Color gradient vectorization for SVG compression of comic image,” Journal of Visual Communication and Image Representation, Vol. 33, pp. 235-246, 2015.
   連結：
2. [4] Fatema Rashid, Ali Miri, Isaac Woungang, “Secure image deduplication through image compression,” Journal of Information Security and Applications, Vol. 27-28, pp. 54-64, 2016.
   連結：
3. [5] Sharma G, Trussell H J, “Digital Color Imaging,” IEEE Transactions on Image Processing, Vol. 6, No. 7, pp. 901–932, 1997.
   連結：
4. [8] R. N. Bracewell, “The Fourier Transform and Its Applications,” McGraw Hill, 3rd ed., 2000.
   連結：
5. [9] Gregory K. Wallace, “The JPEG Still Picture Compression Standard,” Communications of the ACM, Vol. 34, No. 4, pp. 30-44, 1991.
   連結：
6. [10] A. Skodras, C. Christopoulos, T. Ebrahimi, “The JPEG 2000 Still Image Compression Standard,” IEEE Signal Processing Magazine, Vol. 18, No. 5, pp. 36-58, 2001.
   連結：
7. [13] Allen Gersho, Robert M. Gray, “Vector Quantization and Signal Compression,” Kluwer AcademicPublishers, Boston, 1991.
   連結：
8. [14] Abdelatief Hussein Abouali, “Object-based VQ for image compression,” Ain Shams Engineering Journal, Vol. 6, No. 1, pp. 211-216, 2015.
   連結：
9. [15] M. Lakshmi, J. Senthilkumar, Y. Suresh, “Visually lossless compression for Bayer color filter array using optimized Vector Quantization,” Applied Soft Computing, Vol. 46, pp. 1030-1042, 2016. 
   連結：
10. [16] Kiattisin Kanjanawanishkul, Bunyarit Uyyanonvara, “Novel fast color reduction algorithmfor time-constrained applications,” Journal of Visual Communication and Image Representation, Vol. 16, No. 3, pp. 311-332, 2005.
    連結：
11. [18] J. A. Hartigan, M. A. Wong, “A K-Means Clustering Algorithm,” Applied Statistics, Vol. 28, No. 1, pp. 100-108, 1979.
    連結：
12. [19] Y. Linde, A. Buzo, R. Gray, “An algorithm for vector quantization design,” IEEE Transactions on Communications, Vol. l, No. 1, pp. 84–95, 1980.
    連結：
13. [20] T. Kohonen, “Self-organized formation of topologically correct feature maps,” Biological Cybernetics, Vol. 43, No. 1, pp. 59-69, 1982.
    連結：
14. [21] T. Kohonen, T. Honkela, “Kohonen network,” Scholarpedia, 2007.
    連結：
15. [22] T. Kohonen, “Self-organizing map,” Proceedings of the IEEE, Vol. 78, No. 9, pp. 1464-1480, 1990.
    連結：
16. [23] F. Madeiro, R.M. Vilar, B.G.A. Neto, “A Self-Organizing Algorithm for Image Compression,” Proceedings of Vth Brazilian Symposium on Neural Networks, pp. 146–150, 1998.
    連結：
17. [24] C. Amerijckx, M. Verleysen, P. Thissen, J.D. Legat, “Image Compression by Self-Organized Kohonen Map,” IEEE Transactions on Neural Networks, Vol. 9, No. 3, pp. 503–507, 1998.
    連結：
18. [26] Chip-Hong Chang, Pengfei Xu, Rui Xiao, T. Srikanthan, “New Adaptive Color Quantization Method Based on Self-Organizing Maps,” IEEE Transactions on Neural Networks, Vol. 16, No. 1, pp. 237–249, 2005.
    連結：
19. [27] Cheng-Fa Tsai, Yu-Jiun Lin, “LazySOM: Image Compression Using an Enhanced Self-Organizing Map,” Lecture Notes in ComputerScience, Vol. 5414, pp. 118-129, 2009.
    連結：
20. [28] Qian Chen, Jiangang Yang, Jin Gou, “Image Compression Method Using Improved PSO Vector Quantization,” Lecture Notes in Computer Science, Vol. 3612, pp. 490-495, 2005.
    連結：
21. [30] Ming-Huwi Horng, Ting-Wei Jiang, “The Codebook Design of Image Vector Quantization Based on the Firefly Algorithm,” Computational collective intelligence: technologies and applications, Vol. 6423, pp. 438-447, 2010.
    連結：
22. [31] X.S. Yang, “Nature-Inspired Metaheuristic Algorithms,” Luniver Press, 2008.
    連結：
23. 中文文獻
24. [1] 莊鎮安，一個以自組織映射圖為基礎的技術用於灰階影像壓縮之研究，國立屏東科技大學資訊管理學系碩士論文，2007。
25. [2] 陳士杰，類神經網路基礎，國立聯合大學資訊管理學系， http://sjchen.im.nuu.edu.tw/MachineLearning/final/NN_SOM.pdf，2014。
26. 英文文獻
27. [6] Colorni A, M. Dorigo, V. Maniezzo, “An Investigation of Some Properties of an Ant Algorithm,” Proceedings of the Parallel Problem Solving from Nature Conference, Elsevier Publishing, pp. 509-520, 1992. 
28. [7] Martin Ester, Hans-Peter Kriegel, Jorg Sander, Xiaowei Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pp. 226-231, 1996.
29. [11] Khalid Sayood, “Introduction to Data Compression,” Morgan Kaufmann, 2nd ed., 2000.
30. [12] R. Gray, “Vector Quantization,” IEEE ASSP Magazine, Vol. 1, No. 2, pp. 4-29, 1984.
31. [17] Wattanapong Kurdthongmee, “A Colour Image Quantization Algorithm for Time-ConstrainedApplications,” Walailak Journal of Science and Technology, Vol. 2, No. 2, pp. 149-168, 2005.
32. [25] M. Barbalho, A. Duarte, D. Neto, A.F. Costa, L.A. Netto, “Hierarchical SOM applied to image compression,” Proceedings of International Joint Conference on Neural Networks, Vol. 1, pp. 442-447, 2001.
33. [29] J. Kennedy, R. Eberhart, “Particle Swarm Optimization,” Proceedings of the IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.