Registration
The Problem
For the 3D reconstruction inside historic buildings, we need a marker-free automatic registration approach to align different views together, because GPS does not work indoors and markers are not allowed to paste on the walls. We present an automatic matching process, which employs a novel algorithm, Dynamic Matching Tree technique, for a fast and stable coarse-matching to achieve the automatic pre-alignment of two point clouds and uses modified ICP to do a fine matching efficiently.
Methods
The whole process can be divided into three steps:
- Preprocessing
- 2-View matching
- N-View matching
1. Preprocessing
In this stage, we do a segmentation of each point cloud firstly. And then we use a form-descriptor to generate corresponding segment-pairs. By the characteristics of the surfaces, the model in one view is segmented into diverse objects. Here, the difference between normal vectors between adjacent points is treated as segmenting criteria. If the difference between the normal vectors of point p and q is fairly large, then the boundary between two objects will be set through here (See Fig. 1).
Figure 1. Criterion for segmentation |
2. 2-View matching
This is a coarse-to-fine matching process, which consists of two steps: the first is coarse matching, which solves the pre-alignment problem automatically; and the second is fine matching, which aligns two views accurately.
A. Coarse matching
A novel algorithm “Dynamic Matching Tree (DMT)” will be used in this stage. DMT applies the dynamic programming technique to “Matching Tree (MT)” implementation. Matching Tree is designed for 3D global registration out of local correspondent relationships. Every node contains a corresponding pair, which can be valid or invalid. The root contains three non-collinear self-validated nodes. Matching Tree is a tree, and it can be treated as a bipartite matching if we delete its edges, split every tree-node to two object-nodes and add an edge between corresponding object-pair in each valid tree-node
Figure 2. Matching tree and matching |
Validation of the none-root-nodes is through comparing the directed relative distances to the root-nodes (See Fig. 2). That means, we need not only to compare the distances from the corresponding pair in this node to the corresponding pairs in the three root-nodes, but also the position of them, because one object-node can be above or under the root-plane with the same distances to the three root-nodes. As showed in Fig. 3, (p, p”) is a mirror-pair, which cannot be matched by pure translation and rotation. And (p, p’) is the right corresponding pair. We can check it by comparing the direction of the normal vector formed by the three root-nodes with the direction from the center of the root-nodes (O, O’) to the node (p, p’).
If we assign a matching weight to each node, the goal is to get a matching tree with maximal weight. The basic form to solve the sub-problem of dynamic programming is:
-formula-
B. Fine matching
Fine matching can be done in two ways:
As the correct correspondent relationships between segments are decided after the coarse matching. We can generate an arbitrary number of control-point-pairs by projecting the sampling points of one segment to its correspondent segment. And by the use of iterative actions, the result will be refined.
Because the two vies are aligned coarsely after the transformation calculated in coarse matching, the ICP (iterative closest point) algorithm or some variation of ICP can be used here.
3. N-View matching
After the fine two-view matching, all the scans are in a common coordinate system of. So we can generate the corresponding point pairs of the multiple views, and make a bundle adjustment to homogenize the whole point clouds.
Results
To validate our method, various experiments have been done on the reconstruction of historic buildings.
Figure 3. Reflectivity pictures |
Figure 4. Point clouds, before and after registration |
Publications
[1] R. Liu and G. Hirzinger, “Marker-free Automatic Matching of Range Data,” in Proc. of 2nd Panoramic Photogrammetry Workshop, Berlin, Germany, 2005.
[2] R. Liu, D. Burschka and G. Hirzinger: A Novel Approach to Automatic Registration of Point Clouds, In Proc of IEEE International Geoscience and Remote Sensing Symposium (IGARSS), Barcelona, 2007.