---
title: "VPOA: Analyse de l'environnement 3D"
date: 2021-11-04 09:00
categories: [Image S9, VPOA]
tags: [Image, S9, VPOA]
math: true
---
Lien de la [note Hackmd](https://hackmd.io/@lemasymasa/rkmnVzWvt)

# 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


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

:::success
Utile pour les vehicules autonomes
:::

## Reconstruction 2D

Exemple de problematique en 2D:


:::warning
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

:::success

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^tX=d, \Vert n\Vert =1$
- Distance signee d'un point au plan: $d(X_i, P) = n^tX_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(n^tX_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}^mX_i$
- Matrice de covariance des points

$$
M_{cov} = \frac{1}{m}\sum_{i=1}^m(X_i-G)(X_i-G')
$$

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^tG$

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

# Segmentation 3D

:::info
**Definition**

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


:::

## Methodes de segmentation


## Croissance de surface

:::info
**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(\vert r_{12}\cdot n_1\vert, \vert r_{12}\cdot n_2\vert) \le d_{seuil}$
- Points sur le meme plan


## Clustering

:::info
**Definition**

Regroupement de donnees en paquets homogenes selon des caracteristiques commnunes


:::

### DBSCAN

:::info
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

:::info
**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

:::success
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}\lt\lt 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

:::info
**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:

$$
f(R,t) = \sum_{i=1}^n\Vert p_i-(R\cdot p_i'+t)\Vert^2\\
f:\begin{cases}
SE^3&\to \mathbb R^+\\
(R,t)&\mapsto f(R,t)
\end{cases}
$$

On cherche: $(R,t)$ tel que $(R, t)=\text{arg}\min_{R,t}f(R,t)$

Solution par decomposition

TODO

Resolution par Singular Value Decomposition (SVD)
- Entree: jeux de points $(P,P')$
- sortie: Matrice de rotation $R$, vecteur translation $t$
- Algorithme
- Determiner les barycentres $p_m=\frac{1}{n}\sum_{i=1}^n$ et $p_m'$
- Calculer la matrice $H$
- Decomposer $H$ en valeurs singulieres $\exists(U, V, \Sigma)$ TODO
- Calculer $R=VU^T$ et $t=p_m-p_m'$

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
- ...