Maîtrise d'informatique - Module 11
Vision par ordinateur - Cours

Chapitre 3 :

Nous appelons "stéréovision" la reconnaissance du relief à partir de plusieurs images d'une même scène, vue sous différents angles.

Dans ce cours, nous nous limitons à la stéréovision binoculaire, donc à des paires d'images, formées d'une image "gauche" et d'une image "droite" (remarquer la similarité avec la vision humaine).

La stéréovision, comme nous l'avons déjà mentionné au chapitre 2, s'effectue en trois étapes successives :

calibrage

appariement

triangulation

La phase la plus difficile est la phase 2. C'est aussi celle qui varie le plus d'une méthode à l'autre. Les phases 1 et 3 sont purement géométriques, contrairement à la phase 2 qui utilise les niveaux de gris E_i,j des deux images.

Dans ce chapitre, nous allons simuler, dans un cas particulièrement simple, chacune de ces trois phases.

1. Cas élémentaire de stéréovision.

Ce cas survient lorsqu'on n'utilise qu'une caméra, ce qui impose à la scène d'être statique. L'intérêt de n'utiliser qu'une caméra est que les paramètres de la caméra sont les mêmes entre les images gauche et droite. En d'autres termes, la phase de calibrage est nettement simplifiée.

Dans le cas général, par contre, ces paramètres diffèrent, et doivent être déterminés les uns par rapport aux autres.

1.1. Réalisation pratique.

À partir d'une paire d'images numériques stéréoscopiques, on souhaite connaître Z pour chaque point de la scène.

1.2. Correspondance entre points objets et pixels d'une image.

Si l'image est nette, la correspondance entre les points objets et les pixels des images peut être considérée comme la succession de :

Une homothétie de rapport(éventuellement négatif) et de centre O ;

Une projection sur le plan du récepteur ;

Une discrétisation :

Le récepteur reçoit un éclairement e(x,y) par unité de surface ;

Donc le pixel (i , j) reçoit en tout (unité : lux) :

Le niveau de gris E_i,j du pixel (i , j) est une fonction croissante decaractéristique du récepteur. Si le niveau de gris E_i,j est proportionnel à, on dit que le récepteur est linéaire.

2. Le calibrage : phase 1.

Il va être très simple ici.

2.1. Relation mathématique entre points objets et pixels.

Soit un point objetvisible sur les deux images.

On cherche .

Une remarque évidente est que :

intérêt de cette formule

Si on sait calculer x^g_p, on aura x^d_p en remplaçant - par .

Calcul de x^g_p:

O^gx^g

De la même manière :

Bilan :

2.2. Détermination des paramètres de calibrage.

Calibrer consiste à déterminer les coefficients permettant de calculer I^g et I^dpour tout point objet .

D'après les relations (3.3) et (3.3 bis), il y a dans notre cas deux paramètres à déterminer :et .

2.2.a. Détermination de.

D'après (3.3) et (3.3 bis),est un facteur d'échelle, dont on observe toujours la présence en stéréovision. C'est même le seul paramètre de calibrage qui apparaisse dans tous les cas.

2.2.b. Détermination de .

L'angle ne dépend pas des caractéristiques internes de la caméra. Pour cette raison, on dit que est un paramètre "extrinsèque" de calibrage.

Soit un point objet pour lequel on connaît :

les coordonnées X_p, Y_p et Z_p ;

les points images correspondants I^g et I^d.

On a donc :

Le produit du membre gauche de (3.4) par le membre droit de (3.5) est égal au produit du membre droit de (3.4) par le membre gauche de (3.5), ce qui donne, en divisant à gauche et à droite par -2:

Cette équation se réécrit :

Dans (3.6) ou (3.6 bis), seulest inconnu.

II.2.c. Nombre d'angles solutions de l'équation (3.6)

Remarque :

Siet, alors, d'après la remarque précédente et les équations (3.4) et (3.5), on voit que et . On peut donc, dans ce cas, transformer (3.6) de la manière suivante :

Résolution graphique de (3.7) :

Cette résolution graphique montre qu'il y a deux solutions en : . Mais, comme , il est clair que les deux angles sont égaux modulo, c'est-à-dire qu'il y a une solution unique à (3.7), donnée par exemple par :

Si X_p = 0 et Z_p = 0, les équations (3.4) et (3.5) ne donnent aucune information sur. Un tel point P n'est donc pas utile pour le calcul de .

Si X_p = 0 et, l'équation (3.5) donne :

Siet Z_p = 0, l'équation (3.4) donne :

Ce cas est similaire au précédent.

3. L'appariement : phase 2.

L'appariement ou "mise en correspondance" est la phase du traitement la plus difficile, car elle n'est pas purement géométrique. Cette phase fait appel aux niveaux de gris des deux images, contrairement aux phases 1 et 3, dans lesquelles on n'a jamais à utiliser les niveaux de gris E^g_i,j et E^d_k,l.

Nous allons commencer par comparer les niveaux de gris de deux pixels appariés.

3.1. Comparaison des niveaux de gris de deux pixels appariés.

On dit que deux pixels I^g_i,jet I^d_k,lsont appariés s'ils correspondent au même point physique P de la scène. Pour trouver de telles paires à partir de la donnée de deux images, on ne peut que chercher une similarité entre les niveaux de gris E^g_i,jet E^d_k,l correspondant à ces deux pixels :

En fait, P ne réémet pas la même énergie lumineuse dans toutes les directions, ce qui signifie que E^g_i,jet E^d_k,lne sont pas égaux. On voit aussi que si diminue, les valeurs E^g_i,jet E^d_k,lse rapprochent.

De toutes façons, on aura beaucoup de paires erronées si on se contente d'apparier un pixel I^g_i,javec le pixel I^d_k,lqui a le niveau de gris E^d_k,lle plus proche de E^g_i,j.

Pour cette raison, on va comparer non pas un pixel de l'image gauche avec un pixel de l'image droite, mais un pixel de l'image gauche et son voisinage, avec un pixel de l'image droite et son voisinage. C'est ce qu'on appelle la "corrélation".

3.2. Corrélation entre deux pixels et leurs voisinages.

Un pixel I^g_i,j de l'image gauche et un pixel I^d_k,lde l'image droite sont corrélés si les niveaux de gris ont des valeurs similaires au voisinage de ces deux pixels.

Attention :

La corrélation n'a rien à voir avec la convolution ni avec la covariance.

Exemples :

On souhaite pouvoir mesurer numériquement la corrélation entre deux pixels et leurs voisinages.

3.2.a. Définition du voisinage : fenêtre de corrélation.

On peut chercher la corrélation entre deux pixels et leurs voisinages avec une taille de voisinage plus ou moins importante. On appelle ce voisinage la "fenêtre de corrélation".

On impose :

de prendre la même fenêtre de corrélation sur l'image gauche et l'image droite ;

de prendre une fenêtre de corrélation connexe (en un seul morceau) ;

que la fenêtre de corrélation contienne le pixel qu'on cherche à apparier.

Cas le plus courant : fenêtre carrée centrée sur le pixel à apparier.

Exemples :

3.2.b. Mesure de corrélation euclidienne.

Il existe différentes méthodes pour mesurer numériquement la corrélation. La plus élémentaire est la mesure de corrélation euclidienne. Avec une fenêtre de corrélation 3 x 3, elle s'écrit :

Avec l'exemple précédent :

=> pixels "fortement corrélés".

=> pixels "très faiblement corrélés".

Plus la mesure de corrélation euclidienne entre deux pixels et leurs voisinages est faible, plus ces pixels sont corrélés. Cela nous procure une méthode d'appariement.

3.3. Méthode d'appariement.

Rappel :

y^g_P

= y^d_P

contrainte épipolaire

Exemple :

En fait, on se limite aux pixels pour lesquels la fenêtre de corrélation est entièrement contenue dans l'image. Cela élimine les candidats situés sur les bords.

3.3.a. Appariement d'un pixel de l'image gauche.

Soit I^g_i,j un pixel de l'image gauche tel que la fenêtre de corrélation soit contenue dans l'image gauche. On cherche à apparier I^g_i,j. Les candidats sont les pixels I^d_i,lpour lesquels la fenêtre de corrélation est contenue dans l'image droite. On apparie I^g_i,j avec le pixel I^d_i,l pour lequel la mesure de corrélation euclidienne est minimale.

Remarques :

Il peut y avoir des erreurs d'appariement.

Dans le cas exceptionnel où plusieurs candidats donnent la même mesure de corrélation minimale, on ne se détermine pas, puisqu'on court le risque d'effectuer un appariement erroné.

3.3.b. Appariement d'un pixel de l'image droite.

On a privilégié les pixels de l'image gauche sans raison. On peut donc réaliser la même opération pour les pixels de l'image droite. Si I^g_i,j a été apparié avec le pixel I^d_i,l, il se peut très bien que lors de l'opération inverse, I^d_i,lne soit pas apparié avec I^g_i,j.

Exemple :

Chaque simple flèche noire désigne un appariement unilatéral, c'est-à-dire n'ayant pas débouché sur la formation d'une paire.

Les doubles flèches roses indiquent les paires formées d'un pixel de l'image gauche et d'un pixel de l'image droite, c'est-à-dire les paires apparaissant dans les deux appariements : ces paires vérifient ce qu'on appelle la "contrainte d'unicité".

Dans notre exemple, après application de la contrainte d'unicité, il ne reste plus que 11 paires (sur les 16 possibles).

3.3.c. Conclusion.

Cette méthode d'appariement consiste à mettre en bijection nb pixels de l'image gauche (nb < N x M) avec nb pixels de l'image droite.

Un certain nombre de pixels restent non appariés, en particulier sur les bords. Cela n'est pas un problème, et nous verrons plus loin comment traiter ces pixels non appariés.

Un problème plus important est celui des appariements erronés, que nous allons évoquer dans le paragraphe suivant.

3.4. Appariements erronés.

Avec la méthode que nous venons de voir, il est possible de traiter un couple de deux images quelconques :

=> couples de pixels appariés ????!!!!!

Même si on reste dans le cadre qui est le nôtre :

Il se peut très bien qu'un pixel correspondant à une des zones non visibles sur une des images ait été apparié. Il faut éliminer si possible un tel appariement, puisqu'il est forcément erroné.

Pour ce faire, nous introduisons un seuil S, et considérons que deux niveaux de gris E^g_i,jet E^d_i,lsont "proches" si et seulement si :

(3.9)

avec :

Exemple :

E^g_i,j

= 12

E^d_i,l

E^g_i,j

Comme la similarité entre deux pixels est jugée sur les voisinages de ces deux pixels, on va considérer que deux pixels (I^g_i,j , I^d_i,l) forment une paire acceptable si (avec une fenêtre 3 x 3) :

Il est possible de montrer qu'une condition suffisante pour que cette inégalité soit vérifiée s'écrit :

Les paires de pixels ne vérifiant pas cette égalité sont rejetées car trop suspectes. Ceci revient à imposer une contrainte de seuil.

3.5. Améliorations de la méthode d'appariement.

Les trois contraintes que nous avons citées (épipolaire, d'unicité et de seuil) fournissent un ensemble de paires de pixels (I^g_i,j, I^d_i,l) assez bon en général.

Il subsistera des erreurs dans le cas d'un motif périodique ou presque périodique.

Exemple 1 :

Sur le schéma précédent, le tableau de gauche correspond à la phase d'appariement des pixels de l'image gauche et le tableau de droite correspond à la phase d'appariement des pixels de l'image droite.

En appliquant les contraintes d'unicité et de seuil (avec S = 1), il ne reste que les 11 paires suivantes :

Or, on aurait plutôt tendance à penser que deux pixels formant une paire ont des numéros de colonnes identiques :

Il existe deux améliorations possibles à la méthode d'appariement décrite dans les paragraphes précédents :

la contrainte d'ordre ;

l'étude de la courbe de corrélation.

3.5.a. Contrainte d'ordre.

Soit (I^g_i,j1, I^d_i,l1) et (I^g_i,j2, I^d_{i,l 2}) deux paires de pixels, vérifiant les trois contraintes citées précédemment (épipolaire, d'unicité et de seuil).

On impose en plus au produit (j2 - j1) x (l2 - l1) d'être supérieur ou égal à 0. Considérons l'exemple suivant :

Exemple 2 :

Si un pixel I^g_i,j1est à gauche d'un pixel I^g_i,j2 sur l'image gauche, alors I^d_i,l1 doit être à gauche de I^d_{i,l 2} sur l'image droite : c'est la contrainte d'ordre.

Dans l'exemple 2, la figure de droite présente deux paires qui ne vérifient pas cette contrainte.

Remarque :

La contrainte d'ordre est parfois fausse. Par exemple :

Dans la pratique, on cherchera à respecter cette contrainte en éliminant un minimum de paires. Dans l'exemple 1, il suffit d'enlever 2 paires pour respecter la contrainte d'ordre : (I^g_i,2, I^d_i,8) et (I^g_i,3, I^d_i,9). Mais cela ne change pas les appariements erronés. Que faire ?

3.5.b. Étude de la courbe de corrélation.

Pour chaque pixel à apparier, on trace une courbe avec, en abscisse, les indices de colonnes des candidats et, en ordonnée, les mesures de corrélation qui leur correspondent.

Exemple :

I^g_i,2

exemple 1

Deux attitudes sont possibles :

méthode "peureuse": s'il existe plusieurs candidats, on n'en choisit aucun => pixel non apparié (problème déjà évoqué) ;

méthode "hardie" : on cherche à vérifier à la fois la contrainte d'ordre et à réaliser un maximum d'appariements, en choisissant un candidat qui ne correspond pas forcément au minimum absolu (algorithme relativement complexe).

On obtiendra, avec l'exemple 1 (S' = 2) :

Par la méthode "peureuse" :

Il ne reste que 3 couples, ce qui n'est pas très satisfaisant.

Par la méthode "hardie" :

Avec cette méthode, il reste 9 appariements, dont 6 faux, ce qui n'est pas satisfaisant non plus !

Changeons le seuil : les candidats retenus sont maintenant ceux pour lesquels la corrélation est inférieure ou égale à S' = 10.

Par la méthode "peureuse" : il ne reste aucun appariement ;

Par la méthode "hardie" :

Au maximum, on peut réaliser 14 appariements (on ne pourrait pas en réaliser plus), qui sont tous exacts qui plus est !

3.5.c. Conclusions sur ces améliorations.

Les méthodes d'appariement ressemblent souvent à de la "cuisine". Suivant la valeur du seuil S', on obtient par la méthode "hardie" :

si S' = 2 : 9 appariements , dont 6 faux ;

si S' = 10 : 14 appariements exacts.

Par ailleurs, ces méthodes sont beaucoup plus complexes à mettre en oeuvre que la méthode décrite précédemment (avec les trois contraintes initiales).

Passons maintenant à la phase 3 de triangulation, la plus facile.

4. La triangulation : phase 3.

On suppose que :

Les paramètresetsont connus (phase 1) ;
Un certain nombre de paires de pixels (I^g_i,j, I^d_i,l) ont été déterminées (phase 2).

4.1. Expression mathématique.

Soit une paire de pixels appariés (I^g_i,j, I^d_i,l). Le point P= (Xp,Yp,Zp) correspondant à cette paire vérifie les trois équations suivantes :

(3.11)

Les deux dernières équations constituent un système linéaire de deux équations à deux inconnues : Xpet Zp. Calculons son déterminant :

Comme et , il s'ensuit que , donc que le système est un système de Cramer :

soit encore :

(3.12)

4.2. La disparité.

Dans (3.13) apparaît la différence : appelée disparité d'un couple de pixels.
On voit que l'altitude d'un point P est proportionnelle à la disparité du couple de pixels qui lui est associé.

Ces pages ont été réalisées par Jean-Denis Durou et Anne-Marie Pocquet.
Pour tout commentaire, envoyer un mail à durou@irit.fr ou à pocquet@irit.fr.

Maîtrise d'informatique - Module 11 Vision par ordinateur - Cours Chapitre 3 :

1. Cas élémentaire de stéréovision.

1.1. Réalisation pratique.

1.2. Correspondance entre points objets et pixels d'une image.

2. Le calibrage : phase 1.

2.1. Relation mathématique entre points objets et pixels.

Bilan :

2.2. Détermination des paramètres de calibrage.

2.2.a. Détermination de.

2.2.b. Détermination de .

II.2.c. Nombre d'angles solutions de l'équation (3.6)

Remarque :

3. L'appariement : phase 2.

3.1. Comparaison des niveaux de gris de deux pixels appariés.

3.2. Corrélation entre deux pixels et leurs voisinages.

Attention :

Exemples :

3.2.a. Définition du voisinage : fenêtre de corrélation.

Exemples :

3.2.b. Mesure de corrélation euclidienne.

3.3. Méthode d'appariement.

Rappel :

Exemple :

3.3.a. Appariement d'un pixel de l'image gauche.

Remarques :

3.3.b. Appariement d'un pixel de l'image droite.

Exemple :

3.3.c. Conclusion.

3.4. Appariements erronés.

Exemple :

3.5. Améliorations de la méthode d'appariement.

Exemple 1 :

3.5.a. Contrainte d'ordre.

Exemple 2 :

Remarque :

3.5.b. Étude de la courbe de corrélation.

Exemple :

3.5.c. Conclusions sur ces améliorations.

4. La triangulation : phase 3.

4.1. Expression mathématique.

4.2. La disparité.

Maîtrise d'informatique - Module 11
Vision par ordinateur - Cours

Chapitre 3 :