# Fast Cylinder Shape Matching Using Random Sample Consensus in Large Scale Point Cloud
## 2 Related Research  
In general, to estimate an object, a mathematical primitive (parametric shape) is used and accessed through RANSAC [3], Hough transform, or a machine learning algorithm. [PERSON] estimated spherical structures using Hough transform. In order to speed up the computation, the authors proposed a method to increase speed and maintain accuracy by partially performing the calculation without searching the entire point cloud [4]. [PERSON] estimated the roof through RANSAC. The authors proposed a multi model fitting method by applying [PERSON] rule and  
Figure 1: (**a**) Model recognition preprocessing process; (**b**) region growing segmentation [1]. a PCA algorithm to extend plane fit [5]. [PERSON] proposed a mathematical definition of various basic shapes to be applied to RANSAC and a primitive shape decomposition algorithm for estimating objects containing basic shapes in order to apply basic shape fitting to robot grasping [6]. [PERSON] used Hough transform to estimate cylinder shape. Cylinder estimation requires a 5D Hough transform, which is computationally inefficient and generally computed separately in 2D and 3D. The authors proposed a multiple cylinder detection method using a coarse-to-fine approach and a clustering algorithm [7]. [PERSON] proposed a method of evaluating 3D point cloud histograms through support vector machine (SVM), which is the most similar to the model in the database [8]. [PERSON] first extracted and removed the data vertically and horizontally from the ground, called T1 and T2. After that, Hough transform was used to project a plane on the normal vector and propose a cylinder shape estimation method through circle fitting [9; 10; 11]. [PERSON] determined the central axis of the pipe by the skeleton extraction algorithm through Laplacian smoothing and estimated the curved region and the T shape of the cylinder by dividing [12]. [PERSON] classified meaningful data through fast point feature histogram (FPFH) and SVM and segmented it with the classical flood-fill algorithm. Matching was completed through RANSAC in the segmented data. However, the proposed method found only relatively complex shapes such as ball valves and flanges, because those have unique feature points. In other words, a unique feature point is needed for histogram comparisons [13]. [PERSON] extracted primitive models using FPFH in point clouds and recognized objects through Adaboost with library models. The recognition object is merged/adjusted based on directionality and start/end position, and the automatic modeling is completed. However, it takes more than 30 minutes for 10 million pieces of data [14]. [PERSON] computed one plane of normals on the Gaussian sphere after normal estimation through RANSAC. Projection of segmented points on the plane estimates the radius and length of the cylinder. If there is an intersection point with another cylinder through the estimated starting and ending points of the cylinder, it is judged as an elbow. Experimental results show relatively accurate results, but it required a lot of execution time [15]. In the existing study, SVM and the method using RANSAC could extract the cylinder shape, but the center axis and the radius could not be confirmed. To solve this problem, the Hough transform was used. The Hough transform is excellent in terms of accuracy but requires a large amount of computation and a segmentation process. In addition, it has the disadvantage of requiring a lot of resources compared with RANSAC. Partitioning is a method of gradually searching for neighboring points and sorting out a group that meets certain criteria. As the point cloud grows, the execution time increases. Therefore, in a point cloud with a large number of points, object estimation requires a relatively large opportunity cost. In order to overcome these disadvantages, constraints are used to filter the data through vertical/horizontal conditions with the ground. Therefore, data filtering using constraints is inevitable in matching pipes with oblique lines.