CFP last date
20 December 2024
Reseach Article

An Efficient Full Search Block Motion Estimation using Trace and Sum of Off- Diagonal based Match and FPGA Implementation

by Manu T.m, Linganagoud Kulkarni, Basavaraj. S. Anami
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 109 - Number 12
Year of Publication: 2015
Authors: Manu T.m, Linganagoud Kulkarni, Basavaraj. S. Anami
10.5120/19244-0988

Manu T.m, Linganagoud Kulkarni, Basavaraj. S. Anami . An Efficient Full Search Block Motion Estimation using Trace and Sum of Off- Diagonal based Match and FPGA Implementation. International Journal of Computer Applications. 109, 12 ( January 2015), 35-40. DOI=10.5120/19244-0988

@article{ 10.5120/19244-0988,
author = { Manu T.m, Linganagoud Kulkarni, Basavaraj. S. Anami },
title = { An Efficient Full Search Block Motion Estimation using Trace and Sum of Off- Diagonal based Match and FPGA Implementation },
journal = { International Journal of Computer Applications },
issue_date = { January 2015 },
volume = { 109 },
number = { 12 },
month = { January },
year = { 2015 },
issn = { 0975-8887 },
pages = { 35-40 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume109/number12/19244-0988/ },
doi = { 10.5120/19244-0988 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:44:39.490598+05:30
%A Manu T.m
%A Linganagoud Kulkarni
%A Basavaraj. S. Anami
%T An Efficient Full Search Block Motion Estimation using Trace and Sum of Off- Diagonal based Match and FPGA Implementation
%J International Journal of Computer Applications
%@ 0975-8887
%V 109
%N 12
%P 35-40
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The H. 264/AVC offer many coding tools that give higher compression ratio compared to earlier standards. These tools increase the computational complexity of the motion estimation. In this paper, we have presented a computationally efficient method to speed up the search process by minimizing the computational load on general full search. The proposed method is having two phases, wherein the first phase involves search for the nearly matching block using the trace and sum of off-diagonal elements. Only upon match, the Sum of Absolute Differences (SAD)is calculated for best motion prediction in the second phase and it is only for limited number of blocks. The trace and off-diagonal sum matching requires O(2n) computations and O(n2) computations are required in case of full search. Hence, the proposed method reduces 75% to 80% of SAD computations of full search motion estimation. This leads to significant improvement in coding efficiency compared to the existing motion estimation techniques without much degradation in video quality. FPGA implementation result shows that, the design can work at the maximum clock frequency of 420 MHz with the power consumption of 34. 86mW

References
  1. J. Kim, S. Byun, Y. Kim, B. Ahn, "Fast full search motion estimation technique using early detection of impossible candidate vectors", IEEE Trans. Signal Process. 50 (2002) 2355–2365.
  2. Y. Chan, W. Siu, "An efficient search strategy for block motion estimation using image features", IEEE Trans. Image Process. 10 (2001) 1223–1238.
  3. Zhu, S. and K. K. Ma (February, 2000). "A New Diamond Search Algorithm for Fast Block Matching Motion Estimation". IEEE Transactions Image Processing, 9(2), pp. 287–290.
  4. Zhu, C. , Lin, X. and Chau, L. P. , 2002. "Hexagon-based search pattern for fast block motion estimation", IEEE Trans. Circuits Syst. Video Technology, May 2002, vol. 12, pp. 349-355.
  5. L. K. Liu and E. EIG,"A block based gradient descent search technique for fast block motion video coding" IEEE Transaction onCSVT,vol. 6. 419-422,Aug,1996.
  6. H. Loukil, F. Ghozzi, A. Samet, et al. "Hardware implementation of block matching technique with FPGA technology," 6th International Conference On Microelectronics, Proceedings, pp. 542–546, 2004.
  7. Brunello, D. , Calvagno, D. , Mian, G. A. and Rina ldo, R. , 2003. "Lossless compression of video using temporal information", IEEE Trans. Image Process. , pp. 132–139.
  8. Y. Chan, W. Siu, "An efficient search strategy for block motion estimation using image features", IEEE Trans. Image Process. 10 (2001) 1223–1238.
  9. S. Wong, S. Vassiliadis, S. Cotofana, "A Sum of Absolute Differences Implementation in FPGA Hardware," 28th Euromicro Conference (EUROMICRO'02), pp. 183–188, Dortmund, German y, 2002.
  10. Gao, X. Q. , Duanmu, C. J. and Zou, C. R. , 2000, "A multilevel successive elimination algorithm for block matching motion estimation", IEEE Trans. Image Processing , March 2000, vol. 9, pp. 501-504.
  11. Puri, A. , Hang, H. M. and Schilling, 1997. "An efficient block matching algorithm for motion compensated coding", in Proc. IEEE Int. Conf. Acoust. , Speech, Signal Processing, pp. 1063–1066
  12. Behard Baumgarrtner, "An Inequality for the trace of absolute matrix product values", arxiv:21106. 618, 2011.
  13. Kuo. Liang ,Shyh-Tih Ma," Predictive Line search: An Efficient Motion Estimation Algorithm for MPEG-4Encoding Systems on Multimedia processors,IEEE Transaction on CSVT,Vol. 13. no1,Jan2003.
  14. Kuo-Liang chung and lung Chun Chang"A new Predictive Search Area Approach for Fast Block Mtotion estimation",IEEE Transaction on Image processing Vol,12. No. 6, june 2003.
  15. Vasily G. Moshnyaga "A New Computationally adaptive Formulation of Block Matching Motion estimation" ,IEEE Transaction on CSVT,Vol. 11,No. 1,Jan2001.
  16. Michael Bruing and Wolfgang Niehsen "Fast Full Search Block Matching", IEEE Transaction on CSVT,Vol. 11,No. 2,Feb 2001.
  17. H. C Huang and Y. P Hung," Adaptive Early Jump-out Technique for Fast Motion Estimation In Video Coding"Graphical Method and Image Processing, Vol 59,No. 6. PP 388-394. Nov,1997.
  18. Somanath Senagupta ,V. S. K Reddy," A Fast and Efficient Predictive Block Matching Motion estimation" IJCNSN, Vol 7,No. 12,Dec. 2007.
  19. S. Sundaravadivelu, Simon Jeyakumar "An Efficient Motion Estimation Algorithm using Trace Match for Fast Video Compression "European Journal of Scientific Research ISSN 1450-216X Vol. 53 No. 4 (2011), pp. 546-554.
  20. Linganagoud Kulkarni, Manu TM, Basavaraj S Anami, "A Two Step Methodology for minimization computational overhead on FSBME", International Journal of u-and e-Service, Science and TechnologyVol. 7,No. 4(2014),pp. 339-348 http://dx. doi. org/10. 14257/ijunnesst. 2014. 7. 4. 31
Index Terms

Computer Science
Information Sciences

Keywords

Video frames Motion estimation temporal prediction Trace SAD calculation Off-diagonal sum.