Triangulation (vision par ordinateur) - Triangulation (computer vision)

En vision par ordinateur, la triangulation fait référence au processus de détermination d'un point dans l'espace 3D en fonction de ses projections sur deux images ou plus. Afin de résoudre ce problème, il est nécessaire de connaître les paramètres de la fonction de projection de caméra de 3D à 2D pour les caméras impliquées, dans le cas le plus simple représenté par les matrices de caméra . La triangulation est parfois également appelée reconstruction ou intersection .

Le problème de la triangulation est en principe trivial. Comme chaque point d'une image correspond à une ligne dans l'espace 3D, tous les points de la ligne en 3D sont projetés sur le point de l'image. Si une paire de points correspondants dans deux images ou plus peut être trouvée, il doit s'agir de la projection d'un point 3D commun x . L'ensemble des lignes générées par les points de l'image doit se croiser en x (point 3D) et la formulation algébrique des coordonnées de x (point 3D) peut être calculée de différentes manières, comme présenté ci-dessous.

En pratique, cependant, les coordonnées des points d'image ne peuvent pas être mesurées avec une précision arbitraire. Au lieu de cela, divers types de bruit, tels que le bruit géométrique de la distorsion de l'objectif ou l'erreur de détection de point d'intérêt, conduisent à des inexactitudes dans les coordonnées de l'image mesurée. En conséquence, les lignes générées par les points d'image correspondants ne se croisent pas toujours dans l'espace 3D. Le problème, alors, est de trouver un point 3D qui s'adapte de manière optimale aux points d'image mesurés. Dans la littérature, il existe de multiples propositions pour définir l'optimalité et trouver le point 3D optimal. Puisqu'elles sont basées sur différents critères d'optimalité, les différentes méthodes produisent différentes estimations du point 3D x lorsque le bruit est impliqué.

introduction

Dans ce qui suit, on suppose que la triangulation est effectuée sur des points d'image correspondants à partir de deux vues générées par des caméras à sténopé . La généralisation de ces hypothèses est discutée ici .

Le cas idéal de la géométrie épipolaire. Un point 3D x est projeté sur deux images de caméra à travers des lignes (vertes) qui se croisent avec le point focal de chaque caméra, O ₁ et O ₂ . Les points d'image résultants sont y ₁ et y ₂ . Les lignes vertes se coupent en x .

En pratique, les points d'image y ₁ et y ₂ ne peuvent pas être mesurés avec une précision arbitraire. Au lieu de cela, les points y ' ₁ et y' ₂ sont détectés et utilisés pour la triangulation. Les lignes de projection correspondantes (bleues) ne se coupent pas, en général, dans l'espace 3D et peuvent également ne pas se croiser avec le point x .

L'image de gauche illustre la géométrie épipolaire d'une paire de caméras stéréo d'un modèle à sténopé . Un point x (point 3D) dans l'espace 3D est projeté sur le plan d'image respectif le long d'une ligne (verte) qui passe par le point focal de la caméra , et , résultant en les deux points d'image correspondants et . Si et sont donnés et que la géométrie des deux caméras est connue, les deux lignes de projection (lignes vertes) peuvent être déterminées et il faut qu'elles se croisent au point x (point 3D). En utilisant l'algèbre linéaire de base , ce point d'intersection peut être déterminé de manière simple. ${\ displaystyle \ mathbf {O} _ {1}}$ ${\ displaystyle \ mathbf {O} _ {2}}$ ${\ displaystyle \ mathbf {y} _ {1}}$ ${\ displaystyle \ mathbf {y} _ {2}}$ ${\ displaystyle \ mathbf {y} _ {1}}$ ${\ displaystyle \ mathbf {y} _ {2}}$

L'image de droite montre le cas réel. La position de l'image pointe et ne peut pas être mesurée exactement. La raison est une combinaison de facteurs tels que ${\ displaystyle \ mathbf {y} _ {1}}$ ${\ displaystyle \ mathbf {y} _ {2}}$

Distorsion géométrique, par exemple distorsion de l'objectif , ce qui signifie que le mappage 3D vers 2D de la caméra s'écarte du modèle de caméra sténopé . Dans une certaine mesure, ces erreurs peuvent être compensées, laissant une erreur géométrique résiduelle.
Un seul rayon de lumière provenant de x (point 3D) est dispersé dans le système de lentilles des caméras selon une fonction d'étalement de points . La récupération du point image correspondant à partir des mesures de la fonction d'intensité dispersée dans les images donne des erreurs.
Dans un appareil photo numérique, la fonction d'intensité d'image n'est mesurée que dans des éléments de capteur discrets. Une interpolation inexacte de la fonction d'intensité discrète doit être utilisée pour récupérer la vraie.
Les points d'image y ₁^' et y ₂ ' utilisés pour la triangulation sont souvent trouvés en utilisant divers types d'extracteurs de caractéristiques, par exemple des coins ou des points d'intérêt en général. Il existe une erreur de localisation inhérente à tout type d'extraction d'entités basée sur des opérations de voisinage .

Par conséquent, les points d'image mesurés sont et au lieu de et . Cependant, leurs lignes de projection (bleues) ne doivent pas se croiser dans l'espace 3D ou se rapprocher de x . En fait, ces droites se croisent si et seulement si et satisfont la contrainte épipolaire définie par la matrice fondamentale . Compte tenu du bruit de mesure dans et il est plutôt probable que la contrainte épipolaire ne soit pas satisfaite et que les lignes de projection ne se croisent pas. ${\ displaystyle \ mathbf {y} '_ {1}}$ ${\ displaystyle \ mathbf {y} '_ {2}}$ ${\ displaystyle \ mathbf {y} _ {1}}$ ${\ displaystyle \ mathbf {y} _ {2}}$ ${\ displaystyle \ mathbf {y} '_ {1}}$ ${\ displaystyle \ mathbf {y} '_ {2}}$ ${\ displaystyle \ mathbf {y} '_ {1}}$ ${\ displaystyle \ mathbf {y} '_ {2}}$

Cette observation conduit au problème qui se résout en triangulation. Quel est le point 3D x _is est la meilleure estimation de x donné et et la géométrie des caméras? La réponse est souvent trouvée en définissant une mesure d'erreur qui dépend de x _est , puis en minimisant cette erreur. Dans les sections suivantes, quelques - unes des différentes méthodes de calcul x _HNE présentées dans la littérature sont brièvement décrits. ${\ displaystyle \ mathbf {y} '_ {1}}$ ${\ displaystyle \ mathbf {y} '_ {2}}$

Toutes les méthodes de triangulation produisent x _est = x dans le cas où et , c'est-à-dire lorsque la contrainte épipolaire est satisfaite (sauf pour les points singuliers, voir ci-dessous). C'est ce qui se passe lorsque la contrainte n'est pas satisfaite qui diffère entre les méthodes. ${\ displaystyle \ mathbf {y} _ {1} = \ mathbf {y} '_ {1}}$ ${\ displaystyle \ mathbf {y} _ {2} = \ mathbf {y} '_ {2}}$

Propriétés

Une méthode de triangulation peut être décrite en termes d'une fonction telle que ${\ displaystyle \ tau \,}$

{\ displaystyle \ mathbf {x} \ sim \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2})}

où sont les coordonnées homogènes des points d'image détectés et les matrices de la caméra. x (point 3D) est la représentation homogène du point 3D résultant. Le signe implique qu'il suffit de produire un vecteur qui est égal à x jusqu'à une multiplication par un scalaire non nul puisque des vecteurs homogènes sont impliqués. ${\ displaystyle \ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}}$ ${\ displaystyle \ mathbf {C} _ {1}, \ mathbf {C} _ {2}}$ ${\ displaystyle \ sim \,}$ ${\ displaystyle \ tau \,}$

Avant d'examiner les méthodes spécifiques, c'est-à-dire les fonctions spécifiques , il y a quelques concepts généraux liés aux méthodes qui doivent être expliqués. La méthode de triangulation choisie pour un problème particulier dépend dans une certaine mesure de ces caractéristiques. ${\ displaystyle \ tau \,}$

Singularités

Certaines méthodes ne parviennent pas à calculer correctement une estimation de x (point 3D) si elle se trouve dans un certain sous-ensemble de l'espace 3D, correspondant à une combinaison de . Un point de ce sous-ensemble est alors une singularité de la méthode de triangulation. La raison de l'échec peut être qu'un système d'équations à résoudre est sous-déterminé ou que la représentation projective de x _est devient le vecteur nul pour les points singuliers. ${\ displaystyle \ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2}}$

Invariance

Dans certaines applications, il est souhaitable que la triangulation soit indépendante du système de coordonnées utilisé pour représenter les points 3D; si le problème de triangulation est formulé dans une système de coordonnées, puis transformé en un autre l'estimation résultante x _is doit transformer de la même manière. Cette propriété est communément appelée invariance . Toutes les méthodes de triangulation n'assurent pas l'invariance, du moins pas pour les types généraux de transformations de coordonnées.

Pour une représentation homogène des coordonnées 3D, la transformation la plus générale est une transformation projective, représentée par une matrice . Si les coordonnées homogènes sont transformées selon ${\ displaystyle 4 \ fois 4}$ ${\ displaystyle \ mathbf {T}}$

{\ displaystyle \ mathbf {\ bar {x}} \ sim \ mathbf {T} \, \ mathbf {x}}

alors les matrices de la caméra doivent se transformer en ( C _k )

{\ displaystyle \ mathbf {\ bar {C}} _ ​​{k} \ sim \ mathbf {C} _ {k} \, \ mathbf {T} ^ {- 1}}

pour produire les mêmes coordonnées d'image homogènes ( y _k )

{\ displaystyle \ mathbf {y} _ {k} \ sim \ mathbf {\ bar {C}} _ ​​{k} \, \ mathbf {\ bar {x}} = \ mathbf {C} _ {k} \, \ mathbf {x}}

Si la fonction de triangulation est invariante, alors la relation suivante doit être valide ${\ displaystyle \ tau}$ ${\ displaystyle \ mathbf {T}}$

{\ displaystyle \ mathbf {\ bar {x}} _ {\ rm {est}} \ sim \ mathbf {T} \, \ mathbf {x} _ {\ rm {est}}}

d'où découle que

{\ displaystyle \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1}, \ mathbf {C} _ {2}) \ sim \ mathbf {T} ^ {- 1} \, \ tau (\ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}, \ mathbf {C} _ {1} \, \ mathbf {T} ^ {- 1}, \ mathbf {C} _ {2} \, \ mathbf {T} ^ {- 1}),}

pour tous

{\ displaystyle \ mathbf {y} '_ {1}, \ mathbf {y}' _ {2}}

Pour chaque méthode de triangulation, il peut être déterminé si cette dernière relation est valide. Si c'est le cas, il ne peut être satisfait que pour un sous-ensemble des transformations projectives, par exemple, les transformations rigides ou affines.

Complexité informatique

La fonction n'est qu'une représentation abstraite d'un calcul qui, en pratique, peut être relativement complexe. Certaines méthodes aboutissent à une fonction qui est une fonction continue de forme fermée tandis que d'autres doivent être décomposées en une série d'étapes de calcul impliquant, par exemple, SVD ou trouver les racines d'un polynôme. Encore une autre classe de méthodes aboutit à laquelle doit s'appuyer sur une estimation itérative de certains paramètres. Cela signifie que le temps de calcul et la complexité des opérations impliquées peuvent varier entre les différentes méthodes. ${\ displaystyle \ tau}$ ${\ displaystyle \ tau}$ ${\ displaystyle \ tau}$

Méthodes

Méthode du point médian

Chacun des deux points d'image et a une ligne de projection correspondante (bleue dans l'image de droite ci-dessus), ici désignée par et , qui peut être déterminée compte tenu des matrices de la caméra . Soit une fonction de distance entre une (ligne 3D) L et un x (point 3D) telle que la distance euclidienne entre et . La méthode de point médian trouve le point x _is qui minimise ${\ displaystyle \ mathbf {y} '_ {1}}$ ${\ displaystyle \ mathbf {y} '_ {2}}$ ${\ displaystyle \ mathbf {L} '_ {1}}$ ${\ displaystyle \ mathbf {L} '_ {2}}$ ${\ displaystyle \ mathbf {C} _ {1}, \ mathbf {C} _ {2}}$ ${\ displaystyle d \,}$ ${\ displaystyle d (\ mathbf {L}, \ mathbf {x})}$ ${\ displaystyle \ mathbf {L}}$ ${\ displaystyle \ mathbf {x}}$

{\ displaystyle d (\ mathbf {L} '_ {1}, \ mathbf {x}) ^ {2} + d (\ mathbf {L}' _ {2}, \ mathbf {x}) ^ {2} }

Il s'avère que x _est se trouve exactement au milieu du segment de ligne le plus court qui joint les deux lignes de projection.

Transformation linéaire directe

Via la matrice essentielle

Le problème à résoudre ici est de savoir comment calculer les coordonnées d'image normalisées correspondantes et . Si la matrice essentielle est connue et que les transformations de rotation et de translation correspondantes ont été déterminées, cet algorithme (décrit dans l'article de Longuet-Higgins) fournit une solution. ${\ displaystyle (x_ {1}, x_ {2}, x_ {3})}$ ${\ displaystyle (y_ {1}, y_ {2})}$ ${\ displaystyle (y '_ {1}, y' _ {2})}$

Soit la ligne k de la matrice de rotation : ${\ displaystyle \ mathbf {r} _ {k}}$ ${\ displaystyle \ mathbf {R}}$

{\ displaystyle \ mathbf {R} = {\ begin {pmatrix} - \ mathbf {r} _ {1} - \\ - \ mathbf {r} _ {2} - \\ - \ mathbf {r} _ {3 } - \ end {pmatrix}}}

La combinaison des relations ci-dessus entre les coordonnées 3D dans les deux systèmes de coordonnées et le mappage entre les points 3D et 2D décrit précédemment donne

{\ displaystyle y '_ {1} = {\ frac {x' _ {1}} {x '_ {3}}} = {\ frac {\ mathbf {r} _ {1} \ cdot ({\ tilde {\ mathbf {x}}} - \ mathbf {t})} {\ mathbf {r} _ {3} \ cdot ({\ tilde {\ mathbf {x}}} - \ mathbf {t})}} = {\ frac {\ mathbf {r} _ {1} \ cdot (\ mathbf {y} - \ mathbf {t} / x_ {3})} {\ mathbf {r} _ {3} \ cdot (\ mathbf { y} - \ mathbf {t} / x_ {3})}}}

ou

{\ displaystyle x_ {3} = {\ frac {(\ mathbf {r} _ {1} -y '_ {1} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {t}} { (\ mathbf {r} _ {1} -y '_ {1} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {y}}}}

Une fois déterminé, les deux autres coordonnées peuvent être calculées comme ${\ displaystyle x_ {3}}$

{\ displaystyle {\ begin {pmatrix} x_ {1} \\ x_ {2} \ end {pmatrix}} = x_ {3} {\ begin {pmatrix} y_ {1} \\ y_ {2} \ end {pmatrix }}}

La dérivation ci-dessus n'est pas unique. Il est également possible de commencer par une expression pour et de dériver une expression pour selon ${\ displaystyle y '_ {2}}$ ${\ displaystyle x_ {3}}$

{\ displaystyle x_ {3} = {\ frac {(\ mathbf {r} _ {2} -y '_ {2} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {t}} { (\ mathbf {r} _ {2} -y '_ {2} \, \ mathbf {r} _ {3}) \ cdot \ mathbf {y}}}}

Dans le cas idéal, lorsque la caméra cartographie les points 3D selon une caméra sténopé parfaite et que les points 2D résultants peuvent être détectés sans aucun bruit, les deux expressions pour sont égales. En pratique, cependant, ils ne le sont pas et il peut être avantageux de combiner les deux estimations de , par exemple, en termes d'une sorte de moyenne. ${\ displaystyle x_ {3}}$ ${\ displaystyle x_ {3}}$

Il existe également d'autres types d'extensions des calculs ci-dessus qui sont possibles. Ils ont commencé par une expression des coordonnées de l'image amorcée et des coordonnées 3D dérivées dans le système non amorcé. Il est également possible de commencer avec des coordonnées d'image non amorcées et d'obtenir des coordonnées 3D amorcées, qui peuvent finalement être transformées en coordonnées 3D non amorcées. Encore une fois, dans le cas idéal, le résultat doit être égal aux expressions ci-dessus, mais en pratique, ils peuvent différer.

Une dernière remarque concerne le fait que si la matrice essentielle est déterminée à partir de la coordonnée d'image correspondante, ce qui est souvent le cas lorsque des points 3D sont déterminés de cette manière, le vecteur de translation n'est connu que jusqu'à une échelle positive inconnue. En conséquence, les points 3D reconstruits sont également indéterminés par rapport à une mise à l'échelle positive. ${\ displaystyle \ mathbf {t}}$

Triangulation optimale

Voir également

Références

Richard Hartley et Andrew Zisserman (2003). Géométrie à vues multiples en vision par ordinateur . La presse de l'Universite de Cambridge. ISBN 978-0-521-54051-3 .

Liens externes

Triangulation à deux vues et à vues multiples dans Matlab

Languages

In other projects