Motion estimation algorithms for video compression through successive elimination

Résumé

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.

Date	11 août 2017
langue originale	Anglais américain
Établissement diplômant	École de technologie supérieure
Superviseur	Stéphane Coulombe (Directeur(-trice)) & Christian Desrosiers (Codirecteur(-trice))