摘要
向量量化能使語音或影像等資料保持一定的品質下，依然得到良好的壓縮率，因此能有效的降低資料量，而近年來因多媒體的蓬勃發展，使得語音或影像資料量也越來越大，如何加快傳輸速度與結省儲存空間是很重要的問題，因此向量量化的技術被廣泛應用在這上面。然而傳統的搜尋方法需要花費大量的時間，因此許多可以加快搜尋到最佳解速度的方法陸陸續續被提出來。本研究即是提出了一個可提高向量量化效率的搜尋方法，此方法使用了Principal Component Analysis的技術降低資料維度，為了能在降維的過程中保留較多資料特性，我們使用了2~5維做比較，降維後的資料以樹狀結構加速initial codeword的搜尋，並使用Voronoi Diagram 建立鄰居關係表，在找到initial codeword後依據鄰居關係來制定codeword的搜尋範圍，得到搜尋範圍後回到原始維度找出最佳解，為了改善搜尋速度，我們使用了greedy search，再將Voronoi Diagram的鄰居分群來加快搜尋，此方法能在降低搜尋時的計算量時，依然有較小的誤差。實驗結果也顯示，此方法與其他方法比較有較好的結果。
關鍵字：codebook search; principal component analysis; Voronio diagram; tree structure

Abstract
Vector quantization (VQ) technique has been used in various application. Because of the time-consuming of traditional codeword search, lots of methods which save computation time of the best codeword search had been proposed. This paper proposes a new search method to enhance the performance of the VQ search method. The method use principal component analysis (PCA) to reduce dimension, Voronoi diagram to determine the adjacency-list, and tree structure to raise up the initial codeword search speed. In order to keep more data characteristics, we used high dimensional of PCA. After finding the initial codeword by tree structure VQ, we used the VD to decide neighbors of initial codeword to obtain the closer result. With the experimental results, the proposed method has better results than the other method.
Keywords-codebook search; principal component analysis; Voronio diagram; tree structure

目錄
A Hybrid VQ Algorithm Combining Tree Structure and VD 1
混合樹狀結構與范諾圖之混合式向量量化編碼 1
摘要 i
Abstract ii
致謝 iii
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1研究動機 1
1.2研究目的 2
1.3相關背景與相關文獻回顧 3
第二章 Hybrid VQ Search Method 9
2.1 Principal Component Analysis 10
2.2 Tree Structure 11
2.3 Voronoi Diagram 13
2.4 Vector Search Procedure 17
第三章 實驗結果與討論 20
3.1 PCA包含的變異量的影響 20
3.2 TSVQ的影響 22
3.4 VD鄰居數量的影響 28
3.6與其他分法的比較 41
第四章 結論 43
References 44

References
[1]R. M. Gray, “Vector quantization,” IEEE Acoust., Speech, Signal Process. Mag., vol. 1, no. 2, pp. 4–29, Apr. 1984.
[2]Y. Linde, A. Buzo, and R. M. Gray, “An algorithm for vector quantizer design,” IEEE Trans. Commun., vol. COM-28, no. 1, pp. 84–95, Jan. 1980.
[3]C. C. Chang and I. C. Lin, “Fast search algorithm for vector quantisation without extra look-up table using declustered subcodebooks,” IEEE Proc. Vis., Image, Signal Process., vol. 152, no. 5, pp. 513–519, Oct. 2005.
[4]L. Torres and J. Huguet, “An improvement on codebook search for vector quantisation,” IEEE Trans. Commun., vol. 42, no. 2, pp. 208–210, Feb. 1994.
[5]H. Park and V. K. Prasana, “Modular VLSI architectures for real-time full-search-based vector quantization,” IEEE Trans. Circuits Syst. Video Technol., vol. 3, no. 4, pp. 309–317, Aug. 1993.
[6]C. D. Bei and R. M. Gray, “An improvement of the minimum distortion encoding algorithm for vector quantization,” IEEE Trans. Commun., vol. 33, no. 10, pp. 1132–1133, Oct. 1985.
[7]C. C. Chang and T. S. Chen, “New tree-structured vector quantization with closest-coupled multipath searching method,” Opt. Eng., vol. 36, no. 6, pp. 1713–1720, Jun. 1997.
[8]W. C. Chu, "Embedded quantization of line spectral frequencies using a multistage tree-structured vector quantizer," IEEE Trans. Audio, Speech, Language Process., vol. 14, no. 4, pp 1205-1217, Jul. 2006.
[9]J. Makhoul, S. Roucos, and H. Gish, “Vector quantization in speech coding,” Proc. IEEE, vol. 73, pp. 1551–1588, Nov. 1985.
[10]C. C. Chang, F. J. Shiue, and T. S. Chen, “Tree structured vector quantization with dynamic path search,” in Proc. Int. Workshop on Multimedia Network Systems, Aizu, Japan, pp. 536–541, Sep. 1999.
[11]C. C. Chang, D. C. Lin, and T. S. Chen, “An improved VQ codebook search algorithm using principal component analysis,” J. Vis. Commun. Image Represent., vol. 8, no. 1, pp. 27–37, Mar. 1997.
[12]S. J. Wang and C. H. Yang, “Hierarchy-oriented searching algorithms using alternative duplicate codewords for vector quantization mechanism,” Appl. Math. Comput., vol. 162, no. 2, pp. 559–576, Mar. 2005.
[13]C. C. Chang, W. C. Wu, "Fast Planar-Oriented Ripple Search Algorithm for Hyperspace VQ Codebook", IEEE Transaction on image processing, vol 16, no.6, pp.: 1538-1547, Jun. 2007.
[14]A. Okabe, B. Boots, and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. New York: Wiley, 1992.