Higher order prediction for sub-pixel motion estimation

Estimating motion between two frames of a video sequence, up to sub-pixel accuracy, is a critical task for many image processing applications. Efficient block matching algorithms were proposed in [1, 4, 5, 6] for motion estimation up to pixel accuracy. Applying these fast block search algorithms to up-sampled and interpolated frames can produce good results but with significant increase in computations. To reduce the number of search points, and therefore the computational cost, quadratic prediction was proposed earlier [1, 2] to predict the location of minimum block matching error, and then to limit the search window to the vicinity of the predicted location. In this paper we investigate the typical behavior of block matching error surface and propose an improved higher order prediction that models the error surface more accurately, utilizing additional local image behavior. Initial experiments have proved promising results of about 50% more improvement in PSNR compared to quadratic prediction with only a marginal increase in the computational cost.