SY27 - Machines Intelligentes

Perception LiDAR

Rémy Huet, Philippe Xu, Vincent Brebion

Université de technologie de Compiègne

2023-10-11

Principe de fonctionnement

Télémétrie

Déf (Larousse): Mesure de distance obtenue par des procédés acoustiques, optiques ou radioélectriques.

• Acoustique : Sonar
• Radioélectrique : RADAR
• Optique : LiDAR

Télémétrie Time Of Flight

Principe de fonctionnement :

\[ d = \frac{c \cdot \Delta t}{2} \]

Avec

• \(c\) vitesse de la lumière
• \(\Delta t\) temps de vol (AR)

Limité par la précision de l’horloge.

Faire le calcul de la limitation.

c = 3x10^8 Précision à 1.5cm

On obtient \(\Delta t = \frac{2d}{c}\) ce qui donne \(10^{-10}\) soit 10GHz

Télémétrie Phase Shift

Emission constante avec modulation de puissance.

Principe de fonctionnement :

\[ s(t) = \sin(2\pi F_m t) \]

\[ d = \frac{c \cdot \Delta \phi}{4 \pi F_m} \]

Peut permettre une horloge moins puissante. Ex fréquence Velodyne : 905nm

\(\lambda = \frac{c}{f}\) soit une fréquence de 300THz

LiDAR 2D

Figure 1: Principe de fonctionnement d’un LiDAR 2D

LiDAR 3D

Démo

Système de coordonnées

Figure 2: Système de coordonnées sphériques

Avantages et inconvénients

Avantages

• Mesure de distance
• Emmet sa propre lumière
• Vision à 360°

Inconvénients

• Données éparses
• Fréquence d’acquisition
• Coût

Applications

Archéologie

Figure 3: https://www.nationalgeographic.com/history/article/maya-laser-lidar-guatemala-pacunam

Applications

Cartographie urbaine

Figure 4: Cartographie LIDAR

Applications

Robotique mobile

Figure 5: Aspirateur robot équipé d’un capteur LiDAR

Applications

Véhicule autonome

Figure 6: Stanley, DARPA Grand Challenge 2005

Applications

« Radar »

Figure 7: Certains « radars » sont en fait des LiDARs

Traitements de données LiDAR

Correction de mouvement

Problématique

Figure 8: Déplacement d’un LiDAR rotatif

Correction de mouvement

Correction

Déplacement pendant \(\Delta t\)

\[ \begin{pmatrix} x_s \\ y_s \\ \theta_s \end{pmatrix} = \begin{pmatrix} \Delta t \cdot v \cdot \cos(\Delta t \cdot \omega) \\ \Delta t \cdot v \cdot \sin(\Delta t \cdot \omega) \\ \Delta t \cdot \omega \end{pmatrix} \]

Les coordonnées \(\left(x_n, y_n, z_n\right)^T\) d’un point tiré au temps \(t + \Delta t\) deviennent alors

\[ \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} \cos\theta_s & \sin\theta_s & 0 & x_s \\ -\sin\theta_s & \cos\theta_s & 0 & y_s \\ 0 & 0 & 1 & 0 \\ \end{pmatrix} \cdot \begin{pmatrix} x_n \\ y_n \\ z_n \\ 1 \end{pmatrix} \]

Seuillage par intensité

• Les capteurs LiDAR renvoient souvent une valeur d’intensité correspondant à chaque point.
• Dépend de si la surface réfléchit ou non la lumière.

Figure 9: Nuage de points avec intensités

Filtrage de sol

Principe : séparer les points appartenant au sol, et ceux représentant des obstacles. Approches par modèle ou géométriques.

Figure 10: Principe du filtrage de sol

Filtrage de sol

Principal Component Analysis (PCA)

Ensemble de points \[ X = \begin{pmatrix} x_0 & x_1 & \dots & x_N \\ y_0 & y_1 & \dots & y_N \end{pmatrix} \]

de moyenne

\[ \bar{X} = \begin{pmatrix} \bar{x} \\ \bar{y} \end{pmatrix} \]

Figure 11: Jeu de données

Filtrage de sol

PCA - Matrice de Covariance

La matrice de covariance du nuage est :

\[ Cov = \frac{ \left(X - \bar{X}\right) \cdot \left( X - \bar{X} \right)^T }{ N } \]

Figure 12: Covariance du nuage de points

Filtrage de sol

PCA - Valeurs et vecteurs propres

Décomposition de la matrice de covariance : valeurs propres et vecteurs propres.

\[ Cov = Q \cdot \Gamma \cdot Q^{-1} \]

\[ Q = \begin{pmatrix} \color{red}{v_1^x} & \color{green}{v_2^x} \\ \color{red}{v_1^y} & \color{green}{v_2^y} \end{pmatrix} \]

\[ \Gamma = \begin{pmatrix} \color{red}{\sigma_1^2} & 0 \\ 0 & \color{green}{\sigma_2^2} \end{pmatrix} \]

Figure 13: Vecteurs et valeurs propres de la matrice de covariance

Filtrage de sol

PCA - Filtrage

On peut filtrer les points proches du sol grâce à leur distance au modèle :

\[ \left( X_i - X \right)^T \cdot \begin{pmatrix} \color{green}{v_2^x} \\ \color{green}{v_2^y} \end{pmatrix} \in \left[ -\color{green}{\sigma_2}; +\color{green}{\sigma_2} \right] \]

Figure 14: Vecteurs et valeurs propres de la matrice de covariance

Filtrage de sol

PCA - Conclusion

Avantages :

• Rapide
• Permet de trouver l’orientation d’un nuage de points quelconque

Inconvénients :

• Peu robuste (sensible aux outliers)

Figure 15: Exemple de PCA

Filtrage de sol

Random Sample Consensus (RANSAC)

Principe :

1. Sélection aléatoire de points candidats
2. Estimation d’un modèle
3. Vérification de la validité du modèle
4. Mémoriser si mieux que l’ancien

Filtrage de sol

RANSAC

for i = 1 to k do

end for

Figure 16: RANSAC - PointCloud

Filtrage de sol

RANSAC - Sélection aléatoire

for i = 1 to k do
    i_model = rand_id(n)
    inliers = P[i_model]
end for

Figure 17: RANSAC - Sélection aléatoire

Filtrage de sol

RANSAC - Estimation de modèle

for i = 1 to k do
    i_model = rand_id(n)
    inliers = P[i_model]
    model = fit(inliers)
end for

Figure 18: RANSAC - Sélection aléatoire

Filtrage de sol

RANSAC - Consensus

for i = 1 to k do
    i_model = rand_id(n)
    inliers = P[i_model]
    model = fit(inliers)
    for p in P \ P[i_model]
        if p fits model then
            inliers <- p
        end if
    end for
end for

Figure 19: RANSAC - Consensus

Filtrage de sol

RANSAC - Re-fit model

for i = 1 to k do
    i_model = rand_id(n)
    inliers = P[i_model]
    model = fit(inliers)
    for p in P \ P[i_model]
        if p fits model then
            inliers <- p
        end if
    end for
    if size(inliers) > d then
        model = fit(inliers)
    end if
end for

Figure 20: RANSAC - Re-fit model

Filtrage de sol

RANSAC - Sélection du meilleur modèle

for i = 1 to k do
    i_model = rand_id(n)
    inliers = P[i_model]
    model = fit(inliers)
    for p in P \ P[i_model]
        if p fits model then
            inliers <- p
        end if
    end for
    if size(inliers) > d then
        model = fit(inliers)
        model_err = err(model, inliers)
        if model_err < best_err then
            best_model = model
            best_err = model_err
        end if
    end if
end for

Figure 21: RANSAC - Sélection du meilleur modèle

Filtrage de sol

RANSAC - Conclusion

Avantages:

• Robuste aux outliers
• Applicable à tout problème modélisable

Inconvénients:

• Plus grande charge calculatoire
• Résultat aléatoire et convergence non garantie

Figure 22: RANSAC - Sélection du meilleur modèle

Filtrage de sol

Approche géométrique

Figure 23: Filtrage de sol par approche géométrique

Clustering

Clustering euclidien

Principe : Sélection des voisins par distance.

C = [], Q=[]
for p in P do
    Q <- p
    for p in Q do
        Pi = {pi in P t.q. ||p - pi|| < d}
        for pi in Pi do
            if pi not in Q then
                Q <- pi
            end if
        end for
    end for
    P <- P \ Q
    C <- Q, Q = []
end for

Clustering

Clustering euclidien conditionnel

Principe : Sélection des voisins par distance.

C = [], Q=[]
for p in P do
    Q <- p
    for p in Q do
        Pi = {pi in P t.q. ||p - pi|| < d and cond(p, pi)}
        for pi in Pi do
            if pi not in Q then
                Q <- pi
            end if
        end for
    end for
    P <- P \ Q
    C <- Q, Q = []
end for

Segmentation sémantique

Principe : associer une classe parmi un ensemble prédéfini à chaque point du nuage. Approches Deep Learning.

Figure 24: Segmentation sémantique d’un nuage de points