Reconstructing three-dimensional (3-D) surface model is a fundamental and important issue in computer vision due to its wide application in reverse engineering, virtual reality, digital museums, prosthetic design, etc. The development of scanning technology makes it possible to reconstruct the accurate 3-D surface model. As one object cannot be scanned in its entirety from a single viewpoint, scanners are required to acquire range scans from different viewpoints for covering the entire object surface. These range scans are partially overlapping to their neighbors and should then be registered in a common reference frame for surface reconstruction. Therefore, registration of multiview range scans is the prerequisite and a critical problem for surface reconstruction.1,2
The most popular solution to registration is iterative closest point (ICP) algorithm,3,4 which can solve this problem for its good accuracy and fast speed. However, this approach cannot achieve the registration of partially overlapping range scans, which may arise in many practical applications. To address this issue, Chetverikov et al. proposed the trimmed ICP (TrICP) algorithm, which introduces an overlapping parameter into the objective function to discard outliers automatically.5 Further, the performance of this basic approach is improved in efficiency6 and convergence.7 For any given initial parameters, these approaches can converge monotonically to local minima. To obtain the desired global minimum, it requires a good initial alignment, which can be provided by genetic algorithm (GA).8 Besides, particle filter can also be utilized to estimate the global alignment for pair of range scans.9
Although the registration of two range scans is a well-studied problem, multiview registration problem is somewhat more difficult because of the large number of registration parameters. An early approach that achieved the multiview registration was proposed in Ref. 10. For each range scan, it sequentially builds up correspondence to each other scans and calculates the rigid transformation by ICP algorithm, so this approach is time-consuming and difficult to deal with nonoverlapping regions. In Ref. 11, Pulli proposed an approach that first performs registration of range scan pair, where the estimated transformations are viewed as constraints in the global multiview stage. Besides, the multiview registration problem can also be defined as an optimization over the graph of adjacent scans.1213.–14 These approaches cast the multiview registration problem into a diffusion of rigid transformations over the graph of adjacent scans. As these approaches do not optimize correspondences, they cannot really reduce the total registration error as it only transfers the registration errors between coordinate frames. Recently, Shi et al.15 proposed a multiview registration method based on the -means clustering and mean shift clustering theory. Although this approach is very fast, it is not very accurate. At the same time, Simone et al.2 proposed a completely automatic approach for registration of multiple three-dimensional (3-D) range scans. Since this approach requires extracting and describing the key-points from scan data, it is troublesome and not very reliable. More recently, Govindu and Pooja16 proposed a multiview extension of the ICP algorithm by Lie-algebraic averaging that can simultaneously average the redundant information available in arbitrary scans. As this approach adopts ICP algorithm to align range scans with nonoverlapping regions, its performances should be further improved.
Different from previous works, this paper proposes a novel multiview registration approach for surface reconstruction. It first designs the objective function, where all registration parameters are involved. What’s more, it also considers the overlapping parameter for each range scan, which allows it to align scans with nonoverlapping regions. Further, an iterative solution is proposed to solve the well-designed objective function and efficiently obtain accurate multiview registration results.
The remainder of this paper is organized as follows. In Sec. 2, ICP algorithm is briefly reviewed. Section 3 presents the proposed approach. Following that is Sec. 4, in which the proposed approach is tested and evaluated on some public data sets. Finally, some conclusions are drawn in Sec. 5.
Given two absolutely overlapping range scans, a data shape and a model shape , the goal of registration is to find the optimal transformations , with which can be in the best alignment with , so it can be formulated as the following least square problem:1), one of the most popular solutions is ICP algorithm. Given the initial parameters , it can achieve the rigid registration by two iterative steps.
First, assign the correspondence between two range scans with the ’th transformation.
Second, recover the new rigid transformation from the current correspondences.
Although the original ICP algorithm has good performance, it cannot achieve the registration of partially overlapping range scans.
Registration of Multiview 3-D Scans
This section will discuss the multiview registration problem and propose an accurate and efficient solution for surface reconstruction.
Suppose there is a 3-D data set including range scans , which are acquired from an object in different viewpoints. They are partially overlapping or nonoverlapping with each other. Accordingly, the parameters required for full registration of all scans are , where the ’th rigid transformation consists of the rotation matrix and translation . Set ; then it is convenient to define the operation and obtain the reconstructed 3-D surface model .
Denote as the special surface model, which is integrated by () registered range scans acquired from different viewpoints except the ’th scan. Since range scans can cover the entire object surface, the surface model is very close to the full surface model and can turn to be the full one by registering the ’th range scan to itself. Accordingly, and can be viewed as the data shape and model shape, respectively. Besides, has high overlapping percentage to . Assume denotes the overlapping percentage and represents the subset of , which can match with . Then, the mean square error can be defined asRef. 5, the optimal solution of parameters can be obtained by minimizing the following function: 5), only the ’th transformation is involved. Actually, all transformations are unknown in multiview registration problem. Hence, the objective function for multiview registration of range scans can be proposed as 6).
In Eq. (4), the data shape is one range scan and the model shape is the approximately full surface model, which is integrated over all other range scans involved in multiview registration. Hence, the overlapping percentages in Eq. (6) are always higher than that of individual scan pairs, and it is more likely to obtain accurate and robust registration results for the multiview registration problem represented by Eq. (6). From the above-mentioned discussion, the multiview registration problem can be viewed as the two following subproblems: (1) How to reconstruct the accurate surface model . (2) How to solve Eq. (6) and obtain the optimal parameters for the multiview registration.
Multiview Registration Algorithm
Although it is difficult to obtain the accurate surface model, there are some methods to reconstruct coarse surface model. Without loss of generality, the reference frame of the reconstructed surface model can be attached to the first range scan. Hence, and . According to Ref. 8, GA can be utilized to register two arbitrarily oriented range scans, which are partially overlapping. And the registration results of individual range scan pairs can then be sequentially transformed into the initial multiview registration parameters as8) depicts, the surface model represents an approximately full surface model, which can be obtained from the full surface model by discarding the ’th range scan. Since many range scans are involved in multiview registration, transformation errors can be accumulated in Eq. (7), even the registration results of individual scan pairs are accurate enough. That means the initial reconstructed surface model is coarse. Since the coarse surface model has been reconstructed, the remaining question is how to solve Eq. (6) and refine the coarse model.
Usually, there are large numbers of parameters involved in multiview registration, so it is difficult to solve Eq. (6) directly. Therefore, a suboptimal approach should be proposed. In fact, the ’th transformation can be recovered from Eq. (5), which requires to achieve registration of partially overlapping range scans and can be solved by the TrICP algorithm. Given the ’th initial transformation , TrICP algorithm can achieve the registration of partially overlapping range scans by iterations.7 In each iteration, three steps are included.
1. Assign the correspondence for each point with the ’th transformation.
2. Update the ’th overlapping parameter and its corresponding subset .
3. Calculate the optimal transformations .
Repeat steps (1) to (3) until or reaches a maximum number of iterations. Finally, the TrICP algorithm can provide the solution of parameters . In fact, Eq. (9) can be calculated by some efficient nearest-neighbor search methods,1718.–19 and Eq. (10) can be efficiently solved by the approach proposed in Ref. 6. Besides, the optimal transformations in Eq. (11) can be recovered by many closed-form approaches,20 such as the singular value decomposition technique. Accordingly, the TrICP algorithm can be sequentially applied by times to obtain the solution of all transformations involved in Eq. (6).
As mentioned before, when TrICP is applied to calculate the ’th transformation involved in Eq. (6), the surface model is not very accurate. Therefore, the new recovered transformation may not be the optimal solution for the multiview registration, but it is more accurate than the initial one. Hence, the initial transformation should be replaced by the new one before TrICP is applied to estimate the following transformations. That means the reconstructed surface model should be updated and refined when a new transformation is recovered from Eq. (5), so does the surface model . Since there is no way to obtain the optimal solution of each transformation by applying the TrICP algorithm one time, several rounds of update for each transformation should be implemented to obtain the optimal solution. In the new update round, the solution of previous round should be viewed as the initial parameter of the TrICP algorithm. With the increase of update round, the surface model will become more and more accurate, so do all the recovered transformations .
Given the initial parameters () of multiview registration, the proposed registration algorithm can be reasonably outlined as follows:
1. Obtain the initial reconstructed surface model .
2. Set ; view and as the data and model shape, respectively.
3. Calculate the new solution of scan from Eq. (5) by the TrICP algorithm, where the initial parameter is and the maximum number of iteration is .
4. View as the optimal solution and update the corresponding reconstructed surface model .
5. Apply the TrICP to each range scan () sequentially and obtain the optimal solution of from Eq. (6) by repeating steps (2) to (4) until the number of update round reaches the maximum value or .
As steps (1) to (5) depict, the proposed approach solves Eq. (6) in a coarse-to-fine manner. For each scan, it first reconstructs a coarse and incomplete model by other scans with initial multiview alignment. Then, it sequentially registers each scan to the coarse model and returns to refine the coarse model by the registration results. To obtain good results, several update rounds are required for all range scans. Finally, it can accomplish the registration of multiview scans and obtain accurate object model.
To test its performance, the proposed approach is compared with two other related approaches presented in Refs. 10 and 16, which are abbreviated as Robert and Govindu, respectively. During experiments, parameters are set as follows: , , , , and . Experiments were tested on three range data sets from the Stanford repository,21 where the Bunny, Dragon, and Happy Buddha include 10, 15, and 15 range scans, respectively. These range scans in each data set are acquired from varied viewpoints to cover the entire object surface. Figure 1 displays 10 arbitrarily oriented scans acquired from the Stanford Bunny. To assign the correspondences, multiview registration approaches employ the nearest-neighbor search method based on tree. For all three competing approaches, GA is adopted to obtain the accurate registration results for range scan pairs before applying Eq. (7) to provide the initial parameters. Experiments were implemented in MATLAB® and performed on a double-Core 3.1 GHz computer with 4 GB of memory.
Here, the proposed approach was tested on the three above-mentioned range data sets. Given all multiview range scans acquired from one object, the alignment of scan pairs can be estimated by the approach presented in Ref. 8. Then, these alignments can be transformed into the initial multiview results by Eq. (7) and turn to be the coarse surface model. Based on the coarse surface model, accurate surface model can be reconstructed by the proposed approach. These reconstructed surface models are depicted in Fig. 2, where the reconstructed results are also shown in the form of cross-sections and the corresponding regions on the surface models are labeled. As Fig. 2 shows, the proposed approach is able to reconstruct good surface models from arbitrarily oriented range scans.
Besides, the proposed approach was tested on Stanford Bunny with different groups of initial multiview registration parameters, which can be acquired by adding some uniformly random noises to the rotation obtained from Eq. (7). To show the robustness, 50 Monte Carlo (MC) trials were carried out with respect to each noise level and the corresponding results are displayed in Table 1. As Table 1 depicts, the proposed approach can efficiently obtain good registration results under low noise. With the increase of the noise level, the performance of the proposed approach will be reduced. To view the results in a more intuitive way, Fig. 3 displays the objective function value of the registration results for each MC trial and Fig. 4 depicts the convergence of the proposed approach with respect to the update round for four groups of good initial parameters.
The performace of the proposed approach with respect to different noise levels.
|[−0.015,0.015] (rad)||[−0.03,0.03] (rad)||[−0.045,0.045] (rad)||[−0.06,0.06] (rad)|
As shown in Figs. 3 and 4, the proposed approach can converge monotonically to the desired global minimum for any given good initial parameters. That means the proposed approach has certain convergence band and can minimize Eq. (6) by iterations so as to achieve the registration of multiview range scans. Since the proposed approach belongs to the local convergent algorithm, it may fail to obtain good registration results due to the bad initial parameters and the probability of failure will be reduced with the decrease of the noise level.
Hence, the proposed approach requires the good initial parameters, which can be obtained from the results of pair-wise registration by Eq. (7).
Before comparison, it will be shown why the proposed approach can obtain the good results for multiview registration. Figure 5 displays the overlapping percentage of each range scan in three range data sets. As Fig. 5(a) depicts, the overlapping percentage of one scan to most of the other individual scans is very low, so it cannot robustly achieve good registration for most of the range scan pairs. Accordingly, the accurate results may not be obtained by these approaches, which ultilize the registration results of range scan pairs to achieve multiview registration. To address this issue, the formulation of multiview registration is redesigned and the novel objective function [Eq. (6)] is proposed in this paper. As Fig. 5(b) shows, all the overlapping percentages in Eq. (6) are . Due to the high overlapping percentages, it is easy to register one scan to the surface object reconstructed by all other scans and obtain good multiview registration results, which can verify the goodness of the proposed objective function.
For comparison, other two approaches were also tested on the Stanford repository. Since all these competing approaches require the initial multiview registration parameters, it only needs to compare the runtime of multiview registration. Accordingly, Table 2 records the runtime and objective function value of the final registration results for all the competing approaches. To observe the compared results in a more intuitive way, Fig. 6 displays the registration results of three data sets for different approaches in the form of cross-sections.
The compared accuracy and runtime for different approaches.
|Dataset||Initial obj.||Robert’s method10||Govindu’s method16||Ours|
|T (min)||Obj.||T (min)||Obj.||T (min)||Obj.|
Table 2 and Fig. 6 show that the proposed approach can obtain the most efficient and accurate registration results among three approaches. Moreover, smaller values of objective function presented in Table 2 correspond to better results shown in Fig. 6, which can further verify the validity of the objective function [Eq. (6)]. What’s more, these results can ensure that the proposed objective function can be regarded as the criterion for the accurate evaluation of the multiview registration. Since the computation of correspondences is time-consuming and the other two approaches require building up of correspondences between one scan and each other scans, these two approaches are not very efficient. Besides, these two approaches only use the distance threshold to handle nonoverlapping regions of two range scans, so it is difficult to get accurate registration results for individual scan pairs, which will further lead to imprecise multiview registration. While, in our approach, all the other scans are viewed as the model shape when registers each range scan, so it only needs to build up correspondences by one time for each scan. To handle nonoverlapping regions, it introduces the overlapping parameters into the objective function and is able to automatically obtain the right correspondences, which can result in accurate registration of multiview range scans.
This paper proposes a novel multiview registration approach for the 3-D surface reconstruction. By analyzing the registration problem, it designs the objective function for registration of multiview range scans. To solve this function, it further presents a suboptimal solution in the coarse-to-fine manner. The proposed approach has been tested on public available data sets. Experimental results demonstrate that it can efficiently reconstruct the accurate 3-D surface model and has super performance over other related approaches. The main contributions of this paper can be concluded as follows:
1. It designs a novel objective function for the registration of multiview range scans, which can also be viewed as a criterion for the accurate evaluation of the reconstructed model surface.
2. To solve the designed objective function, it then extends the TrICP algorithm to deal with multiple range scans simultaneously.
Though the proposed approach has achieved good results for rigid registration of multiview range scans, there are still many degrees of freedom that could be explored, such as the extension of this approach to the nonrigid registration of multiview range scans.
This work is supported by the National Natural Science Foundation of China under Grant Nos. 61203326, 91120006, and 91120009.
F. SimoneC. UmbertoF. Andrea, “Accurate and automatic alignment of range surfaces,” in Proc. Second Int. Conf. on 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT), Zurich, Switzerland, pp. 73–80 (2012).Google Scholar
D. ChetverikovD. StepanovP. Krsek, “Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm,” Image Vis. Comput. 23(3), 299–309 (2005).IVCODK0262-8856http://dx.doi.org/10.1016/j.imavis.2004.05.007Google Scholar
M. PhillipsL. RanC. Tomasi, “Outlier robust ICP for minimizing fractional RMSD,” in Proc. Sixth Int. Conf. on 3-D Digital Imaging and Modeling (3DIM), Montreal, Canada, pp. 427–434 (2007).Google Scholar
S. Y. Duet al., “Robust iterative closest point algorithm for registration of point sets with outliers,” Opt. Eng. 50(8), 087001 (2011).OPEGAR0091-3286http://dx.doi.org/10.1117/1.3607960Google Scholar
E. LomonosovD. ChetverikovA. Ekárt, “Pre-registration of arbitrarily oriented 3D surfaces using a genetic algorithm,” Pattern Recongnit. Lett. 27(11), 1201–1208 (2006).PRLEDG0167-8655http://dx.doi.org/10.1016/j.patrec.2005.07.018Google Scholar
R. SandhuS. DambrevilleA. Tannenbaum, “Point set registration via particle filtering and stochastic dynamics,” IEEE Trans. Pattern Anal. Mach. Intell. 32(8), 1459–1473 (2010).ITPIDJ0162-8828http://dx.doi.org/10.1109/TPAMI.2009.142Google Scholar
K. Pulli, “Multiview registration for large data sets,” in Proc. Second Int. Conf. on 3-D Digital Imaging and Modeling (3DIM), Ottawa, Canada, pp. 160–168 (1999).Google Scholar
C. S. GregoryW. L. SangK. W. David, “Multiview registration of 3D scenes by minimizing error between coordinate frames,” IEEE Trans. Pattern Anal. Mach. Intell. 26(8), 1037–1050 (2004).ITPIDJ0162-8828http://dx.doi.org/10.1109/TPAMI.2004.49Google Scholar
S. W. ShihY. T. ChuangT. Y. Yu, “An efficient and accurate method for the relaxation of multiview registration error,” IEEE Trans. Image Process. 17(6), 968–981 (2008).IIPRE41057-7149http://dx.doi.org/10.1109/TIP.2008.921987Google Scholar
A. TorselloE. RodolaA. Albarelli, “Multiview registration via graph diffusion of dual quaternions,” in Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition (CVPR), Providence, RI, pp. 2441–2448 (2011).Google Scholar
V. M. GovinduA. Pooja, “On averaging multiview relations for 3D scan registration,” IEEE Trans. Image Process. 23(3), 1289–1302 (2014).IIPRE41057-7149http://dx.doi.org/10.1109/TIP.2013.2246517Google Scholar
M. GreenspanM. Yurick, “Approximate k-d tree search for efficient ICP,” in Proc. Forth Int. Conf. on 3-D Digital Imaging and Modeling (3DIM), Banff, Canada, pp. 442–448 (2003).Google Scholar
K. F. Mulchrone, “Application of Delaunay triangulation to the nearest neighbour method of strain analysis,” J. Struct. Geol. 25(5), 689–702 (2003).JSGEDY0191-8141http://dx.doi.org/10.1016/S0191-8141(02)00067-6Google Scholar
A. NuchterK. LingemannJ. Hertzberg, “Cached k-d tree search for ICP algorithms,” in Proc. Sixth Int. Conf. on 3-D Digital Imaging and Modeling (3DIM), Quebec, Canada, pp. 419–426 (2007).Google Scholar
A. Nüchteret al., “Study of parameterizations for the rigid body transformations of the scan registration problem,” Comput. Vis. Image Underst. 114(8), 963–980 (2010).CVIUF41077-3142http://dx.doi.org/10.1016/j.cviu.2010.03.007Google Scholar
Jihua Zhu received his PhD degree in control science and engineering in 2011 from the Xi’an Jiaotong University, China. He is a lecturer of Xi’an Jiaotong University. His research interests cover computer vision and autonomous robots.
Zhongyu Li is a master student in the School of Software Engineering, Xi’an Jiaotong University, China. He received his BS degree in automation from Xi’an Jiaotong University. His research interests include image registration and three-dimensional reconstruction.
Shaoyi Du received his PhD degree in pattern recognition and intelligence system from Xi’an Jiaotong University, China, in 2009. He is an associate professor at Xi’an Jiaotong University. His research interests include computer vision, pattern recognition, and machine learning.