臺灣博碩士論文加值系統

運動向量估計演算法在現今的視訊編碼器的設計上扮演了舉足輕重的角色，因為其佔了視訊編碼器中一半以上的運算量，且運動向量估計的結果也與壓縮的品質習習相關。儘管已有相當多的快速區塊搜尋演算法被提出來降低運動向量估計的複雜度，卻沒有任何一種可以真正滿足真實世界中各種不同的影片類型—不同的快速區塊搜尋演算法只適用於特定類型的影片。因此在本論文中，首先我們便著眼於如何設計一個快速，同時又適用於各種不同類型影片的演算法。

快速及對不同影片的調適能力是我們的主要目標。為了達到這個目的，在本論文中我們分析了現有快速區塊演算法所適用的各種不同影像類型。然後引進優先序列的編碼觀念，經由探討在優先序列中的運動向量分布情形，我們設計了一個可依據影片特性動態調整搜尋策略的演算架構。將三種現有的快速區塊搜尋演算法搭配使用，截長補短設計出一個全新的可適應性快速區塊搜尋演算法。

在最新的H.264視訊壓縮標準中，為了進一步提高對各種影片類型的壓縮效率，採用了可變動區塊大小的運動向量估計演算法，並引進了多重參考影像的機制。雖然有效地提昇了壓縮品質，多達259種可能的區塊分割及多重參考影像的可能性，卻大大地增加了運動向量估計的複雜度。因此在論文的第二部分，我們針對如何有效率地實現H.264運動向量估計演算法提出了一個快速的搜尋架構。

H.264的區塊搜尋演算法可以經由一個由小到大的SAD合併樹簡化成只要一次的4×4全域區塊搜尋。但大量的中間運算結果仍需要非常大的記憶體空間來儲存，區塊分割模式的決定也要花費不少的運算量。有鑑於此，我們設計內嵌式的合併架構並即時計算R-D結果，隨時保存最佳的模式估算結果。不僅僅省去大量暫存記憶體的需求，對快取記憶體的使用效率也大大的提昇。而我們提出的管線式多重參考影像架構，更進一步將內嵌比較及記憶體節省的觀念推廣到適於多重參考影像的應用中，提供H.264的運動向量估計一個更有效率的實現架構。

Motion estimation (ME) plays an important role in H.264 not only because it has extremely computational complexity, but also it affects the following block coding modes as well as the final coded bit-stream size. Therefore, studying on advance ME algorithms is one of the most efficient ways to improve the coding efficiency of a video codec. In thesis, we exhibit two ME schemes with software- and hardware-based implementations, respectively.

Based on the studying on fast block-matching algorithms (FBMAs) and a priority list, the software-based ME scheme is started with a study on FBMAs, and then their efficiencies are illustrated in terms of algorithm checking points. A priority list is introduced to help with classification of motion content types of real world sequences. After doing statistical analyses on the proposed priority list and FBMAs, we propose a motion-content adaptive FBMA, which can adaptively switching searching strategies among three different FBMAs to maximize the coding efficiency under the considerations of motion-content variations.

The latest H.264/AVC video coding standard adopts the variable block size (VBS) block partitions and multiple reference frames (MRF), which make the motion-compensation stage become extreme complicated. To save intermediate memory and maximum the hardware utilization, we propose an embedded merging scheme with a pipeline-based MRF extension. With this embedded design, only one copy of intermediate memory is required and fully utilization is expected after fulfilling the pipeline stages.

中文摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables and Equations vii
Chapter 1 Introduction 1
Chapter 2 Background 5
2.1 History of Video Coding Standards 5
2.2 Using Priority Info in Motion Estimation 8
2.3 Reviews on FBMAs 11
2.3.1 FBMAs Overview 11
2.3.2 Limitations of Existing FBMAs 23
2.4 The H.264 ME Algorithm 25
2.4.1 VBS Block Partitions 25
2.4.2 Multiple Reference Frames 29
2.5 Previous VLSI Motion Estimation Architectures 30
2.5.1 FBS VLSI Architectures 32
2.5.2 VBS VLSI Architectures 34
Chapter 3 Adaptive Fast Block Matching Algorithm by Switching Search Patterns for Sequences with Wide Range Motion Content[65] 36
3.1 Observations on Existing FBMAs 39
3.2 Proposed Predicted Profit List 41
3.3 A-TDB Algorithm 45
3.4 Experimental Results 51
3.4.1 Comparison of Performance among FBMAs 60
3.4.2 Detailed Behavior of A-TDB 63
3.5 Conclusions 67
Chapter 4 A Pipelining and Embedded Merging Scheme for H.264/AVC Motion Estimation[66]-[68] 68
4.1 The Proposed ME Scheme for H.264/AVC 70
4.1.1 VBS Extension with an Embedded Merging Scheme 71
4.1.2 The Multiple Reference Frame Extension 76
4.1.3 The Feasible MRF Architectures 77
4.1.4 Illustration of Extension with Pipelining MRF Architecture 81
4.2 Conclusions 85
Chapter 5 Future Works and Conclusions 87
References 90

[1] T. Sikora, “Trends and perspectives in image and video coding,” Proceedings of the IEEE, vol. 93, no. 1, Jan. 2005.
[2] T. Sikora, “MPEG digital video coding standards,” IEEE Signal Processing Magazine, vol. 14, no. 5, pp.82–100, Sep. 1997.
[3] Y. Wang, J. Ostermann, and Y.-Q. Zhang, Video Processing And Communications, Prentice Hall, ISBN 0-13-017547-1, 2002
[4] D. Marpe, H. Schwarz, and T. Wiegand, “Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard,” IEEE Transaction on Circuits System for Video Technology, vol. 13, no. 7, pp.620–636, July 2003.
[5] T. Wiegand, G. J. Sullivan, G. Bintegaard, and A. Luthra, “Overview of the H.264/AVC video coding standard,” IEEE Transaction on Circuits System for Video Technology, vol. 13, no. 7, pp.620–636, July 2003.
[6] S. Y. Yap and J. V. McCanny, “A VLSI Architecture for Variable Block Size Video Motion Estimation,” IEEE Transaction on Circuits System – II, Express Briefs, vol. 51, no. 7, pp.384–389, July 2004.
[7] Y.-W. Huang, T.-C. Wang, B.-Y. Hsieh and L.-G. Chen, “Hardware Architecture Design for Variable Block Size Motion Estimation in MPEG-4 AVC/JVT/ITU-T H.264”, in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 2003), vol. 2, pp.II–796 – II–799, May 2003.
[8] “Video codec for audiovisual services at px64 kbits/s,” ITU-T Rec. H.261, v1: Nov 1990, v2: Mar. 1993.
[9] “Video coding for low bit rate communication,” ITU-T Rec. H.263, v1: Nov. 1995, v2: Jan. 1998, v3: Nov. 2000.
[10] “Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s – Part 2: Video,” ISO/IEC 11172 (MPEG-1), Nov. 1993.
[11] “Generic coding of moving pictures and associated audio information – Part 2: Video,” ITU-T Rec. H.262 and ISO/IEC 13818-2 (MPEG-2), Nov. 1994 (with several subsequent amendments and corrigenda).
[12] “Coding of audio-visual objects – Part 2: Visual,” ISO/IEC 14496-2 (MPEG-4 Part 2), Jan. 1999 (with several subsequent amendments and corrigenda).
[13] “Draft ITU-T recommendation and final draft international standard of joint video specification (ITU-T Rec. H.264/ISO/IEC 14 496-10 AVC,” in Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, JVTG050, 2003.
[14] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proceedings, National Telecommunication Conference, New Orleans, LA, pp.G5.3.1–5.3.5, Nov. 29-Dec. 3, 1981.
[15] L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Transaction on Circuits System for Video Technology, vol. 6, pp.419–423, Aug. 1996.
[16] R. Li, B. Zeng, and M. L. Liou, “A new three-step search algorithm for block motion estimation,” IEEE Transaction on Circuits System for Video Technology, vol. 4, pp.438–442, Aug. 1994.
[17] L. M. Po and W. C. Ma, “A novel four-step search algorithm for fast block motion estimation,” IEEE Transaction on Circuits System for Video Technology, vol. 6, pp.313–317, Jun. 1996.
[18] S. Zhu and K.-K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Transaction on Image Processing, vol. 9, pp.287–290, Feb. 2000.
[19] P.-L. Tai, S.-Y. Huang, C.-T. Liu, and J.-S. Wang,“ Computation-aware scheme for software-based block motion estimation,” IEEE Transaction on Circuits System for Video Technology, vol. 13, no. 9, pp.901–913, Sep. 2003.
[20] C. Zhu, X. Lin, L.-P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Transaction on Circuits System for Video Technology, vol. 12, pp.349–355, May 2002.
[21] C.-H. Cheung and L.-M. Po, “A Novel Small-Cross-Diamond Search Algorithm for Fast Video Coding and Videoconferencing Applications,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2002), pp.681–684, Sep. 2002.
[22] A. Andersson, T. Hagerup, “S. Nilsson and R. Raman, Sorting in linear time,” Journal of Computer and System Sciences, vol. 57, pp.74–93, 1998.
[23] Y.-K. Tu, J.-F. Yang, Y.-N. Shen, and M.-T. Sun,” Fast Variable-Size Block Motion Estimation Using Merging Procedure with an Adaptive Threshold,” in Proceedings, IEEE International Conference on Multimedia and Expo (ICME 2003), vol. 2, pp.II–789–92, 6-9 July 2003.
[24] Z. Zhou and M.-T. Sun, “Fast Variable Block-Size Motion Estimation Algorithm Based on Merge and Split Procedures for H.264/MPEG-4 AVC”, in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 2004), vol. 3, pp.III–725–8, 23-26 May 2004.
[25] Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, “Joint Model Number 1, Revision 1(JM-1r1),” ITU-T SG16 Q.6 (VCEG) and ISO/IEC JTC 1/SC 29/WG 11 (MPEG), JVT-A003r1.doc, 2002-01-18.
[26] http://bs.hhi.de/~suehring/tml/, H.264/AVC Software Coordination.
[27] J. Ostermann et al, “Video coding with H.264/AVC: Tools, Performance, and Complexity,” IEEE Circuits and Systems Magazine, pp.7–28, 1st Quarter 2004.
[28] T. Wiegand, H. Schwarz, A. Joch, and F. Kossentini, “Rate-constrained coder control and comparison of video coding standards,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 13, pp.688–703, July 2003.
[29] B. Girod, “Efficiency analysis of multihypothesis motion-compensated prediction for video coding,” IEEE Transaction on Image Processing, vol. 9, pp.173–183, Feb. 2000.
[30] M. Flierl, T. Wiegand, and B. Girod, “Rate-constrained multi-hypothesis motion-compensated prediction for video coding,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2000), vol. 3, pp.150–153, 10-13 Sep., 2000.
[31] L. Yang, K. Yu, J. Li, and S. Li, “An Effective Variable Block-Size Early Termination Algorithm for H.264 Video Coding,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 15, no. 6, pp.784–788, Jun. 2005.
[32] X. Jing and L.-P. Chau, “An Efficient Inter Mode Decision Approach for H.264 Video Coding,” in Proceedings, IEEE International Conference on Multimedia and Expo (ICME 2004), vol. 2, pp.1111–1114, 27-30 Jun., 2004.
[33] K. Khan, S. Masud, A. Ahmad, and M. A. Maud, “Efficient Scheme for Motion Estimation and Block Size Mode Selection in H.264,” in Proceedings, International Symposium on Communications and Information Technologies (ISCIT 2004), vol. 2, pp.747–751, Sapporo, Japan, 26-29 Oct., 2004.
[34] A. Chang, P. H. W. Wong, Y. M. Yeung, O.C. Au, “Fast Integer Motion Estimation for H.264 Video Coding Standard,” in Proceedings, IEEE International Conference on Multimedia and Expo (ICME 2004), vol. 1, pp.289–292, 27-30 Jun., 2004.
[35] T.-H. Tsai and Y.-N. Pan, “A Novel Predict Hexagon Search Algorithm for Fast Block Motion Estimation on H.264 Video Coding,” in Proceedings, IEEE Asia-Pacific Conference on Circuit and System (APCCAS 2004), vol. 1, pp.609–612, 6-9 Dec, 2004.
[36] M. Yang, H. Cui and K. Tang, “Efficient Tree Structured Motion Estimation Using Successive Elimination,” IEE proceedings, Vision, Image and Signal Processing, vol. 151, no. 5, pp.369–377, 30 Oct., 2004.
[37] T. Toivonen and J. Heikkild, “Fast Full Search Block Motion Estimation for H.264/AVC with Multilevel Successive Elimination Algorithm,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2004), vol. 3, pp.1485–1488, 24-27 Oct., 2004.
[38] T. Shimizu, A. Yoneyama, H. Yanagihara, and Y. Nakajima, “A Two-stage Variable Block Size Motion Search Algorithm for H.264 Encoder,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2004), vol. 3, pp.1481–1484, 24-27 Oct., 2004.
[39] W. Lit, G.-H. Li, and J. Zhang, “Efficient Motion Estimation using Two-Phase Algorithm,” in Proceedings, the Third International Conference on Machine Learning and Cyber-metrics, vol. 7, pp.4004–4008, Shanghai, 26-29 Aug., 2004.
[40] A. Chang, O. C. Au, and Y. M. Yeung, “A Novel Approach to Fast Multi-block Motion Estimation for H.264 Video Coding,” in Proceedings, IEEE International Conference on Multimedia and Expo (ICME 2003), vol. 1, pp.I–105–108, 6-9 July 2003.
[41] Y. Su and M.-T. Sun, “Fast multiple reference FRAME motion estimation for H.264,” in Proceedings, IEEE International Conference on Multimedia and Expo (ICME 2004), vol. 1, pp.695–698, 27-30 Jun., 2004.
[42] H. Chung, D. Romacho, and A. Ortegat, “Fast Long-term Motion Estimation for H.264 using Multi-resolution Search,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2003), vol. 1, pp.I–905–908, 14-17 Sep., 2003.
[43] H.-J. Li, C.-T. Hsu, and M.-J. Chen, “Fast Multiple Reference Frame Selection Method for Motion Estimation in JVT/H.264,” in Proceedings, IEEE Asia-Pacific Conference on Circuit and System (APCCAS 2004), vol. 1, pp.605–608, 6-9 Dec, 2004.
[44] Y.-K. Tu, J.-F. Yang, Y.-N. Shen, and M.-T. Sun, “Fast Variable-Size Block Motion Estimation using Merging Procedure with an Adaptive Threshold,” in Proceedings, IEEE International Conference on Multimedia and Expo (ICME 2003), vol. 2, pp.II–789–792, 6-9 July 2003.
[45] S.-C. Tai, Y.-R. Chen and S.-J. Li, “Low Complexity Variable-Size Block Matching Motion Estimation for Adaptive Motion Compensation Block Size in H.264,” in Proceedings, IEEE Asia-Pacific Conference on Circuit and System (APCCAS 2004), vol. 1, pp.613–616, 6-9 Dec, 2004.
[46] H. E. Ates and Y. Altunbasak, “SAD Reuse in Hierarchical Motion Estimation for the H.264 Encoder,” in Proceedings, IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2005), vol. 2, pp.905–908, 18-23 Mar., 2005.
[47] K.-M. Yang, M.-T. Sun, and L. Wu, “A family of VLSI designs for the motion compensation block-matching algorithm,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 36, no. 10, pp.1317–1325, Oct 1989.
[48] Y.-K. Lai and L.-G. Chen, “A Data-Interlacing Architecture with Two-Dimensional Data-Reuse for Full-Search Block-Matching Algorithm,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 8, no. 2, pp.124 –127, Apr. 1998.
[49] T. Komarek and P. Pirsch, “Array architectures for block matching algorithms,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 36, no. 10, pp.1301–1308, Oct 1989.
[50] C.-H. Hsieh and T.-P. Lin, “VLSI architecture for block-matching motion estimation algorithm,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 2, no. 2, pp.169 –175, Jun.1992.
[51] Y.-H. Yeh and C.-Y. Lee, “Scalable VLSI architectures for full-search block matching algorithms,” in Proceedings, IEEE International Conference on Image Processing (ICIP 1996), vol. 1, pp.1035–1038, 16-19 Sep 1996.
[52] V. L. Do and K. Y. Yun, “A low-power VLSI architecture for full-search block-matching motion estimation,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 8, no. 4, pp.393–398, Aug. 1998.
[53] Y.-S. Jehng, L.-G. Chen, and T.-D. Chiueh, “An efficient and simple VLSI tree architecture for motion estimation algorithms,” IEEE Transaction on Signal Processing, vol. 41, no. 2, pp.889–900, Feb. 1993.
[54] J.-C. Tuan, T.-S. Chang, and C.-W. Jen, “On the data reuse and memory bandwidth analysis for full-search block-matching VLSI architecture,” IEEE Transaction on Circuits and Systems for Video Technology, vol. 12, no. 1, pp.61–72, Jan. 2002.
[55] C. Wei and M. Z. Gang, “A Novel SAD Computing Hardware Architecture for Variable-size Block Motion Estimation and Its Implementation with FPGA,” in Proceedings, IEEE 5th International Conference on ASIC, vol. 2, pp.950–953, 21-24 Oct., 2003.
[56] S. Y. Yap and J. V. McCanny, “A VLSI Architecture for Advanced Video Coding Motion Estimation,” in Proceedings, the Application-Specific Systems, Architectures, and Processors, ASAP 2003, pp.293–301, 24-26 Jun., 2003.
[57] Y.-W. Huang, T.-C. Wang, B.-Y. Hsieh, and L.-G. Chen, “Hardware Architecture Design for Variable Block Size Motion Estimation in MPEG-4 AVC/JVT/ITU-T H.264,” in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 2003), vol. 2, pp.II–796–II–799, 25-28 May, 2003.
[58] J. H. Lee and N. S. Lee, “Variable Block Size Motion Estimation Algorithm and Its Hardware Architecture for H.264/AVC,” in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 2004), vol. 3, pp.III–741–III–744, 23-26 May, 2004.
[59] C. Wei, Z. Yan, M. Z. Gang, L. Z. Qiang, “VLSI Architecture Design for Variable-Size Block Motion Estimation in MPEG-4 AVC/H.264,” in Proceedings, IEEE Asia-Pacific Conference on Circuit and System (APCCAS 2004), vol. 1, pp.617–620, 6-9 Dec, 2004.
[60] T.-C. Wang, Y.-W. Huang, H.-C. Fang, and L.-G. Chen, “Performance Analysis of Hardware Oriented Algorithm Modifications in H.264,” in Proceedings, IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2003), vol. 2, pp.II–493–II–496, 6-10 Apr., 2003.
[61] Y.-Y. Wang, Y.-T. Peng, C.-J. Tsai, “VLSI Architecture Design of Motion Estimator and In-Loop Filter for MPEG-4 AVC/H.264 Encoders,” in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 2004), vol. 2, pp.III–149–II–152, 23-26 May, 2004.
[62] L. de Vos and M. Schobinger, “VLSI architecture for a flexible block matching processor,” IEEE Transaction on Circuits System for Video Technology, vol. 5, pp.417–428, Oct., 1995.
[63] G. Fujita, T. Onoye, and I. Shirakawa, “A new motion estimation core dedicated to H.263 video coding,” in Proceedings, IEEE International Symposium on Circuits and Systems (ISCAS 1997), vol. 2, pp.1161–1164, 1997.
[64] J.-F. Shen; T.-C. Wang; L.-G. Chen., “A novel low-power full-search block-matching motion- estimation design for H.263+,” IEEE Transaction on Circuits System for Video Technology, vol.11, no. 7, pp.890–897, July 2001.
[65] S.-Y. Huang, C.-Y. Cho and Jia-Shung Wang, “An Adaptive Fast Block Matching Algorithm Employing Profit List,” IEEE Transaction on Circuits System for Video Technology, vol. 15, no. 11, pp.1373–1384, Nov. 2004.
[66] C.-Y. Cho, S.-Y. Huang, and J.-S. Wang, “An embedded merging scheme for H.264/AVC motion estimation,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2003), vol. 1, pp.I–909–12, 14-17 Sep., 2003.
[67] C.-Y. Cho, S.-Y. Huang, J.-N. Hwang, and J.-S. Wang, “An embedded merging scheme for VLSI implementation of H.264/AVC motion Estimation modules,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2005), vol. 3, pp.III–1016–19, 11-14 Sep., 2005.
[68] C.-Y. Cho, S.-K. Chang and J.-S. Wang, “A multiframe motion estimation architecture for H.264/AVC,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2006), to be appeared, 8-11 Oct., 2006.
[69] Z. Zhou, M.-T. Sun, Y.-F. Hsu, “Fast variable block-size motion estimation algorithm based on merge and split procedures for H.264/MPEG-4 AVC,” in Proceedings, IEEE International Conference on Image Processing (ICIP 2004), vol. 3, pp.III–725–728, May 2004.
[70] S.-Y. Huang, “Advanced mode decision in computation-aware motion estimation for H.264/AVC codec,” Master thesis, Dept. of Computer Science, National Tsing Hua University, Taiwan, July 2005.