Reconstruction of interior walls from point cloud data with min-hashed J-linkage

with L. Magri and E. Maset

Overview

Given in input a scanned point cloud of an interior environment, the aim is to automatically reconstruct its primary facility surfaces - such as floors, walls, and ceilings. This is an essential step and a preparatory phase common to many scan2bim applications. In practice, this problem translates in the robust extraction of multiple geometric structures consisting of lines or planes - from a 3D point cloud or a collection of projected 2D points respectively.

Our solution builds on and improves the efficiency of J-Linkage: we propose to use an efficient min-hash scheme to approximate the Jaccard distances in order to speed up the computation and be capable to tackle large dataset.

minhash
The main idea is to approximate the Jaccard distance between preference set, as the hamming distance between min-hash signatures. Min-Hash signatures collect the minimum of preference sets over uniform random permutations.

Wall reconstruction

The proposed indoor modeling method consists of the following steps. At first we project the 3D point cloud on a 2D plane corresponding to the plane floor, which as been previously detected. 2D wall samples are identified, then we use our min-hashed J-linkage to robustly recover the dominant lines. The preferences of points take into consideration information on their orientations. The partition of the plane induced by the retrieved lines is organised in a cell-complex, and exploited to to perform a simple topological analysis to segment the main room of the building and reject spurious wall segments.

minhash

Code

A MATLAB implementation of min-hashed J-Linkage is available: demo code

Reference papers

  1. L. Magri, A. Fusiello. Reconstruction of interior walls from point cloud data with min-hashed J-linkage. 3DV, 2018. (PDF, Poster)
  2. Maset, E.; Magri, L. and Fusiello, A. Improving Automatic Reconstruction of Interior Walls from Point Cloud Data. In Proceedings of the ISPRS Workshop Indoor 3D, pages 849-855, ISPRS - International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences XLII-2/W13, 2019. (PDF)