臺灣博碩士論文加值系統

由於具有極高的影像壓縮效率，位移估測在目前現行的視訊編碼標準中扮演著一個重要的角色。但是位移估測通常需要花費許多計算時間，因此有許多的演算法被提出來用以減輕位移估測的高計算負載。但是還存有一些相關的課題值得去進一步的研究。 首先，目前幾乎所有的搜尋演算法都只考慮搜尋樣版的形狀，如：Diamond Search演算法 [8]、巢狀搜尋演算法 [9]。另外，這些搜尋演算法通常採用了一套固定的搜尋流程，因此常會造成許多不必要的運算，特別是在處理比較緩慢的視訊串流時。因而本論文提出了兩個估測模組來解決這兩個問題。這兩個模組利用編碼區塊的變動程度來動態的選擇應該使用的搜尋樣板與初始搜尋中心點。實驗的結果顯示，本論文所提出的這兩個模組確能有效改進位移估測的搜尋效率。而且，這兩個模組可以很容易地套用於傳統採用固定搜尋流程的快速搜尋演算法之中，以減輕其計算負載。

In modern video coding, motion estimation plays an important role because of its ability of high compression efficiency. However, motion estimation generally involves heavy computation load, and many fast search algorithms were proposed to alleviate this problem. Despite these efforts, some important issues deserve further study. First, nearly all search algorithms for motion estimation, e.g. Diamond Search [8] and Cellular Search [9], only consider the aspect of the search pattern, and finding the optimal search pattern has been the central issue. Moreover, these methods often employ fixed search routine, which inevitably incur unnecessary computations, particularly in slow image video sequences. Aiming to solve these problems, this thesis presents two estimation modules. Using the variation information of the processing block, the proposed modules are capable of choosing the pattern most suitable for the processing block, and obtaining a better initial search center for the current search window. Experimental results are provided to show the effectiveness of the proposed modules, and their flexibility when incorporated into other search algorithms.

第一章 緒論 1
1-1. 背景說明 1
1-2. 研究動機與目的 2
1-3. 章節簡介 4
第二章 MPEG-2視訊標準簡介 6
2-1. 各模組及流程簡介 6
2-2. MPEG-2畫面編碼方式 12
第三章 BLOCK-MATCHING位移估測演算法 16
3-1 全域搜尋演算法(Full Search Algorithm) 18
3-2 鑽石形搜尋演算法(Diamond Search Algorithm) 18
3-3 巢狀搜尋演算法(Cellular Search Algorithm) 22
第四章 區塊變量與初始搜尋中心估測 27
4-1 適應性位移估測演算法(Adaptive Motion Estimation Algorithm) 27
4-2 應用鄰近區塊向量於區塊變量估測 28
4-3 區塊變量估測(Estimation of block variation) 32
4-4 初始搜尋中心估測(Estimation of initial search center) 35
第五章 實驗結果 38
第六章 結論與討論 45
參考文獻 47

[1] Y. H. Han and J. J. Leou, “Detection and correction of transmission errors in JPEG image,” IEEE Trans. On Circuits and System for Video Tech., 8, No. 2, pp. 221-231, April 1998.
[2] R. C. Gonzalez and R. E. Woods, “Digital image processing,” Addison Wesley, 1992.
[3] Motion Picture Expert Group, “Coding of moving pictures and associated audio for digital storage media at up to about 1.5M bit/s MPEG-1,” International Standard 11172-2, ISO/IEC/JTC1 SC29/WG11, 1994.
[4] Motion Picture Expert Group (JTC1/SC29/WG11) and Expert Group on ATM Video Coding (ITU-T SG15), “Generic coding of moving pictures and associated audio MPEG-2,” Draft International Standard 13818, ISO/IEC, Nov. 1994.
[5] ISO/IEC JTC1/SC29/WG11 14496-2, “Information technology coding of audio visual objects,” March 1998.
[6] Telecommunication Standardization Sector of International Telecommunication Union, “ITU-T recommendation H.261: Video codec for audiovisual services at p*64 k bit/s,” Tech. Rep., ITU-T, 1990.
[7] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” Proc. Nat. Telecommun. Conf., New Orleans, LA, pp. C9.6.1-9.6.5, 1981.
[8] S. Zhu, and K. K. Ma, “A new diamond search algorithm for fast block-matching motion estimation,” IEEE Trans. Image Processing, Vol. 9, No. 2, pp.287-290, 2000.
[9] J. Hung, H. S. Wong, and J. H. Wang, 2001, "A novel cellular search algorithm for block-matching motion estimation," Proc. IEEE International Conf. on Information Technology: Coding and Computing., pp. 629-633, Nevada, USA.
[10] L. —W Lee, J. —F Wang, J. —Y. Lee, and J. —D. Shie, “Dynamic Search-Window Adjustment and Interlaced Search for Block-Matching Algorithm,” IEEE Trans. On Circuits and Systems for Video Technology, vol.3, no.1, pp.85-87, Feb. 1993.
[11] Feng, K. —T. Lo, H. Mehrpour and A. E. Karbowiak, “Adaptive Block Matching Motion Estimation Algorithm for Video Coding,“ Electronic letters, vol. 32, no.18, pp. 1542-1543, Aug. 1995.
[12] H. —S. Oh, G. Park, and H. —K. Lee, “Block-Matching Algorithm Based on Dynamic Search Window Adjustment,” Proc. Intl. workshop, MomuC97, Seoul, Korean, pp.407-412, Sep. 1997.
[13] D. Shckler, Y. Ozturk, H. Abut,” Variable Size Block Motion Estimation,” Conference Record of the Thirty-Second Asilomar Conference on Signals, Systems & Computers, vol.1, pp.868-872, 1998
[14] Jie-Bin Xu, Lai-Man Po, and Chok-Kwan Cheung, “Adaptive Motion Tracking Block Matching Algorithms for Video Cofing,” IEEE Trans. On Circuits and Systems for Video Technology, vol.9, no.7, pp.1025-1029, Oct. 1999.
[15] Hwang-Seek Oh, Heung-Kyu Lee ” Adaptive Adjustment of the Search Window for Block-Matching Algorithm with Variable Block Size,”. IEEE Trans. On Consumer Electronics, vol.4, no.3, pp.659-666, Aug. 1998.
[16] Jong-Hyun Lim; Hae-Wook Choi “Adaptive Motion Estimation Algorithm Using Spatial and Temporal Correlation,” 2001 IEEE Pacific Rim Conference on Communications, Computers and signal Processing, 2001. PACRIM, vol.2, pp.473-476, 2001.
[17] Feng Ya Lin, Yang Xiao Kang, Yu Song Yu“ Adaptive block-matching algorithm for video compression,” Fifth Asia-Pacific Conference on Communications and Fourth Optoelectronics and Communications Conference, APCC/OECC '99, vol.2, pp.920-923, 1999.
[18] 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, pp. 438-442, 1994.
[19] 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, no. 3, pp. 438-442, 1996.