Block matching is an important technique for applications involving motion estimation, such as in video surveillance, TV broadcasting, video games, and so on. To improve the efficiency and effectiveness of block matching algorithms, the authors of this paper propose a block matching algorithm based on stochastic fractal search (SFS-BM). Instead of commonly used hierarchical metaheuristic block matching approaches, SFS-BM calculates motion vectors in a parallel structure. Block matching performance is also related to the initialization of candidate blocks, the fitness function, and the size of search windows. The authors further modify the SFS-BM algorithm as MSFS-BM, in which the initial solutions are evaluated with a fitness function that combines matching criteria and the search space is controlled by an adaptive window size. With the intention of further improving computational time efficiency, the authors also propose a strategy for reducing the number of fitness estimations.
The authors examine the performances of SFS-BM and MSFS-BM against six “other well-known block matching algorithms” on “nine video sequences of different formats and motion types.” The two quantitative metrics used for performance comparison are motion estimation accuracy and the average number of searched points. The experiments “indicate significant improvement of MSFS-BM over SFS-BM with percentages of 34.50 percent in [peak signal-to-noise ratio, PSNR] and 58.08 percent in the number of searched points.” The authors claim that MSFS-BM outperforms all other block matching algorithms in their experiments.
People working in areas of motion estimation would certainly benefit from reading this paper, specifically for the reported performance improvements of the new algorithm. Beyond estimating movements of frames, this work is about discovering patterns of data and estimating temporal redundancy. Therefore, those in data science and artificial intelligence (AI) could also benefit from reading it.