Efficient Grid‐Based Clustering and Concave Hull Extraction for Unstructured Point Clouds

ABSTRACT This paper presents a situational awareness technique for unstructured point clouds collected from ranging sensors, called Grid‐Based Clustering and Concave Hull Extraction (GB‐CACHE), which is shown to be suitable for real‐time implementation. GB‐CACHE can efficiently segment unstructured point clouds and extract concave hulls by sub‐sampling these point clouds to a structured grid. The technique is designed for uncrewed systems that perceive objects on a flat surface, such as the ground plane, water surface, or sea bed. In addition to segmentation and hull extraction, the technique is designed for the optional integration of point filtering, object classification, mapping, and object tracking processes. GB‐CACHE has been applied to four separate uncrewed case studies covering three different domains (surface, aerial, underwater), and using three different sensing modalities (LiDAR, radar, sonar). GB‐CACHE is shown to handle nearly 1 million points and 200–1000 objects at rates of 5–20 Hz on low to mid‐grade computing solutions with object resolutions of 5–10 cm. Furthermore, GB‐CACHE has a lower computational complexity for clustering and concave hull extraction than traditional approaches (e.g., DBSCAN and alpha shapes).