Les algorithmes utilisés par Drive Engine

 

Algorithmes de détection et d’extraction

Le détecteur Harris

La première étape est l’application du gradient. Le gradient est un opérateur mathématique qui peut être vu comme un filtre passe-haut qui laisse passer les hautes fréquences, c’est à dire les changements de niveaux de gris significatifs qui vont donc correspondre aux coins et contours:

gradient

Attention, la mise en place du gradient dépend directement d’un seuil qu’il est important de bien choisir. Toujours dans l’analogie du filtre passe-haut, ce seuil correspondrait à la fréquence de coupure du filtre. Le choix du seuil est une étape délicate: s’il est choisi trop bas, trop de détails apparaîtront sur le gradient, et inversement, s’il est choisi trop haut certaines zones d’intérêt risqueraient de ne pas apparaître sur le gradient.

seuil

Le détecteur Harris repose sur la détection de coins. L’idée est de penser que lorsque nous nous trouvons sur un coin, un déplacement dans n’importe quelle direction produira un changement significatif des niveaux de gris de l’image.

coin

SURF (Speeded-Up Robust Features)

SURF est une méthode assez complexe du point de vue des mathématiques mais une fois encore, bien que tout le côté mathématique soit géré par OpenCV, il est important de saisir son fonctionnement pour pouvoir en analyser les résultats. Elle peut être utilisée aussi bien pour la détection que pour l’extraction et utilise une approximation de la matrice hessienne. Il utilise des images intégrales afin de diminuer fortement les temps de calculs car elles permettent le calcul rapide.

Pour rappel, la valeur d’une image intégrale Ii en un point donné représente la somme de tous les pixels de l’image d’origine Io situés dans le rectangle formé par l’origine et le point considéré :

imint

Et dans notre contexte, la matrice hessienne sera la suivante:hessienne

où les coefficients sont donc par définitions les dérivées secondes suivant les directions x ou y.
Pour trouver les zones d’intérêt il faudra ensuite maximiser le déterminant de cette matrice.

Pour le descripteur (l’extraction), les calculs se feront grâce aux ondelettes de Haar qui permettront d’optimiser l’utilisation du gradient. Les réponses des ondelettes de Haar sont calculées en x et y dans une fenêtre circulaire dont le rayon dépendra d’un facteur d’échelle défini au préalable. La somme des réponses calculées dans ce rayon nous permettra de juger si la zone autour du point d’intérêt est effectivement une zone d’intérêt. Dans le cas où cette zone n’est pas jugées comme intéressante, on en déduira que le point détecté est un faux point d’intérêt.
C’est là la différence fondamentale entre la détection et l’extraction: alors que la détection va calculer de manière isolée, point par point, si un point est un point d’intérêt ou pas; l’extraction va permettre de déterminer si un point d’intérêt en est un ou pas en fonction cette zone de points environnants. Ainsi, grâce à l’extraction, les zones texturées ou les bruits causés par une mauvaise qualité d’image ne seront pas perçus comme des points d’intérêt.

Algorithmes de correspondance

Une fois encore, il existe de nombreuses méthodes pour réaliser cette étape mais pour son application, l’équipe Drive Engine a choisi une méthode Brute-Force Matcher. En informatique, une méthode de force brute est une technique de résolution de problèmes très générale qui consiste à énumérer systématiquement tous les candidats possibles pour la solution et vérifier si chaque candidat satisfait l’énoncé du problème.
Cette méthode présente l’avantage d’être efficace en terme de points matchés mais reste loin d’être optimale.

Pour cette raison, vous pourrez également utiliser la méthode on verra bien sur la plateforme Drive Engine.

Algorithmes de calibration

L’étape de triangulation est la plus significative; c’est au cours de celle-ci que les points des images de 2D sont convertis en un nuage de points 3D.

triang

Concernant la calibration, il existe deux méthodes bien différentes aussi bien au niveau de la simplicité que de l’algorithmie: la calibration avec damier et la calibration sans damier.

La calibration avec damier

La calibration présente plusieurs objectifs:

  • Elle permet de corriger d’éventuelles distorsions géométriques induites par le système optique utilisé.
  • Estimer la position et l’orientation des prises de vues dans l’espace

La calibration est basée sur deux types de paramètres:

  • les paramètres extrinsèques: qui varient suivant la position de la caméra dans l’espace. Ils sont représentés par une matrice de rotation 3×3 et un vecteur position représentant l’orientation et la position de la caméra.
  • Les paramètres intrinsèques: qui sont internes à la caméra. Généralement ces paramètres sont la distance focale, les facteurs d’agrandissement présents sur chaque image et la position du repère (souvent positionné sur le coin bas gauche de l’image). Ils permettront de corriger la distorsion.

Finalement, en plaçant ces paramètres dans les matrices intrinsèque (Matrice 3×3) et extrinsèque (Matrice 4×3) et en effectuant le produit matriciel de ces deux matrices on obtient la matrice caméra qui contiendra toutes les données des matrices intrinsèques et extrinsèques.

A noter que la calibration par damier n’est qu’une méthode spécifique de calibration par mire. Une mire étant un ensemble de points dont les coordonnées sont parfaitement connues et de préférence facilement descriptible, le damier étant une mire très simple on y a souvent recours même s’il peut être remplacé par un autre objet.
Le principe est simple : en connaissant les formes et les dimensions des cases du damier, on peut déduire la position de la caméra par rapport au damier (dont une origine sera établie au préalable) grâce au facteur de rétrécissement et l’inclinaison des cases du damier « vu » par la caméra:

damier

Cette méthode est la plus simple mais présente un inconvénient: elle nécessite qu’un damier (dont les caractéristiques sont connues) soit présent sur le modèle à reconstruire. Il se peut donc qu’elle soit inutilisable et qu’il faille donc utiliser la calibration avec damier.

Calibration sans damier

La calibration sans damier n’est pas une méthode implémentée sur la plateforme, cependant voici quelques prérequis si vous souhaitez l’implémenter ou travailler dessus.
L’une des différences fondamentales, avec la calibration avec damier, qui complexifie grandement le processus de calibration, réside dans le fait qu’ici les calculs sont fait entre image 1 et une image 2 contrairement à la calibration avec damier où les calculs étaient réalisés entre l’image et la caméra. Concernant la calibration sans damier, là encore, il existe un grand nombre de méthodes qui peuvent être plus ou moins adaptées en fonction de l’objet ou la scène à reconstruire et des prises de vue des images 2D.
Lorsque aucune des méthodes spécifiques à la banque d’images 2D ne semble vraiment adaptée il est généralement conseiller de se tourner vers les méthodes basées sur la géométrie épipolaire.

Introduisons donc avant quelques notions de géométrie épipolaire:

épipolaire

Sur le schéma ci-dessus:

  • P est le point de l’objet ou la scène auquel on s’intéresse.
  • O et O’ sont respectivement les centres de projection des caméra 1 et 2. Ils forment ce qu’on appelle la ligne de base.
  • e et e’ sont respectivement les épipoles gauche et droit. Concrètement, un épipôle est le centre de projection d’une caméra vue dans le plan image de l’autre caméra, c’est-à-dire qu’ici, e est la projection de O’ vu par l’image gauche, et inversement pour e’.
  • l et l’ sont les droites épipolaires, elles sont formées par l’épipôle et un point de  l’image (respectivement p et p’)

Calcul de la Matrice Fondamentale

Dans un premier temps, nous allons chercher à exprimer à l’aide d’une matrice la transformation qui permet de définir pour chaque point de la première image la droite épipolaire correspondante sur la deuxième, il s’agit d’une corrélation. Dans le cas du schéma ci-dessus on cherche donc la matrice qui nous permettra d’exprimer la droite épipolaire l associée au point p’, à partir des coordonnées de celui-ci.
Cette matrice sera appelée matrice fondamentale et sera calculée à l’aide de la relation suivante:

formule

En règle générale, on utilisera la méthode des moindres carrés pour résoudre cette équation matricielle.

Calcul des épipoles

Pour la suite des calculs nous aurons besoin de connaitre la position relative des épipole. Pour cela on utilisera une autre contrainte épipolaire: en prenant comme origine e, on a:

formule

Calcul des matrices caméra

Finalement, une fois les épipoles déterminés vous pourrez obtenir directement les matrices caméra à l’aide des relations suivantes:

formcam

P étant la matrice caméra de la première caméra et P’ celle de la deuxième caméra.

Attention, ces matrices caméra ne seront pas exactes à 100%. Il sera donc utile de pouvoir quantifier cette erreur et de la corriger.

 

Algorithme de maillage

Avant d’entreprendre la génération du maillage, il faut passer par une méthode de reconstruction. Cette dernière répond aux conditions physiques associées à l’objet : limites, densité et types de surface (convexes/concaves, intérieures/extérieures). En d’autres termes, elle guide la génération du maillage à travers un ensemble de points désorganisés en délimitant les formes.

Il existe différentes méthodes de reconstruction. L’algorithme, que nous avons choisi d’implémenter  (PCL, « Fast triangulation of unordered point cloud »), se base sur une estimation des normales en chaque point. Pour chaque point 3D, l’algorithme estime alors un vecteur normal selon les composantes X, Y, Z qui permettra d’associer entre eux les points les plus logiques pour la formation du maillage. Ainsi, l’algorithme peut caractériser la surface et estimer la forme finale de l’objet.

L’étape de l’estimation des normales réalisée, l’algorithme procède à la recherche des points les plus proches afin de les relier en triangles. Le maillage est alors réalisé et peut être visualisé.

 

3d reconstruction steps

Représentation des différentes étapes du maillage