The week's pick
Reseach Article
An Optimal Fast Full Search Motion Estimation and Suboptimal Motion Estimation Algorithms
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 57 - Number 3 |
| Year of Publication: 2012 |
| Authors: Adapa Venkata Paramkusam, V. S. K. Reddy |
10.5120/9097-3200
|
Adapa Venkata Paramkusam, V. S. K. Reddy . An Optimal Fast Full Search Motion Estimation and Suboptimal Motion Estimation Algorithms. International Journal of Computer Applications. 57, 3 ( November 2012), 33-40. DOI=10.5120/9097-3200
Abstract
The new fast full search motion estimation algorithm for optimal motion estimation is proposed in this paper. The Fast Computing Method (FCM) which calculates the tighter boundaries faster by exploiting the computational redundancy and the Best Initial Matching Error Predictive Method (BIMEPM) which predicts the best initial matching error that enables the early rejection of highly impossible candidate blocks are presented in this paper. The proposed algorithm provides the optimal solution with fewer computations by utilizing these two methods FCM and BIMEPM. Experimental results show that the proposed new fast full search motion estimation algorithm performs better than other previous optimal motion estimation algorithms such as Successive Elimination Algorithm (SEA), Multilevel Successive Elimination Algorithm (MSEA) and Fine Granularity Successive Elimination (FGSE) on several video sequences. The operation number for this proposed algorithm is reduced down to 1/52 of Full Search (FS). But MSEA and FGSE algorithms can reduce computations by 1/40 and 1/42 of FS. Finally, the proposed new fast full search motion estimation algorithm is modified to sub optimal motion estimation algorithm introducing only a small average PSNR drop of around 0. 2dB but achieves very fast computational speed. The superior performance of this sub optimal motion estimation algorithm over some fast motion estimation algorithms is also proved experimentally.
References
- T. Koga, K. Iinuma, A. Hirano, Y. Iijima and T. Ishiguro, "Motion compensated interframe coding for video conferencing," Pro. Nat. Telecommun. Conf. , New Orleans, pp. G5. 3. 1-5. 3. 5, Nov. 1981
- R. Li, B. Zeng and M. L. Liou, "A new three step search algorithm for block motion estimation," IEEE Trans. on Circuits and Systems for Video Technology, Vol. 4, No. 4, pp. 438-442, Aug. 1994
- 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, Feb. 2000.
- Ce Zhu, Xiao Lin, and Lap-Pui Chau, "Hexagon-Based Search Pattern for Fast Block Motion Estimation" IEEE Trans. on Circuits and Systems for Video Technology, Vol. 12, No. 5, pp. 349-355, may-2002.
- Z. Chen, P. Zhou, Y. He, and Y. Chen, "Fast integer pel and fractional pel motion estimation for JVT," document JVT-F017, ISO/IEC JTC1/SC29/WG11 and ITUT SG16, Dec. 2002.
- Zhibo Chen, Jianfeng Xu, Yun He, and Junli Zheng, "Fastinteger-pel and fractional-pel motion estimation for H. 264/AVC,"Journal of Visual Communication & Image Representation, April 2006, pp. 264- 290.
- W. Li and E. Salari, "Successive elimination algorithm for motion estimation," IEEE Trans. Image Processing, vol. 4, pp. 105–107, Jan. 1995.
- X. Q. Gao, C. J. Duanmu, and C. R. Zou, "A multilevel successive elimination algorithm for block matching motion estimation," IEEE Trans. Image Processing, vol. 9, pp. 501–504, Mar. 2000.
- C. Zhu, W. S. Qi, and W. Ser, "Predictive fine granularity successive elimination for fast optimal block matching motion estimation," IEEE Trans. Image Processing, vol. 14, no. 2 pp. 213-221, Feb. 2005.
Index Terms
Keywords