臺灣博碩士論文加值系統

移動估測及移動補償技術是能減少連續碼框視訊編碼時間的重複性，移動估測在減少訊號傳送量及訊號儲存空間扮演重要的角色，以絕對差值和為基礎的基因法則移動估測演算法 (SADGA) 將呈現一個快速移動估測演算法則，它結合基因法則及鑽石搜尋法則的優點，可得到比較好的PSNR效能，並減少不必要的計算量，絕對差值和為基礎的基因法則移動估測演算法(SADGA) 可減少搜尋的點，它架構於區塊搜尋法則，能以前面已傳送的碼框視訊預測目前的碼框視訊，取得最理想的搜尋起始向量點，可減少許多搜尋點數及搜尋時間；搜尋複雜度也可減低。此法則估測搜尋可達到與全域搜尋演算法之準確度；但搜尋時間卻比全域搜尋演算法短少很多，甚至比鑽石搜尋法則的執行速度還快。

In video coding, the temporal redundancy between consecutive frames can be reduced by the motion estimation and motion compensation technique. Motion estimation plays an important role in reducing the bit rates for transmission or storage of video signals. A robust motion estimation algorithm called the Sum of Absolute Difference based Genetic Algorithm (SADGA) is proposed in this thesis. The proposed scheme applies the genetic algorithm to construct the SAD structure for each block, which combines the advantages of the genetic algorithm and the small diamond search algorithm. Experimental results show that the SADGA not only provides better performance in terms of PSNR but also achieves lower computational complexity compared with the previous famous search algorithms such as TSS, 4SS and DS.

Contents
Chapter 1 1
Introduction 1
Chapter 2 3
Motion Estimation Algorithms 3
2.1 Introduction 3
2.2 Block matching Algorithms 6
2.2.1 Full Search Algorithm 7
2.2.2 Three Step Search Algorithm 9
2.2.3 Four Step Search Algorithm 9
2.2.4 Diamond search algorithm 10
2.2.4.1 Introduction 10
2.2.4.2 Diamond search algorithm 12
2.2.4.3 Comments on DS algorithm implementation 12
2.3 Matching criteria 15
2.3.1 SAD(sum absolute difference) 15
2.3.2 MAE (Mean Absolute Error) 16
2.3.3 MSE(Mean Square Error) 16
Chapter 3 17
The Genetic Algorithm 17
3.1 Introduction 17
3.1.1 Terminology 17
1) Evaluation 17
2) Cross over 17
3) Mutation 18
4) Population 18
3.1.2 Five components of Genetic Algorithm 19
3.2 Genetic motion search algorithm 19
Chapter 4 22
A Sum of Absolute Difference based Genetic Algorithm (SADGA) for Motion Estimation 22
4.1 Introduction 22
4.2 The Proposed SADGA Algorithm 23
4.2.1 The process of SADGA 23
4.3 Experimental Results 27
4.3.1 Peak Signal to Noise Ratio (PSNR) 27
4.3.2 Average SAD search points per block 29
4.3.3 Average of Sum absolute difference (SAD) 29
Chapter 5 45
Conclusions 45
Bibliography 46

[1] A. N. Netravali and J. D. Robbins, “Motion-compensated television coding: part I,” Bell Syst. Tech. J., Vol. 58, pp. 631-670, Mar. 1979.
[2] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishi-guro, “Motion compensated interframe coding for video conferencing,” in Proc. Nat. Telecommun. Conf., New Orleans, LA, pp.G5.3.1—5.3.5. , Nov. 29—Dec. 3 1981.
[3] J. R. Jain and A. K. Jain, “Displacement measurement and its application interframe image coding,” IEEE Trans. Commun., Vol. COMM-29, No. 12, pp. 1799-1808, Dec. 1981.
[4] D. R. Walker and K. R. Rao, “Improved pel-recursive motion compensation,” IEEE Trans. Commun., Vol. COMM-32, pp. 1128-1134, Oct. 1984.
[5] R. Srinivasan and K. R. Rao, “Predictive coding based on efficient motion estimation,” IEEE Trans. Commun., Vol. COMM-33, No. 8, pp. 888-896, Aug. 1985.
[6] H. —H. Nagel, “On the estimation of optical flow: Relations between different approaches and some new results,” Artificial Intelligence, Vol. 33, pp. 299-324, 1987.
[7] M. Ghanbari, “The cross-search algorithm for motion estimation,” IEEE Trans. Commun, Vol. 38, No. 7, pp. 950-953, July. 1990.
[8] Y. O. Zhang and S. Zafar, “Predictive block-matching motion estimation for TV coding-Part II: Interframe prediction,” IEEE Trans. Broadcast, Vol. 37, pp. 102-105, Sept. 1991.
[9] K. H. K. Chow and M. L. Liou, “Genetic motion search algorithm for video compression”, IEEE Trans. Circuits and System for Video Technology, vol. 3, no. 6, pp.440-445, Dec. 1993.
[10] M. J. Chen, L. G. Chen, and T. D. Chiueh, “One-dimensional full search motion estimation algorithm for video coding,” IEEE Trans. Circuits Syst. Video Technol., Vol. 4, pp. 504-509, Oct. 1994.
[11] Renxiang Li,Bing Zeng,and Ming Liou, “A new three-step search algorithm for block motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp. 438—442, Aug. 1994.
[12] W. Li and E. Salari, “Successive elimination algorithm for motion estimation,” IEEE Trans. Image Processing, vol. 4, No. 1, pp. 105-107, Jan. 1995.
[13] 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.
[14] L. K. Liu and E. Feig, “A block-based gradient descent search algorithm for block motion estimation in video coding,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 4, pp. 419—423, Aug. 1996.
[15] Chun-Hung Lin and Ja-Ling Wu, “Genetic block matching algorithm for video coding,” Proceeding of Multimedia’ 96, pp. 544-547, 1996.
[16] Guanghua Qiu and Chaohuan Hou,” A new fast algorithm for the estimation of block motion vectors,” IEEE,1996.
[17] S. Brofferio and F. Rocca, “Interframe redundancy reduction of video signals generated by translating objects,” IEEE Trans. Commun., Vol. COMM-25, pp. 448-455, Apr. 1997.
[18] Chang-Hsing Lee and Ling-Hwei Chen, “A fast motion estimation algorithm based on the block sum pyramid,” IEEE Trans. Image Processing, Vol. 6, No. 11, pp. 1587-1591, Nov. 1997.
[19] Jianhua Lu; Liou, M.L., “A simple and efficient search algorithm for block-matching motion estimation,” IEEE Transactions on Circuits and Systems for Video Technology, Volume: 7 Issue: 2, Apr. 1997.
[20] Kuan Tsang Wang, Oscal T -C. Chen, “Motion estimation using a Four-Step Search Method,” IEEE, pp. IV. 217-220, 1998.
[21] Man F. So and Angus Wu, “Four-Step Genetic Search for Block Motion Estimation,” IEEE, pp. 1393-1396, 1998.
[22] Chun-Hung Lin and Ja-Ling Wu,”A lightweight genetic block matching algorithm for video coding,” IEEE Transactions on Circuits and Systems for Video Technology, Volume: 8 No. 4 , pp. 386-392, Aug. 1998.
[23] Seongsoo Lee; Jeong-Min Kim; Suo-Ik Chae, “New motion estimation algorithm using adaptively quantized low bit-resolution image and its VLSI architecture for MPEG2 video encoding,” IEEE Transactions on Circuits and Systems for Video Technology, Volume: 8 Issue: 6, Oct. 1998.
[24] E.Dixon, C.Pantsios Markhauser and K.R.Rao, “A new video object motion estimation strategy using a multipopulation modified coevolutionary genetic algorithm,” IEEE, pp. 159-165, 1998.
[25] “MPEG-4 video verification model, ver. 14.0,” ISO/IEC JTC1/SC29/WG11/N2932, Oct. 1999.
[26] Shen Li, Wei-pu Xu, Hui Wang,Nan-ning Zheng,” A Novel Fast Motion Estimation Method Based on Genetic Algorithm,” IEEE, pp. 66-69, 1999.
[27] Tae-Myoung Oh, Young-Ro Kim, Won-Gi Hong, and Sung-Jea Ko, “A Fast Full Search Motion Estimation Algorithm Using the Sum of Partial Norms,” Digest of Technical Papers, Int. Conf. Consumer Electronics, pp. 236-237, 2000.
[28] Shan Zhu and Kai-Kuang Ma, “A New Diamond Search Algorithm for Fast Block Matching Motion Estimation,” Transactions on Image Processing, Vol. 9, no. 2, IEEE, pp. 287—290, Feb. 2000.
[29] Hsien His Hsieh and Yeong-Kang Lai, “A Novel Fast Motion Estimation Algorithm Using Fixed Subsamping Pattern and Multiple Local Winners Search,” IEEE, pp. II-241-244, 2001.
[30] Weiguo Zheng, Ishfaq Ahmad and Ming Lei Liou, “Adaptive motion search with elastic diamond for MPEG-4 video coding,” IEEE, pp. 377 —380, 2001.
[31] Yeong Kang Lai, “A Memory Efficient Motion Estimation for Three Step Search Block Matching Algorithm,” IEEE Trans. on Consumer Electronics, Volume: 47. No. 3, pp. 644-651, Aug. 2001.