A Novel Triangular Descriptor for UAV Laser Loop Closure Detection

In the field of robotics, simultaneous localization and mapping (SLAM) is a cornerstone technology for autonomous navigation, particularly for unmanned aerial vehicles (UAV drones) operating in GPS-denied environments such as urban search and rescue or indoor exploration. For UAV drones, high-precision pose estimation is critical for path planning and obstacle avoidance. However, visual SLAM methods often struggle with challenges like intense lighting variations, repetitive structures, or sparse features. In contrast, laser-based SLAM, utilizing Light Detection and Ranging (LiDAR), provides stable and robust geometric features due to its hardware characteristics, effectively avoiding interference from illumination and texture changes. Nonetheless, designing efficient and robust loop closure detection algorithms for UAV drones remains a significant challenge. UAV drones exhibit six degrees of freedom (6-DOF) motion, requiring algorithms with complete rotation and translation invariance. Additionally, dynamic changes in flight altitude and LiDAR scanning properties lead to highly uneven density distribution in point clouds, necessitating robustness to density variations.

Loop closure detection is a core component of SLAM systems, as it corrects accumulated drift by recognizing when a UAV drone revisits a previously mapped location. This enhances long-term localization and mapping stability. Current LiDAR-based loop closure detection methods can be broadly categorized into global descriptor and local feature matching approaches. Global descriptors, such as M2DP and Scan Context, project point clouds onto 2D planes for encoding, but they lose 3D spatial information and may lack discriminability in similar-structured scenes. Methods like LiDAR Iris use Fourier transforms to generate binary signature images, improving rotation invariance, while Intensity Scan Context incorporates intensity information for faster matching. Another category relies on odometry-based neighborhood search, as seen in LeGO-LOAM and LIO-SAM, but these can fail when cumulative errors are large. Local feature encoding methods, such as BoW3D, use feature points to build bag-of-words models, but retrieval efficiency decreases with larger vocabularies, making them less suitable for resource-constrained UAV drone platforms.

To address these limitations, we propose a novel global triangular descriptor with distance information for LiDAR loop closure detection in UAV drones. Our method does not rely on odometry information, ensuring robustness against 6-DOF motion and point cloud density variations. The overall framework involves key point extraction via adaptive Euclidean clustering, construction of distance vectors based on key point relationships, generation of triangular descriptors by fusing geometric features, and efficient retrieval using a hash table. This descriptor is integrated into a full SLAM framework with factor graph optimization for global pose correction. In this paper, we detail the methodology, present experimental results on public datasets and real-world environments, and discuss the implications for UAV drone navigation.

The key contributions of this work are: (1) an adaptive Euclidean clustering algorithm for key point extraction that handles uneven point cloud density; (2) a 10-dimensional distance vector encoding local geometric structure around key points; (3) a triangular descriptor combining distance vectors and side lengths for rotation and translation invariance; and (4) a hash-based retrieval system for efficient loop closure detection. We validate our approach on the KITTI dataset and in real-world UAV drone experiments, demonstrating significant improvements in localization precision and accuracy, along with effective suppression of pose drift in long-term operations.

Methodology

Our loop closure detection algorithm consists of three main steps: key point extraction, descriptor construction, and loop closure detection. Below, we elaborate on each component, emphasizing the design considerations for UAV drone applications.

Key Point Extraction

For UAV drones, point clouds captured by LiDAR often exhibit density variations due to changing flight altitudes. To extract stable key points, we first identify edge points based on curvature, similar to the LOAM algorithm. The curvature for a point \( p_i \) is computed as:

$$ c_i = \frac{1}{|S|} \sum_{j \in S, j \neq i} \left\| p_j – p_i \right\|_2 $$

where \( S \) represents a set of continuous points on the same scan line symmetrically distributed around point \( i \). Points with curvature exceeding a threshold are classified as edge points. However, some edge points are discrete and unstable, potentially disappearing in subsequent scans. To retain effective edge key points, we cluster these edge points using an adaptive Euclidean clustering algorithm.

Traditional Euclidean clustering uses a fixed distance threshold, which is sensitive to point cloud density. To overcome this, we map point clouds to a 2D distance image, where each pixel stores the depth value of an edge point. For an edge point \( p_A \), we compute its spherical coordinates:

$$ \phi = \arctan2(p_{A,y}, p_{A,x}) $$
$$ \theta = \arctan2\left(\sqrt{p_{A,x}^2 + p_{A,y}^2}, p_{A,z}\right) $$
$$ d = \sqrt{p_{A,x}^2 + p_{A,y}^2 + p_{A,z}^2} $$

where \( \phi \) is the azimuth, \( \theta \) is the polar angle, and \( d \) is the depth. The pixel position \( (i, j) \) in the distance image is determined by:

$$ i = \frac{\phi + \pi}{r_h}, \quad j = \frac{\theta + \pi/2}{r_v} $$

with \( r_h \) and \( r_v \) being the horizontal and vertical resolutions, respectively. For a 64-beam LiDAR, we set \( r_h = 0.2 \) degrees per pixel and \( r_v = 0.4 \) degrees per pixel. Neighboring points in the same cluster correspond to nearest neighbors in the distance image. The adaptive distance threshold \( d_{e1} \) is defined as:

$$ d_{e1} = \delta \sin(\alpha) \| d_{\text{min}} \| $$

where \( \delta \) is a redundancy factor (set to 1.2), \( \alpha \) is the horizontal or vertical resolution, and \( d_{\text{min}} \) is the shorter depth between two edge points. Two edge points are considered in the same cluster if \( d_{e1} > d_{AB} \), where \( d_{AB} \) is the Euclidean distance between them. This adaptive approach allows clustering of distant points without losing effectiveness. The centroid of each cluster is computed as a key point:

$$ C_k = \left( \frac{1}{n} \sum_{i=1}^{n} x_{ki}, \frac{1}{n} \sum_{i=1}^{n} y_{ki}, \frac{1}{n} \sum_{i=1}^{n} z_{ki} \right) $$

where \( C_k \) is the centroid of the \( k \)-th cluster with point set \( \{ p_{k1}, p_{k2}, \dots, p_{kn} \} \).

Descriptor Construction

To build descriptors invariant to UAV drone motion, we first project all key points onto the horizontal plane to mitigate vertical density不均匀性. Then, we generate a 10-dimensional distance vector for each key point by dividing the surrounding 360-degree area into 10 equal扇形 regions. For each扇形 region \( i \) (where \( i = 1, 2, \dots, 10 \)), we compute the average distance from all key points within that region to the圆心 (the key point itself). If no key points exist in a region, the corresponding value is set to 0. The distance vector \( \mathbf{v} \) is formed by sorting these average values in ascending order. This encoding captures local geometric structure around key points.

Next, we construct triangular descriptors using key points. For each key point, we use a KD-Tree to find its 10 nearest neighbors. From these, we select two points to form a triangle with the key point. The triangle must satisfy constraints: side lengths between 5 m and 50 m, and all three sides must be unequal to ensure uniqueness. Additionally, duplicate triangles with the same side length combination are discarded. The descriptor stores the three side lengths sorted in ascending order, denoted as \( L_{12}, L_{23}, L_{13} \), along with the distance vectors \( \mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3 \) of the three vertices. This fusion of distance vectors and geometric information enhances discriminability.

For efficient retrieval, we use a hash table to store descriptors. The hash key is computed from the side lengths using:

$$ \text{Hash}(L) = \text{Mod}\left( \text{Mod}\left( (L_{13} \cdot h + L_{23}) \cdot h, B \right) + L_{12}, B \right) $$

where \( h \) is a large prime number (chosen to minimize collisions) and \( B \) is a maximum value to prevent index overflow. Descriptors with similar side lengths are grouped in the same hash bucket, enabling fast similarity searches.

Loop Closure Detection

Given a current frame point cloud, we extract descriptors as above. For each descriptor \( T_q \) in the current frame, we compute its hash key and retrieve candidate descriptors from the hash table. To assess similarity, we compare the distance vectors of corresponding vertices. The similarity score between a query descriptor \( T_q \) and a candidate \( T_c \) is calculated using cosine similarity:

$$ \text{score}(T_q, T_c) = \frac{1}{3} \sum_{i=1}^{3} \frac{\mathbf{v}_q^i \cdot \mathbf{v}_c^i}{\|\mathbf{v}_q^i\| \cdot \|\mathbf{v}_c^i\|} $$

where \( \mathbf{v}_q^i \) and \( \mathbf{v}_c^i \) are the distance vectors of vertex \( i \) in \( T_q \) and \( T_c \), respectively. If the score exceeds a threshold \( \sigma \) (set empirically), the candidate earns one vote. After processing all descriptors in the current frame, the candidate frame with the highest total votes is selected as a loop closure candidate.

To ensure accuracy, we further validate candidate pairs using the Iterative Closest Point (ICP) algorithm. Let \( \{S\}_q \) and \( \{S\}_c \) be the point sets of the current and candidate frames, respectively. The ICP minimizes the objective function:

$$ \min_{\mathbf{R}_q^c, \mathbf{t}_q^c} f(\mathbf{R}_q^c, \mathbf{t}_q^c) = \frac{1}{n} \sum_{i=1}^{n} \left\| \mathbf{R}_q^c \mathbf{p}_q^i + \mathbf{t}_q^c – \mathbf{p}_c^i \right\|^2 $$

where \( \mathbf{R}_q^c \) and \( \mathbf{t}_q^c \) are the rotation matrix and translation vector from the current frame to the candidate frame. If ICP converges successfully, the loop closure is confirmed. Finally, we integrate the loop closure constraint into a factor graph using the GTSAM library for global pose optimization, correcting accumulated drift in the UAV drone’s trajectory.

Experimental Evaluation

We evaluate our algorithm on the public KITTI dataset and in real-world environments to demonstrate its effectiveness for UAV drone applications. All experiments were conducted on a system with an Intel i7 processor and 16GB RAM, simulating onboard computation for UAV drones.

Dataset and Metrics

We use sequences 00, 02, 05, and 08 from the KITTI dataset, which contain urban and highway scenes with loop closures. For real-world testing, we deploy our algorithm on a UAV drone platform equipped with a Livox Mid360 LiDAR and a Jetson Orin NX onboard computer, flying in indoor multi-floor corridor environments. Since ground truth poses are unavailable indoors, we measure the distance error between start and end points when the UAV drone returns to the origin.

Evaluation metrics include precision, recall, and F1 score, defined as:

$$ \text{Precision} (P) = \frac{\text{True Positives}}{\text{True Positives} + \text{False Positives}} $$
$$ \text{Recall} (R) = \frac{\text{True Positives}}{\text{True Positives} + \text{False Negatives}} $$
$$ F1 = 2 \times \frac{P \times R}{P + R} $$

A true loop closure pair is defined as two frames within 3 m in distance and separated by at least 30 seconds in time. We compare our method against three state-of-the-art algorithms: Scan Context, BoW3D, and LiDAR Iris. For real-world comparisons, we use the Euclidean distance-based loop detection in LIO-SAM as a baseline.

Results on KITTI Dataset

Precision-recall curves for sequences 00, 02, 05, and 08 are shown below. Our algorithm maintains high precision even at recall rates above 50%, indicating low false positives. In sequence 08, which contains reverse loops, our method outperforms others significantly, showcasing its rotation invariance—a critical feature for UAV drones with 6-DOF motion.

Method KITTI00 KITTI02 KITTI05 KITTI08
Scan Context 0.930 0.813 0.911 0.585
LiDAR Iris 0.963 0.869 0.957 0.661
BoW3D 0.820 0.268 0.737 0.674
Our Method 0.973 0.901 0.949 0.799

The table above lists maximum F1 scores across sequences. Our algorithm achieves the highest F1 scores on sequences 00, 02, and 08, demonstrating superior overall performance. On sequence 05, LiDAR Iris slightly outperforms ours, but our method remains competitive. The low scores of BoW3D on sequence 02 highlight its limitations in large-scale scenes, while our hash-based retrieval ensures efficiency.

Real-World UAV Drone Experiments

In indoor corridor environments, our algorithm effectively detects loop closures even after long trajectories through degenerate spaces. We compare the mapping results with LIO-SAM’s Euclidean distance-based loop detection. With our method, the UAV drone accurately closes loops and corrects drift, whereas LIO-SAM fails due to accumulated errors, leading to severe map distortion. The distance errors at the end point (relative to the start) are summarized below:

Method x-error (m) y-error (m) z-error (m) Total Error (m)
Our Method -0.047 -0.023 0.008 0.053
Euclidean Distance -0.704 0.429 0.015 0.825

Our algorithm reduces the total error by an order of magnitude, confirming its practicality for UAV drone navigation in challenging environments.

Ablation Study on Vector Dimension

We investigate the impact of distance vector dimension on performance and runtime. Using KITTI sequences, we vary the dimension from 5 to 25 and measure F1 scores and average detection time per frame. Results indicate that as dimension increases, both F1 score and detection time rise. Beyond 10 dimensions, F1 scores plateau while detection time continues to increase. Thus, we select 10 dimensions to balance accuracy and efficiency for real-time UAV drone operations.

Dimension Avg F1 Score Avg Detection Time (ms)
5 0.78 15
10 0.91 22
15 0.92 35
20 0.92 48
25 0.92 60

This ablation study underscores the importance of parameter tuning for onboard computation on UAV drones.

Discussion

Our proposed triangular descriptor with distance information offers several advantages for UAV drone laser SLAM. First, the adaptive Euclidean clustering handles point cloud density variations caused by altitude changes, a common issue for UAV drones. Second, the distance vector encoding captures local geometry without projection, preserving 3D information. Third, the triangular descriptor combines distance vectors and side lengths, ensuring rotation and translation invariance—essential for UAV drones with 6-DOF motion. The hash-based retrieval enables fast loop closure detection, meeting real-time requirements for UAV drone navigation.

Compared to global descriptors like Scan Context, our method avoids information loss from 2D projections, improving discriminability in similar scenes. Against local feature methods like BoW3D, our descriptor retrieval is more efficient due to hashing, avoiding vocabulary scalability issues. The integration with ICP validation and factor graph optimization further enhances reliability, effectively suppressing pose drift in long-term UAV drone missions.

Limitations include sensitivity to extreme point sparsity in large open areas, where key point extraction may become unstable. Future work could incorporate inertial measurement unit (IMU) data to augment descriptor robustness or explore deep learning-based features for improved generalization across diverse environments for UAV drones.

Conclusion

In this paper, we present a novel global triangular descriptor with distance information for LiDAR loop closure detection in UAV drone SLAM systems. The method extracts key points via adaptive Euclidean clustering, constructs distance vectors to encode local geometry, and generates triangular descriptors for robust matching. Experimental results on the KITTI dataset and real-world UAV drone flights demonstrate superior performance in precision, recall, and F1 score compared to state-of-the-art methods. Our algorithm effectively corrects accumulated drift, enhancing long-term localization and mapping stability for UAV drones operating in GPS-denied environments. Future directions include optimizing feature extraction for sparse point clouds and integrating multi-sensor fusion for even greater robustness in complex scenarios for UAV drones.

Scroll to Top