New sorting-based lossless motion estimation algorithms and a partial distortion elimination performance analysis

• Published in: IEEE transactions on circuits and systems for video technology 2005-02, Vol.15 (2), p.210-220
• Main Authors: Montrucchio, B., Quaglia, D.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Blocking; Distortion; Distortion Taylor expansion; Encoding; fast block matching; full search; Information analysis; Lossless; lossless motion estimation; Matching; Measurement standards; Motion estimation; Motion measurement; Partial differential equations; partial distortion elimination (PDE) bounds; Performance analysis; Phases; Searching; Sorting; Studies; Taylor series; Testing
• ISSN: 1051-8215; 1558-2205
• DOI: 10.1109/TCSVT.2004.841689

In video encoding, block motion estimation represents a CPU-intensive task. For this reason, many fast algorithms have been developed to improve 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, (i) we analyze distortion behavior from local information using the Taylor series expansion and show that our general analysis includes other previous similar approaches. (ii) Then, we propose two full-search (lossless), fast-matching, block motion estimation algorithms, based on the PDE idea. The proposed algorithms, called fast full search with sorting by distortion (FFSSD) and fast full search with sorting by gradient (FFSSG), sort the contributions to distortion and the gradient values, respectively, in order to quickly discard invalid blocks. Experimental results show that the proposed algorithms outperform other existing full search algorithms, reducing by up to 20% the total CPU encoding time (with respect to SpiralPDE), while the computation strictly required by the motion estimation is reduced by about 30%. (iii) Finally, we experimentally find an operational lower bound (based on standard test sequences) for the average number of checked pixels in the PDE approach, which measures the performance of the searching and matching phases. In particular, SpiralPDE achieves performances very close to the searching phase bound, while there is still a remarkable margin on the matching phase. We then show that our algorithms, aimed at improving the performances of the matching phase, achieve interesting results, significantly approaching this margin.