跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/07/28 23:12
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張舜傑
研究生(外文):Shun-Chieh Chang
論文名稱:快速搜尋演算法於向量量化之研究
論文名稱(外文):The Research of VQ-Based Fast Search Algorithm
指導教授:黃紹華黃紹華引用關係葉政育
指導教授(外文):Shaw-Hwa HwangCheng-Yu Yeh
口試委員:林政源蔡偉和馬尚智何文楨
口試委員(外文):Cheng-Yuan LinWei-Ho TsaiShang-Chih MaWen-Jen Ho
口試日期:2012-05-21
學位類別:博士
校院名稱:國立臺北科技大學
系所名稱:電機工程系博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:73
中文關鍵詞:語音編碼向量量化二元搜尋空間向量量化線譜對編碼
外文關鍵詞:Speech codingVector quantization (VQ)Binary search space VQLSP
相關次數:
  • 被引用被引用:0
  • 點閱點閱:135
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本文提出一個以快速定位法為基礎的碼簿快速搜尋演算法,並採用學習與取捨的觀點實行此演算法。在向量空間中透過對各維度進行二元搜尋去定位出一個對應的搜尋子空間,並透過全域搜尋法或部分距離去除法在子空間中尋找最佳碼字,是為二元搜尋空間演算法。其中對於取捨的觀點來說,以些微向量量化品質的損失換取計算量大量的節省率;而就學習方面來說,以學習的方式並以全域搜尋演算法當作推論函數作為學習的對象去建立二元搜尋空間演算法的碼簿。此演算法應用在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.

中文摘要 i
Abstract ii
誌謝 iii
Contents iv
List of Tables vi
List of Figures vii
Chapter 1 INTRODUCTION 1
1.1 Background 1
1.2 Motivation 1
1.3 Organization of Dissertation 2
Chapter 2 RELATED WORKS 3
2.1 Vector Quantization 3
2.1.1 Concept of vector quantization 3
2.1.2 Optimal quantization 5
2.2 Full Search Algorithm 9
2.3 Tree-Based Vector Quantization 10
2.3.1 Tree-structured vector quantization 10
2.3.2 Quasi-binary search algorithm 11
2.4 Fast Locating Based Algorithm 13
2.4.1 Double test of principal components algorithm 13
2.4.2 Planar Voronoi diagram search algorithm 15
2.5 Inequality-Based Algorithm 17
2.5.1 Partial distance elimination 17
2.5.2 Triangular inequality elimination 18
2.5.3 Dynamic and intersection TIE algorithm 19
2.6 G.729 Speech Codec 20
2.6.1 Encoder for G.729 codec 21
2.6.2 Decoder for G.729 codec 23
2.6.3 Quantization of LSP coefficients 24
2.6.3.1 Linear prediction analysis 24
2.6.3.2 Quantization of LSF coefficients 25
Chapter 3 THE BINARY SEARCH SPACE VQ ALGORITHM 27
3.1 Concept of BSS-VQ 28
3.1.1 Preliminary concepts 28
3.1.2 BSS-VQ prototype 29
3.1.3 Description of BSS-VQ 31
3.2 Optimal Splitting Point 33
3.3 Learning Aspect of BSS-VQ 36
3.4 Trade-Off Analysis of BSS-VQ 39
3.5 Algorithm of BSS-VQ 43
Chapter 4 EXPERIMENTAL RESULTS 45
4.1 BSS-VQ Training Process 45
4.1.1 Learning analysis for BSS-VQ 47
4.1.2 Trade-off analysis for BSS-VQ 53
4.2 BSS-VQ Encoding Process 58
Chapter 5 CONCLUSIONS AND FUTURE WORKS 65
5.1 Conclusions 65
5.2 Future Works 65
REFERENCE 67
Publication List 73


[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.
[2]A. Gersho, “On the structure of vector quantizers,” IEEE Transactions on Information Theory, vol. 28, no. 2, 1982, pp. 157-166.
[3]R. M. Gray, “Vector Quantization,” IEEE ASSP Magazine, vol. 1, no. 2, 1984, pp. 4-29.
[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.
[8]Z. B. Pan, G. H. Yu, and Y. Li, "Improved fast LBG training algorithm in Hadamard domain," Electronics Letters, vol. 47, no. 8, 2011, pp. 488-489.
[9]ITU-T Recommendation G.729, “Coding of speech at 8 kbit/s using conjugate-structure algebraic-code-excited linear prediction (CS-ACELP),” March 1996.
[10]S. H. Hwang, “Computational improvement for G.729 standard,” Electronics Letters, vol. 36, no. 13, 2000, pp. 1163-1164.
[11]T. M. Prego and S. L. Netto, “Efficient search in the adaptive codebook for ITU-T G.729 codec,” IEEE Signal Processing Letters, vol. 16, no. 10, 2009, pp. 881–884.
[12]ITU-T Recommendation P.800, “Method for subjective determination of transmission quality,” August 1996.
[13]S. W. Kang, C. Y. Son, and H. S. Sung, “A fast-search algorithm for the predictive split VQ of LPC parameters,” IEEE Communication Letters, vol. 5, no. 5, 2001, pp. 212-214.
[14]F. L. Li, X. W. Liu, X. Y. Zhang, and X. L. Du, “A fast VQ codeword Search Algorithm for AMR Wideband Speech Codec,” The 2nd International Conference on Computer and Automation Engineering, Singapore, 2010, pp. 479-482.
[15]C. Y. Wan and L. S. Lee, “Histogram-based quantization for robust and/or distributed speech recognition,” IEEE Transactions on Audio, Speech, Language Processing, vol. 16, no. 4 , 2008, pp. 859-873.
[16]S. Chatterjee, and T. V. Sreenivas, “Optimal switched split vector quantization of LSF parameters,” Signal Processing, vol. 88, no.6, 2008, pp. 1528-1538.
[17]G. Feideropoulou, M. Trocan, J. E. Fowler, B. P-Popescu, and J.-C. Belfiore, “Rotated constellations for video transmission over Rayleigh fading channels,” IEEE Signal Processing Letters, vol. 14, no. 9, 2007, pp. 629-632.
[18]F. K. Chen, and P. Y. Tsai, “Energy first search scheme for spectral envelope vector quantization of linear predictive coding residual,” IET Signal Processing, vol. 1, no. 4, 2007, pp. 190-196.
[19]C. Y. Yeh, C. C. Lin, and L. J. Yan, “An Efficient Line Spectral Frequency Quantization Method in G.729 Speech Codec”, Advanced Science Letters, vol. 9, 2012, pp. 880-884.
[20]A. Buzo, A. H. Gray, Jr., R. M. Gray, and J. D. Markel, “Speech coding based upon vector quantization,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 28, no. 5, 1980, pp. 562-574.
[21]R. M. Gray and Y. Linde, “Vector quantizers and predictive quantizers for Gauss-Markov sources,” IEEE Transactions on Communications, vol. 30, no. 2, 1982, pp. 381-389.
[22]D. Mouloud, D. O’S, “An efficient tree-structured codebook design for embedded vector quantization,” IEEE Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Dallas, Texas, 2010, pp. 4686-4689.
[23]L. J. Yan, S. H. Hwang, “The binary vector quantisation,” IEEE 3rd International Symposium on Communications, Control and Signal Processing, Malta, 2008, pp. 604-607.
[24]L. J. Yan, S. H. Hwang, “Vector quantisation based on a quasi-binary search algorithm,” IET Image Processing, vol. 5, no. 1, 2011, pp. 49-54.
[25]C. Bei and R. M. Gray, “An improvement of the minimum distortion encoding algorithm for vector quantization,” IEEE Transaction on Communications, vol. 33, no. 10, 1985, pp. 1132-1133.
[26]M. R. Soleymani and S. D. Morgera, “A fast MMSE encoding technique for vector quantization,” IEEE Transaction on Communications, vol. 37, no. 6, 1989, pp. 656-659.
[27]S. H. Chen and J. S. Pan, “Fast search algorithm for VQ-based recognition of isolated word,” IEE Proceedings I, Communications, Speech and Vision, vol. 136, no. 6, 1989, pp. 391-396.
[28]S. H. Hwang and S. H. Chen, “Fast encoding algorithm for VQ-based image coding,” Electronics Letters, vol. 26, no. 19, 1990, pp. 1618-1619.
[29]J. J. Chen and S. H. Hwang, “A fast search algorithm on VQ-based LSP quantization,” Proceedings of the National Symposium on Telecommunications, DSP. 3-2, Taiwan, 2002, pp. 395-398.
[30]S. Y. Choi and S. I. Chae, “Incremental-Search Fast Vector Quantiser Using Triangular Inequalities for Multiple Anchors,” Electronics Letters, vol. 34, no. 12, 1998, pp. 1192-1193.
[31]C. H. Hsieh and Y. J. Liu, “Fast Search Algorithms for Vector Quantization of Images Using Multiple Triangle Inequalities and Wavelet Transform,” IEEE Transactions on Image Processing, vol. 9, no. 3, 2000, pp. 321-328.
[32]C. H. Huang, C. Y. Yeh, and S. H. Hwang, “An Improvement of the Triangular Inequality Elimination Algorithm for Vector Quantization,” Special issue of Applied Mathematics and Information Sciences, 2012 (Accepted).
[33]C. H. Lee and L. H. Chen, “Fast closest codeword search algorithm for vector quantization,” IEE Proceedings-Vision, Image and Signal Processing, vol. 141, no. 3, 1994, pp. 143-148.
[34]S. J. Baek, B. K. Jeon, and K. M. Sung, “A fast encoding algorithm for vector quantization,” IEEE Signal Processing Letters, vol. 4, no. 12, 1997, pp. 325-327.
[35]D. Y. Cheng and A. Gersho, “A fast codebook search algorithm for nearest-neighbor pattern matching,” IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 11, 1986, pp. 265-268.
[36]S. J. Beak and K.-M. Sung, “Two Fast Nearest Neighbor Searching Algorithms for Vector Quantization,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E84-A, no. 10, 2001, pp. 2569-2575.
[37]Z. Pan, K. Kotani, and T. Ohmi, “Performance Comparison between Equal-Average Equal-Variance Equal-Norm Nearest Neighbor Search (EEENNS) Method and Improved Equal-Average Equal-Variance Nearest Neighbor Search (IEENNS) Method for Fast Encoding of Vector Quantization,” IEICE Transactions on Information and Systems, vol. E88-D, no. 9, 2005, pp. 2218-2222.
[38]J. S. Pan, Z. M. Lu, and S. H. Sun, “An efficient encoding algorithm for vector quantization based on subvector technique,” IEEE Transactions on Image Processing, vol. 12, no. 3, 2003, pp. 265- 270.
[39]S. X. Chen, F. W. Li, and W. L. Zhu, “Fast searching algorithm for vector quantization based on features of vector and sub-vector,” IET Image Processing, vol. 2, no. 6, 2008, pp. 275-285.
[40]S. X. Chen and F. W. Li, “Fast encoding method for vector quantisation of images using subvector characteristics and Hadamard transform,” IET Image Processing, vol. 5, no. 1, 2011, pp.18-24.
[41]C. C. Chang, D. C. Lin, and T. S. Chen, “An improved VQ codebook search algorithm using principal component analysis,” Journal of Visual Communication and Image Representation, vol. 8, no. 1, 1997, pp. 27–37.
[42]C. C. Chang and W. C. Wu, “Fast Planar-Oriented Ripple Search Algorithm for Hyperspace VQ Codebook,” IEEE Transactions on Image Processing, vol. 16, no. 6, 2007, pp. 1538-1547.
[43]Z. M. Lu, J. S. Pan, and S. H. Sun, “Efficient codeword search algorithm based on Hadamard transform,” Electronics Letters, vol. 36, no. 16, 2000, pp. 1364-1365.
[44]S. Y. Choi and S. I. Chae, “Extended mean-distance-ordered search using multiple l1 and l2 inequalities for fast vector quantization,” IEEE Transactions on Circuit and System II: Analog and Digital Signal Processing, vol. 47, no. 4, 2000, pp. 349-352.
[45]H. Q. Cao and W. Li, “A fast search algorithm for vector quantization using a directed graph,” IEEE Transactions on Circuits and System for Video Technology, vol. 10, no. 4, 2000, pp. 585-593.
[46]M. H. Johnson, R. E. Ladner, and E. A. Riskin, “Fast nearest neighbor search of entropy-constrained vector quantization,” IEEE Transactions on Image Processing, vol. 9, no. 8, 2000, pp. 1435-1437.
[47]K. S. Wu and J. C. Lin, “Fast VQ encoding by an efficient kick-out condition,” IEEE Transactions on Circuits and Systems, vol. 10, no. 1, 2000, pp. 59-62.
[48]Z. Pan, K. Kotani, and T. Ohmi, “A Fast Encoding Method for Vector Quantization Based on 2-Pixel-Merging Sum Pyramid Data Structure,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E86-A, no. 9, 2003, pp.2419-2423.
[49]Z. Pan, K. Kotani, and T. Ohmi, “A Fast Search Method for Vector Quantization Using Enhanced Sum Pyramid Data Structure,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E87-A, no. 3, 2004, pp.764-769.
[50]Z. Pan, K. Kotani, and T. Ohmi, “An Improved Fast Encoding Algorithm for Vector Quantization Using 2-Pixel-Merging Sum Pyramid and Manhattan-Distance-First Check,” IEICE Transactions on Information and Systems, vol. E87-D, no. 2, 2004, pp. 494-499.
[51]Z. Pan, K. Kotani, and T. Ohmi, “An improved full-search-equivalent vector quantization method using the law of cosines,” IEEE Signal Processing Letters, vol. 11, no. 2, 2004, pp. 247-250.
[52]Z. Pan, K. Kotani, and T. Ohmi, “Fast encoding method for vector quantization using modified L2-norm pyramid,” IEEE Signal Processing Letters, vol. 12, no. 9, 2005, pp. 609-612.
[53]C. C. Chang and I. C. Lin, “Fast search algorithm for vector quantisation without extra look-up table using declustered subcodebooks,” IEE Proceedings on Vision, Image and Signal Processing, vol. 152, no. 5, 2005, pp. 513-519.
[54]C. H. Lee, “A Fast Encoding Algorithm for Vector Quantization Using Difference Pyramid Structure,” IEEE Transactions on Communications, vol. 55, no. 12, 2007, pp. 2245-2248.
[55]Y. C. Hu, B. H. Su, and C. C. Tsou, “Fast VQ codebook search algorithm for grayscale image coding,” Image and Vision Computing, vol. 26, no. 5, 2008, pp. 657-666.
[56]C. C. Lee, W. H. Ku, and S. Y. Huang, “A new steganographic scheme based on vector quantization and search-order coding,” IET Image Processing, vol. 3, no. 4, 2009, pp. 243-248.
[57]H. B. Kekre and T. K. Sarode, “Centroid based fast search algorithm for vector quantization,” International Journal of Imaging, vol. 1, no. A08, 2008, pp. 73-83.
[58]H. B. Kekre and T. K. Sarode, “Fast Codevector Search Algorithm for 3-D Vector Quantized Codebook,” WASET International Journal of Computer and Information Engineering, 2008, vol. 2, no. 4, pp. 235–239.
[59]H. B. Kekre and T. K. Sarode, “Fast Codebook Search Algorithm for Vector Quantization Using Sorting Technique,” Proceedings of the International Conference on Advances in Computing, Communication and Control, Mumbai, India, 2009, pp. 317-325.


QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top