RANSAC algorithm and elements of graph theory for automatic plane detection in 3D point clouds

Martyna Poreba (1, 2) , François Goulette (1)

1 CAOR - Centre de Robotique
2 Faculty of Mining Surveying and Environmental Engineering

This paper studies techniques of point cloud segmentation such as fully automatic plane detection. Proposed method is based on RANSAC algorithm providing an iterative plane modelling in point cloud affected by considerable noise. The algorithm is implemented sequentially, therefore each successive plane represented by the largest number of points is separated. Despite all advantages of RANSAC, it sometimes gives erroneous results. The algorithm looks for the best plane without taking into account the particularity of the object. Consequently, RANSAC may combine points belonging to different objects into one single plane. Hence, RANSAC algorithm is optimized by analysing the adjacency relationships of neighbouring points for each plane. The approach based on graph theory is thus proposed, where the point cloud is treated as undirected graph for which connected components are extracted. Introduced method consists of three main steps: identification of k-nearest neighbours for each point of detected plane, construction of adjacency list and finally connected component labelling.

Mots clés: point cloud; segmentation; RANSAC; graph; k-nearest neighbour algorithm; labelling; connected component

Domaines: Automatique / Robotique

Martyna Poreba, François Goulette. RANSAC algorithm and elements of graph theory for automatic plane detection in 3D point clouds. Symposium de PTFiT (Polish Society for Photogrammetry and Remote Sensing), Sep 2012, Poland. pp.301-310. ⟨hal-00846335⟩