Le filtre médian relâché pour la suppression du bruit

Patrick Labatut
( email adress )

Étude d'article réalisée dans le cadre du cours :
Traitement des Images (DEA MVA 2004-2005).

Table des matières

Présentation du problème
Solution proposée
Propriétés
1. Propriétés statistiques
2. Propriétés déterministes
Implémentation
Résultats
Conclusion
Bibliographie
Annexe

1 - Présentation du problème

La suppression du bruit est un des pré-traitements essentiels en vision par ordinateur : il s'agit d'éliminer ce qui est du aux aléas des mesures tout en essayant de ne pas altérer l'information utile contenue dans l'image. Cette opération est fondamentale pour assurer la robustesse des techniques de vision de haut niveau qui requièrent, pour la plupart, l'estimation de dérivées spatiales directement à partir des niveaux de gris des pixels de l'image.

Nous nous limiterons dans la suite de cette étude à la suppression du bruit additif (gaussien ou impulsionnel) : le bruit multiplicatif fait l'objet de méthodes spécifiques.

Les filtres linéaires (dont les plus utilisés en pratique sont le filtre moyenne et le filtre gaussien, en général sur de petites fenêtres de taille 3x3 ou 5x5) ne sont pas très bons et ne permettent d'éliminer que le bruit gaussien additif et pas le bruit impulsionnel. De plus, ils émoussent les contours et font disparaître les lignes trop fines ou les coins.

Aussi, on préfère utiliser le filtre médian qui jouit ainsi d'une bonne réputation puisqu'il arrive à combiner à la fois une suppression efficace du bruit impulsionnel et la conservation des détails suffisamment importants. Ce filtre fait partie de ce que l'on appelle la classe des filtres de rang : la sortie de ce filtre est basée sur un tri des échantillons observés au voisinage de celui dont on détermine la réponse. Les filtres de rang sont généralement robustes, car insensibles aux valeurs extrêmes en entrée et ils ont la propriété intéressante de ne pas créer de valeur qui n'existe pas en entrée.

Cependant, dans le cas de lignes fines ou de coins (particulièrement utilisés en appariement en stéréo-vision), le filtre médian est trop sévère et élimine tout ou partie de ces détails entre autres parce que l'analyse qu'il effectue ne respecte pas les relations de voisinage entre ces éléments.

Nous allons donc étudier le filtre médian relâché, qui est une légère évolution du filtre médian simple, présenté dans les articles [1] et [2] et dont le but est d'avoir une tolérance plus importante envers les détails.

2 - Solution proposée

Dans cette section, nous rappelons la définition du filtre médian et présentons le filtre médian relâché (les notations sont les mêmes que dans les articles de référence [1] et [2]) ainsi que le filtre médian pondéré centré.

On considère une suite d'échantillons (X_i)_i∈Z^d, et une fenêtre glissante W. Soit W_i la fenêtre centrée en un échantillon X_i et contenant 2N+1 échantillons : W_i={X_i+r,r∈W}.

Exemples :

En dimension 1 (N=1, W={-1,0,-1}):
En dimension 2 (avec une fenêtre carrée 3x3 : N=4, W={(-1,-1),(0,-1),(1,-1),(-1,0),(0,0),(1,0),(-1,1),(0,1),(1,1)}) :

Soit alors ([W_i]_r)_r∈W la suite ordonnée des échantillons de la fenêtre W_i : [W_i]₁≤...≤[W_i]₂≤...≤[W_i]_2N+1. On pose m=N+1.

La sortie du filtre médian simple (Simple Median abrégé SM dans la suite) au point X_i est : Y_i=SM(W_i)=med(W_i)=[W_i]_m.

Soit maintenant l et u deux bornes (1≤l≤m≤u≤2N+1) qui définissent ainsi une sous-suite de la suite ([W_i]_r)_r∈W, telle que si X_i appartient à cette sous-suite alors il est n'est pas modifié par le filtre médian relâché. Ces deux paramètres autorisent un compromis entre suppression du bruit et conservation des détails.

La sortie du filtre médian relâché (Relaxed Median abrégé RM dans la suite) au point X_i est : Y_i=RM_l,u(W_i)=X_i si X_i∈[[W_i]_l,[W_i]_u] et Y_i=RM_l,u(W_i)=[W_i]_m=SM(W_i) sinon.

On remarque que pour certaines valeurs particulières de u et l, on obtient des filtres remarquables :

filtre médian : l=u=m.
filtre identité : l=1 et u=2N+1.

Enfin, on introduit le filtre médian pondéré centré (K est un entier positif), qui est une autre variante simple du filtre médian :

La sortie du filtre médian pondéré centré (Center Weighted Median abrégé CWM dans la suite) au point X_i est : Y_i=CWM_2K+1(W_i)=med(W_i•{X_i}•...•{X_i})=SM(W_i•{X_i}•...•{X_i}) où • désigne la concaténation de listes (suites finies) et 2K concaténations sont effectuées (il y a 2K+1 exemplaires de X_i dans la liste dont on prend l'élément médian).

La duplication de l'échantillon d'entrée X_i dans la suite ordonnée dont on prend l'élément médian permet d'augmenter sa chance de sortir intact du filtre.

3 - Propriétés

Voici maintenant quelques propriétés vérifiées par le filtre médian relâché qui permettent de le comparer au filtre médian simple (les preuves des propriétés non triviales sont données dans les articles de référence [1] et [2]) :

3.1 - Propriétés statistiques

Si les entrées du filtre RM_l,u (de taille 2N+1) sont des variables aléatoires indépendantes identiquement distribuées, alors la probabilité pour que la sortie du filtre median relâché soit l'échantillon central de la fenêtre est donnée par : Pr[Y_i=X_i]=(u-l+1)/(2N+1).

Cette propriété permet de connaître la réponse du filtre au bruit et quelles structures dans l'image peuvent être conservées en présence de bruit : si l décroit la probabilité de sortie de l'échantillon central augmente. Enfin, deux propriétés dont on ne donne qu'un énoncé qualitatif :

RM préserve mieux les contours que SM.

RM préserve bien les lignes en présence de bruit blanc.

3.2 - Propriétés déterministes

On fait l'hypothèse suivante de symétrie sur les bornes u et l : u=2N+2-l (u et l sont symétriques par rapport à la position médiane m).

La sortie de RM est invariante par translation et homothétie de l'entrée : ∀ s,t ∈ ℜ, RM(sW_i+t)=sRM(W_i)+t.

Les propriétés suivantes permettent de comprendre quelles structures sont conservées par le filtre RM. On appelle signal « racine », un signal qui n'est pas modifié par filtrage.

Un signal est racine de RM_l,2N+2-l si et seulement si, pour toute position de la fenêtre glissante, il existe au moins l échantillons ayant la même valeur que l'échantillon central.

Dans le cas du filtre médian, on sait que les signaux racines sont les voisinages constants (de longueur minimale N+1) et les contours (au sens de régions monotones entre deux voisinages constants de valeurs différentes).

La longueur minimal d'un voisinage constant pour RM_l,2N+2-l est l.

On remarque que lorsque l décroît, la longueur minimale des voisinages constants décroît également, et donc des détails plus fins peuvent être conservés.

Les racines de RM_l,2N+2-l sont racines de RM_l',2N+2-l' pour tout l≥l'. Autrement dit, en notant R_l l'ensemble des racines de RM_l,2N+2-l et S l'ensemble de toux les signaux : ...⊆R_l⊆R_l-1⊆...⊆S.

4 - Implémentation

Le filtre médian relâché et le filtre médian pondéré centré ont été implémentés sous la forme de modules MegaWave2 pour permettre de manipuler aisément des images. D'autres modules auxiliaires ont aussi été écrits pour faciliter l'exploitation des images obtenues et l'interprétation des résultats.

5 - Résultats

Nous avons comparé les performances en débruitage du filtre médian simple (SM), du filtre médian relâché (RM) et du filtre médian pondéré centré (CWM) avec les paramètres suivants :

bruit blanc de déviation standard σ=15, 20 et 25
bruit impulsionnel de densité d=10, 20 et 30%
fenêtre de taille 3x3 et 5x5
bornes variables pour le filtre médian relâché : (l=4, u=6) et (l=3, u=7) pour une fenêtre 3x3 et (l=12, u=14), (l=11, u=15) et (l=10, u=16) pour une fenêtre 5x5
poid variable pour le filtre médian pondéré centré : K=1 pour une fenêtre 3x3 et K=1 et 2 pour une fenêtre 5x5

L'efficacité du filtrage est mesurée par le rapport des distances euclidiennes entre l'image bruitée filtrée et l'image originale d'une part et l'image bruitée et l'image originale d'autre part. Ce rapport est appelé moyenne normalisée de l'erreur au carré (Normalized Mean Square Error ou NMSE); il est ≥ 1 lorsque le filtrage a permis de se rapprocher de l'image originale au sens de la distance euclidienne. Ainsi si S désigne l'image originale, X l'image bruitée et Y l'image bruitée filtrée :

NMSE(S,X,Y)=Σ_i Σ_j(Y_i,j-S_i,j)²/Σ_iΣ_j(X_i,j- S_i,j)²

5.1 - Images synthétiques

Les images synthétiques utilisées sont les suivantes :

L'exemple suivant permet de vérifier que les filtres se comportent comme prévu : ils éliminent facilement le bruit impulsif et par contre ne sont pas très efficaces contre le bruit gaussien. Visuellement les résultats des différents filtres sont comparables.

image originale (512x512)

image bruitée (bruit impulsionnel de densité d=10%)

image bruitée filtrée (SM 5x5)

image bruitée filtrée (RM_12,14 5x5)

image bruitée filtrée (CWM₃ 5x5)

image bruitée (bruit gaussien de déviation standard σ=20)

image bruitée filtrée (SM 5x5)

image bruitée filtrée (RM_12,14 5x5)

image bruitée filtrée (CWM₃ 5x5)

Dans ce deuxième exemple, on constate la supériorité de RM avec des paramètres bien choisis pour la conservation des détails fins : le bloc 4 de droite de l'image initiale se transforme en rectangle presque uniforme lorsqu'il est filtré par SM alors qu'avec RM il est encore possible de distinger clairement 3 segments horizontaux et verticaux. Enfin, CWM est à mi-chemin entre les deux puisqu'il reste possible de distinguer 3 segments horizontaux et verticaux mais ceux-ci ont commencé à fusionner.

image originale (256x256)

image filtrée (SM 5x5)

image filtrée (RM_10,16 5x5)

image filtrée (CWM₅ 5x5)

Nous avons regroupé ici les moyennes de la NMSE sur les deux images synthétiques, pour différents réglages des filtres. On constate bien que les filtres ont un comportement analogue : ils sont décevants face au bruit gaussien et excellents pour le bruit impulsionnel avec le classement SM≤RM≤CWM.

**NMSE** pour divers filtres et bruits
filtre (fenêtre)		gaussien (σ)			impulsionnel (d)
filtre (fenêtre)		15	20	25	10%	20%	30%
SM	3x3	0.5425810	0.3405870	0.2437620	0.0356110	0.0278720	0.0384251
RM_4,6	3x3	0.4769250	0.3170470	0.2335200	0.0335183	0.0278186	0.0391969
RM_3,7	3x3	0.3773710	0.2662700	0.2122870	0.0321824	0.0416147	0.0619325
CWM₃	3x3	0.3372030	0.2349680	0.1835550	0.0288263	0.0327181	0.0537714
SM	5x5	1.3305800	0.7578130	0.5006020	0.0809747	0.0439601	0.0353378
RM_12,14	5x5	1.3156400	0.7523660	0.4963390	0.0797212	0.0427297	0.0348045
RM_11,15	5x5	1.3035700	0.7468660	0.4959120	0.0792875	0.0411022	0.0335655
RM_10,16	5x5	1.2603000	0.7243900	0.4813470	0.0769085	0.0401380	0.0330367
CWM₃	5x5	1.0170100	0.5872090	0.3954290	0.0665592	0.0349049	0.0297042
CWM₅	5x5	0.9098750	0.5239890	0.3538110	0.0576801	0.0303343	0.0286806

5.2 - Images Réelles

Les images réelles utilisées sont les suivantes:

Cet exemple sur une image réelle permet de montrer les difficultés rencontrées face au réglage des paramètres . Le filtre RM conserve le mieux le motif en escalier entre la toiture de droite et la bâtisse, alors que le filtre SM le transforme en vaguelettes. Le filtre CWM parvient également à ne pas trop détériorer ces détails mais une analyse plus approfondie montre qu'il est moins bon que RM. Par contre, ces deux filtres font apparaître d'importants artefacts dans le ciel alors que le filtre effectue presque parfaitement son travail de suppression du bruit : la conservation des détails implique une perte de la qualité de la suppression du bruit.

image originale (256x256)

image bruitée (bruit impulsionnel de densité d=10%)

image filtrée (SM 3x3)

image bruitée filtrée (RM_3,7 3x3)

image bruitée filtrée (CWM₃ 3x3)

À nouveau, on regroupe dans un tableau les résultats de NMSE pour plusieurs paramètres des filtres : le classement établi sur les images synthétiques n'est plus vraiment respecté, on constate seulement que RM peut être rendu meilleur que SM en suppression du bruit pour un bon choix de paramètres et que CWM est assez souvent très légèrement meilleur que SM.

**NMSE** pour divers filtres et bruits
filtre (fenêtre)		gaussien (σ)			impulsionnel (d)
filtre (fenêtre)		15	20	25	10%	20%	30%
SM	3x3	0.0924191	0.0660461	0.0537103	0.0207873	0.0133615	0.0139090
RM_4,6	3x3	0.0938630	0.0685944	0.0566740	0.0192259	0.0129928	0.0147151
RM_3,7	3x3	0.0990236	0.0782932	0.0682388	0.0175680	0.0163661	0.0226740
CWM₃	3x3	0.0777088	0.0633544	0.0565274	0.0135314	0.0123988	0.0177747
SM	5x5	0.1259790	0.0773626	0.0546564	0.0347986	0.0184012	0.0136698
RM_12,14	5x5	0.1260440	0.0774750	0.0548055	0.0344945	0.0182481	0.0135851
RM_11,15	5x5	0.1262370	0.0779649	0.0553622	0.0339218	0.0178939	0.0133892
RM_10,16	5x5	0.1262530	0.0787450	0.0565035	0.0330836	0.0174180	0.0131312
CWM₃	5x5	0.1065120	0.0672765	0.0488298	0.0281264	0.0151737	0.0117241
CWM₅	5x5	0.0938279	0.0624122	0.0474645	0.0231363	0.0130885	0.0108974

5.3 - Applications

Comme nous l'avons déjà rappelé en introduction, la suppression du bruit n'est qu'un pré-traitement avant l'utilisation de techniques de vision de haut niveau. Nous donnons ainsi deux applications : les détections de contours et de coins dans une image (très utilisées respectivement en segmentation et en stéréo-vision).

5.3.1 - Détection de contours de Canny

L'exemple suivant ne permet pas de trancher favorablement en faveur d'un des filtres : SM fait perdre certains contours fins sur le nez, entre les yeux et les narines mais les deux autres filtres rajoutent des artefacts qui entraînent la détection de petits contours qui n'existent pas.

image originale (512x512)

image bruitée (bruit impulsionnel de densité d=20%)

contours de l'image originale

contours de l'image bruitée

contours de l'image bruitée filtrée (SM 3x3)

contours de l'image bruitée filtrée (RM_3,7 3x3)

contours de l'image bruitée filtrée (CWM₃ 3x3)

5.3.2 - Détection de coins de Harris

Les coins de Harris permettent de démarrer le processus d'appariement en stéréo-vision, processus qui trouve des correspondances entre deux images. Il est très important que les coins utilisés soient de bonne qualité, pour assurer une reconstruction correcte. Ici, on remarque au niveau de la fenêtre de droite, que le filtre SM fait apparaître de nombreux faux coins, alors que le filtre RM restitue presque les coins trouvés sur l'image originale. Le filtre CWM engendre de trop nombreux coins en particulier des coins souvent très proches les uns des autres mais aussi de vrais coins, ce qui est vraiment gênant pour l'application considérée ultérieurement. Ainsi, même si des artefacts apparaissent avec RM (dus à l'obligation d'être plus tolérant au bruit pour conserver les détails fins), ils ne se révèlent pas aussi génants que ceux créés par CWM ou, dans une moindre mesure, par SM.

image originale (256x256)

image bruitée (bruit impulsionnel de densité d=10%)

coins de l'image originale

coins de l'image bruitée

coins de l'image bruitée filtrée (SM 3x3)

coins de l'image bruitée filtrée (RM_3,7 3x3)

coins de l'image bruitée filtrée (CWM₃ 3x3)

6 - Conclusion

Nous avons montré par l'exemple que les propriétés du filtre médian relâché avancées dans les articles de référence [1] et [2] sont effectivement vérifiées : ce filtre qui n'est en fin de compte qu'une légère modification du filtre médian simple permet de choisir un compromis entre suppression du bruit et conservation des détails.

Cependant, jouer sur les paramètres l et u de ce filtre s'avère délicat et parfois insuffisant : on retrouve alors certains des défauts du filtre médian simple. De plus, dans la plupart des cas, le filtre médian pondéré centré se montre aussi performant sinon plus.

L'apport de ce filtre est donc plus théorique que pratique, si l'on veut vraiment lutter contre les deux inconvénients du filtre médian et de ses variantes simples, on pourra s'orienter d'une part vers les filtres médians à plusieurs niveaux ([5]) qui utilisent des masques conserver des détails fins ou bien vers les nouveaux travaux de l'un des auteurs ([6]) qui combinent les filtres moyenne et médian relâché pour lutter efficacement contre le bruit blanc et conserver suffisamment de détails.

7 - Bibliographie

[1]. A. Ben Hamza, P. L. Luque-Escamilla, J. Martinez-Aroza and R. Roman-Roldan, "Removing Noive and Preserving Details with Relaxed Median Filters", Journal of Mathematical Imaging and Vision, Vol. 11, pp. 161-177, 1999.
[2]. A. Ben Hamza, "Some Properties of Relaxed Median Filters", Digital Signal Processing Proceedings, Vol. 2, pp. 957-960, 1997.
[3]. I. Bloch, Y. Gousseau, H. Maître, D. Matignon, B. Pesquet-Popescu, F. Schmitt, M. Sigelle, F. Tupin, "Le Traitement des images - tome 1"
[4]. I. Bloch, Y. Gousseau, H. Maître, D. Matignon, B. Pesquet-Popescu, F. Schmitt, M. Sigelle, F. Tupin, "Le Traitement des images - tome 2"
[5]. G. R. Arce and R. E. Foster, "Detail-Preserving Ranked-Order Based Filters for Image Processing", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 37, No. 1, pp. 83-98, Jan 1989.
[6]. A. Ben Hamza and H. Krim, "Image Denoising: A Nonlinear Robust Statistical Approach", IEEE Transactions on Signal Processing, Vol. 49, No. 12, pp. 3045-3054, Dec 2001.

8 - Annexe

Code source

Le code source des filtres et scripts écrits pour cette étude d'article :

Données

Pour des raisons de place, toutes les données originales ou générées à l'aide des filtres ne sont pas incluses (images au format TIFF compressées sans perte), mais peuvent être recréées à l'aide des scripts, des filtres et de l'environnement MegaWave2.

Liens

Archive de la page web, des images et du code source :: rmedian.tar.gz
MegaWave2 :: http://www.cmla.ens-cachan.fr/Cmla/Megawave/