Lien de la note Hackmd

Introduction

On sait obtenir de l'info en 3D sous la forme d'un nuage de points (sous forme de nuage de points, carte de disparite).

Comment valoriser cette donnee ?

On peut se localiser
Detection d'objets

• Visualisation 3D
• Reconstruction de modele 3D
• Building Information Modeling
• Clustering 3D
• Dimensionnement 3D
• Detection d'objets 3D
• Modele numerique de terrain
• Navigation autonome
• etc

Comment passer d'un nuage de points a une donnee a valeur ajoutee ?

• Analyse 3D
• Segementation
• Recalage

Analyse de Surface et Reconstruction 3D

Segmentation semantique

But:

1. segmenter en temps reel tous les points
2. segmenter toutes les donnees accumulees

Utile pour les vehicules autonomes

Reconstruction 2D

Exemple de problematique en 2D:

Dans la realite, le probleme n'est pas si simple

Extraction de la surface

• Discretisation Octree (1 point par cellule)

• Calcul d'un champ de vecteurs

• Calcul de la fonction indicatrice

• Extraction de l'isosurface

Reconstruction 3D

En 3D, ca donne:

Voxelisation

Differentes methodes de voxelisation

Maillage

Ensemble de sommets connectes

Analyse de surface

Calculs de normales par ACP:

• On cherche le meilleur plan approche dans le voisinage d'un point
  $X_{i0}$
  • Les points du voisinage sont notes
    $X_i$
• Equation d'un plan
  $n^{t}X=d,\Vert n\Vert =1$
• Distance signee d'un point au plan:
  $d(X_i,P)=n^t{X}_i-d$

Resolution

• Methode des moindres carres
• Resolution de l'equation de minimisation pour le plan

Fonction a minimiser: $f(n,d)=\sum_{i=1}^m(ntX_i-d)^2

• 4 parametres:
  $(n,d)$, 1 contrainte:
  $\Vert n\Vert =1$

On pose:

• Barycentre des points
  $G=\frac{1}{m}\sum _{i=1}^m{X}_i$
• Matrice de covariance des points

$$M_{cov}=\frac{1}{m}\sum _{i=1}^m(X_i-G)(X_i-G^{\prime })$$

Le meilleur plan approche est defini par:

• Normale
  $n_{min}$
  • Vecteur propre norme associe a la plus petite valeur propre de
    $M_{cov}$
  • NB: indetermine a un changement de sens pres
• Distance
  $d_{min}$
  • $d_{min}=n^{t}G$

La solution fait appel a l'analyse des directions principales de la matrice de covariance: Analyse en Composantes Principales (ACP)

Segmentation 3D

Definition

Subdiviser (partitionner) le nuage de points 3D en sous-ensembles connexes correspondants a des modeles simples

Methodes de segmentation

Croissance de surface

Principe

• A partir de "surfaces germes" ou "graines" (seed surfaces) dans le nuage de point
• Agregation progressive des points voisins appartenant a la meme surface

Remarque: extension de l'algorithme "croissance de regions" pour les images

Pour chaque point, un calcul de la normale du plan dans un voisinage:

Critere d'agregation:

• Co-normalite:
  $\alpha =\arccos (n_1,n_2)\le {\alpha }_{seuil}$
  • Normales dans le meme sens
• Coplanarite:
  $d=max(|r_{12}\cdot n_1|,|r_{12}\cdot n_2|)\le d_{seuil}$
  • Points sur le meme plan

Clustering

Definition

Regroupement de donnees en paquets homogenes selon des caracteristiques commnunes

DBSCAN

C'est l'un des algorithme de clustering les plus repandus

Principe:

• Choix d'un point graine pour la region
• Identification des voisins du point
• Pour chaque point voisin
  • Si la densite locale de points est suffisante, ajout a la region
  • Sinon, labellisation en tant que bruit
• On continue jusqu'a ne plus pouvoir etendre la region

On peut jouer sur 2 parametres:

• Le rayon de recherche des voisins
• La quantite minimale de voisin ou densite

RANSAC

RANdom SAmple Consensus

Methode de vote sur des echantillons aleatoires de surfaces

• Echantillons calcules a partir du nombre minimal de points necessaires pour definir la surface(quorum)
• Vote: un nombre de points du nuage englobes dans un espace entourant chaque surface
• Le nombre de votes est decide en fonction d'un calcul de probabilites

Tres efficace pour les grandes surfaces en nombre inconnu dans un grand nuage de points

Les surfaces extraites ne sont pas connectees entre elles

Primitives geometriques et quorum de points:

• Droite:
  • Quorum = 2 points non alignes
• Plan:
  • Quorum = 3 points
    $x_i$ non alignes
  • Le plan est defini par:
    • L'un des points, par exemple
      $x_1$
    • Une normale unitaire
      $n$, par exemple definie par:

$$n=\frac{(x_2-x_1)(x_3-x_1)}{\Vert (x_2-x_1)(x_3-x_1)\Vert }$$

Vote:

• Nombre de points compris dans un espace a une certaine distance
  $\delta$ de la surface calculee

Probabilites:

• Hypotheses
  • Plusieurs surfaces possibles, points non bruites
  • $N$ points dans le nuage de points
  • $n$ points appartiennet a la surface recherchee
  • $q$ points pour definir la surface (quorum)
• Probabilites de trouver la surface recherchee:
  • Avec
    $1$ tirage aleatoire:
    $p=(\frac{n}{N}{)}^q$
  • Avec
    $T$ tirages aleatoires
    $p=1-(1-(\frac{n}{N}{)}^q{)}^T$

Nombre de tirages necessaires:

• Nombre de tirage aleatoires
  $T_{min}$ necessaires pour avoir une probabilite
  $p_t$ de trouver une surface d'au moins
  $n_{min}$ points

$$T_{min}=\frac{\log (1-p_t)}{\log (1-(\frac{n_{min}}{N}{)}^q)}$$

• En supposant
  $n_{min}<<N:T_{min}\simeq \log (\frac{1}{1-p_t})(\frac{N}{n_{min}}{)}^q$

Exemple:

Hough 3D

Principe:

• Methode de vote dans l'espace dicretise des parametres
  • Chaque point du nuage genere des votes de surfaces possibles dans l'espace des parametres
  • La cellule qui remporte le plus de votes est retenue comme surface
• Generalisation de la transformee de Hough 2D (image)

Detection de droites

TODO
Probleme

Deep learning

Recalage 3D

Point Set Registration, Point Matching:

• Processus d'alignement de jeux de points TODO

Iterative Closest Point

ICP

Determination de la transformation rigide

$(R,t)$ entre les deux nuages de points

Principe

• Appariement des points du nuage a recaler au point le plus proche dans l'autre nuage (approche de "nearest neighbor")
• Calcul de la transformation
  $(R,t)$ qui minimise la distance entre ces points

Calcul de la transformation

$(R,t)$

Resolution par la methode des moindres carres:

On calcule:

$$\begin{gathered} f(R,t)=\sum _{i=1}^n\Vert p_i-(R\cdot p_i^{\prime }+t){\Vert }^2 \\ f:\{\begin{array}{ll}S{E}^3& \to {\mathbb{R}}^{+}\\ (R,t)& \mapsto f(R,t)\end{array} \end{gathered}$$

On cherche:

$(R,t)$ tel que

$(R,t)=\text{arg}\underset{R,t}{min}f(R,t)$

Solution par decomposition

TODO

Resolution par Singular Value Decomposition (SVD)

• Entree: jeux de points
  $(P,P^{\prime })$
• sortie: Matrice de rotation
  $R$, vecteur translation
  $t$
• Algorithme
  • Determiner les barycentres
    $p_m=\frac{1}{n}\sum _{i=1}^n$ et
    $p_m^{\prime }$
  • Calculer la matrice
    $H$
  • Decomposer
    $H$ en valeurs singulieres
    $\mathrm{\exists }(U,V,\mathrm{\Sigma })$ TODO
  • Calculer
    $R=V{U}^T$ et
    $t=p_m-p_m^{\prime }$

Pseudo code ICP:

Recalage approximatif P'->P
Repeter:
    - Association de donnees P' -> P
    - Calcul de la transformation (R, t)
    - Application de la transformation au nuage de point P'
    - Calcul de la distance entre les nuages
Tant que:
    - Distance normalisee > seuil
    - Et nombre d'iterations < maximum d'iterations

Temps de calcul:

• Appariement en
  $O(n_1,n_2)$, le reste en
  $O(n_1+n_2)$
• Acceptable pour les petits nuages de points, trop lent pour de gros nuages de points
• Necessite de sous-enchatilloner
• Possibilite d'acceleration avec ANN (Approximate Nearest Neighbor):
  $O(n_1\log (n_2))$

Approximate Nearest Neighbor (ANN)

• Principe
  • Pre-calcul d'un kd-tree pour partitionner l'espace
  • Recherche dichotomique avec distance seuil

Variante ICP:

• Metrique point a plan (point to plane)
• Echantillonage: regulier, aleatoire, base sur les normales
• Rejection des outliers
• …