跳到主要內容

臺灣博碩士論文加值系統

(44.221.73.157) 您好!臺灣時間:2024/06/17 20:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:鍾明潔
研究生(外文):CHUNG MING CHIEH
論文名稱:改良式向量量化快速搜尋演算法
論文名稱(外文):An improvement of fast search algorithm for vector quantization
指導教授:陳順智陳順智引用關係
學位類別:碩士
校院名稱:南台科技大學
系所名稱:電子工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
中文關鍵詞:Vector Quantization
相關次數:
  • 被引用被引用:1
  • 點閱點閱:186
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
向量量化是以一個索引值取代一個向量值來達到資料壓縮的目的,由於其具有極高的壓縮效率,以及簡單的查表解碼還原過程,因而被廣泛使用在包含影像、聲音等的多媒體技術應用上。
完全搜尋演算法是最基本的向量量化編碼方式,將已經分割好的輸入向量與編碼簿中的所有碼向量逐一作比較以找出最接近此輸入向量的碼向量,並將此碼向量的索引值當成量化結果送到解碼端。此種編碼方式雖然簡單,由於運算量龐大,往往需要花費相當長的時間,為了提升編碼的速度,各種快速搜尋演算法相繼被提出。一般來說,快速搜尋演算法是藉由推導出的數學不等式來刪除某些不可能更接近輸入向量的碼向量,來減少搜尋次數,以加速整體的編碼速度;但若不等式的複雜度或運算量過高,相反地也可能會延誤整體的編碼速度。因此,本研究延伸部分和原理,利用推導出的不等式以刪除更多不必要實際計算歐基里德距離的碼向量。根據實驗及模擬的結果,提出的演算法可以大量減少不必計算距離的碼向量,在不等式的複雜度與縮小的搜尋次數間取得最佳平衡以獲得令人滿意的壓縮編碼速度,且維持與完全搜尋演算法相同的編碼品質。
目 次
摘要 iv
ABSTRACT v
誌謝 vi
目次 vii
表目錄 ix
圖目錄 x
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 論文架構 2
第二章 向量量化 4
2.1 前言 4
2.2 向量量化 4
2.2.1 向量量化基本原理 4
2.2.2 向量量化編解碼過程 5
2.3 編碼簿的設計 8
2.3.1 LBG演算法 8
2.3.2 初始編碼簿的產生 10
2.4 影像的向量量化 10
第三章 快速搜尋演算法 13
3.1 前言 13
3.2 A Fast Mean-Distance-Ordered Partial Codebook Search Algorithms for Image Vector Quantization 14
3.3 Fast VQ Encoding by An Efficient Kick-Out Condition 16
3.4 A Fast Search Algorithm for Vector Quantization Using L2-Norm Pyramid of Codevectors 19
3.5 A Hierarchical Fast Encoding Algorithm for Vector Quantization with PSNR Equivalent to Full Search 23
第四章 改良式快速搜尋演算法 26
4.1 前言 26
4.2 不等式的推論 26
4.3 改良式快速搜尋演算法 27
4.4 實驗及模擬之結果與分析 29
第五章 結論 43
參考文獻 44







表目錄
表1 以FSA為基準的CPU執行時間比率 33
表2 以FSA為基準的沒有被刪除必須採用PDE的碼向量數量比率 34













圖目錄
圖2.1 向量量化編碼流程圖 6
圖2.2 向量量化解碼流程圖 7
圖2.3 LBG 演算法流程圖 9
圖2.4 影像切割後編號 11
圖2.5 影像向量量化編碼過程示意圖 12
圖2.6 影像向量量化解碼過程示意圖 12
圖3.1 搜尋順序和搜尋範圍 15
圖3.2 搜尋順序 19
圖3.3 金字塔型資料結構 20
圖3.4 排序過的編碼簿以及各階層資料表 22
圖3.5 依總和大小順序排列的總和、部份和、碼向量,以及搜尋順序和搜尋範圍 25
圖4.1 依總和大小順序排列的總和、部份和、碼向量,以及搜尋順序和搜尋範圍 29
圖4.2 測試影像Lena 30
圖4.3 測試影像Pepper 30
圖4.4 測試影像Baboon 31
圖4.5 測試影像Girl 31
圖4.6 重建影像Lena,編碼簿大小256,向量維度 35
圖4.7 重建影像Lena,編碼簿大小512,向量維度 35
圖4.8 重建影像Lena,編碼簿大小256,向量維度 36
圖4.9 重建影像Lena,編碼簿大小512,向量維度 36
圖4.10 重建影像Pepper,編碼簿大小256,向量維度 37
圖4.11 重建影像Pepper,編碼簿大小512,向量維度 37
圖4.12 重建影像Pepper,編碼簿大小256,向量維度 38
圖4.13 重建影像Pepper,編碼簿大小512,向量維度 38
圖4.14 重建影像Baboon,編碼簿大小256,向量維度 39
圖4.15 重建影像Baboon,編碼簿大小512,向量維度 39
圖4.16 重建影像Baboon,編碼簿大小256,向量維度 40
圖4.17 重建影像Baboon,編碼簿大小512,向量維度 40
圖4.18 重建影像Girl,編碼簿大小256,向量維度 41
圖4.19 重建影像Girl,編碼簿大小512,向量維度 41
圖4.20 重建影像Girl,編碼簿大小256,向量維度 42
圖4.21 重建影像Girl,編碼簿大小512,向量維度 42
[1]R. M. Gray, “Vector quantization,” IEEE ASSP Mag., pp. 4-29, Apr. 1984.
[2]C. D. Bei and R. M. Gray, “An improvement of the minimum distortion encoding algorithm for vector quantization,” IEEE Trans. Commun., Vol. 33, pp. 1132-1133, Oct. 1985.
[3]M. R. Soleymani and S. D. Mogera, “An efficient nearest neighbor search method,” IEEE Trans. Commun., Vol. COM-35, pp. 677-679, June 1987.
[4]M. R. Soleymani and S. D. Mogera, “A fast MMSE encoding technique for vector quantization,” IEEE Trans. Commun., Vol. COM-37, pp. 656-659, June 1989.
[5]K. K. Paliwal and V. Ramasubramanian, “Effect of ordering the codebook on the efficiency of the partial distance search algorithm for vector quantization,” IEEE Trans. Commun., Vol. COM-37, pp. 538-540, May 1989.
[6]S. H. Huang and S. H. Chen, “Fast encoding algorithm for VQ-based image coding,” Electron. Lett., Vol. 26, pp. 1618-1619, Sept. 1990.
[7]C. M. Huang, Q. Bi, G. S. Stiles, and R. W. Harris, “Fast full search equivalent encoding algorithms for image compression using vector quantization,” IEEE Trans. Image Processing., Vol. 1, pp. 413-416, July 1992.
[8]S.-W. Ra and J.-K. Kim, “A fast mean-distance-ordered partial codebook search algorithms for image vector quantization,” IEEE Trans. Circuits Syst.II: Analog and Digital Signal Process., Vol. 40, pp. 576-579, Sept. 1993.
[9]G. Poggi, “Fast algorithm for full search VQ encoding,” Electron. Lett., Vol. 29, pp. 1141-1142, June 1993.
[10]L. Torres and J. Huguet, “An improvement on codebook search for vector quantization,” IEEE Trans. Commun., Vol. 42, pp. 208-210, Feb./Mar./Apr. 1994.
[11]W. Li and E. Salari, “A fast vector quantization encoding method for image compression,” IEEE Trans. Circuits Syst. Video Technol., Vol. 5, pp. 119-123, Apr. 1995.
[12]C. H. Lee and L. H. Chen, “A fast search algorithm for vector quantization using mean pyramids of codevectors,” IEEE Trans. Commun., Vol. 43, pp. 1697-1702, Feb. 1995.
[13]K.-S. Wu and J.-C. Lin, “Fast VQ encoding by an efficient kick-out condition,” IEEE Trans. Circuits Syst. Video Technol., Vol. 10, pp. 59-62, Feb. 2000.
[14]J. S. Pan, Z. M. Lu, and S. H. Sun, “Fast codevector search algorithm for image coding based on mean-variance pyramids of codevectors,” Electron. Lett., vol. 36, no. 3, pp. 210–211, Feb. 2000.
[15]B. C. Song and J. B. Ra, “A fast search algorithm for vector quantization using L2-norm pyramid of codevectors,” IEEE Trans. Image Processing., Vol. 11, pp. 10-15, Jan. 2002.
[16]Z. Pan and K. Kotani and T. Ohmi, “A hierarchical fast encoding algorithm for vector quantization with PSNR equivalent to full search,” IEEE ISCAS. Circuits Syst., Vol. 1, pp. 797-800, 2002.
[17]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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top