thumb|upright=1.3|Fig. 1 - Deux appareils photo observent la même scène de deux positions différentes. La géométrie épipolaire décrit les relations entre les deux images.

La géométrie épipolaire est un modèle mathématique de géométrie, qui décrit les relations géométriques de différentes photos du même objet, prises de différents points d'observation. Elle permet de décrire les dépendances entre les pixels en correspondance – c'est-à-dire ceux formés par un seul point de l’objet observé sur chacune des images. Bien que les bases en aient été posées dès 1883 par Guido Hauck, et explorées en 1908 par , la géométrie épipolaire n'a pris quelque importance qu'avec l'exploitation des images numériques, avant tout dans le domaine de la vision artificielle.

En tout premier plan, la géométrie épipolaire sert à restituer l'information tridimensionnelle à partir d'images. Elle sert là de soutien à l'analyse des correspondances, à savoir la détection des pixels en correspondance, et elle permet d'y réduire considérablement le temps de recherche.

Principe thumb|Fig. 2 - Principe de la projection par sténopé : seuls les rayons émanant de l’objet en relief passant par le trou peuvent former l’image, en perspective.|alt=Principe de la projection par sténopé : seuls les rayons émanant de l’objet en relief passant par le trou peuvent former l’image, en perspective.

Un appareil photo, ou une caméra, peut être modélisé géométriquement par une chambre à sténopé. Dans celle-ci, pendant la prise de vue, le centre du trou, chaque point de l'objet visé et le point en correspondance dans l’image sont alignés. Si un point objet a été vu par deux caméras différentes, on peut en fonction des positions des trous dans l’espace, et par rapport aux images, reconstituer les deux droites, et leur intersection, qui est le point objet, que l'on peut donc calculer ultérieurement. On a ainsi la reconstruction à trois dimensions d'un point objet dont on peut identifier les points en correspondance sur deux images. La géométrie épipolaire sert à faciliter cette reconstruction : si le point est donné sur une image, la connaissance de la situation en géométrie épipolaire limite la recherche du point en correspondance sur l'autre image à une ligne.

thumb|left|Fig. 3 - Représentation schématique de la géométrie épipolaire. Dans le schéma ci-contre à gauche, on présente les êtres géométriques suivants : point objet et points image, centres de projection et des deux caméras, ainsi que leurs plans image, replacés en avant des centres de projection par symétrie (ce qui ne change rien à l'alignement, mais facilite la représentation). Le point objet se projette sur l'image de gauche en . À partir de ce point image, le point objet ne peut se trouver que sur le rayon rectiligne : par exemple en , , ou , qui ont tous la même image à gauche. Tous ces points se projettent à droite sur une même droite (« droite épipolaire », en rouge), sur laquelle on peut se borner à rechercher le point en correspondance avec .

La géométrie épipolaire permet de trouver une relation simple entre points en correspondance, sans connaissance de la position des caméras. Bien sûr, pour une géométrie épipolaire donnée, on peut trouver des informations sur les positions relatives des caméras, mais on n'a pas besoin de connaître explicitement les positions des caméras pour cela. La géométrie épipolaire ne dépend que des paramètres des caméras, et est indépendante de la structure de la scène photographiée.

Pour décrire la géométrie épipolaire et ses éléments, on utilise une terminologie donnée. Le plan qui contient les deux centres de projection et le point objet s'appelle plan épipolaire (en vert sur le schéma). Celui-ci coupe chacune des deux images selon une droite, la droite épipolaire (en rouge sur le schéma). Pour un point donné sur une image, le point en correspondance se trouve sur la droite épipolaire de l’autre image. La droite qui joint les deux centres de projection intersecte chaque plan image en un point, l'épipôle (points notés respectivement eG et eD sur le schéma). Les épipôles restent fixes tant que la position relative des caméras reste fixe. L'épipôle d'une image est en même temps l'image du centre de projection de l’autre caméra. Toutes les droites épipolaires d'une image passent par l’épipôle, qui peut d'ailleurs, selon la position relative des caméras, se trouver hors du champ de l'image L'épipôle peut être à l'infini, auquel cas les droites épipolaires sont parallèles. D'où l'intérêt de travailler avec des coordonnées homogènes, où les points à l'infini ne nécessitent pas un traitement spécial par rapport aux autres.Dans le domaine de la photogrammétrie, les termes consacrés jadis, et encore partiellement utilisés aujourd'hui étaient un peu différents ; voir ..

Applications

La géométrie épipolaire est essentiellement utilisée en géométrie projective, en photogrammétrie, et en vision artificielle. Son but principal y est l'analyse des correspondances : si l'on recherche, pour un point remarquable d'une image, le point en correspondance sur l'autre image, il faut, en l'absence d'information sur la géométrie épipolaire, explorer l'ensemble de l'autre image. Si l'on connaît la géométrie épipolaire, il suffit de le rechercher sur la droite épipolaire. Ceci amène à une diminution importante de l'espace d'exploration. Pour cela, on utilise la géométrie épipolaire avant tout là où il faut analyser en trois dimensions une scène ou un objet avec des caméras. Les domaines importants sont la mesure de pièces pour le contrôle de qualité, le relevé de bâtiments en photogrammétrie architecturale, la photogrammétrie aérienne pour l'établissement de cartes géographiques ou encore la vision dans l'espace pour des automates autonomes.

Vision artificielle

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.

Autocalibrage des caméras

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.

Histoire thumb|Fig. 5 - La fig. 1a de la table I de l’article de Hauck illustre la citation. L'histoire de la géométrie épipolaire est étroitement liée avec celle de la photogrammétrie. Le premier à analyser les relations géométriques à sa base a été le mathématicien Guido Hauck. En 1883, il publie un article dans le Journal für die reine und angewandte Mathematik, où le concept de « point central » est utilisé pour la première fois. Sans souci des anachronismes, et pour garder une terminologie uniforme, nous allons utiliser la nomenclature de la géométrie épipolaire, où le point central est clairement l'épipôle.

Soient (Fig. 1a) et deux plans de projection, et les centres de projection correspondants. La droite d'intersection sera la section de base. La droite coupe les plans de projection en et , que nous appellerons épipôles des deux plans.

Horst von Sanden en a fait une présentation plus vaste en 1908 dans le cadre de sa thèse « Détermination des épipôles en photogrammétrie. » Il y décrit des méthodes pour déterminer les épipôles de manière plus simple et plus exacte.

Avant l'introduction de la technique digitale, pour la photogrammétrie prédominante appelée analogique, fondée sur la photographie et son exploitation mécano-optique, l'analyse des correspondances était effectuée de façon manuelle. Comme un opérateur humain peut effectuer sans problème la correspondance entre points d'une scène suffisamment structurée, ces découvertes restèrent sans beaucoup d'applications. Ce n'est que la survenue de la photogrammétrie digitale, avec des photographies digitales et l'exploitation hors-ligne sur ordinateurs, à partir des années 1980, ainsi que le besoin croissant d'une exploitation automatisée des images dans le domaine de la vision artificielle qui a fait revivre de façon plus intensive l'étude de la géométrie épipolaire et de ses applications. Un premier travail, qui témoigne de la redécouverte de cette thématique a été la publication de Hugh Christopher Longuet-Higgins dans la revue Nature. Depuis, de nombreux scientifiques s'intéressent à la géométrie épipolaire, parmi lesquels Huang et Olivier Faugeras, Horn ou Vieville et Lingrand.

Description mathématique

La géométrie épipolaire établit une relation entre les coordonnées des points en correspondance dans les plans image. Ces coordonnées sont souvent des coordonnées cartésiennes orthonormées, mais ce peuvent être des coordonnées affines quelconques. L'origine du système de coordonnées d'une image est souvent au milieu ou dans un coin de l'image. Pour des images numériques (images CCD ou scannées), on peut prendre par exemple la ligne et la colonne des pixels comme coordonnées. Quand les définitions de ligne et de colonne sont différentes, ou que les axes ne sont pas perpendiculaires, on a des coordonnées affines.

Les relations entre les coordonnées image de points en correspondance sont décrites par une matrice fondamentale. Elle permet de définir pour chaque point de la première image la droite épipolaire correspondante sur la deuxième, droite sur laquelle se trouve le point en correspondance.

Coordonnées homogènes et matrice de projection

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 perspectiveLes coordonnées à deux dimensions correspondent aux coordonnées homogènes . Les coordonnées homogènes et représentent le même point, quand . Les cas représentent les points à l'infini, qui n'ont pas de coordonnées cartésiennes. Comme les coordonnées homogènes sont définies à un facteur multiplicatif près, il est interdit de les prendre toutes nulles. Une généralisation à l'espace à trois dimensions est évidente.

Il est possible et parfois commode de représenter ces ensembles de nombres par des matrices, pour le plan de dimensions 3×1 (colonne) ou 1×3 (ligne) transposées, pour l'espace 4×1 ou 1×4..

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 :

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.