二分搜尋法於向量量化演算法之研究

A Study on Binary Search Algorithm for VQ

曾崇儀(Chung-Yi Tzeng)

指導教授 ： 黃紹華 ； 何文楨

國立臺北科技大學/機電學院/電機工程系所/碩士(2006年)

摘要

本論文提出一新式之二分搜尋法，此搜尋法可適用於多維度向量之搜尋，如VQ、C-Means、KNN等演算法之搜尋，使得多維度向量之搜尋計算量被大量降低。
二分搜尋演算法共分四部分去建立樹狀結構之Codebook, 四步驟詳列如下:
一、將既有之Codebook以VQ演算法分成兩塊 Sub-Codebook。
二、使用Boundary Process(BP)技術處理邊界上，重複Codewords。
三、重複將一與二步驟於兩個Sub-Codebook上，直到Sub-Codebook減少之Codeword量小於或等於為止。
四、Codebook之搜尋採用樹狀結構之二分法搜尋，直到樹枝末端為止，剩餘的Sub-Codebook則直接採用Full-Search。
經實作數據分析結果，與全域搜尋法結果比較，本論文所提出之二分搜尋法確實達到計算量大量化簡之目的，其正確率仍然保持100%，以ITU所制定之語音壓縮演算法G.729為例，VQ Codebook包含128個10維之LSP向量，經二分搜尋法後, 計算量降低約55%，而搜尋正確率仍然維持100%。

關鍵字

BVQ ； Tree VQ ； LBG演算法 ； K-Means ； KNN

並列摘要

VQ is a popular and efficient technology for signal processing and data compression. However, the computation requirement on the full-search algorithm is dramatically large. To overcome this issue, many approaches such as TIE, PDE,and Tree-structured … are employed to reduce the computation.
Binary search is a powerful algorithm. It will reduce the search space dramatically. However, the binary search can be worked on the one-dimension space only. The space dimension of VQ is very large for the goal on data compression. In the past, the tree-structure VQ was proposed to eliminate the search space. In this approach, the search space is really down. However, the quality and correction-rate is also down.
In this thesis, the new algorithm for binary search on VQ application is proposed. In this approach, the search space is really down. Moreover, the quality is also kept. With comparison to the traditional VQ, the average correction-rate is 99.6% and the 57% of search space is reduced. These performances is superior than tree-structured VQ.

並列關鍵字

BVQ ； Tree VQ ； LBG Algorithm ； K-Means ； KNN

參考文獻

[1] Linde, Y., Buzo, A., and Gray, R. M., “An algorithm for vector quantizer design,” IEEE Trans. on Communications, Vol.28, No.1, 1980, pp.84-95.

[2] Karayiannis, N. R., and Pai, P. –I., “Fuzzy vector quantization algorithms and their application in image compression,” IEEE Trans. on Image Processing, Vol.4, No.9, 1995, pp.1193-1201.

[3] Han W. J., Kim E. K., and Oh Y. H., “Multi-codebook split vector quantization of LSF parameters”, IEEE signal processing letters, Vol.9, No.12, 2002, pp.418-421.

[4] W. J. Hwang and B. Y. Ye, “Storage-and Entropy-Constrained Multi-Stage Vector Quantization and Its Applications to Progressive Image Transmission,” IEEE Trans. on Consumer Electronics, Vol.43, No.1, 1997, pp.17-23.

[5] Bayazit U. and Pearlman A., “Variable length constrained storage tree structure vector quantization,” IEEE Trans. on Image Processing, Vol.8, No.3, 1999, pp.321 -331.