臺灣博碩士論文加值系統

在運動估計(motion estimation)中移動向量(motion vector)的尋找是極度重要的一個課題，然而最常被使用的方法就是區塊比對演算法(Block Matching Algorithm)，其中全域搜尋演算法(Full search Algorithm)是最穩健的做法，可以取得最佳的影像品質但是其運算量也是極度龐大的，此後更有各種快速演算法被提出，如：三步搜尋演算法、四步搜尋演算法、鑽石搜尋演算法等。
在本研究中提出了一種自適應策略來改良快速搜尋演算法如鑽石搜尋演算法(DS)，適應性十字搜尋演算法(ARPS)等…，藉以提高影像品質，並與其他原始快速搜尋演算法做進一步的比較。
實驗結果顯示，我們雖然犧牲些許時間以及搜尋點數，但是可以取得更高的品質，尤其在運動量較大的影像中有更顯著的效果。

Searching the suitable Motion Vector (MV) is an important issue in Motion Estimation (ME). In order to solve this problem Block Matching Algorithms (BMA) have been proposed. In BMA, Full Search Algorithm (FSA) is the one of most basic approach. It achieves the best video quality but also results in large amount of computation. Therefore, many fast search algorithms are suggested to decrease search points, such as Three-Step Search Algorithm (TSS), Four-step Search Algorithm (FSS) and Diamond Search Algorithm (DS) .
In this paper, Adaptive Strategy Search Algorithm (ASS) is proposed based on some fast search algorithms, such as DS and ARPS, to enhance video quality. Result shows that it can achieve higher quality with a little expense of time and search points, especially in high movement video.

摘要 1
Abstract 2
目錄 3
圖目錄 4
表目錄 4
第一章 緒論 5
1.1 研究背景 5
1.2 H.264/MPEG-4 AVC 6
1.3 運動補償及運動估計 7
1.3.1 比較方法 8
1.3.2 全域搜尋演算法(Full Search, FS) 9
第二章 快速搜尋演算法探討 10
2.1 三步搜尋演算法(Three Step Search, TSS) 10
2.2 四步搜尋演算法(Four Step Search, FSS or 4SS) 12
2.3 鑽石(菱形)搜尋演算法(Diamond Search, DS) 14
2.4 六角搜尋演算法(Hexagon Search, HexS) 16
2.5 預測搜尋演算法(Predictive Search ) 18
2.6 適應性十字搜尋演算法(Adaptive Rood Pattern Search, ARPS) 19
第三章 適應性策略搜尋演算法 21
3.1 適應性策略 21
3.2 畫面張數限制 21
3.3 參數設置α 22
第四章 實驗結果與分析 24
第五章 結論與未來展望 30
參考文獻 31

[1] T. Wiegand, G. J. Sullivan, G. Bjntegaard, and A. Luthra, “Overview of the H.264/AVC Video Coding Standard,” Circuits and Systems for Video Technology, IEEE Transactions on, vol. 13, Issue 7, pp.560-576, July 2003.
[2] G. J. Sullivan and T. Wiegand, “Video compression-from concepts to the H.264/AVC standard,” Proceedings of the IEEE, vol. 93, no. 1, pp.18-31, Jan 2005.
[3] D. Marpe, T. Wiegard, and G. J. Sullivan, “The H.264/MPEG4 advanced video coding standard and its applications,” IEEE Communications Magazine, vol. 44, no. 8 , pp. 134-143, Aug 2006.
[4] Aroh Barjatya, “Block Matching Algorithms For Motion Estimation” Final project paper, DIP, at Utah state university, Spring 2004.
[5] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion-compensated interframe coding for video conferencing,” in Proc. of NTC81, New Orleans, LA , pp. G5.3.1-G5.3.5, 1981.
[6] 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, no. 4, pp. 438-442, Aug 1994.
[7] Xuan Jing, Lap-Pui Chau, “An efficient three-step search algorithm for block motion estimation,” IEEE Trans. on Multimedia., vol. 6, no. 3, pp.435-438, June 2004.
[8] 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.
[9] S. Zhu and K.-K. Ma, “A new diamond search algorithm for fast block matching motion estimation,” IEEE Trans. Image Process., vol. 9, no.2, pp. 287-290, Feb 2000.
[10] C. Zhu, X. Lin, and L. P. Chau, “Hexagon-based search pattern for fast block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 12, no. 5, pp. 349-355, May 2002.
[11] 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.
[12] Yao Nie, and Kai-Kuang Ma, “Adaptive Rood Pattern Search for Fast Block-Matching Motion Estimation,” IEEE Trans. Image Processing, Vol. 11, no. 12, pp.1442-1449, Dec 2002.
[13] Yang Liu, Zheng Guo Li, and Yeng Chai Soh, “Region-of-Interest Based Resource Allocation for Conversational Video of H.264AVC,” IEEE transactions on circuits and systems for video technology, vol. 18, no. 1, pp.134-139, Jan 2008.
[14] Yıldıray Anag&;uuml;n, Erol Seke, “Super Resolution Using Variable Size Block-Matching Motion Estimation With Rotation,” Proceedings of the International Symposium on Innovations in Intelligent Systems and Applications INISTA , July 2012.
[15] Zaynab Ahmed, Abir Jaafar Hussain, and Dhiya Al-Jumeily, “Edge Detection for Fast Block-Matching Motion Estimation to Enhance Mean Predictive Block Matching Algorithm,” Proceedings of the International Symposium on Innovations in Intelligent Systems and Applications INISTA, July 2012.
[16] 吳家鳴, “Adaptive Polygon Predictive Search Algorithm,” Master thesis of National PingTung Institute of Commerce, Taiwan, Jul, 2013.
[17] 徐富翊,“Adaptive Shuffled Frog-Leaping Algorithm for Motion Estimation,”Master thesis of National PingTung Institute of Commerce, Taiwan, Jul, 2013.
[18] 劉原禎, “A modified double layered search pattern algorithm for motion estimation”, Master thesis of National PingTung Institute of Commerce, Taiwan, Jul, 2012.
[19] 傅敬惟, “Fast Hexagon Search Algorithm,” Master thesis of National PingTung Institute of Commerce, Taiwan, Jun, 2009.
[20] C. C. Lin, Y. Lin and H. J. Hsieh, “Multi-direction search algorithm for block motion estimation in H. 264/AVC, ” IEEE Trans. Image Processing, vol. 3, no. 2, pp. 88-99, Apr 2009.
[21] Zhiru Shi,W. A. C. Fernando and A. Kondoz, “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.
[22] S. Acharjee, N. Dey, D. Biswas, P. Das and S. S. Chaudhuri, "A novel Block Matching Algorithmic Approach with smaller block size for motion vector estimation in video compression," Proc. of 12th International Conference on Intelligent Systems Design and Applications (ISDA), pp. 668-672, Nov 2012.
[23] S. Acharjee, N. Dey, D. Biswas, P. Das and S. S. Chaudhuri ,“An Efficient Motion Estimation Algorithm using Division Mechanism of Low and High Motion Zone,” Proc. of International Multi-Conference on Automation, Computing, Communication, Control and Compressed Sensing (iMac4s), pp.52-58, March 2013.