臺灣博碩士論文加值系統

在視訊影像編碼中，移動估計是最廣泛被用來消除時間重覆性(Temporal
redundancy)的技術，而相對的則是必須付出高計算量的代價。為了減少移動估計
所需要的計算量，本論文以拉格朗日(Lagrange)最佳化法則為基礎，在計算量以
及位元-失真之編碼效率間求得最佳化的結果，導出成本函數以提出了適應性巨
區塊搜尋範圍決策演算法。而在近年來的手持行動裝置上，計算量導向的概念越
來越受到重視。因此在這個議題上，我們亦提出適應性有限計算資源分配演算法。
從實驗結果得知，除了可以在計算量充足的情形下，節省70%左右的編碼時間，
也可以在計算量受限的情形下，做有效率的計算量分配。

In video coding standard, the motion estimation technique is widely adopted to
significantly eliminate the temporal redundancies existing in video signal at the cost
of intensive computational burden. To reduce the computational overhead of motion
estimation, a dynamic search range decision algorithm is proposed in this thesis based
on the Lagrange optimization approach which aims at optimizing the tradeoff between
computational complexity and rate distortion performance. In addition, with the rapid
popularity of computation resource constrained devices, computation aware design
receives more and more attentions recently. To address this issue, this thesis proposes
a computation aware motion estimation algorithm which adaptively allocates the
computational resource to the motion estimation process according to the available
computation budgets. Experimental results show that the proposed algorithms can
distribute the proper computation resource to each macroblock (MB) and thus saving
the encoding time up to 70% when compared to full search motion estimation
algorithm.

中文摘要 .................................................................................................................................. 1
Abstract .................................................................................................................................... 2
Table of Content ........................................................................................................................ 8
Figure Index ............................................................................................................................ 10
Table Index .............................................................................................................................. 12
Chapter 1 Introduction ......................................................................................................... 13
1.1 Overview of Video Coding ........................................................................................ 13
1.2 Motivation ................................................................................................................. 21
1.3 Organization of this thesis ......................................................................................... 22
Chapter 2 Overview of Computation-Aware Video Coding ................................................. 23
2.1 Concept of Variable Computation Complexity .......................................................... 23
2.2 Review of the Related Work ...................................................................................... 24
Chapter 3 Proposed Adaptive Search Range Decision Method ........................................... 31
3.1 Observation and Analysis .......................................................................................... 31
3.2 Proposed Adaptive Search Range Decision Algorithm ............................................. 35
3.3 The Computation-aware Adaptive Search Range Decision ....................................... 41
9
Chapter 4 Experimental Results ........................................................................................... 47
4.1 Experiment Environment Setting .............................................................................. 47
4.2 Experimental Results Comparison and Analysis ....................................................... 48
4.3 Experimental results analysis for computation aware method .................................. 54
Chapter 5 Conclusion and Future Work ............................................................................... 63
Reference ................................................................................................................................ 65

[1] Iain E.G. Richardson, “Video Codec Design,” John Wiely & Sons. LTD., 2002.
[2] ITU-T Recommendation H.261. Line transmission of non-telephone signals. Video codec for audiovisual services at px64 kbits/sec, 1993.
[3] ITU-T Recommendation H.263. Video coding for low bitrate communications, 1995.
[4] Video Coding for Low Bit-rate Communication, ITU-T Recommendation H.263 Version 2(H.263+), January 1998.
[5] ISO/IEC IS 11172, Information Technology – Coding of Moving Pictures and associated Audio for Digital Storage Media Up to about 1.5 Mbits/s, 1992. (MPEG-1).
[6] ISO/IEC IS 13818, Information Technology – Generic Coding of Moving Pictures and Associated Audio Information. 1994(MPEG-2).
[7] ISO/IEC IS 14496, Coding of Moving Pictures and Audio, 1998. (MPEG-4).
[8] 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.
[9] S .Kappagantula and K. R. Rao, “Motion compensated interframe image prediction,” IEEE Transactions on Communication, Vol. 33, No. 9, pp.1011-1015, Sep. 1985.
[10] 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, Feb. 2000.
[11] M. H. Ho, J. J. Huang, S.C. Chin and C. L. Hsu, “High efficient NTSS-based parallel architecture for motion estimation in H.264,” in Proceeding of International Conference on Communications, Circuits and Systems, pp. 679-683, May 2008.
[12] Y. N. Wang and Y. Y. Fan, “An adaptive diamond searching algorithm on space-time correlation,” in Proceeding of Fourth International Conference on Image and Graphics, pp. 220-223, Aug. 2007.
[13] S. Saponara, M. Casula, F. Rovati, D. Alfonso, and L. Fanucci, “Dynamic control of motion estimation search parameters for low complex H.264 video coding,” IEEE Transactions on Consumer Electronics, Vol. 52, No. 1, pp. 232-239, Feb. 2006.
[14] Z. Chen, S. Yang, T. Ikenaga and S. Goto, “A macroblock level adaptive search range algorithm for variable block size motion estimation in H.264/AVC,＂ International Symposium on Intelligent Signal Processing and Communication Systems 2007, pp.598-601, Nov. 2007.
[15] Z. Chen, Q. Liu, T. Ikenaga and S. Goto, “A motion vector difference based self-incremental adaptive search range algorithm for variable block size motion estimation,” IEEE International Conference on Image Processing 2008, pp. 1988-1991, Oct. 2008.
[16] P. L. Tai, S. Y. Huang, C. T. Liu and J. S. Wang, “Computation-aware scheme for software-based block motion estimation, ”IEEE Transactions on Circuits and Systems for Video Technology, Vol. 13, No. 9, pp. 901-913, Sep. 2003.
[17] C. J. Lian, S. Y. Chien, C. P. Lin, P. C. Tseng and L. G. Chen, “Power-aware multimedia： concepts and design perspectives,” IEEE Circuits and Systems Magazine, Vol. 7, No. 2, pp. 26-34, 2007.
[18] D. He, Y. Liang, L. Chen, A. I. and D. Wu, “Power-rate-distortion analysis for wireless video communication under energy constraints,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 15, No. 5, pp.645-658, May 2005.
[19] W. Lin, K. Panusopone, D. Baylon and M. T. Sun, “ A new one-pass Complexity-Scalable computation-control method for video coding,” IEEE International Symposium on Circuits and Systems, pp.868-871, May 2009.
[20] C. Y. Cho, N. S. Y. Huang and J. S. Wang, “Design of computation-aware mode decision scheme for H.264/AVC,” in Proceeding of 2006 IEEE International Conference on Acoustics, Speech and Signal Processing, Vol. 2, pp.II-14–II-19, May 2006.
[21] C. Y. Chang, J. J. Leou, S. S. Kuo and H. Y. Chen, “A new computation-aware scheme for motion estimation in H.264/AVC,” in Proceeding of 2008 International Conference on Computer and Information Technology, pp.561-565, July 2008.
[22] M. C. Chien, Z. Y. Chen and P. C. Chang, “Coding-gain based complexity control for h.264 video encoder,” in Proceeding of 2008 International Conference on Image Processing, October 2008.
[23] Joint Video Team software JM14.1, Sep. 2008. http://iphome.hhi.de/suehring/tml/download/old_jm/.