以新的排序技術用於部分失真搜尋之最佳化視訊編碼運動估計演算法

New String Techniques on Partial Distortion Search for Fast Optimal Motion Estimation of the Video Encoding

邱建宏(Jian-Hong Ciou)

指導教授 ： 陳弘明

共同指導教授 ： 陳世穎(Shih-Ying Chen)

國立臺中科技大學/資訊與流通學院/資訊工程系碩士班/碩士(2012年)

https://doi.org/10.6826/NUTC.2012.00027

摘要

運動估計演算法(motion estimation)已被廣泛使用於許多與視訊相關的應用，例如視訊壓縮、視訊分割與視訊追蹤。因此，一個具備高效能的運動估計快速區塊比對(block matching algorithm)演算法已得到相當的重視，並廣泛的應用於現代視訊編碼的標準中，如ISO/IEC MPEG 1/2/4和ITU - T H.263/H.264。根據以往的實驗結果顯示運動估計佔H.264編解碼器60%(一個參考畫面)至百分之80%(五個參考畫面)的總編碼時間。全搜尋區塊匹配(full search block matching, FSBM)方法是第一個被提出用來搜尋最佳匹配區塊的運動估計演算法。由於全搜尋區塊匹配演算法的計算量太高，並不適合用於即時性的編解碼目的。因此，為了減少全搜尋區塊匹配演算法極高的運算複雜度，許多針對運動估計運算複雜度問題的快速演算法被提出。部分失真搜尋(partial distortion search, PDS)是相當有名的無失真快速運動估計演算法，並且被採用於H.264/AVC中，它採用提前終止的觀念，利用累加部分的SAD來消除不可能匹配的區塊，藉此加速運動估計的運算。在本論文中，本研究提出了兩個可用於H.264/AVC的區塊搜尋排序技術來加速PDS淘汰候選區塊的速度，使得PDS能夠得到更好的匹配順序(matching order)。在第一個方法中，匹配順序會藉由將欲編碼區塊與候選區塊進行位移操作後所取得的差級集合(level difference set)中計算出來，並將此順序用於部分失真搜尋演算法上；在第二方法中，藉由計算欲編碼區塊內各個像素與平均像素值的差距來排序像素點計算SAD的順序。實驗結果顯示，第一個方法屬於無失真的運動估計方法，PSNR上與PDS相同，但擁有較低的運算複雜度；而第二個方法與失真方法NPDS進行比較，能夠有效降低運算複雜度，並擁有相似的影像品質，本研究成功的達到降低運算量的目的。

關鍵字

運動估計 ； 部份失真搜尋 ； 視訊編碼

並列摘要

Motion estimation has been widely used in many video applications such as video compression, video segmentation, and video tracking. Efficient block matching algorithms (BMAs) have received considerable attention and have been adopted in modern video compression standards such as ISO/IEC MPEG1/2/4 and ITU-T H.263/H.264. The experimental results have shown motion estimation can consume 60% (1 reference frame) to 80% (5 reference frames) of the total encoding time of H.264 codec. The Full-Search MB-Matching (FSBM) method was first proposed to search for the best matching image MB. As this algorithm has large computational overhead, it is not suitable for real time purposes. Partial distortion search (PDS) is a good example of the fast matching method. PDS, which is a basic early termination scheme, uses the accumulated partial sum of absolute difference (SAD) to eliminate the impossible candidates of motion vector in a matching block.
In this thesis, we proposed two new sorting techniques to get a better matching order on the lossless partial distortion search algorithm. In the first method, by sorting the level difference sets calculated from the approximate distortion between the two-bit transformed coding block and candidate block, the matching order can be computed to apply to the typical PDS. In the second method, we sort pixel calculation of the matching order of SAD by the difference between the block mean and inter pixel value.
Experimental results show that two proposed methods can effectively reduce the computational complexity without affecting the video quality, reductions in computational complexity were achieved.

並列關鍵字

motion estimation ； partial distortion search ； video encoding

參考文獻

[2] K.L. Chung, Y.S. Lai, and P.L. Huang, “An Efficient Predictive Watershed Video Segmentation Algorithm Using Motion Vectors,” Journal of Information Science and Engineering, 26, 2010, pp. 699- 711, 2010.

[1] A. Puria, X. Chenb, and A. Luthrac, “Video Coding Using the H.264/MPEG-4 AVC Compression Standard,” SP:IC(19), No. 9, pp. 793-849, October 2004.

[3] J.A. Vijverberg, M.J.H. Loomans, C.J. Koeleman and P.H.N. de With, “Two Novel Motion-based Algorithms for Surveillance Video Analysis on Embedded Platforms,” Real-Time Image and Video Processing, Proc. SPIE 7724, pp.772401, 2010.

[6] Reoxiang Li, Bing Zeng and Liou, M.L, “A New Three-step Search Algorithm for Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 4,pp.438-442, Aug. 1994.

[7] Lai-Man Po, Wing-Chung Ma, “A Novel Four-step Search Algorithm for Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Vol 6, pp.313 –317, June 1996.