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. Then, (ii) 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 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\%. Finally, (iii) 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.

New Sorting-Based Lossless Motion Estimation Algorithms and a Partial Distortion Elimination Performance Analysis

QUAGLIA, Davide
2005-01-01

Abstract

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. Then, (ii) 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 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\%. Finally, (iii) 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/233589
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 65
  • ???jsp.display-item.citation.isi??? 52
social impact