Etude et test des algorithmes d'estimation de mouvement en MPEG

PLAN

● Techniques de compression video MPEG.● Traitement des redondances temporelles:

algorithmes d'estimation de Mouvement.● Test des implémentations DivX

– Protocole– Mise en oeuvre– Résultats– Interpretation

Introduction:Pourquoi la compression Video ?

● Absence de compression inconcevable– Exemple pour une qualité Télévision analogique:

● Image 640*480 @25 Images / sec.● profondeur de pixels: 24 bits● Total: 22 Mo/s

● Compression avec pertes nécessaire, utilisant les redondances spatiales et temporelles

● MPEG4 (dans la pratique: divx): 64 Ko/s ; facteur de compression = 350

Techniques de compression MPEG: Sous échantillonnage

● Passage de la base RGB en YUV.● Perception humaine moins sensible à la

chrominance.● Codage en 4:2:0● Compression: 2

Techniques de compression MPEG:exploitation de la redondance spatiale● Découpage de l'image en Macroblocs de 16*16

pixels, puis en blocs de 8*8 pixels● Compression des blocs en DCT (Discrete

Consine Transform) pour le MPEG1 et 2, ondelettes pour le MPEG4.

● But de ces transformées: sous échantillonnage des fréquences basses.

● Puis codage VLC et RLE.

Techniques de compression MPEG:exploitation de la redondance temporelle

● 3 types d'images:● Intra frame (I) ou Key-frame: image entière● Predictive Frame (P): codage en fonction d'une image

précédente.● Bidirectionnal frame (B): codage en fonction de deux

images (I ou P).

● Images P et B générées grâce à l'estimation de mouvement.

Estimation de mouvement:Principe

● Pour le codage des images P et B– Recherche de blocs carrés

de pixels les 'plus ressemblants' dans l'image précédente

– Critères de ressemblance à minimiser: SAD (Sum of absolute difference) sur la luminance.

Compensation de mouvement

● Plutot qu'un bloc d'image 8*8, on transmet:– le vecteur de mouvement du bloc– Bloc 8*8 contenant l'erreur résiduelle entre les deux

blocs, encodée en DCT. ● Décodage: on compense l'image précédente grâce

aux vecteurs de mouvement et aux erreurs résiduelles.

● Comment trouver les blocs ?

Techniques pour la recherche de mouvement

● Comment trouver les blocs ressemblants?

● Full Search: recherche exhaustive– Optimal: on trouve

forcément le meilleur bloc

– Mais: très lourd

Estimation de mouvement:Three Step Search

– Recherche d'une direction: test sur 9 valeurs en partant du vecteur (0,0).

– Nouvelle recherche avec un rayon plus faible à partir du minimum précedent.

– 3e recherche avec un rayon encore plus faible.

● Rapide mais peu précis, possibilité de minimum locaux.

Estimation de mouvement:Méthode 2D-logarithmique

– Recherche sur 5 points à partir du centre à une distance D.

– Déplacement selon le minimum.

– Réduction du rayon de recherche à log D quand le minimum tombe au centre ou sur un coté.

– Minimums locaux

Estimation de mouvement:diamond based algorithm

– Recherche du déplacement médian en fonction des blocs connexes.

– Critère sur 9 points disposés en diamant. Déplacement selon le minimum.

– Utilisation d'un deuxième diamant plus petit si minimum au centre.

Techniques de block Matching:PMVFAST

– Recherche du déplacement maximum des blocs connexes. Mouvement estimé petit, moyen ou grand.

● Petit: on utilise le petit diamant pour la recherche.● Moyen: on utilise le grand diamant 1 seule itération.● Grand: on utilise le grand diamant:

– Tant que le minimum n'est pas au centre, on se déplace en direction du minimum.

– Quand le minimum est trouvé au centre, deuxième recherche avec le petit diamant.

Estimation de mouvement en mpeg-4

● MPEG-1 et 2: block matching sur des blocs réguliers

● MPEG-4: block matching sur des formes quelconques– Segmentation de l'image– Plus adapté aux images réelles

● Gain en compression: 10 %● Gain en qualité visuelle: 100%

Comparaison avec/sans segmentation

– Exemple: quadtree● Moins de motion vector: gain en compression● Plus de précision: gain en qualité visuelle

Test des implémentations

● But des tests: relation algorithme de block matching - Qualité d'image

● 3 implémentations testées:– Xvid: algorithme PMVFAST– Ffmpeg: méthode 2Dlogarithmique– DivX4: Diamond based algorithm

Protocole de test

● Comparaison des images issues des flux encodés, non encodés.

● Permet d'estimer les pertes engendrées par l'encodage.

Mise en oeuvre● Outils de test:

– Encodage: transcode, encodage en deux passes– Calcul des différences: PIL (Python Image Library)

● Critère de différences d'images: Moindres carrés sur la luminance:

Exemple: Différence entre deux images

Moindres carrés: résultats

● Critère des moindres carrés sommé pour toutes les images d'un flux

● Résultats peu pertinents pour les séquences lentes: valeurs proches, pas d'information sur la nature des erreurs.

● Solution: visualiser la répartition des erreurs

Répartition des erreurs

● Répartition des erreurs: histogrammes des erreurs

● Somme pour toutes les images du flux

Répartition d'erreur: Résultats

● Répartion interessante● Comparaison difficile● Solution: erreur

relative entre les implémentations

Comparaison des répartitions d'erreur

● Résultats pertinents● Inversion

petites/grosses erreurs● Différences selon le

type de séquence

Interpretation des résultats

● Xvid et PMVFAST– Performant, peu de grosses erreurs

● DivX4: 2Dlog + Quarter pixel– Excellent pour les petites erreurs, mais...

● FFmpeg: Diamond based– Compromis

Conclusion

● Beaucoup d'autres tests possibles sur les codecs divx: – Temps d'encodage– CPU au décodage

● Étude MPEG très interessante par sa diversité.● Développement du MPEG4 très rapide.