Noyau (traitement d'image)

En traitement d'images, un noyau, une matrice de convolution ou un masque est une petite matrice utilisée pour le floutage, l'amélioration de la netteté de l'image, le gaufrage, la détection de contours, et d'autres. Tout cela est accompli en faisant une convolution entre le noyau et l'image.

Détails

Suivant les valeurs, un noyau peut avoir un grand nombre d'effets.

Opération	Noyau	Résultat
Identité	${\begin{bmatrix}0&0&0\\0&1&0\\0&0&0\end{bmatrix}}$
La détection de contours	${\begin{bmatrix}\ \ 1&0&-1\\\ \ 0&0&\ \ 0\\-1&0&\ \ 1\end{bmatrix}}$
	${\begin{bmatrix}0&\ \ 1&0\\1&-4&1\\0&\ \ 1&0\end{bmatrix}}$
	${\begin{bmatrix}-1&-1&-1\\-1&\ \ 8&-1\\-1&-1&-1\end{bmatrix}}$
Amélioration de la netteté	${\begin{bmatrix}\ \ 0&-1&\ \ 0\\-1&\ \ 5&-1\\\ \ 0&-1&\ \ 0\end{bmatrix}}$
Box blur (normalized)	${\frac {1}{9}}{\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}}$
Flou de Gauss 3 × 3 (approximation)	${\frac {1}{16}}{\begin{bmatrix}1&2&1\\2&4&2\\1&2&1\end{bmatrix}}$
Flou de Gauss 5 × 5 (approximation)	${\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}}$
Masque flou 5 × 5 Basé sur un flou de Gauss avec un montant en 1 et un seuil de 0 (sans masquage)	${\frac {-1}{256}}{\begin{bmatrix}1&4&\ \ 6&4&1\\4&16&\ \ 24&16&4\\6&24&-476&24&6\\4&16&\ \ 24&16&4\\1&4&\ \ 6&4&1\end{bmatrix}}$

Ce sont juste quelques exemples montrant les effets des noyaux de convolutions sur les images.

Origine

L'origine est la position du noyau qui est au-dessus (conceptuellement) du pixel courant. Elle peut être à l’extérieur du noyau, cependant, elle correspond la plupart du temps à un élément du noyau. Pour un noyau symétrique, l'origine est souvent l'élément central.

Convolution

La convolution est le processus consistant à ajouter chaque élément de l'image à ses voisins immédiats, pondéré par les éléments du noyau. C'est une forme de produit de convolution. Il devra être noté que les opérations matricielles effectuées (les convolutions) ne sont pas des multiplications traditionnelles de matrices malgré le fait que ce soit noté par un « * ».

Par exemple, si nous avons deux matrices 3×3, la première étant le noyau et la seconde une partie de l'image, la convolution est le processus consistant à retourner les colonnes et les lignes du noyau puis de multiplier localement les valeurs ayant la même position, puis sommer le tout. L'élément au coordonnée [2, 2] (l'élément central) de l'image de sortie devrait être pondéré par la combinaison de toutes les entrées de la matrice de l'image, avec les poids données par le noyau comme suit :

$\left({\begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}}{\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}\right)[2,2]=(i\cdot 1)+(h\cdot 2)+(g\cdot 3)+(f\cdot 4)+(e\cdot 5)+(d\cdot 6)+(c\cdot 7)+(b\cdot 8)+(a\cdot 9).$

Les autres entrées devraient être pondérées de manière similaire, appliquée à tous les pixels de l'image.

La valeur d'un pixel dans l'image de sortie peut être calculé en multipliant le noyau sur chaque pixel. Cela peut être décrit algorithmiquement par le pseudo-code suivant :

pour chaque ligne de image d'entrée:
   pour chaque pixel de ligne:

      accumulateur prend la valeur 0

      pour chaque ligne noyau de noyau:
         pour chaque élement de ligne noyau:

            si la position de élément  correspond* à la position de pixel alors
               multiplier la valeur de élément par la valeur de pixel
               ajouter le résultat à accumulateur
            fin du si

      mettre pixel de l'image de sortie à accumulateur

*les pixels sont retrouvés par rapport à l'origine du noyau

Si le noyau est symétrique, on place le centre (l'origine) du noyau sur le pixel courant ; de ce fait, le noyau chevauchera aussi les pixels voisins. Ensuite, il faudra multiplier les éléments du noyau avec la valeur des pixels qu'il chevauche et ajouter le tout pour obtenir le résultat. La valeur de sortie sera celle du pixel courant qui est à l'origine du noyau.

Si le noyau n'est pas symétrique, il faut retourner par rapport à l'axe horizontal et vertical avant de calculer la convolution comme ci-dessus.

Traitement des bords

Traitement par extension

Les noyaux de convolution demandent souvent des valeurs à l’extérieur des limites de l'image, il existe plusieurs méthodes pour pallier ce problème.

Extension

Le pixel le plus près du bord est conceptuellement étendu autant que nécessaire pour donner des valeurs pour la convolution. Les pixels en coin sont étendus à 90°, et les autres sont étendus en ligne.

Enroullage (Wrap)

L'image est conceptuellement enroulée, les valeurs sont récupérées des bords opposés.

Miroir

L'image est conceptuellement reflétée sur les bords. Par exemple, pour lire un pixel 3 unité en dehors de l'image, on lit le pixel à 3 unité à l'intérieur de l'image.

Crop

Tout pixel demandant l'utilisation de pixel en dehors de l'image est passé. Cette méthode peut résulter en une image de sortie étant un petit peu plus petite, avec les bords coupés.

Kernel Crop

Tout pixel dans le noyau requérant l'utilisation des pixels en dehors de l'image n'est pas utilisé et la normalisation est ajustée pour compenser.

Normalisation

La normalisation est définie comme la division de chaque élément du noyau par la somme de tous les éléments du noyau, donc la somme des éléments d'un noyau normalisé est 1. Cela assure que la moyenne des pixels dans l'image modifiée est aussi lumineuse que dans l'image originale

Voir aussi

Bibliographie

• Jamie (n.d.) Ludwig, Image Convolution, pdf (lire en ligne)
• Olivier Lecarme et Karine Delvare, The Book of GIMP : A Complete Guide to Nearly Everything, janvier 2013, 429 p. (ISBN 978-1-59327-383-5, lire en ligne)
• Jason van Gumster et Robert Shimonski, GIMP Bible, mars 2012, 438–442 p. (ISBN 978-0-470-52397-1, lire en ligne)
• Linda G. Shapiro et George C. Stockman, Computer Vision, février 2001, 53–54 p. (ISBN 978-0-13-030796-5)

Liens externes

• Implementing 2d convolution on FPGA
• vImage Programming Guide: Performing Convolution Operations
• « Image Processing using 2D-Convolution »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}
• GNU Image Manipulation Program - User Manual - 8.2. Convolution Matrix
• Interactive Demonstration of 3x3 Convolution Kernels