RR-2665 : On the Geometry and Algebra of the Point and Line Correspondences between $N$ Images

Abstract : We explore the geometric and algebraic relations that exist between correspondences of points and lines in an arbitrary number of images. We propose to use the formalism of the Grassmann-Cayley algebra as the simplest way to make both geometric and algebraic statements in a very synthetic and effective way (i.e. allowing actual computation if needed). We have a fairly complete picture of the situation in the case of points: there are only three types of algebraic relations which are satisfied by the coordinates of the images of a 3-D point: bilinear relations arising when we consider pairs of images among the $N$ and which are the well-known epipolar constraints, trilinear relations arising when we consider triples of images among the $N$, and quadrilinear relations arising when we consider four-tuples of images among the $N$. Moreover, we show that for a given triple of images, once the epipolar constraints are known, there is only one algebraically independent trilinear relation which can be used to predict the image coordinates of a point in a third image, given the coordinates of the images in the other two images, even in cases where the prediction by the epipolar constraints fails (points in the trifocal plane, or optical centers aligned). We also show that the trilinear relations imply the bilinear ones, i.e. the epipolar constraints. Finally, we show that the quadrilinear relations are algebraically dependent of the trilinear and bilinear ones, i.e. do not bring in any new information. In the case of lines, we show how the traditional perspective projection equation can be suitably generalized and that in the case of three images there exist two independent trilinear relations between the coordinates of the images of a 3-D line.

Résumé : Nous étudions les relations algébriques et géométriques entre les correspondences de points et de droites dans un nombre arbitraire d'images. Nous proposons pour ce faire d'utiliser le formalisme de l'algèbre de Grassmann-Cayley qui nous apparaît comme l'un des moyens les plus simples pour exprimer de manière effective (c'est-à-dire permettant les calculs) des propriétés géométriques et algébriques. La situation dans le cas des points est assez bien comprise. Il n'y a que trois types de relations algébriques sur les coordonnées images d'un point 3-D : des relations bilinéaires apparaîssent lorsqu'on considère des couples d'images et induisent les contraintes épipolaires, bien connues; des relations trilinéaires apparaîssent lorsque l'on considère des triplets d'images, et des relations quadrilinéaires apparaîssent lorsque l'on considère des quadruplets d'images. De plus nous montrons que pour un triplet d'images donné, lorsque les contraintes épipolaires sont connues, il n'y a qu'une relation trilinéaire algébriquement indépendante et qui peut être utilisée pour prédire les coordonnées d'un point dans la troisième image à partir des coordonnées des deux autres, ceci même dans les cas où la géométrie épipolaire ne permet pas de le faire (points dans le plan trifocal, centres optiques alignés). Nous monstrons aussi que les relations trilinéaires impliquent les bilinéaires, c'est-à-dire les contraintes épipolaires. Enfin nous montrons que les relations quadrilinéaires sont algébriquement dépendantes des relations bilinéaires et trilinéaires, et donc n'apportent pas a priori d'information supplémentaire. Dans le cas des droites nous montrons que l'équation classique de projection perspective peut être généralisée convenablement et que dans le cas de trois images il existe deux relations trilinéaires indépendantes entre les coordonnées des images d'une droite 3-D.

RR-2665 - On the Geometry and Algebra of the Point and Line Correspondences between $N$ Images