Home ]

Etude et test des normes et implémentations MPEG4

Clément Chatelain



Remerciements

Je tiens à remercier eProcess pour m'avoir permis de faire ce stage qui a parfaitement répondu à mes attentes, tant pour l'intérêt qu'il présentait que pour la validation de mes diplômes. Je remercie toute l'équipe pour sa disponibilité et ses conseils, pour toutes les connaissances qu'ils m'ont transmises, ainsi que pour leur bonne humeur.

Table des matières
Introduction
1. L'entreprise: eProcess
2. MPEG: normes, compression et application
2.1. Principes de compression du MPEG 1
2.1.1. Sous échantillonage
2.1.2. Utilisation de la redondance spatiale
2.1.3. Utilisation de la redondance temporelle
2.2. Principes du MPEG 2
2.2.1. Différences entre MPEG1 et MPEG2
2.2.2. Encodage en 2 passes
2.3. Principes du MPEG4
2.3.1. Extension des normes MPEG1 et MPEG2
2.3.2. Amélioration de la compression
2.4. Etude industrielle du MPEG4 et du DivX
2.4.1. Les courants normatifs du MPEG-4
2.4.2. Les implémentations DivX
2.4.3. Décodage hard du MPEG-4
2.4.4. Diffusion du MPEG 4
2.4.5. Conclusion de l'étude industrielle
3. Estimation de mouvement
3.1. principe de l'estimation de mouvement
3.2. Estimation de mouvement par bloc carré régulier
3.2.1. Calcul de l'erreur résiduelle
3.2.2. Compensation de mouvement
3.3. Algorithmes de Block Matching
3.3.1. Méthode Full Search (FS)
3.3.2. Méthode Three Step Search (TSS)
3.3.3. Recherche en Diamant
3.3.4. Algorithmes 2D-logarithmiques
3.3.5. méthode PHODS
3.3.6. Zonal Based Algorithm
3.4. Estimation de mouvement par segmentation
3.4.1. Principe
3.4.2. Algorithmes de segmentation pour la compensation de mouvement
4. Test de Qualité des implémentations DivX
4.1. Protocole de test
4.1.1. mesure de l'erreur
4.1.2. Algorithmes testés
4.2. mise en oeuvre des tests
4.2.1. Compression des flux
4.2.2. Comparaison des flux
4.3. Résultats
4.3.1. Moindres carrés
4.3.2. Histogrammes des erreurs
4.3.3. Séquence tennis, comparaison de l'algorithme Xvid à ffmpeg et DivX4.
4.3.4. Séquence mobile, comparaison de l'algorithme FFmpeg à Xvid et DivX4.
4.3.5. Séquence flower, comparaison de l'algorithme DivX4 à Xvid et FFmpeg.
4.4. Interpretation des résultats
4.4.1. role du quarter-pel (quart de pixel)
4.4.2. Conclusions sur les algorithmes PMVFAST et Predictive Diamond Search
4.4.3. Méthode 2Dlogarithmique
4.5. Prospectives
Conclusion
Bibliographie
A. Annexes: Histogrammes des erreurs
A.1. Xvid
A.2. FFmpeg
A.3. DivX4
B. Annexe: fichier de script python
B.1. imagediff.py: différence de deux images et résultat dans une troisième
B.2. histo.py: affichage de l'histogramme d'une image
B.3. somme.py
Liste des tableaux
4-1. erreurs des moindres carrés
Liste des illustrations
2-1. Sous échantillonnage en 4:2:0
2-2. Corrélation des pixels dans un bloc
2-3. Bloc 8*8 pixels avant DCT
2-4. Bloc 8*8 pixels après DCT
2-5. Algorithme zigzag
2-6. Coefficients de la DCT
2-7. Formule analytique de la DCT
2-8. Transformée DCT inverse
3-1. Recherche de pattern dans l'image précédente
3-2. Erreur résiduelle entre deux blocs de 16*16 pixels
3-3. Méthode Full Search: Nombre d'instruction par seconde
3-4. Méthode Full Search: Fenêtre de recherche
3-5. Approximation de l'erreur (cf sad.pdf)
3-6. Algorithme "three step search":
3-7. Algorithme "Diamond search":
3-8. Exemple de recherche 2D-logarithmique
3-9. Compensation de mouvement avec segmentation
3-10. Vecteurs de mouvement avec des blocs de taille fixe
3-11. Vecteurs de mouvement avec des blocs découpés en quadtree
4-1. Protocole de test
4-2. Critère des moindres carrés
4-3. Différence de deux images d'un même flux, espacées de 15 images.
4-4. Différence (amplifiée) entre deux images encodées avec des codecs différents
4-5. Exemple d'histogramme avec gracePlot
4-6. Différence d'histogrammes
4-7. Sommes d'histogrammes
4-8. Comparaison de l'erreur issue de Xvid sur la séquence tennis:
4-9. Comparaison de l'erreur issue de FFmpeg sur la séquence mobile:
4-10. Comparaison de l'erreur issue de DivX4 sur la séquence flower:
A-1. Xvid, séquence tennis
A-2. Xvid, séquence susie
A-3. Xvid, séquence mobile
A-4. Xvid, séquence flower
A-5. Ffmpeg, séquence tennis
A-6. Ffmpeg, séquence susie
A-7. Ffmpeg, séquence mobile
A-8. Ffmpeg, séquence flower
A-9. Divx4, séquence tennis
A-10. Divx4, séquence susie
A-11. Divx4, séquence mobile
A-12. Divx4, séquence flower
Liste des exemples
2-1. exemple d'analyse d'un fichier MPEG1 (durée: 3,44 secondes)

Introduction

Jusqu'à l'apparition de la norme MPEG4, les normes MPEG1 et MPEG2 régissaient les formats vidéo. Le MPEG1 permettait une qualité vidéo médiocre à un faible débit, le MPEG2 une très bonne qualité avec un débit énorme. Le MPEG4 offre - d'une part d'atteindre des débits bas avec une très bonne qualité grace à des améliorations des algorithmes de compression - d'autre part d'étendre la norme MPEG "vidéo" à un format plus général permettant, entre autre, l'interactivité.

Bien que le MPEG4 "interactif" ne soit pas opérationnel, il existe des implémentations partielles MPEG4: les algorithmes divx qui implémentent la seule partie vidéo. L'étude des formats MPEG1, MPEG2 et MPEG4 nous conduira à nous interesser aux méthodes de compression utilisées dans les nouveaux algorithmes, et aux tests de ceux ci sur des implémentations divx existantes.

On présentera les trois normes MPEG, les algorithmes de compression associés ainsi qu'une étude industrielle de la norme MPEG4. Puis on reviendra précisement sur les techniques de compression liées à la redondance temporelle, pierre angulaire de la compression divx. Cette compression, basée sur l'estimation de mouvement, est essentielle pour une bonne compression et surtout pour une bonne qualité d'image du flux compréssé. La dernière partie de ce rapport proposera un protocole testant trois implémentations opensource pour mettre en relation la qualité visuelle avec l'algorithme d'estimation de mouvement utilisé.


Chapitre 1. L'entreprise: eProcess

eProcess est une société anonyme d'une quinzaine de personnes créée en aout 1999 et basée à Montpellier. C'est un éditeur logiciel de produits multimédia pour systèmes embarqués. Elle a consacré sa première année d'existence à la recherche, ce qui lui a permis de cibler son activité: développement d'une technologie logicielle modulaire permettant le traitement d'information multimédia.

eProcess a développé une plateforme modulaire baptisée "COMEDIA" (COMponents for multiMEDIA) qui permet, en fonction de la demande du client, d'ajouter des modules nécessaires à différentes applications multimédias. On aura donc un module "vidéo", un module "internet", un module "mp3", etc... L'application principale prévue est la VOD: Vidéo On Demand, installée par exemple dans des chambres d'hotel. Tous ces modules sont placés sur un système d'exploitation réduit à base de noyau linux développé par eProcess: enux. Cette plateforme s'intègre en environnement embarqué: principalement des set top boxes (boitier qu'on "pose sur un poste de télévision").

La diffusion des films sur les set top boxes se fait via le réseau; d'où l'intérêt d'un format tel que le MPEG4 qui possède des débits beaucoup plus faibles que le MPEG2. Les différentes études menées lors de mon stage ont permis de mieux connaitre le MPEG4 et ses implémentations en vue d'intégrer la décompression MPEG4 à la plateforme COMEDIA.


Chapitre 2. MPEG: normes, compression et application


2.1. Principes de compression du MPEG 1

L'algorithme MPEG-1 [1] fut originellement conçu pour des taux de transfert de CD simple vitesse (1,5 Mbit/s soit 200 Ko/s). Il présente une qualité semblable au VHS.

Plus qu'une compression particulière, c'est la compostion de plusieurs algorithmes de compression qui font la qualité du MPEG. Nous voyons dans cette partie les principes du MPEG1, qui sont repris ou améliorés dans les versions suivantes.


2.1.2. Utilisation de la redondance spatiale


2.1.2.1. Principe de la DCT

La DCT s'applique à des tableaux de N * N pixels. On effectue une transformation de l'image I(x,y) en fréquence pour obtenir F(u,v). Voyons comment cette transformation peut favoriser une compression efficace.

Si on représente la corrélation entre les pixels voisins d'un bloc 8*8 d'une image, on obtiendra un nuage de points regroupé le long d'une droite. En effet, deux pixels voisins ont de fortes chances de posseder des attributs similaires.

Le but de la transformation en fréquence est de décorréler ces pixels, ce qui concentre l'information de l'image dans un nombre réduit de coefficients fréquentiels. Seuls quelques coefficients contiennent l'information globale du bloc. Ce sont les hautes fréquences qui correspondent aux contours d'une image. Ces coefficients sont appelés AC et sont placés en haut à gauche de la matrice d'arrivé. Les autres coefficients possèdent une valeur faible ou nulle. Ces basses fréquences sont les textures et sontappelés les coefficients DC.

C'est à ce niveau qu'intervient la compression: Les faibles valeurs sont délibéremment codées sur un nombre très restreint de bit. La quantification tronquera les nombres à virgule en valeur entières. En effet le codage en virgule flottante est gourmant en espace mémoire. Cette sous quantification n'affecte que peu la quantité d'information. C'est un codage "entropique", c'est à dire que le nombre de bit alloué pour chaque composante fréquentielle dépend de la quantité d'information qu'elle contient.

Cette compression est donc basée sur deux principes:

On voit en haut à gauche de la matrice les valeurs qui concentrent l'énergie des pixels. Cette matrice est ensuite parcourue avec l'algorithme "zig-zag", dont l'intêret est de lire les valeurs des plus importantes aux plus faibles.

Les grandes valeurs (AC) sont très bien quantifiées, alors que les valeurs plus faibles (DC) sont sous échantillonnées et codées sur peu de bits. Une erreur sur les faibles valeurs altère peu les valeurs du bloc lors de la transformée inverse.


2.1.3. Utilisation de la redondance temporelle

L'estimation de mouvement va rechercher les parties d'une image identiques ou ressemblantes dans une autre image déja codée. Au lieu de recoder cette partie, il suffira de faire une référence au morceau d'image ressemblant. Le gain en compression est donc très interessant. En MPEG1, l'estimation de mouvement est effectuée sur des blocs carrés et réguliers. Elle sera faite de manière plus complexe dans les autre formats MPEG2 et MPEG4. L'estimation de mouvement constitue la partie de la compression la moins figée: il existe de nombreux algorithmes présentant des qualités de vitesse, qualité et robustesse variées. On reviendra plus précisement sur l'estimation de mouvement dans la partie suivante de ce rapport.

Pour coder les redondances temporelles, le MPEG distingue trois types d'images:

La fréquence des images I est générallement réglable lors de l'encodage. Un faible taux d'image I permet une compression efficace mais une faible résistance aux erreurs: si une erreur survient sur une Image I, toutes les images P et B faisant référence à cette frame seront afféctées. Par exemple les flux destinés à être diffusés par satellite sont exposés aux erreurs de transmission et requierent un fort taux d'image I.

La taille des images P et B étant nettement inférieure à celle des images I, on va chercher à en coder le plus possible. Un critère d'estimation de mouvement basé sur la luminance permet de quantifier la différence existante entre deux frames. On décide de recoder une image I lorsque ce critère est trop important.


2.2. Principes du MPEG 2

Le MPEG2 [1] permet une très bonne qualité de vidéo, nettement supérieure au MPEG1: le framerate est passé à 30 Image par secondes, la résolution est de 720*576 et le débit de 15 Mbit par seconde. L'application la plus connue du MPEG2 est le DVD.

Cette norme est la continuation logique de la norme MPEG-1. Ainsi elle reprend les memes specifications et conserve la compatibilité entre les deux médias. De nouveaux concepts ont cependant été mis en avant.


2.2.1. Différences entre MPEG1 et MPEG2


2.2.2. Encodage en 2 passes

Nous avons vu que le mPEG2 adaptait son bitrate à la complexité de l'image. C'est l'encodage en deux passes qui permet cela [2]. L'encodage en deux passes se déroule de la manière suivante:

  • Première passe: encodage à un bitrate constant. L'algorithme accumule des statistiques sur la complexité des images. Pour chaque image, on fait d'une part une estimation du mouvement: on calcule les variations de luminance d'une image sur l'autre. C'est "l'activité du macrobloc". D'autre part, on estime la complexité des textures. La somme des deux valeurs constitue la complexité de l'image.

  • Deuxième passe: redistribution des bits diponibles sur chaque frame en fonction de la complexité mesurée lors de la première passe. Le but de cette allocation de bit est d'avoir non pas un birate constant mais une qualité visuelle constante. Il est évident qu'une scène très précise et rapide nécessite plus de bits qu'une scène très simple.

l'encodage en deux passes n'est toutefois pas imposé; il est possible d'encoder en temps réel.


2.3. Principes du MPEG4

2.3.1. Extension des normes MPEG1 et MPEG2

Créé en 1998, la norme MPEG4 [1, 3] a pour but de trouver un compromis entre qualité et taille des fichiers. En effet, les flux MPEG1 possédaient une taille raisonnable, mais une mauvaise qualité. Inversement le MPEG2 possède une très bonne qualité mais la taille des fichiers est énorme, en particulier si l'on veut faire circuler ceux ci sur un réseau. Les fichiers MPEG4 sont prévus pour pallier ces deux problèmes, avec un bitrate de 64kBit/s.

Mais au dela de la compression, la norme MPEG4 propose également une nouvelle organisation des flux audio-vidéo, orientée objet. La description des scènes se fait en séparant les objets vidéo ou audio, codés séparémment. Chaque objet pouvant alors interagir avec un autre et évoluer dans différents plans. Un personnage qui parle peut être décomposé en un objet vidéo "personne", et un objet audio "voix", les deux étant synchronisés et ajoutés par dessus l'objet "décors" placé en second plan. Le but de cette décomposition est d'organiser les scènes en mediaobject sur lesquels on peut agir séparemment: codage, édition, transparence, etc. La suppression de la précédente personne est possible, et on arrive alors à la notion d'interactivité, actuellement très prisée. Un autre avantage de ce type de description est la possibilité d'appliquer des techniques de codage adaptées aux différents objets de la scène. Le bitrate et le framerate seront fixés en fonction du besoin.

La norme MPEG4 ne s'arrète pas à la décomposition des scènes en objets, elle propose également les techniques suivantes:

  • division des images en plans [4]. On peut alors séparer les mouvements des différents plans. Par exemple on peut reconstituer le décor de fond, et effectuer des zooms avec des angles différents suivant les scènes. Il suffit de coder une seule fois le décor.

  • La décomposition des visages en maillage fil de fer et texture. On a alors un gain en compression.

  • La possibilité d'insérer des objets synthétiques.

  • Une gestion des profils très précise qui prend en compte les aspects interactivité et diffusion sur un réseau.


2.4. Etude industrielle du MPEG4 et du DivX

Présentation du DivX

Outre les améliorations des algorithmes de compression, la norme MPEG-4 prévoit l'utilisation d'objets virtuels, la décomposition des objets 3D en maillage fil de fer et texture codée séparément, l'interactivité du film avec l'utilisateur, etc. Autant de concepts novateurs voire révolutionnaires, mais très ambitieux à l'heure actuelle. On remarque de plus l'absence totale de contenu MPEG-4, c'est à dire de fichier video contenant des objets synthétiques, des décompositions structurelles des objets, etc. D'où le constat: l'inexistence du MPEG4 dans l'industrie à l'heure actuelle.

Cependant la norme MPEG-4 se développe et trouve même une application très répandue: l'utilisation des algorithmes de compression pour la réduction de la taille des fichiers vidéo. C'est la compression DivX, qui est conforme à du MPEG-4 ISO visual simple profile ou advanced simple profil: un simple plan de video ne contenant pas d'objets synthétiques. Les algorithmes DivX ont remportés un grand succès en permettant de faire tenir un film sur un seul cd.

La norme MPEG-4 est très vaste et concerne de nombreux domaines tels que la compression et l'organisation de données, le transport d'information sur des réseaux, la gestion des droits et des licences, etc. D'où l'émergence de plusieurs normes ou organisations spécialisées dans les domaines d'applications du MPEG-4. Après avoir présenté ces courants, on s'intéressera dans cette partie aux implémentations existantes du DivX, puis aux solutions matérielles permettant le décodage de vidéo.


2.4.1. Les courants normatifs du MPEG-4

2.4.1.1. MPEG iso

Le courant MPEG 4 initial est celui du Moving Picture Expert Group appartenant au groupe ISO/IEC, créateur des normes MPEG1 et MPEG2. Ils sont les précurseurs de la norme MPEG4. [1, 3]

Le Moving Picture Expert Group ne définit pas d'algorithme d'encodage mais propose simplement des techniques de compression (sans les algorithmes) et la façon dont doit être agencé les données de vidéo, de son et de synchronisation dans le flux MPEG4.

Deux versions de la norme MPEG-4 ISO existent déja:

  • la version 1 approuvée en octobre 1998

  • la version 2 finalisée en décembre 1999

Les versions 3, 4 et 5 sont en cours.

La société MPEG LA travaille en collaboration avec le Moving Expert Picture Group pour représenter ses interêts commerciaux. MPEG LA s'occupe de la gestion des droits de la propriété intellectuelle et des licences du contenu MPEG-4.


2.4.1.2. MPEG-4 Industry Forum

Les principaux membres du MPEG-4 Industry Forum (M4IF) [6] sont: MPEG LA, Microsoft Corporation, Intel Corp., le Fraunhofer Institute IIS-A, DivXNetworks Inc., Motorola, etc (liste non exaustive). C'est une organisation à but non lucratif dont le but est "d'uniformiser la norme et l'utilisation du MPEG4 pour les développeurs, les prestataires de services et les utilisateurs". Le M4IF essaye de promouvoir le MPEG4 dans le milieu industriel et veille au passage du MPEG4 de la norme ISO à l'industrie.

Toutes les implémentations des sociétés membres travaillent donc en relation avec le M4IF, en particulier pour celle de DivXNetworks: DivX5. Le but du M4IF est d'avoir dans la pratique une normalisation des contenus, codeurs et décodeurs MPEG4.


2.4.1.3. ISMA: Internet Streaming Media Alliance

Ce consortium [7] est composé de Apple, Cisco, IBM, Philips, Sun Microsystems, et rassemble également la participation de AOL, Lucent, Dolby (son AAC), Sony, etc. On remarquera que toutes ces sociétés appartiennent également au M4IF. Le but de l'ISMA est de travailler sur les aspects de normalisation des transports de flux sur les réseaux, en particulier sur le streaming..

Ce consortium fournit une norme ainsi qu'un codec: Quicktime 6. Une version beta est diponible pour Mac et Windows; il est optimisé pour les processeurs Motorola G3 et G4. Selon Apple, tous les formats respectant le MPEG-4 iso pour la video et AAC pour l'audio devraient etre décodable par Quicktime 6. De même pour le MPEG-2 lors de la version finale.


2.4.2. Les implémentations DivX


2.4.2.1. le projet mayo

La première implémentation de l'algorithme DivX [8] fut développée en 1999 par Jérôme Rota à Montpellier. Celui ci a ensuite créé le project mayo, site regroupant les algorithmes opensource DivX ainsi que d'autres projets de player vidéo. Ce projet a sorti la première version du DivX: DivX 3.11 alpha, version illégale car piratée sur le codec Microsoft WMV vidéo codec. Une nouvelle version légale est sortie plus tard, remportant un très grand succès: l'agorithme DivX4 ou OpenDivX.

Puis une séparation s'est faite entre les développeurs initiaux du project mayo, désireux d'accelérer le développement des algorithmes, et d'autres personnes voulant continuer l'implémentation opensource.

D'où la création de la société DivXNetworks, reprenant l'activité commerciale des algorithmes en fermant les sources du DivX 4 et en lancant le DivX 5. D'autre part, le développement du codec opensource du projet mayo continue desormais sous le nom xvid. Le site du projet Mayo acceuille maintenant le projet Opendivx sans toutefois mettre à disposition les sources du codec.


2.4.2.2. DivXNetworks

DivXNetworks [9, 10] est donc issu du projet Mayo mais leurs algorithmes ont été complètement repris: ils ne sont pas basés sur le code openDivX. La dernière version du codec DivX est la version 5 qui se décline en deux versions:

  • DivX Video Software. L'utilisation de cet algorithme est gratuit tant qu'elle n'est pas à des fins commerciales. Deux exceptions toutefois: l'utilisation pour les réalisateurs de film ainsi que l'inclusion dans des packages est gratuite.

    Il utilise les I-VOP et P-VOP (Video Object Plane, en réalité des frames), permet l'encodage en plusieurs passes, 5 degrés prédéfinis de qualité d'encodage, la détection automatique de scènes (pour l'insertion d'image I), l'insertion automatique ou manuelle des I-frame. La quantification peut être faite en YUV 4.2.0, 24 ou 32 bits RGB, YUV2, UYVY ou YVYU. L'algorithme DivX 5 supporte le MPEG-4 simple profile.

    En outre, il fonctionne sur les plateformes Windows, linux, Mac OS et bientôt Pocket PC. DivXNetwork est basé sur le MPEG4 ISO mais est désormais membre du M4IF.

  • DivX Pro Video Software. Cette version est payante (30 Dollars US). A qualité égale, la taille des fichiers est inférieure de 25% avec DivX pro. Dans les améliorations par rapport à l'algorithme DivX, on retrouve les B-Video Object Plane, la global motion compensation et le quarter pixel. Il supporte donc le MPEG-4 advanced simple profile.

    Il existe pour cette version un Ad Suported Software nommé GAIN: Gator Advertising & Information Network permettant l'utilisation gratuite de DivX Pro Video Software et diffusant en contre partie de la publicité.

La version 5 de DivX contient encore des bugs. La version 4 est actuellement la plus répandue.


2.4.2.3. Xvid

Xvid [11] est également issu du projet Mayo, mais se différencie de DivX car il est open source. C'est la reprise de opendivx quand les sources de celui ci ont été fermées par DivXNetworks. Il présente les meilleures performances en terme de rapidité de compression. Il ne gère cependant pas les B frames ni la "global motion estimation". Xvid utilise l'algorithme PMVFAST pour la recherche de mouvement (Cf. Chapitre 3: Estimation de mouvement). Contrairement à DivX4, cette implémentation est en constante évolution et constitue la principale alternative aux algorithmes de DivXNetworks.

Il y a deux implémentations de l'algorithme Xvid: Koepi et Nick's codec. Ces algorithmes sont conformes au MPEG4 ISO simple profile.


2.4.2.4. FFmpeg

FFmpeg [12] est un autre projet opensource. Il contient deux parties:

  • FFmpeg: un codeur/décodeur mpeg4 qui supporte le MPEG4 simple profil (pas de B-pictures). Il offre la possibilité de convertir des flux vidéo d'un format à un autre, ou d'encoder en temps réel à 25fps en 352*288. Dans ce cas, les techniques de block matching sont très limitées et effectuent la recherche uniquement pour les motion vector (0,0). FFmpeg est multiformat: il manipule les fichiers MPEG1, H263, Real Video, MPEG4, DivX et MJPEG. Pour la compression en AVI, plusieurs méthodes d'estimation de mouvement sont disponibles: Full search, 2Dlog et PHODS.

  • FFserver: serveur de streaming permettant la diffusion de flux via HTTP. Malheureusement, FFserver ne gère que le program stream et non le transport stream. Il n'y a donc pas la possibilité de gérer la diffusion sur une connexion non fiable: . La diffusion est donc limitée à un réseau local.

Ce projet est récent, comporte moins de fonctionnalités que DivX ou Xvid, mais s'améliore très rapidement et la fonctionnalité serveur de streaming est intéressante.


2.4.3. Décodage hard du MPEG-4


2.4.4. Diffusion du MPEG 4

Le MPEG4, avec son fort taux de compression, est particulièrement bien adapté à internet, et permet sa diffusion en streaming. Plusieurs sociétés sont capable de diffuser du contenu MPEG4:

D'autres sociétés telles que Packet Video ou Emblaze travaillent également à des solutions de streaming à bas débit, en particulier à destination des téléphones mobiles.

La société MPEGLA, chargée de gérer les droits sur les détenteurs du brevet MPEG4, réclame 0,02$ par heure de streaming, et 0,25$ par produit équipé de la technologie MPEG4. MPEGLA était très critiquée au sein de l'ISMA à cause de ces tarifs jugés trop importants, mais la situation vient de se débloquer: les tarifs sont maintenus mais les conditions ont été assouplies. Les 0,25$ ne sont appliqués qu'à partir de 50000 exemplaires et il y a un plafond pour chaque société de 1000000 $ par an. Les solutions de RealNetworks et Apple n'étaient donc pas encore commercialisée mais ils devraient arriver rapidement sur le marché.

De son coté, Microsoft possède déja la technologie MPEG4 intégrée à son lecteur Windows média player depuis deux ans dans un format propriétaire: windowsMedia (wmv). Windows espère avoir une position de leader grâce à des taux de compression plus importants. En effet, selon Microsoft, WindowsMedia 8 permet de réduire de 40% le poids d'un fichier et compte encore l'améliorer de 20% avec WindowsMedia 9 (Corona).

On peut donc se demander si le marché va basculer du coté du format ouvert MPEG4 qui donne le choix au niveau des nombreux partenaires, ou bien du coté de Microsoft avec toute sa puissance commerciale et son format propriétaire. Toutefois, l'accord trouvé entre les différents consortium pour la gestion des licences MPEG4 est de bonne augure pour le MPEG4.

Le MPEG-4 sera t'il le standard pour le streaming ? (NetEconomie).


Chapitre 3. Estimation de mouvement


3.1. principe de l'estimation de mouvement

En MPEG les images ne sont pas toujours transmises en entier. La plupart du temps, on transmet les différences entre les images seulement. Dans un second temps, on compresse ces images par DCT (MPEG1, MPEG2) ou ondelettes (MPEG4) pour réduire le volume de données à traiter et stocker.

L'estimation de mouvement [13, 14] va encore améliorer cette technique de codage "delta" en réduisant les différences à coder entre deux images. Pour cela, on essaye pour une image donnée de "prédire" la suivante. En réalité on code l'image actuelle par rapport à des morceaux de l'image précédente. On fait une recherche sur l'image d'avant pour trouver des partitions ressemblantes. Puis on trouve le vecteur de mouvement pour la partition entière.

Gain pour la compression: on peut coder non pas la différence entre l'image actuelle et l'image suivante, mais la différence entre la prédiction de l'image suivante et l'image suivante. Si la prédiction est bonne, la différence sera très faible et donc la quantité d'information à transmettre aussi. De plus, plutot que de coder le mouvement pour chaque pixel, on code seulement le mouvement global de la forme, ainsi que les écarts à ce mouvement.

Dans un premier temps, on s'intéresse à l'estimation de mouvement par bloc carré et régulier qui présente l'avantage d'être simple et peu couteuse à mettre en oeuvre. On verra dans un second temps le block matching appliqué à des formes moins régulières.


3.2. Estimation de mouvement par bloc carré régulier

L'estimation de mouvement est utilisée pour le codage des images P et B pour exploiter la redondance temporelle présente entre deux images consécutives dans un flux vidéo.

En MPEG1, on utilise des méthodes de block matching avec un partitionnement carré régulier, c'est à dire qu'on va rechercher les mouvements de blocs carrés de pixels d'une image par rapport à l'image précédente. La taille des blocs à rechercher est importante: elle influe sur la qualité et la rapidité de compression: Des blocs de grosses tailles favorisent la compression car on a moins de vecteur de mouvement à transmettre, mais font perdre en qualité car les contours en mouvement sont altérés. Inversement, les petits blocs favorisent la qualité mais demandent un nombre plus important de vecteurs de mouvement à transmettre. Des blocs de 16*16 sont utilisés en MPEG1, qui présentent l'avantage d'être un bon compromis qualité/compression et une puissance de deux.

Le MPEG 2 fonctionne de la même manière mais permet eventuellement un partitionnement 16*8 pixels. On ne transmet pas le mouvement pour chaque pixel mais pour des carrés de pixels. Le type de mouvement se limitera aux translations. De l'image actuelle à la précédente, on cherche le bloc le plus ressemblant. Soit on trouve un bloc exactement identique, soit un bloc légèrement différent. Il ne restera qu'à transmettre les coordonnées de la translation entre la position du bloc le plus ressemblant dans l'image précédente et le bloc courant. Il faut également transmettre l'erreur résiduelle entre les blocs si elle existe.


3.2.1. Calcul de l'erreur résiduelle

Pour la recherche de blocs d'une image à la suivante, on va d'abord regarder si le bloc de mêmes coordonnées est identique. Dans le cas contraire, on mesure l'erreur résiduelle sur la luminance entre les deux blocs. Elle est généralement calculée par la somme des valeurs absolues des luminances des pixels du bloc.

Ce critère est appelé Sum of Absolute Difference (SAD). Le but étant de minimiser ce critère dans une zone au voisinnage du bloc. C'est une "mesure" de différence, aussi appelé matching criteria ou distortion function. En déplacant la fenètre de recherche du bloc aux alentours du bloc de départ, on trouve le bloc le plus ressemblant dans l'image précédente. On voit qu'il est nécessaire de définir le voisinnage: on fixe des seuils sur le critère pour ne pas trop se déplacer (seuil de maximum displacement). Les seuils sur le critère sont relachés au fur et à mesure que l'on s'éloigne de la position de départ.

Les autres critères tels que les moindres carrés, l'erreur absolue ou la projection intégrale sont également utilisés. Ils donnent des performances semblables mais la SAD est la moins complexe pour certaines architectures. Elle est utilisée dans tous les formats MPEG.

Cette opération de block matching est effectuée pour tous les blocs 16*16 pixels de l'image à coder. Pour un bloc donné, on ne trouve pas necessairement un bloc ressemblant. En effet on ne va pas coder un bloc par différences si la compression donne un code plus gros que si l'on avait codé le bloc en entier. C'est donc également le rôle des seuils de définir la limite à partir de laquelle on code le bloc pixel par pixel.

Une fois le mouvement estimé sur toute l'image, il reste à coder l'erreur résiduelle pour tous les blocs dont le critère n'était pas nul. Le codage de l'erreur résiduelle se fait par DCT.


3.3. Algorithmes de Block Matching

Le block matching consiste à rechercher les blocs ressemblants d'une image sur l'autre. On obtient le "match" pour la minimisation de l'erreur résiduelle.

La recherche des blocs (carrés réguliers ou non) est la partie de la compression vidéo demandant le plus de calculs processeur. D'où l'interêt d'optimiser cette phase de recherche. De la méthode triviale qu'est l'algorithme Full Search aux méthodes sub-optimales, voici une présentation de ce qui est l'objet de nombreuses recherches.


3.3.2. Méthode Three Step Search (TSS)

La méthode TSS [15] a été conçue pour réduire la compléxité de l'algorithme FS. On se limite à trois pas pour trouver le meilleur bloc. On cherche le bloc le plus ressemblant dans l'image précédente de la façon suivante:

  • Initialisation: On se place au vecteur de mouvement (0,0). C'est le centre de la recherche.

  • Etape 1: On teste le critère aux alentours du centre à un rayon R1 (8-connexité), et on repère le point qui minimise le critère.

  • Etape 2: On prend le minimum trouvé précédemment comme nouveau centre et on recherche aux alentours de ce point avec un rayon R2 < R1. On reprend le minimum comme centre de la prochaine étape.

  • Etape 3:On renouvelle une troisième fois l'opération avec un rayon R3 inférieur aux deux premiers.

Cet algorithme converge. Il est très rapide (3 phases de 8 tests seulement) mais on a une baisse de qualité visuelle.


3.3.3. Recherche en Diamant

Diamant simple: La recherche en diamant (Diamond search) [16] débute la recherche au vecteur (0,0). Puis il examine le critère en déplacant la fenêtre sur 9 points disposés en diamant. Une fois le minimum des ces neufs points trouvé, on reprend la recherche avec le minimum précédent comme centre de la nouvelle recherche. On repète l'opération tant que le minimum ne se trouve pas au entre du diamant. Quand on a effectivement le minimum au centre, on effectue une dernière recherche avec un plus petit diamant qui determinera le minimum estimé de l'image.


3.3.6. Zonal Based Algorithm

3.3.6.1. méthode PMVFAST

La méthode PMVFAST [23, 17] correspond au fast motion utilisé dans le MPEG4 et plus partculièrement dans les algorithmes DivX. Il permet une estimation de mouvement rapide et une très bonne qualité visuelle.


3.4. Estimation de mouvement par segmentation

Dans le MPEG1 et MPEG2, la division de l'image est simplement faite en quadrillant l'image en bloc 16*16 ou 16*8 pixels. Cette division en bloc n'utilise pas au mieux la redondance spatiale de l'image. Elle "casse" par exemple la redondance entre les pixels proches des frontières des blocs. Voyons comment la segmentation améliore la compensation de mouvement.


3.4.1. Principe

La segmentation [19] va permettre de diviser l'image en zone contenant plus de sens. Elle consiste à regrouper des pixels de caractéristiques communes ou proches.

Pour le MPEG, la segmentation est utile car d'une manière générale, dans un flux vidéo, les blocs de pixels se déplacant (les objets, personnages,...) ne sont pas des blocs carrés. La segmentation va permettre de découper les images en régions plus adaptées aux images réelles et par conséquent de mieux exploiter la redondance spatiale des images. L'erreur de mouvement à transmettre sera moindre et on gagnera donc en compression.

Les deux gros avantages de la segmentation sont les suivants:

C'est donc grâce à ces propriétés de block matching avec segmentation qu'on obtient les excellents taux de compression du MPEG4.

Cependant la segmentation est une opération qui demande beaucoup de calcul. Elle doit être optimisée. Il existe de nombreux algorithmes de segmentation dans le but de compresser la video. Voici une présentation de quelques un de ces algorithmes.


3.4.2. Algorithmes de segmentation pour la compensation de mouvement

3.4.2.1. segmentation par approximation de blocs carrés

Une première méthode simple de segmentation est d'approximer les blocs par des blocs de référence [5]. Pour cela, on découpe chaque bloc en sous blocs que l'on compare à des patterns de référence. Ces patterns sont établis en fonction des sous blocs les plus rencontrés. Les sous blocs ne peuvent contenir que deux régions au maximum. Puis on minimise le critère des moindres carrés sur les sous blocs de référence pour déterminer quel sous bloc correspond le mieux. On a alors sur toute l'image un ensemble de régions segmentées.

Cet algorithme donne de bons résultats: utilisée avec la méthode de recherche Full Search associée à une décomposition pyramidale de 3 niveaux [21], on obtient un gain en compression de 10% par rapport à la même technique sans segmentation.


3.4.2.2. segmentation par quadtrees

Si on observe les vecteurs de mouvement avec un partitionnement régulier de l'image, on remarque des zones de plusieurs blocs peuvent être regroupées car elles possèdent les mêmes vecteurs de mouvement:

On peut utiliser l'algorithme du quad-tree pour découper l'image [22]. Voici son principe et son application pour l'estimation de mouvement:

On part de blocs relativement grands, et on teste l'erreur résiduelle sur ces blocs. Tant que l'erreur résiduelle est supérieure à un certain seuil, on redécoupe le bloc en quatre. Ainsi si des grands blocs possèdent un vecteur de mouvement uniforme, on aura une erreur résiduelle faible et un seul vecteur devra être transmis.

On voit que l'image découpée en quadtree possède des grandes zones de vecteurs identiques. Sur ces zones, on a un gain important en compression. D'autre part, certaines zones ont été découpées beaucoup plus finement qu'avec des blocs de taille constante. Ici on a un gain en qualité visuelle. Les petites zones mobiles sont beaucoup mieux codées.

La segmentation d'image est prévue par la norme MPEG4 mais n'est pas encore implémentée dans les programmes DivX existants. Elle est jugée trop importante à mettre en oeuvre pour l'instant, mais nul doute que l'implémentation verra le jour quand la puissance des machines aura augmenté.


Chapitre 4. Test de Qualité des implémentations DivX


4.1. Protocole de test

Nous allons tester la qualité de l'encodage divx des différents algorithmes en mesurant l'erreur entre un flux de référence et ce flux encodé avec les différents encodeurs à tester. On prendra comme fichiers de référence les flux élémentaires MPEG2 de Tektronix disponibles gratuitement:

flux de référence Tektronix

Ceux ci sont intéressants car ils comportent des séquences de translation sur des objets contenant des textures complexes. Cela permet d'évaluer la qualité de l'estimation de mouvement du codec.

Voici une description générale du protocole utilisé pour estimer la qualité de la recherche de mouvement: comparaison des images issues des flux encodés ou non, et mesure de l'erreur.

A partir d'un flux vidéo de référence, on encode celui ci avec les différents encodeurs à tester. Puis on effectue une extraction (sans pertes) des images composants les flux. La mise en correspondance des images permettra d'estimer l'écart des flux encodés avec le flux de départ.

La comparaison des images du flux vidéo de départ avec les images issues des flux encodés permettra de mesurer la qualité de l'encodeur. On ne s'intéresse pas ici à la taille des fichiers encodés ni à la vitesse d'encodage.


4.1.2. Algorithmes testés

Les tests sont effectués sur les implémentations opensources. En effet, le logiciel libre permet l'accès aux sources des programmes, condition nécessaire pour connaitre la nature exacte des algorithmes, en particulier les algorithmes de block matching utilisés. La documentation des implémentations telles que DivX 5 n'est pas assez précise et ne spécifie pas la nature des recherches de bloc pour la prédiction de frames. Il est donc impossible de mettre en relation la qualité d'image avec la technique utilisée et les mesures perdent de leur intérêt.

Les trois algorithmes opensource disponible sont les suivants:


4.1.2.1. DivX4Linux

Toutes les implémentations opensources existantes sont issues du même projet: le projet Mayo. La dernière implémentation libre du projet Mayo avant que celui ci ne ferme ses sources est DivX4Linux. C'est le codec DivX4 [10], désormais renommé par DivXNetworks Opendivx (malgré la fermeture des sources).

La méthode de block matching utilisée par divx4 est l'algorithme diamond based algorithm. L'agorithme divx4 implémente le demi et le quart de pixel, qui apporte théoriquement une bonne précision.


4.1.2.2. Xvid

Après la fermeture des sources de DivX4 et la fondation de la société DivXNetworks, le code de Divx4linux a été repris par les partisans de l'opensource, et amélioré. C'est le projet Xvid [11], moins abouti que DivX4 mais de réputation plus performant. De plus, Xvid ne supporte pas le Advanced Simple profil. C'est le plus gros projet alternatif à l'algorithme de Divxnetworks.

Xvid utilise l'algorithme de block matching PMVFAST, algorithme rapide et possèdant une bonne qualité visuelle.


4.1.2.3. FFmpeg

FFmpeg 12 est une implémentation opensource récente qui prévoit les fonctionnalités suivantes: encodeur/décodeur mpeg4, ainsi que serveur de streaming via http (FFserver). Cette dernière partie n'est pas opérationnelle mais se développe rapidement. L'encodage peut être fait en temps réel. FFmpeg est donc une solution intéressante et l'algorithme mérite d'être étudié. Une fois les sources compilées, on obtient la librairie libavcodec.

FFmpeg possède une interface graphique optionnelle: Xffmpeg. Il existe également un module d'export FFmpeg pour QuickTime utilisant la librairie: FFmpeg for QT (librairie libavqt).

Concernant les algorithmes de block matching, FFmpeg permet l'utilisation de plusieurs méthodes: Full Search (utilisée en high quality), une méthode 2Dlogarithmique, et la méthode PHODS (Parallel Hierarchical One-Dimensional Search). La méthode 2Dlogarithmique est utilisée dans l'encodage de séquences "classiques".


4.2. mise en oeuvre des tests


4.2.1. Compression des flux

4.2.1.1. Transcode

L'encodage sera fait via transcode [24, 25], un outil de transformation de flux vidéo sous licence GPL. Transcode utilise plusieurs librairies de codage/décodage video et fait la liaison entre ces modules. Il offre une couche d'abstraction au dessus des outils de traitement.

Quel que soit le format, transcode démultiplexe la vidéo de l'audio pour permettre des traitements séparés. Puis des modules d'import et d'export sont sélectionnables pour manipuler les objets vidéo dans les formats désirés. Le gros intérêt de transcode est sa souplesse: il possède un repertoire contenant toutes les librairies utilisées sous forme de librairies dynamiques pour les modules d'entrée et de sortie. Transcode possède les librairies pour les formats suivants:

  • Modules d'entrée: (librairies import_XXX.so)

    DV, DVD, mjpeg, mpeg2, AVI, divx

  • Modules de sortie: (librairies export_XXX.so)

    divx4, divx5, ffmpeg4, mjpeg, opendivx, xvid, WAV, PCM.

Cette liste n'est pas exhaustive, il est possible de rajouter ses propres modules d'import ou d'export.

Transcode est donc très versatile, mais il possède également de nombreuses fonctions de traitement pour l'encodage ou la transformation de flux vidéo: il permet de choisir lors de l'encodage le framerate, le bitrate et la résolution du fichier ensortie. L'utilitaire tcprobe permet de connaitre le bitrate adéquat pour une taille de fichier donnée.


4.2.1.2. encodage

Avec transcode, on compresse donc notre fichier MPEG2 de référence en utilisant les trois codecs différents, en utilisant les options d'encodage:

L'encodage se fait en deux passes: la première pour estimer la complexité de chaque image et la deuxième qui affecte en fonction de la complexité un certain nombre de bits pour chaque frame.

Exemple: encodage du flux MPEG2 movie.m2v en flux MPEG4 movie.avi avec le codec divx4linux en deux passes:

première passe:

transcode -V -i movie.m2v -o movie.avi -y divx4 -R 1
(production d'un fichier log contenant les statistiques sur la complexité des frame)

deuxième passe:

transcode -V -i movie.m2v -o movie.avi -y divx4 -R 2

Pour encoder avec FFmpeg ou xvid on modifiera la précédente commande avec -y ffmpeg4 ou -y xvidcvs pour changer le module d'export du fichier.

Remarques:

Une fois les flux encodés, on va extraire les images du flux de manière à les comparer. Cette opération est faite avec transcode en choisissant le module de sortie ppm:

transcode -i movie.avi -y ppm

On a alors la suite des images composant les flux. Leur format est le PPM, qui correspond à du RGB non compréssé.

encode nom_fichier codec.

nom_fichier désigne le nom du fichier m2v à encoder sans l'extension. codec est l'un des codecs suivants: xvid, ffmpeg, divx4, ou all (encodage avec les trois codecs.)

script d'encodage

C'est à partir de ces images qu'on va pouvoir comparer la qualité d'encodage. La comparaison est effectuée avec PIL: Python ImageLib.


4.2.2. Comparaison des flux


4.2.2.1. Outil de comparaison: PIL

PIL. Python Image Library[26] est une librairie de traitement d'image pour le langage de script python. Cette librairie supporte de nombreux formats d'image: PNG, BMP, JPEG, GIF, etc, et permet aussi de créer et manipuler ses propres formats. PIL possède des fonctions évoluées pour l'affichage (via XV) et le traitement des images. Il offre la possibilité d'appliquer des filtres, d'effectuer des opérations entre deux images, ou d'effectuer des transformations (redimensionnement, rotation, transformation affine,...). Avec les librairies Numeric et gracePlot, il est possible d'obtenir des fonctions statistiques ainsi que des histogrammes des images utilisées.

La classe Image offre les opérations classiques de manipulation d'image: ouverture, création, etc, ainsi que les opérations de rassemblement, de mélange entre deux images. La classe ImageChops permet les opérations entre les images: différence, ajout d'un offset, opérations logiques, etc. Il est utile de compiler les modules Numeric et gracePlot pour accéder à des fonctions de traitement plus évoluées. Comme dans Matlab ou Mathematica, on a alors un GUI. Certaines de ces fonctions nous serons nécessaires; voici les fonctions utilisées pour la comparaison d'images:

moindres carrés avec PIL. Il faut définir une fonction effectuant les moindres carrés entre deux images. voici le script renvoyant la valeur voulue:

def rmsdiff(im1, im2):

#on se sert de l'histogramme

h = ImageChops.difference(im1, im2).histogram()

# formule

return math.sqrt(reduce(operator.add,
map(lambda h, i: h*(i**2), h, range(256))
) / (float(im1.size[0]) * im1.size[1]))

Le critère des moindres carrés donne un bon aperçu de la différence existante entre deux images.

Pour estimer l'erreur résiduelle sur une séquence de test, on somme l'erreur des moindres carrés sur toutes les images constituant la séquence.

différence d'histogrammes. pour obtenir la répartition de l'erreur, on soustrait l'histogramme de l'image en codé à l'histogramme de l'image de départ, en répétant l'opération pour toutes les images du flux. Ces histogrammes sont en suite additionnés. On connait alors le nombre de pixels comportant une erreur d'une valeur donnée.


4.3. Résultats


4.3.2. Histogrammes des erreurs

Si on soustrait l'histogramme de l'image encodée à celui de l'image de départ, on obtient non seulement les erreurs résultant de l'encodage, mais aussi leur répartition. Les histogrammes d'erreurs sont sommés sur toutes les images du flux.

exemple de sommes d'histogrammes d'erreurs sur les 50 premières images de la séquence tennis, suivant les trois algorithmes xvid, ffmpeg et divx4:

(Ces histogrammes ont été générés par le fichier somme.py )

Les résultats semblent cohérents: la répartition des erreurs montre un grand nombre de petites erreurs (différence de luminance proche de 0), quantité qui décroit au fur et à mesure que l'erreur augmente. On a peu de très grosses erreurs: les écarts de luminance supérieur à 25 sont peu nombreux.

Le but de ces test est de comparer les trois algorithmes, et Il est difficile de tirer des conclusions de ces trois histogrammes: on voit des différences mais il est il est impossible de les quantifier. leur aspect global reste trop similaire.

On décide donc de calculer les différences entre ces trois histogrammes par une soustraction d'histogrammes (soustraction niveau de gris à niveau de gris). On aura la répartition des différences entre les algorithmes. Pour une bonne comparaison, on présente pour un algorithme:

  • L'histogramme "classique" des erreurs entre le flux de référence et le flux encodé sur une séquence.

  • La différence des erreurs obtenues entre l'algorithme et ses deux concurrents. On peut alors nettement comparer les algorithmes.

Nous présentons les histogrammes les plus "parlants". L'intégralité des résultats est en annexe. Ils sont constitués pour chaque algorithme des histogrammes de chaque séquence et de la différence avec les deux autres algorithmes. Tous les histogrammes possèdent la même échelle en abscisse (erreur de luminance: 0.5 - 35.5) mais pas forcément en ordonnée.


4.3.3. Séquence tennis, comparaison de l'algorithme Xvid à ffmpeg et DivX4.

Cette séquence montre les mouvements rapides d'un personnage sur fond fixe, puis changeant. On rappelle le critère des moindres carrés obtenu sur cette séquence:

Le premier histogramme représente l'histogramme de l'erreur entre le flux de référence et le flux encodé avec Xvid en deux passes. Il représente la somme des histogrammes d'erreur pour toutes les images du flux. On remarque un grand nombre d'erreurs pour des petites différences de niveau de gris. Jusqu'à 10, le nombre d'erreur est important. Les erreurs supérieures à 25 deviennent rares et 40 inexistantes.

Les deux autres histogrammes représentent la soustraction des histogrammes FFmpeg et DivX4 à l'histogramme Xvid. Il faut donc lire l'histogramme "xvid - ffmpeg" de la manière suivante: prenons la barre d'abscisse 2 (qui atteint environ 220 millions de pixels), elle signifie qu'il y a 220 millions de pixels de plus dans le flux Xvid que dans le flux ffmpeg qui possèdent une erreur de luminance de 2 par rapport au flux de référence.

On voit nettement les différences entre les deux codecs: sur le deuxième histogramme, les erreurs de Xvid sont plus nombreuses que FFmpeg pour les différences de niveaux de gris de 1 à 3. Xvid comporte donc plus de petites erreurs: une différence de niveau de gris de 2 ou 3 est cependant difficilement visible à l'oeil nu. A partir du niveau de gris 4, Xvid devient meilleur que FFmpeg: la différence devient négative, ce qui signifie une présence plus forte de grosses erreurs dans le flux encodé avec FFmpeg. Au dela d'une différence de niveau de gris de 20, les erreurs et donc les différences deviennent minimes.

Sur le troisième histogramme qui compare l'algorithme Xvid à DivX4, on retrouve le même type de graphique, mais le nombre d'erreurs différentes est plus important; le nombre de petites erreurs est encore inférieur avec Divx4: il y a environ 1,75 millions de pixels de plus dans le flux Xvid que dans le flux DivX4 qui possèdent une erreur de luminance de 1. l'inversion se fait pour une erreur de 4 et là aussi on voit la supériorité de Xvid pour le nombre de grosses erreurs.


4.4. Interpretation des résultats

La répartition des erreurs indique clairement des différences entre les algorithmes. On en tire les conclusions suivantes:

Xvid est l'algorithme comportant le moins de grosses erreurs, mais le plus de petites. Inversement, L'algorithme DivX4 génère plus d'erreurs importantes que les autres algorithmes, mais moins de petites.

Les grosses différences de luminance sont beaucoup plus visibles par l'oeil humain qui distingue à peine les variations de luminance d'une ou deux unités. On accorde plus d'importance aux grosses erreurs: mieux vaut plusieurs petites erreurs non detectables qu'une seule grosse.

C'est dans les séquences contenant du mouvement que les algorithmes de block matching travaillent le plus. C'est précisement lors de ces séquences (tennis, mobile) que l'on constate les résultats les plus marquants: Xvid et son algorithme PMVFAST possède la meilleure qualité d'image. la recherche de blocs durant les séquences en mouvements rapides est plus performante. Pour les séquences plus lente, peu de grosses erreurs sont à priori générées puisque les meilleurs blocs se situent pour des motions vectors nuls ou proches de 0. C'es donc l'algorithme DivX4 qui semble le plus performant pour ce type de scènes.

La méthode 2Dlogarithmique de FFmpeg se situe entre les deux algorithmes Xvid et DivX4, tant pour les scènes rapides que pour les lentes.


Conclusion

Par la diversité des domaines auxquels touche le MPEG4, cette étude fut un travail de synthèse passionnant. J'ai ainsi abordé de nombreux domaines tels que le traitement d'image, l'industrie du multimédia, l'élaboration d'un protocole de test et la réalisation de celui ci.

Une connaissance et une synthèse sur le MPEG4 ont été apportée à l'entreprise, et le test des implémentations s'est avéré concluant. Plus que l'importance des résultats, c'est l'élaboration du protocole et l'application des recherches effectuées précédemment qui présentent un intérêt.

Des principes de l'estimation de mouvement à l'étude des chips de décodage, j'ai pu faire la relation entre la théorie associée à la norme MPEG4 et l'application de cette norme dans l'industrie. Cette transition ne se fait pas facilement: il faut adapter la théorie aux contraintes de l'informatique: espace mémoire, débits, puissance des machines, couts de développement, formatage et conditions imposées par les consortiums et grosses puissances industrielles. On notera cependant une chose: les tests réalisés montrent que l'algorithme le plus performant est Xvid, une branche opensource du divx, sur lequel le marché et l'industrie n'ont pas de pouvoir.


Bibliographie

MPEG

[1] site du MPEG.

[2] Two-pass MPEG-2 variable-bit-rate en coding, P. H. Westerlink, R. Rajagopalan, C. A. Gonzales, 1999 fichier pdf.

[3] Overview of the MPEG4 standard, Rob Koenen, ISO, 2002.

[4] On the use of layers for video coding and object manipulation, L. Torres, D. Garcia, A. Mates, 1997 fichier ps.

[5] Estimation de mouvement avec segmentation de blocs en codage d'images, A. Ouerfelli et H. Vu Thien, Laboratoire Electronique et Communication, Conservatoire National des Arts et metiers..

[6] Mpeg4 Industry Forum.

[7] Internet Streaming Media Alliance.

[8] Project Mayo.

[9] DivXNetworks.

[10] DivX.com.

[11] XviD.org.

[12] FFmpeg Streaming Multimedia System.


Compensation de mouvement

[13] MPEG, Images animées, compensation de mouvement, J. Leroux, 2001. Site web.

[14] Motion compensation, Woobin Lee, 1995. site web.

[15] Three Step Search Algorithm, Colin Manning. site web.

[16] Predictive Diamond Search Algorithm: diamond algorithm et predictive diamond algorithm, A.M. Tourapis, G. Shen, M. L. Liou, O. C. Au, I. Ahmad, 2000. fichier pdf.

[17] "Predictive Motion Vector Fast Search Algorithm technique", A.M. Tourapis, G. Shen, M. L. Liou. fichier pdf.

[18] "comparaison des algorithmes PMVFAST, Full Search", Oscar Au. site web.

[19] "Motion Compensated Video Compression Overview", Colin Manning. site web.

[20] "Codage des objets virtuels", 1999. site web.

[21] "Hierarchical Block Matching Algorithms", Colin Manning. site web.

[22] "Variable Size Block-Matching" (VSBM), Multimedia Coding Group. Variable Size Block-Matching (VSBM).

[23] "An Adaptive Center (Radar) Zonal Based Algorithm for Motion Estimation", A.M. Tourapis, Oscar Au, M. L. Liou, 1999 fichier pdf.


Outils de tests

[24] Transcode, le couteau suisse de la vidéo, Guillaume Rousse, 2002. site web.

[25] Transcode: Linux Video Stream Processing Tool. site web.

[26] Python Imaging Library. site web.


Annexe A. Annexes: Histogrammes des erreurs


Annexe B. Annexe: fichier de script python


B.3. somme.py

import os, sys
import Image, ImageChops
import math, operator
from gracePlot import gracePlot


def compare(nomfic, nb):

p1 = gracePlot() # pour les histogrammes
#p2 = gracePlot()
#p3 = gracePlot()
indices = range(nb) # nombre d'image à comparer

nomfic="tens_060"

# Initialisation des histogrammes
histo_xvid = [0] * 256
histo_ffmpeg = [0] * 256
histo_divx4 = [0] * 256


for j in indices :
nom = "000%d.ppm" %(j)
if j < 100:
nom = "0000%d.ppm" %(j)
if j < 10:
nom = "00000%d.ppm" %(j)

# chargement image issue du flux non encodé
img_REF = Image.open("/opt/videos/"+nomfic+"/ppm_REF/" + nom)

# chargement images des trois flux encodés
img_xvid = Image.open("/opt/videos/"+nomfic+"/ppm_xvid/"+ nom)
img_ffmpeg = Image.open("/opt/videos/"+nomfic+"/ppm_ffmpeg/"+ nom)
img_divx4 = Image.open("/opt/videos/"+nomfic+"/ppm_divx4/"+ nom)

# conversion des images en luminance
img_REF = img_REF.convert("L")
img_xvid = img_xvid.convert("L")
img_ffmpeg = img_ffmpeg.convert("L")
img_divx4 = img_divx4.convert("L")


if img_REF.size == img_xvid.size:

diff_xvid = ImageChops.difference(img_REF,img_xvid)
h = diff_xvid.histogram()
histo_xvid = add(histo_xvid,h)

if img_REF.size == img_ffmpeg.size:

diff_ffmpeg = ImageChops.difference(img_REF,img_ffmpeg)
h = diff_ffmpeg.histogram()
histo_ffmpeg = add(histo_ffmpeg,h)

if img_REF.size == img_xvid.size:

diff_divx4 = ImageChops.difference(img_REF,img_divx4)
h = diff_divx4.histogram()
histo_divx4 = add(histo_divx4,h)

#histo_x_moins_d = sub(histo_xvid,histo_divx4)

p1.multi(1,3)

p1.focus(0,0)
p1.title('xvid')
p1.histoPlot(histo_xvid)
p1.xlimit(0, 30)

p1.focus(0,1)
p1.histoPlot(histo_ffmpeg)
p1.title('ffmpeg')
p1.xlimit(0, 30)

p1.focus(0,2)
p1.histoPlot(histo_divx4)
p1.title('divx4')
p1.xlimit(0, 30)

#p1.histoPlot(histo_x_moins_d)

# fonction qui additionne deux histogrammes

def add(self, other):
return map(lambda x,y: x+y, self, other)

def sub(self, other):
return map(lambda x,y: x-y, self, other)


compare("flwr_060", 50)