Multiscale modeling and estimation of motion fields for video coding

We present a systematic approach to forward-motion-compensated predictive video coding. The first step is the definition of a flexible model that compactly represents motion fields. The inhomogeneity and spatial coherence properties of motion fields are captured using linear multiscale models. One possible design is based on linear finite elements and yields a multiscale extension of the triangle motion compensation (TMC) method. The second step is the choice of a computational technique that identifies the coefficients of the linear model. We study a modified optical flow technique and minimize a cost function closely related to Horn and Schunck's criterion. The cost function balances accuracy and complexity of the motion-compensated predictor and is viewed as a measure of goodness of the motion field. It determines not only the coefficients of the model, but also the quantization method. We formulate the estimation and quantization problems jointly as a discrete optimization problem and solve it using a fast multiscale relaxation algorithm. A hierarchical extension of the algorithm allows proper handling of large displacements. Simulations on a variety of video sequences have produced improvements over TMC and over the half-pel-accuracy, full-search block matching algorithm, in excess of 0.5 dB in average. The results are visually superior as well. In particular, the reconstructed video is entirely free of blocking artifacts.