- Somme des différences absolues
-
La Somme des différences absolues ou SAD pour Sum of absolute differences est un algorithme simple, utilisé dans la compression vidéo afin de trouver une corrélation entre les blocs ou macroblocs d'une image. Elle est déterminée en calculant la différence absolue entre chaque pixel dans le bloc d'origine et le pixel correspondant du bloc ciblé. Ces différences sont additionnées pour créer une mesure simple de similiarité du bloc, la norme L1 de l'image des différences.
La somme des différences absolues peut être utilisées pour différents objectifs : la reconnaissance d'objet, la génération de carte de disparité pour les images stéréo et l'estimation de mouvement pour la compression vidéo.
Sommaire
Exemple
L'exemple ci-dessous utilises la SAD pour identifier quelle partie d'une image cible est la plus proche de l'image du modèle. Dans cet exemple, le modèle est un bloc de taille 3x3 pixels tandis que l'image cible est de dimension 3x5 pixels. Chaque pixel est représenté par une valeur entière de 0 à 9.
Modèle Image cible 2 5 5 2 7 5 8 6 4 0 7 1 7 4 2 7 7 5 9 8 4 6 8 5
Il existe exactement trois positions uniques à l'intérieur de l'image cible où le modèle peut s'adapter: le côté gauche de l'image, le centre et le côté droit. Pour calculer les valeurs de SAD, on détermine d'abord la différence absolue entre chaque pair de pixel correspondante. Pour la première position: on doit calculer la différence entre 2 et 2 soit 0, 4 et 1 soit 3, 7 et 8 soit 1, etc...
Si le calcul est réalisé pour les trois positions du modèle, on obtient les valeurs suivantes:
Gauche Centre Droite 0 2 0 5 0 3 3 3 1 3 7 3 3 4 5 0 2 0 1 1 3 3 1 1 1 3 4
La SAD est obtenue pour chaque cas en additionnant les valeurs des blocs soit 20 pour le cas à gauche, 25 pour le cas au centre et 17 pour le cas à droite. A partir de ces trois valeurs de SAD, le bloc le plus similaire au bloc d'origine peut être déterminé. Plus la somme est élevée et plus la distorsion entre les images est importance. Par conséquent, la SAD la plus faible est la meilleure. Dans cet exemple, il s'agit du cas à droite avec une valeur de 17.
Comparaison avec les autres critères d'évaluation
Reconnaissance d'objet
La SAD fournit une manière simple d'automatiser la recherche d'objet au sein d'une image, mais elle peut ne pas être fiable à cause des effets des facteurs contextuels comme les changement de luminosité, de couleur, d'angle de vision, de taille ou de forme. La SAD peut être utilisé en complément avec d'autres méthodes de reconnaissance d'objets. Par exemple, il existe la détection de contours qui augmente la fiabilité des résultats.
Compression vidéo
La SAD est un critère d'évaluation extrêmement rapide due à sa simplicité. En effet, elle permet d'obtenir une mesure pertinente en prenant en compte tous les pixels d'un bloc. Son utilisation dans l'estimation de mouvement pour un encodage de inter-trame est efficace car elle permet de cibler rapidement quel bloc de l'image de référence est similaire au bloc courant à encoder et qui ne l'est pas en chiffrant la distorsion. La SAD est aussi facilement parallélisable étant donné que l'analyse de chaque pixel peut être réalisée séparément, ce qui rend l'implémentation facile à optimiser avec des instructions en assembleur tels que MMX et SSE2. Une fois le bloc candidat identifié, le dernier raffinement de l'estimation de mouvement est souvent réalisé avec d'autres critères de mesures plus lents mais plus précis en termes de qualité et qui prennent en compte la perception de l'œil humain. Parmi ces mesures, il existe la somme des différences absolues transformées ou SADT, la somme des carrés des différences ou SSD et l'optimisation débit-distorsion.
Références
- (en) E. G. Richardson, H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, Chichester, John Wiley & Sons Ltd., septembre 2003 (ISBN 0-470-84837-5)
- ThomasWiegand, Gary J. Sullivan, « “Overview of the H.264/AVC Video Coding Standard » sur http://ip.hhi.de, IEEE, 2003. Consulté le 19 janvier 2011
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sum of absolute differences » (voir la liste des auteurs)
Annexes
Articles connexes
Liens externes
Wikimedia Foundation. 2010.
