Ayant terminé la création de l'architecture web pour notre nouvelle bande dessinée web
Meow the Infinite , j'ai décidé qu'il était temps d'écrire quelques articles techniques attendus depuis longtemps. Cet article se concentrera sur un filtre que j'ai développé il y a plusieurs années. Cela n'a jamais été discuté dans le domaine de la compression vidéo, bien qu'il me semble que cela en vaille la peine.
En 2011, j'ai développé le «filtre demi-pel». Il s'agit d'un type spécial de filtre qui prend une image entrante et affiche de manière convaincante à quoi ressemblerait l'image lorsqu'elle serait décalée
exactement d'un demi-pixel .
Vous vous demandez probablement pourquoi un tel filtre peut être nécessaire. En fait, ils sont assez courants dans les codecs vidéo modernes. Les codecs vidéo utilisent des filtres similaires pour prendre des fragments d'images précédentes et les utiliser dans les images suivantes. Les codecs plus anciens ne déplaçaient les données de trame que d'un pixel entier à la fois, mais les nouveaux codecs allaient plus loin et permettaient un décalage d'un demi ou même d'un quart de pixel pour mieux transmettre les petits mouvements.
Lors de l'analyse du comportement des algorithmes de compensation de mouvement dans les filtres demi-pixel traditionnels,
Jeff Roberts a constaté que lorsqu'ils étaient appliqués à plusieurs reprises à des images séquentielles, ils se dégradaient rapidement, forçant les autres parties du compresseur vidéo à utiliser plus de données que nécessaire pour corriger les artefacts. Si vous désactivez ces corrections et regardez les résultats "bruts" du filtre halfpel, voici l'image d'origine:
se transforme en ceci:
juste une seconde plus tard la vidéo. Comme il se doit, il est décalé sur le côté, car chaque image a décalé l'image d'un demi-pixel. Mais le résultat ne ressemble pas à une version déplacée de l'image d'origine, il est sérieusement déformé.
Pendant le "vidéo d'une seconde", le filtre est en fait appliqué plusieurs fois - 60 si la vidéo est lue à une fréquence de 60 images par seconde. Mais idéalement, nous avons besoin de filtres résistants à de telles distorsions. Si nous les avions, les vidéos à défilement fluide n'auraient pas été encodées avec autant de corrections d'artefacts, ce qui les aurait rendues inférieures, ou meilleures, ou les deux.
Si vous connaissez le domaine de la compression vidéo, vous vous demandez peut-être pourquoi devons-nous même utiliser le filtre halfpel plus d'une fois. En fin de compte, si nous appliquons le filtre halfpel deux fois, nous déplacerons déjà un pixel entier, alors pourquoi ne pas simplement utiliser les données de
deux images et les reprendre?
La réponse n'est pas si simple. Premièrement, plus nous avons besoin de données pour coder les données, moins nous obtenons de compression. Par conséquent, si nous commençons à coder sans avoir besoin de trop de données telles que «à partir de quelle image prendre les données», la vidéo ne sera pas très bien compressée.
Mais ce n'est pas le plus important. Le principal problème est que si nous devons prendre des informations de trames précédentes, nous
devrons les stocker . Pour conserver les deux images précédentes, au lieu d'une, vous devez deviner que vous avez deux fois plus de mémoire. Pour les processeurs modernes, ce n'est pas un problème particulier, ils ont beaucoup de mémoire et une telle bagatelle ne les dérange pas. Mais c'est un
problème pour vous si vous voulez créer un format vidéo rapide, portable et largement utilisé qui devrait fonctionner dans des appareils avec une petite quantité de mémoire (téléphones mobiles, électronique intégrée, etc.).
Nous ne voulons vraiment pas stocker plusieurs images afin de compenser le mouvement afin de ne pas utiliser de filtre demi-pixel. Par conséquent, on m'a demandé de savoir ce qui se passe exactement ici et de déterminer si je peux créer un filtre qui ne présente pas de tels problèmes.
Avant cela, je n'avais jamais travaillé avec des filtres et je n'avais aucune idée de la façon dont ils sont généralement développés. Curieusement, cela s'est avéré en ma faveur, car je devais examiner ce problème sans préjugés.
Les bases
J'ai rapidement réalisé que les filtres halfpel les plus populaires ont une structure similaire: pour chaque pixel de l'image de sortie, 2 à 8 pixels de l'image d'entrée sont pris, qui sont échantillonnés et mélangés avec certains coefficients. Différents filtres ne diffèrent que par le nombre de pixels sources échantillonnés (souvent dans le jargon des développeurs de filtres, ils sont appelés tap) et les facteurs de mélange des pixels. Ces coefficients sont souvent appelés «noyau de filtre» et c'est tout ce qui est nécessaire pour décrire complètement le filtre.
Si vous connaissez tout type d'échantillonnage ou de rééchantillonnage d'images (par exemple, la mise à l'échelle d'images), cela devrait être clair pour vous. Essentiellement, les filtres font la même chose. Étant donné que la compression vidéo est un vaste domaine dans lequel diverses études sont effectuées, il est évident qu'il existe de nombreuses
autres façons de compenser le mouvement autres que le simple filtrage. Mais les codecs courants utilisent généralement des procédures de compensation de mouvement avec des filtres demi-pixels, qui sont essentiellement identiques aux filtres de mise à l'échelle de l'image: ils prennent simplement les pixels d'origine, les multiplient par certains poids, les ajoutent et obtiennent les pixels de sortie.
Le besoin de "netteté"
Nous devons donc déplacer l'image d'un demi-pixel. Si vous êtes un programmeur graphique, mais que vous n'êtes pas particulièrement familier avec le filtrage, vous pourriez penser: "J'ai aussi un problème, utilisez simplement un filtre bilinéaire." Il s'agit d'un processus standard pour travailler avec des graphiques, lorsque nous devons calculer des valeurs intermédiaires entre deux éléments de données entrants, comme cela se produit ici.
Un filtre bilinéaire pour déplacer exactement un demi-pixel peut être facilement décrit par le noyau de filtre suivant:
Cela fonctionnera, mais pas sans problèmes. Si votre objectif est des images de haute qualité, et dans le cas de la compression vidéo, l'objectif n'est que cela, alors un filtre bilinéaire n'est pas la meilleure solution, car il ajoute plus de flou au résultat que nécessaire. Ce n'est pas tant, mais
plus que d'autres filtres n'en créent.
Pour le montrer clairement, voici une image approximative de l'œil du morse à partir de l'image d'origine après une seule application des filtres les plus courants:
A gauche, l'original, à droite, le filtrage bilinéaire. Entre eux se trouvent les filtres halfpel les plus largement utilisés des codecs vidéo. Si vous regardez attentivement, vous pouvez voir que presque toutes les images se ressemblent, à l'
exception d'une image bilinéaire, qui est légèrement plus floue. Bien qu'il n'y ait pas beaucoup de flou, si votre objectif principal est la qualité d'image, cela suffit pour préférer un filtre différent à un filtre bilinéaire.
Alors, comment les autres filtres «maintiennent-ils» la netteté et évitent-ils le flou? Rappelons à quoi ressemble le noyau du flou bilinéaire:
BilinearKernel[] = {1.0/2.0, 1.0/2.0};
C'est très simple. Pour décaler l'image d'un demi-pixel, on prend un pixel et on le mélange à 50% avec son voisin. C’est tout. On peut imaginer comment cela «brouille» l'image, car dans les endroits où le pixel blanc brillant est adjacent au noir foncé, ces deux pixels sont moyennés lors du filtrage bilinéaire, créant un pixel gris qui «adoucit» la bordure. Cela se produit avec chaque pixel, donc littéralement chaque zone où il y a une nette différence de couleur ou de luminosité. lissé.
C'est pourquoi dans les codecs de haute qualité, le filtrage bilinéaire n'est pas utilisé pour la compensation de mouvement (bien qu'il puisse être utilisé dans d'autres cas). Au lieu de cela, des filtres sont utilisés qui préservent la netteté, par exemple, tels que:
Comme vous pouvez le voir, là où le filtrage bilinéaire ne prenait en compte que deux pixels, ces filtres prennent en compte six (h.264) voire huit (HEVC) pixels. De plus, ils ne calculent pas seulement les valeurs moyennes pondérées habituelles de ces pixels, mais utilisent
des poids
négatifs pour certains pixels pour
soustraire ces pixels des autres valeurs.
Pourquoi font-ils ça?
En fait, il n'est pas difficile de comprendre cela: en utilisant à la fois des valeurs positives et négatives, et en considérant également une «fenêtre» plus large, le filtre est capable de prendre en compte la
différence entre les pixels adjacents et de simuler la netteté des deux pixels les plus proches par rapport à leurs voisins les plus éloignés. Cela vous permet de maintenir la netteté du résultat de l'image dans les endroits où les pixels diffèrent considérablement de leurs voisins, tandis que la moyenne est toujours utilisée pour créer des valeurs crédibles de décalages de "demi-pixel", qui doivent nécessairement refléter la combinaison de pixels de l'image entrante.
Filtrage instable
Alors, le problème est-il résolu? Oui, c'est possible, mais si vous n'avez besoin que d'un décalage d'un demi-pixel. Cependant, ces filtres «d'accentuation» (et j'utilise ce terme ici intentionnellement) font en fait quelque chose de dangereux,
essentiellement similaire à ce que fait le filtrage bilinéaire. Ils savent mieux comment le cacher.
Lorsque le filtrage bilinéaire
réduit la netteté de l'image, ces filtres standard l'
augmentent , comme l'opération de netteté dans certains programmes graphiques. La quantité de netteté est très faible, donc si nous n'exécutons le filtre qu'une seule fois, nous ne le remarquerons pas. Mais si le filtrage est effectué plusieurs fois, cela peut devenir très visible.
Et, malheureusement, puisque cette netteté est procédurale et dépend de la différence entre les pixels, elle
crée une boucle de rétroaction qui continuera à rendre la même bordure encore et encore jusqu'à ce qu'elle détruise l'image. Vous pouvez le montrer avec des exemples spécifiques.
Ci-dessus - l'image d'origine, ci-dessous - avec filtrage bilinéaire, effectuée sur 60 images:
Comme vous pouvez vous y attendre, le flou continue simplement de réduire la netteté de l'image jusqu'à ce qu'elle devienne assez floue. Maintenant, l'original sera en haut et le filtre halfpel du codec h.264 qui fonctionnera pendant 60 images en bas:
Voir tous ces déchets? Le filtre fait la même chose que l'effet «flou» du filtrage bilinéaire, mais
vice versa - il «augmente la netteté de l'image» de sorte que toutes les parties où les détails sont transformés en motifs clair / foncé fortement déformés.
Le codec HEVC utilisant 8 pixels se comporte-t-il mieux? Eh bien, il fait certainement mieux que le h.264:
mais si nous augmentons le temps de 60 images (1 seconde) à 120 images (2 secondes), nous verrons toujours qu'il y a un retour et l'image est détruite:
Pour ceux qui aiment le traitement du signal, je vais ajouter un filtre fenêtré-sinc (appelé filtre Lanczos) pour référence:
Je n'expliquerai pas dans cet article pourquoi quelqu'un pourrait être intéressé par le "windowed sinc", mais il suffit de dire que ce filtre est populaire pour des raisons théoriques, alors regardez à quoi il ressemble lors du traitement de 60 images (1 seconde):
et lors du traitement de 120 images (2 secondes):
Mieux que h.264, et à peu près le même que HEVC.
Filtrage stable
Comment pouvons-nous obtenir de meilleurs résultats que h.264, HEVC et sinc fenêtré? Et combien peuvent-ils être mieux?
Je
m'attendrais à voir des questions similaires dans la littérature sur la compression vidéo et elles devraient être bien connues des spécialistes de la compression, mais en fait (au moins pour 2011), je n'ai trouvé personne qui a au moins déclaré que c'était un problème. J'ai donc dû trouver une solution seule.
Heureusement, l'énoncé du problème est très simple: créez un filtre qui peut être appliqué autant de fois que possible afin que l'image soit à peu près la même qu'au début.
J'appelle cette définition «filtrage stable» car, à mon avis, elle peut être considérée comme une propriété de filtre. Un filtre est «stable» s'il ne tombe pas dans sa boucle de rétroaction, c'est-à-dire qu'il peut être appliqué à plusieurs reprises sans créer d'artefacts. Un filtre est "instable" s'il crée des artefacts qui sont amplifiés par une utilisation répétée et finissent par détruire l'image.
Je le répète, je ne comprends pas pourquoi ce sujet n'est pas pris en compte dans la littérature sur les codecs vidéo ou le traitement d'image. Il utilise peut-être une terminologie différente, mais je ne l'ai pas rencontrée. Le concept de «feedback» est bien établi dans le domaine du travail avec le son. mais pas un problème important dans le traitement d'image. Peut-être parce que les filtres ne doivent généralement être appliqués qu'une seule fois?
Si j'étais un spécialiste dans ce domaine, alors j'avais probablement une opinion à ce sujet, et peut-être même connaîtrais-je ces recoins de la littérature spécialisée où il existe déjà des solutions à ce problème, peu connues. Mais, comme je l'ai dit au début de l'article, je n'avais jamais été en mesure de créer des filtres auparavant, j'ai donc cherché uniquement dans des articles bien connus (bien qu'il soit intéressant de noter qu'il y a au moins une personne bien connue dans la littérature qui n'a également rien entendu de tel) )
Le matin, ils m'ont dit que nous avions besoin de ce filtre et j'ai essayé de le créer toute la journée. Mon approche était simple: j'ai créé un programme qui a exécuté le filtre des centaines de fois et à la fin a produit une image pour que je puisse voir le résultat de longues exécutions. Ensuite, j'ai expérimenté différents coefficients de filtre et observé les résultats. C'était littéralement un processus directionnel d'essais et d'erreurs.
Environ une heure plus tard, j'ai choisi les meilleurs coefficients de filtre adaptés à cette tâche (mais ils avaient un défaut, dont je parlerai dans la deuxième partie de l'article):
MyKernel[] = {1.0/32.0, -4.0/32.0, 19.0/32.0, 19.0/32.0, -4.0/32.0, 1.0/32.0};
Ce noyau est sur le point d'être affûté et flou. Étant donné que la netteté conduit toujours à une rétroaction qui crée des artefacts vifs et évidents, ce noyau de filtre préfère un peu de flou pour que l'image semble juste un peu plus «terne».
Voici à quoi cela ressemble après 60 images. Pour référence, j'ai montré tous les filtres dans cet ordre: l'image d'origine (sans filtrage), mon filtre, bilinéaire, Lanczos, h.264, HEVC:
Comme vous pouvez le voir, mon filtre donne des résultats légèrement plus flous que les filtres de netteté, mais n'a pas d'artefacts de netteté inacceptables après 60 images. Cependant, vous pouvez préférer les artefacts de flou pour aiguiser les artefacts, vous pouvez donc choisir entre le meilleur filtre de netteté (Lanczos) et le mien. Cependant, si nous augmentons le nombre à 120 images, mon filtre est hors compétition:
Après 300 images, tous les filtres, sauf le mien, deviennent comme une mauvaise blague:
Après 600 images, la blague devient encore plus cruelle:
Vous n'avez même pas besoin de dire ce qui se passe après 900 images:
Est-il stable?
A ce stade, on se demandera naturellement: mon filtre est-il
vraiment stable, ou est-ce juste un flou très lent, beaucoup plus lent que le filtrage bilinéaire? Peut-être qu'après des milliers de répétitions, mon filtre brouillera
progressivement l'image?
Étonnamment, la réponse semble être négative. Bien qu'un peu de flou soit ajouté au cours d'une centaine de premières superpositions, il semble que le filtre
converge vers une représentation stable de l'image, qui
ne se dégrade ensuite
jamais . Voici une autre image agrandie d'un œil de morse:
De gauche à droite: l'image d'origine, mon filtre appliqué 60 fois, 120 fois, 300 fois, 600 et 900 fois. Comme vous pouvez le voir, le flou converge vers un état stable, qui ne se dégrade plus même après des centaines de superpositions de filtres. Par contraste, comparez cela avec la synchronisation fenêtrée pour le même nombre d'échantillons (appuyez) et voyez à quel point (et rapide!) Les artefacts forment le feedback et créent un résultat inutile:
Mon filtre semble très stable, et comparé à tous les filtres que j'ai vus, il crée les meilleurs résultats après une utilisation répétée. Il semble qu'il possède une certaine propriété «asymptotique», dans laquelle les données convergent rapidement vers une image lissée (limitée), puis cette image lissée est enregistrée et n'effectue pas de dégradation illimitée pour terminer les ordures.
J'ai même essayé d'appliquer le filtre un
million de fois, et il semble qu'après les quelques centaines de superpositions, il ne se dégrade plus. Sans une meilleure analyse mathématique (et je n'ai pas encore trouvé de solution mathématique qui puisse le prouver exactement, mais je suis sûr que c'est quelque part), je ne peux pas dire avec certitude que quelque part après des milliards ou des milliards de superpositions qui -il ne cassera pas. Dans des tests raisonnables, je n'ai pas pu détecter de dégradation supplémentaire.
Est-ce le meilleur filtre Halfpel stable pour six tap?
A ce stade, il serait logique de se poser la question: est-ce vraiment le meilleur que l'on puisse trouver? L'intuition nous dit que ce n'est pas le cas, parce que je n'avais absolument aucune connaissance sur le développement des filtres et que je n'avais presque pas étudié la littérature, j'ai récupéré ce filtre en seulement une heure. Au moins, on peut
supposer qu'après une étude aussi brève, je n'aurais pas trouvé de filtre définitif, le meilleur et le plus conquérant.
Cette hypothèse est-elle vraie? Et si c'est vrai,
quel sera le meilleur filtre final? Je vais en discuter plus en détail dans la deuxième partie de l'article.