Detection and Tracking of Small Objects in Sparse 3D Laser Range Data

Jan Razlaw, Jan Quenzel, Sven Behnke

TL;DR

This paper presents a computationally efficient pipeline for detecting and tracking small dynamic objects (like humans) using sparse LiDAR data on hardware-constrained platforms like Micro Aerial Vehicles (MAVs). By leveraging a novel width-based segmentation approach using dual median filters, the authors achieve real-time performance on a single CPU core while maintaining tracking accuracy comparable to more complex models.

What Problem Does This Paper Address?

Autonomous robots, particularly MAVs, need to perceive and predict the movement of dynamic objects to navigate safely. However, MAVs face a "double bind": they have very limited lifting capacity (meaning they must use lightweight, low-resolution sensors) and limited onboard computational power.

Standard 3D LiDAR sensors used on MAVs, such as the Velodyne VLP-16, produce "sparse" point clouds—only 16 scan rings. At a distance, a human might be represented by only a handful of points, making traditional shape-based recognition extremely difficult. Furthermore, many state-of-the-art tracking algorithms require powerful GPUs that a small drone simply cannot carry. The authors aim to bridge this gap with an algorithm that is both robust to sparse data and efficient enough to run on a standard mobile CPU.

Methods

The authors propose a multi-stage pipeline designed to exploit the inherent grid-like structure of organized LiDAR scans:

  1. Segmentation via Dual Median Filters: Instead of using a complex neural network, the team uses two median filters with different kernel sizes applied to the distance readings of the scan rings. A "noise filter" (small kernel) removes tiny outliers, while a "background filter" (larger kernel) identifies the general environment. If the two filters return significantly different results for a point, that point is classified as a foreground object. This effectively isolates objects based on their width, which is a more reliable feature than height in sparse data.
  2. Region Growing Clustering (RGC): Segmented points are grouped into clusters. The authors modified standard RGC to handle sparsity by checking Euclidean distances between neighbors, preventing the algorithm from accidentally merging two people walking close to each other.
  3. Multi-Object Tracking (MOT): The system maintains "object hypotheses" using Kalman filters with a constant velocity model. To match new detections to existing tracks, they use the Hungarian method with a cost matrix based on the Bhattacharyya distance.
  4. Temporal Feedback: Interestingly, the tracker provides feedback to the detector. If a track already exists, the detector "relaxes" its constraints (e.g., allowing for smaller or wider clusters) to avoid losing a track due to a momentary sensor occlusion or sparse return.

Datasets

The approach was evaluated on three distinct types of data:

  • InLiDa (Indoor LiDAR Dataset): A real-world dataset of humans and robots moving in corridors and halls, hand-labeled at the point level.
  • Simulated Data: Created using Gazebo and a VLP-16 simulator. This included diverse outdoor environments (empty fields, industrial sites, and parks) with up to 50 dynamic persons to test the limits of the clustering and tracking.
  • Real-World MAV Data: Recorded by the authors using a DJI Matrice 600 equipped with a VLP-16 flying in a courtyard in Bonn, Germany.

Key Insights and Ideas

  • Width over Height: In sparse 16-beam data, an object might easily fall between scan rings, making height a volatile metric. Width, measured along the horizontal scan line, is much more consistent and serves as the primary feature for their segmentation.
  • Exploiting Data Structure: By treating the LiDAR data as a 2D grid (16 rings x n horizontal points) rather than an unorganized 3D point cloud, the algorithms (especially median filtering and clustering) become significantly faster.
  • Handling "Invalid" Points: The authors found that treating "out of range" or "no return" points (like the sky) as a fixed maximum distance allowed the median filters to continue working at the edges of objects, improving segmentation at high altitudes.
  • Static vs. Dynamic Classification: Every track starts as "static." It is only promoted to "dynamic" once its bounding box moves enough to no longer intersect with its starting position. This helps filter out "ghost" tracks caused by sensor noise on stationary objects.

Key Results

  • Real-Time Performance: The entire pipeline (segmentation, detection, and tracking) runs in under 100ms per scan on a single core of an Intel Core i7-6770HQ, making it viable for real-time flight.
  • Accuracy: On the InLiDa dataset, the method achieved a Multi-Object Tracking Accuracy (MOTA) of 0.562, significantly outperforming the baseline "InLiDa Tracking" approach (-0.213) which struggled with the robot/human distinction.
  • Mapping Application: The authors demonstrated a practical application where dynamic objects are filtered out of the point cloud in real-time, allowing for the generation of clean "static-only" maps of the environment even in crowded areas.

Limitations and Future Work

  • Erratic Motion: The Kalman filter uses a constant velocity model, which struggles to track humans making sudden, sharp turns or complex movements.
  • Occlusion Sensitivity: While the system can maintain tracks through short occlusions, the authors note that incorporating explicit occlusion reasoning (e.g., "I expect the person to be behind this pillar") would make the tracker more robust.
  • Bounding Box Volatility: During partial occlusions, the apparent size of an object's bounding box changes. The system sometimes interprets this change in shape as actual movement, leading to false dynamic classifications.
  • Computational Scaling: While efficient, the segmentation time still scales with the "target width" parameter; tracking very wide objects in close proximity would increase the computational load.

Summary updated

Abstract

Detection and tracking of dynamic objects is a key feature for autonomous behavior in a continuously changing environment. With the increasing popularity and capability of micro aerial vehicles (MAVs) efficient algorithms have to be utilized to enable multi object tracking on limited hardware and data provided by lightweight sensors. We present a novel segmentation approach based on a combination of median filters and an efficient pipeline for detection and tracking of small objects within sparse point clouds generated by a Velodyne VLP-16 sensor. We achieve real-time performance on a single core of our MAV hardware by exploiting the inherent structure of the data. Our approach is evaluated on simulated and real scans of in- and outdoor environments, obtaining results comparable to the state of the art. Additionally, we provide an application for filtering the dynamic and mapping the static part of the data, generating further insights into the performance of the pipeline on unlabeled data.
BibTeX
@inproceedings{razlaw2019detection,
  author = {Jan Razlaw and Jan Quenzel and Sven Behnke},
  title = {{Detection and Tracking of Small Objects in Sparse 3D Laser Range Data}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2019},
  url = {https://openreview.net/forum?id=GNq0hxO5ROa},
}

Loading related content...

Figure