Opérateurs Morphologiques Auto-Duaux :
Application en Filtrage et Rehaussement d'Images*

2. Ordonné partiel auto-dual

Soient , on n'utilise pas dans tout ce qui suite l'opérateur de comparaison usuelle mais on définit un nouvel ordre partiel.

Au sens de cet opérateur, deux entiers sont comparables s'ils sont de même signe ou si au moins un des deux est nul. Cet opérateur est intéressant puisqu'il est auto-dual, c'est-à-dire,

Cet opérateur n'est pas le même que l'opérateur classique où l'application de négation inverse l'ordre. On note l'ensemble des fonctions d'un espace dans . hérite naturellement de l'ordre partiel de : pour on a

La figure à droite illustre deux fonctions x, y tels que

On considère un poset (ensemble ordonné partiel) avec l'ordre partiel . Un poset vérifie la propriété que tout sous-ensemble non vide a toujours un infimum, calculé par

Néanmoins, le supremum n'existe pas nécessairement. On dit donc que est un inf-demilattice complet, ou simplement cisl.

La figure à droite illustre deux fonctions et y incomparables, c'est-à-dire

3. Dilatation et Erosion

Définition 1. Soient et deux posets. Un couple d'applications et est appelé une adjonction si pour tout et

S'il n'y a pas de confusion, on va noter désormais les deux opérateur des posets par .

Proposition 2. Si est une adjonction alors et sont croissantes. Deplus,

Preuve: Pour tout on a . Donc par définition d'adjonction, on obtient ce qui implique . De la même manière, on a aussi
Pour montrer que , on applique directement le résultat précédent. On a car . En outre, donne . Donc, .
Idem pour .

Définition 3. Un opérateur est appellé une érosion si

pour toute collection non vide .

Etant donnée une érosion sur , on définit l'ensemble par

On appelle la dilatation adjointe à . Les deux propositions suivantes montrent que l'opérateur est bien défini.

Proposition 4. Si est une adjonction entre et alors a infimum , pour tout .

Preuve: Tout d'abord, comme , si , on obtient que est une borne inférieure de . On suppose maintenant que a est une borne inférieure de cet ensemble, alors car d'où le résultat.

Proposition 5. Le couple est une adjonction entre et

Preuve: On suppose que , alors appartient à mais est la borne inférieure de cet ensemble, donc . Maintenant on suppose que . On veut montrer que mais c'est clair par la définition de .

Définition 6. Un opérateur sur un poset est appellé une ouverture s'il est croissant, idempotent () et anti-extensive (, pour ).

Proposition 7. Si est une érosion , alors est une ouverture.

Preuve: est croissant puisqu'il est la composée de deux opérateurs croissants. La Proposition 2 donne , ce qui est équivalent à . On conclut le preuve en démontrant que pour tout mais c'est exactement l'inégalité de la Proposition 2.

On suppose maintenant qu'il existe un automorphisme sur . A un opérateur on peut associer un autre opérateur donné par

Si on choisit qui a l'interprétation d'une négation. Dans ce cas est appellé l'opérateur négatif de .

Il n'est pas difficile de vérifier que est une érosion et que avec . Dans le contexte des fonctions d'échelle de gris avec , cela veut dire que la négation (ou dual) d'une érosion est encore une érosion, ce qui est différent du cas classique où la négation d'une érosion est une dilatation et vice-versa.

4. Invariance par translation

Erosion et dilatation sont invariantes par translation dans la morphologie classique. On veut la même propriété pour le inf-demilattice complet (cisl). On rappelle que est l'ensemble des fonctions d'un espace dans . Soit un groupe abélien et A un sous-ensemble de , on définit l'opérateur par

    (1)

définit une érosion invariante par translation dans le sens que pour . L'ensemble A est appelé l'élément de structure de . La figure à droite représente l'érosion d'un signal pour le cas où A = {-3, -2, -1, 0, 1, 2, 3}

L'ensemble contient toutes les fonctions telles que

pour tout ,

pour un certain . Autrement dit,

pour tout ,

Ceci implique que le supremum de sur existe pour tout , et on a

On définit l'opérateur par

    (2)

Par construction, , c'est-à-dire que est la dilatation adjointe à l'érosion donné par (1).

On définit pour . Les opérateurs construits dans cette section ont quelques propriétés intéressantes.

Définition 8. Un opérateur sur est appellé auto-dual si .

Proposition 9. L'érosion donnée par (1) est auto-duale.

Preuve: On va démontrer que pour tout . En effet, par définition de la négation d'un opérateur et d'un signal on a

Par définition de l'érosion on a

Par conséquent,

On obtient en remarquant que l'opérateur est auto-dual

De la même manière, on peut montrer que pour tout . Donc, .

Les propositions suivantes montrent que la dilatation et l'ouverture sont également auto-duales.

Proposition 10. Si une érosion sur est auto-duale, alors si et seulement si , et est auto-duale aussi, i.e., pour .

Preuve: On suppose que , donc par définition de il existe tel que qui est équivalent à . Or , donc . De la même manière, on peut montrer que si .

On veut maintenant montrer que pour tout . En effet,

En remplaçant par , on obtient

L'opérateur est auto-dual donc l'infimum va changer la signe si on fait la même chose à tous les élément, c'est-à-dire,

Corrollaire 11. Soit l'érosion donnée par (1) et soit la dilatation adjointe, alors l'ouverture est auto-dual.

Preuve: Par définition de négation on a

On a déjà montré que et sont auto-duaux. Par conséquent,

d'où le résultat.

5. Construction directe d'opérateurs auto-duaux

Une simple méthode à construire un opérateur auto-dual sur est de décomposé des fonction aux parties positive et négative. Chaque peut être écrit comme

où et sont contenus dans , les fonctions appliquant dans .

C'est facile à voir que donc et sont les fonctions disjointes. Donné un opérateur sur , on peut définit un opérateur sur par

    (3)

Un opérateur sur est appellé à préserver la disjonction si les résulats et sont disjoints.

Proposition 12. Soit un opérateur à préserver la disjonction et une fonction donnée par (3).

(a) Si est croissant sur alors est croissant sur .

(b) L'opérateur est auto-dual, c'est-à-dire .

(c) Si est anti-extensive sur alors est anti-extensive sur .

(d) Si est idempotent alors est idempotent.

Preuve: Tout d'abord on veut montrer que

et

pour tout . On note par le supremum des fonctions. Ce n'est pas difficile à voir la relation de distributivité suivante

On a par définition de

En remplaçant 0 par et appliquant la relation de distributivié, on obtient

Mais n'est pas autre que car et sont les fonctions disjointes., Par conséquent,

De la même façon, on peut aussi montrer que .

(a) On suppose maintenant que , alors

d'où .

(b) Par définition de ,

Mais et , donc

(c) Pour on a et qui donnent .

(d) Pour on a

Par l'hypothèse, est idempotent, donc

.

Corollaire 13. Si est une ouverture sur alors est une ouverture auto-dualle sur .

Preuve: Par (a) (c) et (d) de la proposition précédente, est croissant, idempotent et anti-extensive donc est une ouverture. Elle est auto-dualle par (b).

6. Applications

a) Filtrage

Soit un opérateur morphologique auto-dual sur construit par une des sections précédentes. On suppose que l'entrée de l'opérateur est la différence d'une image et une image de référence . On définit l'opérateur sur par

    (4)

C'est facile à voir que

On observe que est un opérateur sur , c'est-à-dire, applique de dans si est anti-extensive à .

On suppose maintenant que l'image de référence dans (4) dépend à . On suppose que prend valeurs dans {0, 1,..., N} et choisit , où est un opérateur qui est auto-dual au sens que . Substitution dans (4) donne

Une simple calculation montre que

d'où est auto-dual. Le plus efficace "pousse" son entrée à zero (par exemple érosions ou ouvertures avec grands éléments de structure), le plus "pousse" vers

b) Rehaussement de contraste

Soit une image et soitent deux réels et tels que , et . On a démontré dans la section 2 que . Donc et sont la fonction minorante et la fontion majorante de respectivement. L'image rehaussée est obtenue en faisant basculer les points vers la fonction minorante ou vers la fonction majorante par

où . C'est facile à vérifier que l'image est rehausée aux points au bord, i.e. aux points dont le gradient est assez grand.

7. Logiciels

Les sources et images utilisées dans ce projet: [sources.zip] [sources.tar] [sources.tar.gz]

Qt	MegaWave2	Fonction	Usage
[addnoise.cpp]	[addnoise.c]	Bruiter l'image par le méthode poivre-sel	addnoise [-t type] [-p prob] in out    -t type : Type of noise: 0=pepper & salt, 1=salt, 2=pepper, default 0    -p prob : Probability of noise per cent, default 20    in : Input image    out : Output image
[filmedian.cpp]	[filmedian.c]	Filtre médian	filmedian [-w W] in out    -w W : Size of filtering window, must be odd (1..19), default 3    in : Input image    out : Output image
[diffpn.cpp]	[diffpn.c]	Soustraitre deux images à deux images positives	diffpn A B O1 O2    A : Input image A    B : Input image B    O1 : Output positive image    O2 : Output negative image
[sdopening.cpp]	[sdopening.c]	Ouverture auto-dual d'un image	sdopening [-w W] in out    -w W : Size of filtering window, must be odd (1..19), default 3    in : Input image    out : Output image
[closing.cpp]	[closing.c]	Ferméture (non auto-dualle) d'un image	closing [-w W] in out    -w W : Size of filtering window, must be odd (1..19), default 3    in : Input image    out : Output image
[filter.cpp]	[filter.c]	Filtre final	filter A B ref out    A : Input positive image    B : Input negative image    ref : Reference image    out : Output image
[enhancement.cpp]	[enhancement.c]	Rehaussement un image	enhancement in inf sup a b out    in : Input image    inf : Inferior image    sup : Superior image    a : Coefficient a    b : Coefficient b    out : Output image

8. Résultat expérimental

a) Filtrage

Soit une image src. On veut lui rajouter les bruits poivre-sel (impulsionnels) avec la probabilité 20%. L'image bruitée est inoise

addnoise -p 20 src inoise

Maintenant on construit une image de référence ref par le filtre médian avec la fenêtre 7x7.

filmedian -w 7 inoise ref

Après avoir l'image de référence, le filtrage auto-dual peut être calculé par un des deux façons suivants qui donnent le même résultat.

La deuxième manière va être introduite plus tard avec la comparaison du fitre auto-dual au filtre alterné séquentiel. Pour la première façon, on sert la construction directe présentée dans la section 5. On décompose la différence de l'image avec bruit et l'image de référence, diff = inoise - ref, à une partie positive diffp et une partie négative diffn. Explicitement, si le niveau d'un point diff(x, y) est positif alors diffp(x, y) = diff(x, y) et diffn(x, y) = 0. En revanche, si ce niveau n'est pas positif, diffp(x, y) est mis à nul alors que diffn(x, y) = -diff(x, y).

diffpn inoise ref diffp diffn

Il est immédiat que ces deux parties sont positives et disjointes. On peut donc appliquer l'opérateur d'ouverture (auto-dual ou non) séparément à deux parties diffp et diffn et obtient les résultats openp et openn.

opening diffp openp opening diffn openn

Enfin, l'image résultat out est simplement calculée par out = openp - openn + ref.

filter openp openn ref out

Image d'origin src	Image bruitée poivre-sel 20% inoise	Image de référence ref
Image openp	Image openn	Résultat final out

On peut voir que l'image obtenue out calculée par openp - openn + ref est beaucoup mieux que l'image de référence ref surtout sur quelques positions de l'image: le nez, les yeux et les dents et les lèvres de la fille. On peut le vérifier en visualisant les images openp et openn qui sont augmentée et diminuée à l'image de référence.

Maintenante, on bruite l'image d'origin par la méthode gaussienne avec déviation standard 10% (image gnoise).

fnoise -g 10 src gnoise

On va comparer l'efficace du filtre auto-dual avec du filtre alterné séquentiel. On rappelle qu'un filtre alterné séquentiel est une fonction s'exprimant comme:

où et sont des filtres morphologiques et . Il n'est pas difficile à vérifier que est croissant et idempotent donc un filtre morphologique. Ce filtre cependant n'est pas auto-dual. Les opérateurs d'ouverture et de ferméture vérifient les conditions de et respectivement. Donc le processus du filtre alterné séquentiel peut être comme suivant:

opening gnoise out2 closing out2 out2

On va calculer le filtre auto-dual par une autre façon que la précédente. Tout d'abord, on crée une image de référence en simplement choisissant l'image out2, et on calcule la différence entre cette image et l'image bruitée: diff = gnoise - out2.

fdiff gnoise out2 diff

On calcule directement l'ouverture de l'image de différence grâce à la propriété auto-dualle de cet opérateur et on trouve l'image open.

sdopening diff open

On remarque que l'image diff contient nombreux de bruits qui peuvent être enlevés efficacement par l'ouverture. Les éléments qui restent rajoutés à l'image de référence "poussent" l'image résultat plus proche de celle d'origin.

fadd ref open out3

Image bruitée gaussien 10% gnoise	Resultat par filtre alterné séquentiel out2	Resultat par filtre auto-dual out3

L'image résultat out3 du filtre auto-dual est mieux que l'image out2 qui est obtenue par le filtre alterné séquentiel. On peut vérifier cela en visualisant les zones du nez, de l'oeil gauche et surtout des dents de la fille.

Le filtre auto-dual dans ce projet ne donne pas toujours le meilleur résultat. Pour les bruits impulsionnels, le filtre de grain fonctionne de façon très efficace. C'est un filtre morphologique et aussi auto-dual au sens que . Cet opérateur enlève toutes les lignes de niveau dont l'aire est suffisamment petit donc peut supprimer les bruits impulsionnels.

fgrain inoise out4

Pour les bruits gaussiens, l'algorithme de diffusion d'une image en minimisant la variation totale est très efficace. Ce filtre cependant n'est pas morphologique ni auto-dual.

cfdiffuse gnoise out5

Résultat par filtre de grain out4	Resultat par filtre de diffusion out5

b) Rehaussement

Soit une image src, on applique la ferméture et l'ouverture séparément sur l'image src et on trouve l'image minorante inf et l'image majorante sup.

opening -w 9 src inf

closing -w 9 src sup

On rehausse l'image src avec deux paramètres et étant 0.3. L'image rehaussée est retournée à out.

enhancement src inf sup 0.3 0.3 out

L'opérateur de rehaussement fonctionne de la manière suivante. Si le niveau d'un point de l'image d'origin est assez proche de ce de l'image inférieure, il est mis à le niveau inférieur. En revanche, il est mis à le niveau supérieur s'il est près de ce niveau. Sinon, ce point ne change pas son niveau. L'effet de cet opérateur est que l'image est bien contrastée surtout aux points de bord où l'ouverture et la ferméture changent plus l'image inférieure et l'image supérieure par rapport à l'image d'origin. On peut vérifier cela en visualisant la différence |out - src|. Les paramètres et indiquent les intervals de niveau "proches" de deux extrémités.

Image d'origin src	Image inférieure inf	Image supérieure sup
Image après rehaussement out	Différence entre deux images |out-src|

Références

[1] Heijmans, H.J.A.M., Self-dual morphological operators and filters, J. Math. Imaging Vision 6 (1), 1996, p. 15-36.

[2] Heijmans, H.J.A.M. and Keshet, R., First steps towards a self-dual morphology, Proceedings of the IEEE International Conference on Image Processing, Vancouver, Canada, Sep 2000.

[3] Heijmans, H.J.A.M. and Keshet, R., Inf-semilattice approach to self-dual morphology, J. Math. Imaging Vision 17 (1), p. 55-80, 2002.

[4] Maître, H., Le traitement des images Tome I, ENST, Paris, 2004.

[5] Serra, J., Image Analysis and Mathematical Morphology, London, Academic Press, 1982.

[6] Serra, J., Image Analysis and Mathematical Morphology. Vol. 2: Theoretical Advances, London, Academic Press, 1988.