在本篇論文中，我們總共提出了三個適用於區塊式動態影像編碼之移動估測演算法。區塊式移動估測已於十數年來廣泛使用於多種動態影像壓縮標準，例如MPEG-1、MPEG-2、MPEG-4、與H.263等。自從2001年Joint Video Team的MPEG以及VCEG協會共同開發H.264/MPEG-4 Part10 Advanced Video Coding後，其許多新的特性更是一直為大家所討論的重點，其中多張參考畫面更是大大地增加位移估測演算法搜尋能力。雖然新的標準壓縮效能方面遠勝過其他先前所提出的標準，但是其編碼的計算高複雜度卻容易導致無法達到即時(real-time)的問題。對於目前H.264標準的參考軟體， JM10.1版本內所採用的快速移動估測方法為非對稱多解析度六角搜尋演算法(UMHexagonS)，在移動估測中，為了尋找到最佳的移動向量，UMHexagonS演算法的混合式移動搜尋策略方式明顯的優於其他演算法(FS, 3SS, 4SS, DS,…etc.)。但是，相較於其他演算法，UMHexagonS演算法的運算複雜度以及不易被實現的問題也隨之而產生。在本論文中，我們針對這個問題，提出一個單純並有效率的移動搜尋演算法，所提的演算法藉由更精確的預測初始搜尋中心能避免尋找到局部預測錯誤，並讓硬體實現問題能被有效解決。實驗結果顯示，本篇論文當中對此所提的新演算法可明顯的減少位移向量估測時間，並大幅度降低搜尋點數；並且客觀影像評估(Peak Signal to Noise Ratio)以及位元率(bit-rate)方面與H.264採用的UMHexagon演算法幾乎可與其比擬。另，除了針對H.264提出新的演算法之外；基於區塊式比對方法的特性，我們亦發展出了二種新型的動態影像移動估測演算法，稱之為混合型預測式六角暨三步搜尋法(HPHTS)與鑽石-弧形-六角混合式搜尋法(DAHS)。在這二個演算法中，對於小動作與大動作的預測，也皆能達到良好的動態影像預測效果與提昇搜尋速度。

In the past years, video coding experts from ITU-T H.264 and ISO/IEC MPEG-4 Advanced Video Coding (AVC) group formed the Joint Video Team (JVT) to develop the emerging standard. H.264/AVC has achieved significant rate-distortion efficiency by many useful video encoding and decoding tools. Compared with H.263, the new technique includes motion estimation (ME) with variable block sizes and multiple reference frames, intra prediction, 4×4 block based residue coding, adaptive block size transform, in-loop deblocking filter, …, etc. However, the motion estimation process concerns greatly on computational complexity. Hence, the algorithm on fast motion estimation becomes one of the most important issues in the development of H.264/AVC.
In the new version reference software JM 10.1 of H.264 standard, the UMHexagonS motion estimation algorithm is adopted to find the best motion vector for video coding. The hybrid search strategies have significantly outperformed other algorithms (FS, 3TT, 4TT, DS, …, etc.). However the highly computational complexity leads the codec to become too complex and hard to be implemented in real time applications. In this work, we propose an efficient algorithm by using the precision initial search and simple search strategies to finish the motion estimation. Experimental results indicate that the proposed method can obtain good performances. Through the proposed features, the coding performance can be improved significantly, and the computation complexity of the integer pixel motion estimation of H.264 is also decreased tremendously. In this thesis, a new fast motion estimation algorithm, Hierarchical Predictable Hexagon Search (HPHS), is proposed for H.264. 
   In addition to the proposed HPHS for H.264 video coding standard, we also developed two new algorithms for block-matching motion estimation, Hybrid Predictable Hexagon with Three-Step Search (HPHTS) and Diamond-Arc-Hexagon Search (DAHS). These two algorithms both achieve good performance in search speed and the prediction of the video quality.

第一章  緒論	1
1.1 H.264/MPEG-4 AVC動態影像編碼簡介	1
1.2 H.264/MPEG-4 AVC的畫格內預測模式	3
1.3 H.264/MPEG-4 AVC的畫格間預測模式	5
1.3.1 移動估測的可變區塊模式	5
1.3.2 部份像素的移動估測	6
1.3.3 區塊比對法的移動估測	8
1.4 快速移動估測演算法	10
第二章  H.264編碼之移動估測	12
2.1 初始搜尋中心預測	12
2.1.1 中間值預測	13
2.1.2  階層式預測	14
2.1.3  對應區塊預測	15
2.1.4  鄰近參考畫面預測	16
2.2 非對稱多解析度六角形搜尋演算法	17
2.3 使用於非對稱多解析六角形搜尋演算法的提前中斷	18
第三章  適用於H.264編碼之階層可預測式六角形移動估測演算法	20
3.1  引言	20
3.2  可預測式六角形搜尋演算法（PHS）	20
3.3  精確化的初始搜尋中心（Precision Initial Center）	22
3.4  階層式的處理程序	23
3.5  模擬環境設定與實驗結果分析	24
第四章  混合型預測式六角暨三步搜尋之區塊移動估測演算法	29
4.1  引言	29
4.2  三步搜尋法的探討	29
4.3  新可預測式六角形搜尋策略	32
4.4  混合型可預測式六角暨三步搜尋移動估測演算法	34
第五章  鑽石-弧形-六角搜尋之區塊移動估測演算法	36
5.1  引言	36
5.2  三步搜尋法於大動作向量估測的探討	36
5.3  鑽石-弧形的搜尋策略	37
5.4  鑽石-弧形-六角搜尋之區塊移動估測演算法	39
第六章  模擬結果與討論	44
6.1  模擬條件	44
6.2  評估方式與模擬結果	44
6.3  分析與討論	46
第七章  結論與未來展望	50
Reference  52
圖目
圖 1.1: H.264編碼器架構圖	2
圖 1.2: H.264解碼器架構圖	2
圖 1.3: 4×4的畫格內預測模式	4
圖 1.4: 16×16的畫格內預測模式與效果	4
圖 1.5: Macroblock的7種切割模式	5
圖 1.6: Half-pel sample的示意圖	6
圖 1.7: Quarter-pel sample的示意圖	7
圖 1.8: 區塊比對法示意圖	9
圖 1.9: 全域搜尋法範例	10
圖 2.1: 中間值預測示意圖	14
圖 2.2: 階層式預測的模式選擇	15
圖 2.3: 對應區塊預測	16
圖 2.4: 鄰近參考畫面示意圖	17
圖 2.5: 非對稱多解析度六角形搜尋演算法	18
圖 2.6: 非對稱多解析度六角形搜尋演算法與提前中斷策略	19
圖 3.1: PHS演算法	21
圖 3.2: 使用PHS演算法做為初始搜尋中心示意圖	22
圖 3.3: 使用小鑽石形態做為初始搜尋中心示意圖	23
圖 3.4: 階層式處理程序所形成的HPHS演算法	24
圖 3.5: 所有測試的動態影像樣本平均值比較	27
圖 3.6: “Coastguard”的失真比率曲線圖	28
圖 3.7: “Highway”的失真比率曲線圖	28
圖 4.1: 3SS的初始搜尋形態示意圖	30
圖 4.2: N3SS的初始搜尋形態示意圖	31
圖 4.3: E3SS的初始搜尋形態示意圖	31
圖 4.4: N3SS於中央搜尋地帶舉例示意圖	31
圖 4.5: E3SS的初始搜尋形態示意圖 32
圖 4.6: 新可預測式六角形搜尋策略搜尋形態 33
圖 4.7: 最佳向量於(4,2)的示意圖 33
圖 4.8: 新可預測式六角形搜尋策略流程圖 34
圖 4.9: 混合型可預測式六角暨三步移動估測演算法流程圖 35
圖 5.1: 使用效率式三步搜尋法於(5,-3)找到最佳向量  36
圖 5.2: 大鑽石搜尋形態(LDSP)示意圖  38
圖 5.3: 弧形搜尋形態示意圖  38
圖 5.4: 延展的弧形示意圖1  39
圖 5.5: 延展的弧形示意圖2  39
圖 5.6: 雙重鑽石形態(DDSP)示意圖  41
圖 5.7: DAHS演算法流程圖  41
圖 5.8: DAHS演算法於向量(4,0), 總共搜尋了18個點  42
圖 5.9: DAHS演算法於向量(5,-1), 總共搜尋了22個點  42
圖 5.10: DAHS演算法的弧形數學式推導示意圖  43
圖 6.1: 區塊演算法的初始搜尋形態  46
圖 6.2: DAHS找到最佳搜尋向量(5,-2)  47
圖 6.3: DAHS找到最佳搜尋向量(6,-1)  48
圖 6.4: DAHS找到最佳搜尋向量(7,-7)  48
表目
表 3.1: JM 10.1與模擬環境的詳細設定  25
表 3.2: 實驗結果數據比較表  26
表 3.3: 實驗結果數據比較表(轉換成百分比的差異做表示)  26
表 6.1: 均方誤差平均值(MSE)比較表  45
表 6.2: 每個區塊的平均搜尋點數比較表  45
表 6.3: DAHS演算法與E3SS、HEXBS轉換為百分比格式比較表  45
表 6.4: HPHTS演算法與E3SS、HEXBS轉換為百分比格式比較表  46
表 6.5: MSE轉換為PSNR值比較表  49
表 7.1: HPHS、HPHTS與DAHS演算法特性比較  51

[1]   J.   Mitchell,   W.   Pennebaker,   C.   Fogg   and  D.   LeGall,   "MPEG  VIDEO COMPRESSION STANDARD," pp. 94-98, CHAPMAN & HALL, 1997.
[2]   URL: http://www.vcodex.com , H.264/MPEG-4 Part 10 White Paper.
[3] "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, JVTG050, 2003.
[4] "Video Coding for Low Bit Rate Communication," ITU-T, ITU-T Recommendation H.263 version 1, 1995.
[5] Z. Chen, P. Zhou, and Y. He, "Fast Integer Pel and Fractional Pel Motion Estimation for JVT," JVT-F017r1.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 6th meeting, Awaji Island, 5-13 December, 2002.
[6]  Z. Chen, P. Zhou, and Y. He, "Fast Motion Estimation for JVT," JVT-G016.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 7th Meeting, Pattaya Thailand, 7-14 March, 2003.
[7] H.-Y. Cheong and A. Michael, "Fast Motion Estimation within the JVT codec," JVT-E023.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 5th Meeting, Geneva Switzerland, 09-17 October, 2002.
[8] Z. Chen and Y. He, "Fast Integer and Fractional Pel Motion Estimation," JVT-E045.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 5th Meeting, Geneva Switzerland, 09-17 October, 2002.
[9]  Z. Chen and Y. He, "Prediction based Directional Refinement (PDR) algorithm for Fractional Pixel Motion Search Strategy," JVT-D069.doc, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 4th Meeting, Klagenfurt, Austria, 22-26 July, 2002.
[10] JVT Reference Software old_jm Version 10.1,
http://iphome.hhi.de/suehring/tml/download/old jm/.
[11]  T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion-compensated interframe coding for video conferencing,” in Proc.NTC81, New Orleans, LA, Nov. 1981, pp. C9.6.1-9.6.5.
[12]  L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. Circuit Syst. Video Technol., vol. 6, pp. 313-317, Jun. 1996.
[13]  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-442, Aug. 1994.
[14]  X. Jing and L.-P. Chau, “An efficient three-step search algorithm for block motion estimation,” IEEE Trans. Multimedia, vol. 6, no. 3, June 2004.
[15]  S. Zhu and K.-K Ma, “A new diamond search algorithm for fast block-matching motion estimation, “ IEEE Trans. Image Processing, vol. 9, pp. 287-290, Feb. 2000.
[16]  J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim “A novel unrestricted center-based diamond search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 369-377, Aug. 1998.
[17]  C. Zhu, X. Lin, L. P. Chau, K. P. Lim, H. A. Ang, and C. Y. Ong, “A novel hexagon-based search algorithm for fast block motion estimation,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing, May 2001.
[18]  T.-H. Tsai and Y.-N. Pan, “A novel predict hexagon search algorithm for fast block motion estimation on H.264 video coding,” IEEE Asia-Pacific Conference on Circuits and Systems, pp. 609-612, Dec 2004.
[19]  P. Yang, Y.-W. He, and S.-Q. Yang, "An Unsymmetrical-Cross Multi-Resolution Motion Search Algorithm for MPEG-4/AVC/H.264 Coding," International Conference on Multimedia and Expo, vol. 1, 27-30, pp. 531-534, June 2004.
[20]	 Jianfeng Xu, Zhibo Chen, and Yun He “Efficient fast ME predictions and early-termination strategy based on H.264 statistical characters,” International Information, Communications and Signal Processing and the Fourth Pacific Rim Conference on Multimedia, vol.1, pp. 218-222, Dec. 2003.
[21]	 Jen-Shiun Chiang, Hsin-Guo Chou, and Je-Yu Tzou “An efficient and regular motion estimation algorithm for MPEG4-AVC/H.264 coding,” Cellular Neural Networks and Their Applications, pp. 253-256, May. 2005.