臺灣博碩士論文加值系統

傳統快速運動估測方法通常注重在減少計算量上，例如，減少每一個區塊的搜尋點數或減少每一個搜尋點的計算複雜度來加速運動估測步驟。然而，假如原本可用的計算量就不足以完成整個完整搜尋或快速搜尋的運動估測程序，這些傳統運動估測方法將會被強迫中途停止。在本研究中，我們提出一種應用於 H.264 之視訊運動估測之計算調節方法，內容是適當地調配有限的運動估測計算量。其目的是當可用計算量不足以完成整個運動估測程序時，適當分配可用計算量給 H.264 視訊編碼端，得到最小的視訊品質下降量以及視訊編碼率增加量。
在視訊編碼的運動估測程序中，運動向量的預測技術可以有效的預測出一個區塊的運動，因此在本研究中，我們用時域運動向量預測法來預測出一張視訊影像中所有區塊的運動向量並以向量二個分量的長度和來代表此向量的強度，以這些向量強度來做為計算量調配的標準。本研究中，可用計算量的調配被分成四個階段，首先決定目前這張視訊影像的可用計算量；然後將目前視訊影像的可用計算量分配至每個區塊可用的計算量；接著，依各個區塊所分配到的計算量分類，將區塊可用的計算量分配到各種區塊大小的搜尋種類的可用計算量；最後，再對整數像素及分數像素的計算量做適當的調配。實驗結果顯示，與現有的計算調節方法做比較，我們所提出的方法在大部分情況下有較好的效能，這顯示我們所提方法之可適性。

The conventional fast ME algorithms always focus on reducing computation consumption, i.e., reducing the number of checking points required for every block or reducing the computation complexity of a checking point to speed up the ME procedure. However, if the total ME computation power is not sufficient to finish the whole motion estimation process essentially using either the FS or fast search algorithms, these conventional motion search algorithms may force the encoding process to terminate suddenly. In this study, a computation-aware scheme for motion estimation in H.264 video is proposed, in which an ME computation power distribution and allocation (arrange appropriately) technique proposed. The objective of the proposed algorithm is to distribute the available ME computation power of the H.264 video coding procedure performed at the encoder with slight average PSNR degradation and slight average bit rate increment while the available ME computation power is not sufficient to finish the whole motion estimation process.
For the motion estimation process in video encoding, motion vector prediction technique is useful for predicting the motion of an macroblock (MB), thus the temporal motion vector prediction method is used to get the predicted motion vectors (PMVs). The sum of absolute components of the PMVs (PSACs) of all the MBs of a video frame to help to allocate the available computation power to the frame (Avalb_CP_FM) and then distribute Avalb_CP_FM to all the MBs of the frame in the proposed computation-aware scheme. In this study, the proposed scheme contains four phases: 1) the frame level computation distribution to determine the available computation (checking point) for current frame, Avalb_CP_FMt, 2) the MB level computation allocation to allocate the computation, Avalb_CP_FMt, into every MBi’s available computation (checking point), Avalb_CP_MBi, 3) the mode level computation allocation to allocate each INTER-mode computation by the classification of the MBi’s available computation (checking point), and 4) the pixel level computation allocation to allocate integer-pixel and sub-pixel computations for integer-pixel and sub-pixel search. The proposed computation-aware scheme for motion estimation in H.264 video usually has the better performance (the average PSNR and the average bit rate) in most simulation cases. This shows the feasibility of the proposed algorithm.

摘 要 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 6
1.2.1 Fast ME algorithms for reducing the number of checking points 6
1.2.2 Fast ME algorithms reducing computational complexity at each checking points 7
1.2.3 Fast ME algorithms arranging restricted computational power appropriately 8
1.3 Overview of Proposed Approach 10
1.4 Thesis Organization 10

CHAPTER 2 H.264 VIDEO COMPRESSION STANDARD AND H.264 MOTION ESTIMATION SCHEMES 12
2.1 H.264 Video Compression Standard 12
2.1.1 Overview of H.264 video 12
2.1.2 H.264 video compression techniques 12
2.1.3 Syntax and data organization of H.264 video 16
2.2 H.264 ME Schemes 24
2.2.1 ME and mode decision 24
2.2.2 Full integer pixel block motion search 27
2.2.3 Adaptive dual-cross search 34

CHAPTER 3 PROPOSED COMPUTATION-AWARE SCHEME FOR MOTION ESTIMATION IN H.264 VIDEO 38
3.1 An Existing Computation-Aware Scheme 38
3.2 Proposed Computation-Aware Scheme for ME in H.264 video 42
3.2.1 Overview 42
3.2.2 Temporal Motion Vector Prediction 43
3.2.3 Frame Level Computation Distribution 45
3.2.4 MB Level Computation Allocation 46
3.2.5 Mode Level Computation Allocation 46
3.2.6 Pixel Level Computation Allocation 51

CHAPTER 4 SIMULATION RESULTS 53

CHAPTER 5 DISCUSSIONS AND CONCLUSIONS 61
5.1 Discussions 61
5.2 Conclusions 61

REFERENCES 64

REFERENCES

[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 p64 kbit/s, CCITT Recommendation H.261, 1990.
[10]Video coding for low bitrate 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]ITU-T Recommendation H.264/ISO/IEC 11496-10, “Advance Video Coding,” Final Committee Draft, Document JVT-F100, Dec. 2002.
[13]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.
[14]J. R. Jain and A. K. Jain, “Displacement measurement and its application in interframe image coding,” IEEE Trans. on Communications, vol. COMM-29, no. 12, pp. 1799-1808, Dec. 1981.
[15]A. N. Netravali and J. D. Robbins, “Motion compensated television coding: Part I,” Bell Syst. Tech. J., vol. 58, pp. 631–670, March 1979.
[16]A. Murat Tekalp, Digital Video Processing. Englewood Cliffs, NJ: Prentice-Hall, 1995, pp. 72–129.
[17]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.
[18]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, 1981, pp. C9.6.1-C9.6.5.
[19]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.
[20]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.
[21]L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 6, no. 4, pp. 419-423, Aug. 1996.
[22]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.
[23]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.
[24]C. Zhu, X. Lin, and L. P. Chau, “An enhanced hexagonal search algorithm for block motion estimation,” in Proc. of IEEE Int. Symposium on Circuits and Systems, 2003, pp. 392-395.
[25]Y. Nie and K. K. Ma, “Adaptive rood pattern search for fast block-matching motion estimation,” IEEE Trans. on Image Processing, vol. 11, no. 12, pp. 1442–1449, Dec. 2002.
[26]K. K. Ma and G. Qiu, “An improved adaptive rood pattern search for fast block-matching motion estimation in JVT/H.26L,” in Proc. of IEEE Int. Symposium on Circuits and Systems, May 2003, pp. 708-711.
[27]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, pp. 901-904.
[28]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.
[29]Y. L. Chan and W. C. Siu, “New adaptive pixel decimation for block motion vector estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 6, no. 1, pp. 113-118, Feb. 1996.
[30]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.
[31]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, March 2000.
[32]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.
[33]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.
[34]P. L. Tai, S. Y. Huang, C. T. Liu, and J. S. Wang “Computation-aware scheme for software-based block motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 13, no. 9, pp. 901-913, Sept. 2003.
[35]Z. Chen, P. Zhou, and Y. He, “Fast integer pel and fractional pel motion estimation for JVT,” Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG Document JVT-F017, the 6th meeting, Awaji Island, Japan, Dec. 2002.
[36]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.
[37]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.
[38]X. Q. Banh and Y. P. Tan, “Adaptive dual-cross search algorithm for block-matching motion estimation,” IEEE Trans. on Consumer Electronics, vol. 50, no. 2, pp. 766–775, May 2004.
[39]I. Ismaeil, A. Docef, F. Kossentini, and R.Ward, “Efficient motion estimation using spatial and temporal motion vector prediction,” in Proc. of IEEE Int. Conf. on Image Processing, Kobe, Oct. 1999, vol. 1, pp. 70–74.
[40]J. Luo, I. Ahmad, Y. Sun, and Y. Liang, “A multistage fast motion estimation scheme for video compression,” in Proc. of IEEE Int. Conf. on Image Processing, vol. 3, pp. 1441-1444, Oct. 2004.