Motion estimation is the science of predicting the current frame in a
video sequence from the past frame (or frames), by
slicing it into rectangular blocks of pixels, and matching these to past such blocks. The displacement in the spatial position of the block in the current frame with respect to the past frame is called the
motion vector. This method of temporally decorrelating the
video sequence by finding the
best matching blocks from past reference frames—
motion estimation—makes up about 80% or more of the computation in a video
encoder. That is, it is enormously expensive, and methods do so that are efficient are in high demand. Thus the field of
motion estimation within video coding is rich in the breadth and diversity of approaches that have been put forward. Yet it is often the simplest methods that are the most effective. So it is in this case. While it is well-known that a full search over all possible positions within a fixed window is an optimal method in terms of performance, it is generally prohibitive in computation. In this patent disclosure, we define an efficient, new method of searching only a very sparse subset of possible displacement positions (or motion vectors) among all possible ones, to see if we can get a good enough match, and terminate early. This set of sparse subset of motion vectors is preselected, using a priori knowledge and extensive testing on video sequences, so that these “predictors” for the
motion vector are essentially magic. The art of this method is the preselection of excellent sparse subsets of vectors, the smart thresholds for acceptance or rejection, and even in the order of the testing prior to decision.