臺灣博碩士論文加值系統

新一代的視訊壓縮標準H.264，由ITU-T Video Coding Experts Group (VCEG)與ISO/IEC Moving Picture Experts Group (MEPG)共同合作制定，這個標準主要目標是設計一個先進且具備高壓縮率而又符合網路應用的視訊編碼標準。餵了能夠達到最好的壓縮效能，新的標準採用更複雜的編碼架構，支援不同區塊大小(16x16~4x4)的移動估測、多張參考畫面的時間預測、四分之ㄧ像素向量精準度、畫面內部預測、去區塊濾波器與整數轉換…等，然而這樣的架構使得編碼器的複雜度大幅提升，尤其是在區塊選擇與移動估測的部份。
本論文中，我們針對了H.264中複雜度較高的移動估測部分，提出了一種快速且有效率的演算法，為了達到更加速的效果，我們在區塊選擇部份，也提出了一種簡單卻快速的演算法。實驗結果顯示，本論文提出的快速區塊選擇與快速移動估測演算法，大幅度的減少所需的屏區搜尋點數，且近似於JM9.3全域搜尋的主觀品質與客觀品質。

H.264 is the video coding standard developed jointly by the ITU-T video coding experts group (VCEG) and the ISO/IEC moving piture experts group (MPEG). The main goals of this standard are to develop advanced video coding design, with enhanced compression performance, and to provide “network-friendly” applications. To achieve the highest coding efficiency, H.264 adopts complicated coding schemes, employing motion compensation with variable blocks sizes from 16×16 to 4×4, multiple reference frames for temporal predicition, quarter-pel motion vector accuracy, intra coding, deblocking filter and integer transform, etc. However, these features incur a considerable increase in encoder complexity, mainly due to mode decision and motion estimation.
In this thesis work, we proposed an algorithm for fast motion estimation and also fast mode decision. In the proposed algorithm, the motion vector of the neighboring blocks are used to reduce the search points on a hexagon-based motion search and early termination is adopted to speed up mode decision. The proposed algorithm has an average 99% point saving over the full search algorithm with only slight accuracy degradation.

致謝辭 II
中文摘要 III
英文摘要 IV
目錄 V
圖目錄 VIII
表目錄 XI
第一章 簡介 1
1.1 國際視訊壓縮標準簡介 1
1.2 動機與目的 2
1.3 論文架構 4
第二章 相關文獻回顧 5
2.1 H.264視訊壓縮標準簡介 5
2.1.1. H.264效能改進情形 6
2.1.2. H.264架構介紹 7
2.1.3. 轉換編碼 8
2.1.4. 量化 9
2.1.5. 空間預測模式 10
2.1.6. 時間預測模式 10
2.1.7. 多幅參考畫面 11
2.2 移動估測 12
2.2.1 可變區塊大小的移動估測 16
2.2.2非整數點的移動估測 17
2.2.3 多幅參考畫面的移動估測 17
2.3 模式選擇 18
2.4 快速移動估測演算法 29
2.4.1 三步搜尋法 29
2.4.2 新三步搜尋法 30
2.4.3 四步搜尋法 31
2.4.4 以區塊為基底下降傾斜搜尋法 31
2.2.5 鑽石搜尋法 32
2.2.6 以六角形為基底搜尋法 33
2.2.7 搜尋區域預測法 34
2.5 快速模式選擇 37
第三章 快速模式決策與移動估測演算法 40
3.1 快速移動估測演算法 40
3.1.1動機 40
3.1.2提出方法一 42
3.1.3實驗數據一 46
3.1.4提出方法二 56
3.1.5實驗結果二 58
3.2 模式選擇 65
3.2.1 影片分析及機率統計 65
3.2.2 提出方法三 71
3.2.3 實驗結果三 81
3.3 模式選擇與快速移動估測演算法之流程說明 89
第四章 實驗結果與數據討論 91
4.1 在固定量化參數QP=10下之實驗結果 91
4.1.1 無加速模式選擇 91
4.1.2 有加速模式選擇 94
4.2 在固定量化參數QP=28下之實驗結果 98
4.2.1 無加速模式選擇 98
4.2.2 有加速模式選擇 100
4.3 在固定量化參數QP=40下之實驗結果 104
4.3.1 無加速模式選擇 104
4.3.2 有加速模式選擇 106
4.4 我們所提出方法之結論與討論 109
第五章 結論與未來展望 117
參考文獻 118

【1】“Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to About 1.5 Mbits/s,” ISO/IEC 1117-2: Video (MPEG-1), November, 1991.
【2】“Generic Coding of Moving Pictures and Associated Audio Information,” ISO/IEC 13818-2: Video (MPEG-2), May 1996.
【3】“Coding of Audio-Visual Objects - Part 2: Visual,” in ISO/IEC 14496-2 (MPEG-4 Visual Version 1), Apr. 1999.
【4】“Video Codec for Audio Visual Services at px64 kbits/s,” ITU-T Recommendation H.261, 1990.
【5】“Video Coding for Low Bit Rate Communication, Version 1,” ITU-T Recommendation H.263, 1995.
【6】“Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification (ITU-T Rec. H.264 | ISO/IEC 144496-10 AVC),” Joint Video Team of ISO/IEC and ITU-T, March 2003.
【7】戴顯權, 多媒體通訊, 紳藍出版社, 5, 2003.
【8】J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer and T. Wedi, “Video Coding with H.264/AVC: tools, Performance, and Complexity,” IEEE on Circuits and Systems, vol. 4, pp. 7-28, 2004.
【9】Iain E.G. Richardson, “H.264 and MPEG-4 Video Compression”, WILEY, 2003
【10】Gary J. Sullivan and Thomas Wiegand, “Rate-Distortion Optimization for Video Compression” IEEE Signal Processing Magazine, vol. 15, pp. 74–90, Nov.1998.
【11】T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion Compensated Interframe Coding for Video Conferencing,” in Proc. NTC 81, pp. C9.6.1-9.6.5, New Orleans, LA, Nov./Dec. 1981.
【12】R. Li, B. Zeng, and M. L. Liou, “A New Three-Step Search Algorithm for Block Motion Estimation,” IEEE Trans. on 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. on Circuits Syst. Video Technol., vol. 6, pp.313- 317, June 1996.
【14】L. K. Liu and E. Feig, “A Block-Based Gradient Descent Search Algorithm for Block Motion Estimation in Video Coding,” IEEE Trans. on Circuits Syst. Video Technol., vol. 6, pp.419-423, Aug. 1996.
【15】S. Zhu and K. -K. Ma, “A New Diamond Search Algorithm for Fast Block Matching Motion Estimation,” IEEE Trans. on Image Processing, vol. 9, pp.287-290, Feb. 2000.
【16】C. Zhu, X. Lin, and L. P. Chau, “Hexagon-Based Search Pattern for Fast Block Motion Estimation,” IEEE Trans. on Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349-355, May 2002.
【17】Kuo-Liang Chung, and Lung-Chun Chang “A New Predictive Search Area Approach for Fast Block Motion Estimation,” IEEE Trans. on Image Processing, vol. 12, no. 6, pp.648-652. June 2003.
【18】D.Wu, S. Wu, K.P. Lim, F. Pan, Z.G. Li and X. Lin, “Block Inter Mode Decision for Fast Encoding of H.264,” IEEE international conference on Acoustics, Speech, and Signal Processing, vol. 3, pp.181-184, May 2004.
【19】D.Wu, S. Wu, K.P. Lim, F. Pan, Z.G. Li and C.C. Ko, “Fast Inter Mode Decision with Adaptive Thresholds for H.264 Encoding,” IEEE International Symposium on Consumer Electronics, pp. 406-409, September 2004.
【20】F. Pan, L.S. Rahardja, K.P. Lim, L.D. Wu, W.S. Wu, C. Zhu, W. Ye, and Z.Liang, “Fast Intra Mode Decision Algorithm for H.264-AVC Video Coding,” IEEE International Conference on Image Processing, vol. 2, pp.781-784, October 2004.
【21】X. Jing and L.-P. Chau, “Fast Approach for H.264 Inter Mode Decision,” Electronics Letters, vol. 40, pp. 1050-1052, Aug. 2004.
【22】X. Jing and L.-P. Chau, “An Efficient Inter Mode Decision Approach for H.264 Video Coding,” IEEE International Conference Multimedia and Expo, vol.2, pp. 1111-1114, June 2004.
【23】Y. Shen, D. Zhang, C. Huang and J. Li, “Fast Mode Selection Based on Texture Analysis and Local Motion Activity in H.264/JVT,” IEEE International Conference on Communication, Circuits and Systems, vol. 1, pp.539-542, June 2004.
【24】A.C. Yu and G.R. Martin, “Advanced Block Size Selection Algorithm for Inter Frame Coding in H.264/MPEG-4 AVC,” IEEE International Conference on Image Processing, vol. 1, pp.95-98, Oct. 2004.
【25】A.C. Yu, “Efficient Block-Size Selection Algorithm for Inter-Frame Coding in H.264/MPEG-4 AVC,” IEEE International Conference on Acoustics Speech, and Signal Processing, vol. 3, pp. 169-172, May 2004.
【26】Y.-H. Kim, J.-W. Yoo, S.-W. Lee, J.Shin, J. Paik and H.-K. Jung, “Adaptive Mode Decision for H.264 Encoder,” Electronics Letters, vol. 40, pp. 1172-1173, September 2004.
【27】Y.-H. Kim, J.-W. Yoo, S.-W. Lee, J. Paik and B. Choi, “Optimization of H.264 Encoder Using Adaptive Mode Decision and SIMD Instructions,” IEEE International Conference on Consumer Electronics, pp. 289-290, Jan. 2005.
【28】M. Yang and W. Wang, “Fast Macroblock Mode Selection Based on Motion Content Classification in H.264/AVC,” IEEE International Conference on Image Processing, vol. 2, pp. 741-744, Oct. 2004.
【29】A. Ahmad, N. Khan, S. Masud, and M.A. Maud, “Selection of Variable Block Sizes in H.264,” IEEE International Conference on Acoustics Speech, and Signal Processing, vol. 3, pp.173-176 May 2004.
【30】A. Ahmad, N. Khan, S. Masud, and M.A. Maud, “Efficient Block Size Selection in H.264 Video Coding Standard,” Electronics Letters, vol. 40, pp.19-21, Jan. 2004.
【31】N. Khan, S. Masud, and M.A. Maud, “Efficient Scheme for Motion Estimation and Block Size Mode Selection in H.264,”IEEE International Symposium on Communication and Information Technology, vol. 2 pp. 747-751, Oct. 2004.
【32】Q. Dai, D. Zhu and R. Ding, “Fast Mode Decision for Inter Prediction in H.264,” IEEE International Conference on Image Processing, vol. 1, pp. 119-122, Oct. 2004.
【33】C.H. Kuo, M.S. and C.-C.J. Kuo, “Fast Inter-Prediction Mode Decision and Motion Search for H.264,” IEEE International Conference Multimedia and Expo, vol. 1, pp. 663-666, 2004.
【34】A. Chang, P.H.W. Wong, Y.M. Yeung, and O.C. Au, “Fast Multi-Block Selection for H.264 Video Coding,” IEEE International Symposium on Circuits and Systems, vol. 3, pp. 817-820, May 2004.
【35】J. Lee and B. Jeon, “Fast Mode Decision for H.264,” IEEE International Conference Multimedia and Expo, vol. 2, pp. 1131-1134, June 2004.
【36】I. Choi, J. Lee and B. Jeon, “Efficient Coding Mode Decision in MPEG-4 Part-10 AVC/H.264 Main Profile,” IEEE International Conference on Image Processing, vol. 2, pp. 1141-1144, Oct. 2004.
【37】L. Yang, K. Yu, J. Li, and S. Li, “An Effective Variable Block-Size Early Termination Algorithm for H.264 Video Coding,” IEEE Tran. on Circuits and Syst. for Video Technol., vol. 15, pp. 784-788, June 2005.
【38】K-H. Han and Y.-L. Lee, “Fast Macroblock Mode Decision in H.264,” IEEE Region 10 Conference, vol. A, pp, 347-350, Nov. 2004.
【39】A. M. Tourapis, O. C. Au, and M. L. Liou, “Predictive Motion Vector Field Adaptive Search Technique (PMVFAST) Enhancing Block-Based Motion Estimation,” in Proc. SPIE Conf. Visual Communication and Image Processing, Jan. 2001, pp. 883–892.
【40】He Li, Z. G. Li, and Changyun Wen, “Fast Mode Decision Algorithm for Inter-Frame Coding in Fully Scalable Video Coding,” IEEE Tran. on Circuits and Syst. for Video Technol., Vol. 16, pp. 889-895, July 2006
【41】Chu-Yu Chang, Chia-Ho Pan,and Homer Chen, “Fast Mode Decision For P-Frame In H.264,” Picture Coding Symposium, San Francisco, Dec. 2004
【42】Zhibo Chen, Peng Zhou, Yun He, “Fast Integer Pel and Fractional Pel Motion Estimation for JVT,” JVT-F017.doc, 6th Meeting: Awaji, Island, JP, 5-13 December, 2002.
【43】Zhibo Chen, Peng Zhou, Yun He, “Fast Motion Estimation for JVT,” JVT-G016.doc, 7th Meeting: Pattaya ll, Thailand, 7-14 March, 2002.