Sub-pixel accuracy motion estimation using linear approximate model of the error criterion function

Sub-pixel accuracy takes up a significant portion of the motion estimation with respect to the computational complexity of video coding. The error criterion function of motion estimation is well represented by a mathematical expression such as quadratic and linear model around the optimal point. Pre-computed error criterion values computed at full-pixel accuracy can be used to derive the motion vector and the error criterion values at sub-pixel accuracy. Based on a linear model function, explicit solutions of the motion vector and the error criterion values at sub-pixel accuracy are derived, which results in the dramatic reduction of computing complexity during the motion estimation process. In addition, a gradient based method is proposed and applied in search of the optimal point which improves further the motion estimation performance while the complexity increase remains negligible.