Home
Scholarly Works
Simple and efficient motion estimation algorithm...
Journal article

Simple and efficient motion estimation algorithm by continuum search

Abstract

Motion estimation plays a vital role in reducing temporal correlation in video codecs but it requires high computational complexity. Different algorithms have tried to reduce this complexity. However these reduced-complexity routines are not as regular as the full search algorithm (FSA). Also, regularity of an algorithm is very important in order to have a hardware implementation of that algorithm even if it leads to more complexity burden. The goal of this paper is to develop an efficient and regular algorithm which mimics FSA by searching a small area exhaustively. Our proposed algorithm is designed based on two observations. The first observation is that the motion vector of a block falls within a specific rectangular area designated by the prediction vectors. The second observation is that in most cases, this rectangular area is smaller than one fourth of the FSA’s search area. Therefore, the search area of the proposed method is adaptively found for each block of a frame. To find the search area, the temporal and spatial correlations among motion vectors of blocks are exploited. Based on these correlations, a rectangular search area is determined and the best matching block in this area is selected. The proposed algorithm is similar to FSA in terms of regularity but requires less computational complexity due to its smaller search area. Also, the suggested algorithm is as simple as FSA in terms of implementation and is comparable with many of the existing fast search algorithms. Simulation results show the claimed performance and efficiency of the algorithm.

Authors

Soroushmehr SMR; Samavi S; Shirani S

Journal

Multimedia Tools and Applications, Vol. 71, No. 3, pp. 1615–1633

Publisher

Springer Nature

Publication Date

January 1, 2014

DOI

10.1007/s11042-012-1298-3

ISSN

1380-7501

Contact the Experts team