跳到主要內容

臺灣博碩士論文加值系統

(44.192.38.248) 您好!臺灣時間:2022/11/27 00:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:李安邦
研究生(外文):An-Pang Li
論文名稱:適用於移動估計視訊編碼之改良式鑽石搜尋演算法及其晶片設計
論文名稱(外文):An Enhanced Diamond Search Algorithm and It's VLSI Architecture for Motion Estimation in Video Coding
指導教授:呂紹偉
指導教授(外文):Shao-Wei Lew
學位類別:碩士
校院名稱:國立臺灣海洋大學
系所名稱:電機工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:60
中文關鍵詞:移動估計區塊匹配鑽石搜尋演算法Verilog
外文關鍵詞:Motion EstimateBlock MatchingDiamond Search algorithmVerilog
相關次數:
  • 被引用被引用:0
  • 點閱點閱:323
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近幾年來,隨著數位科技的進步與網際網路的蓬勃發展,多媒體和行動通訊不論在技術或市場上都有大幅的成長,包含影像、聲音與視訊之多媒體資料日益龐大,這些多媒體資料需要很大的儲存空間和傳輸頻寬,所以在儲存或傳送多媒體資料時大多使用資料壓縮的技術。在視訊壓縮標準中,移動估計(Motion Estimation)扮演著相當關鍵的技術。區塊匹配(Block Matching)是目前普遍使用的方法,而全區域搜尋演算法可獲得最佳的影像品質,但計算量極大,如果要符合即時視訊編碼,將付出極大的硬體成本。所以在維持不錯的影像品質下,許多快速搜尋演算法被提出,如三步搜尋演算法、四步搜尋演算法、鑽石搜尋演算法等。
本論文提出一種可改善鑽石搜尋(Diamond Search)演算法的新方法,我們稱之為改良式鑽石搜尋演算法。此演算法依據特定的搜尋原則,動態決定需要比對的區塊,並採用一種即時中斷的決策法,當匹配區塊與預測區塊的差異值為零時,直接輸出此匹配區塊位置,因此可減少區塊搜尋數目,達到降低計算量的目的。因所需計算量較少,相當適用於可攜式裝置,如行動電話或數位像機等。經實驗結果得知,我們所提出的演算法計算量比鑽石搜尋演算法減少30%,且能維持一定的影像品質。並針對此演算法提出平行處理的架構,而電路實現是以Verilog撰寫可合成RTL模型,最高工作頻率為91 MHz,並以TSMC 0.35µm 2P4M 標準元件庫完成晶片設計。
With the advances of digital technologies and the proliferation of communication networks, multimedia contents consisting of both audio and video recordings continue to grow at an enormous rate. Multimedia, especially video, data normally takes huge storage space and also requires substantial amount of channel bandwidth to transmit. Consequently, data compression has become an indispensable tool of trade when dealing with multimedia data. For the compression of video data, motion estimation represents a class of critical technologies. To implement motion estimation, block matching is the most frequently used technique. Among the various search strategies to perform block matching, full search obviously gives the best picture quality, but requires heavy computation. This could mean very high hardware cost for real-time video encoding. To limit the hardware cost while keeping the picture quality at an acceptable level, many fast block search algorithms have been proposed, such as three-step search (TTS), four-step search (4SS), and diamond search (DS) algorithms.
In this thesis, we propose an enhancement to the diamond search algorithm. This new algorithm combines the DS with other previously proposed search strategies and is able to select its candidate block more efficiently. Also by stopping the search process right after the best-matched block is found, the number of candidate blocks to compare is substantially reduced. The reduction of computation makes easier for adopting the algorithm in mobile devices such as cell phones and digital cameras. Experimental results show that our algorithm outperforms the diamond search by requiring 30% less computations while keeping the picture quality comparable. To show the feasibility of our algorithm, we also propose a tree-based parallel computing architecture. We describe the architecture as a synthesizable RTL model using the Verilog HDL and implement the chip by using the TSMC 0.35um 2P4M standard library. The maximum clock frequency of the chip reaches 91 MHz.
第一章 導論………………………………………………. 1
1.1 前言……………………………………………………….. 1
1.2 研究動機與目的………………………………………….. 3
1.2 論文組織.............................................................................. 3
第二章 移動估計演算法..................................................... 5
2.1 區塊匹配演算法………………………………………….. 6
2.2 區塊匹配評量標準……………………………………….. 7
2.3 移動補償流程…………………………………………….. 9
2.4 各種移動估計的介紹…………………………………….. 10
2.4.1全區域搜尋演算法…………………………………... 10
2.4.2三步搜尋演算法……………………………………... 12
2.4.3鑽石搜尋演算法……………………………………... 15

第三章 改良式鑽石搜尋演算法…………………………. 19
3.1簡述....................................................................................... 19
3.2演算法與流程圖................................................................... 20
3.3模擬結果…………………………………………………... 27

第四章 硬體架構與實現…………………………………. 33
4.1電路架構…………………………………………………... 33
4.2運算單元設計....................................................................... 34
4.3位址產生器………………………………………………... 36
4.4控制單元設計……………………………………………... 37
4.5效能分析…………………………………………………... 39
4.6晶片實作…………………………………………………... 39
4.6.1設計流程……………………………………………... 39
4.6.2演算法驗證…………………………………………... 40
2.6.3電路實現與驗證……………………………………... 41

第五章 結論與未來發展…………………………………. 42

參考文獻………………………………………………………. 43
附錄 A Matlab程式…………………………………………. 45
A-1測試樣版程式……………………………………………... 45
A-2改良式鑽石搜尋演算法程式……………………………... 46
附錄 B Verilog程式…………………………………………. 57
[1] ITU-T Rec. H.262, ISO/IEC 13818-2: Information Technology-Generic Coding of Moving Pictures and Associated Audio Information, Part 2: Video, Draft International Standard, 1994.
[2] S. Zhu and K. K. Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion,” IEEE Trans. Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000.
[3] P. Kuhn, Algorithms, Complexity Analysis and VLSI Architectures for MPEG-4 Motion Estimation. Kluwer Academic Publishers, 1999.
[4] V. G. Moshnyaga, “An Adaptive Block-Matching Algorithm for Motion Estimation,” IEEE International Conference on Acoustics, Speech, and Signal Processing, vol. 4, pp. 1953-1956, Mar. 1999.
[5] H. Gharavi and H. Reza-Alikhani, “Pel-recursive Motion Estimation Algotithm,” IEEE Electronics Letters, vol. 37, issue 21, pp. 1285-1286, Oct. 2001.
[6] N. Habili, A.R. Moini, and N. Burgess, “A Variable Search Count Block-Matching Algorithm for Video Coding,” (TENCON '99). Proceedings of the IEEE Region 10 Conference, vo1. 1, pp. 108-111, 1999.
[7] L.K. Liu and E. Feig “A Block-Based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding,” IEEE Trans. Circuit and Systems for Video Technology, vol. 6, no. 4, pp. 419-423, Aug. 1996.
[8] R. C. Gonzalez and R. E. Wood, Digitial Image Processing, 2nd ed. Prentice-Hall, 2002.
[9] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion Compensated Interframe Coding for Video-Conferencing,” in Proc. NTC’81, pp. G5.3.1-G5.3.5, 1981.
[10] K. M. Yang, M. T. Sun, and L. Wu, “A Family of VLSI Designs for the Motion Compensation Block-Matching Algorithm,” IEEE Trans. Circuits and Systems, vol. 36, no. 10, pp. 1317-1325, Oct. 1989.
[11] L. D. Vos and M. Stegherr, “Parameterizable VLSI Architectures for the Full-Search Block-Matching Algorithm” IEEE Trans. Circuits and Systems, vol. 36, no. 10, pp. 1309-1316, Oct. 1989.
[12] E. G. Tzeng and C. Y. Lee, “An Efficient Memory Architecture for Motion Estimation Processor Design,” 1995 IEEE International Symposium on Circuits and Systems (ISCAS '95), vol. 1, pp. 712-715, May 1995.
[13] W. M. Chao, C. W. Hsu, Y. C. Chang, and L. G. Chen, “A Novel Hybrid Motion Estimator Supporting Diamond Search and Fast Full Search,” 2002 IEEE International Symposium on Circuits and Systems (ISCAS '02), vol. 2, May 2002.
[14] Y. S. Jehng, L. G. Chen, and T. D. Chiueh, “An Efficient and Simple VLSI Tree Architecture for Motion Estimation Algorithms,” IEEE Trans. Signal Processing, vol. 41, pp. 889-900, Feb. 1993.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top