Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/6982
標題: 應用於全域搜尋移動估測的次取樣前處理快速全域淘汰演算法設計與VLSI實作
VLSI Design of Fast Global Elimination Algorithm with Sub-sampling Preprocess for Full Search Motion Estimation
作者: 林聲偉
Lin, Sheng-Wei
關鍵字: Motion estimation;移動估測;ME;FGEA;全域搜尋;視訊壓縮
出版社: 電機工程學系所
引用: [1] W. Li and E. Salari, “Successive elimination algorithm for motion estimation,” IEEE Trans. Image Processing, vol. 4, pp. 105-107 , Jan. 1995. [2] 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. [3] 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. Circuits Syst. Video Technol. vol. 14, pp. 898-907, June 2004. [4] Y. W. Huang, C. H. Tsai and L. G. Chen, “Parallel global elimination algorithm and architecture design for fast block matching motion estimation,” IEEE Trans. Circuits Syst. Video Technol. vol. 5, pp. 153-6, May 2004. [5] J. F. Yang, S. C. Chang, and C. Y. Chen, “Computation Reduction for motion search in low rate video coders,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp. 948-951, Oct. 2002. [6] R. Li, B. Zeng, and M.L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438-443, Aug. 1994. [7] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 313-317, June 1996. [8] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block matching motion estimation,” IEEE Trans. Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000. [9] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol. vol. 8, pp. 369-377, Aug. 1998. [10] Y. S. Chen, Y. P. Huang, and C. S. Fuh, “Fast block matching algorithm based on the winner-update strategy,” IEEE Trans. Image Processing, vol. 10, pp. 1212-1222, Aug.2001. [11] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation ,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, issue 5, pp.349-355, May 2002. [12] K. M. Yang, M. T. Sun, and L. Wu, “A family of VLSI designs for the motion compensation block matching algorithm,” IEEE Trans. Circuits Syst., vol. 36, pp. 1317-1325, Oct. 1989. [13] T. Komarek and P. Pirsch, “Array architectures for block matching algorithms, ”IEEE Trans. Circuits Syst., vol. 36, pp. 1301-1308, Oct. 1989. [14] 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. [15] Y. K. Lai and L. G. Chen, “A data-interlacing architecture with two dimensional data-reuse for full-search block matching algorithm,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 124-127, Apr. 1998.
摘要: 
本論文我們提出了一個快速且有效率的全域搜尋移動估測演算法,透過次取樣前處理的技術,應用在視訊壓縮的全域搜尋移動估測演算法中,也因此減少了區塊比對的運算花費,同時加快了移動估測(ME)的處理速度。而我們所提出的FGEA(fast global elimination algorithm),主要是參考之前的全域搜尋移動估測演算法: MSEA(multilevel successive elimination algorithm)與GEA,而這兩個演算法主要的觀念即是透過某些前處理運算先過濾一些沒有參考價值的後選區塊(candidate block),如此可大量減少區塊比對的次數同時增加ME 的處理速度。而我們的演算法主要是修改前處理單元的運算方式,利用subblock absolute difference (subblock-AD)和的計算(SSAD)找出較有參考價值的candidate block,再從這些有參考價值的candidate block 利用absolute difference (SAD)和的比對準則求出最後的移動向量(motion vector)。分析模擬結果顯示,我們提出的演算法可以減少約38%的相減絕對值(AD)的計算花費,在平均執行時間也要比 GEA 快1.64倍,在跟 FSBMA 比較下仍可維持非常接近的影像品質。
此外我們也提出了FGEA 相對應的 VLSI 硬體架構,其中包括六個核心的模組: 如四組並列式先進先出架構 four parallel FIFO(計算subblock 和的資料)、SAD tree(計算SSAD與SAD)、CMP1(在搜尋範圍中找出有參考價值的候選區塊)、CMP2(在有參考價值的候選區塊中找出最後的移動向量)、on chip記憶體(儲存search area與current block資料)與控制單元(控制整個ME的流程)等等。合成結果顯示我們所提出的架構之 gatecount 比 GEA 的架構要來的少,且操作頻率也只有 24.72MHz。也因此我們的架構在面積與速度的平均效能上,是比許多的 FSBMA 架構要來的好。

In this thesis, a fast and efficient full search algorithm, which is accelerated by sub-sampling preprocess, is proposed to reduce the computation costs of block matching algorithm for full search motion estimation in video compressions. The proposed fast global elimination algorithm (FGEA) is derived from the previous GEA and multilevel successive elimination algorithm (MSEA), which can skip unnecessary search positions by the preprocessing unit. We employ the preprocessing unit to calculate the sub-sampling sum of subblock absolute difference (subblock-AD) for each candidate macro-block (MB) in the search range, where the preprocessing can select a number of probable candidate motion blocks. Then we calculate the sum of absolute difference (SAD) from these selected candidate blocks and find out the final motion vector. Simulation results show that the proposed fast full search algorithm can reduce about 38% absolute difference (AD) costs and performs average 1.64 faster runtime than the previous GEA method on the basis of the same compensated video quality with the FSBMA.
Moreover, we also propose the VLSI architecture of the FGEA, which includes six core modules, such as four parallel FIFO(compute sum of subblock data), SAD tree(compute SSAD and SAD values), CMP1(find out the probable candidate blocks in search range), CMP2(find out the motion vector in probable candidate blocks), on chip memory(save current block and search area data) and Control Unit(control ME flow), etc. Synthesis reports show that the gate count of our architecture is fewer than that of the GEA architecture, and then the operation frequency of our architecture is only 24.72MHz. So the area-speed performance of our architecture is better than that of many FSBMA architectures.
URI: http://hdl.handle.net/11455/6982
其他識別: U0005-2607200613411600
Appears in Collections:電機工程學系所

Show full item record
 

Google ScholarTM

Check


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