跳到主要內容

臺灣博碩士論文加值系統

(34.204.169.230) 您好!臺灣時間:2024/02/28 06:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:海珊
研究生(外文):Esam A. Al_Qaralleh
論文名稱:用於MPEG-4與H.264視訊編碼的移動估測設計
論文名稱(外文):Design of Motion Estimation for MPEG-4 and H.264 Video Coding
指導教授:張添烜任建葳任建葳引用關係
指導教授(外文):Tian-Sheuan ChangChein-Wei Jen
學位類別:博士
校院名稱:國立交通大學
系所名稱:電子工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:100
中文關鍵詞:視訊編碼移動估測
外文關鍵詞:motion estimationdata reusebinary motion estimation for shape codingvariable block size
相關次數:
  • 被引用被引用:0
  • 點閱點閱:156
  • 評分評分:
  • 下載下載:20
  • 收藏至我的研究室書目清單書目收藏:0
Motion estimation is one of key part in modern video standards like MPEG-4 and H.264 to remove the temporal redundancy between video frames. However, it is also computational intensive and memory intensive. Thus, in this dissertation, we propose two designs, binary motion estimation and variable block size motion estimation, to reduce the computational load, and one vertical data reuse scheme to minimize the memory access.
The first work supports the binary motion estimation for shape coding adopted by MPEG-4. In binary motion estimation, its processing is at the bit level and thus is not suitable for general purpose processors due to their word-level processing capability. Thus, we propose a fast algorithm and its architecture that takes advantages of this bit level (binary level). With the count of bits in a block, the proposed algorithm classifies and tests every candidate search position and then skips those unlikely to be a match. The proposed algorithm can adaptively overlap matching between different classes to get more accurate motion vector or more skipping ratio. The proposed algorithm achieves a saving in computational complexity ranging from 96.69% to 99.71% comes with the expense of increasing the shape encoded bits by 0.7% to 12.8%. Due to the simplicity and the regularity of the algorithm, the proposed hardware is also regular and needs only 11582 gate count.
The second work supports the variable block size motion estimation. Variable block size limits the efficiency of early termination, but the algorithm shows good performance in this field. This design uses the early termination that adaptively changes its threshold to fit the variable block size and achieve early skipping. Different variables can be tuned by the algorithm to compromise between the high skipping ratio and the accurate motion vector. The proposed algorithm outperforms other similar algorithms with a complexity reduction of 78% and 51% for MPEG-4 and H.264 respectively. The hardware implementation of the algorithm can process one MB in 16 clock cycles, and completes a 16x16 search window in 4096 clock cycle without any termination process and an average 1032 clock cycles with termination process. The hardware uses only 16 registers and 31 adders and gate count of 16k.
Finally, the third work reduces the huge memory access by vertical processing adjacent current macroblocks. Vertical processing can achieve the same speed up of the horizontal processing but lower memory access especially for large search window. A design is introduced to demonstrate the efficiency of the vertical processing compared to horizontal processing using the same number of processing elements. This simple and regular design can be easily extended to any number of PE without extra cost to the control circuit or any change in the data flow. The required data bandwidth is reduced by 60.9% with four processing elements and 61k gate count when compared to the previous designs.
Chapter 1 Introduction 1
1.1 Overview of Video Coding 1
1.2 Cores of Digital Video Technology 2
1.2.1 MPEG-4 Overview . 3
1.2.2 H.264 Overview 6
1.3 Motivation and Contributions 8
1.4 Dissertation Organization 10
Chapter 2 A Fast Binary Motion Estimation Algorithm and its Architecture Design 11
2.1 Overview of the MPEG-4 Video System 11
2.1.1 Video Object and Video Object Plane 11
2.1.2 MPEG-4 Binary Shape Coding 12
2.2 Motion Estimation for MPEG-4 Video 16
2.2.1 Block-matching Algorithm . 17
2.2.2 Search Range and Search Points 18
2.3 Analysis of Binary Motion Estimation 19
2.4 Previous Work on Binary Motion Estimation 20
2.5 Motivation for Fast Binary Motion Estimation 22
2.6 The Proposed Algorithm .. 24
2.6.1 Software simulation results and analysis 24
2.6.2 Block-matching Algorithm . 25
2.6.3 Consideration for the Classification and Matching Methods 29
2.7 The Architecture Design. 30
2.7.1 Architecture Design 30
2.7.2 PE Design .. 31
2.7.3 Data reuse and data flow 32
2.7.4 Experiments results ... 34
2.7.5 Comparisons ... 36
2.8 Summary .. 37
Chapter 3 Texture Motion Estimation for MPEG-4 and H.264 39
3.1 Introduction to Block Matching 39
3.2 Exploration of Algorithms 41
3.2.1 Proposed Algorithm-Software Approach 42
3.3 Exploration of Architectures 53
3.3.1 ME Architectures – an overview 54
3.3.2 Proposed Architecture 54
3.4 Summary 60
Chapter 4 Data Reuse Exploration Between Vertical Adjacent Macro Blocks . 62
4.1 Introduction 62
4.2 Data reuse in the motion estimation 63
4.3 Data reuse and parallel processing of vertical blocks. . 64
4.3.1 Proposed data reuse scheme 67
4.3.2 Architecture Design 70
4.3.3 Design comparisons 77
4.4 Summary 78
Chapter 5 Future Work and Conclusion 79
5.1 Contributions Summary 79
5.2 Future Work 82
5.2.1 Fractional Motion Estimation 82
5.2.2 Mode Selection and Hilbert Transform 87
5.2.3 Binary Motion Estimation 89
5.3 Summary 91
References 93
[1] ISO/IEC JTC1/SC29, Coding of moving pictures and associated audio for digital storage media up to about1.5 Mbit/s, ISO/IEC 1172-2, International Standard, November 1992.
[2] ISO/IEC JTC1/SC29, Generic coding of moving pictures and associated audio, ISO/IEC 13818-2, Draft International Standard, November 1994.
[3] ISO AEC JTC1/SC29/WG11, N2502a, Generic coding of Audio-Visual Objects: Visual 14496-2, Final Draft IS, Atlantic City, Dec. 1998.
[4] ISO/IEC JTC1/SC29, Coding of audio-visual objects, ISO/IEC 14496-2, International Standard: 1999/Amd1:2000, January 2000.
[5] Joint Video Team (JVT), “Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification,” 7th Meeting, Pattaya, Thailand, March 7-14, 2003.
[6] ISO/IEC JTC1/SC29/WG11 N3908, “MPEG-4 Video Verification Model Version 18.0,” Jan. 2001.
[7] JVT reference software version 9.0 http://bs.hhi.de/~suehring/tml/download/.
[8] N. Brady, "MPEG-4 standardized methods for the compression of arbitrarily shaped video objects," IEEE Transactions on Circuits and Systems for Video Technology, vol.9, no. 8, pp:1170-1189, Dec. 1999.
[9] A. Puri, X. Chen and A. Luthra,"Video coding using the H.264/MPEG-4 AVC compression standard," Signal processing: Image Commuincation, vol.19, no. 9, pp: 793-849, Oct. 2004.
[10] Y. C. Wang, H. C. Chang, W. M. Chao and L. G. Chen,”An Efficient Architecture of Binary Motion Estimation for MPEG-4 Shape Coding,” Visual Commuinactios and Image Processing, San Jose, CA, pp: 959-967, Jan. 2001.
[11] T. H. Tsai and C. P. Chen;” An efficient binary motion estimation algorithm and its architecture for MPEG-4 shape coding,” in proceeding of IEEE International Symposium on Circuit and System, vol. 2, pp: 496-499, May 2003.
[12] T. H. Tsai; C. P. Chen;” A Fast Binary Motion Estimation algorithm for MPEG-4 shape coding,” IEEE Transactions on Circuits and System for Video Technology, vol. 14, no. 6, pp: 908 – 913, June 2004.
[13] D. Yu, S. K. Jang and J. B. Ra,”Fast Motion Estimation for Shape Coding in MPEG-4,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no.4, pp: 358 – 363, April 2003.
[14] K. Panusopone and X. Chen,“ A fast motion estimation method for MPEG-4 arbitrarily shaped objects,” in Proceeding of IEE International Conference on Image Processing, vol. 3, pp: 624-627, Sept. 2000.
[15] Peter Kuhn,"Algorithms, Complexity Analysis and VLSI Archtectures for MPEG-4 Motion Estimation," Kluwer Academic Publishers, 1999.
[16] J. Jain and A. Jain, "Displacement measurement and its application in internal image coding," IEEE Transactions on Communications, vol. COM-29, no. 12, pp: 1799-1808, Dec. 1981.
[17] T. Koga, K. Iinuma, A. Hirano, Y. lijima, and T. Ishiguro, "Motion compensated interframe coding for video conferencing," in Proceedings of National Telecom¬munication Conference, pp: C9.6.1-C9.6.5, 1981.
[18] R. Srinivasan and K. R. Rao,"Predictive coding based on efficient motion estima¬tion," IEEE Transactions on Communications, vol. COM-33, no. 8, pp: 888-896, Aug. 1985.
[19] S. Kappagantula and K. R. Rao, "Motion compensated interframe image predic¬tion," IEEE Transactions on Communications, vol. COM-33, no. 9, pp: 1011— 1015, Sept. 1985.
[20] M. Ghanbari, "The cross search algorithm for motion estimation," IEEE Trans¬actions on Communications, vol. 38, no. 7, pp: 950-953, July 1990.
[21] L. G. Chen, W. T. Chen, Y. S. Jehng, and T. D. Chiueh, "An efficient parallel motion estimation algorithm for digital image processing," IEEE Transactions on Circuits and Systems for Video Technology, vol. 1, no. 4, pp: 378-385, Dec. 1991.
[22] M. J. Chen, L. G. Chen, and T. D. Chiueh, "One-dimensional full search mo¬tion estimation algorithm for video coding," IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no. 5, pp: 504-509, June 1994.
[23] R. Li, B. Zeng, and M. L. Liou,"A new three-step search algorithm for block motion estimation," IEEE Transactions on Circuits and Systems for Video Tech¬nology, vol. 4, no. 4, pp: 438-442, Aug. 1994.
[24] L. M. Po and W. C. Ma,"A novel four-step search algorithm for fast block mo¬tion estimation," IEEE Transactions on Circuits and Systems for Video Technol¬ogy, vol. 6, no. 3, pp: 313-317, June 1996.
[25] L. K. Liu and E. Feig,"A block-based gradient descent search algorithm for block motion estimation in video coding," IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 4, pp: 419-422, Aug. 1996.
[26] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, "A novel unre¬stricted center-biased diamond search algorithm for block motion estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 4, pp: 369-377, Aug. 1998.
[27] S. Zhu and K. K. Ma, "A new diamond search algorithm for fast block-matching motion estimation," IEEE Transations on Image Processing, vol. 9, no. 2, pp:287-290, Feb. 2000.
[28] A. M. Tourapis, O. C. Au, M. L. Liou, G. Shen, and I. Ahmad, "Optimizing the MPEG-4 encoder - advanced diamond zonal search," in Proceedings of IEEE International Symposium on Circuits and Systems , pp: 674-677, 2000
[29] A. M. Tourapis, O. C. Au, and M. L. Liu, "Highly efficient predictive zonal algorithms for fast block-matching motion estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 10, pp: 934-947, Oct. 2002.
[30] V. Christopoulos and J. Comelis, "A center-biased adaptive search algorithm for block motion estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, no. 3, pp: 423-426, Apr. 2000.
[31] O. T. C. Chen, "Motion estimation using a one-dimensional gradient descent search," IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, no. 4, pp: 608-616, June 2000.
[32] C. H. Cheung and L. M. Po, "A novel cross diamond search algorithm for fast block motion estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 12, pp: 1168-1177, Dec. 2002.
[33] Y. W. Huang, S. Y. Ma, C. F. Shen, and L. G. Chen, "Predictive line search: an efficient motion estimation algorithm for mpeg-4 encoding systems on multime¬dia processors," IEEE Transactions on Circuits and Systems for Video Technol¬ogy, vol. 13, no. l, pp: 111-117, Jan. 2003.
[34] C. W. Lam, L. M. Po, and C. H. Cheung, "A novel kite-cross-diamond search algorithm for fast video coding and videoconferencing applications," in Proceed¬ings of IEEE International Conference on Acoustics, Speech, and Signal Process¬ing, pp: 365-368, 2004.
[35] M. Bierling, "Displacement estimation by hierarchical block matching," in Pro¬ceedings of SPIE Visual Communication and Image Processing, pp: 942-951, 1988.
[36] H. Gharavi and M. Mills, "Block matching motion estimation algorithms - new results," IEEE Transactions on Circuits and Systems, vol. 37, no. 5, pp: 649-651, May 1990.
[37] J. S. Kim and R. H. Park, "A fast feature-based block matching algorithm using integral projections," IEEE Journal on Selected Areas in Communications, vol. 10, no. 5, pp: 968-979, June 1992.
[38] K. Sauer and B. Schwartz, "Efficient block motion estimation using integral projections," IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 5, pp: 513-518, Oct. 1996.
[39] B. Natarajan and V. Bhaskaran, "Low-complexity block-based motion estimation via one-bit transforms," IEEE Transactions on Circuits and Systems for Video Technology, vol. 7, no. 4, pp: 702-706, Aug. 1997.
[40] J. H. Luo, C. N. Wang, and T. Chiang, "A novel all-binary motion estimation (ABME) with optimized hardware architectures," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 8, pp: 700-712, Aug. 2002.
[41] Z. L. He, C. Y. Tsui, K. K. Chan, and M. L. Liou, "Low-power VLSI design for motion estimation using adaptive pixel truncation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, no. 5, pp: 669-678, Aug. 2000.
[42] W. Li and E. Salari, "Successive elimination algorithm for motion estimation," IEEE Transations on Image Processing, vol. 4, no. 1, pp: 105-107, Jan. 1995.
[43] Digital Video Coding Group, ITU-T recommendation H.263 software implemen¬tation, Telenor R&D, 1995.
[44] J. N. Kim and T. S. Choi, "A fast full-search motion-estimation algorithm using representative pixels and adaptive matching scan," IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, no. 7, pp: 1040-1048, Oct. 2000.
[45] Y. W. Huang, S. Y. Chien, B. Y. Hsieh, L. G. Chen, ”An efficient and low power architecture design for motion estimation using global elimination algorithm,” in Proceedings of Acoustics, Speech, and Signal Processing, vol. 3, pp: 3120-3123, May 2002,.
[46] K. B. Lee, H. Y. Chin, H. C. Hsu, C. W. Jen, ”QME: an efficient subsampling-based block matching algorithm for motion estimation,” IEEE International Symposium on Circuits and Systems, vol. 2, pp:II -305 – II-308, May 2004
[47] Y. L. Chan, W. C. Siu, ”An adaptive partial distortion search for block motion estimation,” IEEE International Conference on Acoustics, Speech and Signal Processing, vol.3, pp:153-156, April 2003.
[48] C. H. Cheung, 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, Jan. 2003.
[49] S. Y. Kung, VLSI Array Processors, Englewood Cliffs, NJ: Prentice Hall, 1988.
[50] T. Komarek and P. Pirsch, "Array architectures for block matching algorithms," IEEE Transactions on Circuits and Systems, vol. 36, no. 2, pp: 1301-1308, Oct. 1989.
[51] L. D. Vos and M. Stegherr, "Parameterizable VLSI architectures for the full-search block-matching algorithm," IEEE Transactions on Circuits and Systems, vol. 36, no. 2, pp: 1309-1316, Oct. 1989.
[52] K. M. Yang, M. T. Sun, and L. Wu, "A family of VLSI designs for the motion compensation block-matching algorithm," IEEE Transactions on Circuits and Systems, vol. 36, no. 2, pp: 1317-1325, Oct. 1989.
[53] A. Hanami, S. Scotzniovsky, K. Ishihara, T. Matsumura, S. I. Takeuchi, H. Ohkuma, K. Nishigaki, H. Suzuki, M. Kazayama, T. Yoshida, and K. Tsuchi-hashi, "A 165-GOPS motion estimation processor with adaptive dual-array ar¬chitecture for high quality video-encoding applications," in Proceedings of IEEE Custom Integrated Circuits Conference, pp: 169-172, 1998
[54] H. M. Jong, L. G. Chen, and T. D. Chiueh, "Parallel architectures for 3-step hierarchical search block-matching algorithm," IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no. 4, pp: 407-416, Aug. 1994.
[55] S. Dutta and W. Wolf, "A flexible parallel architecture adopted to block-matching motion estimation algorithms," IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 1, pp: 74—86, Feb. 1996.
[56] H. D. Lin, A. Anesko, and B. Petryna, "A 14-GOPS programmable motion es¬timator for H.26X video coding," IEEE Journal of Solid-State Circuits, vol. 31, no. 11, pp: 1742-1750, Nov. 1996.
[57] V. G. Moshnyaga, "A new computationally adaptive formulation of block-matching motion estimation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 11, no. 1, pp: 118-124, Jan. 2001.
[58] S. C. Hsia, "VLSI implementation for low-complexity full-search motion esti¬mation," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 7, pp: 613-619, July 2002.
[59] C. D. Vleeschouwer, T. Nilsson, K. Denolf, and J. Bormans, "Algorithmic and architectural co-design of a motion-estimation engine for low-power video de¬vices," IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, no. 12, pp: 1093-1105, Dec. 2002.
[60] W. M. Chao, C. W. Hsu, Y. C. Chang, and L. G. Chen, "A novel motion esti¬mator supporting diamond search and fast full search," Proceedings of IEEE International Symposium on Circuits and Systems, pp: 492-495, 2002.
[61] S. Y. Yap, J. V. McCanny, “A VLSI architecture for variable block size video motion estimation,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol 51, no. 7, pp: 384 – 389, July 2004.
[62] Y. W. Huang, T. C. Wang, B. Y. Hsieh, L. G. Chen, “Hardware architecture design for variable block size motion estimation in MPEG-4 AVC/JVT/ITU-T H.264,” Proceedings of the International Symposium on Circuits and Systems, vol 2, pp: II-796 - II-799, May 2003.
[63] B. S. Kim, J. D. Cho, “Maximizing memory data reuse for lower power motion estimation,” Proceedings of the 10th Great Lakes Symposium on VLSI, pp.133-138, March 2000.
[64] 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 Transactions on Circuits and Systems for Video Technology, vol. 12, pp: 61-72, Jan. 2002.
[65] P.I.Hosur and K.K.Ma, “Motion Vector Field Adaptive Fast Motion Estimation”, Second International Conference on Information Communications and Signal Processing. Singapore. Dec. 1999.
[66] A. M. Tourapis, O. C. Au, M. L.Liou, “New results on zonal based motion estimation algorithms-advanced predictive diamond zonal search,” International Symposium on Circuits and Systems, vol 5 , pp: 183 -186, 2001
[67] T. Wiegand, M. Lightstone, T. G. Campbell, and S. K. Mitra, "Rate-distortion optimized mode selection forvery low bit rate video coding and the emerging H.263 standard," IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 2, pp: 182.190, Apr. 1996.
[68] H. Malvar, A. Hallapuro, M. Karczewicz, and L. Kerofsky, "Low-complexity transform and quantization in H.264/AVC," IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp: 598-603, July 2003.
[69] D. Marpe, H. Schwarz, and T. Wiegand, "Context based adaptive binary arithmetic coding in the H.264/AVC video coding compression standard," IEEE Transactions on Circuits and Systems for Video Technology, vol. 13, no. 7, pp:620-636, July 2003.
[70] H. Kim and Y. Altunbasak, "Low-Complexity Macroblock Mode Selection for H.264/AVC. Encoders," IEEE International Conference for Image Processing, Oct. 2004.
[71] Yanfei Shen, Dongming Zhang, Chao Huang, Jintao Li, "Fast mode selection based on texture analysis and local motion activity in H.264/JVT," Internation Conefernce on Communications, Circuits and Systems, vol. 1, pp:539 – 542, June 2004.
[72] X. Song, T. Chiang, X. Lee, and Y. Q. Zhang, “New fast binary pyramid motion estimation for MPEG2 and HDTV encoding,” IEEE Transactions on Circuits and Sysems for Video Technology, vol. 10, pp: 1015–1028, Oct. 2000.
[73] J. H. Luo, C. N. Wang, and T. Chiang, "A novel all binary motion estimation (ABME)," IEEE International Symposium on Circuits and Systems, vol. 2, pp:II-480 - II-483. May 2002
[74] "Memory Organization and Its Interface to PEs for Motion Estimation," Jen-Chien Tuan, Master thesis. NCTU
[75] "Algorithm and Architectuer Design for Motion Estimation, H.264/AVC Standard, and Intelligent Video Signal processing" Yu-Wen Huang, Ph.D thesis, NTU.
[76] "Motion Estimation Engine for MPEG-4 Video," Hao-Yun Chin, Master thesis, NCTU.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊