臺灣博碩士論文加值系統

近年來，由於網際網路蓬勃發展，使得視訊多媒體逐年進步，其中利用視訊壓縮編碼技術，達到高畫質、低容量的視訊技術，在網路多媒體上已漸普及。現今視訊壓縮H.264 的技術開發上，動態估測(motion estimation)一直是視訊編碼壓縮較關鍵的角色。動態估測通常用於區塊比對(block matching)演算法來判斷移動向量(motion vector)，預測在視訊影像裡相鄰兩影像中同一物體的位移量，以達到動態補償和視訊壓縮的效果。在本篇論文裡，我們提出一個新的動態估測演算法，藉由應用ARPS(Adaptive Rood Pattern Search)、CS(Cross Search)、OctaS(Octagon Search)、PS(Prediction Search)4種演算法組成一種多邊形向量的預測搜尋法，與其他演算法：三步、新三步、鑽石、預測...等，並進一步以PSNR 測試其方法，以達到良好的壓縮效果。

Motion estimation has been the most key role on video encoding. It is usually applied to block matching algorithm for choosing the best motion vector. The two adjacent images are searched to find the displacement of the same object in the video image. Many fast motion vector block matching algorithms are proposed, and they achieve the efficiency of motion compensation and video compression. In our paper, Adaptive Polygon Predictive Search Algorithm (APPS) that based on ARPS、CS、OctaS and PS is proposed. The experimental results show that the PSNR of the proposed method is better than that of other block matching methods on all kinds of video.

致謝 I
摘要 II
Abstract III
目錄 IV
圖目錄 VI
表目錄 VIII
第一章緒論 1
1.1 研究背景 1
1.2 MPEG-4 視訊編碼壓縮技術簡介 2
1.3 H.264 視訊壓縮編碼簡介 3
1.4 動態估測 4
1.4.1 比對方法 6
1.4.2 全域演算法 6
1.5 動態補償 7
第二章快速搜尋演算法探討 8
2.1 三步搜尋演算法(Three Step Search, TSS) 8
2.2 交錯搜尋演算法(Cross Search, CS) 9
2.3 新三步搜尋演算法(New Three Step Search, NTSS) 11
2.4 簡易效能搜尋演算法(Simple and Efficient Search, SES) 13
2.5 四步搜尋演算法(Four Step Search, FSS or 4SS) 15
2.6 鑽石(菱形)搜尋演算法(Diamond Search, DS) 17
2.7 六角搜尋演算法(Hexagon Search, HexaS) 19
2.8 八角搜尋演算法(Octagon Search, OctaS) 20
2.9 適應性十字搜尋演算法(Adaptive Rood Pattern Search, ARPS) 22
第三章適應性多邊形預測搜尋演算法 24
3.1 交錯模組 24
3.2 扁平模組 25
3.3 十字扁平模組 28
3.4 4N 多邊形模組 30
3.5 4N 多邊形預測模組 32
第四章應用多層次模組搜尋 40
4.1 最小3 層4NP 搜尋法(Minimun Triplex 4NP Search, MinT4NPS) 40
4.2 多層次4NP 搜尋法(Multilevel 4NP Search, Multi4NPS) 41
4.3 多層次鑽石八角搜尋法(Multilevel Dimond-Octagon Search, MultiDOS) 42
第五章實驗結果 43
5.1 驗測試與方法 43
5.2 數據結果 46
5.2.1 各搜尋法search point 46
5.2.2 各搜尋法psnr 48
5.3 數據統計 50
第六章結論與未來展望 51
參考文獻 52

[1] 陸錦正,”MPEG-4/H.264 視頻編解碼工程實踐”, pp.2–20,Aug, 2008
[2] 彭信元、陳昭榮,”MPEG-4 視訊壓縮技術”, pp.2-1–2-11,Mar,2006
[3] “Advanced video coding for generic audio visual services” (ITU-TRec. H.264|ISO/IEC 201201-S AVC),Joint Video Team of ISO/IE Cand ITU-T, Jan, 2012
[4] Aroh Barjatya,“ Block Matching Algorithms For Motion Estimation”Final project paper, DIP, at Utah state university, spring,2004
[5] 劉原禎, “A modified double layered search pattern algorithm for motion estimation”, Master thesis of National PingTung Institute of Commerce, Taiwan, Jul, 2012
[6] 傅敬惟, “Fast Hexagon Search Algorithm”, Master thesis of National PingTung Institute of Commerce, Taiwan, Jun,2009
[7] O. A. Ojo and G. de Haan, “Robust motion compensated video upcon version,” IEEE Trans. Consumer Electronics, vol. 43, no. 4, pp.1045–1056, Nov, 1997
[8] T. Koga, K. Linuma, A. Hirano, Y. Iijima and T.Ishiguro, “Motion-compensated inter frame coding for video conferencing,” Proceedings of NTC'81, pp.G5.3.1-G5.3.5, New Orleans, LA, Dec, 1981
[9] M. Ghanbari, “ The Cross-Search Algorithm for Motion Estimation”, IEEE Trans. On Communications, vol. COM-38, no. 7, pp.950-953, Jul, 1990
[10] Renxiang Li, Bing Zeng, and Ming L. Liou, “A New Three-Step Search Algorithm for Block Motion Estimation”, IEEE Trans. Circuits And Systems For Video Technology, vol.4, no. 4, pp.438-442, Aug, 1994
[11] Jianhua Lu, Ming L.Liou,”A Simple and Efficent Search Algorithm for Block Matching Motion Estimation”, IEEE Trans. Circuits And Systems For Video Technology, vol 7, no.2, pp.429-433, Apr, 1997
[12] 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, Jun, 1996
[13] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “A novel unrestricted center-biased diamond search algorithm for block motion estimation”, IEEE Trans, Circuits Syst. Video Technol., vol. 8, no. 4, pp.369-377, Aug, 1998
[14] Ce Zhu, Xiao Lin, and Lap-Pui Chau, “ Hexagon-Based Search Pattern for Fast Block Motion Estimation” IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 12, NO. 5, pp.349-355, May, 2002
[15] Chun-Ho Cheung, and Lai-Man Po, “Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation” IEEE TRANSACTIONS ON MULTIMEDIA, VOL. 7, NO. 1, pp.16-22, Feb, 2005
[16] Lap-Pui Chau ? , Ce Zhu, “A fast octagon-based search algorithm for motion estimation” School of Electrical & Electronic Engineering, Nanyang Technological University, Nanyang Avenue, Singapore 639 798, Signal Processing 83, Journal,pp.671-675, Mar, 2002
[17] Yao Nie, and Kai-Kuang Ma,“Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation” IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 11, NO. 12, pp.1442-1449, Dec, 2002
[18] 葉明岳, “A Predictive Kite-Cross-Diamond Algorithm For Fast Block Motion Estimation”國立台灣科技大學電機工程所, Jun, 2006
[19] Chi-Wai Lam, Lai-Man Po,and Chun Ho Cheung, “A Novel Kite-Cross-Diamond Search Algorithm For Fast Block Motion Estimation” Circuits and Systems, 2004.ISCAS '04. Proceedings of the 2004 International Symposium on , pp.23-26 May, 2004
[20] 賴院容, “Motion Estimation using Simulated Annealing”, 義守大學資訊工程所, Jun, 2008
[21] L. Luo, C. Zou, X. Gao, and Z. He, “A new prediction search algorithm for block motion estimation in video coding,” IEEE Trans. Consumer Electronics, vol. 43, no.1, pp.56-61, Feb, 1997
[22] Choudhury A. Rahman, Wael Badawy, “ UMHexagonS Algorithm Based Motion Estimation Architecture for H.264/AVC” System-on-Chip for Real-Time Applications, 2005. Proceedings. Fifth International Workshop on, pp.207-210, 2005
[23] Zhiru Shi, and W.A.C. Fernando,” Adaptive Direction Search Algorithms based on Motion Correlation for Block Motion Estimation” IEEE Transactions on Consumer Electronics, Vol. 57, No. 3, pp.1354-1361, Aug, 2011