Home   >   CSC-OpenAccess Library   >    Manuscript Information
Fast Motion Estimation for Quad-Tree Based Video Coder Using Normalized Cross-Correlation Measure
Eskinder Anteneh Ayele, Ravindra Eknath Chaudhari, S. B. Dhok
Pages - 330 - 338     |    Revised - 15-08-2013     |    Published - 15-09-2013
Volume - 7   Issue - 4    |    Publication Date - September 2013  Table of Contents
FFT, Motion Estimation, Normalized Cross Correlation, Quad-tree, Video Compression.
Motion estimation is the most challenging and time consuming stage in block based video codec. To reduce the computation time, many fast motion estimation algorithms were proposed and implemented. This paper proposes a quad-tree based Normalized Cross Correlation (NCC) measure for obtaining estimates of inter-frame motion. The measure operates in frequency domain using FFT algorithm as the similarity measure with an exhaustive full search in region of interest. NCC is a more suitable similarity measure than Sum of Absolute Difference (SAD) for reducing the temporal redundancy in video compression since we can attain flatter residual after motion compensation. The degrees of homogeneous and stationery regions are determined by selecting suitable initial fixed threshold for block partitioning. An experimental result of the proposed method shows that actual numbers of motion vectors are significantly less compared to existing methods with marginal effect on the quality of reconstructed frame. It also gives higher speed up ratio for both fixed block and quad-tree based motion estimation methods.
CITED BY (1)  
1 Chaudhari, R. E., & Dhok, S. B. Fast Quadtree Based Normalized Cross Correlation Method for Fractal Video Compression using FFT.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
A. Barjatya, “Block Matching Algorithms for Motion Estimation”, Digital Image Processing (DIP 6620) ,Final project paper, Utah State University, Spring 2004.
A. J. H. Hii, C. E. Hann, J. G. Chase, and E. E. W. Van Houten, “Fast Normalized Cross Correlation for Motion Tracking Using Basis Functions”, Journal of Computer Methods and Programs in Biomedicine, vol. 82, no. 2, pp. 144-156, 2006.
B. C. Song, “A Fast Normalized Cross Correlation-Based Block Matching Algorithm Using Multilevel Cauchy-Schwartz Inequality”, ETRI Journal, vol. 33, no.3, pp. 401-406, June 2011.
C. Kasai, K. Namekawa, A. Koyana and R. Omoto “Real-Time Two-Dimensional Blood Flow Imaging Using an Autocorrelation Technique”, IEEE Transaction on Sonics and Ultrasonics,vol. 32, issue 3, pp. 458-464, May 1985.
F. Viola and W. F. Walker, “A spline-based algorithm for continuous time-delay estimation using sampled data”, IEEE Transactions on Ultrasonics. Ferroelectrics. Frequency Control,vol. 52, no. 1, pp. 80–93, 2005.
G. J. Sullivan and R. L. Baker, “Efficient Quadtree Coding of Images and Video”, IEEE Transactions on Image Processing, vol. 3, issue 3, pp. 327-331, May 1994.
G. M. Schuster and A. K. Katsaggelos, “An Optimal Quadtree Based Motion Estimation and Motion-Compensated Interpolation Scheme for Video Compression”, IEEE Transactions on Image Processing, vol. 7, issue 11, pp. 1505-1523, Nov. 1998.
J. Lee, “Optimal quadtree for variable block size motion estimation”, IEEE International Conference on Image Processing, Oct. 1995, vol. 3, pp. 480-483.
J. Luo and E. E. Konofagou, “A Fast Normalized Cross-Correlation Calculation Method for Motion Estimation”, IEEE Transactions on Ultrasonics, Ferroelectrics, and Frequency Control, vol. 57, issue 6, pp. 1347-1357, June 2010.
P. Anandan, ”A Computational Framework and an Algorithm for the Measurement of Visual Motion”, International Journal of Computer Vision, vol. 2, pp. 283-310, 1989.
S. D. Wei, W. H. Pan and S. H. Lai, “A novel motion estimation method based on normalized cross correlation for video compression”, Proceedings-14th International Multimedia Modeling Conference, MMM 2008, Kyoto, Japan, Jan. 2008, pp. 338-.347.
S. Langeland, J. D’hooge, H. Torp, B. Bijnens, and P. Suetens, “Comparison of TimeDomain Displacement Estimators for Two-Dimensional RF Tracking”, Ultrasound in Medicine and Biology, vol. 29, no. 8, pp. 1177–1186, 2003.
V. Argyriou and T. Vlachos, “Motion estimation using quad-tree phase correlation”, IEEE International Conference on Image Processing, 2005, vol. 1, pp. I-1081-I-1084.
V. Argyriou and T. Vlachos, ”Quad-Tree Motion Estimation in the Frequency Domain Using Gradient Correlation”, IEEE Transactions on Multimedia, vol 9, issue 6, pp. 1147-1154, Oct.2007.
V. Seferidis and M. Ghanbari, “Generalised Block-Matching Motion Estimation using QuadTree Structured Spatial Decomposition”, IEE Proceedings- Vision, Image and Signal Processing, vol. 141, issue 6, pp. 446-452, 1994.
Dr. Eskinder Anteneh Ayele
Research Scholar/ Department of Electronics Enginee ring Visvesvaraya National Institute of Technology Nagpur,440022 - India
Mr. Ravindra Eknath Chaudhari
Asst. Professor/Dept. of ECE St. Francis Institute of Technology Mumbai,400103 - India
Dr. S. B. Dhok
Asso. Professor/Department of Electronics Engineeri ng Visvesvaraya National Institute of Technology Nagpur,440022 -