臺灣博碩士論文加值系統

移動估計演算法(Motion Estimation Algorithm)在視訊編碼技術上扮演著舉足輕重的角色，利用視訊影像之移動估測，可大量減少視訊影像中時間域重複性(Temporal Redundancy)。目前最新的國際視訊編碼標準H.264為了更進一步的達到高品質編碼及低位元率，採用可變區塊大小(Variable Block Sizes)的移動估計技術。有鑑於H.264高運算複雜度，在本論文中提出快速移動估計演算法於提升H.264於移動估計運算效率，分別是：以優先權為基礎之正規化部份誤差抉擇快速移動估測演算法、適應性搜尋範圍決策、搜尋方法決策及低動量區塊搜尋提前中止演算法。藉由H.264之實驗平台JM 12.2與其他快速演算法相較，透過本論文所提出來的演算法可更有效率地減少H.264移動估計所需之高複雜運算，並且維持高品質的影像視訊。

The newest video coding standard called H.264 provides considerable performance improvement over a wide range of bit rates and video resolutions compared to previous standards. In H.264, the motion estimation module occupies the largest computational complexity in an encoder, and it supports seven various block sizes with a tree structured macroblock partition. In order to reduce the computational complexity of motion estimation in H.264, Priority-Based Normalized Partial Distortion Search Algorithm for Fast Motion Estimation, Adaptive Search Range Decision, Search Method Decision and Early Termination for Very Low Motion MBs are proposed in this thesis. Experimental results show that the proposed algorithms provide significant coding time improvement with only slightly PSNR degradation compared to several fast motion estimation algorithms which are implemented under the JM12.2 reference software platform.

Abstract
Chapter 1 Introduction
1.1 Overview of Video Coding
1.2 Motivation
1.3 Thesis Organization
Chapter 2 Overview of Motion Estimation
2.1 Motion Estimation for Video Coding
2.2 Survey of the Fast Motion Estimation Algorithms
Chapter 3 Proposed Priority-Based Normalized Partial Distortion Search Algorithm
3.1 Priority-Based Normalized Partial Distortion Search (P-B NPDS) Algorithm
3.1.1 Proposed Priority-Based NPDS Algorithm
3.1.2 Proposed Adaptive Search Range Decision
3.1.3 Simulation Results
3.2 Implementation of P-B NPDS Fast Motion Estimation Algorithm for H.264
3.2.1 Improvement of P-B NPDS in H.264
3.2.2 Search Method Decision
3.2.3 Early Termination for Very Low Motion MBs
3.3 Summary
Chapter 4 Simulation Results and Discussion
4.1 Parameter Setting
4.2 Performance Comparisons
4.3 Performance Analysis
Chapter 5 Conclusions and Future Work

[1] ITU-T Recommendation H.261. Line transmission of non-telephone signals. Video codec for audiovisual services at px64 kbits, 1993.
[2] ITU-T Recommendataion H.263. Video coding for low bitrate communications, 1995.
[3] Video Coding for Low Bit-rate Communication, ITU-T Recommandation H.263 Version 2 (H.263+), January 1998.
[4] ISO/IEC IS 11172, Information Technology – Coding of oving Pictures and Associated Audio for Digital Storage Media Up to about 1.5 Mbits/s, 1992. (MPEG-1)
[5] ISO/IEC IS 13818, Information Technology – Generic Coding of Moving Pictures and Associated Audio Information, 1994.(MPEG-2)
[6] ISO/IEC IS 14496, Coding of Moving Pictures and Audio, 1998. (MPEG-4)
[7] Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, “Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 14496-10 AVC),” March 2003.
[8] W. K. Pratt, Digital Image Processing, Toronto, Ont. Canada: Wiley 1978.
[9] “ITU-T Recommendation H.263 Software Implementation,” Digital Video Coding Group, Telenor R&D, 1995.
[10] S. Kappagantula and K. R. Rao, “Motion compensated interframe image prediction,” IEEE Transactions on Communication, vol.33, no.9, pp.1011-1015, September 1985.
[11] S. Zhu and K.-K Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transactions on Image Processing, vol.9, no.2, pp. 287-290, February 2000.
[12] C. Zhu, X. Lin and L.-P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol.12, no.5, pp.349-355, May 2002.
[13] C.-K. Cheung and L.-M. Po, “Normalized partial distortion search algorithm for block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol.10, no.3, pp.417-422, Aprial 2000.
[14] C.-H. Cheung and L.-M. Po, “Adjustable partial distortion search algorithm for fast block motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol.13, no.1, pp.100-110, January 2003.
[15] C.-C. Wang and C.-J. Lo, “New adaptive partial distotion search algorithm for block motion estimation,” IEICE Electronics Express, vol.2, no.22, pp.554-560, November 2005.
[16] B. Montrucchio and D. Quaglia, “Now sorting-based lossless motion estimation algorithms and a partial distortion elimination performance analysis,” IEEE Transactions on Circuits and Systems for Video Technology, vol.15, no.2, pp.210-220, February 2005.
[17] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Chap.7, 2nd ed. The MIT Press, Cambridge, Mass., May 2001.
[18] Joint Video Team software JM12.2, March 2007. http://iphome.hhi.de/suehring/tml/download/
[19] A. M. Tourapis, “Enhanced predictive zonal search for single and multiple frame motion estimation,” in Proceedings of Visual Communications and Image Processing, pp. 1069-79, San Jose, CA, January 2002.
[20] 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.