Motion estimation algorithms for video compression through successive elimination

Trudeau, Luc (2017). Motion estimation algorithms for video compression through successive elimination. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (525kB) | Prévisualisation

Résumé

Recent advancements in the processing capabilities of handsets, tablets and computers have resulted in a considerable increase of the demand for improved visual quality and higher resolution video content. To meet these demands, modern video compression standards, like H.264/advanced video coding (AVC) and H.265/high efficiency video coding (HEVC), have considerably increased the solution space of motion estimation (ME). Modern motion estimation algorithms only consider a very small part of the solution space, which results in suboptimal solutions that not only reduce visual quality but also increase the bit rate.

Approaches like the successive elimination algorithm (SEA) and its derivatives show great potential in reducing the solution space of ME without reducing visual quality or increasing the bit rate. However, SEA is rarely used in modern encoders, because it has not been adapted to modern coding tools and, since, historically, it was intended for exhaustive searches, not suboptimal ones. In this thesis, we propose multiple algorithms to improve the efficiency of SEA and we also tailor SEA to suboptimal search algorithms.

Our first proposition is a cost-based search ordering pattern for SEA, which is based on new insight that conventional search orderings can weaken the filtering criterion of SEA in a rateconstrained context. On average, for the H.264 reference software encoder, the number of sum of the absolute differences (SAD) operations is reduced by 2.86%. For smaller block sizes, this can exceed 10%.

Our second contribution is the sorted subset approach, a dynamic search ordering for SEA that avoids performing unnecessary cost function evaluations. On average, it reduces SAD operations by 3.66% for the HEVC reference software encoder. For smaller block sizes, the average rises to 8.06%.

Our third contribution to SEA is a fast cost-based search ordering algorithm. It decreases the number of SAD operations by approximately 3%. It allows for a new early-termination criterion which only requires performing 36% and 46% of block-matching loop iterations for Random Access and Low Delay respectively. This new solution is more than five times faster than the HEVC HM encoder in full search mode, without impact on visual quality or rate.

Our fourth contribution applies more generally to motion estimation and allows for an enhanced rate constraint. This rate constraint reuses information from the partitioning ME algorithms. When combined with the rate-constrained successive elimination algorithm (RCSEA) in the HEVC HM encoder reference software, the number of SAD operations drops by an average of 94.9%, resulting in an average speedup of 6.13x in full search mode.

Finally, our fifth contribution, is the multi-level rate-constrained successive elimination algorithm (ML-RCSEA) a derivative of the SEA designed to be used with the suboptimal ME algorithm implemented in the HEVC reference software encoder, the TZ-Search. It reduces the motion estimation time by approximately 45% contributing to an average encoding time reduction of about 7% without impact on visual quality or rate.

Titre traduit

Algorithmes d’estimation du mouvement pour la compression vidéo avec élimination successive

Résumé traduit

Les récents progrès dans les capacités de traitement des appareils mobiles, des tablettes et des ordinateurs ont entrainé une augmentation considérable de la demande pour une meilleure qualité visuelle ainsi que pour du contenu vidéo de haute résolution. Pour répondre à ces exigences, les normes de compression vidéo modernes, comme H.264 et H.265, ont considérablement augmenté l’espace de recherche des algorithmes d’estimation de mouvement. Cependant, les algorithmes d’estimation de mouvement modernes n’évaluent qu’une très petite partie de l’espace de recherche; ce qui se traduit par des solutions sousoptimales qui réduisent la qualité visuelle et augmentent le débit binaire.

Des approches telles que l’élimination successive et ses dérivées présentent un grand potential dans la réduction de l’espace de recherche sans pour autant réduire la qualité visuelle ou augmenter le débit binaire. Cependant, l’élimination successive est rarement implémentée dans les encodeurs modernes, car elle n’a pas été adaptée aux outils de codage modernes et étant donné qu’historiquement, elle a été conçue pour la recherche exhaustive, et non pas pour les algorithmes de recherche sous-optimaux. Dans cette thèse, nous améliorons l’efficacité des algorithmes d’élimination successive. De plus, nous proposons une version sur mesure de l’élimination successive destinée aux algorithmes de recherche sous-optimaux.

Notre première proposition est un patron de recherche basé sur le cout des vecteurs de mouvement. Ce patron repose sur le concept innovateur que, dans un contexte où le debit binaire est contraint, les ordonnancements conventionnels peuvent affaiblir le critère de filtrage de l’élimination successive. En moyenne, pour l’encodeur logiciel de référence H.264, on observe une réduction du nombre d’opérations de sommation de la différence absolue de 2,86%. Pour les blocs de plus petite taille, cela peut dépasser 10%.

Notre deuxième contribution est l’approche du sous-ensemble trié. Il s’agit d’un ordonnancement de recherche dynamique permettant d’éviter d’évaluer des candidats inutilement. En moyenne, il réduit le nombre d’opérations de sommation de la différence absolue par 3,66 % pour l’encodeur logiciel de référence H.265. Pour les petites tailles de blocs, la moyenne augmente à 8,06 %.

Notre troisième contribution est un algorithme rapide pour générer des ordres de recherché basés sur le cout des vecteurs de mouvement. Il diminue le nombre d’opérations de summation de la différence absolue d’environ 3%. De plus, ceci permet l’emploi d’un nouveau critère de terminaison anticipée. Ce dernier nécessite d’effectuer uniquement 36 % à 46 % des iterations de la boucle d’appariement de blocs pour les conditions de tests Random Access et Low Delay respectivement. Cette nouvelle solution est plus de cinq fois plus rapide que la configuration de recherche exhaustive de l’encodeur logiciel de référence H.265, sans impact sur la qualité visuelle ni sur le débit binaire.

Notre quatrième contribution s’applique plus généralement à l’estimation du mouvement et permet une contrainte plus accrue du débit binaire. Cette contrainte réutilise l’information des algorithmes d’estimation du mouvement appliqués lors du partitionnement d’un bloc. Lorsque combinée à l’élimination successive, le nombre d’opérations de sommation de la différence absolue chute en moyenne de 94,9 %, résultant en une accélération moyenne de 6.13x comparativement à la configuration de recherche exhaustive de l’encodeur logiciel de référence H.265.

Finalement, notre cinquième contribution est l’élimination successive multi-niveaux contrainte par le débit binaire. Il s’agit d’une dérivée de l’élimination successive conçue pour être utilisée avec l’algorithme d’estimation du mouvement sous-optimale que l’on retrouve dans l’encodeur logiciel de référence H.265, le TZ-Search. Il réduit le temps d’estimation du movement d’environ 45 % contribuant à une réduction moyenne du temps d’encodage d’environ 7 % sans impact sur la qualité visuelle ni sur le débit binaire.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Thesis presented to École de technologie supérieure in partial fulfillment for the degree of doctor of philosophy". Comprend des références bibliographiques (pages 115-118).
Mots-clés libres:	compression vidéo, estimation du mouvement, successive elimination algorithm (SEA), multilevel successive elimination algorithm (MSEA), rate-constrained successive elimination algorithm (RCSEA), high efficiency video coding (HEVC), advanced video coding (AVC)
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Coulombe, Stéphane
Codirecteur:	Codirecteur Desrosiers, Christian
Programme:	Doctorat en génie > Génie
Date de dépôt:	20 janv. 2021 14:01
Dernière modification:	20 janv. 2021 14:01
URI:	https://espace.etsmtl.ca/id/eprint/1923

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt