Please use this identifier to cite or link to this item:
標題: 基於排序移動估測演算法研究及架構設計與實現
Analysis and Architecture Design of Sorting-based Motion Estimation Algorithm
作者: 賴彥芳
Lai, Yen-Fang
關鍵字: Video Compression;影像壓縮;Motion Estimation;VLSI;移動估測;超大型積體電路
出版社: 電機工程學系所
引用: [1] Information Technology - Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbit/s - Part 2: Video, ISO/IEC 11172-2, 1993 [2] Information Technology - Generic Coding of Moving Pictures and Associated Audio Information: Video, ISO/IEC 13818-2 and ITU-T Recommendation H.262, 1996. [3] Information Technology - Coding of Audio-Visual Objects - Part 2: Visual, ISO/IEC 14496-2, 1999. [4] Video Codec for Audiovisual Services at p × 64 Kbit/s, ITU-T Recommendation H.261, Mar. 1993. [5] Video Coding for Low Bit Rate Communication, ITU-T Recommendation H.263, Feb. 1998. [6] Draft ITU-T recommendation and final draft international standard of joint video specification(ITU-T Rec. H.264/ISO/IEC 14 496-10 AVC), in Joint Video Team(JVT)of ISO/IEC MPEG and ITU-T VCEG, JVT-G050, 2003. [7] K. M. Yang, M. T. Sun, and L. Wu, “A Family of VLSI Designs for the Motion Compensation Block-Matching Algorithm,” IEEE Trans. on Circuit and Syst., vol. 36, no. 10, Oct. 1989. [8] T. Koga, K. Iinuma, A. Hirano, Y. Iijima and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proc. Nut. Telecommun. Conf., pp. G5.3.1-5.3.5, Nov. 1981. [9] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrest- ricted center-biased diamond aearch algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, no. 4, pp. 369-378, Aug. 1998. [10] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transactions on Image Processing, vol. 9, pp. 287-290, Feb. 2000. [11] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. on Circuits and Syst. Video Technol., vol. 6, no. 3, pp. 313-317, Jun. 1996. [12] W. Li and E. Salari, “Successive elimination algorithm for motion estimation,” IEEE Trans. Image Processing, vol. 4, pp. 105-107, Jan. 1995. [13] X. Q. Gao, C. J. Duanmu, and C. R. Zou, “A multilevel successive elimination algorithm for block matching motion estimation,” IEEE Trans. Image Processing, vol. 9, pp. 501-504, Mar. 2000. [14] M. Brunig and W. Niehsen, “Fast full-search block matching,” IEEE Trans. Circuits Syst. Video Technol., vol. 11, pp. 241-247, Feb. 2001. [15] Y. W. Huang, S. Y. Chien, B. Y. Hsieh and L. G. Chen, “Global elimination algorithm and architecture design for fast block matching motion estimation,” IEEE Trans. on Circuits and Syst. for Video Technol., Vol. 14, pp. 898-907, 2004. [16] J. N. Kim, D. K. Kang, S. C. Byun, I. L. Lee and B. H. Ahn, “A fast full search motion estimation algorithm using sequential rejection of candidates from hierarchical decision structure,” IEEE Trans. on Broadcasting., Vol. 48, pp. 43-46, 2002. [17] T. G. Ahn, Y. H. Moon, and J. H. Kim, “Fast full search motion estimation base on multilevel successive elimination algorithm,” IEEE Trans. on Circuits and Syst. for Video Technol., Vol. 14, pp 1256-1269, 2004 [18] T. Komarek and P. Pirsch, “Array architectures for block matching algorithms,” IEEE Trans. on Circuit and Syst., vol. 36, no. 10, Oct. 1989. [19] H. Yeo and Y. H. Hu, “A novel modular systolic array architecture for full-search block matching motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 5, pp. 407-416, Oct. 1995. [20] H. M. Jong, L. G. Chen, and T. D. Chiueh, “Accuracy improvement and cost reduction of the 3-step search block-matching algorithm for video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 88-90, Feb. 1994.
在視訊編碼系統中,移動估測(motion estimation)需要相當龐大的運算量。本論文提出一個快速全域演算法及架構,它所重建的畫面和全域搜尋區塊演算法(Full search block matching Algorithm,FSBMA)擁有相同的畫質,且大幅地降低運算量。

本論文提出一個以排序為基礎的移動估測演算法,並將其演算法轉換成對應的硬體電路。演算法分析採用C語言進行模擬,可得重建畫面的峰值訊號雜訊比(Peak signal noise ratio,PSNR)與FSBMA相同,且在搜尋範圍設定為[-16,15],平均每個區塊的搜尋點數約47個,佔FSMBA的4.59%。硬體架構大致上分為記憶體(儲存current block data及search area data)、平行計算單元(計算sub-block像素和)、SAD Tree(計算msea及SAD)、排序單元(排序msea值)、取代單元(執行minimal SAD取代)及控制單元(控制硬體依data flow動作)等。晶片實作部分,採用CIC提供的cell-based標準元件庫以及TSMC 0.18um 1P6M製程實作,可在24.14 MHz的頻率下,以每秒30張畫面的速率,處理CIF(352 × 288)解析度的畫面。最高工作頻率為66 MHz,消耗功率為109.0 mW,晶片面積為2.08 × 2.08 mm2。


In the video coding system, the motion estimation requires a large of computational complexity. This paper proposed a fast full search algorithm and architecture, that reconstructed image and full search algorithms have the same quality, and significantly reduce the computational complexity.
In the thesis, a sorting-based motion estimation algorithm is proposed and transformed the algorithm into the corresponding hardware circuit. The algorithms using C language to simulate it, the peak signal noise ratio (PSNR) of reconstructed image is the same as FSBMA. In search range of [-16,15], the average search points per block is 47, occupying 4.59% of FSBMA. The proposed hardware architecture would be divided into memory ( store current block data and search data ), parallel computing unit ( compute sum of sub-block data ), SAD Tree ( compute msea and SAD value ), sorter (sorting msea value ), replacer ( to replace the implementation of minimal SAD ) , control unit ( according to data flow action ) and so on. The proposed architecture has been implemented using standard cell methodology by TSMC 0.18um 1P6M process technology. The proposed architecture can process CIF resolution pictures in 30 frames per second at 24.14 MHz. However, it can work at 66 MHz and the power consumption is about 109 mW. As a result, the chip area is 2.08 × 2.08 mm2.
In conclusion, the proposed motion estimation algorithm and architecture with a significant saving in computing the amount of results. We sincerely hope that our research results can make progress for the video technology.
其他識別: U0005-2906201117290200
Appears in Collections:電機工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.