On New Sorting-Based Lossless Motion Estimation Algorithms

Block motion estimation represents a cpu-intensive task in video encoding and many fast algorithms have been developed to improve the searching and matching phases. A milestone within the lossless approach is partial distortion elimination (PDE/SpiralPDE) in which distortion is the difference between the block to be coded and the candidate prediction block. In this paper we show that contributions to distortion can be reliably estimated using the Taylor series expansion. The approximation method is then used to derive eight new PDE–based algorithms in which the matching order depends on the magnitude of the estimated distortion contributions. Exhaustive comparisons using several, widely different, video sequences show that these algorithms reduce the total encoding time by up to 20% with respect to SpiralPDE, while the computation for motion estimation is reduced by about 30%. The proposed algorithms are also compared with other PDE–based lossless approaches known in literature and there is a significant gain over all of them.