向量量化Vector Quantization(VQ)是一種目前十分常見的數位影像壓縮方法，它不僅快速、簡單，且能有效率的將數位影像壓縮至極小的儲存容量；在目前資訊與網路發達的科技下，快速壓縮及較小的儲存容量對於透過網路交換資訊是十分重要的技術。

許多基植於向量量化編碼法的壓縮技術不斷地被提出，主要是由於向量量化擁有架構簡單，容易實現的優點。在本論文中，我們提出了一個新的架構能更進一步的將向量量化的索引表進行無失真壓縮，以期達到更好的壓縮效率。我們將向量量化的編碼簿採用了主成份分析Principal Component Analysis (PCA)演算法進行排序，透過主成份分析，我們可以使編碼簿中相鄰的編碼字擁有較高的相似性。然後利用搜尋順序編碼法Search-Order Coding (SOC) 尋找鄰近且已經編碼完成的區塊是否有與目前欲編碼區塊相同的索引值；若搜尋順序編碼法失敗，再套用動態化的狀態編碼簿(Dynamic State Codebook) 的機制，以邊緣吻合向量量化Side Match Vector Quantization (SMVQ) 編碼法進行編碼。實驗結果顯示我們提出的架構可以不影響原本VQ壓縮後的影像品質，而且達到更好的壓縮效能。

Vector Quantization (VQ) is a popular digital image compression technique. VQ can compress digital images with a very small capacity of storage space in a fast, simple and efficient process. It is an important technique with fast compress and small size of storage in current of information and network environment.

Many new schemes based on VQ have been proposed. In this thesis, we propose a new scheme that can further compress VQ index table to achieve better compression rate. To speed up our process, we sort VQ codebook with Principal Component Analysis (PCA). By using PCA, we can make the neighboring codewords with maximum similarity and correlation. And then we apply Search-Order Coding (SOC) to find whether the neighboring blocks are the same as the encoding block. If SOC fails to encode the current block, we then apply Side Match Vector Quantization (SMVQ) with dynamic state codebook to encode it. To increase the performance of SMVQ, we classify the current block into ten groups with different state codebook size by referring the variances of its upper and left blocks. The experiment results confirm our proposed scheme provides lower compression ratios without distortion than Chang et al.’s and Chen et al.’s schemes did.

中文摘要 ……………………………………………………………… i
英文摘要 ……………………………………………………………… ii
誌謝 ……………………………………………………………… iii
目錄 ……………………………………………………………… iv
表目錄 ……………………………………………………………… v
圖目錄 ……………………………………………………………… vi
第一章 緒論………………………………………………………… 1
第二章 相關研究…………………………………………………… 4
2.1 向量量化Vector Quantization (VQ)……………………… 4
2.2 LBG演算法………………………………………………… 6
2.3 主成份分析Principal Component Analysis (PCA) ……… 7
2.4 搜尋順序編碼Search-Order Coding (SOC) ……………… 8
2.5 邊緣吻合向量量化Side Match Vector Quantization(SMVQ) 12
2.6 區塊分類器Block Classifier ……………………………… 14
2.7 相關研究論文探討…………………………………………… 15
第三章 採用動態狀態編碼簿機制的數位影像壓縮技術…………… 23
3.1 本論文提出架構的整體概觀………………………………… 23
3.2 向量量化編碼階段…………………………………………… 25
3.3 搜尋順序編碼階段…………………………………………… 26
3.4 邊緣吻合向量量化編碼階段………………………………… 28
3.5 解碼階段……………………………………………………… 34
第四章 實驗數據……………………………………………………… 36
第五章 結論…………………………………………………………… 46
參考文獻 ………………………………………………………………… 48

[1] R. M. Gray, “Vector Quantization,” IEEE ASSP Mag., vol. 1, no. 2, April 1984, pp. 4-29.

[2] N. M. Nasrabadi and R. A. King, “Image Coding Using Vector Quantization: A Review,” IEEE Trans. on Communs., vol. 36, no. 8, August 1988, pp. 957-971.

[3] Y. Linde, A. Buzo and R. M. Gray, “An Algorithm for Vector Quantizer Design,” IEEE Trans. on Communs., Vol. 28, 1980, pp. 84-95.

[4] A. Aravind and A. Gersho, “Image Compression Based on Vector Quantization with Finite Memory,” Opt. Eng., vol. 26, May 1987, pp. 570-580.

[5] T. Lookabaugh, V. Riskin, P. A. Chou and R. M. Gary, “Variable Rate Vector Quantization for Speech, Image, and Video Compression,” IEEE Trans. Commun., vol. 41, no. 1, 1993, pp. 186-199.

[6] N. M. Nasrabadi and Y. Feng, “Image Compress Using Address Vector Quantization,” IEEE Trans. Commun., vol. 38, 1990, pp. 2166-2173.

[7] C. H. Hsieh and J. C. Tsai, “Lossless Compression of VQ Index with Search-Order Coding,” IEEE Trans. on Image Processing, Vol. 5, No. 11, 1996, pp. 1579-1582.

[8] R. C. T. Lee, Y. H. Chin and S. C. Chang, “Application of Principal Component Analysis to Multikey Searching,” IEEE Trans. on Software Engineering, Vol. SE-2, No. 3, 1976, pp. 185-193.

[9] T. Kim, “Side Match and Overlap Match Vector Quantizers for Images,” IEEE Trans. on Image Processing, vol. 1, no. 2, 1992, pp. 170-185.

[10] R. F. Chang and W. T. Chen, “Image Coding Using Variable-Rate Side-Match Finite-State Vector Quantization,” IEEE Trans on Image Processing, Vol. 2, No. 1, January 1993, pp. 104-108.

[11] P. Y. Chen and C. T. Yu, “Lossless Vector-Quantised Index Coding Design and Implementation,” IEE Proc.-Circuits Devices Syst., Vol. 152, No. 2, April 2005, pp. 109-117.

[12] C. C. Chang, C. C. Lin, and C. Y. Lin, “Compressing Vector Quantization Index Table Using Side Match State Codebook,” to appear Journal of Applied Systems Studies, (Cambridge International Science Publishing, accepted in 2005/12).