臺灣博碩士論文加值系統

在MPEG-1,2,4 及H.26X 系列的視訊編碼中，為了尋找畫面與畫面間的移動向量，最常被使用的是區塊比對演算法。而全域搜尋法(full search,FS)是最早被使用的搜尋演算法，此演算法的視訊品質最佳，但是運算量過於龐大。因此許多為了能維持視訊品質和減少搜尋點數的以區塊比對為概念的演算法被提出來，如三步搜尋演算法、鑽石搜尋演算法、六角搜尋演算法等。
在本研究中，為了提高移動估測的效能，我們提出了基於混合蛙跳演算法 (Shuffled frog-leaping algorithm)所演進之新演算法，以及加入初始搜尋樣式和具適應性的終止條件，以提高移動估測的整體效能。並且測試其視訊品質和搜尋速度，並與其他演算法進行比較以驗證改良之新演算法的可行性。而根據實驗結果，我們的演算法可以在高移動量的視訊中，比其他演算法更容易找到最佳點獲得更好的視訊品質，並且在搜尋速度上也有相當好的表現。

In MPEG and H.26X series, Block Matching Algorithm is used for finding the motion vector between frame and frame. The Full Search Algorithm (FS) retrieves the best video quality, but the computation is too complex. In order to maintain video quality and reduce search points, Fast Block Matching Algorithms such as Three-Step Search algorithm (TSS), Diamond Search algorithm (DS), Hexagon-based Search algorithm (HEXS) are proposed.
In this paper, Shuffled Frog-Leaping Algorithm (SFLA) is proposed based on the evolution of the new algorithm, the initial search pattern and the adaptive termination conditions to improve the overall performance of motion estimation. According to the experimental results, under the condition of the
high movement video chips, our algorithm is easier to find the best spot and get better video quality than other BMA algorithms, and the search speed is also the fastest compared to other algorithms.

摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
一、緒論 1
1.1 移動估測 2
1.1.1 全域搜尋演算法 2
1.1.2 快速演算法 4
1.2 論文組織與架構 4
二、文獻探討 5
2.1 快速搜尋演算法 5
2.1.1 三步搜尋演算法 5
2.1.2 新三步搜尋演算法 6
2.1.3 效能三步搜尋演算法 7
2.1.4 鑽石搜尋演算法 9
2.1.5 六角搜尋演算法 10
2.1.6 預測搜尋演算法 11
2.2 演化式演算法 13
2.2.1 混合蛙跳演算法 14
2.2.2 改良式混合蛙跳演算法 16
三、適應性混合蛙跳演算法於移動估測 17
3.1 混合蛙跳演算法模組應用於區塊比對演算法 17
3.2 減少重複搜尋問題 20
3.3 初始化搜尋樣式 21
3.4 引用預測演算法 21
3.5 終止條件 22
3.6 演算法流程圖 23
四、實驗結果與分析 25
4.1 實驗設置 25
4.2 方法測試實驗 26
4.2.1 減少重複搜尋實驗 26
4.2.2 預測初始搜尋樣式 27
4.2.3 適應性終止條件 29
4.3 實驗結果分析 31
五、結論與未來展望 40

[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, Volume 13, Issue 7, Page(s): 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] 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-G..5.3.5, 1981.
[5] 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.
[6] 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.
[7] 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.
[8] Xuan Jing, Lap-Pui Chau,“An efficient three-step search algorithm forblock motion estimation”, IEEE Trans. on Multimedia, vol. 6, no. 3, pp.435-438, June 2004.
[9] 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.
[10] Hung-Chan Chai, “The Applications of modified shuffled frog-leaping optimization algorithm to the image thresholding and the classifications of support vector machines”, Master thesis of National PingTung Institute of Commerce, Taiwan, July 2012.
[11] K. Hammouche, M. Diaf, P. Siarry, “A multilevel automatic thresholding method based on a genetic algorithm for a fast image segmentation”, Computer Vision Graphics and Image Understanding 109 (2008), 163-175.
[12] M. Dorigo and T. Stutzle, “Ant colony optimization”, MIT, July 2004.
[13] X. Yuan, X. Shen, Block matching algorithm based on particle swarm optimization for motion estimation, in: International Conference on Embedded Software and Systems (ICESS’2008), 2008.
[14] Kennedy, J. and Eberhart, R., Particle swarm optimization, in Proceedings IEEE International Conference on Neural Networks, IEEE Service Center, Piscataway, NJ, pp. 1942 – 1948, 1995.
[15] J. Cai, W. David Pan, On fast and accurate block-based motion estimation algorithms using particle swarm optimization, Information Sciences 197 (2012) 53–64.
[16] D. Karaboga, B. Basturk, “An artificial bee colony (ABC) algorithm for numeric function optimization,” IEEE Swarm Intelligence Symposium, 2006, pp.1971-1997.
[17] E. Cuevas, et al., Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC), Appl. Soft Comput. J. (2012).
[18] M.M. Eusuff, K.E. Lansey, “Optimization of Water Distribution Network Design using the Shuffled Frog Leaping Algorithm”, Journal of Water Resources Planning and Management, Vol. 129, No. 3, May/June 2003, 210-225.
[19] E. Elbeltagi, T. Hegazy, D. Grierson, “A modified shuffled frog-leaping optimization algorithm: applications to project management”, Structure and Infrastructure Engineering, Vol. 3, No. 1, March 2007, 53-60.
[20] 傅敬惟, “Fast Hexagon Search Algorithm”, Master thesis of National PingTung Institute of Commerce, Taiwan, June 2009.
[21] 劉原禎, “A modified double layered search pattern algorithm for motion estimation”, Master thesis of National PingTung Institute of Commerce, Taiwan, Jul, 2012
[22] 葉明岳, “A Predictive Kite-Cross-Diamond Algorithm For Fast Block Motion Estimation”Master thesis of National Taiwan University of Science and Technology, June, 2006