Classez et segmentez des données visuelles

Dans le chapitre précédent, je vous avais introduit la problématique de réduction du bruit d'une image et présenté une première solution, le lissage par moyennage. Cette technique est en fait basée sur l'application d'un filtre.

Le filtrage constitue un volet important en traitement d'images, et un de ses objectifs principaux est de nettoyer l'image en éliminant le plus de bruit possible. Dans ce chapitre, nous allons nous intéresser davantage à cette classe de méthodes, et en particulier à la notion de filtre linéaire. 

Les filtres linéaires

Il existe différentes techniques de filtrage selon le type de bruit à atténuer. Le lissage par moyennage utilise un filtre linéaire et fait partie, en ce sens, de la classe de filtrage la plus simple.

Rappelons tout d'abord la notion de linéarité. Un opérateur $\$\backslash (G\backslash )\$$ est dit linéaire s'il vérifie les deux propriétés suivantes :

• Additivité : pour deux fonctions $\$\backslash (u\backslash )\$$ et $\$\backslash (v\backslash )\$$, $\$\backslash (G(u\; +\; v)\; =\; G(u)\; +\; G(v)\backslash )\$$

• Homogénéité : pour une fonction $\$\backslash (u\backslash )\$$ et une constante $\$\backslash (\backslash lambda\backslash )\$$, $\$\backslash (G(\backslash lambda\; u)\; =\; \backslash lambda\; G(u)\backslash )\$$

En traitement d'images, et même plus généralement en traitement du signal, un filtre linéaire est un système qui transforme une image en utilisant un opérateur linéaire. Il s'agit généralement d'un traitement local.

Une propriété importante d'un filtre linéaire est l'invariance par translation : la modification d'un pixel dépend de son voisinage, et non de sa position dans l'image.

Le lissage par moyennage utilise bien un filtre linéaire, appelé filtre moyenneur. En effet, l'opération appliquée à l'image initiale de représentation matricielle $\$\backslash (X\backslash )\$$ pour obtenir l'image débruitée $\$\backslash (Y\backslash )\$$ est composée d'additions et d'une division :

$\$\backslash [Y\_\{i,j\}\; =\; \backslash dfrac\{X\_\{i-1,j-1\}\; +\; X\_\{i-1,j\}\; +\; X\_\{i-1,j+1\}\; +\; X\_\{i,j-1\}\; +\; X\_\{i,j\}\; +\; X\_\{i,j+1\}\; +\; X\_\{i+1,j-1\}\; +\; X\_\{i+1,j\}\; +\; X\_\{i+1,j+1\}\}\{9\}\backslash ]\$$

Comme je vous l'avais expliqué, ce lissage part du principe selon lequel chaque pixel dans une image de bonne qualité doit avoir une intensité similaire à celle de ses voisins. La moyenne arithmétique suppose même que chaque voisin contribue à part égale. Cela peut donner lieu à des incohérences, surtout si le nombre de voisins considéré est grand : il y a de plus grandes chances qu'un pixel soit corrigé en fonction de pixels qui décrivent des objets différents dans l'image, et qui ont donc peu de points communs avec lui !

Ainsi, nous pouvons améliorer le lissage par moyennage, en donnant des poids différents aux pixels dans la moyenne : les coefficients n'ont plus tous la même valeur et dépendent de la position du voisin par rapport au pixel central.

L'opération appliquée par ce filtre moyenneur "généralisé" s'écrit alors formellement de la façon suivante :

où les coefficients $\$\backslash (H\_\{i,j\}\backslash )\$$ désignent les poids dans la moyenne. Vous pouvez constater qu'il s'agit toujours d'un filtre linéaire. 

En fait, il est possible de généraliser la forme de la transformation mathématique opérée par n'importe quel filtre linéaire : c'est l'objet de la prochaine section !

L'opérateur de convolution

Un filtre linéaire remplace la valeur de chaque pixel en entrée par une combinaison linéaire des intensités de ses pixels voisins. L'opérateur permettant d’effectuer cette transformation est appelé produit de convolution. C'est pourquoi l'application d'un filtre linéaire est également connue sous le terme de filtrage par convolution. 

En notant $\$\backslash (*\backslash )\$$ l'opérateur de convolution, la relation mathématique entre l'image initiale $\$\backslash (X\backslash )\$$ et l'image filtrée $\$\backslash (Y\; \backslash )\$$ pour tout type de filtre linéaire s'écrit $\$\backslash (Y\; =\; H\; *\; X\backslash )\$$.  Cela revient à modifier la valeur de chaque pixel de la manière suivante :

$\$\backslash [Y\_\{i,j\}\; =\; \backslash sum\_\{u=-k\}^k\; \backslash sum\_\{v=-k\}^k\; H\_\{u,v\}.X\_\{i-u,\; j-v\}\backslash ]\$$

 
$\$\backslash (H\backslash )\$$ est le noyau (ou masque) de convolution : il s'agit d'une matrice carrée de taille impaire $\$\backslash (2k+1\backslash )\$$, qui caractérise le filtre linéaire appliqué. Par exemple, le lissage par moyennage sur un voisinage de taille $\$\backslash (2k+1\backslash )\$$ a pour noyau

Cette formule correspond bien à une généralisation de la transformation opérée par le filtre moyenneur "perfectionné" : pour vous en convaincre, prenez $\$\backslash (k=1\backslash )\$$ et réécrivez chaque terme de la double somme. Les coefficients de $\$\backslash (H\backslash )\$$ correspondent aux différents poids accordés aux pixels environnants. 

Notez que le produit de convolution est bien un opérateur linéaire invariant par translation puisqu'il est seulement construit à partir de multiplications et d'additions.

Vous vous êtes sûrement déjà aperçus des limites du produit de convolution : l'opération ne peut être appliquée aux pixels situés aux bords de l'image. Il faut donc appliquer un traitement spécifique à ces rangées.

Plusieurs solutions sont possibles : on peut donner la même valeur à tous ces pixels, par exemple 0 (noir), de sorte que l'image filtrée présente un contour monochrome, ou on peut appliquer une convolution partielle avec les pixels voisins disponibles. Dans tous les cas, il est préférable de ne pas réduire la taille de l'image !

Exemples de filtres courants

Le choix des coefficients et de la taille du noyau de convolution $\$\backslash (H\backslash )\$$ nous permet de définir une multitude de filtres linéaires différents. Les deux types de filtres linéaires les plus populaires sont les filtres moyenneurs, que nous connaissons déjà, et les filtres gaussiens, que nous allons étudier maintenant. 

Filtre gaussien

Un filtre gaussien est un filtre linéaire dont les éléments du noyau de convolution sont déterminés selon la densité d'une loi gaussienne centrée à 2 dimensions :

$\$\backslash [h(x,y)\; =\; \backslash frac\{1\}\{2\backslash pi\backslash sigma^2\}\; e^\{-\backslash frac\{x^2+y^2\}\{2\backslash sigma^2\}\}\backslash ]\$$

Comme le noyau doit comporter un nombre fini d'éléments, nous devons calculer une approximation discrète de la densité gaussienne, celle-ci étant continue et strictement positive sur $\$\backslash (\backslash mathbb\{R\}\backslash )\$$ . En pratique, la fonction est souvent échantillonnée sur $\$\backslash (]-3\backslash sigma,\; 3\backslash sigma[\backslash )\$$ , car elle est quasiment nulle en dehors de cet intervalle.  

De plus, le filtre gaussien est séparable : son noyau peut-être écrit comme un produit de deux noyaux plus simples. En effet, $\$\backslash (e^\{-\backslash frac\{x^2+y^2\}\{2\backslash sigma^2\}\}\; =\; e^\{-\backslash frac\{x^2\}\{2\backslash sigma^2\}\}.\; e^\{-\backslash frac\{y^2\}\{2\backslash sigma^2\}\}\backslash )\$$ , donc $\$\backslash (H\; =\; H\_x^\backslash top.H\_y\backslash )\$$ avec $\$\backslash (H\_x\backslash )\$$ (respectivement $\$\backslash (H\_y\backslash )\$$) le vecteur colonne contenant les exponentielles en $\$\backslash (x\backslash )\$$ (respectivement en $\$\backslash (y\backslash )\$$).

La convolution 2D peut alors être réalisée de façon plus efficace : on applique d'abord une convolution gaussienne 1D sur les lignes de l'image, puis une autre sur les colonnes.

En résumé, le design du noyau d'un filtre gaussien se fait selon le processus ci-dessous :

1. Choix de la taille du noyau $\$\backslash (H\backslash )\$$ : c'est l'entier $\$\backslash (2k+1\backslash )\$$impair inférieur le plus proche de $\$\backslash (6\backslash sigma\backslash )\$$

2. Calcul des vecteurs $\$\backslash (H\_x\backslash )\$$ et $\$\backslash (H\_y\backslash )\$$ : on calcule les valeurs $\$\backslash (h\_i\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\backslash pi\backslash sigma^2\}\}e^\{\backslash frac\{-i^2\}\{2\backslash sigma^2\}\}\backslash )\$$  pour $\$\backslash (i\; \backslash in\; \backslash \{0,...,k\backslash \}\backslash )\$$, et par symétrie, $\$\backslash (h\_\{-i\}\; =\; h\_i\backslash )\$$

3. Normalisation : on divise chaque coefficient par la somme de tous les poids  $\$\backslash (h\_i\backslash )\$$

La performance du filtre gaussien dépend de la valeur de sa variance : plus l'image est bruitée, plus on doit augmenter la variance, mais plus l'image devient floue. Remarquez que tout filtre linéaire agit de la façon suivante sur une image bruitée :

  $\$\backslash (G(I+\backslash eta)(x,y)=G(I)(x,y)+G(\backslash eta)(x,y)\backslash )\$$ 

Le terme  G(\eta)(x,y)  nous convient très bien: une somme pondérée de  n  gaussiennes de même variance  \sigma^2  est encore une gaussienne, mais de variance  \frac{\sigma^2}{n}  . On atténue donc le bruit et quand n est suffisamment grand, il tend vers 0. Malheureusement, on n'obtient pas l'image parfaite  I  mais l'image lissée  G(I)  , d'où le résultat flou. Ce problème est intrinsèque aux filtres linéaires !

Filtre médian (non-linéaire)

Bien que les filtres linéaires soient facile à concevoir et à implémenter, notamment avec la propriété de séparabilité, ils ne parviennent pas toujours à éliminer efficacement le bruit, notamment le bruit impulsionnel (par exemple, "poivre et sel").

Ces limitations ont motivé la création des filtres non-linéaires : il s'agit de filtres dont le fonctionnement ne peut être défini comme un produit de convolution.  

Un exemple de filtre non-linéaire est le filtre médian, dont le principe est proche du filtre moyenneur : la valeur de chaque pixel est remplacée par la médiane (et non la moyenne) de son voisinage.