LES PYRAMIDES MORPHOLOGIQUES

 
 
 
 
 
 


 
 
 
 
 

Rapport projet Fidel Kpan - Philippe Maillet
DEA MVA - ENS Cachan
kpan@dptmaths.ens-cachan.fr
maillet@dptmaths.ens-cachan.fr





Introduction:

En traitement d'images, l'approche morphologique a pour but de faciliter la reconnaissance de formes dans une image. Il s'agit souvent de simplifier l'image pour arriver au niveau de detail qui nous interesse. Les pyramides morphologiques permettent une analyse multi-resolutions utilisant des operateurs de morphologie (l'erosion et la dilatation).  Dans un premier temps, la notion generale de pyramide sera formalisee mathematiquement. Puis nous verrons un exemple de construction avec les operateurs morphologiques. Enfin, une comparaison avec les pyramides d'ondelettes sera donnee.
 

Principe general des pyramides :    soit une famille d'espaces .
Supposons qu'on veille passer du niveau  j  au niveau j+1 par le moyen d'opérateur d' analyse .
De même pour passer du niveau  j+1 au niveau plus bas j  on a besoin d'un opérateur de synthèse .
On obtient le schéma : .
Chaque opérateur d'analyse est désigné pour réduire l'information contenue dans l'image au niveau j. et donc est généralement non-inversible.
La composition  donne une approximation de l'image  tandis qu'  on impose à l'opérateur de synthèse d'etre inversible.
On obtient ainsi la condition des pyramides :
Pour tout  , les opérateurs etsatisfassent :
pour   ( 1)
La condition (1) entraîne que la composée  est idempotente.
Le schéma des pyramides introduit plus haut peut être utilisé pour obtenir une autre représentation de l'image x. Cela introduit une addition  et soustraction  sur l'espace  .
Soit  l'image d'origine, on a le schéma récurrent suivant :
où 

 

L'image originale est reconstruite exactement à partir des  et des details  par la formule :

qui est la transformation inverse.

Au niveau j, l'approximation est obtenue en partant de xj et en appliquant l'operateur de synthese a chaque niveau (du niveau j

au niveau 0).
Les pyramides morphologiques :
Soit un espace , une paire d'opérateurs  avec  et   est une adjonction si :
si et seulement si  pour tout .
Dans ce cas  est une érosion et  une dilatation.
Cette pyramide vérifie les contraintes suivantes:
(i)   Les espaces d'image  sont definies sur des ensembles decroissants de points (treillis de points).
(ii)   La paire Analyse/Synthèse  forme une adjonction.
Supposons qu'il existe deux ensembles S, Q et une relation binaire sur   s --> q.  Concretement, S et Q vont representer respectivement les
points sur les treillis au niveau j et au niveau j+1. Les relations s donnant q vont permettre de calculer les valeurs de niveau de gris des points q en fonction des valeurs des points s (et inversement).
Soit  et  les ensembles de niveaux de gris respectifs de S et Q .On peut définir une adjonction  entre  et de la façon suivante :
et  où et . (2)
La paire  est une adjonction et pour qu'elle vérifie la condition (1) on a la proposition suivante :
Proposition :      la paire donnée par (2) vérifie la condition (1)  sur .
Si et seulement si pour  il existe  tel que : .
Remarque: les formules definissant les operateurs d' analyse/ synthese avec min et max correspond bien a des erosions/dilatations definies a l'aide d'un element structurant. Et donc l'approximation par analyse puis synthese revient a une ouverture.
Implementation:
Pour l'implementation, les treillis utilises aux differents niveaux sont les suivants :

Aux niveaux j, avec j pair, la grille est du type 2^j.N*N.

Aux niveaux j, avec j impair, la grille est du type "quinconce".

La figure suivante montre le passage d'un niveau j pair au niveau j+1, puis le passage du niveau j+1 au niveau j+2 :
 
 


 
 

Les relations binaires s donne q sont representees par les fleches. L'ensemble Q est compose des "gros" points noirs, S comprend tous les points.

La partie suivante donne les resultats obtenus aux differents niveaux de la pyramide. En dessous sont presentes les resultats sur la meme image de depart en utilisant une pyramide d'ondelettes. Cette derniere pyramide est obtenue en utilisant les ondelettes de Daubechies a differents niveaux de resolution : 1, 2, 4, 8 et 16. L'image a droite de l'approximation donne l'image quantifiee utilisee pour la reconstitution.

Resultats experimentaux :
 

Pyramides morphologiques :
 

L'algorithme utilise est base directement sur la methode exposee ci-dessus. Pour un niveau choisi n, celui-ci calcule iterativement les images X1, ..., Xn definies sur des treillis de plus en plus reduits. L'approximation est ensuite calculee a partir de Xn en appliquant iterativement l'operateur de synthese.  Remarque : ci-dessous, les images Xn avec n impair paraissent plus "blanches" : etant definies sur un treillis en quinconce, les points "hors treillis ont ete arbitrairement mis a blanc.

Programme en C :   pyramide_source_C.htm
 
 

                                                                                                                        Niveau 0


                        image originale x0
 

                                                                                                                       Niveau 1
 


                         approximation                                                                          erreur  y0                                                                             x1
 

                                                                                                                       Niveau 2
 


 

                                                                                                                       Niveau 3
 


 

                                                                                                                       Niveau 4


 

                                                                                                                       Niveau 5


 
 
 

Pyramides en ondelettes:

Pour obtenir ces images, nous avons utilise les fonctions d'ondelettes de Matlab. Chaque niveau n correspond a la decomposition en ondelettes de frequence spatiale 1/2^n. Cela revient a partir d'une image echantillonnee tous les 2^n pixels. Ici, nous n'avons pas considere de niveaux intermediaires definis sur des treillis en quinconce.
 
 

                                                                                                                        Niveau 0
 


                        image originale x0

                                                                                                                        Niveau 1
 


                         approximation                                           image quantifiee et coefficients (peu visibles!)

                                                                                                                        Niveau 2
 
 


 

                                                                                                                        Niveau 3
 
 


 

                                                                                                                        Niveau 4
 
 


 
 

Commentaires :

La photo presente differents niveaux : on peut voir a l'echelle la plus grossiere les 3 pyramides comme un seul bloc, a une echelle intermediaire distinguer chacune des 3 pyramides, tandis qu'a l'echelle la plus fine on distingue les lignes horizontales sur les flancs des pyramides.

La pyramide morphologique conduit bien a des formes de plus en plus simplifiees, tandis que la pyramide d'ondelettes supprime au fur et a mesure les hautes frequences.

En plus de l'aide a la reconnaisance de forme, l'utilisation des pyramides permet une compression du codage de l'image puisqu'a chaque niveau l'approximation fournie utilise de moins en moins de points. On peut aussi imaginer une utilisation plus precise des pyramides sur une image : au lieu de choisir un niveau N pour l'ensemble de l'image, cette derniere pourrait etre subdivisee en blocs approximes par des niveaux differents dans la pyramide .(principe du codage Jpeg par blocs)

Bibliographie :

La methode de construction des pyramides morphologiques presentee dans ce rapport est basee sur le "Morphological pyramids and wavelets" de Henk Heijmans et John Goutsias.

Autres references :

Heijmans : Morphological Image Operators. 1994
Heijmans, Goutsias : Multiresolution signal decomposition schemes. Part 1: Linear and morphological pyramids.
C. Andrew Segall : Video tracking using morphological pyramids.
Rong-Jian Chen and Bin-Chang Chieu : Multiresolutional Image Representation and Coding Using Morphological Pyramids.