Comment j'ai créé un filtre qui ne corrompe pas l'image même après un million d'exécutions - partie 2

Dans la première partie de cet article, j'ai expliqué comment l'utilisation répétée de filtres demi-pixels standard crée des images déformées, puis j'ai montré un nouveau filtre qui ne présente pas ce problème.

C'était un peu plus flou et cela ne convenait pas à tout le monde. Cependant, c'était mieux que ses alternatives - en fait, ce filtre était utilisé dans la version originale de Bink 2 . En raison de la charge de travail constante, je n'ai jamais réussi à revenir vers lui et à l'examiner plus en détail.

Mais maintenant que j'ai trouvé le temps de revenir sur ce filtre et d'écrire un article à ce sujet, je devrais enfin poser la question: existe-t-il un filtre moins flou qui conserve encore la propriété de «stabilité infinie»?

Avertissement de spoiler: la bonne réponse est «probablement pas» et «certainement là». Mais avant de comprendre pourquoi il y a deux réponses à cette question et ce qu'elles signifient, préparons mieux le banc d'essai.

Réglage du décalage

Quand j'ai d'abord travaillé sur ce problème, je n'avais aucune idée de ce que je cherchais. Je ne savais même pas qu'il existait un filtre demi-pixel «infiniment stable», donc je n'ai pas créé de système dans sa recherche. Je cherchais juste quelque chose qui résisterait aux «nombreuses» itérations du filtre sans distorsion de l'image. Toutes les images de la première partie reflètent cette méthodologie: l'image est décalée de droite à gauche d'un demi-pixel à la fois, c'est-à-dire que si vous appliquez le filtre 100 fois, l'image résultante sera décalée de 50 pixels.

Maintenant que nous savons ce que nous recherchons, nous pouvons être un peu plus précis. En appliquant le filtre halfpel deux fois, nous décalons l'image exactement d'un pixel. Autrement dit, si nous déplaçons simplement l'image d'un pixel en arrière , elle restera dans le même espace. Grâce à cela, le test sera beaucoup plus beau, car nous pourrons non seulement appliquer le filtre un certain nombre de fois, sans craindre que l'image ne "rampe" loin de l'écran, mais nous pourrons également trouver la différence de l' image avec les versions précédentes et avec l'original.

Cela nous permettra de tester les filtres automatiquement. Nous appliquons simplement le filtre plusieurs fois et voyons l'une des deux choses: soit la convergence vers une image inchangée, indiquant que le filtre est infiniment stable, soit un écart significativement important par rapport à l'image d'origine, indiquant que le filtre est «cassé». Pour ces tests, j'ai choisi l'erreur moyenne par canal 64 (sur 255), ou l'erreur maximale sur l'un des canaux au maximum 255 comme «significativement grande». Si l'une de ces conditions est vraie, nous supposerons que le filtre «s'est cassé» ".

Re-tester les filtres de la première partie

Donc, maintenant nous comprenons mieux comment tester ces filtres, alors jetons un nouveau regard sur les filtres de la première partie. Commençons par un bilinéaire, ce qui, bien sûr, n'est pas très intéressant:


Ceci est une image après 244 itérations. Comme vous pouvez vous y attendre, l'image se «casse» progressivement en raison de la moyenne constante des pixels. Mais même elle atteint progressivement la limite de l'erreur moyenne.

Voici h.264:


Pour briser l'image, 78 itérations lui suffisent. Le filtre HEVC avec 8 échantillons se comporte un peu mieux, mais se casse toujours après 150 itérations:


Lanczos avec 6 échantillons se brise après 166 itérations:


C'est tout nos filtres cassés. Tout ce qui reste est mon filtre entier:


Comme prévu, il n'était pas le seul à casser. Il converge vers une image infiniment stable après 208 itérations.

Ce que nous savons est tout à fait remarquable ici: au moins pour une large gamme d'images de test, ce filtre est infiniment stable , c'est-à-dire qu'il ne créera jamais d'artefact, quel que soit le nombre de fois qu'il est utilisé.

Cela nous ramène à la question initiale: est-il vraiment le meilleur? Et vous connaissez déjà les réponses, car au début de l'article, j'ai aussi écrit: «probablement pas» et «définitivement, oui».

Examinons d'abord la partie «probablement pas» en premier.

Filtres entiers

Donc, dans la première partie de l'article, j'ai mentionné que le noyau de filtre que j'ai trouvé était "le meilleur des détectés", et c'est sa particularité. Et voici la fonctionnalité:

Quand je cherchais ce filtre, en fait je ne cherchais pas le meilleur filtre. Je cherchais le meilleur filtre qui puisse être exprimé avec un très petit nombre de décalages entiers, d'additions et de soustractions . Cela peut sembler étrange, mais prenez votre temps.

Vous avez peut-être remarqué que lorsque j'ai montré les coefficients de h.264, HEVC et le filtre bilinéaire, ainsi que mon filtre, je les ai écrits comme des numérateurs entiers sur des dénominateurs entiers, comme ceci:

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}; 

Mais dans le cas de sinc fenêtré, j'ai agi différemment et l'ai écrit comme ceci:

 LanczosKernel[] = {0.02446, -0.13587, 0.61141, 0.61141, -0.13587, 0.02446}; 

La raison en est que le sinc fenêtré est en fait déduit d'une fonction mathématique continue qui n'a rien à voir avec les fractions entières ordinaires. Lorsque vous utilisez ce filtre, des nombres à virgule flottante (aussi précis que possible) sont utilisés qui correspondent aux valeurs de la fonction sinc. Si vous vous efforcez de les appliquer avec précision, vous ne devez pas les arrondir aux fractions ordinaires, car cela ajoutera une erreur.

Les codecs vidéo ne peuvent traditionnellement pas se permettre d'effectuer de telles opérations. Les opérations en virgule flottante sur des tâches aussi «lourdes» que la compensation de mouvement sont tout simplement impossibles à utiliser sur des équipements de faible puissance ou spécialisés. Cela est particulièrement vrai si nous parlons de codecs standard de l'industrie qui devraient fonctionner sur une large gamme d'appareils, y compris des puces intégrées à faible coût et à faible coût.

De plus, même si vous les exécutez sur le CPU, les jeux d'instructions modernes sont basés sur SIMD, c'est-à-dire que les opérations entières sur le CPU peuvent toujours être effectuées plus rapidement: vous pouvez insérer deux entiers 16 bits dans l'espace d'un flottant 32 bits, doublant essentiellement les performances des opérations, par conséquent, si nous considérons le nombre exact de cycles par opération, un point flottant n'est pas toujours l'option la plus rapide.

Vous voyez maintenant pourquoi cette fonctionnalité était importante. Comme je n'avais besoin que de simples opérations sur des nombres entiers de 16 bits, j'ai cherché ces noyaux qui peuvent être exprimés en petits nombres entiers sur des diviseurs de deux à 64 et pas plus. Il s'agit d'un ensemble de filtres beaucoup plus limité que si je considérais un ensemble de 6 coefficients à virgule flottante.

De même, pour des raisons d'efficacité, je n'ai considéré aucun autre nombre d'échantillons. La seule option était 6 ou moins, donc je n'ai même pas testé les versions avec 8 ou 10 échantillons.

C'est ainsi que nous sommes arrivés à la première réponse: "probablement pas". Si nous adhérons à ces restrictions, nous ne trouverons probablement pas de meilleur filtre qui puisse être appliqué un nombre infini de fois sans dégradation. Le noyau du filtre de la première partie est probablement le meilleur que nous puissions trouver, bien que je dois admettre que je ne peux pas le prouver de manière exhaustive.

Mais que se passe-t - il si nous n'avons pas besoin de respecter de telles restrictions?

Version à virgule flottante

Si nous nous débarrassons des limitations spécifiques à la version originale de Bink 2 (qui est maintenant assez obsolète - de nombreuses révisions ont depuis été publiées) et utilisons des coefficients arbitraires en virgule flottante, comment pouvons-nous améliorer les résultats?

Eh bien, puisque nous savons que mon noyau entier ne se dégrade jamais, et nous savons que Lanczos est plus net, mais se dégrade, il est logique que nous puissions trouver une place entre les deux ensembles de coefficients où la dégradation commence. J'ai donc écrit un programme qui m'a aidé à trouver ce point particulier, et voici le noyau que j'ai trouvé:

 MyFloatKernel6[] = {0.027617, -0.130815, 0.603198, 0.603198, -0.130815, 0.027617}; 

Ce noyau nécessite 272 itérations pour converger, mais il est infiniment stable et semble beaucoup plus net que mon filtre entier:


En fait, il est presque impossible de le distinguer de l'original:


Presque ... mais pas tout à fait. Si vous regardez attentivement, vous pouvez toujours voir le flou et l'atténuation dans les zones à contraste élevé. La façon la plus simple de voir cela est dans l'œil d'un "dinosaure" orange et dans des zones de lumière vive derrière le bambou.

Autrement dit, un filtre à virgule flottante à 6 échantillons est certainement meilleur, mais ce n'est pas parfait. Peut-il encore être amélioré?

Augmentez la largeur du filtre

Initialement, un filtre à 6 échantillons a été sélectionné pour les mêmes raisons que les fractions à petits entiers: je cherchais un filtre extrêmement efficace. Mais maintenant, nous faisons des recherches et nous sommes déjà passés à des nombres à virgule flottante, alors pourquoi ne pas envisager un filtre plus large?

En combinant notre filtre entier à 6 échantillons avec le Lanczos à 6 échantillons, nous avons obtenu un très bon filtre. Pourquoi ne le couplons-nous pas avec les Lanczos à 8 échantillons?

Le Lanczos à 8 échantillons ressemble à ceci:

 Lanczos8[] = {-0.01263, 0.05976, -0.16601, 0.61888, 0.61888, -0.16601, 0.05976, -0.01263}; 

Comme le Lanczos à 6 échantillons, il est très instable et s'effondre après 178 itérations:


Si nous recherchons un meilleur filtre entre un filtre entier à 6 échantillons et un Lanczos à 8 échantillons, nous trouvons ce filtre à 8 échantillons plutôt remarquable:

 MyFloatKernel8[] = {-0.010547, 0.052344, -0.156641, 0.614844, 0.614844, -0.156641, 0.052344, -0.010547}; 

En tant que filtre infiniment stable, il fonctionne incroyablement bien. Il converge après 202 itérations (la convergence est plus rapide que mes deux filtres), et ressemble tellement à l'original qu'il est difficile de déterminer lequel est lequel:


Voici à nouveau l'original pour référence:


Par rapport à mon filtre entier d'origine, il y a une amélioration significative.

Comment fonctionnent les filtres infiniment stables?

J'allais terminer ce post quelque chose comme ceci:

"Je ne sais pas exactement comment tout cela fonctionne. Dans d'autres domaines où j'ai travaillé avec les transformations applicables à l'infini, je sais comment les mathématiques des limites sont effectuées et une analyse utile est créée. Tout d'abord, il s'agit de l'analyse de la surface limite pour les surfaces de subdivision, où les valeurs propres et les vecteurs propres de la matrice de subdivision sont calculés, après quoi il est possible de prendre précisément la limite à un degré infini. Mais je n'ai aucune expérience dans la réalisation d'une telle analyse pour les filtres halfpel, car ils ne laissent pas les pixels en place, mais les décalent latéralement. "

C'était mon plan. Mais entre l'écriture des première et deuxième parties, j'ai envoyé les résultats du filtre amélioré à Fabien Giessen et Charles Bloom . Il n'est pas surprenant qu'ils connaissent les mathématiques nécessaires à l'étude analytique de ce problème. Il s'est avéré que pour les filtres, il y a vraiment une analyse des valeurs propres et des vecteurs, mais cela ne fonctionne pas tout à fait de cette façon.

Mais il peut être facilement exécuté - en fait, il est intégré dans les programmes CAM comme un processus trivial en une seule étape et nous pouvons vraiment regarder les valeurs propres des filtres. Il ne nous donne pas de réponses complètes, car ici le fait d' arrondir (ou troncature) à 8 bits (ou 10 bits, ou 12 bits) après chaque filtrage est important, car la troncature affecte la méthode d'accumulation des erreurs par rapport à l'algèbre infiniment précise.

Malheureusement, comme ce n'est pas du tout mon domaine d'expertise, je ne peux même pas avoir un aperçu précis de cette analyse. J'ai demandé à Fabien et Charles s'ils pouvaient écrire des articles avec les bonnes informations qu'ils m'ont envoyées par la poste (ils ont tous les deux des blogs techniques - le blog ryg et cbloom rants ), et Fabien a écrit une excellente série d'articles sur les fondements mathématiques des filtres stables . Si vous êtes intéressé par la structure théorique de ce qui se passe dans mes deux articles, alors je vous recommande de lire cette série!