5. Mise en correspondance

 

La mise en correspondance de deux images stéréoscopique se divise en deux étapes principales:

1) l'extraction de points homologues appelés amers qui servent à initialiser le processus de mise en correspondance

2) l'élargissement de la correspondance à l'ensemble des deux images appelée fusion des images dans la suite de ce chapitre.

La détermination des points amers se fait en trois phases:

1) Mise en correspondance des contours suivant des critères de forme. Cette phase détermine un sous ensemble de contours homologues potentiels et définit une correspondance point à point entre ceux-ci.

2) Application de contraintes géométriques sur les couples de contours en s'appuyant sur les correspondances de points définies lors de la phase 1. Cette phase permet d'éliminer les appariements aberrants et de limiter le combinatoire de l'étape suivante.

3) Choix du meilleur sous ensemble de couples de contours et extraction sur ces contours des points amers les plus fiables. Cette phase élargit la contrainte géométrique à plusieurs contours et prend en compte leurs positions relatives sur les deux images.

 

La fusion des deux images se fait en deux phases:

1) Recalcul d'une image par rapport à l'autre afin de superposer les droites épipolaires homologues. Cette phase utilise la géométrie épipolaire décrite dans le chapitre 3 et corrige l'image homologue par rapport à l'image de référence afin de faciliter le traitement de la phase suivante.

2) Mise en correspondance des droites épipolaires homologues pour obtenir la correspondance point à point entre les deux images homologues. Cette phase fait appel aux techniques de programmation dynamique entre droites épipolaire, en utilisant comme critère de similarité la luminance des points homologues qui est supposée identique.

Dans la suite de ce chapitre, nous présentons les cinq phases successives qui mènent à la mise en correspondance des images.

5.1 Appariement de contours

Les contours extraits de l'étape présentée dans le chapitre précédent ont été codés sur l'alphabet de Freeman. Cette représentation permet d'élaborer un critère de ressemblance entre contours, basé sur les directions successives des arcs formant le contour.

Cette phase a pour but de "proposer" des appariements suivant un critère de forme basé sur la direction des arcs successifs qui forment un contour. La direction d'un arc est calculée relativement à celle d'un arc précédent pour s'affranchir du problème de rotation d'une image par rapport à l'autre. Nous avons présenté cette technique en lors de la définition de l'alphabet de Freeman.

La figure suivante présente un exemple d'appariement rejeté du fait d'une trop grande disparité de forme et un exemple d'appariement potentiel du fait de la ressemblance des deux contours.

 

 

 

Figure 5.1: Appariement suivant le critère de forme

 

Pour simplifier le problème de mise en correspondance des contours, nous considérons plusieurs hypothèse :

1) Les contours sont ouverts, ce qui permet de définir leur début et leur fin et de conserver une relation d'ordre entre les points homologues des deux contours.

2) Chaque contour extrait est orienté. Le gradient représentant une variation d'intensité lumineuse, la luminance est plus forte d'un côté du contour que de l'autre. Le début et la fin des contours doivent se correspondre pour que les contours soient codés dans le même sens.

3) La taille de l'objet observé est similaire sur les deux images homologues.

Nous proposons de prendre comme critère de ressemblance la différence de direction entre les arcs homologues des contours. La minimisation de la somme des différence nous donne la correspondance entre les points des contours homologues. Elle peut être évaluée par des algorithmes de recherche de chemin de coût minimum dans un graphe valué dont les noeuds sont les correspondances entre points des deux contours, et les arcs les différences de direction des arcs entre points successifs des deux contours. Ainsi, une suite d'orientations relatives semblable pour les deux contours détermine une zone de valeurs nulles dans la matrice.

Il est donc possible de mettre en correspondance les phrases représentant les contours par des méthodes de comparaison dynamiques de chaînes. Ces méthodes sont basées sur le principe de distance d'édition entre chaînes qui permet d'obtenir une fonction de ressemblance entre contours. Les techniques de programmation dynamique sont présentées dans l'ouvrage de Miclet [MICL84], notamment l'algorithme de Wagner et Fisher que nous décrirons dans la première section de ce chapitre.

5.1.1 Distance d'édition entre contours

 

a) Principe de la distance d'édition

On définit trois opérations élémentaires possibles dont les combinaisons permettent de transformer une chaîne en une autre:

La substitution: a -> b coût: k(a,b)

L'insertion : 0 -> a coût: k(0,a)

La destruction : a -> 0 coût: k(a,0)

La phrase x=ab est transformée en y=bac par les opérations élémentaires:

(0 -> c), (b -> 0), (c -> b), (0 -> c).

Un méthode de transformation peut être la suite de phrases:

ab, cab, ca, ba, bac.

Le coût total de cette transformation est:

k(0,c) + k(b,0) + k(c,b) + k(0,c).

La distance d'édition d(x,y) (ou distance de Levenstein) entre les deux phrases est le coût de la suite de transformations élémentaires la moins coûteuse pour transformer x en y.

 

b) Adaptation au codage des contours

Si l'on considère les contours codés sous forme de chaînes de Freeman, nous pouvons calculer une distance d'édition entre les contours. Les coûts sont définis comme suit:

1) La substitution aura comme coût l'écart de direction entre arcs. Soit pour les direction u et v appartenant à {0,..,7}:

     k[u,v] = abs(u - v);
     Si abs(u - v)>4 ALORS {k[u,v] = 8 - abs(u - v);}

Formule du coût pour le calcul de la distance d'édition

2) L'insertion et la destruction auront pour valeur la différence de direction entre l'élément courant et l'élément inséré ou détruit, suivant la même formule que la substitution.

Les chaînes étant orientées, l'algorithme revient à chercher de la même façon un chemin de coût minimum dans un graphe d'état représenté par une matrice dont l'élément courant d(i,j) représente la distance optimale entre

x(i) = a1 ... ai et y(j) = b1 ... bj.

c) Algorithme de Wagner et Fisher

L'algorithme de Wagner et Fisher calcule la distance d(x,y) dans une matrice [m,n]. Il se présente comme suit:

1) D(0,0) = 0 
2) Pour i := 1 à n
    Faire D(i,0) := D(i-1,0) + k(ai,0)
3) Pour j := 1 à m
    Faire D(0,j) := D(0,j-1) + k(0,bj)
4) Pour i := 1 à n
    Pour j := 1 à m
    Faire m1 := D(i-1,j-1) + k(ai,bj)
    m2 := D(i-1,j) + k(ai,0)
    m3 := D(i,j-1) + k(0,bj)
    D(i,j) = MIN (m1, m2, m3)
5) Distance d'édition d(x,y) = D(n,m)

Les phases 1,2,3 correspondent à l'initialisation de la première ligne et première colonne de la matrice.

La phase 4 correspond au remplissage de la matrice suivant les coûts définis.

La phase 5 correspond au calcul du coût aux valeurs x et y.

La complexité de cet algorithme est en O(n m).

d) Programmation

La mise en oeuvre de l'algorithme présenté dans le paragraphe précédent est légèrement plus complexe pour obtenir des informations supplémentaires nécessaires au choix des meilleurs contours homologues à un contour donné.

La structure de donnée est une matrice dont chaque élément comprend quatre informations:

- Le coût local calculé comme décrit dans le premier paragraphe de ce chapitre.

- Le poids courant du chemin de mise en correspondance.

- Le nombre de sommets courants, c'est à dire la longueur courante du chemin de correspondance.

- Le nombre courant de diagonales dans le chemin, c'est à dire les zones de correspondance point à point entre les contours.

L'algorithme se déroule en cinq temps:

1) Initialisation de la matrice des poids locaux

2) Initialisation de la première ligne et la dernière colonne:
poids_courant:=0; nb_sommets:=1; nb_diago:=0;
(étapes 1, 2 et 3 de l'algorithme décrit)

3) Calcul des matrices poids_courant, nb_sommets et nb_diago.
En comparant les poids locaux des cases voisines en haut, en haut à droite, et à droite de la case courante, on choisit le poids courant le plus faible (en privilégiant la diagonale en cas d'égalité).
Lorsque le voisin PRED est choisi, les valeur courantes deviennent:
. Nb_sommet := PRED.nb_sommets + 1,
. Poids_courant := PRED.poids_courant + poids_local,
. SI la diagonale a été choisie ALORS Nb_diago:=PRED.nb_diago+1

4) Recherche du départ du meilleur chemin dans la matrice, c'est à dire la case de poids minimum, et de nombre de diagonales maximum. Cette recherche s'effectue sur la première colonne et la dernière ligne de la matrice.

5) Remontée du chemin jusqu'à la dernière colonne ou la première ligne de la matrice. Codage de la correspondance entre les contours. La figure suivante présente le chemin de correspondance entre les contours gauche et droit. La suite des directions du contour gauche forme les ordonnées, et les directions du contour droit les abscisses. Le chemin permet de définir la correspondance entre les deux contours en mettant en relation l'abscisse (point gauche) et l'ordonnée (point droit) du point du chemin de correspondance. Ce chemin est lui aussi codé dans l'alphabet de Freeman (0, 1, 2). Une valeur 0 signifie qu'un point gauche a deux points correspondants à droite et une valeur 2 met un point droit en relation avec deux points à gauche. Les diagonales du chemin de correspondance codées avec la valeur 1 correspondent à une correspondance unique entre les points gauches et droits. Les suite de valeurs 1 dans la codage du chemin sont des zones de bonne correspondance entre les contours.

Fig.5.2: Chemin de correspondance entre les contours

Cette technique nous donne un bon critère de ressemblance de formes entre deux contours par le coût du chemin formé de la somme des différences d'orientations des arcs homologues des deux contours, et le rapport entre le nombre de diagonales du chemin et sa longueur totale.

e) Optimisation de la méthode

Dans le principe présenté au paragraphe précédent, la recherche du meilleur chemin se fait entre tous les points des contours. Cette méthode est très gourmande en place mémoire et temps de calcul. Si on ne compare que des contours de taille proche, il est alors possible d'optimiser la méthode en ne calculant les chemins que dans une bande de la matrice si l'on considère que l'écart entre les indices des points homologues des deux contours ne peut dépasser la différence de longueur entre les deux contours. Il faut alors gérer en plus d'une matrice contenant l'ensemble des zones de recherche, un vecteur de décalage de chaque ligne par rapport à la précédente.

La figure suivante présente la zone de recherche du meilleur chemin dans la matrice.

Fig.5.3: Limitation de la zone de calcul dans la matrice de correspondance

Côté du carré de départ:

h = (% de différence maxi) * (min de longueur des deux contours)

Largeur de la bande:

B = ( h * ( X + Y - 2h ) ) / ( Y - h )

Décalage entre deux lignes consécutives:

d = ( X - B ) / ( Y - 2h )

Borne supérieure des décalages à partir de laquelle le décalage est maximum:

S = ( Y - h )

 

Les figures suivantes présentent les meilleurs chemins de correspondance entre contours. La première calcule la correspondance d'un point sur toute la longueur du contour homologue, et la deuxième limite la recherche dans une fenêtre limitée à un certain pourcentage de longueur. Les niveaux de gris correspondent à la disparité d'orientation des contours. Plus un point de la matrice de correspondance est sombre, plus l'orientation locale des contours est semblable, et donc meilleure est la correspondance locale. Le chemin de correspondance entre les arcs des contours est présenté en blanc et se déplace du haut à gauche vers le bas à droite de la figure. Nous observons que le chemin calculé est le même dans les deux cas, avec un gain en temps de calcul d'un facteur 3 pour la deuxième méthode puisqu'il n'est réalisé que sur une partie de la matrice.

 

Fig.5.3: Chemin de correspondance entre contours (méthode globale)

 

Fig.5.4: Chemin de correspondance entre contours (fenêtre de recherche)

 

 

5.1.2 Algorithme de mise en correspondance

L'algorithme présenté dans le paragraphe précédent donne la distance d'édition entre deux contours quelconques. Il fournit le coût, la longueur du chemin de correspondance et le nombre de diagonales dans ce chemin. Le chemin est codé dans l'alphabet de Freeman, et comprend des valeurs 0, 1 ou 2.

La recherche des contours homologues est effectuée entre des contours de longueur comparable pour éviter des calculs importants dûs à une explosion combinatoire, mais aussi pour optimiser la recherche du meilleur chemin de correspondance, comme présenté dans le paragraphe précédent.

Les tests ont porté sur des contours ne différant pas de plus de 5 à 20 pour-cent de longueur entre eux.

Si l'on recherche les contours homologues entre deux ensembles E1 et E2 comprenant respectivement N1 et N2 contours, le principe de l'algorithme est le suivant:

- Calcul de la distance d'édition entre les contours de longueurs comparables (cf paragraphe précédent).

- Mise en mémoire dans une matrice N1 * N2 (contours gauches * droits). La matrice obtenue est une matrice creuse qui mémorise les résultats des calculs précédent, ci-dessous, un exemple est présenté avec les valeurs des distances d'édition calculés. Les case vides correspondent aux appariements non calculés du fait d'une trop grande disparité de longueur entre contours.

- Recherche des coûts ligne minima qui soient en même temps minima colonne. Ceci revient à chercher les contours de l'ensemble E1 et E2 qui soient respectivement les meilleurs appariement l'un pour l'autre dans chacun des ensembles.

 

    1  2  3  4  5  6  7  8  9

1

2

3

4

5

6

7

  .  .  .  . 12 23 10  .  .

  . 34  . 23  6 12  3  .  .

  4  .  . 10  .  .  .  .  .

  .  .  .  .  .  .  .  .  .

  5  . 10  .  .  .  .  . 23

 89  . 67  .  .  .  . 45  .

  . 45  .  .  .  .  .  .  .


Matrice des distances d'édition

taille N1 * N2

Dans l'exemple présenté ci-dessus, les contours retenus seront:

Numéro ligne 2 3 6

Numéro colonne 7 1 8

Coût 3 4 45

 

 

Il est possible d'optimiser la méthode présentée dans le paragraphe précédent et d'éviter l'utilisation d'une matrice pour mémoriser les résultats. L'algorithme présenté ci-dessous a le même effet mais utilise moins de place mémoire et est plus rapide.

Fig.5.6: Structure des données pour la mise en correspondance des contours

 

Algorithme optimisé:

1) Tri des contours gauches et droits par ordre croissant de longueur et mémorisation sous forme de chaînes de Freeman dans deux tableaux de données. Un troisième tableau, indicé comme l'ensemble des contours gauches, mémorise le chemin de correspondance entre le contour gauche et son meilleur homologue à droite, ainsi que le poids du chemin et le nombre de diagonales du chemin.

2) Calcul de la distance d'édition des contours de longueur proche. On calcule une correspondance de chaque contour gauche avec tous les contours droits répondant au critère:lg_droit-(lg_gauche * C%) < lg_gauche < lg_droit+(lg_gauche * C%).
Avec : lg_gauche, lg_droit:longueur des contours gauche et droit, et C% : pourcentage de tolérance de longueur entre les contours.

3) Mémorisation des couples de contours qui ont réciproquement pour meilleur correspondant l'autre contour. Le critère de ressemblance se fait sur le poids du chemin de correspondance et le nombre de diagonales du chemin. Pour les deux contours, si la correspondance est meilleure que celle calculée précédemment avec un autre, on déchaîne les deux contours précédemment liés. Si la correspondance est meilleure pour les deux contours gauche et droit, ou qu'ils n'étaient liés à aucun autre contour, on chaîne les contours gauche et droit par le troisième tableau présenté dans la figure précédente.

4) A la fin du traitement, seul les contours respectivement les plus proche au sens de la distance de Levenstein sont chaînés entre eux. On obtient ainsi une première sélection des appariements entre contours.

 

5.2 Contrainte géométrique de forme

Dans la section précédente nous avons présenté une méthode de mise en correspondance de contours basée sur un critère de forme. Cette technique représente la première phase de l'appariement des contours. Les résultats à ce stade du traitement montrent une majorité de bons appariement, mais aussi quelques erreurs de mise en correspondance. La deuxième phase de l'appariement des contours des deux images consiste à faire intervenir la contrainte géométrique liée au modèle des images stéréoscopiques. Le modèle géométrique des images stéréoscopiques a été présenté dans le chapitre 3 de ce rapport.

Ce traitement s'applique aux couples de contours appariés dans la première phase de la mise en correspondance. Pour chaque couple de contours nous disposons d'un ensemble de points appariés qui sont définis par le chemin coût minimum évalué dans l'algorithme de Wagner et Fisher.

Nous choisissons un sous ensemble de 8 couples de points et nous appliquons la méthode décrite dans le chapitre 3 sur l'ensemble des points du contour homologue. L'épipôle obtenu est peu significatif car très instable, cependant d'une part l'autocontrôle sur les variables liées nous donne une idée de la validité de la relation, d'autre part la somme des distances entre chaque point et son homologue transformé par l'homographie calculée, que l'on peut assimiler à la surface de disparité des deux contours donne un critère intéressant de similarité.

Propriétés:

Si les contours sont plans dans l'espace et les appariement point à point correctement effectués dans la phase précédente, alors après projection sur un même plan de l'espace par rapport à leur centre optique respectif, ils coincident exactement.

S'ils ne sont pas plans, alors la disparité de leur projection est liée à un écart par rapport à un plan de l'espace.

Ces propriétés découlent de la géométrie décrite dans le chapitre 3. Nous réalisons le calcul en trois étapes:

1) sur les deux contours appariés, trois couples de points homologues sont utilisés comme base projective (le point unitaire est le barycentre de ces trois points). Les trois points sur chaque contour ne doivent pas être alignés. Ils sont choisis dans des zones de variation d'orientation sur les contours pour la précision de position, et doivent former les triangles de surface maximale pour la stabilité des calculs (maximisation du rapport distance_entre_points / erreur_de_discrétisation).

2) les coordonnées des points des deux contours sont transformées en coordonnées projectives par rapport à leur référentiel respectif.

3) l'homographie qui permet d'aligner les points homologues avec les points du premier contour est calculée suivant la méthode décrite dans le chapitre 3. Nous obtenons deux informations qui constituent le critère de similarité : l'erreur sur l'autocontrôle des coefficients de l'homographie et la somme des distances entre couples de points recalculés.

Le critère de validité des appariements entre deux contours est formé par:

a) l'erreur sur les coefficients: cette valeur est obtenue en calculant les incohérences entre les valeurs calculées en résolvant le système linéaire à six variables liées dont on tire les coefficients a et b de l'homographie. Cette valeur erreur_coef est donc utilisée pour éliminer les appariements "suspects". Les appariement donnant des erreurs supérieures à un seuil fixé sont considérés comme faux.

b) la somme des distances entre chaque point du contour de référence et son point homologue recalculé. Cette distance est mémorisée pour chaque appariement, puis triée par ordre croissant pour préparer l'étape suivante.

Dans cette étape, nous avons calculé les erreurs liées à la géométrie des images sur les appariements de contours issus de la première étape du filtrage, nous ne gardons que les appariements dont les erreurs sur les coefficients sont inférieurs à un seuil.

Pour les couples de contours satisfaisant à l'autocontrôle sur les coefficients, nous trions leur surface de disparité par ordre croissant. On peut être ainsi assuré que les distances minimales correspondent à des contours relativement plans dans l'espace pour lesquels l'appariement point à point a été correctement réalisé lors de la phase 1.

La figure suivante présente un exemple d'appariement rejeté et d'un appariement considéré comme exact.

Figure 5.7 Appariement par contrainte géométrique locale

 

5.3 Cohérence géométrique de position

L'étape précédente nous fournit un ensemble de contours appariés après application du critère géométrique localement. Dans cette phase, nous nous intéressons au sous ensemble de contours qui respectent au mieux la contrainte épipolaire et qui minimise la distance entre tous les points pour l'ensemble de couples de contours. La figure suivante présente un ensemble d'appariement de couples de contours homologues considérés comme faux et un ensemble considéré comme vrai.

Figure 5.8 Appariement par contrainte géométrique globale

 

Cette méthode fonctionne comme celle du paragraphe précédent. La différence réside dans le choix des points de la base projective sur trois contours différents. Le calcul de la distance entre points homologues après application de l'homographie sur l'image homologue nous donne un critère de similarité basé sur la position des contours dans les deux images.

Nous recherchons le meilleur ensemble de contours appariés au sens de ce critère en calculant de façon combinatoire les surfaces de disparité entre des sous ensembles de couples potentiels dans l'ensemble issu de la phase précédente. Le sous ensemble est limité à cinq couples de contours, ce qui est suffisant pour garantir une dispersion des points dans les images. La base projective s'appuie sur les trois points du sous ensemble formant le triangle de surface maximale sur l'image de référence.

Pour éviter une explosion combinatoire, nous limitons le nombre de couples considérés. Dans nos expérimentations, nous ne considérons que les huit appariements de distances minimales et nous recalculons l'homographie engendrée par leurs appariements cinq par cinq. Le meilleur résultat constitue l'ensemble résiduel de points qui seront utilisés dans les phases suivantes. Cette méthode est un bon compromis, car elle évite un excès de combinatoire et fournit un ensemble résiduel de points suffisant pour obtenir une bonne approximation d'une relation entre les deux images qui permettra le recalcul présenté dans le chapitre suivant.

A la fin de cette phase de la mise en correspondance, nous disposons d'un ensemble de points amers sur les deux images et de l'homographie calculée suivant la méthode du chapitre 3, ainsi qu'une base projective qui utilise les points amers les plus dispersés sur l'image de référence.

5.4 Algorithme d'extraction d'amers

Ce paragraphe résume les différentes étapes de l'algorithme. Dans notre description des critères de sélection nous emploierons le terme de distance, bien que les critères définis pour les contraintes épipolaires n'aient pas ses propriétés, car par exemple d(a,b)<>d(b,a). Cet abus de langage permet d'exprimer les contraintes sous une forme parlante souvent utilisée par les auteurs. L'orientation de la distance entre les contours des images met en relief le fait que notre méthode se base sur une image qui servira de référence. La deuxième image du couple stéréo sera calculée par rapport à celle-ci.

 

Les trois critères de sélection sont dans leur ordre d'apparition:

- Distance de Levenstein d1(Ca,Cb) entre les contours des images A et B de longueur semblable. Cette distance est un indice de ressemblance des formes de contours deux à deux.

- Distance épipolaire locale d2(Ca,Cb) entre les contours potentiellement homologues pris deux à deux. Cette distance est intéressante car si on suppose que chaque contours est relativement plan, le recalcul du contour Cb de l'image B se superposera avec son homologue Ca sur l'image A.

- Distance épipolaire globale d3(Cai,Cbj) entre cinq couples de contours homologues. Le meilleur sous-ensemble de cinq couple est conservé parmi ceux issus de l'étape précédente. Cette étape nous donne une homographie entre les deux images basée sur un plan moyen passant par les contours sélectionnés.

 

Au niveau calculatoire, il est intéressant d'évaluer le combinatoire et les techniques choisis pour le limiter. Les images de microscopie testées ont environ 40 contours.

- La distance d1 est calculée sur 40x40=1600 couples potentiels. On limite le combinatoire sur un critère de similarité de longueur entre contours testés. A la fin de cette étape on obtient 15 couples de contours potentiellement homologues.

- La distance d2 s'applique sur ce sous ensemble. L'élimination des couples se fait sur le critère des erreurs de coefficients lors du calcul de l'homographie entre contours. Après cette étape on dispose de 10 couples fortement potentiels, triés suivant leur distance d2.

- La distance d3 est calculée sur les huit couples de distance minimale de l'ensemble précédent. Les cinq couples les plus homogènes forment le résultat final.

5.5 Résultats

Nous avons testé cette méthode sur les types d'images utilisées pour l'extraction de contours.

Les résultats sont en général satisfaisants comme le montrent les images présentées ci-dessous. Des problèmes surgissent sur des images comportant peu de contours ou sur des contours mités, peut être du fait de la non optimisation des critères d'extraction de contours.

Pour les contours fermés, notre méthode ne convient pas car nous ne pouvons définir le début des contours à mettre en correspondance dans l'étape 1. Cependant, le choix du début des contours fermés au maximum de courbure permet de résoudre partiellement ce problème dans le cas de contours fermés.

La méthode ne s'applique pas bien aux contours rectilignes car le critère de similarité est surtout performant dans les changements de direction.

Pour les images à contours répétitifs, comme par exemple les images de cristaux en microscopie électronique, la contrainte épipolaire globale est un puissant critère qui permet d'extraire des ensembles homogènes d'appariements.

L'application de notre méthode n'a pas donné de résultat pour les images dont les contours sont peu nombreux, rectilignes ou fermés. Par contre, sur les images de photographie aérienne ou de microscopie électronique, l'extraction a donné de très bons résultats, même dans le cas d'images à contours répétitifs.

Un approfondissement de notre technique permettra sans doute d'améliorer encore la fiabilité de l'appariement entre contours.

 

Contours et amers de l'image de référence

 

Contours et amers de l'image homologue

Fig.5.8: Images de calcite de M.E.B.

 

 

Contours et amers de l'image de référence

Contours et amers de l'image homologue

Fig.5.9: Images de photographie aérienne (Belle Ile)

 

5.6 Recalcul d'images

5.6.1 Principe

Le principe du recalcul d'images consiste à choisir une image de référence et à corriger l'image homologue par rapport à celle-ci suivant la méthode présentée dans le chapitre 3. Elle consiste en une première projection sur un plan P de l'espace par le centre optique homologue, puis une deuxième projection vers l'image de référence par le centre optique de celle ci. Le plan de l'espace correspond à celui qui passe par les trois points définis sur chaque image comme base projective, le point unitaire étant choisi arbitrairement.

Cette technique ressemble aux procédés optiques de redressement utilisés en photogrammétrie au moyen de chambres claires.

L'image de référence n'est pas modifiée. On calcule l'antécédent de chaque point de l'image de référence par l'homographie inverse. Cette méthode permet d'obtenir l'image homologue recalculée sur l'image de référence. Il est important de rappeler que ce recalcul ne nécessite aucune calibration des systèmes de prise de vue. Il est uniquement basé sur les homologies de points extraites lors de l'étape de mise en correspondance de contours.

Les propriétés de la superposition de l'image de référence et de l'image homologue recalculée sont:

- la superposition des couples de points homologues appartenant au plan P de l'espace, ainsi qu'une relation entre la distance du point au plan P dans l'espace et l'écart entre ses deux images. Cette relation est linéaire dans le cas de la projection parallèle, où les centres optiques sont rejetés à l'infini.

- l'alignement de tous les couples de points homologues avec un point appelé épipôle.

 

5.6.2 Intérêt de cette représentation

Les intérêts de cette méthode sont triples:

- Contrôle visuel de la validité de la relation entre les images. En effet, l'observation visuelle de la superposition d'images recalculées permet d'évaluer la qualité de la superposition et même de déduire une idée de relief, soit de façon subjective, soit en tirant parti de l'information qualitative liée à la position d'un point par rapport à un plan de référence. En effet, il est possible de contrôler que des point perçus comme homologues sont alignés avec l'épipôle de l'image de référence et d'évaluer le relief par la distance entre deux images d'un même point après recalcul de l'image homologue.

- Mise à l'échelle de l'image homologue par rapport à l'image de référence. L'image recalculée est superposée à l'image de référence, l'écart entre les images homologues est lié à la position du point dans l'espace. Cet écart est relativement limité et homogène sur toute l'image, ce qui améliore la qualité de la mise en correspondance point à point ou fusion des deux images présentée dans le chapitre suivant.

- Préparation à la fusion des images stéréo sans passer par la calibration du système de prise de vue. La contrainte épipolaire fait que les points de l'image de référence et leurs homologues recalculés par homographie sont alignés avec l'épipôle de l'image de référence. C'est une contrainte fondamentale qui permet de diminuer de façon significative le calcul nécessaire à la fusion d'images. En effet, l'homologue d'un point de l'image de référence est sur la droite passant par lui même et l'épipôle. Donc la recherche se fait de façon monodimensionnelle et beaucoup plus facilement que dans l'espace bidimensionnel.

Il est important de noter que le recalcul de l'image, c'est à dire l'homographie calculée est fonction des points de référence utilisés comme base des coordonnées projectives.

 

5.6.3 Expérimentation

 

a) Modalités de l'expérimentation

 

Dans ce chapitre, nous observons les résultats sur quatre types d'images réelles.

- Objet plan: affiche verset

- Objet à faible relief: clavier d'ordinateur

- Objet fortement grossi au microscope électronique: calcite

- Objet tri-dimensionnel : pyramide

Pour chaque expérience, nous présentons :

1) les images d'origine gauche et droite

2) l'image droite corrigée par homographie et sa superposition avec l'image gauche d'origine

3) l'influence du choix des points de base des coordonnées projectives (A1, A2, A3) sur la position du centre du faisceau de droites calculé.

Nous avons choisi six combinaisons de points comme dans le paragraphe 3.5, soit:

. Quatre manuellement en prenant successivement les points (1,2,3), (2,3,4), (3,4,5) et (4,5,6) de la liste des points homologues.

.une combinaison en prenant

A1: M(x,y), M'(x,y) tel que Mx minimum

A2 Mx maximum

A3 My minimum

.une combinaison en prenant les points A1, A2, A3 formant le triangle de surface maximale.

4) l'influence du bruit, c'est à dire l'erreur sur l'acquisition des points homologues.

.Sur les points secondaires autres que les points A1, A2 et A3.

. Sur les points de base A1, A2 et A3 des coordonnées homogènes.

Nous avons introduit dans les coordonnées des points sur les images un bruit blanc dont le maximum varie 1 à 20 pixels et calculé pour chaque fenêtre de variation les coefficients a et b de l'homographie (c étant fixé à 1) 100 fois. Les graphiques montrent pour chaque fenêtre d'erreur la moyenne, l'écart type et l'écart maximum à la moyenne des coefficients a et b de l'homographie.

 

b) Image optique d'objet plan (Verset)

 

Image gauche d'origine (référence)

 

 

Image droite d'origine

 

 

Image droite corrigée par rapport à l'image de référence

 

 

Superposition de l'image gauche et de la droite corrigée

Points 1 2 3

Points 2 3 4

Points 3 4 5

Points 4 5 6

Points MIN/MAX X Y

Points surface max

 

Influence du choix des points de base

 

 


Influence des erreurs

 

c) Image optique d'objet tridimensionnel (clavier)

 

Image gauche d'origine (référence)

 

Image droite d'origine

 

 

Image droite corrigée par rapport à l'image de référence

 

 

Superposition de l'image gauche et de la droite corrigée

 

Points 1 2 3

Points 2 3 4

Points 3 4 5

Points 4 5 6

Points MIN/MAX X Y

Points surface max


Influence du choix des points de base

 

 

 

 

Influence des erreurs

 

 

d) Image de microscopie électronique (calcite)

 

Image gauche d'origine (référence)

 

Image droite d'origine

 

 

Image droite corrigée par rapport à l'image de référence

 

 

Superposition de l'image gauche et de la droite corrigée

 

 

Points 1 2 3

Points 2 3 4

Points 3 4 5

Points 4 5 6

Points MIN/MAX X Y

Points surface max


Influence du choix des points de base

 

 

 

Influence des erreurs

 

 

e) Image optique 3D (pyramide)

 

Image gauche d'origine (référence)

 

Image droite d'origine

 

 

Image droite corrigée par rapport à l'image de référence

 

 

Superposition de l'image gauche et de la droite corrigée

 

Image gauche de référence

Image droite corrigée

Superposition des 2 images

Exemple de quatre recalculs d'images optiques (pyramide)

 

 

Points 1 2 3

Points 2 3 4

Points 3 4 5

Points 4 5 6

Points MIN/MAX X Y

Points surface max


Influence du choix des points de base

 

 

 

 

Influence des erreurs

 

5.6.4 Interprétation des résultats

La visualisation des images nous amènent à plusieurs remarques.

- Les épipôles obtenus sur les images réelles sont très instables, contrairement à ceux calculés sur les ensembles de points générés artificiellement en projection centrale. Cette instabilité est dues aux imprécisions de positionnement des points homologues, aux déformations du plan image et à la discrétisation de l'image numérique. Les épipôles calculés sur des images de faible relief sont sans signification, du fait que les droites sont définies par des couples de points très proches. A la limite, pour l'image d'un objet plan, les points étant confondus, le calcul d'un épipôle revêt un caractère complètement aléatoire.

- Les recalculs d'images sont assez stables ainsi que les paramètres de l'homographie entre les plans images pour des points de référence donnés. Ils sont même assez résistant au bruit, ce qui est un indice de fiabilité de la méthode.

Cette méthode présente donc une application dans la mise en correspondance point à point (fusion) d'images stéréoscopiques puisqu'elle constitue un premier traitement qui rapproche les caractéristiques des images pour favoriser une correspondance plus fine que nous étudions ci-dessous.

5.7 Fusion d'images

La fusion d'images stéréoscopiques consiste à mettre deux images homologues en relation point à point, c'est à dire, si l'on prend une image comme référence, de rechercher pour chaque point de cette image, son correspondant sur l'image homologue. Il faut tenir compte du fait que tous les points de l'image de référence n'ont pas forcément, un correspondant, soit parce que le point correspondant est en dehors de l'image homologue (problème de recouvrement de zone observée), soit parce que ce point est caché par un objet plus proche lors de l'observation d'un point de vue différent (problème d'occlusion).

Le problème de mise en correspondance entre deux images est au départ bidimensionnel, ce qui pour une image de taille 512 x 512 représente pour chaque point 512 x 512 possibilités d'appariement. Il est donc impératif de réduire le combinatoire si l'on veut obtenir des algorithmes exploitables. Dans le chapitre 3, nous avons étudié le modèle géométrique des images stéréoscopique, et calculé la relation qui existe entre deux images homologues. La géométrie épipolaire nous offre un puissant outil qui nous permet de réduire considérablement la zone de recherche de l'homologue d'un point de l'image de référence. En effet, la connaissance des droites homologues entre les deux images permet en théorie de ramener le problème bidimensionnel de la mise en correspondance à un problème monodimensionnel. Si l'on considère 512 lignes épipolaire de longueur constante 512, le nombre de possibilités d'appariement pour un point devient alors 512. Si l'on prend en compte la relation d'ordre qui existe en général entre les points des droites homologues, la recherche d'un point homologue se limite à une fenêtre de recherche sur l'autre ligne épipolaire. Pour un fenêtre de 10, le nombre d'appariements possible pour chaque point devient 10 ce qui est plus facilement calculable.

Les algorithmes de fusion d'images stéréoscopique [BENA83] [SHI87] [FORE88] utilisent généralement les propriétés de la géométrie épipolaire ainsi que la relation d'ordre sur deux droites épipolaires homologues comme principes de base. Le critère de corrélation est basé sur la luminance des points et de leur voisinage, ce qui revient à déplacer une fenêtre de corrélation le long des droites épipolaires.

 

Nous avons choisi d'utiliser l'algorithmique de programmation dynamique pour résoudre ce problème, puisque la recherche de points homologues sur deux droites épipolaire peut se traiter par la recherche d'un chemin de coût minimum dan un graphe valué. Les noeuds du graphe sont les couples de points de référence et homologues potentiels, et les arcs valués le critère de similarité. L'algorithme de mise en correspondance est celui de Wagner et Fischer présenté au début de ce chapitre. La contrainte est de prendre les lignes épipolaires homologues dans le même sens, c'est à dire que les points des droites homologues ont la même relation d'ordre avec leur épipôle respectif. Le critère de similarité est basé sur la minimisation des différences de luminance entre points homologues.

La figure suivante présente un exemple de chemin de correspondance entre lignes épipolaires. La recherche se fait dans une fenêtre pour limiter le temps de calcul. Les niveaux de gris de la figure représentent la valeur absolue des disparités de luminance entre points de deux lignes épipolaire homologues. Plus la zone est sombre, plus les luminances sont semblables, et donc plus les points se correspondent s'ils gardent la même luminance entre les deux prises de vue. Le chemin de mise en correspondance est dessiné en blanc dans la matrice.

Fig.5.10: Chemin de correspondance entre deux droites épipolaires homologues

 

Algorithme:

L'algorithme de fusion de deux images stéréoscopique s'applique à une image de référence et son homologue corrigée selon la technique décrite dans le paragraphe précédent. Les droites épipolaires homologues sont superposées et l'épipôle dans l'images de référence est connu.

 

Il comprend cinq phases principales:

1) Mise en correspondance des droites épipolaires homologues. Cette phase consiste à extraire les deux droites homologues en faisant tourner un rayon autour de l'épipôle suivant un pas variable afin de balayer l'ensemble des deux images superposées. Les droites sont représentées comme une suite de points caractérisés par leur luminance.

2) Mise en correspondance par programmation dynamique des suites de valeurs issues de la première phase. Cette mise en correspondance se fait en cherchant un chemin de coût minimal du haut à gauche vers le bas à droite dans la matrice présentée dans la figure précédente. Ensuite, on cherche un deuxième chemin du bas à droite vers en haut à gauche dans la même matrice. Le résultat de cette phase est un ensemble de points appartenant à la fois au premier et au deuxième chemin. Cette technique permet de limiter les faux appariements.

3) Pour éviter un mitage trop important de la correspondance et en nous appuyant sur les hypothèses d'ordre des points homologues et de continuité des surfaces observées présentées au chapitre 2, nous réalisons une interpolation entre deux couples appariés. Cette interpolation est limitée à une fenêtre de trois points, c'est à dire que nous appliquons cette technique lorsque deux appariements dans la suite des points formant la droite sont séparés de moins de quatre points. Si nous appelons l'appariement '*', le non appariement '.' et l'interpolation '-', la suite '***...*....*..***...' est transformée en '***---*....*--***...'

4) Les étapes 1), 2) et 3) sont répétées sur l'ensemble de l'image. A la fin de ce traitement, nous avons une correspondance entre l'image de référence et l'image homologue corrigée. nous appliquons une deuxième interpolation sur l'ensemble de l'image dans une fenêtre de trois points, ce qui permet d'élargir la relation entre les deux images. A la fin de cette étape, nous avons une mise en correspondance de 90 à 95% des points selon les images. Cette correspondance est faite entre les points de l'image de référence et l'image homologue.

5) Pour obtenir une correspondance entre les deux images d'origines, il suffit pour chaque point de revenir à l'antécédent du point recalculé de l'image homologue, ce qui revient à appliquer à ses coordonnées, l'homographie inverse calculée au chapitre 3. Cependant, cette phase n'est pas nécessaire pour le calcul du point dans l'espace puisque celui ci s'appuie sur les coordonnées transformées par homographie et exprimées dans le référentiel de l'image de référence.

Les images suivantes montrent des images d'origine gauche et droite de photographie aérienne, puis l'image droite recalculée par rapport à la gauche, et enfin le résultat de la fusion entre l'image gauche de référence et l'image droite recalculée. Cette dernière image de correspondance est formée par les points homologues appariés de l'image droite ramenés aux coordonnées de leur équivalent sur l'image de référence. Les parties de l'image homologue non représentées sur l'image de correspondance correspondent à de zones non appariées.

Pour évaluer la qualité de la fusion des deux images nous superposons l'image de référence en rouge et l'image de correspondance en vert et bleu. Si l'on considère que les points homologues ont la même luminance, les zones de bonne correspondance s'affichent en noir et blanc par l'addition avec la même intensité des couleurs de base.

Nous observons une bonne mise en correspondance en général, sauf dans des zones où la luminance présente des variations importantes entre les deux images du fait de reflets du soleil sur la mer. Ceci est dû au critère de similarité choisi entre les points homologues, puisque l'on considère les points selon leurs caractéristiques de luminance. Des tests réalisés sur le gradient de l'image n'ont pas présenté de meilleurs résultats. Il est envisageable de définir un critère mixte qui prenne en compte les caractéristiques de luminance et gradient de l'image afin d'atténuer les inconvénients d'un critère unique.

Une interpolation plus large peut être réalisée pour remplir des zones non appariées, mais cela risque de nuire à la précision de la mise en correspondance.

L'élargissement de la recherche à une fenêtre de corrélation le long des droites épipolaires améliorera les performances de cette mise en correspondance puisqu'elle palliera l'instabilité des centres épipolaires qui induit des décalages entre droites épipolaires conjuguées.

 

Fig.5.11: Image gauche d'origine (référence)

 

Fig.5.12: Image droite d'origine

 

Fig.5.13: Image droite recalculée par rapport à l'image gauche

 

Fig.5.14: Résultat de la fusion entre l'image gauche et l'image droite recalculée

 

5.8 Conclusion

Dans ce chapitre, nous avons présenté une chaîne de mise en correspondance de couples d'images stéréoscopiques. Cette méthode est divisée en trois étapes principales:

1) Extractions d'amers à partir de mise en correspondance de contours.

2) Calcul de la géométrie épipolaire à partir des amers, et recalcul de l'image homologue pour superposer les droites épipolaires homologues.

3) Fusion des deux images en élargissant correspondance entre les deux images à partir de l'image de référence et de l'image homologue recalculée lors de l'étape 3.

L'application de notre méthode à des images stéréoscopiques réelles donne de bons résultats. Cependant certains types d'images posent des problèmes pour l'extraction des amers, ou bien pour la fusion du couple stéréoscopique.

Nous avons essayé de caractériser les problèmes à résoudre pour chaque étape de la mise en correspondance afin d'orienter notre travail dans l'avenir.

Les améliorations envisagées sont les suivantes:

1) pour l'étape d'extraction d'amers, les difficultés liées aux contours rectilignes peuvent être surmontées par la coopération d'une méthode basée sur le codage par segments [AYAC89], mais en tous cas il faut que les images aient suffisamment de contours pour qu'un appariement soit possible. Si cette étape est irréalisable, il est toujours possible de déterminer les correspondances entre points manuellement, ce qui permet de passer à l'étape suivante de la mise en correspondance. L'impossibilité d'extraction d'amers n'interdit donc pas la fusion d'un couple d'images stéréoscopiques.

2) le calcul des épipôles qui permet le recalcul de l'image homologue par rapport à l'image de référence pose parfois un problème de stabilité, surtout pour les scènes à relief peu marqué. Cette instabilité des épipôles est due aux imprécisions de l'appariement des amers, aux déformations des plans images, et dans une certaine mesure à la discrétisation des images. Il y a donc un travail important à réaliser sur l'étude des déformations des plans images et des algorithmes de corrections d'images. Cet aspect est capital pour une amélioration de la précision du calcul des points dans l'espace, puisque la géométrie calculée à cette étape est fondamentale pour la qualité des résultats.

3) pour la fusion des deux images, les variations radiométriques que nous avons observées sur les couples stéréo nous invitent à élaborer un critère de similarité plus complexe que la luminance, peut être qu'une combinaison de la luminance et du gradient permettrait de lever certaines ambiguïtés. D'autre part, la prise en compte du voisinage soit par la recherche d'une surface de coût minimum dans un espace à quatre dimensions par programmation dynamique, soit par une fenêtre de corrélation, améliorerait sans doute la qualité des résultats, au prix cependant d'un temps de calcul plus important. Nous pouvons sans doute envisager un algorithme de mise en correspondance basé sur des conditions de réaction entre les points des deux images (luminance, gradient, ordre, alignement avec l'épipôle), qui s'inspirerait des méthodes de croissance des régions et de minimisation de fonction d'énergie représentant la somme des disparités des points appariés. En tous cas, les grandes surfaces de zones homogènes restent difficilement fusionables de façon précise.

Suite