Abstract
Modern 3D sensors generate high-frequency point clouds that pose significant computational challenges for real-time scene segmentation. This paper introduces PAN-Search (Projected Area Neighborhood Searching), a $k$-nearest neighbor ($k$NN) algorithm that exploits the inherent 2.5D grid structure of depth maps. By utilizing the known projection model of the sensor, PAN-Search achieves constant-time neighbor lookups without the overhead of building traditional 3D data structures like kd-trees. Experimental results on the Middlebury and KITTI datasets demonstrate that PAN-Search provides superior speed and precision compared to industry-standard approximate nearest neighbor libraries, maintaining stable performance regardless of point cloud density.
Introduction
For mobile robots to navigate and interact with their surroundings, they must perform scene segmentation—the process of grouping millions of individual 3D points into meaningful objects. This task relies heavily on spatial clustering, which is computationally dominated by $k$-nearest neighbor ($k$NN) searches.
Traditional sensors like Kinect or LIDAR produce over a million points per second, creating a "data firehose" that overwhelms standard algorithms. Tree-based structures, such as those in the Fast Library for Approximate Nearest Neighbors (FLANN), suffer from significant build overhead and $O(\log n)$ scaling. As sensor resolutions increase, these methods become bottlenecks for real-time robotics applications.
PAN-Search: Exploiting Projection Structure
The core innovation of this work is PAN-Search, which treats the point cloud as a structured 2.5D depth map rather than an unorganized "bag of points." Because the data originates from a camera with a known projection model, points proximal in 3D space are typically proximal in the 2D image grid.
The algorithm initiates a search at a query pixel and expands in a radial spiral pattern. A critical component is the dynamic termination criterion: the algorithm calculates a maximum search radius ($r_{max}$) in the 2D grid based on the 3D distance to the $k$-th closest point found. Once the 2D search area exceeds this radius, geometric constraints guarantee that no closer neighbors exist, allowing the search to terminate early. This approach ensures $O(k)$ complexity, making query times independent of the total number of points ($n$).
Experimental Evaluation
The authors evaluated PAN-Search using the Middlebury 2006 indoor dataset and the KITTI outdoor traffic dataset. These datasets provided a range of resolutions and noise levels to test the algorithm's robustness and scaling.
Key findings include:
- Computational Efficiency: PAN-Search demonstrated a significant speed advantage over FLANN. On 0.5-megapixel KITTI frames, it remained faster for $k$ values up to 20.
- Scaling: While FLANN's query time increased with the number of points, PAN-Search's performance remained flat, proving its suitability for future high-resolution sensors.
- Precision: PAN-Search achieved near-perfect precision (~0.98) on the KITTI dataset, significantly outperforming FLANN's approximate results.
Conclusion
PAN-Search offers a highly efficient alternative for $k$NN-based segmentation by leveraging the structured nature of sensor data. By eliminating tree-building overhead and achieving constant-time searches, it enables real-time processing of dense point clouds. While currently limited to structured 2.5D data, future work aims to incorporate additional modalities like RGB and surface normals to further refine unsupervised segmentation quality.
Summary updated