Title: A hierarchical algorithm with fast convergence spiral search pattern for block matching in motion estimation

Authors: S. Immanuel Alex Pandian; G. Josemin Bala; Maya K. Kuriakose; J. Anitha

Addresses: Department of ECE, Karunya University, Coimbatore, India ' Department of ECE, Karunya University, Coimbatore, India ' Department of ECE, Karunya University, Coimbatore, India ' Department of CSE, Karunya University, Coimbatore, India

Abstract: In a video encoding process, motion estimation (ME) has an important effect, because it approximately takes 60% to 80% of computation in the total computation complexity of video coding. ME is usually applied to reduce the redundancy that exists between successive frames of a video sequence. The motion vector (MV) obtained through this process represent the movement of objects between the frames. One of the most efficient and well-known ME techniques is block matching algorithm (BMA). BMAs have been widely used in several video coding standards. There are various BMAs which try to reduce the number of computations in order to speed up the video encoding process. Here, a block matching ME algorithm called hierarchical algorithm with fast convergence spiral search (HAFCSS) is developed with the intention of reducing the computational complexity while maintaining the visual quality. This is implemented in MATLAB with different video sequences having different motion content. The proposed method provides a better speed improvement of 9% to 45% with reduced number of search points.

Keywords: block matching algorithm; BMA; video compression; video coding; motion estimation; motion compensation; motion vector; spiral search; hierarchical search; video sequences.

DOI: 10.1504/IJCVR.2016.079402

International Journal of Computational Vision and Robotics, 2016 Vol.6 No.4, pp.435 - 449

Accepted: 15 Oct 2014
Published online: 28 Sep 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article