臺灣博碩士論文加值系統

H.264/AVC為JVT所制定視訊編碼標準，具有很好的視訊編碼效率，近年來，隨著網路頻寬提升以及科技的進步，多媒體影音的產品及服務不斷推陳出新，如視訊電話、隨選視訊系統(VOD)、視訊會議、高畫質數位電視(HDTV)等等，都是需要一個良好的視訊壓縮標準的支持，在H.264/AVC編碼架構中，運動估計(Motion Estimation)則是在整個視訊壓縮中佔最大的計算量，因此本文將針對減少運動估計演算法中的搜尋像素點數量，及維持一定的視訊影像品質來進行視訊編碼研究。
本論文分析多種快速運動估計演算法，其中以部分失真搜尋(Normalized Partial Distortion Search ; NPDS) 演算法編碼效能較為顯著，NPDS在區塊匹配搜尋像素點的排列順序與搜尋視窗範圍都是固定的，無法依據各視訊畫面的特性去排列搜尋順序，因此本研究提出結合動態搜尋範圍之部分失真搜尋視訊編碼快速運動估計演算法，此方法可依據各種視訊畫面的特性進行視訊編碼，不同的視訊畫面給予不同的像素計算排列方式，再依據畫面特性的變化與相鄰區塊的運動向量去調整搜尋視窗的分布範圍。本研究可有效率地減少視訊編碼搜尋像素點數量，且維持一定的視訊品質。

H.264/AVC is JVT video coding standard developed by a good video coding efficiency, in recent years, with the network bandwidth improvements, and advances in technology, multimedia products and services continued to emerge, such as video telephone, on-demand video system (VOD), video conferencing, high-definition digital television (HDTV), etc.. All need a good video compression standards support in the H.264/AVC encoder architecture. Motion estimated (ME) is the compression of the entire video, accounted for the largest amount of computation, this thesis has proposed a new motion estimation algorithm to reduce number of search points in motion estimation algorithm maintaining a certain visual quality. This study has by analyzed a variety of fast motion estimation algorithms. Normalized Partial Distortion Search(N PDS) algorithm is one of algorithm with better coding performance. However, NPDS in the block matching search points of order and arrangement are fixed, can not be the basis of each depending characteristics of the information screen to arrange the search order, this study proposes to combine dynamic search partial distortion search video coding fast motion estimation algorithm. This method is based on various video picture characteristics of video encoding, video screen different pixels to calculate the arrangement, based on changes in the characteristics of the screen and motion vectors of adjacent blocks to adjust the distribution range of the search window. Compare to the proposed algorithm. Experimental results show that this study can efficiently reduce video encoding of search points, and to maintain a certain video quality.

第一章 緒論 1
1.1研究背景 1
1.2研究動機 3
1.3論文架構 4
第二章H.264/AVC視訊編碼標準 5
2.1 H.264/AVC視訊編碼架構 5
2.2 Inter-frame編碼技術 6
2.3Intra-frame編碼技術 8
2.4 整數離散餘弦轉換(DCT)及殘餘量化 9
2.5 Rate-Distortion Cost 11
2.6運動估計演算法之複雜度探討 13
第三章 應用於H.264/AVC快速運動估計演算法探討 15
3.1快速運動估計演算法介紹 17
3.1.1 全域搜尋演算法(Full Search Algorithm) 17
3.1.3 半途終止之快速運動估計搜尋演算法(Halfway-stop search algorithm) 19
3.2快速運動匹配估計演算法之介紹 31
3.2.1無失真快速運動區塊匹配估計演算法 32
3.2.2部分失真快速運動區塊匹配估計演算法(Partial Distortion Search) 34
3.3動態搜尋範圍演算法之探討(Dynamic Search Range) 37
3.4初始運動向量預測(Predict Motion Vector) 38
第四章 研究方法 40
4.1新的像素計算排列方式 40
4.2預測初始搜尋位置 42
4.3動態搜尋範圍(Dynamic Search Range) 44
4.4結合動態搜尋範圍之部分失真搜尋視訊編碼快速運動估計演算法(Combining Dynamic Search Range with Improved Normalized Partial Distortion Search for Fast Motion Estimation Algorithm in Video Coding) 47
第五章 實驗結果與討論 49
第六章 結論 60
參考文獻 61

參考文獻
[1]Information Technology-Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1.5 Mbit/s-Part 2:Video, ISO/IEC 111722-2(MPEG Video), 1993.
[2]Information Technology-Generic Coding of Moving Pictures and Associated Audio Information: Video, ISOIEC 13818-2 (MPEG-2 Video)/ITU-T H.262, 1996.
[3]Atul Puria, Xuemin Chenb, Ajay Luthrac, "Video coding using the H.264/MPEG-4 AVC compression standard", Signal Processing: Image Communication SP:IC(19), No. 9, October 2004, pp. 793-849.
[4]Video codec for audiovisual services at pX 64 kbit/s, ITU-T recommendation H.261 Version 3, Mar. 1993.
[5]Video coding for low bitrate communication, draft itu-t recommendation H.263, May 1996.
[6]G. J. Sullivan, P. Topiwala, and A. Luthra, "The H.264/AVC Advanced VideoCoding Standard: Overview and Introduction to the Fidelity Range tensions,"SPIE Conference on Applications of Digital Image Processing, vol. 5558,pp.53-74, Aug. 2004.
[7]"Information technology－Coding of audio-visual objects. Part 10: Advancedvideo coding, final draft international standard," ISO/IEC 14496-10, Dec. 2003.
[8]D. Marpe, T. Wiegand, and S. Gordon, "H.264/MPEG4-AVC Fidelity Range Extensions: Tools, Profiles, Performance, and Application Areas, "ICIP 2005. IEEE International Conference", vol. 1, pp. I-593-6, Sept 2005.
[9]B. Jeon, and J. Lee, "Fast mode decision for H.264, "ITU-T Q.6/16, Doc. #JVT-J033," 2003.
[10]Y. Huang, B. Hsieh, S. Chien, S. Ma, and L. Chen, "Analysis and complexity reduction of multiple reference frames motion estimation H.264/AVC," IEEE Trans. Circuits Syst. Video Technol., vol. 16, no. 4, pp. 507–522, Apr. 2006.
[11]T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, "Motion-com-pensated interframe coding for video conferencing," in Proc. NTC81 Nov. 1981, pp. G5.3.1-G5.3.5.
[12]R. Li, B. Zeng, and M. L. Liou, "A new three-step search algorithm for block motion estimation," IEEE Trans. Circuits. Syst. Video Technol., vol. 4, pp. 438-442, Aug. 1994.
[13]L. M. Po and W. C. Ma, "A novel four-step search algorithm for fast block motion estimation," IEEE Trans. Circuits Syst. Video Technol., vol.6, pp. 313-317, June 1996.
[14]C. Zhu, X. Lin, and L. P. Chau, "Hexagon-based search pattern for fast blockmotion estimation," IEEE Trans. Circuits Syst. Video Technol., vol. 12, pp.349-355, May 2002.
[15]C.-K. Cheung and L.-M. Po, "Normalized partial distortion search algorithm for block motion estimation," IEEE Trans. Circuits. syst. video technol., vol. 10, no. 3, pp.417-422, Apr. 2000.
[16]W. Li and E. Salari, "Successive elimination algorithm for motion estimation," IEEE Trans. Image Process., vol. 4, no. 1, pp. 105-107, Jan. 1995.
[17]C. D. Bei and R.M. Gray, "An improvement of the minimum distortion encoding algorithm for vector quantization," IEEE Trans. Commun., vol. COM-33, pp. 1132-1133, Oct. 1985
[18]S. Y. Chien ,Y. W. Huang, C. Y. Chen, H. H. Chen and L. G.. Chen, "Hardware architecture design of video compression for multimedia communication systems,” IEEE Communications Magazine, pp.122-131, Aug. 2005.
[19]J. M. Moon, Y. H. Moon, and J. H. Kim, "A computation reduction method for RDO mode decision based on an approximation of the distortion,” in IEEE International Conference on Image Processing (ICIP), Oct. 2006, pp. 2481–2484.
[20]Hu, T. Zhao, H. Wang, S. Kwong, "Fast inter-mode decision based on rate-distortion cost characteristics,” Proceeding PCM''10 Proceedings of the Advances in multimedia information processing, and 11th Pacific Rim conference on Multimedia: Part II, Shanghai, China, September 21-24, 2010.
[21]J. Bu, S. Lou, C. Chen, and J. Zhu, "A predictive block-size mode selection for inter frame in H.264,” in IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP),May 2006, vol. 2, pp. 917–920.
[22]I. Choi, J. Lee, and B. Jeon, "Fast coding mode selection with rate-distortion optimization for MPEG-4 part-10 AVC/H.264,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 12, pp. 1557–1561, Dec. 2006.
[23]C. S. Kannangara, I. E. G. Richardson, M. Bystrom, J. Solera, Y. Zhao, A. Maclennan, and R. Cooney, "Low complexity skip prediction for H.264 through Lagrangian cost estimation,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 2, pp. 202–208, Feb. 2006.
[24]Y. M. Lee and Y. Lin, "Zero-block mode decision algorithm for H.264/AVC,” IEEE Transactions on Image Processing, vol. 18, pp. 524-533, March 2009.
[25]Yu-Ming Lee, Yin-Yi Lin, "A Fast Inter-mode Mode Decision for H.264 Video Coding,” Signal Processing, The 8th International Conference on, Volume 2, 2006.
[26]Grecos, C., Yang, M., "Fast Mode Prediction for the Baseline and Main Profiles in the H.264 Video Coding Standard,” IEEE Transactions on Multimedia, Volume 8, Issue 6, Dec. 2006.
[27]K.-H. Han, Y.-L. Lee, "Fast macroblock mode decision in H.264,” TENCON 2004. 2004 IEEE Region 10 Conference, Volume A, 21-24 Nov. 2004.
[28]C.-L. Hsu, M.-H. Ho, M.-K. Liu, "High-Efficient Mode-Decision Design for Motion Estimation in H.264," ICCE 2007. Digest of Technical Papers. International Conference on Consumer Electronics, Jan. 2007.
[29]B. Feng, G.-X. Zhu, W.-Y. Liu, "Complexity scalable inter modes decision algorithm for H.264 based on spatial correlation," ICACT 2006. The 8th International Conference Advanced Communication Technology, vol. 2, 20-22 Feb. 2006.
[30]Y. Jo, Y.-G. Kim, Y. Choi, "Fast Mode Decision Algorithm Using Optimal Mode Predictions for H.264-based Mobile Devices,” ICCE 2007. Digest of Technical Papers. International Conference on Consumer Electronic, Jan. 2007.
[31]Z. Wei, K. N.i Ngan, "A Fast Rate-Distortion Optimization Algorithm for H.264/AVC", ICASSP 2007. IEEE International Conference on Acoustics, Speech and Signal Processing vol. 1, 15-20 April 2007 Page(s):I-1157 - I-1160.
[32]Z. Liu, L. Shen, Z. Zhang, "An Efficient Inter mode Decision Algorithm Based on Motion Homogeneity for H.264/AVC", IEEE Transactions on Circuits and Systems for Video Technology, vol. 19, Issue 1, Jan. 2009 Page(s):128 – 132.
[33]A. C. Yu, N. K. Ngi, "Graham R. Martin. Efficient intra- and inter-mode selection algorithms for H.264/ AVC, " Journal of visual communication &; image representation, 17 (2006) 322–344.
[34]Z. Zhou, J. Xin, M.-T. Sun, "Fast motion estimation and Inter-mode decision for H.264/MPEG-4 AVC encoding, " Journal of visual communication &; image representation, 17 (2006) 243–263.
[35]H. Zeng, C. Cai, K.-K. Ma, "A Novel Fast Mode Decision for the H.264/AVC Based on Local Macroblock Motion Activity, " The Fourth International Conference on Image and Graphics, Chengdu, China, August 2007.
[36]J. Liu; C. Cai; "Fast inter-frame mode decision for H.264 using Bayesian model and motion status, "3rd International Symposium on Communications, Control and Signal Processing, 2008(ISCCSP 2008), pp. 629 – 633, 12-14 March 2008.
[37]H. Zeng, C. Cai, and K.-K. Ma, "Fast mode decision for H.264/AVC based on macroblock motion activity,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, no. 4, pp. 491–499, Apr. 2009.
[38]D. Wu, F. Pan, K. P. Lim, S. Wu, Z. G. Li, X. Lin, S. Rahardja, and C. C. Ko, "Fast Intermode Decision in H.264/AVC Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 15, Issue 7, July 2005.
[39]X. Jing, L.-P. Chau, "An efficient inter mode decision approach for H.264 video coding,” IEEE International Conference on Multimedia and Expo ICME ''04. 2004, Vol. 2, 27-30 June 2004.
[40]H. Wang and X. Zhou, "Adaptive motion estimation and mode decision strategy for H.264 encoder,” Proceedings of the 6th World Congress on Intelligent Control and Automation, June 2006.
[41]Z. Chen, Y. Song, T. Ikenaga and S. Goto, " Adaptive Search Range Algorithms for Variable Block Size Motion Estimation in H.264/AVC," IEICE Trans. Fundamentals vol. E91-a, No. 4, April 2008, pp 1015-122.
[42]Z. Chen, Q. Liu, T. Ikenaga, S. Goto, " A motion vector difference based self-incremental adaptive search range algorithm for variable block size motion estimation", ICIP08, 2008, pp1988-1991.
[43]M. G. Sarwer, and Q. M. Jonathan Wu "An efficient search range decision algorithm for motion estimation in H.264/AVC" International journal of circuits, systems and signal processing, Issue 4, Volume 3, pp.173-180, 2009.
[44]C.-C. Yang, G.-L. Li, M.-C. Chi, M.-J. Chen, and C.-H. Yeh "Prediction Error Prioritizing Strategy for fast normalized partial distortion motion estimation algorithm” IEEE Transactions on circuits and systems for video technology, vol. 20, no. 8, August 2010.
[45]S. LEE "Fast motion estimation based on search range adjustment and matching point decimation" IET Image Process., Vol. 4, Issue. 1, pp. 1-10, 2010
[46]Z. Chen, et al., "A Hardware/Software Co-solution to Achieving High Throughput Required by Motion Estimation Part in H.264/AVC HDTV Realtime Application”, Proc. of IEEE International Symposium on VLSI Design, Automation and test (VLSI-DAT), Apr. 2008.
[47]X. Yi and N. Ling, "Improved normalized partial distortion search with dual-halfway-stop for rapid block motion estimation," IEEE Trans. Multimedia, vol. 9, no.5 pp. 995-1003, Aug. 2007.
[48]S. LEE "Fast motion estimation based on search range adjustment and matching point decimation" IET Image Process., Vol. 4, Issue. 1, pp. 1-10, 2010
[49]Y.-H. Ko, H.-S. Kang and S.-W. Lee, "Adaptive Search Range Motion Estimation Using Neighboring Motion Vector Differences," IEEE Trans. Consumer Electronics, vol. 57, no. 2, pp. 726-730 May 2011.
[50]S.-H. Ri, Y. Vatis and J. Ostermann, "Fast Inter-Mode decision in an H.264/AVC Encoder using mode and larangian cost correlation," IEEE Trans. circuits and systems for video technology, vol. 19, no. 2, Feb. 2009.