L'algorithme présenté dans le document est un algorithme de SLAM (Simultaneous
Localization and Mapping) basé sur l'extraction de segments de ligne à partir de données
laser en 2D.
1. Objectif de l'algorithme
L'algorithme vise à extraire des segments de ligne dans des données laser 2D pour :
Faciliter la localisation et la cartographie simultanées (SLAM).
Fournir une représentation simplifiée et structurée de l'environnement, utile pour les
robots dans des environnements intérieurs semi-structurés (bureaux, couloirs, etc.).
Il se base sur une technique appelée Seeded Region Growing, empruntée au traitement
d'image.
2. Étapes principales de l'algorithme
a. Détection de "seed-segments"
But : Identifier les segments initiaux qui serviront de base pour extraire des lignes
complètes.
Les points laser successifs sont ajustés à une droite en utilisant une méthode des
moindres carrés orthogonaux.
Les critères pour qu'un segment soit un "seed-segment" :
1. La distance entre chaque point et la droite ajustée doit être inférieure à un seuil.
2. La distance entre deux points successifs dans le segment doit respecter une
limite (pour éviter les "breakpoints").
b. Croissance régionale (Region Growing)
But : Étendre les seed-segments en segments de ligne complets.
Les points voisins d'un segment initial sont ajoutés à la ligne s'ils respectent les
critères de distance par rapport à la droite.
Chaque fois qu'un nouveau point est ajouté, la ligne est réajustée en temps réel.
c. Gestion des régions qui se chevauchent
Lorsqu'il y a un chevauchement entre deux segments adjacents :
1. S'ils sont colinéaires : fusion des deux segments en une seule ligne ajustée.
2. S'ils ne sont pas colinéaires : les points sont attribués au segment le plus
proche.
d. Génération des points d'extrémité
Une fois les segments complets, leurs points d'extrémité sont calculés.
Les points d'extrémité sont dérivés des intersections entre la droite ajustée et les lignes
perpendiculaires passant par les points les plus éloignés.
3. Améliorations par rapport aux algorithmes existants
Contrairement à Split-and-Merge, l'algorithme n'est pas récursif, ce qui améliore
l'efficacité et la stabilité.
Il réduit les erreurs aux extrémités des segments et évite les problèmes de
"breakpoints".
La précision et la complétude des segments détectés sont supérieures.
4. Résultats expérimentaux
Des tests ont été réalisés dans deux environnements (un couloir et un laboratoire) en
utilisant un capteur laser UTM-30LX.
Les performances de l'algorithme (efficacité, précision, et correction) sont comparées
à celles de Split-and-Merge.
Résultats :
o Meilleure précision des points d'extrémité.
o Temps de calcul plus court (grâce à l'élimination des itérations inutiles).
5. Applications
Localisation et navigation autonome des robots.
Reconnaissance des lieux et détection de boucles ("loop closure").
Simplification des modèles de cartographie pour une meilleure compréhension de
l'environnement.
1.1. Détection des "Seed Segments"
Cette étape identifie les segments de points laser qui pourraient correspondre à une ligne.
1. Méthode des moindres carrés orthogonaux :
o Ajuste une droite ax + by + c = 0à un petit groupe de points successifs.
o Minimise la distance perpendiculaire de chaque point à la droite.
2. Critères de validation pour un seed segment :
o La distance entre chaque point et la ligne ajustée est inférieure à un seuil donné
(ϵ\epsilonϵ).
o La distance entre les points successifs est inférieure à un seuil (d) pour éviter
les discontinuités.
1.2. Croissance régionale
À partir d'un seed segment valide :
1. Les points adjacents sont ajoutés à la ligne si leur distance perpendiculaire à la ligne
ajustée est inférieure à ϵ\epsilonϵ.
2. Après chaque ajout, la ligne est recalculée en réajustant tous les points du segment
actuel.
3. Le processus continue jusqu'à ce qu'aucun point supplémentaire ne puisse être ajouté.
1.3. Gestion des chevauchements
Lorsqu'un segment détecté chevauche un autre :
Colinéarité : Si les deux segments sont colinéaires, fusionnez-les en une seule ligne
ajustée.
Non-colinéarité : Les points appartenant aux segments sont redistribués en fonction
de leur proximité avec chaque ligne.
1.4. Génération des points d'extrémité
Les points d'extrémité de chaque segment sont calculés en trouvant l'intersection entre
la droite ajustée et des lignes perpendiculaires passant par les points extrêmes.
1.5. Critères d'arrêt
Un segment valide doit contenir un nombre minimum de points (PminP_{\
text{min}}Pmin).
La longueur du segment doit être supérieure à une longueur minimale (LminL_{\
text{min}}Lmin).
Pseudo de lalgo
Input: Laser points {P1, P2, ..., PN}, distance threshold d, line fitting threshold ε
Output: Line segments {L1, L2, ..., LM}
# Étape 1 : Détection des Seed Segments
function detect_seed_segments(points, ε, d):
seed_segments = []
for each subset of points S (of size S_num):
line = fit_line(S) # Ajuste une droite avec moindres carrés orthogonaux
if all(point_to_line_distance(point, line) < ε for point in S) and
all(distance_between_points(S[i], S[i+1]) < d for i in range(len(S)-1)):
seed_segments.append(S)
return seed_segments
# Étape 2 : Croissance régionale
function region_growing(seed_segments, points, ε):
line_segments = []
for seed in seed_segments:
segment = seed
while True:
new_point = find_closest_point_to_line(segment, points, ε)
if new_point is None:
break
[Link](new_point)
segment = refit_line(segment) # Réajuste la ligne
line_segments.append(segment)
return line_segments
# Étape 3 : Gestion des chevauchements
function handle_overlap(segments):
for i, seg1 in enumerate(segments):
for j, seg2 in enumerate(segments):
if i != j and overlap(seg1, seg2):
if is_collinear(seg1, seg2):
merged = merge_segments(seg1, seg2)
segments[i] = merged
[Link](j)
else:
redistribute_points(seg1, seg2)
return segments
# Étape 4 : Génération des points d'extrémité
function generate_endpoints(segments):
for segment in segments:
endpoints = calculate_endpoints(segment)
[Link] = endpoints
return segments
# Étape principale
function line_segment_extraction(points, ε, d, P_min, L_min):
seed_segments = detect_seed_segments(points, ε, d)
line_segments = region_growing(seed_segments, points, ε)
line_segments = handle_overlap(line_segments)
line_segments = filter_segments(line_segments, P_min, L_min)
line_segments = generate_endpoints(line_segments)
Points-clés de l'algorithme
1. Performance : Cet algorithme est plus rapide que les approches traditionnelles
comme Split-and-Merge grâce à l'utilisation de la croissance régionale.
2. Précision : L'ajustement en temps réel de la ligne améliore la précision, en particulier
aux extrémités des segments.
3. Robustesse : Les segments détectés sont plus complets et fiables, ce qui est crucial
pour le SLAM dans des environnements réels.