# Primitive Shape Fitting in Point Clouds Using the Bees Algorithm
## 1 Introduction  
Point clouds (PCs) are widely used in machine vision and robotics to represent 3D scenes and objects sensed through laser scanning devices. Understanding PC models, and extracting concise and meaningful high-level descriptions such as the shape and properties of objects, is necessary for many industrial applications like robotic grasping and pick-and place [1; 2]. This ability is naturally acquired by humans and animals, but difficult to reliably automate [3], particularly in real-time applications where time and hardware limitations require very efficient procedures.  
This paper is concerned with the identification of the shape of objects in 3D PCs for robot manipulation. In many industrial applications, man-made artefacts can be associated with good approximation to a set of geometrical primitive shapes like spheres, boxes, and cylinders. The problem becomes then to fit these primitive shapes to clusters of points in PC models (the primitive fitting problem). Since PCs are composed of a very large number of points, the efficiency of the identification algorithms is of primary importance. At the same time, for the sake of generality, problem-specific assumptions should be limited.  
The primitive fitting problem is well known in the literature, and many of the solutions are based on two popular and very successful algorithms: the Hough transform (HT) [4] and random sample consensus (RANSAC) [5]. Given a 3D scene, the HT looks for parameterisations of primitive shapes that fit the largest number of data points. To increase the efficiency of the HT, the space of the parameterisations may be quantised, and in that case the granularity of the quantisation becomes an important parameter [6]. RANSAC randomly picks from the PC minimal sets of points that are used toparameterise candidate primitive shapes. RANSAC verifies the candidate shapes against the remaining points in the scene, and picks the instance that fits the largest number of points. An approximation tolerance is usually set to decide whether a point is an inlier or outlier to a given shape. The main limitations of the HT and RANSAC are their computational complexity, and the sensitivity of the results to the algorithm parameterisation (the quantisation of parameters in the HT, the approximation tolerance in RANSAC).  
The approach proposed in this paper is to tackle primitive fitting as a parameter optimisation problem. Similarly to the HT approach, the goal of the procedure is to manipulate the parameters of a given type of primitive to maximise its fit to the point data. The fit is measured by a primitive-specific fitness function which is used to guide the optimisation process. The bees algorithm (BA) [7] will be used as the parameter optimisation routine, and the results compared with those achieved using an evolutionary algorithm (EA) [8] and RANSAC.  
The main advantage of metaheuristics like swarm (bees algorithm) and evolutionary algorithms over standard primitive fitting techniques is the generality of the approach, which does not require prior scene knowledge (e.g., the noise level to set the approximation tolerance in RANSAC). These metaheuristics can be used to fit any kind of shape, as long as its goodness of fit can be defined via a fitness function. Thank to their intelligent sampling of the solution space, swarm and evolutionary algorithms are also computationally reasonably efficient.  
Section 2 presents a critical overview of the primitive fitting literature. Section 3 describes the bees algorithm, and the two control algorithms. Section 4 details the experimental method used, whilst Section 5 presents the experimental results. The results are discussed in Section 6, and Section 7 concludes the paper and outlines suggestions for further work.