Hough-Transform and Extended RANSAC Algorithms for Automatic Detection of 3D Building Roof Planes from Lidar Data

Airborne laser scanner technique is broadly the most appropriate way to acquire rapidly and with high density 3D data over a city. <br />Once the 3D Lidar data are available, the next task is the automatic data processing, with major aim to construct 3D building models. <br />Among the numerous automatic reconstruction methods, the techniques allowing the detection of 3D building roof planes are of <br />crucial importance. Three main methods arise from the literature: region growing, Hough-transform and Random Sample Consensus <br />(RANSAC) paradigm. Since region growing algorithms are sometimes not very transparent and not homogenously applied, this <br />paper focuses only on the Hough-transform and the RANSAC algorithm. Their principles, their pseudocode - rarely detailed in the <br />related literature - as well as their complete analyses are presented in this paper. An analytic comparison of both algorithms, in terms <br />of processing time and sensitivity to cloud characteristics, shows that despite the limitation encountered in both methods, RANSAC <br />algorithm is still more efficient than the first one. Under other advantages, its processing time is negligible even when the input data <br />size is very large. On the other hand, Hough-transform is very sensitive to the segmentation parameters values. Therefore, RANSAC <br />algorithm has been chosen and extended to exceed its limitations. Its major limitation is that it searches to detect the best <br />mathematical plane among 3D building point cloud even if this plane does not always represent a roof plane. So the proposed <br />extension allows harmonizing the mathematical aspect of the algorithm with the geometry of a roof. At last, it is shown that the <br />extended approach provides very satisfying results, even in the case of very weak point density and for different levels of building <br />complexity. Therefore, once the roof planes are successfully detected, the automatic building modelling can be carried out