Speak the Same Language: Global LiDAR Registration on BIM Using Pose Hough Transform

BIM serves as a digital representation of buildings and other physical assets in the architectural, engineering, and construction (AEC) industry. BIM generally encompasses comprehensive 3D spatial information, making it suitable for aligning robotic sensing data with the BIM model. This alignment process can effectively reveal deviations between the as-built and as-designed states, thereby benefiting the AEC industry. Conversely, BIM could also serve as a spatial map that facilitates robot localization and planning, eliminating the need for traditional mapping approaches. By leveraging the information provided by BIM, robots can navigate and operate within the environment without relying on explicit mapping procedures. This mapping-free characteristic of BIM enhances robot navigation capabilities. The subsequent paragraphs will delve into the relevant works conducted in these two aspects, namely aligning robot sensings to BIM for deviation analysis and utilizing BIM as a spatial map for robot navigation.

Visual data is highly informative in nature. Han et al. [3] introduce a technique where vanishing lines and points are detected in images and subsequently projected onto the BIM for the purpose of progress monitoring. Similarly, Chen et al. [4] propose a method that enables the alignment of photometric point clouds with BIM, thereby achieving precise camera localization, commonly referred to as the ”align-to-locate” approach. It is worth noting that a single 2D image cannot inherently provide depth information, which restricts the deployment on image-to-BIM. While stereo vision can offer depth perception [5], its suitability for large-scale alignment is limited. In light of these challenges, our study proposes the utilization of LiDAR point clouds as the input, facilitating direct 3D modeling of the environment.

In the robotics community, an existing recognition is that for long-term robots operating in stable environments, the mapping process of SLAM can be redundant as the generated map remains largely unchanged over time. As an alternative, utilizing Building Information Modeling (BIM) or low-level floorplans has emerged as a potential solution for long-term robot navigation. One notable approach is FloorPlanNet, proposed by Feng et al. [6], which segments rooms from point cloud data and aligns them with a floor plan. The core architecture of FloorPlanNet is based on a graph neural network for effective feature learning. Similarly, Zimmerman et al. [7] introduce a semantic visibility model integrated into a particle filter, enhancing long-term robot indoor localization. These works leverage floorplans as 2D maps, while BIM is a good choice for providing 3D point cloud maps. Yin et al. [8] generated a semantic-metric point cloud map from a BIM and designed a semantic-aided iterative closest point (ICP) algorithm for robot localization. This method effectively localizes a robot equipped with a moving sensor within the BIM environment. While the aforementioned works focus on point-level operations, there is also a promising direction in building instance-level robot navigation. In the study by Shaheer et al. [9], a novel map called S-Graph is designed based on BIM. The S-Graph consists of three-layered hierarchical representations, and a particle filter-based approach is employed to support robot navigation at the instance level.

All the works above aim to align observed data to a floorplan-based or BIM-based map, in which point cloud registration is an indispensable function. This will be discussed in the following subsection.

Point cloud registration, like iterative closest point (ICP) [10] and normal distributions transform (NDT) [11], focuses on local point-level alignment with a good initial guess. Global point cloud registration aims at solving pose estimation from scratch [12]. The global point cloud registration can be categorized into two primary models: correspondence-free[13] and correspondence-based. This study is in a correspondence-based manner. We mainly focus on point descriptors to provide correspondences and recent advances in this task.

Traditional 3D descriptors like Fast Point Feature Histogram (FPFH) [14] compute rotation-invariant features such as distances and angles between points and normals. Then, it searches correspondences on a k-d tree constructed from the FPFH features. Although it performs well in environments with rich geometric features, it degenerates in scenes with ambiguous structures. With the development of 3D representation learning such as PointNet [15] and KPConv [16], various of learning-based methods are proposed to encode and match point cloud features. Deep Closet Point (DCP) [17] encodes 3D point features and incorporates self-attention and cross-attention layers on the encoded features. Point correspondences can be searched by computing the all-to-all feature similarities. After that, GeoTransformer [18] utilizes KPConv to encode hierarchical 3D point features and use optimal transport for correspondence estimation. Although DCP and GeoTransformer have achieved promising results on small-scale benchmarks [19, 20], they face two main challenges for LiDAR global registration with BIM. Firstly, these environments contain numerous similar 3D structures, especially surface planes, making it difficult to distinguish and match corresponding elements accurately. Secondly, the differences in modalities between BIM and LiDAR data create a large domain gap, leading to ambiguous encoding of the 3D point cloud by the 3D backbone. Additionally, learning-based methods incorporating multiple attention layers consume a large amount of memory, making them impractical for use in large-scale environments with current computing platforms.

The 3D point descriptor can also be constructed along with semantic information. Given an RGB-D sequence as input, Kimera by Rosinol et al. [21] constructs a hierarchical scene graph in a large-scale indoor environment. Based on Kimera, Hydra [22] encodes the semantic objects and rooms as hierarchical features. Some related methods reconstruct a semantic graph and encode the graph topology using random walk descriptors. Outram by Yin et al. [23] proposes a triangulated 3D scene graph to search correspondences. BoxGraph by Pramatarov et al. [24] clusters the semantic point cloud into instances. It matches each pair of instances while considering their shape similarity and semantic label. In [7], the floorplan-based method extracts the semantic objects in the 2D floorplan and incorporates the objects into the Monte Carlo Localization model. These semantic-aided approaches are hard to apply in our task registration because the semantic information significantly differs between a BIM model and a LiDAR data, especially when a large deviation exists between the as-designed and as-built in the semantic level. BIM mainly involves structural elements such as walls and rooms, while the methods above detect furniture and small-size objects in LiDAR or RGB-D maps. The inconsistent semantic descriptors pose serious challenges in matching them across modalities.

The density and size of a single LiDAR scan and a BIM model often differ significantly due to modality differences. For effective construction monitoring, denser LiDAR data are preferable to capture detailed geometric information. Conversely, to reduce the complexity of the problem, preprocessing of LiDAR scans and BIM is necessary to align them in size and density. This involves accumulating sequential LiDAR scans to form the LiDAR submap $\mathcal{S}$, and decomposing the BIM into subBIMs $\{\mathcal{B}\}$.

In typical indoor environments, various semantic elements such as floors, columns, and walls exist [8]. Among these elements, the wall is a fundamental component of modern architecture. In this study, we propose selecting walls as the shared representations for LiDAR and BIM data. However, accurately modeling walls from LiDAR data using traditional point cloud processing techniques can be time-consuming. Additionally, learning-based wall recognition methods often require additional data to support training. These factors pose challenges in achieving large-scale global registration, especially on resource-constrained platforms.

On the other hand, the inertial measurement unit (IMU) is a gold standard for modern robotic sensing platforms. IMU can provide the gravity direction of the mapping platform, hence, the 6-degree of freedom (DoF) registration problem can be reduced to 3-DoF in the case of a planar floor. Thus, our basic idea is to project the 3D walls to 2D lines and extract corner points as features, thus generating descriptors for the downstream data association and 3-DoF pose estimation ($x-y$ coordinates and the yaw angle).

We first elaborate on the feature extraction for the LiDAR submap, as illustrated in Figure 3. With the built LiDAR submap, we perform plane detection on a single query submap to extract walls and filter out irrelevant components, notably the ground. Then the 3D walls are converted into 2D corners for the following descriptor computation and transformation estimation. Specifically, the entire point cloud is divided into voxels with predetermined dimensions $s_{v}$. Each voxel contains a collection of points $\mathbf{p}_{i}$, where $i=1,\ldots,N$. Next, we calculate the covariance matrix $\Sigma$ for the points within each voxel:

To determine the content of each voxel, we analyze the ratio of the smallest eigenvalue $\lambda_{3}$ to the second smallest eigenvalue $\lambda_{2}$ of the covariance matrix $\Sigma$. If the ratio exceeds a predefined threshold, the voxel is considered to belong to a plane. To further consolidate plane voxels into coherent plane segments, we employ a region-growing technique. The criteria for merging voxels into plane segments are described in detail in our previous G3Reg by Qiao et al. [25].

Once plane segmentation is completed, we filter out ground points and project the remaining vertical wall points onto the floor plane. 2D corners are obtained by applying the following procedure:

1. 1.

   We project wall points onto a 2D image at pixel scale $s_{\mathrm{I}}$ and apply a line segment detector to identify potential wall structures. We utilize the LSD algorithm by [26] for this purpose.

2. 2.

   Detected line segments are then grouped based on their orientation. Segments whose lengths are below $L_{\mathrm{min}}$ will be discarded.

3. 3.

   Within each group, the classical DBSCAN algorithm [27] is employed, using the distances between line segment endpoints to form clusters that likely correspond to individual walls.

4. 4.

   We merge close and parallel line segments within the same cluster and refit them into a single line segment to accurately represent each wall.

5. 5.

   Finally, these line segments are extended by a predefined distance, and their intersections are computed to identify corner points. These corners are crucial in subsequent data association and pose estimation.

Following a similar pipeline used for the LiDAR submap, we estimate corners of the subBIMs from extracted walls. This consistent approach across LiDAR submaps and subBIMs facilitates subsequent data association and back-end pose estimation.

Upon preprocessing the BIM and the LiDAR submap, we employ triangle descriptors to establish correspondences between them. This method is inspired by the STD introduced in [28]. We leverage both corners and wall segments to construct these descriptors.

Corners extracted from the LiDAR submap and subBIM are used to form a neighborhood graph, where vertices represent corners and edges connect two corners if they are within a maximum distance of $L_{max}$. Cliques in this graph with three vertices are used to form triangle descriptors, denoted by $\Delta$. These triangles are formed by corner triplets $(A,B,C)$, as illustrated in Figure 4. The attributes of a triangle descriptor $\Delta$ include:

• •

  Side lengths $\|AB\|,\|BC\|,\|AC\|$: These are ordered such that $\|AB\|\leq\|BC\|\leq\|AC\|$, encoding the geometric shape of the triangle.

• •

  Angles $\alpha,\beta,\gamma$: These angles are defined as the smaller angle between a triangle side and the intersecting wall segments. Specifically, $\alpha=\min(\angle(AB,l_{m}),\angle(AB,l_{n}))$ where $A$ is the intersection of wall segments $l_{m}$ and $l_{n}$. Similar definitions apply for $\beta$ and $\gamma$, associated with sides $BC$ and $AC$, respectively.

These sorted side lengths and angles capture both the geometric and structural details of the local environment, distinguishing this approach from the original STD descriptor [28]. As shown in Figure 5, querying each triangle in the submap can yield multiple responses in the subBIM due to repetitive architectural patterns. The inclusion of angles $\alpha,\beta,\gamma$ helps to differentiate triangles that have identical shapes but differ in their angular relationships with adjacent wall segments, thus significantly reducing incorrect correspondences.

For efficient data management and retrieval, we construct a hash table for both LiDAR submap and subBIMs. The keys are formed using the triangle descriptor $\Delta=[\|AB\|,\|BC\|,\|AC\|,\alpha,\beta,\gamma]$, with $\Delta\in\mathbf{R}^{6}$, and are quantized based on side length resolution $r_{\mathrm{s}}$ and angle resolution $r_{\mathrm{a}}$ as detailed in Table II and analyzed in Section VI-C1. Multiple corner triplets that yield the same hash key are stored together:

where $N^{s}$ and $N^{b}$ denote the number of triangle descriptors, and $K^{s}$ and $K^{b}$ represent the number of corner triplets for each descriptor in the submap and subBIM, respectively.

During the subBIM retrieval stage, hash keys from the submap are used to vote for potential matched subBIMs. The retrieval score for a subBIM is determined by the number of key intersections with the submap’s keys. This process is expedited by the $O(1)$ query complexity of the hash table. Then we retain all subBIMs with a nonzero number of votes as potential matching candidates, given the presence of numerous repetitive patterns that generate significant ambiguity in indoor scenes. For each subBIM candidate, the matched triangle descriptor can naturally be transformed into a set of corner triplet correspondences by exhaustively matching all corner triplets within two descriptors. Though triplet-based correspondences are with a extremely large number and high outlier ratio, they are crucial for the transformation estimation process, which will be discussed in the next section.

The Hough transform is a robust technique in computer vision for converting raw measurements into a parameter space, where optimal parameters are identified through a voting mechanism to effectively reject outliers. Our implementation includes two primary steps:

Parameter Space Construction: The parameter space, based on the $\operatorname{SE}(2)$ Lie group, includes 2 degrees of freedom (DOF) for translation and one for yaw. This space is rasterized into voxels at resolutions specified by $r_{\mathrm{xy}}$ for x-y translation and $r_{\mathrm{yaw}}$ for yaw, as detailed in Table II and discussed in the ablation study (Section VI-C2).

Voting by Corner Triplet Correspondences: For each corner triplet correspondence $\left[(A,B,C)_{s},(A,B,C)_{b}\right]$, transformation parameters $(x,y,yaw)$ are computed using a closed-form solution for 2D registration [29]. A line segment overlap-based filter is applied to ensure that line segments intersecting at a submap corner overlap with those at the corresponding BIM corner. Only triplet correspondences that pass this filter contribute to the voting process.

For each subBIM, multiple corner triplet correspondences $\{\left(\Delta_{i}^{s},\Delta_{i}^{b}\right)\}_{i=1}^{N_{c}}$ are obtained through triangle descriptor based matching. Each corner triplet from $\Delta^{s}$ is matched against every triplet in $\Delta^{b}$, forming a minimum vote set where each voxel in the parameter space receives at most one vote. All minimum vote sets from $N_{c}$ descriptor correspondences are then combined to form the vote set for one subBIM candidate. In cases where voxels receive votes from multiple subBIM candidates, only the voxel with the maximum votes is retained. The final step involves grouping all pose voxels by their vote counts and selecting the top $J$ groups with the highest votes. The average votes falling into the same voxel represent our transformation candidate.

The computational complexity of this stage is primarily focused on the Hough transform step, denoted as $O(n)$, where $n$ is the number of corner triplet correspondences. This complexity is comparatively efficient, especially when juxtaposed against alternative transformation estimation methods such as RANSAC and TEASER++ (Section VI-C3).

Given transformation candidates for $J$ groups, our objective is to develop a verification scheme to determine the optimal transformation. While corners serve as a common reference between the submap and subBIMs in previous sections, they do not fully capture the geometric structure, leading to potential inaccuracies in alignment determination. To address this, we leverage walls, which encompass the majority of the common geometric structure between the submap and subBIMs, to verify the transformation candidates. The verification process consists of two components: wall preprocessing and similarity score computation.

In the wall preprocessing step, we project the wall point cloud data from both the subBIM and the transformed submap into images $I_{\mathcal{B}}$ and $I_{\mathcal{S}}$ at a pixel scale $s_{\mathrm{I}}$. However, directly comparing these images might not accurately reflect the true alignment quality for two primary reasons. First, the actual construction conditions (as-built data) may differ from the BIM designs (as-designed data). To mitigate this discrepancy, we apply a dilation to the wall pixels in the submap image by a radius of 1 meter. Second, as the submap only partially overlaps with the subBIM, we define a region of interest (ROI) within the subBIM image to focus the assessment on corresponding areas where the submap image exhibits wall pixels.

The similarity between the two images is quantified using the normalized cross correlation coefficient (NCC), a standard measure for image similarity:

where $(u,v)$ are the coordinates within the ROI.

A typical case study illustrating this verification process is presented in Figure 6. Despite generating multiple transformation candidates through a Hough transform and voting procedure, the wall-based transformation verification effectively resolves ambiguities from the corner correspondences by selecting the transformation that best aligns the submap with the subBIM.

The registration recall results on the LiBIM-UST dataset are summarized in Table III. This table compares the performance of image registration, point cloud registration, and our method.

Methods relying on local descriptors, such as SIFT [31], Superpoint [32], and FPFH [34], all recorded a 0% registration recall. Despite attempts to optimize these methods by adjusting descriptor parameters and increasing the number of correspondences (typical counts were 400 for SIFT and Superpoint, and 4000 for FPFH), none were successful. The failure of these methods can be primarily attributed to two factors:

• •

  Inherent Limitations of Local Descriptors: The LiDAR submap and BIM share only basic geometric structures such as walls and corners, which often exhibit repetitive patterns (like single planes or simple intersections). This leads to local descriptors that are not discriminative enough for effective registration.

• •

  Mismatch with BIM’s Geometric Information: For image descriptors, the lack of rich gradient information due to uniform heights of indoor floors and ceilings poses a challenge. Point cloud descriptors like FPFH struggle because they require a diverse distribution of normal vectors, which is not typical in the mostly parallel or perpendicular planes found in BIM environments.

The 3D-BBS method [36] showed potential for LiDAR to BIM registration by searching through transformation space to align submaps closely with BIM. However, it does not account for discrepancies between as-designed and as-built conditions, and the extensive size of BIM compared to submaps makes the search process for 3D-BBS quite time-consuming.

Our method outperforms the aforementioned techniques by leveraging only the geometric features common to both the LiDAR submap and BIM, such as corners and walls. This approach not only reduces computational overhead but also minimizes interference from non-shared structures. By employing a Hough transform coupled with a voting mechanism, our method ensures that the pool of transformation candidates maximally includes potential true transformations, thereby enhancing the registration recall. Additionally, unlike the exhaustive search in 3D-BBS, our use of triangle descriptor-based matching significantly narrows the search scope. We also observed that a larger submap size ($d_{s}$) tends to increase recall, indicating its benefit in preventing registration degeneration, particularly in corridor settings.

In this section, we explore the effects of several key parameters on the overall performance of our registration system. These parameters include the side length resolution $r_{\mathrm{s}}$ and angle resolution $r_{\mathrm{a}}$ for triangle descriptors, the x-y resolution $r_{\mathrm{xy}}$, yaw resolution $r_{\mathrm{yaw}}$, and the parameter $J$ in the voting and verification process, as well as different back-end systems for pose estimation. We set $d_{s}=10m$ for Building Day sequences and $d_{s}=30m$ for office sequences by default.

This subsection highlights specific scenarios that demonstrate the limitations of our proposed method. As depicted in Figure 10, our method struggles in environments characterized by repetitive architectural patterns which lack distinctive corner triplets. Additionally, in scenarios where the mobile platform navigates through narrow and elongated corridors, the observable effective corner points are markedly reduced. This scarcity of corner points often leads to what we term as ‘degeneration issues,’ where the lack of sufficient distinctive features compromises the algorithm’s performance.

Figure 10 also provides further visualizations of the registration outcomes across different scenarios, supplemented with visual images captured by fisheye cameras mounted on the mobile platform. These visual aids illustrate the practical challenges faced in these specific architectural settings and help in understanding the limitations of the current system in managing complex environments.