Prétopologie Traitement d’Images Et Structure Pyramidale

PRETOPOLOGIE EN TRAITEMENT D’IMAGES

1.1 SAPIN : l’introduction de la prétopologie en traitement d’image [Lamure-87] Certains algorithmes, par exemple celui de HILDITCH sur la squelettisation ou celui de CHASSERY sur le suivi de contour, relèvent naturellement d’une approche topologique mais n’utilisent pas en réalité ces concepts au sens mathématique. Dans leur fonctionnement, d’autres algorithmes mettent en jeu, de fait, des opérateurs qui à défaut d’être topologiques relèvent évidemment d’une version affaiblie de la topologie. Par exemple, l’ »Expand Algorithm » qui consiste à dilater une image binaire, selon une règle bien définie, fait fortement penser à la fonction d’adhérence topologique. En vertu de telles remarques faites sur les méthodes classiques de traitement d’images, M. LAMURE exprime la nécessité de pouvoir disposer d’un langage de type topologique « adapté à la situation » qui soit également un outil débouchant sur des procédures informatiques en accord total avec les concepts théoriques avancés. Il introduit donc pour la première fois la prétopologie en traitement et analyse d’images binaires et à niveaux de gris [Lamure-87]. M. LAMURE propose un système nommé SAPIN (Système d’Analyse Prétopologique des Images Numérisées) contenant des opérateurs informatiques qui sont l’exacte traduction des opérateurs prétopologiques définis a priori. Ces opérateurs possèdent des propriétés précisément connues qui permettent d’en évaluer les performances non seulement en termes de rapidité et de complexité mais aussi en termes de résultats ; ils partagent tous la propriété remarquable de fournir un résultat indépendant du mode de balayage de l’image traitée. Les opérateurs présentés sont des applications mathématiques de P(E) dans P(E) où E est un sous ensemble de Z² qui représentent le support de l’image à traiter. Dans ce cas l’image a été digitalisée au moyen d’une grille carrée. A chaque x de E on associe un voisinage, B(x), qui est un sous ensemble de ces huit voisins. Soit A une partie quelconque de E, on construit les opérateurs suivants ; sur P(E) :  – l’adhérence a : a(A) = {x ∈ E , B(x) ∩ Ac ≠ ∅} cet opérateur est utilisé pour dilater les formes dans l’image – le bord b : b(A) = {x ∈ A , B(x) ∩ Ac ≠ ∅} cet opérateur délimite la semi-frontière intérieure des objets – l’intérieur i : i(A) = {x ∈ E , B(x) ⊂ A } pour la recherche de l’intérieur des objets comme son nom l’indique – l’orle o : o(A) = {x ∈ Ac , B(x) ∩ A ≠ ∅} cet opérateur délimite la semi-frontière extérieure des objets – la frontière f : f(A) = {x ∈ E , B(x) ∩ A ≠ ∅ et B(x) ∩ Ac ≠ ∅ } il calcule un contour épais des formes – le dérivé d : d(A) = {x ∈ E , (B(x) – {x}) ∩ A ≠ ∅} c’est le dilaté de A auquel on a extrait les points isolés (ceux qui n’ont aucun voisin) – la cohérence c : c(A) = {x ∈ A , {B(x) – x} ∩ A ≠ ∅} cet opérateur calcul les points de A qui ne sont pas isolés – l’extérieur e : e(A) = {x ∈ E, B(x) ⊂ Ac ≠ ∅} l’extérieur de A donne le négatif (au sens photographique) de a(A).  

Les lignes de crête dans les images à niveaux de gris

Les prétopologies associées à des relations binaires occupent une place importante car elles sont basées sur la notion de relation locale entre des données c’est un concept important dans l’élaboration des algorithmes pratiques en reconnaissance des formes. Nous trouvons dans [Selmaoui-92] une utilisation intéressante des prétopologies des ascendants d’ordre 1 et des descendants d’ordre 1 en analyse d’image. Pour des raisons de simplification nous faisons une présentation de cette utilisation un peu différente de celle de l’auteur, tout en gardant l’esprit de sa méthode. L’algorithme utilisé par N. SELMAOUI dans la recherche des ligne de crête et des talwegs est inspiré de l’algorithme de groupement par propagation présenté en Classification Automatique.Partant de l’ensemble E représentant les pixels de l’image à traiter, on construit deux relations binaires à partir de la différence des niveaux de gris (NG) entre les pixels voisins de la façon suivante : ∀ p,q ∈ E, p R1 q Ù { q=p ou q est l’un des 8-voisins de p tel que NG(p) ≤ NG(q) } ∀ p,q ∈ E, p R2 q Ù { q=p ou q est l’un des 8-voisins de p tel que NG(p) ≥ NG(q) } ces deux relations binaires engendrent naturellement les adhérences prétopologiques associées adR1 et adR2 : ∀ A ⊂ E, adRi (A) = {x ∈ E, ∃ y ∈ A, y Ri x } i=1 ou 2 Grâce à ces deux adhérences l’auteur propose un algorithme qui peut détecter des lignes de crête et des talwegs (vallées) sur l’image analysée. Le déroulement de l’algorithme se fait grossièrement suivant les étapes suivantes : – on part d’une partie A (respectivement B) constituée des pixels vérifiant le minimum (respectivement le maximum) local en niveau de gris – on procède à des adhérences successives des points de A grâce à l’application adR2 (respectivement adR1 ) – ce processus itératif s’arrête lorsque pour tout x de A il existe un n tel que l’adhérence (n+1)- ième est identique à l’adhérence n-ième de x – à cette étape de l’algorithme on se retrouve avec des régions disjointes dont les « noyaux » sont les points de A (respectivement de B) – la fin de l’algorithme est marquée par la détermination des crêtes (respectivement les talwegs) qui sont définies par les frontières communes de ces régions. 

Détection des bassins versant par l’algorithme de PIEGAY 

L’image est assimilée à un relief dont l’altitude correspond aux niveaux de gris des pixels. Le but est de chercher les concavités (ou les bassins versants) du relief. Le support de la méthode est l’algorithme de PIEGAY que nous avons déjà présenté pour la classification automatique (cf : Chapitre III). Ici l’algorithme utilise des paramètres adaptés aux images à niveaux de gris. Les paramètres de l’algorithme pour le traitement d’images : Graphe de voisinage : Chaque pixel de l’image est muni d’un niveau de gris, d’un voisinage (ses 8-voisins), d’une fonction structurante (valeur 0 au centre, 2 pour les 4-voisins et 3 pour les 8-voisins diagonaux). Régions noyaux de hauteur h : Ce sont des composantes connexes formées de pixels d’altitude h, dont tous les pixels de contour extérieur ont une altitude strictement supérieure à h. Coût d’agrégation d’un pixel à un bassin : Il est évalué sur le chemin que le bassin a parcouru depuis sa région noyau jusqu’à ce pixel. Ce coût est basé sur le calcul de l’altitude maximale du chemin (la dénivelée) et de la distance parcourue depuis le maximum a été atteint.La propagation des bassins, comme en classification, est effectuée par des adhérences prétopologiques successives. Tout pixel x (classé ou non classé) voisin d’un bassin B peut y être agrégé. Il changera de bassin si un nouveau bassin lui propose un coût d’agrégation plus faible. L’application directe de l’algorithme sur une image donne un résultat sursegmenté, donc non interprétable. Pour surmonter cette difficulté l’auteur propose de fusionner les bassins qui vérifient un certain critère qui est fonction du voisinage, de l’altitude et du maximum de la fonction coût. 

Extraction de l’écriture du fond des chèques

 Les auteurs proposent d’extraire les lignes d’écriture des chèques, par une approche itérative basée sur un formalisme prétopologique de croissance de régions qui inclue un critère d’homogénéité évaluée à partir d’une mesure de filiformité. Les lignes d’écriture sont définies comme des parties fermées de l’image. La fonction adhérence est définie à partir de la mesure de filiformité ainsi que du niveau de gris de l’image. L’indice de filiformité µ(x) est calculé sur toutes les directions D. µ(x) = Max{Min(η(s1), η(s2)) – η(x)} où η (si) = Max {η(p), p ∈ si}. L’adhérence d’un point x est donnée par les 8-voisins de x qui vérifient un certain critère ψ calculé à partir de l’indice de filiformité µ. L’algorithme initie un germe comme le point de l’image susceptible de faire partie d’une ligne d’écriture. L’agrégation à partir de ce germe aboutit à une partie fermée de l’image composée par une ligne d’écriture. Algorithme – Initialiser CE, le complémentaire de E, à toute l’image. – Boucle : Tant que CE n’est pas vide, faire: { 1-Choix d’un germe initial : Prendre de CE, le point de l’image qui présente la valeur maximum de ψ . Si cette valeur est inférieure au seuil S, aller à Fin. Sinon: Initialiser une nouvelle classe d’équivalence CG avec ce germe. 2- Agrégation : Tant que le cardinal de CG change, faire: { – Considérer les points de CE qui ont pour voisin un des points de CG. – Définir les candidats comme ceux qui vérifient ψ > S. – Prendre ceux qui vérifient le critère d’homogénéité et les intégrer à CG – Redéfinir le complémentaire CE, en lui soustrayant la classe CG } } – Fin : Afficher toutes les classes d’équivalence.