自從2001年Joint Video Term的MPEG群組以及VCEG群組共同開發H.264/MPEG-4 Part10 Advanced Video Coding之後，許多新的特性便一直是大家討論的重點，其中多張參考畫面更是大大的增加位移估測演算法搜尋能力。雖然新的標準壓縮效能方面遠遠勝過其他先前所提出的標準，但是編碼的計算複雜卻無法達到即時(real-time)，對於目前H.264標準的參考軟體， JM9.2版本所採用的快速移動估測方法為非對稱多解析度六角搜尋演算法(UMHexagonS)，在移動估測中，為了尋找最佳的移動向量，UMHexagonS演算法的混合式移動搜尋策略方式明顯的優於其他演算法(FS, 3TT, 4TT, DS,…etc.)。但是，相較於其他演算法，UMHexagonS演算法的計算複雜度以及不容易被實現的問題也隨之而產生。在本論文中，我們針對這個問題，提出一個單純並有效率的移動搜尋演算法，所提的演算法藉由更精確的預測初始搜尋中心能避免尋找到區域最佳解，另外，我們提出單一搜尋策略讓硬體實現問題能被有效解決。實驗結果顯示，本篇論文當中所提的演算法明顯的加速位移向量估測時間，大幅度的降低搜尋點數，並且客觀影像評估(Peak Signal to Noise Ratio)以及位元率(Bitrate)方面與H.264採用的UMHexagon演算法幾乎無差異。

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 Term (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 JM9.2 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 Single Cross Search (HSCS), is proposed for H.264.

Contents
CHAPTER 1 Introduction	1
1.1 Overview of H.264/MPEG-4 AVC Video Coding	1
1.2 H.264/MPEG-4 AVC Intra Prediction Mode	3
1.3 H.264/MPEG-4 AVC Inter Prediction Mode	6
1.3.1 Variable Block Size for Motion Estimation	6
1.3.2 Fractional-pixel Motion Estimation	6
1.3.3 Block-based Motion Estimation	7
1.4 In-Loop Deblocking filter	8
CHAPTER 2 Motion Estimation in H.264/AVC Coding.....	10
2.1 Initial Search Center Prediction	11
2.1.1 Median Predictor	11
2.1.2 Up Layer Predictor	12
2.1.3 Corresponding-block Prediction	13
2.1.4 Neighboring Ref-Frame Prediction	14
2.2 Unsymmetrical Multi-resolution Hexagon Search Algorithm........	15
2.3 Early Termination with UMHexagonS Algorithm	16
2.3.1 Sum of Absolute Difference for Early Termination	17
2.3.2 Introduction of Modulated Factor and Parameter	18
2.4 Bit-Allocation Problem for Motion Estimation	21
CHAPTER 3 Proposed Algorithm for H.264/AVC Motion Estimation 	23
3.1 Previous Remark	23
3.2 Precision Initial Search Center	24
3.3 Refining Motion Vector by Single Search Strategy	27
3.4 Different Search Pattern for Single Search Strategy	29
3.5 Classification and Comparison for different Search Strategy	30
CHAPTER 4 Analysis and Judgment of Experimantal Results	32
4.1 Parameter setting of simulation platform	32
4.2 All kind of Sequences in the Experiment	33
4.3 Objective Video Quality Evaluation	34
4.4 Experiment Results of Coding Bit-Rate	36
4.5 Experiment Results of Motion Estimation Time	37
4.6 Rate Distortion Curve	39
4.7 Subjective Video Quality Evaluation	56
CHAPTER 5 Conclusion and Future Work	61
5.1 Conclusion	61
5.2 Future Work	61
REFERENCE.............62

LIST OF FIGURES
Figure 1.1: Block diagram of H.264 encoder ........................................................................ 2
Figure 1.2: Block diagram of H.264 decoder ........................................................................ 2
Figure 1.3: Intra_4x4 prediction modes ................................................................................ 4
Figure 1.4: Intra_16x16 prediction modes ............................................................................ 5
Figure 1.5: Seven modes of macroblock partition................................................................. 6
Figure 1.6: Fractional-pixel interpolation for quarter-samples a-q and half-samples aa-hh . 7
Figure 1.7: Block matching algorithm................................................................................... 8
Figure 2.1: Spatial block location for the current frame...................................................... 12
Figure 2.2: Hierarchical search order for the decision block mode..................................... 13
Figure 2.3: Temporal prediction of the last frames of the motion vector ............................ 14
Figure 2.4: Temporal scaling prediction of the motion vector ............................................ 15
Figure 2.5: Prediction flow in the UMHexagonS algorithm ............................................... 16
Figure 2.6: Flow chart of UMHexagonS algorithm and early termination ......................... 20
Figure 3.1: Four types of prediction means of the refinement ............................................ 25
Figure 3.2: Flowchart of precision initial search center ...................................................... 26
Figure 3.3: Small-cross search pattern ................................................................................ 28
Figure 3.4: Single-cross search flow ................................................................................... 28
Figure 3.5: Diamond search pattern Figure 3.6: Rectangular search
pattern............................................................................ ...................................................... 29
Figure 3.7: Procedure for proposed algorithm .................................................................... 30
Figure 4.1: Picture of the motion for various sequences. .................................................... 33
Figure 4.2: Rate distortion curve of Akiyo with 5 reference frames. .................................. 40
Figure 4.3: Rate distortion curve of Akiyo with 1 reference frame..................................... 40
Figure 4.4: Rate distortion curve of Carphone with 5 reference frames. ............................ 41
Figure 4.5: Rate distortion curve of Carphone with 1 reference frame............................... 41
Figure 4.6: Rate distortion curve of Claire with 5 reference frames. .................................. 42
Figure 4.7: Rate distortion curve of Claire with 1 reference frame..................................... 42
Figure 4.8: Rate distortion curve of Coastguard with 5 reference frames........................... 43
Figure 4.9: Rate distortion curve of Coastguard with 1 reference frame. ........................... 43
Figure 4.10: Rate distortion curve of Container with 5 reference frames. .......................... 44
Figure 4.11: Rate distortion curve of Container with 1 reference frame............................. 44
Figure 4.12: Rate distortion curve of Foreman with 5 reference frames............................. 45
Figure 4.13: Rate distortion curve of Foreman with 1 reference frame. ............................. 45
Figure 4.14: Rate distortion curve of Grandma with 5 reference frames. ........................... 46
Figure 4.15: Rate distortion curve of Grandma with 1 reference frame.............................. 46
Figure 4.16: Rate distortion curve of Highway with 5 reference frames. ........................... 47
Figure 4.17: Rate distortion curve of Highway with 1 reference frame.............................. 47
Figure 4.18: Rate distortion curve of Miss_am with 5 reference frames. ........................... 48
Figure 4.19: Rate distortion curve of Miss_am with 1 reference frame.............................. 48
Figure 4.20: Rate distortion curve of Mobile with 5 reference frames. .............................. 49
Figure 4.21: Rate distortion curve of Mobile with 1 reference frame................................. 49
Figure 4.22: Rate distortion curve of mthr_dotr with 5 reference frames........................... 50
Figure 4.23: Rate distortion curve of mthr_dotr with 1 reference frame. ........................... 50
Figure 4.24: Rate distortion curve of News with 5 reference frames.................................. 51
Figure 4.25: Rate distortion curve of News with 1 reference frame. .................................. 51
Figure 4.26: Rate distortion curve of Salesman with 5 reference frames............................ 52
Figure 4.27: Rate distortion curve of Salesman with 1 reference frame. ............................ 52
Figure 4.28: Rate distortion curve of Silent with 5 reference frames.................................. 53
Figure 4.29: Rate distortion curve of Silent with 1 reference frame. .................................. 53
Figure 4.30: Rate distortion curve of Suzie with 5 reference frames. ................................. 54
Figure 4.31: Rate distortion curve of Suzie with 1 reference frame.................................... 54
Figure 4.32: Rate distortion curve of Trevor with 5 reference frames. ............................... 55
Figure 4.33: Rate distortion curve of Trevor with 1 reference frame.................................. 55
Figure 4.34: Subjective quality evaluation of coastguard, mobile and highway for three
different algorithms. ............................................................................................................ 58
Figure 4.35: Subjective quality evaluation of foreman (CIF) for three different algorithms.
............................................................................................................................................ 60
LIST OF TABLES
Table 3.1: Comparision of hybrid search and single search pattern.................................... 31
Table 4.1: Simulation environment of JM9.2 reference software ....................................... 32
Table 4.2: Average PSNR results obtained by different algorithms .................................... 35
Table 4.3: Average PSNR difference from the full search algorithm .................................. 35
Table 4.4: Coding Bit-rate results obtained by different algorithms ................................... 36
Table 4.5: Coding Bit-rate difference from the full search algorithm ................................. 37
Table 4.6: Coding ME Time results obtained by different algorithms ................................ 38
Table 4.7: Coding ME time variation from the full search algorithm ................................. 38

Reference
[1] URL: http://iphome.hhi.de/suehring/tml/.
[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]	Zhibo Chen, Peng Zhou and Yun 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]	Zhibo Chen, Peng Zhou and Yun 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]	Hye-Yeon Cheong and Alexis 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] 	Zhibo Chen and Yun 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] 	Zhibo Chen and Yun 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 9.2,
http://iphome.hhi.de/suehring/tml/download/old_jm/.
[11] Joan L. Mitchell, William B. Pennebaker, Chad E. Fogg and Didier J. LeGall, “MPEG VIDEO COMPRESSION STANDARD”, pp. 94-98, CHAPMAN & HALL, 1997.
[12]	Iain E.G. Richardson, “H.264 and MPEG-4 Video Compression”, John Wiley & Sons Ltd, 2003.
[13]	T. Wiegand and G. J. Sullivan, G. Bjontegaard and A. Luthra, “Overview of the H.264/AVC Video Coding Standard” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, pp.560-576, July. 2003.
[14]	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.
[15] L. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 4, pp. 419-422, June 1996.
[16] L. Po and W. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313-317, June 1996.
[17]	Ce Zhu, Xiao Lin, and Lap-Pui Chau, “Hexagon-Based Search Patten for Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, pp. 349-355, Vol. 12, no. 5, May, 2002.
[18] Sheng-Jia Li, “Speed-Up of the Selections of Motion-Estimation Modes in H.264,” Master Thesis, Dept. Elect. Eng, NCKU, Taiwan, July 2004.
[19] Shiang-Yang Wang, “VLSI Architectures for Full-Search Variable-Size Block Matching in H.264/AVC,” Master Thesis, Dept. Elect. Eng, NTHU, Taiwan, July 2003.
[20] Yi-Yen Chiang, “Fast Motion Estimation Algorithms for H.264 Standard,” Master Thesis, Dept. Elect. Eng, NDHU, Taiwan, July 2003.
[21] Cheng-Yi Chen, “An Efficient and Effective Deblocking Algorithm for Video Signals,” Master Thesis, Dept. Elect. Eng, NCKU, Taiwan, July 2003.
[22] Xuan-Quang Banh and Yap-Peng Tan, “Adaptive Dual-Cross Search Algorithm for Block –Matching Motion Estimation,” IEEE Transactions on Consumer Electronics, vol. 50, no. 2, pp. 766-775, MAY 2004.
[23] Viet L. Do and Kenneth Y. Yun, “A Low-Power VLSI Architecture for Full-Search Block-Matching Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 4, pp. 393-398, August 1998.
[24] Pei-Yin Chen and Jer Min Jou, “An Efficient Blocking-Matching Algorithm Based on Fuzzy Reasoning,” IEEE Transactions on Systems, Man and Cybernetics-part B: Cybernetics, vol. 31, no. 2, pp. 253-259, April 2001.
[25] Peter List, Anthony Joch, Jani Lainema, Gisle Bjontegaard, and Marta Karczewicz, “Adaptive Deblocking Filter,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp. 614-619, July 2003.
[26] Swee Yeow Yap and John V. McCanny, “A VLSI Architecture for Variable Block Size Video Motion Estimation,” IEEE Transactions on Circuits and Systems -II: Express Briefs, vol. 51, no. 7, pp. 384-389, July 2004.
[27] Yap-Peng Tan and Haiwei Sun, “Fast Motion Re-Estimation for Arbitrary Downsizing Video Transcoding using H.264/AVC Standard,” IEEE Transactions on Consumer Electronics, vol. 50, issue: 3, pp. 887-894, August 2004.
[28] Antonio Chimienti, Claudia Ferraris and Danilo Pau, “A Complexity Bounded Motion Estimation Algorithm,” IEEE Transactions on Image Processing, vol. 11, no. 4, pp. 387-392, April 2002.
[29] Peng Yang, Yu-Wen He and Shi Qiang 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.