# Primitive Shape Fitting in Point Clouds Using the Bees Algorithm
## 2 Literature Review  
The HT aims to fit primitive shapes to sets of points in the scene. Primitive fitting is regarded as a search problem in the space of the shape parameters, and sequential search algorithms are typically used to find the instances that include the largest number of points. The HT is widely used in machine vision [9], but is computationally demanding and becomes rapidly inefficient as the number of parameters needed to define the shape increases. As a consequence, the HT has been mainly used to fit elementary shapes such as lines and circles [10]. Only a few implementations of the HT transform were proposed for 3D primitive shape recognition, either based on parameter search heuristics [11], or customising the search to detect one particular instance of shape [12]. Alternative methods to the HT [13] have been developed to fit geometric primitives to point data, often based on robust statistical estimation of the shape parameters. The RANSAC algorithm randomly picks from the scene minimal sets of points that uniquely define a given type of geometric primitive. Candidate shapes are tested against all points, and the shape that approximates the largest number of points is extracted. The procedure is then sequentially repeated on the remaining data. RANSAC approaches have shown promising results for 3D scenes in terms of accuracy and efficiency [14; 15], and were shown able to fit candidate primitives in environments of 90% noise with little error [15]. Advanced subroutines can be applied to pre-emptively terminate bad hypotheses [16]. Much effort has been dedicated to optimise RANSAC sampling (OP-RANSAC) and shape evaluation efficiency (R-RANSAC): OP-RANSAC has shown \"substantial speedup for highly contaminated sets\" with as much as 96% noise [17], whilst R-RANSAC has been shown to run 2-10 times faster than standard RANSAC [18]. By combing these optimisation strategies, some forms of RANSAC were able to fit primitive shapes to a field of millions of points in less than one minute [15]. The success of RANSAC greatly depends on the trade-off between accuracy and computational complexity, namely, by the number of candidate shapes evaluated. The results obtained using RANSAC are also sensitive to the setting for the tolerance threshold used to judge whether a data point is an inlier or an outlier to a given candidate shape. Some RANSAC implementations do not utilise tolerance threshold and score candidate shapes based on histogram analysis [19]. However, these implementations were usually tested only on PCs of varying levels of background noise (henceforth called noise, Figure 1), instead of the more deceptive case of local error (henceforth called error, Figure 1) which may arise from granularity or low precision of sensors. Some examples of EA methods for primitive fitting have been proposed. [PERSON] and [PERSON] (20); [PERSON] and [PERSON] (21) used a population of many possible shapes. Each individual (candidate solution) in the population represents the minimal set of points that uniquely define the primitive, whilst the fitness function counts the number of points inside a fixed boundary around the primitive. Similarly, [PERSON] et al. (22) used an EA for tackling a sub-task of the surface extraction problem. In this case the population of candidate solutions is composed uniquely of planes, and each individual represents the minimum set of points (three) needed to define a plane, sampled in a sub-region of the cloud. The optimisation strategy of the above EA approaches is clearly based on the RANSAC procedure, and still needs a careful setting of the approximation tolerance. [PERSON] et al. (23) tested one instance of swarm algorithm (24) and one instance of evolutionary algorithm (25) for object fitting. Each candidate solution encoded the six parameters defining a rigid transformation (rotation+translation) of a template _PC_ shape. The fitness function evaluated the difference between the rotated and translated template and the target shape.