5. Motion Estimation

Motion estimation is a major problem for video-coding applications. Among several other motion estimation approaches, block matching (BM) algorithms are the most popular methods due to their effectiveness and simplicity at their software and hardware implementation. The BM approach assumes that the pixel movement inside a given region of the current frame (Macro-Block, MB) can be modeled as a pixel translation from its corresponding region in the previous frame. In this procedure, the motion vector is obtained by minimizing the sum of absolute differences (SAD) from the current frame’s MB over a determined search window from the previous frame. Unfortunately, the SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. 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. However, several fast BM algorithms have been lately presented to reduce the number of SAD operations by calculating only a fixed subset of search locations at the price of poor accuracy. In this chapter, a new algorithm based on Differential Evolution (DE) is presented to reduce the number of search locations in the BM process. In order to avoid the computing of several search locations, the algorithm estimates the SAD (fitness) values for some locations by considering SAD values from previously calculated neighboring positions. Since the presented algorithm does not consider any fixed search pattern or other different assumption, a high probability for finding the true minimum (accurate motion vector) is expected. In comparison to other fast BM algorithms, the presented method deploys more accurate motion vectors yet delivering competitive time rates.