Comment le flou gaussien est-il mis en œuvre?

J'ai lu que le flou se fait en temps réel avec des graphiques en le faisant sur un axe, puis sur l'autre.

J'ai déjà fait un peu de convolution dans 1D dans le passé, mais je ne suis pas très à l'aise avec cela, je ne sais pas non plus quoi convolver dans ce cas.

Quelqu'un peut-il expliquer en termes simples comment un flou gaussien en 2D d'une image est créé?

J'ai également entendu dire que le rayon du flou peut avoir une incidence sur les performances. Est-ce dû à une convolution plus importante?

En convolution, deux fonctions mathématiques sont combinées pour produire une troisième fonction. Dans le traitement des images, les fonctions sont généralement appelées noyaux. Un noyau n'est rien d'autre qu'un tableau (carré) de pixels (une petite image pour ainsi dire). Habituellement, les valeurs du noyau totalisent un. Cela permet de s’assurer qu’aucune énergie n’est ajoutée ou retirée de l’image après l’opération.

Plus précisément, un noyau gaussien (utilisé pour le flou gaussien) est un tableau carré de pixels dont les valeurs de pixel correspondent aux valeurs d’une courbe gaussienne (en 2D).

Chaque pixel de l'image est multiplié par le noyau gaussien. Pour ce faire, placez le pixel central du noyau sur le pixel de l'image et multipliez les valeurs de l'image d'origine par les pixels du noyau qui se chevauchent. Les valeurs résultant de ces multiplications sont additionnées et ce résultat est utilisé pour la valeur au pixel de destination. En regardant l'image, vous multiplieriez la valeur en (0,0) dans le tableau en entrée par la valeur en (i) dans le tableau du noyau, la valeur en (1,0) dans le tableau en entrée par la valeur en (h ) dans le tableau du noyau, et ainsi de suite. puis ajoutez toutes ces valeurs pour obtenir la valeur de (1,1) sur l'image de sortie.

Pour répondre à votre deuxième question en premier, plus le noyau est gros, plus l'opération est coûteuse. Ainsi, plus le rayon du flou est large, plus l'opération durera longtemps.

Pour répondre à votre première question, comme expliqué ci-dessus, la convolution peut être effectuée en multipliant chaque pixel d'entrée par le noyau entier. Cependant, si le noyau est symétrique (ce qui est un noyau gaussien), vous pouvez également multiplier chaque axe (x et y) indépendamment, ce qui réduira le nombre total de multiplications. En termes mathématiques appropriés, si une matrice est séparable, elle peut être décomposée en matrices (M × 1) et (1 × N). Pour le noyau gaussien ci-dessus, cela signifie que vous pouvez également utiliser les noyaux suivants:

$$\frac1{256}\cdot\begin{bmatrix} 1&4&6&4&1\\ 4&16&24&16&4\\ 6&24&36&24&6\\ 4&16&24&16&4\\ 1&4&6&4&1 \end{bmatrix} = \frac1{256}\cdot\begin{bmatrix} 1\\4\\6\\4\\1 \end{bmatrix}\cdot\begin{bmatrix} 1&4&6&4&1 \end{bmatrix}$$

Vous devez maintenant multiplier chaque pixel de l'image d'entrée avec les deux noyaux et ajouter les valeurs résultantes pour obtenir la valeur du pixel de sortie.

Pour plus d'informations sur la manière de savoir si un noyau est séparable, suivez ce lien .

Edit: les deux noyaux présentés ci-dessus utilisent des valeurs légèrement différentes. En effet, le paramètre (sigma) utilisé pour la courbe gaussienne afin de créer ces noyaux était légèrement différent dans les deux cas. Pour une explication sur les paramètres qui influencent la forme de la courbe gaussienne, les valeurs dans le noyau suivent ce lien.

Edit: dans la deuxième image ci-dessus, il est indiqué que le noyau utilisé est retourné. Cela ne fait bien sûr aucune différence si le noyau que vous utilisez n'est pas symétrique. La raison pour laquelle vous devez retourner le noyau est liée aux propriétés mathématiques de l'opération de convolution (voir le lien pour une explication plus détaillée de la convolution). En termes simples: si vous n’inversez pas le noyau, le résultat de l’opération de convolution sera inversé. En retournant le noyau, vous obtenez le résultat correct.

Voici le meilleur article que j'ai lu sur le sujet: Flou gaussien efficace avec échantillonnage linéaire . Il répond à toutes vos questions et est vraiment accessible.

Pour le profane, explication très brève: le gaussien est une fonction avec la propriété d'être séparable, ce qui signifie qu'une fonction gaussienne 2D peut être calculée en combinant deux fonctions gaussiennes 1D.

Ainsi, pour une taille ( ), il suffit d’évaluer valeurs ( ), ce qui est nettement inférieur. Si votre opération consiste à lire un élément de texture (communément appelé "tap" ), c'est une bonne nouvelle: moins de taps est moins cher, car un extraction de texture a un coût.$n \times n$$O(n^2)$$2 \times n$$O(n)$

C'est pourquoi les algorithmes de flou utilisent cette propriété en effectuant deux passes: une pour flouter horizontalement en regroupant les pixels horizontaux, et une pour flou verticalement en regroupant les pixels verticaux. Le résultat est la couleur de pixel floue finale.$n$$n$

En général, une convolution est effectuée en prenant l'intégrale du produit de deux fonctions dans une fenêtre glissante, mais si vous n'êtes pas mathématicien, ce n'est pas une explication très utile et ne vous donnera certainement pas une intuition utile. pour ça. Plus intuitivement, une convolution permet à plusieurs points d’un signal d’entrée d’affecter un seul point d’un signal de sortie.

Puisque vous n'êtes pas très à l'aise avec les convolutions, examinons d'abord ce que signifie une convolution dans un contexte discret comme celui-ci, puis examinons un flou plus simple.

Dans notre contexte discret, nous pouvons multiplier nos deux signaux en multipliant simplement chaque échantillon correspondant. L'intégrale est également simple à faire discrètement, nous additionnons simplement chaque échantillon dans l'intervalle d'intégration. Une simple convolution discrète consiste à calculer une moyenne mobile. Si vous voulez prendre la moyenne mobile de 10 échantillons, cela peut être considéré comme une convolution de votre signal par une distribution de 10 échantillons de long et 0,1 de hauteur, chaque échantillon de la fenêtre est tout d'abord multiplié par 0,1, puis tous les 10 sont additionnés pour produire la moyenne. Cela révèle également une distinction intéressante et importante: lorsque vous êtes flou avec une convolution, la distribution que vous utilisez doit totaliser 1,0 sur tous ses échantillons, sinon elle augmentera ou diminuera la luminosité globale de l'image lorsque vous l'appliquerez.

Maintenant que nous avons examiné les convolutions, nous pouvons passer au flou. Un flou gaussien est mis en oeuvre par convolution d’une image par une distribution gaussienne. Les autres flous sont généralement mis en oeuvre en convoluant l'image par d'autres distributions. Le flou le plus simple est le flou de la boîte et utilise la même distribution que celle décrite ci-dessus, une boîte avec une unité de surface. Si nous voulons rendre une zone 10x10 floue, nous multiplions chaque échantillon de la zone par 0,01, puis nous les additionnons tous pour produire le pixel central. Nous devons encore nous assurer que la somme totale de tous les échantillons de notre distribution de flou est égale à 1,0 pour que l'image ne soit ni plus claire ni plus sombre.

Le flou gaussien suit la même procédure générale que celle utilisée pour le flou en boîte, mais il utilise une formule plus complexe pour déterminer les poids. La distribution peut être calculée en fonction de la distance au centre r, en évaluant La somme de tous les échantillons d'un gaussien sera éventuellement environ 1,0 si vous échantillonnez chaque pixel, mais le fait qu'une gaussienne ait un support infini (il a des valeurs partout) signifie que vous devez utiliser une version légèrement modifiée qui totalise 1.0 en utilisant seulement quelques valeurs.

$$\frac{e^{-x^2/2}}{\sqrt{2\pi}}$$

Bien sûr, ces deux processus peuvent être très coûteux si vous les exécutez sur un très grand rayon, car vous devez échantillonner beaucoup de pixels pour calculer le flou. C'est ici que l'astuce finale intervient: un flou gaussien et un flou de boîte sont ce qu'on appelle un flou "séparable". Cela signifie que si vous appliquez le flou sur un axe, puis sur l’autre, le résultat obtenu est identique à celui obtenu si vous l’aviez effectué simultanément sur les deux axes. Cela peut être extrêmement important. Si votre flou a une largeur de 10 pixels, il nécessite 100 échantillons au format naïf, mais seulement 20 échantillons séparés. La différence ne fait que grandir car le flou combiné est , tandis que la forme séparée est .$O(n^2)$$O(n)$

La chose la plus importante à prendre en compte lors de l’application du flou gaussien est, comme d’autres l'ont déjà souligné, de séparer le filtre de convolution 2D en deux convolutions 1D, car il ramène la complexité de à .$O(n^2)$$O(n)$

Mais il y a deux autres astuces à prendre en compte dans une implémentation réelle:

Le filtre a un certain rayon et à cause de cela, aux limites mêmes, vous devrez calculer avec les pixels qui se trouvent en dehors de l'image. Dans ce cas, vous pouvez essayer l'une des opérations suivantes: pour les pixels extérieurs, vous prenez simplement la dernière valeur possible (c'est-à-dire le pixel situé à la limite même, comme dans max(x, 0). Vous pouvez également "refléter" l'image vers l'extérieur (comme dans x < 0 ? -x : x). Ou vous pouvez simplement vous arrêter à la frontière, mais vous devrez alors ajuster le filtre de convolution du dénominateur de sorte qu'il soit égal à 1. Par exemple:

$$\operatorname{sum} \frac{1}{256} \begin{bmatrix} 1 & 4 & 6 & 4 & 1 \\ 4 & 16 & 24 & 16 & 4 \\ 6 & 24 & 36 & 24 & 6 \\ 4 & 16 & 24 & 16 & 4 \\ 1 & 4 & 6 & 4 & 1 \\ \end{bmatrix} = \operatorname{sum} \frac{1}{225} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 16 & 24 & 16 & 0 \\ 0 & 24 & 36 & 16 & 0 \\ 0 & 16 & 24 & 16 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} = 1.$$ Une autre astuce concerne le calcul des coefficients réels du noyau. Évidemment, vous pouvez essayer d'implémenter la fonction gaussienne, mais le moyen le plus rapide consiste à observer que le noyau 1D rassemble le triangle de Pascal . Par exemple:

     1
    1 1
   1 2 1
  1 3 3 1
[1 4 6 4 1]