臺灣博碩士論文加值系統

向量量化(Vector Quantization)編碼法目前廣泛被運用於多媒體通訊之影像資料壓縮上，但向量量化編碼法有一個重大的缺點，就是需將輸入影像區塊與編碼簿中的碼向量一一比較搜尋出最佳匹配碼向量。使用完全搜尋法雖然簡單，但此種方法會隨著編碼簿的增大使得搜尋時間也呈指數的成長。
為了能使向量量化編碼端能夠快速編碼，本論文提出一個基於總和式金字塔架構等效於全搜尋法品質之向量量化快速搜尋編碼演算法，此演算法首先運用柯西不等式之原理計算出可利用碼向量之間的總和差，用來限制出編碼簿之碼向量搜尋範圍，以便先期剔除一部份不需要的碼向量，然後再配合總和式金字塔之資料結構，一層一層剔除不可能為最佳匹配碼向量，故可免除大量的歐基里德距離計算，加快搜尋編碼簿的速度。
所提出的演算法，曾利用標準灰階影作實驗証明，可得到與完全搜尋法等價的影像品質，並且與其它快速搜尋演算法相較下，不但可達到與完全搜尋演算法相同的影像品質，並且搜尋時間不會隨著編碼簿增大而呈指數成長；而達到較低的計算量以及更快的搜尋速度。

Vector quantization (VQ) is a well-know data compression technique. In the codebook design phase as well as the encoding phase, given a block represented as a vector, searching the closest codeword in the codebook is a time-consuming task. In order to encode an image using VQ fast, it is most important to eliminate unnecessary distance computation as much as possible while searching for best-matched codeword.
To overcome this problem, based on the Sum-Norm pyramid data structure of a vector, a fast encoding algorithm with PSNR equivalent to full search is proposed. Sum is used as feature to roughly measure the difference between an input image block and a codeword to check whether current codeword could be a promising candidate best-matched codeword or not.
For typical standard gray-level images of size 512x512 with very different details, the proposed search algorithm significantly reduces the encoding complexity while maintaining the same encoding quality as that of the full search algorithm. Experimental results of VQ encoding demonstrate that the proposed method is very search effective.

表目錄---------------------------------------------------Ⅰ
圖目錄 --------------------------------------------------Ⅱ
第一章 緖論---------------------------------------------1
第二章 影像向量量化
2.1 向量量化基本原理--------------------------------4
2.2 編碼簿設計-----------------------------------------8
2.3 影像品質評估-------------------------------------10
第三章 相關之影像向量量化快速搜尋演算法
3.1影像向量量化快速搜尋演算法---------------------------13
3.2 使用剔除條件之快速向量量化編碼--------------------14
3.3 等價於完全搜尋的影像品質之向量量量化階層式
快速編演算法----------------------------------------------------16
3.4 基於總和式金字塔碼向量之編碼簿快速搜尋演算
法-------------------------------------------------------------------19
第四章 基於總和式金字塔架構等效於全搜尋品質之向量量化快速搜尋編碼演算法
4.1基於總和式金字塔架構等效於全搜尋品質之向量量化快速搜尋編碼演算法之推論----------------------24
4.2基於總和式金字塔架構等效於全搜尋品質之向量量化快速搜尋編碼演算法-------------------------------26
第五章 實驗與討論--------------------------------------32
第六章 結論-----------------------------------------------41
參考文獻---------------------------------------------------42

References
[1] B. C. Song and J. B. Ra, “A fast search algorithm for vector quantization using L2-norm pyramid of codewords,” IEEE Trans. Image Processing, vol.11, no 1,pp.10-15,Jan.2002
[2] C.D.Bei and R. M. Gray, “ An improvement of the minimum distortion encoding algorithm for vector quantization,”IEEE Trans. Commum., vol.COM-33,pp.1132-1133, Oct.1985
[3] C.-H. Hsieh and Y.-J. Liu, “Fast search algorithms for vector quantization of images using multiple triangle inequalities and wavelet transform,” IEEE Trans.Image Processing, vol. 9, pp.321-328, Mar.2000.
[4] C.-H Lee and L.-H. Chen, “A fast search algorithm for vector quantization using mean pyramids of codewords,” IEEE Trans. Commun., vol.43, pp.1697-1702, Feb.1995.
[5] H. Q. Cao and W. Li,”A fast search algorithm for vector quantization using a directed graph,”IEEE Trans. Circuits Syst. Video Technol.,vol.10,pp.585-593,Jun.2000.
[6] J. S. Pan, Z.M. Lu, and S. H. Sun, “Fast codeword search algorithm for image coding based on mean-variance pyramids of codewords,” Electron. Lett., vol. 36,no. 3, pp.210-211, Feb. 2000.
[7] K.-S. Wu and J.-C. Lin ,”Fast VQ encoding by an kick-out condition,”IEEE Trans. Circuits Syst.Video Technol., vol.10, pp.59-62,Feb.2000
[8] Kuo-Liang Chung and Jenn-Yang Lai “An efficient law-of-cosine-based search for vector quantization“ Pattern Recognition Letters, v.25 n.14, pp.1613-1617,2004.
[9] Mielikainen, J. ”A novel full-search vector quantization algorithm based on the law of cosines ”IEEE Signal Processing Letters, vol 9, pp.175-176,June2002
[10] N.M Nasarabadi and R.A.king, “Image coding using vector quantization:A review,”IEEE Trans. Commun, vol,36, pp.957- 971 ,Aug,1988.
[11] Pan, Z. and Kotani, K. and Ohmi, T, ”An improved full-search-equivalent vector quantization method using the law of cosines” IEEE Signal Processing Letters, vol 11,pp.247– 250,Feb.2004
[12] R. M. Gray ,”Vector Quantization,”IEEE ASSP Magazine, pp.4-29,1984
[13] Shinfeng D.Lin,Shih-Chieh Shie and Chi-Yang Hung“A fast codebook search algorithm based on sum-norm pyramid of codewords”16th IPPR Conference on Computer Vision, Graphics and Image Processing .2003
[14] S. W. Ra and J. K. Kim, “A fast mean-distance-ordered partial codebook search algorithm for image vector quantization” IEEE Trans. On Circuits and Systems-Ⅱ：Analog and Digital Signal Processing, vol. 40, no.9,pp.576-579,1993.
[15] T.S.Chen and C.C. Chang, ”Diagonal axes method (DAM)：A fast search algorithm for vector quantization ”,IEEE Trans.on Circuits and System for video Technology, vol.7,no.3, pp.555 -559,1997
[16] W. H. Eguitz, ”A new vector quantization clustering algorithm”IEEE Trans. On Acoustics, speech ,and signal processing, 37(10),pp.1568-1575.1989
[17] Y. Linde, A. Buzo, & R. M. Gray, "An algorithm for vector quantizer design",IEEE Trans. Commun., vol. COM-28, pp. 84-95, Jan. 1980,.
[18] Zhibin Pan; Kotani, K.; Ohmi, T.” A hierarchical fast encoding algorithm for vector quantization with PSNR equivalent to full search”Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on vol 1, pp.797-800,May 2002
[19] 張真誠、黃國峰、陳同孝，數位影像處理技術，台北市，松崗電腦圖書資料股份有限公司，2000
[20] 戴顯權、陳瀅如、王春清，資料壓縮，高雄市，紳藍出版社，2002
[21].鐘國亮，資料壓縮的原理與應用，台北市，全華科技圖書股份有限公司，2002