Predictive fine granularity successive elimination for fast optimal block-matching motion estimation

Given the number of checking points, the speed of block motion estimation depends on how fast the block matching is. A new framework, fine granularity successive elimination (FGSE), is proposed for fast optimal block matching in motion estimation. The FGSE features providing a sequence of nondecreasing fine-grained boundary levels to reject a checking point using as little computation as possible, where block complexity is utilized to determine the order of partitioning larger subblocks into smaller subblocks in the creation of the fine-grained boundary levels. It is shown that the well-known successive elimination algorithm (SEA) and multilevel successive elimination algorithm (MSEA) are just two special cases in the FGSE framework. Moreover, in view that two adjacent checking points (blocks) share most of the block pixels with just one pixel shifting horizontally or vertically, we develop a scheme to predict the rejection level for a candidate by exploiting the correlation of matching errors between two adjacent checking points. The resulting predictive FGSE algorithm can further reduce computation load by skipping some redundant boundary levels. Experimental results are presented to verify substantial computational savings of the proposed algorithm in comparison with the SEA/MSEA.