Sobol Partial Distortion Algorithm for Fast Full Search in Block Motion Estimation

Abstract

Block motion estimation is a cpu intensive task for video encoding. Many fast algorithms have been developed to solve this problem, trying to improve both block searching and block matching. Some of them reduce the image quality compared to the full search method in order to improve performance. The algorithm presented in this paper, called Sobol Partial Distoriton (SPD) algorithm, is a full search (lossless), fast matching, block motion estimation algorithm, applying partial distortion elimination. It uses a new matching strategy to quickly compute distortion and reduce block matching computation. Image-dependent computation is not required, since the matching strategy does not depend on the frame sequence. the proposed algorithm performs well in terms of computational speedup in comparison with other existing full search algorithms.