Géométrie épipolaire

La géométrie épipolaire limite le domaine de recherche des points en correspondance dans l'identification d'objets aux lignes épipolaires, et permet par là une énorme économie de temps de calcul. Simultanément, elle diminue le nombre de fausses correspondances en raison de la diminution du domaine de recherche. Les deux sont d'un grand intérêt dans la vision artificielle. En particulier dans le domaine des robots autonomes, il est nécessaire de simplifier les calculs pour atteindre de hautes performances, d'une part en raison des limitations sur le volume des circuits, et d'autre part pour atteindre les réactions rapides nécessaires pour éviter les collisions. C'est ainsi que l'un des participants au DARPA Grand Challenge, concours entre véhicules autonomes, a utilisé la bibliothèque de programmes OpenCV, qui contient des routines de calcul rapide de géométrie épipolaire et d'analyse de correspondance.

La reconstruction en relief (3D) d'une scène sur des photographies peut être faite si la calibration et la position des caméras est connue. Comme la géométrie épipolaire décrit la relation projective entre deux images, elle est soumise à l'autocalibration, c'est-à-dire à un calcul automatique des paramètres des caméras. Dans ce cas, la géométrie épipolaire n'est pas utilisée à la recherche des correspondances, mais elle fait l'inverse : à partir de correspondances connues, elle reconstitue une grande partie de la calibration et de la position des caméras.

L'application des points objets sur le plan image peut être décrite avec les coordonnées homogènes utilisées en géométrie projective. Les coordonnées homogènes sont les coordonnées cartésiennes ou affines, augmentées d'une coordonnée, mais ne sont définies qu'à un facteur d'échelle près. Elles permettent de représenter de façon cohérente les points à l'infini ou points de fuite des amateurs de perspective[n 3].

En coordonnées homogènes, l'application d'un point objet de l’espace à trois dimensions sur le plan bidimensionnel du plan image peut être décrite par une application linéaire :

${\displaystyle \mathbf {x} =\left({\begin{array}{c}u\\v\\w\end{array}}\right)=\mathbf {P} \,\mathbf {X} =\left({\begin{array}{cccc}p_{11}&p_{12}&p_{13}&p_{14}\\p_{21}&p_{22}&p_{23}&p_{24}\\p_{31}&p_{32}&p_{33}&p_{34}\end{array}}\right)\left({\begin{array}{c}U\\V\\W\\1\\\end{array}}\right)}$

Les coordonnées homogènes d'un point dans un plan forment un tableau 3×1, que l'on peut traiter avec les règles du calcul matriciel. Nous désignerons ainsi des points comme des matrices.

On obtient les coordonnées cartésiennes à partir de ${\displaystyle x=u/w}$ et ${\displaystyle y=v/w}$. La matrice de projection ${\displaystyle \mathbf {P} }$, de taille ${\displaystyle 3\times 4}$, décrit la projection en perspective des points objets sur le plan image. Elle contient des données d'orientation et de position de la caméra. Comme dans cette projection, il se perd une dimension (la distance de l’objet à la caméra), elle n'est pas inversible sans ambiguïté.

Le calcul de la matrice fondamentale repose sur l’idée de choisir un point ${\displaystyle \mathbf {x} _{1}}$ sur la première image, puis de déterminer un point objet ${\displaystyle \mathbf {X} }$ se projetant sur ce point image, et finalement de calculer l'image ${\displaystyle \mathbf {x} _{2}}$ de ${\displaystyle \mathbf {X} }$ sur la deuxième image. Ce point ${\displaystyle \mathbf {x} _{2}}$ et l’épipôle ${\displaystyle \mathbf {e} _{2}}$ de la deuxième image se trouvent sur la droite épipolaire et la déterminent donc de façon unique.

Étant donné un point ${\displaystyle \mathbf {x} _{1}}$ sur la première image, le rayon sur lequel se trouve le point objet correspondant est défini par la matrice de projection ${\displaystyle \mathbf {P} _{1}}$. Avec seulement la première image, il est impossible de savoir où sur le rayon il se trouve, puisque sa distance à la caméra est inconnue. En revanche, il est possible d'obtenir un point quelconque du rayon au moyen du pseudo-inverse ${\displaystyle \mathbf {P} _{1}^{+}}$ de ${\displaystyle \mathbf {P} _{1}}$ :

${\displaystyle \mathbf {X} ^{(0)}=\mathbf {P} _{1}^{+}\mathbf {x} _{1}}$

Ce point peut être projeté sur la deuxième image, à l'aide de la matrice de projection ${\displaystyle \mathbf {P} _{2}}$ de celle-ci :

${\displaystyle \mathbf {x} _{2}^{(0)}=\mathbf {P} _{2}\mathbf {P} _{1}^{+}\mathbf {x} _{1}}$

Ainsi, le point ${\displaystyle \mathbf {x} _{2}}$ obtenu se trouve sur la droite épipolaire de la deuxième image en correspondance avec ${\displaystyle \mathbf {x} _{1}}$. Un autre point est l’épipôle ${\displaystyle \mathbf {e} _{2}}$, image du centre de projection ${\displaystyle \mathbf {O} _{1}}$ de la caméra 1 :

${\displaystyle \mathbf {e} _{2}=\mathbf {P} _{2}\mathbf {O} _{1}}$

En coordonnées homogènes, un point de coordonnées ${\displaystyle (u,v,w)}$ appartient à la droite passant par les points de coordonnées ${\displaystyle (u_{1},v_{1},w_{1})}$ et ${\displaystyle (u_{2},v_{2},w_{2})}$ si et seulement si ${\displaystyle (u,v,w)}$ est une combinaison linéaire de ${\displaystyle (u_{1},v_{1},w_{1})}$ et ${\displaystyle (u_{2},v_{2},w_{2})}$. Autrement dit, le déterminant suivant est nul[n 4] :

${\displaystyle \left|{\begin{array}{ccc}u_{1}&u_{2}&u\\v_{1}&v_{2}&v\\w_{1}&w_{2}&w\\\end{array}}\right|=0}$

Ainsi, la droite épipolaire a pour équation en coordonnées homogènes :

${\displaystyle \mathrm {Det} (\mathbf {x} _{2}^{(0)},\mathbf {e} _{2},\mathbf {x} _{2})=0}$

Soit, en réinjectant les expressions précédentes ${\displaystyle \mathbf {x} _{2}^{(0)}}$ de et ${\displaystyle \mathbf {e} _{2}}$ :

${\displaystyle \mathrm {Det} (\mathbf {P} _{2}\mathbf {P} _{1}^{+}\mathbf {x} _{1},\mathbf {P} _{2}\mathbf {O} _{1},\mathbf {x} )=0}$

Développant le déterminant sous forme de produit mixte, on obtient :

${\displaystyle {(\mathbf {P} _{2}\mathbf {P} _{1}^{+}\mathbf {x} _{1}\times \mathbf {P} _{2}\mathbf {O} _{1})}^{\mathrm {T} }\mathbf {x} _{2}=0}$

En posant ${\displaystyle \mathbf {l} _{2}=\mathbf {P} _{2}\mathbf {P} _{1}^{+}\mathbf {x} _{1}\times \mathbf {P} _{2}\mathbf {O} _{1}}$, et en transposant l'équation précédente, on a alors :

${\displaystyle \mathbf {x} _{2}^{\mathrm {T} }\mathbf {l} _{2}=0}$

Comme ${\displaystyle \mathbf {l} _{2}}$ est une fonction linéaire homogène de ${\displaystyle \mathbf {x} _{1}}$, il existe une matrice ${\displaystyle \mathbf {F} }$[n 5] telle que ${\displaystyle \mathbf {l} _{2}=\mathbf {F} \mathbf {x} _{1}}$. On appelle cette matrice la matrice fondamentale. La relation entre ${\displaystyle \mathbf {x} _{1}}$ et ${\displaystyle \mathbf {x} _{2}}$ s'écrit finalement :

${\displaystyle \mathbf {x} _{2}^{\mathrm {T} }\,\mathbf {F} \,\mathbf {x} _{1}=0}$

ou encore :

${\displaystyle \left({\begin{array}{ccc}u_{2}&v_{2}&w_{2}\end{array}}\right)\left({\begin{array}{ccc}f_{11}&f_{12}&f_{13}\\f_{21}&f_{22}&f_{23}\\f_{31}&f_{32}&f_{33}\end{array}}\right)\left({\begin{array}{c}u_{1}\\v_{1}\\w_{1}\end{array}}\right)=0}$

Cette équation est appelée équation épipolaire. Étant donné un point sur l'image 2 (coordonnées ${\displaystyle u_{2}}$, ${\displaystyle v_{2}}$ et ${\displaystyle w_{2}}$ fixées), elle s'interprète comme l'équation d'une droite sur l'image 1 (${\displaystyle u_{1}}$, ${\displaystyle v_{1}}$ et ${\displaystyle w_{1}}$ variables), et inversement.

Un cas particulier de la matrice fondamentale est la matrice essentielle. Celle-ci apparaît quand on utilise des coordonnées image orthonormées, dont l’origine est la projection perpendiculaire du centre de projection sur le plan image. Comme cette condition n'est pas nécessaire pour la matrice fondamentale, la définition de cette dernière est plus générale que celle de la matrice essentielle.

La matrice fondamentale ${\displaystyle \mathbf {F} }$ (aussi appelée « tenseur bifocal ») contient toute l'information nécessaire sur la géométrie épipolaire. On peut aussi la déterminer sans connaissance sur les matrices de projection ${\displaystyle \mathbf {P} _{1}}$ et ${\displaystyle \mathbf {P} _{2}}$, ni sur les centres de projection ${\displaystyle \mathbf {O} _{1}}$ et ${\displaystyle \mathbf {O} _{2}}$, à partir de coordonnées images de points en correspondance.

La matrice fondamentale 3 × 3 n'est définie qu'à un facteur multiplicatif près, puisque le produit de la matrice fondamentale par n'importe quel nombre différent de 0 ne change rien à la validité de l'équation épipolaire ${\displaystyle \mathbf {x} _{2}^{\mathrm {T} }\mathbf {F} \mathbf {x} _{1}=0}$. Donc seuls 8 éléments de la matrice sont indépendants. Comme la matrice antisymétrique 3×3 : ${\displaystyle \times \mathbf {P} _{2}\mathbf {O} _{1}}$ comme toute matrice ${\textstyle n\times n}$ antisymétrique est singulière pour ${\displaystyle n}$ impair, ${\displaystyle \mathbf {F} }$ est singulière, et son déterminant est donc nul. Cette condition supplémentaire diminue le nombre de degrés de liberté de la matrice fondamentale à 7.

Au moyen de la matrice fondamentale, on peut calculer pour tout point ${\displaystyle \mathbf {x} _{1}}$ la droite[n 6] épipolaire correspondante ${\displaystyle \mathbf {l} _{2}}$ dans la deuxième image :

${\textstyle \mathbf {l} _{2}=\mathbf {F} \mathbf {x} _{1}}$

et évidemment inversement à un point ${\displaystyle \mathbf {x} _{2}}$ sur la deuxième image, la droite épipolaire ${\displaystyle \mathbf {l} _{1}}$ :

${\displaystyle \mathbf {l} _{1}=\mathbf {F} ^{\mathrm {T} }\mathbf {x} _{2}}$

À partir d'une droite épipolaire sur une image, on ne peut pas calculer le point correspondant sur l’autre image. Pour cela, il faudrait pouvoir inverser la matrice fondamentale, ce qui est impossible, puisqu'elle est singulière. Comme l'épipôle ${\displaystyle \mathbf {e} _{2}}$ est sur toutes les droites épipolaires ${\displaystyle \mathbf {l} _{2}}$, il faut que

${\displaystyle \mathbf {l} _{2}^{\mathrm {T} }\mathbf {e} _{2}=(\mathbf {F} \mathbf {x} _{1})^{\mathrm {T} }\mathbf {e} _{2}=\mathbf {x} _{1}^{\mathrm {T} }\mathbf {F} ^{\mathrm {T} }\mathbf {e} _{2}=0}$

pour tous les ${\displaystyle \mathbf {x} _{1}}$, si bien que l'épipôle ${\displaystyle \mathbf {e} _{2}}$, et de même ${\textstyle \mathbf {e} _{1}}$ satisfont aux équations :

${\displaystyle \mathbf {F} ^{\mathrm {T} }\mathbf {e} _{2}=0}$ et ${\displaystyle \mathbf {F} \mathbf {e} _{1}=0}$

De ces équations, on voit que le déterminant de la matrice fondamentale doit être nul, sinon, les équations n'auraient que les solutions ${\displaystyle \mathbf {e} _{1}=\mathbf {e} _{2}=0}$, ce qui est interdit en coordonnées homogènes.

Le calcul de la matrice fondamentale peut être effectué, en supposant les caméras calibrées, à partir des deux matrices de projection et d'un centre de projection (voir supra). Mais comme le calcul de la matrice fondamentale doit intervenir en général avant celle des matrices de projection, ce cas est relativement rare. Dans la suite, il sera montré comment calculer ${\displaystyle \mathbf {F} }$ avec la seule connaissance de points en correspondance.

Pour calculer la matrice fondamentale d'un ensemble de points en correspondance, développons l'équation épipolaire ${\displaystyle \mathbf {x} _{2}^{\mathrm {T} }\mathbf {F} \mathbf {x} _{1}=0}$ :

${\displaystyle x_{2}x_{1}f_{11}+x_{2}y_{1}f_{12}+x_{2}f_{13}+y_{2}x_{1}f_{21}+y_{2}y_{1}f_{22}+y_{2}f_{23}+x_{1}f_{31}+y_{1}f_{32}+f_{33}=0}$

ou, de manière vectorielle :

${\displaystyle (x_{2}x_{1},x_{2}y_{1},x_{2},y_{2}x_{1},y_{2}y_{1},y_{2},x_{1},y_{1},1)\cdot \mathbf {f} =0}$

avec :

${\displaystyle \mathbf {f} ={(f_{11},f_{12},f_{13},f_{21},f_{22},f_{23},f_{31},f_{32},f_{33})}^{\mathrm {T} }}$

À partir de ${\displaystyle n}$ points, on établit le système d'équations linéaires homogènes (l'indice supérieur désigne le point considéré) :

${\displaystyle \left({\begin{array}{ccccccccc}x_{2}^{1}x_{1}^{1}&x_{2}^{1}y_{1}^{1}&x_{2}^{1}&y_{2}^{1}x_{1}^{1}&y_{2}^{1}y_{1}^{1}&y_{2}^{1}&x_{1}^{1}&y_{1}^{1}&1\\[-1ex]\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\[-1ex]x_{2}^{n}x_{1}^{1}&x_{2}^{n}y_{1}^{1}&x_{2}^{n}&y_{2}^{n}x_{1}^{n}&y_{2}^{n}y_{1}^{n}&y_{2}^{n}&x_{1}^{n}&y_{1}^{n}&1\end{array}}\right)\,\cdot \,\mathbf {f} \,=\,\mathbf {A} \,\cdot \,\mathbf {f} \,=\,0}$

Comme les coordonnées de points en correspondance satisfont l'équation épipolaire, les colonnes de ${\textstyle \mathbf {A} }$ sont linéairement dépendantes. La matrice ${\textstyle \mathbf {A} }$ a donc au plus le rang 8. Pour plus de 8 lignes, ceci n'est valable s'il n'y a aucune erreur de mesure sur les coordonnées, et aucune paire de points faussement mis en correspondance. Si ${\textstyle \mathbf {A} }$ n'a pas un rang égal à son nombre de colonnes, il existe pour ${\displaystyle \mathbf {f} }$ (hors le cas trivial ${\displaystyle \mathbf {f} =0}$) un ensemble de solutions qui forment le noyau de ${\textstyle \mathbf {A} }$.

En général, il se produit lors de la définition des correspondances de petites erreurs de mesure, puisque les points image ne peuvent être caractérisés qu'avec une résolution finie. La matrice fondamentale ${\displaystyle \mathbf {F} }$ exprimée par le vecteur ${\displaystyle \mathbf {f} }$ n'a alors pas le rang 2 et n'est pas singulière. Ceci conduit à ce que les droites épipolaires d'une image ne se coupent pas toutes en un même point.

Pratiquement, on utilise deux méthodes pour calculer la matrice fondamentale, qui conduisent à la condition de singularité : l'algorithme à 7 points et l'algorithme à 8 points. Dans les deux méthodes, on n'utilise en général pas directement les coordonnées mesurées des points image, mais des coordonnées normalisées au préalable : on déplace l’origine des coordonnées vers le centre de gravité des points image, et on normalise les coordonnées de manière qu'elles soient de l’ordre de grandeur de 1. Avec cette normalisation, on obtient une amélioration significative des résultats.

Ce procédé utilise 7 correspondances de points pour le calcul de la matrice ${\displaystyle \mathbf {F} }$. Comme ${\displaystyle \mathbf {F} }$ n'est définie qu'à un facteur près, 7 points, ainsi que la condition ${\displaystyle \mathrm {Det} (\mathbf {F} )=0}$ suffisent pour déterminer les 9 éléments de ${\displaystyle \mathbf {F} }$. Pour les 7 correspondances de points, le système d'équations ${\textstyle \mathbf {A} }$ ne contient que 7 équations. Il possède donc deux solutions linéairement indépendantes ${\displaystyle \mathbf {f} _{1}}$ et ${\displaystyle \mathbf {f} _{2}}$ du noyau de ${\textstyle \mathbf {A} }$. La matrice fondamentale ${\displaystyle \mathbf {F} }$ est construite comme combinaison linéaire des matrices ${\displaystyle \mathbf {F} _{1}}$ et ${\displaystyle \mathbf {F} _{2}}$ construites à partir de ${\displaystyle \mathbf {f} _{1}}$ et ${\displaystyle \mathbf {f} _{2}}$ :

${\displaystyle \mathbf {F} =\alpha \,\mathbf {F} _{1}+(1-\alpha )\,\mathbf {F} _{2}}$ avec ${\displaystyle \alpha }$ réel.

Pour choisir dans l'ensemble des solutions celle qui a le rang 2, on utilise le fait que ${\displaystyle \mathrm {Det} (\mathbf {F} )=0}$ :

${\displaystyle \mathrm {Det} (\alpha \,\mathbf {F} _{1}+(1-\alpha )\,\mathbf {F} _{2})=0}$

Cette équation cubique en ${\displaystyle \alpha }$ a au moins une solution réelle, et au plus trois, si le coefficient de ${\displaystyle \alpha ^{3}}$, qui est ${\displaystyle \mathrm {Det} (\mathbf {F} _{1}-\mathbf {F} _{2})}$ est non nul. Sinon, il peut n'y avoir aucune solution pour ${\displaystyle \alpha }$ fini. Cependant, comme ${\displaystyle \mathbf {F} _{1}-\mathbf {F} _{2}}$ a un déterminant nul, c'est une bonne solution pour le problème.

On peut calculer une matrice fondamentale avec chacune des trois. Dans le cas où il existe plus d'une solution, on prend d'autres points, afin de déterminer quelle est la bonne. On choisit celle qui satisfait l'équation épipolaire pour ces points supplémentaires, aux erreurs de mesure près.

Fig. 6 - Image vue de gauche avec les points marquants

Fig. 7 - Image vue de droite avec les points marquants

Fig. 8 - Décalages entre points censés être en correspondance, reportés sur la vue de droite.

En général, on a plus de 7 correspondances de points. L'algorithme décrit ci-après nécessite au moins 8 correspondances, d'où son nom, mais peut en utiliser plus. L'idée de cet algorithme est due à Longuet-Higgins[3].

Dans une première étape, on ne considère que le système ${\textstyle \mathbf {A} \mathbf {f} =0}$, sans s'occuper de la condition ${\displaystyle \mathrm {Det} (\mathbf {F} )=0}$. Dans le cas idéal, la matrice ${\textstyle \mathbf {A} }$ a le rang 8 ; dans la pratique, comme il y a plus de 8 points, ce n'est pas le cas, ce qui fait que la solution ${\displaystyle \mathbf {f} }$ est réduite à 0. À la place, on va déterminer la solution par la méthode des moindres carrés, ou par la recherche des valeurs propres.

Dans la méthode des moindres carrés, on détermine ${\displaystyle \mathbf {f} }$ de manière que ${\displaystyle \|\mathbf {A} \mathbf {f} \|}$ soit minimal. Comme ${\displaystyle \mathbf {f} }$ n'est défini qu'à un facteur près, il faut introduire une condition de normalisation, par exemple qu'un certain élément de ${\displaystyle \mathbf {f} }$ soit égal à l'unité. Le problème ici est le choix de l’élément : il ne faut pas que c'en soit un d'un ordre de grandeur bien plus petit que les autres, ce que l'on ne connaît pas a priori. On peut essayer diverses possibilités.

L'autre méthode consiste précisément à minimiser ${\displaystyle \|\mathbf {A} \mathbf {f} \|}$, tout en satisfaisant à la condition ${\displaystyle \|\mathbf {f} \|=1}$. Ceci conduit au résultat que la solution ${\displaystyle \mathbf {f} }$ est le vecteur propre de la matrice ${\displaystyle \mathbf {A} ^{\mathrm {T} }\mathbf {A} }$ avec la plus petite valeur propre.

Mais la solution ${\displaystyle \mathbf {f} }$ ainsi obtenue ne conduit pas en général à une matrice ${\displaystyle \mathbf {F} }$ singulière. Cette condition doit être satisfaite dans une deuxième étape. À cette fin, la matrice ${\displaystyle \mathbf {F} }$ est diagonalisée sous la forme :

${\displaystyle \mathbf {F} =\mathbf {U} \mathbf {S} \mathbf {V} }$

où S est une matrice diagonale dont les éléments diagonaux sont les valeurs propres de ${\displaystyle \mathbf {F} }$. On met à 0 la plus petite de ces valeurs propres, et on recalcule ${\displaystyle \mathbf {F} }$ à partir des matrices ${\displaystyle \mathbf {U} }$, ${\displaystyle \mathbf {S} }$ ainsi rendue singulière, et ${\displaystyle \mathbf {V} }$. Le produit est donc lui-même singulier.

L'algorithme à 8 points est un processus simple pour déterminer la matrice fondamentale, mais il est instable vis-à-vis des erreurs de mesure. Ceci est dû au fait que la condition de singularité de la matrice fondamentale est introduite a posteriori, et que la grandeur minimisée ${\displaystyle \|\mathbf {A} \mathbf {f} \|}$ ne possède aucune signification physique. Il existe d'autres processus qui ne présentent aucun de ces inconvénients[7]. Mais ces procédés sont plus lourds et rarement utilisés en pratique.

Ce n'est qu'avec des objectifs de haute qualité que l'on peut négliger la distorsion. Avec des objectifs de moindre qualité, il faut considérer la distorsion pour aboutir à une bonne précision de la reconstitution. La distorsion peut souvent être modélisée comme une distorsion radiale, c'est-à-dire qu'un point qui aurait pour coordonnées polaires par rapport au centre de l'image ${\textstyle (r,\theta )}$ en l'absence de distorsion a, à cause des distorsions, des coordonnées polaires ${\displaystyle (rf(r),\theta )}$, où ${\displaystyle f(r)=1}$ pour ${\displaystyle r}$ petit, mais s'en écarte progressivement de quelques pourcents vers les bords de l’image pour des objectifs très quelconques.

Si une caméra est soigneusement calibrée, et si la distorsion est connue, les images peuvent être corrigées. On peut alors travailler avec les images corrigées comme sur des images sans distorsion.

Dans certaines conditions, la distorsion peut être prise en compte par une matrice fondamentale généralisée. On suppose pour chaque image une distorsion caractérisée par un paramètre inconnu, et qui correspond au remplacement du plan image par une surface quadratique dans l'espace projectif à trois dimensions (à 4 coordonnées homogènes). La relation entre deux points en correspondance s'exprime alors par une matrice ${\displaystyle 4\times 4}$ à 9 degrés de liberté[8].

Pour les caméras à grand angle, qui permettent des prises de vue à grand champ, on ne peut plus modéliser la géométrie de prise de vue par un sténopé avec une image plane. La description de la géométrie épipolaire dépend du type de caméra. Par exemple, pour une caméra consistant en un sténopé avec un miroir hyperbolique, les lignes épipolaires sont des coniques.

• (de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Epipolargeometrie » (voir la liste des auteurs).