Convolution 2D dans le traitement de l’image

Cet article donne un aperçu de la convolution bidimensionnelle et du remplissage du zéro en ce qui concerne le traitement numérique de l’image.

Dans mon article précédent « Un meilleur aperçu du DSP : apprendre la convolution », j’ai discuté de la convolution et de ses deux applications importantes dans le domaine du traitement du signal. Là, les signaux étaient vraisemblablement considérés comme unidimensionnels dans le domaine spatial. Cependant, le processus de convolution peut aussi être effectué sur des signaux multidimensionnels.

Dans cet article, nous allons essayer de mieux comprendre le processus et les conséquences de la convolution bidimensionnelle, très utilisée dans le domaine du traitement des images.

La définition de la convolution 2D

La convolution impliquant des signaux unidimensionnels est appelée convolution 1D ou simplement convolution. Si la convolution est effectuée entre deux signaux s’étendant le long de deux dimensions mutuellement perpendiculaires (c’est-à-dire si les signaux sont de nature bidimensionnelle), on parlera alors de convolution 2D. Ce concept peut être étendu pour impliquer des signaux multidimensionnels en raison desquels nous pouvons avoir une convolution multidimensionnelle.

Dans le domaine numérique, la convolution est effectuée en multipliant et en accumulant les valeurs instantanées des échantillons qui se chevauchent correspondant à deux signaux d’entrée, dont l’un est retourné. Cette définition de la convolution 1D est applicable même pour la convolution 2D sauf que, dans ce dernier cas, l’une des entrées est retournée deux fois.

Ce type d’opération est largement utilisé dans le domaine du traitement numérique des images où la matrice 2D représentant l’image sera convoluée avec une matrice comparativement plus petite appelée noyau 2D.

Un exemple de convolution 2D

Tentons de calculer la valeur des pixels de l’image de sortie résultant de la convolution de la matrice d’image x de taille 5×5 avec le noyau h de taille 3×3, représentée ci-dessous sur la figure 1.

Figure 1 : Matrices d’entrée, où x représente l’image originale et h représente le noyau. Image créée par Sneha H.L.

Pour y parvenir, la procédure à suivre étape par étape est décrite ci-dessous.

Etape 1 : Inversion de la matrice

Cette étape implique une inversion du noyau le long, disons, des lignes, suivie d’une inversion le long de ses colonnes, comme le montre la figure 2.

Figure 2 : Représentation picturale de l’inversion de matrice. Image créée par Sneha H.L.

En conséquence, chaque (i,j)ème élément du noyau d’origine devient le (j,i)ème élément de la nouvelle matrice.

Etape 2 : Faire glisser le noyau sur l’image et effectuer l’opération MAC à chaque instant

Faire glisser le noyau inversé sur l’image, en avançant pixel par pixel.

Pour chaque cas, calculer le produit des pixels se chevauchant mutuellement et calculer leur somme. Le résultat sera la valeur du pixel de sortie à cet endroit particulier. Pour cet exemple, les pixels qui ne se chevauchent pas seront supposés avoir une valeur de « 0 ». Nous en discuterons plus en détail dans la prochaine section sur le « Zero Padding ».

Dans le présent exemple, nous commencerons à faire glisser le noyau en colonne d’abord, puis nous avancerons le long des rangées.

Pixels rangée par rangée

D’abord, couvrons complètement la première rangée, puis avançons vers la deuxième, et ainsi de suite.

Pendant ce processus, le premier chevauchement entre le noyau et les pixels de l’image se produirait lorsque le pixel en bas à droite du noyau tombe sur la valeur du premier pixel en haut à gauche de la matrice d’image. Ces deux valeurs de pixel sont mises en évidence et représentées en rouge foncé sur la figure 3a. Ainsi, la première valeur de pixel de l’image de sortie sera 25 × 1 = 25.

Puis, faisons avancer le noyau le long de la même ligne d’un seul pixel. À ce stade, deux valeurs de la matrice du noyau (0, 1 – indiquées en caractères rouge foncé) se chevauchent avec deux pixels de l’image (25 et 100 indiqués en caractères rouge foncé), comme le montre la figure 3b. Ainsi, la valeur du pixel de sortie résultant sera 25 × 0 + 100 × 1 = 100.

Figure 3a, 3b. Résultats de convolution obtenus pour les pixels de sortie à l’emplacement (1,1) et (1,2). Image créée par Sneha H.L.

Figure 3c, 3d : Résultats de convolution obtenus pour les pixels de sortie à l’emplacement (1,4) et (1,7). Image créée par Sneha H.L.

En avançant de la même manière, toutes les valeurs des pixels de la première ligne de l’image de sortie peuvent être calculées. Deux exemples de ce type, correspondant aux quatrième et septième pixels de sortie de la matrice de sortie, sont présentés sur les figures 3c et 3d, respectivement.

Si nous faisons encore glisser le noyau le long de la même ligne, aucun des pixels du noyau ne chevauche ceux de l’image. Cela indique que nous avons terminé le long de la ligne actuelle.

Déplacer verticalement vers le bas, avancer horizontalement

L’étape suivante serait d’avancer verticalement vers le bas d’un seul pixel avant de recommencer à se déplacer horizontalement. Le premier chevauchement qui se produirait alors est comme indiqué sur la figure 4a et en effectuant l’opération MAC sur eux ; nous obtenons le résultat comme 25 × 0 + 50 × 1 = 50.

Après cela, nous pouvons faire glisser le noyau dans la direction horizontale jusqu’à ce qu’il n’y ait plus de valeurs qui se chevauchent entre le noyau et les matrices d’image. Un tel cas correspondant à la sixième valeur de pixel de la matrice de sortie (= 49 × 0 + 130 × 1 + 70 × 1 + 100 × 0 = 200) est illustré à la figure 4b.

Figure 4a, 4b. Résultats de convolution obtenus pour les pixels de sortie à l’emplacement (2,1) et (2,6). Image créée par Sneha H.L.

Ce processus de déplacement d’un pas vers le bas suivi d’un balayage horizontal doit être poursuivi jusqu’à la dernière ligne de la matrice d’image. Trois exemples aléatoires concernés par les sorties de pixels aux emplacements (4,3), (6,5) et (8,6) sont présentés sur les figures 5a-c.

Figure 5a. Résultats de convolution obtenus pour les pixels de sortie en (4,3). Image créée par Sneha H.L.

Figure 5b. Résultats de convolution obtenus pour les pixels de sortie à (6,5). Image créée par Sneha H.L.

Figure 5c. Résultats de convolution obtenus pour les pixels de sortie à (8,6). Image créée par Sneha H.L.

Etape

Donc la matrice de sortie résultante sera:

Figure 6. La matrice de sortie résultante de notre exemple. Image créée par Sneha H.L.

Zero Padding

La formulation mathématique de la convolution 2-D est donnée par

$$ y\left=\sum_{m=-\infty}^\infty\sum_{n=-\infty}^\infty h\left \cdot x\left $$

où, x représente la matrice de l’image d’entrée à convoluer avec la matrice du noyau h pour aboutir à une nouvelle matrice y, représentant l’image de sortie. Ici, les indices i et j concernent les matrices d’image tandis que ceux de m et n traitent de celle du noyau. Si la taille du noyau impliqué dans la convolution est de 3 × 3, alors les indices m et n vont de -1 à 1. Dans ce cas, une expansion de la formule présentée donne

$$ y\left=\sum_{m=-\infty}^\infty h\left \cdot x\left + h\left \cdot x\left \\cdot x\left $$

$$ y\left= h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \\ + h\left \cdot x\left + h\left \cdot x\left + h\left \cdot x\left \\c + h\left \cdot x\left + h\left \cdot x\left $$

Cela indique que pour obtenir chaque pixel de sortie, il faut effectuer 9 multiplications dont les facteurs sont les éléments de pixels superposés de l’image et du noyau. Cependant, lorsque nous avons calculé la valeur de notre premier pixel de sortie, nous n’avons effectué qu’une seule multiplication (figure 3a reproduite comme figure 7a). Qu’est-ce que cela signifie ? Cela implique-t-il une incohérence avec la forme d’équation de la convolution 2-D ?

Non, pas vraiment. Car, le résultat obtenu par la sommation de neuf termes produits peut être égal au produit d’un seul terme si l’effet collectif des huit autres termes produits s’égalise à zéro. L’un de ces cas est celui où chaque produit des huit autres termes s’évalue à zéro. Dans le contexte de notre exemple, cela signifie que tous les termes produits correspondant aux pixels non chevauchants (entre l’image et le noyau) doivent devenir nuls pour que les résultats du calcul par formule soient égaux à ceux du calcul graphique.

D’après nos connaissances élémentaires en mathématiques, nous savons que si au moins un des facteurs impliqués dans la multiplication est nul, alors le produit résultant est également nul. Par cette analogie, nous pouvons affirmer que, dans notre exemple, nous devons avoir un pixel-image à valeur zéro correspondant à chaque pixel non chevauchant de la matrice du noyau. La représentation picturale de cette situation est illustrée à la figure 7b. Une chose importante à noter ici est qu’un tel ajout de zéros à l’image ne modifie pas l’image dans tous les sens, sauf sa taille.

Figure 7 : Remplissage de zéro montré pour le premier pixel de l’image (Dessiné par moi)

Ce processus d’ajout de zéros supplémentaires est connu sous le nom de remplissage de zéro et doit être fait dans chaque cas où il n’y a pas de pixels d’image pour chevaucher les pixels du noyau. Dans notre exemple, le remplissage du zéro doit être effectué pour chaque pixel qui se trouve le long des deux premières lignes et colonnes ainsi que pour ceux qui apparaissent le long des deux dernières lignes et colonnes (ces pixels sont indiqués en bleu sur la figure 8). En général, le nombre de lignes ou de colonnes à capitonner à zéro de chaque côté de l’image d’entrée est donné par (nombre de lignes ou de colonnes dans le noyau – 1).

Figure 8

Une chose importante à mentionner est le fait que le capitonnage à zéro n’est pas la seule façon de traiter les effets de bord apportés par la convolution. D’autres techniques de rembourrage comprennent le rembourrage répété, l’extension périodique, le miroir, etc. (Digital Image Processing Using Matlab 2E, Gonzalez, Tata McGraw-Hill Education, 2009).

Summary

Cet article a pour but d’expliquer la méthode graphique de la convolution 2-D et le concept de rembourrage zéro en ce qui concerne le traitement des images numériques.