UNE ÉTAPE D'UNE CHAÎNE — CE QUI ENTRE, CE QUI SORT, CE QUI CASSE ENSUITE
Où cette étape se situe dans la chaîne d'encodage
Un encodeur vidéo n'est pas un algorithme mais huit étapes dans un ordre fixe, et cet ordre n'est pas arbitraire : chaque étape existe parce que la précédente a rendu son travail possible. Cet outil modélise l'une d'elles. La chaîne ci-dessous renvoie aux sept autres.
Simulateur d'estimation de mouvement — trouve où chaque bloc s'est déplacé, puis code la différence au lieu du bloc
- Ce qui entre
- Une image P ou B accompagnée de ses images de référence.
- Ce qui sort
- Un vecteur de mouvement par bloc et un résidu — exactement ce que la prédiction a raté.
- Ce que suppose l'étape suivante
- La quantification reçoit un résidu, pas une image. Les résidus sont proches de zéro presque partout, et c'est précisément ce qui rend leur quantification bon marché.
- Ce qui se casse ici
- Une mauvaise correspondance ne produit pas une image fausse mais une image chère. Le résidu porte plus d'énergie, et le même réglage de quantificateur émet alors plus de bits. Cette étape change la taille de la sortie, pas ses réglages.
Problème entièrement résolu
-
La fenêtre de recherche déduite de 225 positions par bloc 5 étapes
Une recherche exhaustive de mouvement teste 225 positions par bloc, soit 14 400 au total. Déduisez-en la fenêtre de recherche, ainsi que le gain apporté par une recherche rapide.
-
225 est un carré parfait, et là réside l'indice : la recherche s'effectue dans une fenêtre carrée de 15 par 15 déplacements candidats, ce qui signifie de −7 à +7 pixels dans chaque direction.
-
Diviser le total par le nombre de positions par bloc donne le nombre de blocs dans lesquels l'image a été découpée.
-
Le coût augmente comme le carré du rayon de recherche, de sorte qu'agrandir la fenêtre devient vite très coûteux : un rayon de 7 coûte 225 positions, un rayon de 15 coûte 961, et un rayon de 31 coûte 3969.
-
Cette croissance quadratique explique l'existence des recherches rapides. Une recherche en trois étapes échantillonne neuf points, affine, puis répète — 27 positions au lieu de 225.
-
Huit fois moins chère, et non équivalente : elle descend vers un minimum local et peut passer à côté du meilleur vecteur correspondant si la surface d'erreur présente plusieurs creux.
Réponse
L’outil indique 14 400 points examinés, soit 225,0 par bloc. Tout l’enjeu pratique du codage vidéo est là : la recherche exhaustive donne le meilleur résultat, mais son coût croît comme le carré du rayon. Les encodeurs recourent donc tous à une heuristique, quitte à choisir parfois un vecteur moins bon. La ligne Énergie résiduelle (EQM) montre une partie du prix de cette erreur. Un mauvais vecteur laisse un résidu plus important, qui exige davantage de données pour être codé. Une recherche rapide du mouvement repose sur un pari concret : les bits supplémentaires dus à des vecteurs imparfaits coûteront moins que ceux que les ressources économisées permettront de gagner ailleurs.
-
Références (2)
- Block matching and motion vectors as the standard uses them: T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra, "Overview of the H.264/AVC video coding standard." IEEE Transactions on Circuits and Systems for Video Technology 13(7), 560–576, 2003.
- The diamond search this tool implements alongside full search: S. Zhu and K.-K. Ma, "A new diamond search algorithm for fast block-matching motion estimation." IEEE Transactions on Image Processing 9(2), 287–290, 2000.