<4D6963726F736F667420576F7264202D20DAE1ED20C7E1C8CFD1ED20E6C7CDE3CF20E6E3DAE433342D203432> Al-Khwarizmi Engineering Journal Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, Sptember, (2020) P. P. 34- 42 Pre-Processing and Surface Reconstruction of Points Cloud Based on Chord Angle Algorithm Technique Ali M. Al-Bdairy* Ahmed A. A. Al-Duroobi** Maan A. Tawfiq*** *,***Department of Production Engineering and Metallurgy/ University of Technology/ Baghdad / Iraq . **Department of Prosthetics and Orthotics Engineering / Al-Nahrain University/ Baghdad / Iraq . *Email: 70120@uotechnology.edu.iq **Email: ahmed_abdulsamii7@yahoo.co.uk *** Email:70057@ uotechnology.edu.iq (Received 6 March 2020; accepted 5 July 2020) https://doi.org/10.22153/kej.2020.07.002 Abstract Although the rapid development in reverse engineering techniques, 3D laser scanners can be considered the modern technology used to digitize the 3D objects, but some troubles may be associated with this process due to the environmental noises and limitation of the used scanners. So, in this paper a data pre-processing algorithm will be proposed to obtain the necessary geometric features and mathematical representation of scanned object from its point cloud which obtained by a (Matter and Form) 3D’s laser scanner through isolating the noised points. The proposed algorithm based on continuous calculations of chord angle between each adjacent pair of points in points cloud. MATLAB program has been built for perform the introduced algorithm which implemented using a suggested case studies with cylinder and dome shape. The resulted point cloud from application the proposed algorithm, and the result of surface fitting for the case studies has been ensured the proficiency of the introduced chord angle algorithm in pre- processing of data points and clean the points cloud. Where the data percent which was deleted as noised data points according to proposed chord angle algorithm was arrived to (81.52%) and (75.01%) of the total data points number in points cloud for first and second case studies, respectively. Keywords: Chord Angle Algorithm, Point Cloud, Surface Reconstruction. 1. Introduction As result to developments of 3D laser scanners in previous years, were pushed the interesting to obtain a surfaces representations and reconstructions of the 3D parts from its points cloud was obtained by such techniques. However, this points cloud is involving some unnecessary and noisy data points, due to the resolution of some scanners and the reflectivity property of the scanned surfaces, also the contrast problems. Point cloud acquiring using a 3D laser scanner may be contained more information for a ten of thousands of massive data, so that, the huge data points in cloud which used to surface model reconstruction, subsequent processing, and storage, represent the main difficulties in 3D laser scanning process [1]. In other word, not all of the data points can be used in follow-up process. Therefore, there is need to extract only the data point clouds which reflect the surface of scanned shape, and removing the redundant data points. Therefore, it’s essential to determine the noisy data and delete it for the points cloud set, as manner to gives the pretty representations of the 3D scanned surfaces, and remining the required geometrical features for surface. So, that, the pre-processing of 3D points cloud and reconstruction of surface from these points cloud, has more attention of researchers in this domain. Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 35 Many researchers showed in their literatures different algorithms for simplification of data points obtained from 3D laser scanners. J. Liu et al [2] proposed an effective and simple reconstruction algorithm based on interpolation of B-spline surfaces of blade surface by section curves with less acquired points, to improve the aerodynamic performance for the blade surfaces. The less acquired points of the section curves were gritted using the Coordinate Measuring Machine. B. Cyganek et al [3] proposed an approach for classification of multidimensional data to allow complex structures processing. This method is depended on a tensor kernel which applied to train of the Support Vector Machines (SVM) and Sequential Minimal Optimization (SMO) also based on a kernel of chord distances. M. Xiao et al [4] provided a surface flattening algorithm to detect the damage or deterioration on the tunnel’s inner wall, started with the reconstruction of surface triangular mesh from the 3D point cloud data, based on mechanics revision to ensure the railway of transportation operations. Z. Kang et al [5] proposed an interpolation approach to extract the central axis and wall cross-sectional points of the tunnel, that depended on the quadric parametric surfaces fitting using the 2D projections of the points cloud with curves fitting to obtain the tunnel central axis, also the intersections of arbitrary straight lines to tunnel points cloud was used to getting the cross- sectional surfaces. F. Bernard et al [6] presented a methodology for object’s shape or surface reconstruction from a given sparse surface points using a statistical shape model (SSM) which represented by surface mesh and a point distribution model (PDM). The methodology classified the given points according to the surface normal based on surface-based fitting process, using Gaussian Mixture Model (GMM). D. Xia et al [7] performed numerical and analytical investigations to reduce the noise data properties for regions-of-interest (ROI), and reconstruct the images based on chord image reconstructions using different scanning configurations. S. Gauthier et al [8] proposed a method based on analyze and segment the digitized 3D surface mesh curvature histogram using a real object through detecting the peak and valley primitives, also proposed to use the curvature histogram analysis to measure the quality of mesh for a lot of reverse engineering steps, which could be used to construct the CAD model. C. Mineo et al [9], suggests a filtering approach to identify the boundary points and spatial procedure that use Fast Fourier Transform (FFT), the approach generate the tessellated surfaces directly without noise from the points cloud data by detecting the points of the sharp and creases edges. K. W. Lee and P. Bo [10] introduce a procedure to reconstruction the feature curves by intersections of determined strip pairs to approximates the regions beside the features to obtain a smooth feature curves from points cloud of model. A. Duroobi et al [11] presented a practical method to obtain the control points to derive a representation equation for the profile using Bezier technique from a huge data as a reverse engineering application, also the author used the image modifications process by Solid Work package to perform the dimensional comparison. D. A. Mahmood et al [12] proposed a method for determining the measuring positions of CMM probe which was depend on the Articulated Arm Coordinate Measuring(AACMM)Machine and kinematics calculations of the used robot, it’s found the proposed method was accurate and precise and eliminate the design error effects. Due to the problems which associated to the 3D scanning process there are some of un necessary information data need to be manipulated. So, present work proposes a data point cloud pre-processing algorithm which based on calculation of the chord angle for simplifying the stream lines of point cloud. Which will be acquired using a 3D laser scanner, to determine the necessary points for representing the geometrical information of the scanned object. Also, to detect and neglect the noisy points in point cloud, then obtaining the real surface representation equations which of the selected case studies as a benefit of reverse engineering domain. The introduced paper is organized as follows, section 2 divided into two subsections; section-I covers a short review on the chord angle algorithm methodology, and subsection-II presents the detail of the proposed algorithm and its implementation in MATLAB environment. Section 3 tests the validity of the proposed algorithm through the selected case studies. Sections 4 records and analyzes the results obtained for selected case studies. Finally, section 5 presents evaluation and conclusion of the proposed algorithm in according to the obtained results. Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 36 2. Chord Angle Algorithm The chord angle algorithm is simplest and more effective algorithm to manipulate the obtained points cloud by the 3D laser scanners to determine the noisy points. The algorithm is based on calculating the maximum chord angle value between each pair of adjacent points in point cloud. Then compare this value with precomputed allowed permissible chord deviation angle (∆α). I. Chord Angle Algorithm Methodology The chord angle will be calculated continuously between each set of three adjacent points (Po, P1, and P2), and the value of each calculated angle will be compared with the preset value of chord angle(∆α). Whether the value of angle (α) is smaller than or equal to (∆α) such as (αo) and (α1), the set of adjacent point will be recorded as the needed points, while if the value of angle (α) is larger than (∆α) such as (α2), then the middle point(P3) will be neglected as a noise point and taken the points (P2, P4, andP5) to calculate the next chord angle, this procedure illustrated in figure 1. The process will be proceeded until all data point included in the sequence. Figure 2 illustrates the difference between chord height and chord angle where for the same set of three adjacent points it could be have the same value of chord height but it has a different chord angle, depending on the distance between each two point in point cloud. Where the chord height (ho) term for a set of points represent the shortest distance between Pi+1 and the line that connect the Pi and Pi+2. Fig. 1. Demonstrate the Chord Angle Algorithm. Fig. 2. The Different Chord Angles for the Same Chord Height. As result to application the chord angle algorithm the noise or scattered points can be detect and ignore from the resulted point cloud. The chord angle algorithm can be applied by sequential steps as shown in figure 3 which are: • Input the row point cloud • set the iteration i for the points in point cloud • Set the allowable value of chord angle (∆α), depending on accuracy that adopted. • Construct the vectors V1 and V2 between the points P0, P2 and P1, P2 respectively as [13]. …(1) …(2) Where: (xo, yo, zo), (x1, y1, z1), and (x2, y2, z2) are the coordinates of the first, second and third point respectively in the point cloud. • Compute the dot product between the vectors V1 and V2 as …(3) • Compute the angle(α) between V1 and V2 vectors using the formula …(4) P2 P1 P0 P’0 ho d0 d’0 α α'0 P3 Po P1 P2 P3 α o α 1 α 2 Noise point Noised curve Not noised P4 P5 Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 37 Fig. 3. Flowchart for proposed Chord Angle Pre-Processing Algorithm. • If α1≥(∆α), save P1, then go to next assessment, and calculate the height of chord P1P2P3 according to the same procedure and carry on assessment, • If α1<(∆α), delete P1, and calculate the chord angle of point set PoP2P3, namely α2. • Proceed process until the last point (n) of the scanning line. These points which don’t accord with the requirement of chord angle value will be neglected. II. Proposed Program of the Chord Angle Algorithm A MATLAB program is constructed to achieve the methodology of the adopted chord angle simplifying algorithm. Figure 3 illustrate the flowchart and general steps of the proposed program, where the constructed program begin to receiving the data points as a points cloud which acquired using a 3D laser scanners devices. Then compute the allowable chord angle value automatically within the program, after that the chord angle for each set of three adjacent points in point cloud will be computed using the illustrated methodology procedure in section I. Input the data point Pi, Pi+1, Pi+2,..., Pn |∆α | ≤ αi Input value of allowable chord height (∆α) Determine the equations of vectors V(i),V(i+1),…., Compute the dot product of each neighboring vectors Eq. (3) Find the angle (αi) between the neighboring vectors Eq. ( 4) i=i+1 Delete Pi+1 save Pi+1 i=i+1 Let iteration (i)=1 Start End Yes No i ≥ n Yes No Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 38 Finally, the decision will be made according the comparison between the calculated and allowable chord angle assessment. 3. Suggested Case Studies To prove the effectiveness of the adopted algorithm for pre-processing the point cloud, two case studies with shape cylinder and dome were selected as shown in figure 4 and figure 5. The case studies had been scanned by a laser scanner device named (Matter and Form). The output scanning file of the studied case studies were saved as points cloud of data point with format (‘file name’. xyz) in 3D’s coordinate by the scanner software ‘Matter and Form’, then the output file was processed in ‘Excel’ program to save in (.xlsx) format, after that the file has been opened within ‘MATLAB’ program to perform the pre-process with the chord angle algorithm and saved as a data file (‘file name.dat.’). The file of the first case study (cylinder) has been involved (527884) as total points number of in the, after completing the scanning process, while the file of second case study (dome) has (1082908) as the total points number. Fig. 4. Cylinder Case Study. Fig. 5. Dome Case Study. Figure 6 shows the scanned shape of the first case study (cylinder) after completing scanning process, while figure 7 illustrates the scanning process of the second case study that is contained an unperfect and loosed scanning data, also presence a noise points. The purpose of the proposed simplifying algorithm is to identifying and deleting the noisy points which is appear in figure 6 and figure 7 as red points, which are needed to processed and deleted with respect to the criteria of the adopted algorithm. Fig. 6. Noise Points in Cylinder Case Study. Fig. 7. Noise Points in Dome Case Study. Scanner device Case study Calibration board Case study Case study Scanner device Case study Calibration board Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 39 4. Results and Discussions From the results of application of the proposed chord angle algorithm for simplifying the points cloud, the first file belong to cylinder case study was contains only(97528) total points, for just single pre-processing attempt also the noise points percent was equal to (81.52%), which was ignored as an unrequired points, while the dome case study file was contains (270532) points and the deleted points percent become (75.01%), when executing the adopted algorithm for one attempts. These results of the selected two case studies proved the effectiveness of the adopted algorithm to simplifying the data points through identifying and deleting the unrequired noisy points. This indicates that the adopted algorithm is very efficient to simplifying the data points and deleting the unnecessary noisy points. The final result of the simplifying process for the proposed case studies is shown in figure 8 and 9 for the point clouds of the two selected case studies. Fig. 8. Cloud Points for Cylinder Case Study. Fig. 9. Cloud Points for Dome Case Study. The obtaining point clouds which were resulted from application the introduced chord angle algorithm were used to gives the surface representations of the studied case studies using the facilities of MATLAB program. And the resulted equations for fitting 1- Cylinder case study: 3D degree of an linear polynomial for x and y direction: …�5� the Coefficients of the polynomial are inserted in Table 1. Table 1, Coefficients of Polynomial of the First Case Study (Cylinder). 2- Dome case study : 3D degree of linear polynomial equation for x and y direction: …�6� Coefficient p00 p10 p01 p20 p11 p02 p30 p21 p12 p03 Value 0 .5 5 8 7 - 0 .1 9 1 6 0 .2 5 0 .0 5 7 6 3 -0 .0 0 6 8 6 4 0 .0 5 5 9 3 0 .0 0 0 1 2 8 - 0 .0 0 1 3 1 4 0 .0 0 0 4 4 0 2 -0 .0 0 0 3 8 Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 40 And the polynomial coefficients are listed in Table 2. Table 2, Coefficients of Polynomial of the Second Case Study (Dome). After achieving the pre-processing algorithms for the proposed case studies, and completing the simplification process, a surface reconstruction process for intended case studies was done with facilities which associated within MeshLab program as shown in figures 10 and 11 for cylinder and dome respectively. Fig.10. Reconstructed Surface Model of Cylinder Shape Case Study. Fig. 11. Reconstructed Surface Model of Dome Shape Case Study. 5. Conclusions Acquiring process of 3D data by a 3D modern laser scanners devices is important to regeneration process of parts as a reverse engineering application, but there is some unclear detailed data, such as noisy points in obtained points cloud of the scanned parts, which associated to the scanning process. So, it’s necessary to process and simplify the obtained data from these devices using a number of simplifying and pre-processing approaches. The introduced paper, present a data pre-processing and simplifying algorithm to extract only the required points to generate the geometrical representations of scanned parts, the adopted algorithm depended on the sequential calculations of chord angle value for each set of three contiguous points in the points cloud. The obtained results by the surface fitting, and the percent of detected noisy points were illustrated that, the adopted algorithm was very efficient in pre-processing and simplifying the points cloud for any other case study. The total points number of the first suggested case study (cylinder) was (527884) points which becomes (97528) points after applying the adopted chord angle algorithm, and the deleted points percent was about (81.52%), of total number of data points, while the scanned file of the second case study (dome) was involved (1082908) points, then the points number becomes (270532) after applying the adopted chord angle algorithm, with proficiency (75.01%). Coefficient p00 p10 p01 p20 p11 p02 p30 p21 p12 p03 Value 0 .0 2 0 1 0 .4 4 0 3 0 .0 7 0 8 2 0 .0 6 5 2 7 -0 .0 0 1 3 0 7 0 .0 6 8 8 4 -0 .0 0 0 3 1 6 7 -0 .0 0 0 4 8 9 7 -0 .0 0 0 4 6 4 3 -0 .0 0 0 4 7 3 1 Ali M. Al-Bdairy Al-Khwarizmi Engineering Journal, Vol. 16, No. 3, P.P. 34- 42 (2020) 41 6. References [1] G. Wang, Y. Lv, N. Han, and D. Zhang, “Simplification Method and Application of 3D Laser Scan Point Cloud Data’’, International Conference on Mechanical Engineering and Material Science, MEMS, 2012. [2] J. Liu, J. Zhao, X. Yang, J. Liu, X. Qu, and X. Wang, “A Reconstruction Algorithm for Blade Surface Based on Less Measured Points”, Hindawi Publishing Corporation, IJAE, International Journal of Aerospace Engineering, Vol. 2015, Article ID 431824, 2015. [3] B. Cyganek, B. Krawczyk, and M. Woźniak, “Multidimensional Data Classification with Chordal Distance Based Kernel and Support Vector Machines”, Elsevier, EAAI, Engineering Applications of Artificial Intelligence, Vol. 46 pp. 10–22, 2015. [4] M. Xiao, Z. Qi, and H. Shi, “The Surface Flattening based on Mechanics Revision of the Tunnel 3D Point Cloud Data from Laser Scanner”, Elsevier, Procedia Computer Science, Vol. 131, pp. 1229–1237, 2018. [5] Z. Kang, L. Zhang , L. Tuo, B. Wang and J. Chen, “Continuous Extraction of Subway Tunnel Cross Sections Based on Terrestrial Point Clouds “, Remote Sensing journal, Vol. 2072-4292, pp. 857-879, 2014 . [6] F. Bernard et al, “Shape-aware Surface Reconstruction from Sparse 3D Point-Clouds”, https://github.com/fbernardpi/sparsePdmFi tting 2016. [7] D. Xia et al, “Noise Properties of Chord-Image Reconstruction” IEEE Transactions on Medical Imaging, Vol. 26, No. 10, 2007. [8] S. Gauthier, W. Puech, R. Bénière, and G. Subsol, “Analysis of Digitized 3D Mesh Curvature Histograms for Reverse Engineering”, Elsevier, Computers in Industry, Vol. 82, pp. 67–83, 2017. [9] C. Mineo, S. G. Pierce, and R. Summan, “Novel Algorithms for 3D Surface Point Cloud Boundary Detection and Edge Reconstruction’’, CDE, journal of Computational Design and Engineering, Vol. 6, pp. 81–91, 2019. [10] K. W. Lee, and P. Bo, “Feature Curve Extraction from Point Clouds via Developable Strip Intersection”, Elsevier, journal of Computational Design and Engineering, Vol. 3, pp. 102–111, 2016. [11] A. Duroobi et al, “Reverse Engineering Representation Using an Image Processing Modification’’, Baghdad University Al- Khwarizmi Engineering Journal, vol. 15, pp. 56-62 , 2019. [12] D. A. Mahmood et al, “Improving Reverse Engineering Processes by using Articulated Arm Coordinate Measuring Machine’’, Baghdad University Al-Khwarizmi Engineering Journal, vol. 16, pps. 42-54 , 2020. [13] P. Comninos, “Mathematical and Computer Programming Techniques for Computer Graphics”, Springer, Verlag, London, 2006. � ا���ري� �� � 3ا���د، ����16 ا���ارز�� ا���� �� ا����� ��� ��� ،42 -34 )2020( 42 د �� ��ارز����!�" #� ا��. ط وا� دة *()�' ا�&%�ح # ��� ا��&�.� �&� ا�� *.��� زاو/� ا��*( � ا���/(ي* � �� 7 � #� *�5�6*** ** � ��� ا�&��4 ��� ا��ھ ب ا��رو#�ا1� ��� ��� ا��7اق/ 5�4�& ا�#3(012�2&/ /.)اد-,+ ھ()'& ا%$#�ج وا� ��دن /ا�*،*** ا��7اق/ $)/ 1�4�& ا�(?7<=/ /.)ادا�>(�;0& وا� ,�ھ()'& ا:ط7اف ,+- ** 70120@uotechnology.edu.iq :A$7<) ا%�3#7وBا�* ahmed_abdulsamii7@yahoo.co.uk :A$7<) ا%�3#7وBا�** 70057@ uotechnology.edu.iq و$A:*ا�7B<) ا7#3�%** �� ا��8 +C7��/ (D#, ا� &E>(Fا� ��ت ا�0L2M& ا�J0Kر<& 0GHG& ا:/��د ا�012�2)3#F'��ر ا� B#;0,3& ، < 3= ا�ت ا�?()'& ا��0)OP AQ R>7,2ر ا�S#4& �7- (& 4= ا� T0Bء ا��V2Mا� WB,/ &0K �ه ا�Yھ ZQ7اP A#ا� [\��ت ا�0L2M& ا� ,#a�Y� .&4(D ، ا1%,�م 0GHG& ا:/��د ، و�23P (- =3ن ھ(�ك /�^ ا� [F'�0& وF4)دات ا� Dا� cK; 2ل �ً0L2V +P A#0& ا�SO)ا� k#/�F' =4P�?K02T ا� &B,)اھا��?�� Q0& وL�V2V ط�O)\) cإ� &o7#O 7 ا�P22ارز04& زاو<& ا�D� �ًOت ٧٥.٠١٪) و (٨١.٥٢�$�0Bط ا��O$ د(; A��٪) 4= إ1 &0SO)ا� &/�F,ا� AQ&0'ا�)را &��FK� Aا�#2ا� cK; &0$�Eوا� cا:و�.