This paper, presented at ICRA 2018 by researchers from the Oxford Robotics Institute, introduces a more efficient way for robots to autonomously map 3D environments.
TL;DR
The Surface Edge Explorer (SEE) is a "scene-model-free" approach to Next Best View (NBV) planning that uses point cloud density to identify exploration frontiers. It achieves higher surface coverage in significantly less time than traditional voxel-based methods, scaling effectively from small objects to large-scale architecture.
What Problem Does This Paper Address?
To build a high-resolution 3D model of an unknown object or environment, a robot must decide where to point its sensors next—a challenge known as Next Best View (NBV) planning.
Existing solutions generally fall into two camps:
- Volumetric approaches: These divide space into a grid of "voxels." While reliable, they scale poorly; as the scene gets larger or the required resolution higher, the memory and computational cost of ray-tracing through millions of voxels becomes prohibitive.
- Surface-based approaches: These estimate the geometry of the object itself. While they scale better, they often require complex, unintuitive parameter tuning or multiple "passes" (e.g., a low-res scan followed by a high-res scan).
The authors sought a method that provides the high-resolution scaling of surface methods with the "one-pass" simplicity and generality of volumetric methods.
Methods
The core innovation of SEE is representing the scene through measurement density rather than a fixed spatial grid.
- Density-Based Frontier Detection: SEE uses a modified version of the DBSCAN clustering algorithm. It classifies points in the current 3D scan as "core" (surrounded by enough neighbors), "outlier" (isolated), or "frontier" (on the edge between observed and unobserved space).
- Local Geometry Estimation: For every frontier point, the algorithm performs an eigendecomposition (Principal Component Analysis) of its neighborhood. This math reveals the surface normal (which way the surface faces) and the direction of the "gap" that needs to be filled.
- Local View Adjustment: Real-world objects have "self-occlusions" (like the space behind a teapot handle). If a proposed view is blocked or hits a sharp edge, SEE iteratively adjusts the sensor's position and rotation—effectively "peering around the corner"—until the frontier is expanded.
- Global Planning: To keep the robot efficient, the Next Best View is selected to minimize the travel distance from both the robot's starting point and its current position.
Datasets
The authors evaluated SEE in a simulated environment against seven state-of-the-art volumetric NBV metrics (such as Average Entropy and Area Factor). They used:
- Standard CAD Models: The Stanford Armadillo, Bunny, and Dragon, and the Newell Teapot (all scaled to ~1m).
- Large-Scale Model: A 40m-tall, full-scale model of the Radcliffe Camera in Oxford to test scalability.
Key Insights and Ideas
- Scaling with Data, Not Volume: Because SEE relies on the density of points already collected, its computational complexity scales with the number of measurements, not the physical size of the scene. This makes it uniquely suited for large structures like bridges or buildings.
- Intuitive Parameters: Instead of tuning abstract voxel sizes, users define "resolution" and "target density." These are intuitive values that directly correspond to the desired quality of the final 3D map.
- Handling Discontinuities: The "Local View Adjustment" strategy allows the robot to handle complex geometries (edges and corners) dynamically without needing a global, computationally expensive visibility map.
Key Results
- Superior Coverage: On the large-scale Radcliffe Camera model, SEE achieved 99% surface coverage. The best-performing volumetric approach (Average Entropy) only reached 79% in the same number of views.
- Speed: SEE's computational performance was logarithmically better than volumetric approaches. As the complexity of the scene increased, the time required for SEE to plan the next move stayed low, while volumetric methods slowed down significantly.
- Efficiency: SEE achieved these results while moving the sensor roughly the same total distance as competing methods, proving it wasn't just "moving more," but "moving smarter."
Limitations and Future Work
- Finite Scene Assumption: The algorithm currently assumes the scene is finite and requires a predefined boundary to know when to stop discarding points that fall outside the area of interest.
- Simulation vs. Reality: While the simulation included sensor noise, the system has yet to be tested on a physical platform. The authors noted that their next step is deploying SEE on an autonomous aerial vehicle (drone) for real-world infrastructure inspection.
- Surface-Based Comparisons: The paper primarily compares SEE against volumetric methods; the authors noted a lack of publicly available, high-quality implementations of competing surface-based NBV planners for a direct head-to-head.
Summary updated