We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 December 2024
Reseach Article

An Optimal Fast Full Search Motion Estimation and Suboptimal Motion Estimation Algorithms

by Adapa Venkata Paramkusam, V. S. K. Reddy
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

@article{ 10.5120/9097-3200,
author = { Adapa Venkata Paramkusam, V. S. K. Reddy },
title = { An Optimal Fast Full Search Motion Estimation and Suboptimal Motion Estimation Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { November 2012 },
volume = { 57 },
number = { 3 },
month = { November },
year = { 2012 },
issn = { 0975-8887 },
pages = { 33-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume57/number3/9097-3200/ },
doi = { 10.5120/9097-3200 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:59:31.351885+05:30
%A Adapa Venkata Paramkusam
%A V. S. K. Reddy
%T An Optimal Fast Full Search Motion Estimation and Suboptimal Motion Estimation Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 57
%N 3
%P 33-40
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. 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
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. W. Li and E. Salari, "Successive elimination algorithm for motion estimation," IEEE Trans. Image Processing, vol. 4, pp. 105–107, Jan. 1995.
  8. 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.
  9. 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

Computer Science
Information Sciences

Keywords

Successive elimination algorithm fast full search motion estimation motion vector suboptimal motion estimation