TY - JOUR
T1 - Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC)
AU - Cuevas, Erik
AU - Zaldívar, Daniel
AU - Pérez-Cisneros, Marco
AU - Sossa, Humberto
AU - Osuna, Valentín
N1 - Funding Information:
V. Osuna thanks CONACYT for the scholarship to finish his doctoral studies. He also thanks the CIC-INP and the UDG for the support to complete his studies. H. Sossa would like to thank CONACYT and SIP-IPN for the economical founding to accomplish this research, under Grants 155014 and 20121311.
PY - 2013
Y1 - 2013
N2 - Block matching (BM) motion estimation plays a very important role in video coding. In a BM approach, image frames in a video sequence are divided into blocks. For each block in the current frame, the best matching block is identified inside a region of the previous frame, aiming to minimize the sum of absolute differences (SAD). Unfortunately, the SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. Therefore, BM motion estimation can be approached as an optimization problem, where the goal is to find the best matching block within a search space. The simplest available BM method is the full search algorithm (FSA) which finds the most accurate motion vector through an exhaustive computation of SAD values for all elements of the search window. Recently, several fast BM algorithms have been proposed to reduce the number of SAD operations by calculating only a fixed subset of search locations at the price of poor accuracy. In this paper, a new algorithm based on Artificial Bee Colony (ABC) optimization is proposed to reduce the number of search locations in the BM process. In our algorithm, the computation of search locations is drastically reduced by considering a fitness calculation strategy which indicates when it is feasible to calculate or only estimate new search locations. Since the proposed algorithm does not consider any fixed search pattern or any other movement assumption as most of other BM approaches do, a high probability for finding the true minimum (accurate motion vector) is expected. Conducted simulations show that the proposed method achieves the best balance over other fast BM algorithms, in terms of both estimation accuracy and computational cost.
AB - Block matching (BM) motion estimation plays a very important role in video coding. In a BM approach, image frames in a video sequence are divided into blocks. For each block in the current frame, the best matching block is identified inside a region of the previous frame, aiming to minimize the sum of absolute differences (SAD). Unfortunately, the SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. Therefore, BM motion estimation can be approached as an optimization problem, where the goal is to find the best matching block within a search space. The simplest available BM method is the full search algorithm (FSA) which finds the most accurate motion vector through an exhaustive computation of SAD values for all elements of the search window. Recently, several fast BM algorithms have been proposed to reduce the number of SAD operations by calculating only a fixed subset of search locations at the price of poor accuracy. In this paper, a new algorithm based on Artificial Bee Colony (ABC) optimization is proposed to reduce the number of search locations in the BM process. In our algorithm, the computation of search locations is drastically reduced by considering a fitness calculation strategy which indicates when it is feasible to calculate or only estimate new search locations. Since the proposed algorithm does not consider any fixed search pattern or any other movement assumption as most of other BM approaches do, a high probability for finding the true minimum (accurate motion vector) is expected. Conducted simulations show that the proposed method achieves the best balance over other fast BM algorithms, in terms of both estimation accuracy and computational cost.
KW - Artificial Bee Colony
KW - Block matching algorithms
KW - Fitness approximation
KW - Motion estimation
UR - http://www.scopus.com/inward/record.url?scp=84878109112&partnerID=8YFLogxK
U2 - 10.1016/j.asoc.2012.09.020
DO - 10.1016/j.asoc.2012.09.020
M3 - Artículo
SN - 1568-4946
VL - 13
SP - 3047
EP - 3059
JO - Applied Soft Computing Journal
JF - Applied Soft Computing Journal
IS - 6
ER -