快速搜尋演算法於向量量化之研究

本文提出一個以快速定位法為基礎的碼簿快速搜尋演算法，並採用學習與取捨的觀點實行此演算法。在向量空間中透過對各維度進行二元搜尋去定位出一個對應的搜尋子空間，並透過全域搜尋法或部分距離去除法在子空間中尋找最佳碼字，是為二元搜尋空間演算法。其中對於取捨的觀點來說，以些微向量量化品質的損失換取計算量大量的節省率；而就學習方面來說，以學習的方式並以全域搜尋演算法當作推論函數作為學習的對象去建立二元搜尋空間演算法的碼簿。此演算法應用在G.729語音編碼的線譜對二階合成向量編碼器上，其編碼器分別包含一個128碼字與兩個32碼字的小型碼簿。同時，介於語音訊號在訊框間的高相關性經過移動平均濾波器後，也隨之被消除。在線譜對編碼器上這些問題對於發展有效的快速搜尋演算法是一大挑戰。在實驗數據方面，動態交集三角不等式去除法、樹狀結構向量量化、二元搜尋空間向量量化等方法的計算量節省率分別為61.72%、88.63%與92.36%，而量化準確率分別為100%、26.07%與99.22%，以上數據驗證了二元搜尋空間向量量化優秀的效能。此外，二元搜尋空間向量量化與三角不等式去除法不同，在於它並不需要依賴訊號的高相關性來降低計算量，因此很適合使用在G.729語音編碼的線譜對向量編碼器上。

關鍵字

語音編碼；向量量化；二元搜尋空間向量量化；線譜對編碼

並列摘要

This dissertation proposes a fast search algorithm for vector quantization (VQ) based on a fast locating method, and uses learning and trade-off analysis to implement this algorithm. The proposed algorithm is a binary search space VQ (BSS-VQ) that determines a search subspace by binary search in each dimension, and the full search VQ (FSVQ) or partial distance elimination (PDE) is subsequently used to obtain the best-matched codeword. In trade-off analysis, a slight loss occurred in quantization quality; however, a substantial computational saving was achieved. In learning analysis, the BSS was built by the learning process, which uses full search VQ (FSVQ) as an inferred function. The BSS-VQ algorithm is applied to the line spectral pairs (LSP) encoder of the G.729 standard, which is a two-stage VQ encoder with a codebook size of 128 and two small codebook sizes of 32. In addition, a moving average (MA) filters the LSP parameter beforehand, and the high correlation characteristics are degraded between consecutive speech frames. These factors present a challenge for developing fast and efficient search algorithms for VQ. In the experiment, the computational savings of DITIE, TSVQ, and BSS-VQ are 61.72%, 88.63%, and 92.36%, respectively, and the quantization accuracy of DITIE, TSVQ, and BSS-VQ are 100%, 26.07%, and 99.22%, respectively, which confirmed the excellent performance of the BSS-VQ algorithm. Moreover, unlike the TIE method, the BSS-VQ algorithm does not depend on the high correlation characteristics of signals to reduce the amount of computation; thus, it is suitable for the LSP encoder of the G.729 standard.

並列關鍵字

Speech coding ； Vector quantization (VQ) ； Binary search space VQ ； LSP

參考文獻

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

[4] H. A. Monawer, “Image vector quantisation using a modified LBG algorithm with approximated centroids,” Electronics Letters, vol. 31, no. 3, 1995, pp. 174-175.

[5] S. M. Cheng, K. T. Lo, and K. C. Li, “Efficient LBG initialisation method for image vector quantisation,” Electronics Letters, vol. 31, no. 19, 1995, pp. 1654-1656.

[6] X. Wu and L. Guan, “Acceleration of the LBG algorithm,” IEEE Transactions on Communications, vol. 42, no. 234, 1994, pp. 1518-1523.

[7] K. S. Wu and J. C. Lin, “Fast LBG codebook generation for BTC image compression,” Electronics Letters, vol. 31, no. 17, 1995, pp. 1427-1428.

國際替代計量

快速搜尋演算法於向量量化之研究

全文下載

主題瀏覽