臺灣博碩士論文加值系統

H.264/AVC 具有非常高的編碼效率，主要因素為進行畫面間預
測編碼時，H.264 使用了七種不同的區塊大小來進行移動補償
(Motion Compensation)，同時又可參考多幅畫面，因此其編碼過程中
之計算複雜度較以往的視訊編碼標準高出數倍，故近年來有許多的研
究致力於發展H.264 快速演算法。
由於硬體對外部記憶體之存取頻寬有限，由參考文獻中可知，若
採用階層式取樣架構，並將硬體可平行處理的特性加入考慮，即可有
效降低處理高解析視訊所需之頻寬，如何在此架構及條件下兼顧畫面
品質以及位元率來加速演算法為本研究之主要目標。
本論文提出一套可在資源有限之硬體上壓縮高解析視訊畫面的
階層式H.264 移動估測快速演算法，在空間域上利用階層式的搜尋方
式減少搜尋點數，於時間域上利用線性移動動量模型(Linear Motion
Model)的假設以減少搜尋範圍，同時在空間域及時間域上進行加速，
實驗結果顯示，整體運算複雜度最低可達到原始JM 12.4 的1.80%，
且只犧牲了0.10dB 的視訊品質。

H.264 advanced video coding exhibits much higher coding gain as
well as computational complexity than previous video coding standards
due to the utilization of coding tools such as variable block size and
multi-reference frame in motion compensation process. There exist plenty
of research outcomes that focus on the development of H.264 fast
algorithms.
The limited bandwidth during the access between hardware
components and the external memory often becomes the bottleneck of the
system performance. One of the solutions of encoding the high-definition
video in hardware with limited resources is to employ a hierarchical
subsampling structure with the parallel-processing hardware architecture.
The main objective of this work is to maintain both the video quality and
bit-rate while pursuing the gain from computational complexity
reduction.
This thesis proposes a hierarchical H.264 fast motion estimation
algorithm by decreasing the coding complexity in both spatial and
temporal domains. In spatial domain, we utilize the hierarchical search
method to decrease the search points. In temporal domain, we utilize the
linear motion model to reduce the search range. The simulation results
show that the proposed algorithm can reduce the computational
complexity to as low as 1.80% compared to JM12.4 with less than
0.10dB video quality degradation.

摘 要 I
Abstract II
目 錄 III
附圖索引 V
附表索引 VIII
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 論文架構 4
第二章 H.264快速演算法發展現況與簡介 5
2.1 H.264視訊壓縮標準簡介 5
2.1.1 H.264架構介紹 7
2.1.2 網路提取層 8
2.1.3 視訊編碼層 9
2.2 H.264編碼複雜度分析 13
2.3 移動估測快速演算法之發展現況 15
2.4 硬體實作考量 18
第三章 適於硬體實現之快速演算法 21
3.1 Uhl’s Algorithm [13] 21
3.2 Altunbasak’s Algorithm [14] 23
3.3 Chen’s Algorithm [16] 25
3.3.1 可根據視訊內容調整複雜度之快速演算法 26
3.3.2 硬體架構 29
3.4 Chang’s Algorithm [20] 30
3.4.1 可平行處理之多層解析度移動估測(PMRME) 31
3.4.2 單次疊代之分數點移動估測(SIFME) 33
3.4.3 區塊模式篩選(Mode Filtering) 35
3.4.4 硬體架構 36
第四章 時空階層式移動估測快速演算法 39
4.1 空間階層式移動估測演算法(SHME) 39
4.1.1 三層空間階層式移動估測演算法(SHME-3L) 39
4.1.2 二層空間階層式移動估測演算法(SHME-2L) 43
4.2 時空階層式移動估測演算法(STHME) 47
4.2.1 三層時空階層式移動估測演算法(STHME-3L) 47
4.2.2 二層空間階層式移動估測演算法(STHME-2L) 56
第五章 實驗結果與討論 59
5.1 實驗參數環境 59
5.2 空間域上的加速 64
5.3 時間域與空間域上的加速 75
第六章 結論 87
參考文獻 88

[1]Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification, ITU-T Rec. H.264/ ISO/ IEC 14496-10 AVC, Mar. 2003.
[2]Yeping Su and Ming-Ting Sun, “Fast MultipleReference Frame Motion Eestimation for H.264,” 2004 IEEE International Conference on Multimedia and Expo, (ICME ''04), Vol. 1, pp. 695- 698, June 2004.
[3]Xiang Li, E.Q. Li and Yen-Kuang Chen, “Fast Multi-frame motion Estimation Algorithm with Adaptive Search Strategies in H.264,” IEEE International Conference Acoustics, Speech, and Signal Processing (ICASSP ''04), Vol. 3, pp. iii- 369-72, May 2004.
[4]Yu-Jen Wang, Chao-Chung Cheng, and Tian-Sheuan Chang, “A Fast Algorithm and Its VLSI Architecture for Fractional Motion Estimation for H.264/MPEG-4 AVC Video Coding,” IEEE Transactions on Circuits and Systems for Video Technology, VOL. 17, NO. 5, May 2007.
[5]Shu-Fa Lin, Che-Yu Chang, Che-Chun Su, Yi-Lun Lin, Chia-Ho Pan, and H. Chen, “Fast Multi-Frame Motion Estimation and Mode Decision for H.264 Encoders,” 2005 International Conference on Wireless Networks, Communications and Mobile Computing, Vol. 2, pp. 1237 – 1242, June 2005.
[6]Sheng-Kai Lin, Sung-Wen Wang, Shu-Sian Yang, Yi-Shin Tung, and Ja-Ling Wu, “Motion Transitive Based Fast Multi-Frame Motion Estimation Algorithm For MPEG-4 AVC/H.264,” International Conference on Consumer Electronics (ICCE ’07) Digest of Technical Papers., pp.1 - 2, Jan. 2007.
[7]Gwo-Long Li and Mei-Juan Chen, “Fast Motion Estimation Algorithm by Finite-State Side Match for H.264 Video Coding Standard,” IEEE Asia Pacific Conference on Circuits and Systems (APCCAS ‘06), pp.414 – 417, 4-7 Dec. 2006.
[8]Changsung Kim, Hsuan-Huei Shih, and C.-C. Jay Kuo, “Feature-Based Intra-Prediction Mode Decision for H.264,” International Conference on image Processing (ICIP), 2004.
[9]Chuan-Yu Cho, Sheng-Kai Chang, and Jia-Shung Wang, “A Multiframe Motion Estimation Architecture for H.264/AVC,” International Conference on image Processing (ICIP), 2006.
[10]徐意瑄,“H.264快速橫向線型移動預估實現於Equator數位訊號處理器,” 國立中央大學通訊工程研究所碩士論文, 中華民國九十三年七月.
[11]Yi-Hung Hsiao, Tien-Hsu Lee, and Pao-Chi Chang, "Short/Long-Term Motion Vector Prediction in Multi-Frame Video Coding System," in Proceedings of IEEE International Conference on Image Processing, pp.1449-1452, Singapore, Oct. 2004.
[12]Mahdi Nazm Bojnordi, Mehdi Semsarzadeh, Mahmoud Reza Hashemi, and Omid Fatemi, “Efficient Hardware Implementation for H.264/AVC Motion Estimation,” IEEE Asia Pacific Conference on Circuit and System (APCCAS), Dec. 2006.
[13]Ch. Hufnagl and A. Uhl, “Fast Block-Matching Algorithms for High-Resolution Video Compression,” In Proceedings of the International Picture Coding Symposium (PCS’99), pages 295–298, Portland, Oregon USA, Apr. 1999.
[14]Hasan F. Ates and Yucel Altunbasak, “SAD Reuse in Hierarchical Motion Estimation for the H.264 Encoder,” IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Volume 2, pp. ii/905 - ii/908, 18-23 March 2005.
[15]Sinan Yalcin, Hasan F. Ates, and Ilker Hamzaoglu, ”A High Performance Hardware Architecture for an SAD Reuse Based Hierarchical Motion Estimation Algorithm for H.264 Video Coding,” International Conference on Field Programmable Logic and Applications (FPL), pp. 509-514, 24-26 Aug. 2005.
[16]Yu-Han Chen, Tung-Chien Chen, and Liang-Gee Chen, “Hardware Oriented Content-Adaptive Fast Algorithm for Variable Block-Size Integer Motion Estimation in H.264,” Proceedings of 2005 International Symposium on Intelligent Signal Processing and Communication Systems, Dec. 2005.
[17]Tung-Chien Chen, Yu-Han Chen, Sung-Fang Tsai, Shao-Yi Chien, and Liang-Gee Chen, “Fast Algorithm and Architecture Design of Low-Power Integer Motion Estimation for H.264AVC,” IEEE Transactions on Circuits and Systems for Video Technology, VOL. 17, NO. 5, May 2007.
[18]Lai-Man Po and Wing-Chung Ma, “A Novel Four-Step Search Algorithm for Fast Block Motion Estimation,” IEEE Transactions on Circuits and Systems for Video Technology, VOL. 6, NO. 3, June 1996.
[19]Chia-Chun Lin, Yu-Kun Lin, and Tian-Sheuan Chang, ”PMRME: A Parallel Multi-Resolution Motion Estimation Algorithm and Architecture for HDTV Sized H.264 Video Coding,” IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Volume 2, pp.II/385 – II/388, 15-20 April 2007.
[20]Yu-Kun Lin, Chia-Chun Lin, Tzu-Yun Kuo, and Tian-Sheuan Chang, “A Hardware Efficient H.264/AVC Motion Estimation Design for High Definition Video,” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. (Accepted for future publication, revised in Sep. 2007)
[21]JM 12.4. Reference Software of JVT.
[22]盧慶儒, “零件採購－MPEG4與H.264擁抱HDTV時代來臨,” DigiTimes, April 2006. http://tech.digitimes.com.tw/print.aspx?zNotesDocId=EF9FC195DA1E88C24825714100421F6D
[23]郭其昌, “H.264先進視訊編解碼標準,” 數位視訊月刊, http://www.tvro.com.tw/main5/maimtxt/H.264%E5%A0%B1%E5%B0%8E%EF%BC%8D%E5%B7%A5%E7%A0%94%E9%99%A2.htm