CHEMICAL ENGINEERING TRANSACTIONS VOL. 51, 2016 A publication of The Italian Association of Chemical Engineering Online at www.aidic.it/cet Guest Editors: Tichun Wang, Hongyang Zhang, Lei Tian Copyright © 2016, AIDIC Servizi S.r.l., ISBN 978-88-95608-43-3; ISSN 2283-9216 A Point Cloud Registration Algorithm for Free-form Surface Chunfa Sha*, Zhangping Lu, Rui Li, Hang Zheng, Enock A. Duodu Graphics Technology Institute, Jiangsu University, Zhenjiang, 212013, China. 24679598@qq.com To improve the searching efficiency of the precise position of workpiece with free-form surface, a new two- step point cloud registration method is proposed. It seeks to improve the preliminary registration algorithm and the iterative closest point (ICP) algorithm. Firstly, for preliminary registration, the co-planar 4-points sets are searched based on the constraints of distance and proportional relationship between points. Then the invariant of these co-planar 4-points sets are used for random sample consensus algorithm (RANSAC) to get initial position of the target point cloud. Secondly, re-sampling of source data, matching method based on double direction normal projection and elimination of unreliable point-pairs are used to improve the original ICP algorithm to optimize the preliminary registration result. The registration simulations of two simple workpieces were conducted. The results show that the improved algorithm has higher efficiency and better precision than the traditional ones. 1. Introduction In the field of industrial manufacturing, some workpieces of free-form surface (such as titanium skin) without any obvious features should be made in a non-binding state with no fixtures. This can lead to unknown position and posture of the surface. Thereby it is unable to get the precise position for the subsequent work, like drilling, cutting and other processes. A traditional technique is to use the tools called "profile model" to fix the position manually, which leads to high manufacturing costs, inefficiency, poor flexibility and low yield. A registration process of two point clouds for free-form surfaces, where one point cloud is created from CAD model and the other is scanned from the corresponding workpiece, is proposed to achieve the precise position of the workpiece. With this method, there are no "profile model" tools and only the key is the algorithm which is used to get the precise alignment between the two point clouds. Currently, there are usually two automatic registration techniques used in engineering: feature-based matching algorithm, for example sample-sphere matching algorithm based on normal (Meng and Zhang, 2011) and algorithm based on the boundary of point cloud (Wang and Zhang, 2012); ICP algorithm (Besl and Mckay, 1992). In order to improve the accuracy and efficiency of the registration, this paper intends to design a new two- steps registration method: RANSAC algorithm based on co-planar 4-points sets for the preliminary registration and an improved ICP algorithm for accurate registration. 2. RANSAC algorithm based on co-planar 4-points sets for the preliminary registration RANSAC algorithm (Fischler and Bolles, 1987; Chen and Hung, 1999) is an estimation algorithm with good robustness that can handle point cloud data and is widely used in the field of computer sciences. In this paper, for the preliminary registration, co-planar 4-points sets are used as the initial sample to improve RANSAC. 2.1 Co-planar 4-points sets As shown in Figure 1, it is hypothesized that 4 non-collinear points from the target point cloud P is in the same plane. Then e as the intersection of ab and cd could be found. The length and the ratio as indicated in Eq(1) of the two lines are Euclidean invariant with rigid transformation(Sharp and Sang, 2002; Urfalıoḡlu and Mikulastik, 2006). Therefore the corresponding 4 co-planar points could be obtained in the reference point cloud Q based on the equal length of line segment and the same split ratio of the intersection. DOI: 10.3303/CET1651079 Please cite this article as: Sha C.F., Lu Z.P., Li R., Zheng H., Duodu E.A., 2016, A point cloud registration algorithm for free-form surface, Chemical Engineering Transactions, 51, 469-474 DOI:10.3303/CET1651079 469 http://dict.youdao.com/w/workpiece/ http://dict.youdao.com/w/workpiece/ http://dict.youdao.com/w/workpiece/ Figure 1: Co-planar 4-points 1 2 1 2 ' ' ' ' ' ' ' ' ' ' ' ' d a b a b d c d c d a e a e r a b a b c e c e r c d c d                           (1) 2.2 Searching for the corresponding 4-points sets The corresponding 4-points sets for preliminary registration can be searched as follows. Firstly, in P, 4 non-collinear but co-planar points {𝑎,𝑏,𝑐,𝑑} with distances long enough between each other are selected randomly in the overlapping region of the two point clouds based on the condition 0 < 𝑟𝑖 < 1(𝑖 = 1,2) , otherwise the points should be sampled again. Then, 𝑑1 , 𝑑2 , 𝑟2 and 𝑟2 are calculated after the intersection e is obtained. Secondly, all the two points with the distance 𝑑1 in Q are stored in a point set S. And all the two points with the 𝑑2 distance in Q are stored in a point set T. Thirdly, the intersections 𝑒1 and 𝑒2 of every line segment in S are calculated as 𝑒1 = 𝑎′ + 𝑟1(𝑏′ − 𝑎′) and 𝑒2 = 𝑎 ′ + 𝑟1(𝑎 ′ − 𝑏′) . Equally, the intersections 𝑒3 and 𝑒4 of each line segment in T are obtained as 𝑒3 = 𝑑 ′ + 𝑟2(𝑐 ′ − 𝑑′) and 𝑒4 = 𝑑′ + 𝑟2(𝑑′ − 𝑐′). If two intersections respectively from S and T satisfy 𝑒𝑠 = 𝑒𝑡, the four end points of the two lines are the corresponding 4-points set {𝑎′,𝑏′,𝑐′,𝑑′}, as illustrated in Figure 2. Figure 2: The corresponding 4-points set 2.3 RANSAC algorithm based on co-planar 4-points sets RANSAC algorithm improved based on co-planar 4-points sets as follows is used for the preliminary registration. (1) Select 4 non-collinear points {𝑎,𝑏,𝑐,𝑑} in a same plane randomly in P, and compute 𝑑1, 𝑑2, 𝑟2 and 𝑟2; (2) Find out the corresponding 4-points set {𝑎′,𝑏′,𝑐′,𝑑′} in Q with the method described in the section 2.2; (3) Take the two co-planar 4-points sets as estimating points to compute the Euclidean transformation matrix 𝐻𝑐 between the two point clouds; (4) Calculate the degree of consistency between P and Q based on 𝐻𝑐. If the number of point-pairs that are matching with the error threshold δ (a given error threshold) is greater than n (n = λ ∗ 𝑁, N is the point number 470 http://dict.youdao.com/w/respectively/ of P, and λ is the rate of the interior points of P obtained in the pre-processing of the point cloud), the transformation matrix 𝐻𝑐 will be exported as a satisfactory one. (5) Go back to step (1) and do iteration again. After K times random sampling and registration, transformation matrix H that has the best degree of consistency is selected as the final transformation matrix for preliminary registration; K = log(1−𝜎) log(1−λ4) (2) Where 𝜎 is the probability that K times sampling contains at least a good sample. 3. The improved ICP algorithm for accurate registration The position obtained by preliminary registration creates a favorable condition for the accurate registration. ICP approach is the most widely accepted algorithm for accurate registration. It has simple registration idea, high accuracy, robust and stable. But, all points in P should be took into iteration and it requires a larger overlap area and an original position as close as possible between the two point clouds, or the results may not necessarily be a global optimal solution but a local one (Senin and Colosimo, 2013; Zhou and Yong, 2011). So, there are more things need to be done for ICP. 3.1 Re-sampling of source data The accuracy of the algorithm depends on the matching accuracy of point-pairs rather than the number of point-pairs. Thus one can use re-sampling way which extracts points from the target point cloud to reduce the number of points that need to be matched. There are several common methods for re-sampling: random sampling, uniformly distributed sampling, sampling based on feature space. It was shown that random sampling is better than the other two for the point cloud having no obvious features (Rusinkiewicz and Levoy, 2001). There are no distinctive features in workpieces with free-form surface. In each iteration, this paper takes random sampling as the re-sampling way. 3.2 Establishment of matching point-pair Corresponding points in Q matching with re-sampled points should be found. This paper propose a double- direction normal projection matching method: The re-sampled point 𝑝𝑖 from P is projected onto the fitting surface of Q along its normal vector. Firstly, when the projection intersection m point is exactly a point 𝑞𝑖 of Q, the point 𝑚′ can be obtained, which is the projection point of point 𝑞𝑖 along its normal vector onto the point cloud P. If ‖𝑝𝑖 − 𝑚′‖ ≤ 𝑡, a set of matched point-pair (𝑝𝑖,𝑞𝑖) could be built, for example (𝑝1,𝑞1) in Figure 3. If not, the point 𝑝𝑖 should be deleted from the matched point-pairs. Secondly, when the projection intersection point denoted as m is not a point of cloud Q, as 𝑝2 shown in Figure 3. The nearest point 𝑞2 of the point m within the threshold range t is found in Q. Then the point 𝑚′, which is the projection point of the point 𝑞2 along its normal vector onto the point cloud P can be obtained. If ‖𝑝2 − 𝑚′‖ ≤ 𝑡, point-pair (𝑝2,𝑞2) could be used as matched point-pair, or the point 𝑝2 should be deleted from the matched points. t is the mean value of all distances between the projection point m and its closest points. Figure 3：Matching method based on double-direction normal projection 3.3 Elimination of unreliable point-pairs Due to the strategy used to search for the putative correspondences, there are necessarily unreliable point- pairs in the matched point-pair sets established by the method proposed above. Commonly, there are two constrains to exclude unreliable points: the rigid constraints, the constraints based on geometric consistency. But they may diminish too much erroneous point-pairs or be time-consuming especially for the massive point clouds (Xie and Shang, 2010). In this paper, a method using the distance and the point curvature features as constraints to eliminate unreliable point-pairs is applied as follows. Firstly, all the distance between the matched points are calculated. If the distance satisfies Eq(3), then the 471 http://dict.youdao.com/w/mean/ http://dict.youdao.com/w/value/ point-pair (𝑝𝑖,𝑞𝑖) would be removed from matched point set. | 2(𝑑𝑖−𝐷𝑚) 𝑑𝑚𝑎𝑥−𝐷𝑚𝑖𝑛 | > 0.8 (3) Where 𝑑𝑖 is the distance of the point-pair (𝑝𝑖,𝑞𝑖), 𝐷𝑚 is the mean distance of all point-pairs, 𝑑𝑚𝑎𝑥 and 𝑑𝑚𝑖𝑛 are the largest and smallest distance respectively. Secondly, the matched point-pairs whose curvatures do not satisfy Eq(4), are eliminated from the remaining point-pairs after the first step. { ∅min𝑖 = |𝑘1(𝑝𝑖)−𝑘1(𝑞𝑖)| |𝑘1(𝑝𝑖)+𝑘1(𝑞𝑖)| ≤ 𝜀1 ∅max𝑖 = |𝑘2(𝑝𝑖)−𝑘2(𝑞𝑖)| |𝑘2(𝑝𝑖)+𝑘2(𝑞𝑖)| ≤ 𝜀2 𝜀1 = ∑∅min𝑖 𝑁 𝜀2 = ∑∅max𝑖 𝑁 (4) Where 𝑘1(𝑝𝑖) and 𝑘2(𝑝𝑖) are the minimum and maximum values of the normal curvature at point 𝑝𝑖. Only the remaining point-pairs after the two steps are considered into the subsequent alignment process. 3.4 The improved ICP algorithm The steps of the improved ICP algorithm can be shown as follows. (1) Get the preliminary registration with RANSAC algorithm based on co-planar 4-points set; (2) Re-sample the target point cloud P. In this study, 20% points of P is left to keep its characteristics; (3) For each point 𝑝𝑖 of the 20% points of P, search its matching point 𝑞𝑖′ in Q based on the double-direction normal projection. And then eliminate erroneously matched point-pairs based on rigid distance constraint and curvature features constraint as described in section 3.3. (4) Estimate the transformation matrix 𝐻𝑘 = [ 𝑅𝑘 𝑇𝑘 0 1 ] based on the remaining matched point-pairs by minimizing the objective function, where R is a 33 rotation matrix and T is a 13 translation matrix; (5) Update P with the equation 𝑃′ = 𝐻𝑘𝑃 = 𝑅𝑘𝑃 + 𝑇𝑘; (6) If the difference of the registration error between two adjacent iterations meets the requirement as in Eq (5), the iteration ends and the registration is considered completed; if not, go back to step (2) and do iteration again. | 𝑑𝑘+1−𝑑𝑘 𝑑𝑘−𝑑𝑘−1 | < 𝜏,(𝑑𝑘 = 1 𝑁 ∑ ‖𝑅𝐾𝑃𝑖−1 + 𝑇𝐾 − 𝑃𝑖−1′‖ 2𝑁 𝑖=1 ) (5) Where τ is a given threshold based on experience. 4. Simulation and analysis Two group point clouds of free-form surface (where the point number of reference point cloud is more than that of target number) were used for simulation in the Matlab software with Intel Pentium Dual CPU and 2 GB memory. τ and δ were set as 0.1 and 0.5 respectively based on empirical experience. Figure 6-8 shows the results of the main registration steps. Figure 4 shows the best co-planar 4-points sets found in the two free-form surfaces with RANSAC algorithm for preliminary registration. The rigid matrixes were finally calculated based on these two sets. And the preliminary registration results conducted using these matrixes is displayed in Figure 5. As indicated in Figure 5, the RANSAC algorithm based on co-planar 4-points proposed for preliminary registration brought the majority of the point data close to the registration requirements, but the fine registration is still in needs. The accurate registration took the preliminary registration results as the new initial positions. And the results which fundamentally satisfied the registration accuracy are shown in Figure 6. In addition, comparisons were made in this paper among “the traditional preliminary registration algorithm” based on features (Ko and Maekawa, 2003), “RANSAC algorithm based on co-planar 4-points” proposed for preliminary registration by this study, “the traditional preliminary registration algorithm + the traditional ICP algorithm” and “RANSAC algorithm based on co-planar 4-points + the improved ICP algorithm” both proposed by the paper. Table 1 and Table 2 list the registration uptime and errors of with these algorithms. As shown in the tables, there are almost no difference in registration accuracy between the traditional preliminary registration algorithm and the one proposed in this paper. But for traditional one, it is more time-consuming in terms of the calculation on the curvature of every point of the point cloud. It is also shown in tables that the registration speed and accuracy of the improved ICP algorithm are better than the traditional one. 472 http://dict.youdao.com/w/iteration/ http://dict.youdao.com/w/iteration/ Figure 4: Co-planar 4-points sets Figure 5: The results of preliminary registration Figure 6: The results of accurate registration Table 1: Registration Comparison of the first group of point cloud surfaces Algorithm the point number of Q the point number of P Registration uptime (s) Registration error (mm) The traditional preliminary registration algorithm 21780 18139 95.284 0.0945 RANSAC algorithm based on co-planar 4-points 45.250 0.0820 traditional preliminary registration algorithm + the traditional ICP algorithm 103.413 0.0078 RANSAC algorithm based on co-planar 4-points + the improved ICP proposed 60.128 0.0052 Table 2: Registration Comparison of the second group of point cloud surfaces Algorithm the point number of Q the point number of P Registration uptime (s) Registration error (mm) The traditional preliminary registration algorithm 205.613 0.0982 RANSAC algorithm based on co-planar 4-points 94.339 0.1056 The traditional preliminary registration algorithm + the traditional ICP algorithm 82800 36340 476.912 0.0128 RANSAC algorithm based on co-planar 4-points +the improved ICP proposed by the paper 228.108 0.0096 5. Conclusions A RANSAC algorithm based on co-planar 4-points sets was proposed which could be employed before accurate registration to provide smaller registration error and accelerate the convergence speed. The 473 simulation results is in good agreement with the work (Papazov and Burschka, 2010). It was established that registration algorithm based on RANSAC framework has better robustness against noise, and could make good registration accuracy. Compared with the traditional ICP algorithm, the improved ICP algorithm proposed by the paper not only reduces the registration time which is important for the application in the production line, but also improves the accuracy of registration as well. The paper improved the key conditions about the study (Lu and Zheng, 2015) in detail, did new simulations and got more satisfying results. However, in order to provide a reliable position and orientation reference for flow-line production, the application system and the improvement of the algorithm require further study. Acknowledgments We thank the support from the Graduate Student Innovation Project for Common College in Jiangsu Province, China（No.CXLX11-0566). References Besl, P. J., Mckay, N. D., 1992, A method for registration of 3-d shapes, IEEE Transactions on Pattern Analysis & Machine Intelligence, 14(2), pp. 239-256, DOI: 10.1109/34.121791 Chen, C. S., Hung, Y. P., Cheng, J. B., 1999, RANSAC-based DARCES: a new approach to fast automatic registration of partially overlapping range images, IEEE Transactions on Pattern Analysis & Machine Intelligence, 21(11), pp. 1229-1234, DOI: 10.1109/34.809117 Fischler, M. A., Bolles, R. C., 1987, Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography, Communications of the Acm, 24(6), pp. 381- 395, DOI:10.1016/B978-0-08-051581-6.50070-2 Ko, K. H., Maekawa, T., Patrikalakis, N. M., 2003, An algorithm for optimal free-form object matching, Computer-Aided Design, 35(10), pp. 913-923, DOI: 10.1016/S0010-4485(02)00205-1 Lu, Z. P., Zheng, H., Sha, C. F., Li, M. Z., 2015, Point cloud registration algorithm based on free-form surface. Jiangsu Daxue Xuebao, 36(3), pp. 319-323, DOI: 10.3969/j.issn.1671-7775.2015.03.013 Meng, Y., Zhang, H., 2011, Registration of point clouds using sample-sphere and adaptive distance restriction, Visual Computer, 27(6-8), 543-553, DOI: 10.1007/s00371-011-0580-0 Papazov, C., Burschka, D., 2010, An Efficient RANSAC for 3D Object Recognition in Noisy and Occluded Scenes, Computer Vision – ACCV 2010, Springer Berlin Heidelberg, pp. 135-148, DOI: 10.1007/978-3- 642-19315-6_11 Rusinkiewicz S., Levoy M., 2001, Efficient Variants of the ICP Algorithm, International Conference on 3D Digital Imaging and Modeling, Quebec City, Canada, 1, pp. 145-152, DOI:10.1109/IM.2001.924423 Senin, N., Colosimo, B. M., Pacella, M., 2013, Point set augmentation through fitting for enhanced icp registration of point clouds in multisensor coordinate metrology, Robotics and Computer-Integrated Manufacturing, 29(1), pp. 39-52. DOI: 10.1016/j.rcim.2012.07.003 Sharp, G. C., Sang, W. L., Wehe, D. K., 2002, ICP registration using invariant features, IEEE Transactions on Pattern Analysis & Machine Intelligence, 24(1), 90-102, DOI:10.1109/34.982886 Urfalıoḡlu, O., Mikulastik, P., Stegmann, I., 2006, Scale Invariant Robust Registration of 3D-Point Data and a Triangle Mesh by Global Optimization, Advanced Concepts for Intelligent Vision Systems, Springer Berlin Heidelberg, DOI: 10.1007/11864349_96 Wang, X., Zhang, M. M., Xiao, Y. U., Zhang, M. C., 2012, Point cloud registration based on improved iterative closest point method, Optics & Precision Engineering, 20(9), 2068-2076, DOI: 10.3788/OPE.20122009.2068 Xie, Z. X., Shang, X. U., 2010, A survey on the ICP algorithm and its variants in registration of 3d point clouds, Periodical of Ocean University of China, 40(1), pp. 99-103, DOI: 10.3969/j.issn.1672- 5174.2010.01.019 Zhou, C. Y., Yong, L. I., Zou, Z. R., 2011, Three-dimensional cloud ICP algorithm improvement, Computer Technology & Development, 21(8), pp. 75-81, DOI: 10.3969/j.issn.1673-629X.2011.08.019 474 http://dict.youdao.com/w/line/ http://search.cnki.com.cn/Search.aspx?q=supported%20by%202011%20Innovation%20Project%20for%20Graduate%20Student%20from%20Common%20College%20in%20Jiangsu%20Province:%20CXZZ11-0293 http://search.cnki.com.cn/Search.aspx?q=supported%20by%202011%20Innovation%20Project%20for%20Graduate%20Student%20from%20Common%20College%20in%20Jiangsu%20Province:%20CXZZ11-0293 http://dx.doi.org/10.1109/34.121791 http://dx.doi.org/10.1109/34.809117 http://dx.doi.org/10.1016/B978-0-08-051581-6.50070-2 http://dx.doi.org/10.1016/S0010-4485(02)00205-1 http://dx.doi.org/10.1016/j.rcim.2012.07.003 http://dx.chinadoi.cn/10.3969%2fj.issn.1672-5174.2010.01.019 http://dx.chinadoi.cn/10.3969%2fj.issn.1672-5174.2010.01.019 http://dx.chinadoi.cn/10.3969%2fj.issn.1673-629X.2011.08.019