在本研究中，我們提出一個應用於H.264視訊編碼之可調適快速全域搜尋運動估測方法，其目的是加快H.264編碼端壓縮程序的速度，但不會影響到編碼的結果。
為了降低全域搜尋運動估測方法的計算複雜度，在本研究中提出了兩個主要的技術。第一個技術叫修改式資料再利用(MDR)，此方法以減少SAD計算量來減少運動估測所需的處理時間，其中不必要及重複的運動估測計算量將大量減少。在所提的十字搜尋順序，其搜尋順序將使MV_COST值的分佈與搜尋順序呈線性關係，MV_COST計算量將大量地減少。第二個技術叫可調適的搜尋順序(ASO)，此方法以減少MV_COST計算量及在螺旋搜尋順序及十字搜尋順序之間調適性地切換運動估測順序來減少運動估測所需的處理時間。
本研究中的實驗結果顯示，我們所提出的MDR加上ASO快速全域搜尋運動估測方法之性能優於四種現有的快速全域搜尋運動估測方法，這顯示出所提方法的可行性。

In this study, an adaptive fast full search motion estimation (ME) algorithm for H.264 is proposed. The objective of the proposed algorithm is to speed up the H.264 video coding procedure performed at the encoder, without influencing the coding results.
To reduce the computational complexity of the full search motion estimation algorithm, two main techniques are proposed in this study. First, the proposed modified data reusing (MDR) technique is used to speed up the ME processing time by reducing the SAD computations. In the proposed MDR technique, both the unnecessary and repeated SAD computations will be avoided or reduced. In the proposed rood search order (RSO), the search order can be determined in such a way that the distribution of the MV_COST values is “linearly-related” with the search order, i.e., the MV_COST value is a monotonically non-decreasing function of the search order so that the number of MV_COST computations will be greatly reduced. Second, the proposed adaptive search order (ASO) technique is used to speed up the ME processing time by reducing the MV_COST computations and adaptively switching the ME search order between the spiral search order and the proposed rood search order (RSO).
Based on the simulation results obtained in this study, the performance (the average processing time) of the proposed algorithm (MDR+ASO) is better than that of four comparison fast full search algorithms. This shows the feasibility of the proposed approach.

摘 要 i
ABSTRACT ii
ACKNOWLEDGMENTS iv
TABLE OF CONTENTS v
LIST OF FIGURES vii
LIST OF TABLES viii
CHAPTER 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Survey of Related Researches 4
1.2.1 Fast lossy search ME algorithms 4
1.2.2 Fast full search ME algorithms (FFS) 6
1.3 Overview of Proposed Approach 9
1.4 Thesis Organization 10
CHAPTER 2 THE H.264 VIDEO COMPRESSION STANDARD AND BLOCK MOTION ESTIMATION SCHEMES IN H.264 11
2.1 The H.264 Video Compression Standard 11
2.1.1 Overview of H.264 video 11
2.1.2 H.264 video compression techniques 11
2.1.3 Syntax and data organization of H.264 video 15
2.2 Block Motion Estimation Schemes in H.264 23
2.2.1 Motion estimation and mode decision 23
2.2.2 Full integer pixel block motion search 25
CHAPTER 3 PROPOSED FAST FULL SEARCH MOTION ESTIMATION ALGORITHM FOR H.264 31
3.1 Proposed Modified Data Reusing (MDR) Technique for Reducing SAD Computations 31
3.2 Proposed Adaptive Search Order (ASO) 37
3.2.1 Rood search order (RSO) and distribution of MVs 37
3.2.2 Adaptive search order (ASO) and modified MB self-
prediction 43
CHAPTER 4 SIMULATION RESULTS 47
CHAPTER 5 DISCUSSIONS AND CONCLUSIONS 65
5.1 Discussions 65
5.2 Conclusions 69
REFERENCES 71

[1] K. N. Ngan, C. W. Yap, and K. T. Tan, Video Coding for Wireless Communications. New Jersey: Prentice Hall, 2002.
[2] Y. Wang, J. Ostermann, and Y. Q. Zhang, Video Processing and Communications. New Jersey: Prentice Hall, 2002.
[3] A. M. Tekalp, Digital Video Processing. New Jersey: Prentice Hall PTR, 1995.
[4] M. T. Sun and A. R. Reibman, Compressed Video over Networks. New York: Marcel Dekker, 2001.
[5] J. L. Mitchell, W. B. Pennebaker, C. E. Fogg, and D. J. LeGall, MPEG Video Compression Standard. New York: Chapman & Hall, 1997.
[6] B. G. Haskell, A. Puri, and A. N. Netravali, Digital Video: An Introduction to MPEG-2. New York: Chapman & Hall, 1997.
[7] ISO/IEC JTC1/SC29/WG11/602, “Coding of moving pictures and associated audio,” Recommendation H.262, 1993.
[8] ISO/IEC JTC1/SC29/WG11 N3515, “MPEG-4 video verification model version 17.0,” Beijing, July 2000.
[9] Video codec for audiovisual services at p64 kbit/s, CCITT Recommendation H.261, 1990.
[10] Video coding for low bit rate communication, ITU-T Recommendation H.263, May 1998.
[11] ITU-T Q.6/SG16, “H.26L Test Model Long Term Number 9 (TML-9) draft0,” Dec. 2001.
[12] V. Lappalainen, A. Hallapuro, and T. D. Hamadinen, “Optimization of emerging H.26L video encoder,” in Proc. of IEEE Workshop on Signal Processing, Sept. 2001, pp. 406-415.
[13] A. Hallapuro, V. Lappalainen, and T. D. Hamadinen, “Performance analysis of low bit rate H.26L video encoder,” in Proc. of IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, May 2001, vol. 2, pp. 1129-1132.
[14] H.264, Draft ITU-T Recommendation and Final Draft International Standard, Pattaya, Thailand, 2003.
[15] A. N. Netravali and J. D. Robbins, “Motion compensated television coding: Part I,” Bell System Technical J., vol. 58, pp. 631-670, Mar. 1979.
[16] A. Murat Tekalp, Digital Video Processing. Englewood Cliffs, NJ: Prentice-Hall, 1995.
[17] C. Cafforio and F. Rocca, “Methods for measuring small displacement of television images,” IEEE Trans. on Information Theory, vol. IT-22, no. 5, pp. 573-579, Sept. 1976.
[18] J. R. Jain and A. K. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Trans. on Communications, vol. 29, pp. 1799-1808, Dec. 1991.
[19] F. Dufaus and F. Moscheni, “Motion estimation techniques for digital TV: a review and a new contribution,” Proceedings of the IEEE, vol. 83, no. 6, pp. 858-876, June 1995.
[20] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conference,” in Proc. National Telecommun. Conf., New Orleans, LA, Nov. 29-Dec. 3, 1981, pp. G5.3.1-G5.3.5.
[21] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 6, no. 3, pp. 313-317, June 1996.
[22] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 4, no. 4, pp. 438-442, Aug. 1994.
[23] J. N. Kim and T. S. Choi, “A fast three-step search algorithm with minimum checking points using unimodal error surface assumption,” IEEE Trans. on Consumer Electronics, vol. 44, no. 3, pp. 638-648, Aug. 1998.
[24] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Trans. on Image Processing, vol. 9, no. 2, pp. 287-290, Feb. 2000.
[25] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 12, no. 5, pp. 349-355, May 2002.
[26] K. K. Ma and G. Qiu, “Unequal-arm adaptive rood pattern search for fast block-matching motion estimation in the JVT/H.26L,” in Proc. of IEEE Int. Conf. on Image Processing, Sept. 2003, vol. 1, pp. 901-904.
[27] Z. Zhou, M. T. Sun, and Y. F. Hsu, “Fast variable block-size motion estimation algorithms based on merge and split procedures for H.264/MPEG-4 AVC,” in Proc. of IEEE Int. Sym. on Circuits and Systems, May 2004, pp. 725-728.
[28] Y. K. Chen and T. C. Chen, “A fast and effective method for motion estimation,” in Proc. of IEEE Int. Conf. on Multimedia and Expo, June 2004.
[29] C. W. Lam, L. M. Po, and C. H. Cheung, “A novel kite-cross-diamond search algorithm for fast block matching motion estimation,” in Proc. of IEEE Int. Sym. on Circuits and Systems, May 2004, pp. 729-732.
[30] Y. Liu and S. Oraintara, “A novel adaptive multi-mode search algorithm for fast block-matching motion estimation,” in Proc. of IEEE Int. Sym. on Circuits and Systems, May 2004, pp. 977-980.
[31] Y. Liu and S. Oraintara, “Complexity comparison of fast block-matching motion estimation algorithms,” in Proc. of IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, May 2004, pp. 341-344.
[32] H. Jia and L. Zhang, “A new cross diamond search algorithm for block motion estimation,” in Proc. of IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, May 2004, pp. 357-360.
[33] M. Bierling, “Displacement estimation by hierarchical block matching,” in Proc. of SPIE, 1988, vol. 1001, pp. 942-951.
[34] Y. Q. Shi and X. Xia, “A thresholding multiresolution block matching algorithm,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, no. 2, pp. 437-440, Feb. 1997.
[35] J. Chalidabhongse and C. C. J. Kuo, “Fast motion vector estimation using multiresolution-spatio-temporal correlations,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, no. 3, pp. 477-488, June 1997.
[36] Y. Q. Zhang and S. Zafar, “Motion-compensated wavelet transform coding for color video compression,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 2, no. 3, pp. 285-296, Sept. 1992.
[37] B. Liu and A. Zaccarin, “New fast algorithms for the estimation of block motion vectors,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 3, no. 2, pp. 148-157, April 1993.
[38] C. K. Cheung and L. M. Po, “Normalized partial distortion search algorithm for block motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 10, no. 3, pp. 417-422, April 2000.
[39] C. H. Cheung and L. M. Po, “Adjustable partial distortion search algorithm for fast block motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, no. 1, pp. 100-110, Jan. 2003.
[40] L. J. Luo, C. Zou, and X. Q. Gao, “A new prediction search algorithm for block motion estimation in video coding,” IEEE Trans. on Consumer Electronics, vol. 43, no. 1, pp. 56-61, Feb. 1997.
[41] J. B. Xu, L. M. Po, and C. K. Cheng, “Adaptive motion tracking block matching algorithms for video coding,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 97, no. 7, pp. 1025-1029, Oct. 1999.
[42] A. Chang, P. H. W. Wong, Y. M. Yeung, and O. C. Au, “Fast integer motion estimation for H.264 video coding standard,” in Proc. of IEEE Int. Conf. on Multimedia and Expo, June 2004.
[43] C. H. Hsieh, P. C. Lu, J. S. Shyn, and E. H. Lu, “Motion estimation algorithm using interblock correlation,” Electronics Letters, vol. 26, no. 5, pp. 276-277, Mar. 1990.
[44] J. Chana and P. Agathoklis, “Adaptive motion estimating for efficient video compression,” in Proc. of 29th Asilomar Conf. on Signals, Systems, and Computers, 1996, vol. 1, pp. 690-693.
[45] J. C. Tsai, C. H. Hsieh, S. K. Weng, and M. F. Lai, “Block-matching motion estimating using correlation search algorithm,” Signal Processing: Image Communication, vol. 13, no. 2, pp. 119-133, 1998.
[46] D. W. Kim, J. S. Choi, and J. T. Kim, “Adaptive motion estimation based on spatio—temporal correlation,” Signal Processing: Image Communication, vol. 13, no. 2, pp. 161-170, 1998.
[47] W. Li and E. Salari, “Successive elimination algorithm for motion estimation,” IEEE Trans. on Image Processing, vol. 4, no. 1, pp. 105-107, Jan. 1995.
[48] C. H. Lee and L. H. Chen, “A fast motion estimation algorithm based on the block sum pyramid,” IEEE Trans. on Image Processing, vol. 6, no. 11, pp. 1587-1591, Nov. 1997.
[49] T. M. Oh, Y. R. Kim, W. G. Hong, and S. J. Ko, “A fast full search motion estimation algorithm using the sum of partial norms,” in Proc. of IEEE Int. Conf. on Consumer Electronics, June 2000, pp. 236-237.
[50] X. Q. Gao, C. J. Duanmu, and C. R. Zou, “A multilevel successive elimination algorithm for block matching motion estimation,” IEEE Trans. on Image Processing, vol. 9, no. 3, pp. 501-504, Mar. 2000.
[51] W. G. Hong, T. M. Oh, and S. J. Ko, “Fast motion-estimation algorithm based on progressive partial norm matching,” Electronics Letters, vol. 37, no. 14, pp. 890-892, July 2001.
[52] 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, no. 1, pp. 43-46, Mar. 2002.
[53] C. Zhu, W. S. Qi, and W. Ser, “A new successive elimination algorithm for fast block matching in motion estimation,” in Proc. of IEEE Int. Sym. on Circuits and Systems, May 2004, pp. 733-736.
[54] A. Gersho, and R. M. Gray, Vector Quantization and Signal Compression. Boston MA: Kluwer, 1991.
[55] S. Eckart and C. Fogg, “ISO/IEC MPEG-2 software video codec,” Proc. SPIE, 1995, vol. 2419, pp. 100-118.
[56] “ITU-T recommendation H.263 software implementation,” Digital Video Coding Group, Telenor R&D, 1995.
[57] J. N. Kim and T. S. Choi, “Adaptive matching scan algorithm based on gradient magnitude for fast full search in motion estimation,” IEEE Trans. on Consumer Electronics, vol. 45, no. 3, pp. 762-772, Aug. 1999.
[58] J. N. Kim, and T. S. Choi, “A fast full-search motion-estimation algorithm using representative pixels and adaptive matching scan,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 10, no. 7, pp. 1040-1048, Oct. 2000.
[59] J. N. Kim, S. C. Byun, and B. H. Ahn, “Fast full search motion estimation algorithm using various matching scans in video coding,” IEEE Trans. on Systems, Man, and Cybernetics-Part C: Applications and Reviews, vol. 31, no. 4, pp. 540-548, Nov. 2001.
[60] J. N. Kim, S. C. Byun, Y. H. Kim, and B. H. Ahn, “Fast full search motion estimation algorithm using early detection of impossible candidate vectors,” IEEE Trans. on Signal Processing, vol. 50, no. 9, pp. 2355-2365, Sept. 2002.
[61] M. Brnig, and W. Niehsen, “Fast full-search block matching,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 11, no. 2, pp. 241-247, Feb. 2001.
[62] Y. S. Chen, Y. P. Hung, and C. S. Fuh, “Fast block matching algorithm based on the winner-update strategy,” IEEE Trans. on Image Processing, vol. 10, no. 8, pp. 1212-1222, Aug. 2001.