臺灣博碩士論文加值系統

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

　　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 MPEG-4 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 MPEG-4 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) in this study. The sum of absolute components of the PMVs (PSACs) of all the MBs of a video frame are used to help to allocate the target computation power to the frame (CF) and then distribute CF to all the MBs of the frame in the proposed computation-aware scheme which contain three phases: 1) the frame level computation allocation, 2) the MB level computation distribution, and 3) the mode level computation allocation. In the frame level, CF is allocated by two parameters, namely, the information of the previously encoded frames and the average MV computation of the following unencoded frames. In the MB level, the CF of the current frame is distributed to each MBs in the frame according to the taken proportion by the PSAC of this MB to decide the target computation power to it (CMB). In the mode level, the range of initial SAD value (at mv(0, 0)), SADinit, of an MB is divided into four intervals. Based on the different characteristics of the four intervals, the CMB will be distributed to the different modes, namely, 16´16 or 8´8 size for integer or sub pixel of the current MB. Three conventional block matching ME algorithms, namely, full search (FS), diamond search (DS), and motion vector field adaptive search technique (MVFAST) are used to perform the simulations of both the proposed and the comparison schemes. The proposed computation-aware scheme for motion estimation in MPEG-4 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 7
1.2.2 Fast ME algorithms reducing computational complexity at each checking point 8
1.2.3 Fast ME algorithms arranging restricted computational power appropriately 9
1.3 Overview of Proposed Approach 11
1.4 Thesis Organization 12

CHAPTER 2 MPEG-4 VIDEO COMPRESSION STANDARD AND MPEG-4 MOTION ESTIMATION SCHEMES 13
2.1 MPEG-4 Video Compression Standard 13
2.2 MPEG-4 Video Compression Techniques 14
2.2.1 Source coder of MPEG-4 14
2.2.2 Temporal redundancy reduction 15
2.2.3 Integer pixel motion estimation 16
2.2.4 Half sample search 17
2.2.5 INTRA/INTER mode decision 18
2.2.6 Motion compensation 19
2.2.7 Spatial redundancy reduction 19
2.2.8 Quantization method 21
2.3 Syntax and Data Organization of MPEG-4 Video 22
2.4 MPEG-4 Motion Estimation Schemes 25
2.4.1 Full search 26
2.4.2 Diamond search 27
2.4.3 Motion vector field adaptive search technique 28

CHAPTER 3 PROPOSED COMPUTATION-AWARE SCHEME FOR MOTION ESTIMATION IN MPEG-4 VIDEO 30
3.1 An Existing Computation-Aware Scheme 30
3.2 Proposed Computation-Aware Scheme for Motion Estimation in MPEG-4 34
3.2.1 Overview 34
3.2.2 Measurement unit for computation power 35
3.2.3 Temporal motion vector prediction 37
3.2.4 Frame level computation allocation 39
3.2.5 MB level computation distribution 41
3.2.6 Mode level computation allocation 41

CHAPTER 4 SIMULATION RESULTS 44

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

REFERENCES 55

[1]Y. Q. Shi and H. Sun, Image and Video Compression for Multimedia Engineering: Fundamentals, Algorithms, and Standards. New York: CRC, 2000.
[2]M. T. Sun and A. R. Reibman (Eds.), Compressed Video over Networks. New York: Marcel Dekker, 2001.
[3]R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2nd Edition. Upper Saddle River, NJ: Prentice Hall, 2002.
[4]Y. Wang, J. Ostermann, and Y. Q. Zhang, Video Processing and Communications. Upper Saddle River, NJ: Prentice Hall, 2002.
[5]K. N. Ngan, C. W. Yap, and K. T. Tan, Video Coding for Wireless Communications. New Jersey: Prentice Hall, 2002.
[6]D. L. Gall, “MPEG: a video compression standard for multimedia applications,” Commun. of the ACM, vol. 34, no. 4, pp. 46-58, April 1991.
[7]ISO/IEC 11172-2, Information technology-coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s: video, Nov. 1991.
[8]ISO/IEC DIS 13818-2, Information technology-generic coding of moving pictures and associated audio information: video, Nov. 1994.
[9]J. L. Mitchell, W. B. Pennebaker, C. E. Fogg, and D. J. LeGall, MPEG Video Compression Standard. New York: Chapman & Hall, 1997.
[10]B. G. Haskell, A. Puri, and A. N. Netravali, Digital Video: An Introduction to MPEG-2. New York: Chapman & Hall, 1997.
[11]ISO/IEC JTC1/SC29/WG11 N3908, “MPEG-4 video verification model V18.0,” Jan. 2001.
[12]ISO/IEC JTC1/SC29/WG11 N4668, “MPEG-4 overview,” March 2002.
[13]T. Sikora, “The MPEG-4 video standard verification model,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 7, no. 1, pp. 19-31, Feb. 1997.
[14]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.
[15]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.
[16]A. N. Netravali and J. D. Robbins, “Motion compensated television coding: Part I,” Bell Syst. Tech. J., vol. 58, pp. 631-670, March 1979.
[17]A. Murat Tekalp, Digital Video Processing. Englewood Cliffs, NJ: Prentice-Hall, 1995.
[18]Video codec for audiovisual services at p´64 kbit/s, CCITT Recommendation H.261, 1990.
[19]Video coding for low bitrate communication, ITU-T Recommendation H.263, May 1998.
[20]D. J. Le Gall, “The MPEG video compression algorithm,” Signal Processing: Image Commun., vol. 4, no. 4, pp. 129-140, 1992.
[21]R. Schäfer and T. Sikora, “Digital video coding standards and their role in video communications,” Proceedings of the IEEE, vol. 83, no. 6, pp. 907-924, June 1995.
[22]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.
[23]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.
[24]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.
[25]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.
[26]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.
[27]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.
[28]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.
[29]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.
[30]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.
[31]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.
[32]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.
[33]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.
[34]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.
[35]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.
[36]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.
[37]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.
[38]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.
[39]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.
[40]J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation,” IEEE Trans. on Circuits and Systems of Video Technology, vol. 8, no. 4, pp. 369-377, Aug. 1998.
[41]P. I. Hosur and K. K. Ma, “Report on performance of fast motion using motion vector field adaptive search technique,” ISO/IEC JTC1/SC29/WG11 M5453, Dec. 1999.
[42]H. S. Yoon and G. S. Lee, “Motion estimation based on spatio-temporal correlations,” in Proc. of IEEE Int. Conf. on Image Processing, vol. 2, Sept. 2003, pp. 359-362.
[43]T. Chiang, H. J. Lee, and H. Sun, “An overview of the encoding tools in the MPEG-4 reference software,” in Proc. of IEEE Int. Symposium on Circuits and Systems, vol. 1, May 2000, pp. 295-298.
[44]ISO/IEC JTC1/SC29/WG11 N3324, “Optimization model version 1.0,” March 2000.
[45]W. Zheng, I. Ahmad, and M. L. Liou, “Adaptive motion search with elastic diamond for MPEG-4 video coding,” in Proc. of IEEE Int. Conf. on Image Processing, vol. 1, Oct. 2001, pp. 377-380.
[46]A. M. Tourapis, O. C. Au, M. L. Liou, G. Shen, and I. Ahmad, “Optimizing the MPEG-4 encoder-advanced diamond zonal search,” in Proc. of IEEE Int. Symposium on Circuits and Systems, vol. 3, May 2000, pp. 674-677.
[47]P. I. Hosur and K. K. Ma, “Motion vector field adaptive fast motion estimation,” in Second Int. Conf. on Information, Communications, and Signal Processing (ICICS), Singapore, Dec. 1999, pp. 7-10.
[48]K. K. Ma and P. I. Hosur, “Performance report of motion vector field adaptive search technique (MVFAST),” ISO/IEC JTC1/SC29/WG11 MPEG99/M5851, March 2000.
[49]A. M. Tourapis, O. C. Au, and M. L. Liou, “Highly efficient predictive zonal algorithms for fast block-matching motion estimation,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 12, no. 10, pp. 934-947, Oct. 2002.
[50]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, vol. 1, pp. 70-74, Oct. 1999.
[51]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, Oct. 2004, pp. 1441-1444.