# Sphere Fitting with Applications to Machine Tracking
### Related Work
#### 1.1.4 Heuristics for Circles Detection in \(2d\) Images  
Most significant work has been done for two Dimensional data in the context of image processing. Extensive work tends to compute circles for the purpose of object detection in images. However, most of these heuristics do no provide approximation guarantees and suitable only for \(d=2\). A common heuristic to fit points to a circle is the well-known Circle Hough transform (CHT) [13]. The approach of this technique is to find imperfect instances of spheres by a voting procedure. This voting rates candidates of possible spheres (i.e., center and radius). The main drawback of this technique is its inefficient running time of complexity \(O(n^{d})\). In [14], a circle detection was applied by Learning Automata (LA), which is a heuristic method to solve complex multi-modal optimization problems. The detection process is considered a multi-modal  
Figure 1: An RGB image that captured a flame of fire [12]. The goal is to approximate the center of the flaming ring. optimization problem, allowing the detection of multiple circular shapes through only one optimization procedure. The drawbacks of this algorithm is that it is designated to \(2D\) images. A variant of a Hough transform algorithm, called EDCircles [15], aims to approximate points by arcs which are based on their Edge Drawing Parameter Free (EDPF). The general idea of the algorithm is to extract line segments in an image, convert them into circular arcs and then combine these arcs to detect circles, which is performed by an arc join heuristic algorithm with no approximation guarantees. Moreover, its running time is still inefficient when dealing with big data and large dimensional space (i.e., \(O(n^{d})\)) in the worst case. In [16], a circle detector based on region-growing of gradient and histogram distribution of Euclidean distances is presented. Region-growing of the gradient is applied to generate arc support regions from a single point. The corresponding square fitting areas are defined to accelerate detection and decrease storage. A histogram is then used to count frequency of the distances that participates in the accumulator and the parameters of each circle are acquired. In [17], the proposed detection method is based on geometric property and polynomial fitting in polar coordinates instead of Cartesian coordinates. It is tailored for two-dimensional LIDAR (laser radar sensors) data. They use Support Vector Machines (SVM) to detect the target circular object from natural lidar coordinates features representing segments from the image. For specific examples, they measure up to 99.79% detections with execution time of 16.9 milliseconds per image. A circle detection algorithm that is based on a random sampling of isosceles triangles (ITs) is presented in [18]. This algorithm provides a distinctive probability distribution for circular shapes using a small number of iterations. Although they introduced an accurate and robust detection at sharp images, it does not handle corrupted and moving images and does not have provable guarantees. Another variant of the Hough transform algorithm [19], called Vector Quantization (VQHT), tries to detect circles by decomposing their edges in the image into many sub-images by using Vector Quantization (VQ) algorithm. The edge points that reside in each sub-image are considered as one circle candidate group. Then the  
VQHT algorithm is applied for fast circle detection. In [20; 21], a randomized iterative work-flow is suggested, which exploits geometrical properties of isophotes in the image to select the most meaningful edge pixels and to classify them in subsets of equal isophote curvature. In [22], the authors propose a method to recognize a circular form using a geometric symmetry through a rotational scanning process. The random sample consensus (RANSAC) algorithm introduced by [PERSON] and [PERSON] in [23] is a widely used robust estimator that has become a standard in the field of computer vision.