J. Zhu et al. / Computers and Electrical Engineering 58 (2017) 477–488 479
Fig. 1. Overview of the coarse-to-fine registration approach. Each dot denotes a scan; the black dot is the reference scan; each dotted line represents an
initial parameter. Scans inside one red circle are integrated into a coarse model.
three steps are included in each iteration: for each point in the data shape, find its nearest-neighbor from the model shape;
based on established correspondences, confirm overlapping areas between the model and data shapes; utilize these point
pairs located in overlapping areas to calculate the rigid transformation. Given suitable initial parameters, the optimal solu-
tion can be obtained by the iteration of these three steps until convergence criteria are satisfied. For further details, please
refer to [23] .
2.2. Coarse-to-fine registration approach
Given a set of initially posed scans, multi-view registration can be achieved by the coarse-to-fine approach based on the
TrICP algorithm [23] . Fig. 1 displays an overview of this approach, which can be described as follows:
(1) Divide all the involved scans into two parts: the n th scan and the coarse model integrated by all other scans. The
n th scan and the coarse model can be viewed as the data shape and the model shape, respectively. In this case,
parameters of the n th scan can be refined by pairwise registration. Because the reference frame is attached to the
first scan, it is always in its correct position. Therefore, there is no requirement to refine its registration parameters.
(2) Refine registration parameters of the n th scan. In general, the n th scan has a high overlap percentage to the coarse
model, which is integrated by all other scans. Given initial parameters of the n th scan, the TrICP algorithm can be
applied to obtain more accurate parameters, which can be returned to refine the coarse model for the registration of
other scans.
(3) Process each scan sequentially by the implementation of the above two steps.
(4) To obtain the desired registration result, several update cycles are required. After one update cycle, registration pa-
rameters of all scans become more accurate. However, during the update of the i th scan, the other scans are not in
their correct positions; hence, it is not possible to obtain the desired registration with only one update cycle.
(5) Repeat steps (1) ∼ (4) until the iteration number reaches the threshold or other stop conditions are satisfied.
Given suitable initial parameters, the coarse-to-fine approach can obtain accurate results for multi-view registration.
However, its efficiency and robustness must be further improved especially when multi-view scans are initially posed with
less than suitable parameters.
3. Methodology
This section presents the proposed approach for multi-view registration of initially posed scans using a spanning tree,
including the construction of the spanning tree, local, and global multi-view registration.
3.1. Overview
Given a set of initially posed scans, the goal of multi-view registration is to refine these rigid transformations of the
other scans to the reference scan. Without loss of generality, the coordinate of the first scan can be viewed as the reference
frame. Because there are many parameters required to be estimated, multi-view registration is time-consuming and accurate
results are difficult to obtain. Therefore, an effective approach must be proposed to solve this problem.
For the registration problem, three facts can be reviewed: the more suitable the initial parameters provided for multi-
view registration, the more easily it will be solved; multi-view registration is more difficult than pairwise registration, how-
ever, its difficulty is decreased with a decrease of the number of involved scans; for pairwise registration, its difficulty is
decreased with an increase of the overlap percentage between two scans. Motivated by these three facts, the multi-view
registration problem can be decomposed into sub-problems: pairwise registration, local, and global multi-view registration.
Fig. 2 displays an overview of the proposed approach, which solves these sub-problems by three steps:
(1) Construction of a spanning tree. Based on initial parameters, estimate the overlap percentage for each scan pair and
then construct a spanning tree according to the estimation of overlap percentages.
(2) Local multi-view registration. For these scans located in the second level of the spanning tree, local multi-view regis-
tration can be applied to refine their registration parameters. After local registration, these scans in the second level