# Direct Least Absolute Deviation Fitting of Ellipses

Authors: Gang Zhou; Kai Zhong; Zhongwei Li; Yusheng Shi
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Scattered data from edge detection usually involve undesired noise which seriously affects the accuracy of ellipse fitting. In order to alleviate this kind of degradation, a method of direct least absolute deviation ellipse fitting by minimizing theℓ1 algebraic distance is presented. Unlike the conventional ℓ2 estimators which tend to produce a satisfied performance on ideal and Gaussian noise data, while do a poor job for non-Gaussian outliers, the proposed method shows very competitive results for non-Gaussian noise. In addition, an efficient numerical algorithm based on the split Bregman iteration is developed to solve the resulting ℓ1 optimization problem, according to which the computational burden is significantly reduced. Furthermore, two classes of ℓ2 solutions are introduced as the initial guess, and the selection of algorithm parameters is studied in detail; thus, it does not suffer from the convergence issues due to poor initialization which is a common drawback existing in iterative-based approaches. Numerical experiments reveal that the proposed method is superior to its ℓ2 counterpart and outperforms some of the state-of-the-art algorithms for both Gaussian and non-Gaussian artifacts.


---

## Body

## 1. Introduction

Ellipse fitting is a fundamental tool for many computer vision tasks such as object detection, recognition, camera calibration [1], and 3D reconstruction [2]. A large amount of technologies have been developed for this issue and work well under the assumption that the fitting error follows a Gaussian distribution, among which Fitzgibbon’s direct least square fitting [3] has attracted a lot of attention due to its high accurateness, solution uniqueness, and fast and easy to use and has been regarded as the standardized landmark of ℓ2 fitting. Based on which, the scale normalization [4], robust data preprocessing for noise removal [5], optimization of the Sampson distance [6, 7], minimizing the algebraic distance in subject to suitable quadratic constraints [8, 9], and modeling the noise as a sum of random amplitude-modulated complex exponentials [10] and iterative orthogonal transformations [11] are launched. Although the performance has been improved to some extent, the inherit disadvantage of ℓ2 norm-based methods is that the square term will enlarge the influence of outliers and lead to a rough result. To overcome this shortcoming, the ℓ1 [12] and ℓ0 norms [13] are cited to address this issue; theoretically, it turns to be less sensitive to outliers for algorithms based on ℓp-norm 0<p<2, and the selection of iterative initial value is still pending yet. Given the advantage of ℓ1-norm and direct algebraic distance minimizing strategy, a natural way is to replace the ℓ2 item with ℓ1 in Fitzgibbon’s model thus comes out our ℓ1 model, and we will explore its efficacy in the following sections.


## 2. The Proposedℓ1 Minimization Model

### 2.1. Problem Modeling

For a general conic by an implicit second-order polynomial, it can be drawn as(1)FD,α=Dα=ax2+bxy+cy2+dx+ey+f=0,where α = abcdefT is denoted as the conic parameter, D = x2xyy2xy1T is the data point, for every point i=1,2,…,N, where N is the number of data points, and Diα is called the algebraic distance between the data point xi,yi and the conic FD,α=0; note that the symbol x stands for the absolute value of x. The sum of all algebraic distances at each point from 1 to N is(2)FD,α=∑i=1NDiα.In order to force the conic curve into an ellipse, the parameters of the conic curve should meet the necessary conditionsb2−4ac<0; for convenience, we take its subset 4ac−b2=1 instead [3], and its matrix form can be rewritten as αTCα=1, with(3)C=0020000−10000200000000000000000000000.Thus, the matrix form of the objectiveℓ1 minimization model is given as follows:(4)minαDα1s.t.αTCα=1.By introducing the Lagrange multiplierλ, the constrained problem can be turned into an unconstrained one as(5)arg minαDα1+λαTCα−1.


### 2.2. Numerical Aspects

Thus, our method is to seek optimalα that minimizes the cost function in equation (5). The difficulty in solving equation (5) is that the ℓ1 term is nondifferentiable and inseparable. To overcome this problem, we follow the method of Zhou et al. [14]. The split Bregman method is first introduced in [15] as a very efficient tool to solve the general ℓ1 -regularized optimization problems. The basic idea is to convert the unconstrained minimization problem in equation (5) into a constrained one by introducing one auxiliary variable s=Dα; this leads to the constrained problem:(6)arg minα,ss1+λαTCα−1s.t.s=Dα.We can approximate equation (6) by adding one penalty function term as done in [16] to obtain an unconstrained problem. This yields(7)arg minα,ss1+μ2s−Dα22+λαTCα−1,where μ is a positive penalization parameter. Finally, we strictly enforced the constraints by applying the split Bregman iteration [17] with a Bregman variable t to obtain two subproblems:(8)arg minα,s,ts1+μ2s−Dα−t22+λαTCα−1,(9)tk+1=tk+Dαk+1−sk+1.In order to further simplify the subproblems, we split equation (8) into two separate ones. We now investigate these subproblems one by one.(1)
Theα-related subproblem is(10)arg minαμ2s−Dα−t22+λαTCα−1.Note that it is a least-square problem. Thus, we can obtain a closed solution as follows:(11)αk+1=μDTsk−tkμDTD+2λC.(2)
Thes-related subproblem is(12)arg minss1+μ2s−Dα−t22.This type of problem can be effectively computed using the standard soft-threshold formula presented in [16].(13)sk+1=shrinkDαk+1+tk,1μ,where(14)shrinkx,r=xxmaxx−r,0.The complete procedure of minimization problem equation (5) with the split Bregman iteration is summarized in Algorithm 1, where nmax is the maximum number of iterations; to avoid the procedure falling into an invalid solution, the iteration stop criterion is set as the algebraic distance calculated on the (k + 1)-th iteration, Dαk+11 is greater than k-th Dαk1 or the iterations reach to the maximum.Algorithm 1:ℓ1-norm-based direct least absolute deviation ellipse fitting with split Bregman iteration (DLAD).
(1)
Setk=0,nmaxiter=300,μ=1,λ=1,t0=0,s0=DT−1⋅η,α0(2)
whileDαk+11<Dαk1&&k<nmax(3)
Solvesk+1 using (13)(4)
Solvetk+1 using (9)(5)
Solveαk+1 using (11)(6)
Setk := k + 1.(7)
end while(8)
returnαk(15)Jα=arg minαDα2+λ′αTCα−1.With the high development of the variational partial differential equation (PDE) in the field of image process, theℓ1-regularized PDE-based methods have gained more and more attention and turned out to be a promising approach for various applications such as denoise [18], destripe [19], deblur [20, 21], compressive sensing [22], and object tracking [23]. Though, the ℓ1-regularized model typically achieves a very competitive performance, however, we have to select its parameters carefully or else it may fall into a local extremum and results in an undesired outcome. Almost all PDE-based methods suffer from this defect, so it is difficult to be promoted in industrial environments. Considering the classical ℓ2 ellipse fitting [3, 24], it aims to minimizing the following energy functional:For it is a least-square problem, set∂J/∂α=0, and we have(16)DTD+λ′Cα=0.Comparing theℓ1 solution derived from equation (11) with the ℓ2 solution in equation (16), when it satisfies the following conditions,(17)μDTD+2λC≈DTD+λ′C,μDTsk−tk≈0,the initial solution of ℓ1 is close to ℓ2. Without losing generality, we set μ=1,λ=1,λ′=1, for(18)DTD=x4x3yx2y2x3x2yx2x3yx2yxy3x2yxy2xyx2y2xy3y4xy2y3y2x3x2yxy2x2xyxx2yxy2y3xyy2yx2xyy2xy1,where x, y represents the position of the data point, thus, DTD≫C; therefore, we can get μDTD+2λC≈DTD+λ′C≈DTD. On the contrary, when t0=0, for any input data point D, if and only if s0=DT−1⋅η, where η>0 is a constant, as η⟶0, the expression μDTsk−tk⟶0. Until now, only the empirical parameter η is undetermined. When the ellipse parameter α = abcdefT is solved, we can normalize f=1; thus, it becomes α = ABCDE1T. Then, its centroid Xc,Yc, major semiaxis Rx, minor semiaxis Ry, and angle θ can be determined by [25](19)Xc=BE−2CD4AC−B2,Yc=BD−2AE4AC−B2,Rx=2AXc2+CYc2+BXcYc−1A+C−A−C2+B2,Ry=2AXc2+CYc2+BXcYc−1A+C+A−C2+B2,θ=12tan−1BA−C.For two ellipsesE and F, their relative error can be defined as(20)1−SE∩SFSE∪SF∗100%,where SE∩SF denotes the area covered by ellipses E and F and simultaneously said the intersection of E and F and SE∪SF represents the area covered by ellipses E and F in total and said the union of E and F.


## 2.1. Problem Modeling

For a general conic by an implicit second-order polynomial, it can be drawn as(1)FD,α=Dα=ax2+bxy+cy2+dx+ey+f=0,where α = abcdefT is denoted as the conic parameter, D = x2xyy2xy1T is the data point, for every point i=1,2,…,N, where N is the number of data points, and Diα is called the algebraic distance between the data point xi,yi and the conic FD,α=0; note that the symbol x stands for the absolute value of x. The sum of all algebraic distances at each point from 1 to N is(2)FD,α=∑i=1NDiα.In order to force the conic curve into an ellipse, the parameters of the conic curve should meet the necessary conditionsb2−4ac<0; for convenience, we take its subset 4ac−b2=1 instead [3], and its matrix form can be rewritten as αTCα=1, with(3)C=0020000−10000200000000000000000000000.Thus, the matrix form of the objectiveℓ1 minimization model is given as follows:(4)minαDα1s.t.αTCα=1.By introducing the Lagrange multiplierλ, the constrained problem can be turned into an unconstrained one as(5)arg minαDα1+λαTCα−1.


## 2.2. Numerical Aspects

Thus, our method is to seek optimalα that minimizes the cost function in equation (5). The difficulty in solving equation (5) is that the ℓ1 term is nondifferentiable and inseparable. To overcome this problem, we follow the method of Zhou et al. [14]. The split Bregman method is first introduced in [15] as a very efficient tool to solve the general ℓ1 -regularized optimization problems. The basic idea is to convert the unconstrained minimization problem in equation (5) into a constrained one by introducing one auxiliary variable s=Dα; this leads to the constrained problem:(6)arg minα,ss1+λαTCα−1s.t.s=Dα.We can approximate equation (6) by adding one penalty function term as done in [16] to obtain an unconstrained problem. This yields(7)arg minα,ss1+μ2s−Dα22+λαTCα−1,where μ is a positive penalization parameter. Finally, we strictly enforced the constraints by applying the split Bregman iteration [17] with a Bregman variable t to obtain two subproblems:(8)arg minα,s,ts1+μ2s−Dα−t22+λαTCα−1,(9)tk+1=tk+Dαk+1−sk+1.In order to further simplify the subproblems, we split equation (8) into two separate ones. We now investigate these subproblems one by one.(1)
Theα-related subproblem is(10)arg minαμ2s−Dα−t22+λαTCα−1.Note that it is a least-square problem. Thus, we can obtain a closed solution as follows:(11)αk+1=μDTsk−tkμDTD+2λC.(2)
Thes-related subproblem is(12)arg minss1+μ2s−Dα−t22.This type of problem can be effectively computed using the standard soft-threshold formula presented in [16].(13)sk+1=shrinkDαk+1+tk,1μ,where(14)shrinkx,r=xxmaxx−r,0.The complete procedure of minimization problem equation (5) with the split Bregman iteration is summarized in Algorithm 1, where nmax is the maximum number of iterations; to avoid the procedure falling into an invalid solution, the iteration stop criterion is set as the algebraic distance calculated on the (k + 1)-th iteration, Dαk+11 is greater than k-th Dαk1 or the iterations reach to the maximum.Algorithm 1:ℓ1-norm-based direct least absolute deviation ellipse fitting with split Bregman iteration (DLAD).
(1)
Setk=0,nmaxiter=300,μ=1,λ=1,t0=0,s0=DT−1⋅η,α0(2)
whileDαk+11<Dαk1&&k<nmax(3)
Solvesk+1 using (13)(4)
Solvetk+1 using (9)(5)
Solveαk+1 using (11)(6)
Setk := k + 1.(7)
end while(8)
returnαk(15)Jα=arg minαDα2+λ′αTCα−1.With the high development of the variational partial differential equation (PDE) in the field of image process, theℓ1-regularized PDE-based methods have gained more and more attention and turned out to be a promising approach for various applications such as denoise [18], destripe [19], deblur [20, 21], compressive sensing [22], and object tracking [23]. Though, the ℓ1-regularized model typically achieves a very competitive performance, however, we have to select its parameters carefully or else it may fall into a local extremum and results in an undesired outcome. Almost all PDE-based methods suffer from this defect, so it is difficult to be promoted in industrial environments. Considering the classical ℓ2 ellipse fitting [3, 24], it aims to minimizing the following energy functional:For it is a least-square problem, set∂J/∂α=0, and we have(16)DTD+λ′Cα=0.Comparing theℓ1 solution derived from equation (11) with the ℓ2 solution in equation (16), when it satisfies the following conditions,(17)μDTD+2λC≈DTD+λ′C,μDTsk−tk≈0,the initial solution of ℓ1 is close to ℓ2. Without losing generality, we set μ=1,λ=1,λ′=1, for(18)DTD=x4x3yx2y2x3x2yx2x3yx2yxy3x2yxy2xyx2y2xy3y4xy2y3y2x3x2yxy2x2xyxx2yxy2y3xyy2yx2xyy2xy1,where x, y represents the position of the data point, thus, DTD≫C; therefore, we can get μDTD+2λC≈DTD+λ′C≈DTD. On the contrary, when t0=0, for any input data point D, if and only if s0=DT−1⋅η, where η>0 is a constant, as η⟶0, the expression μDTsk−tk⟶0. Until now, only the empirical parameter η is undetermined. When the ellipse parameter α = abcdefT is solved, we can normalize f=1; thus, it becomes α = ABCDE1T. Then, its centroid Xc,Yc, major semiaxis Rx, minor semiaxis Ry, and angle θ can be determined by [25](19)Xc=BE−2CD4AC−B2,Yc=BD−2AE4AC−B2,Rx=2AXc2+CYc2+BXcYc−1A+C−A−C2+B2,Ry=2AXc2+CYc2+BXcYc−1A+C+A−C2+B2,θ=12tan−1BA−C.For two ellipsesE and F, their relative error can be defined as(20)1−SE∩SFSE∪SF∗100%,where SE∩SF denotes the area covered by ellipses E and F and simultaneously said the intersection of E and F and SE∪SF represents the area covered by ellipses E and F in total and said the union of E and F.


## 3. Experimental Results

In this section, some experiments are conducted to verify the robustness of the proposed method in suppressing the influence of noise for ellipse fitting with synthetic and natural data. Several state-of-the-art ellipse fitting algorithms are implemented for performance comparison such as Fitzgibbon’sℓ2-norm based direct least-squares ellipse fitting (DLS) [3], the hyper-least-squares fitting (HyperLS) [4], guaranteed ellipse fitting with Sampson distance (SampsonLS) [6], ElliFit [26], and the RANSAC method (RANSAC) [2] which are investigated. If there is no special explanation, all the parameters hold the same for all experiments. The scale normalization parameter f0=600 is set for HyperLS. The number of sampling, the maximum number of iterations, and the threshold for eliminating the outliers in the RANSAC method are 5, 1,000, and 2, respectively, as the author advised. The parameter η=0 is set for the proposed method. We also studied the average running time of all tested algorithms as shown in Table 1.Table 1
Average running time of tested methods (millisecond).
MethodsDLSHyperLSSampsonLSElliFitRANSACProposed (α0=DLS)Proposed (α0=HyperLS)9.2615.96153.227.3425.5637.6127.61


### 3.1. Ellipse Fitting with Synthetic Data

In this section, experiments on three types of simulated ellipse data including Gaussian noise, Laplace outlier, and ellipse fragment are conducted to evaluate the performance of the proposed method.(1)
In the first experiment, 256 data points were sampled from an ellipseα=Xc=72,Yc=64,Rx=70,Ry=50,θ=30° according to a uniform sampling in angle. The noise is stochastic additive Gaussian one with mean μ=0 and standard deviation σ=0.5,5,10,15,20,25, where the noise level σ is equivalent to 1%,10%,20%,30%,40%,50% of the length of the ellipse minor semiaxis Ry. For this kind of degradation, 100% data points are polluted. Figure 1(a) gives an example of simulated ellipse points corroded with Gaussian noise with μ=0,σ=5. For a total run of 100 trials at per noise level σ, the mean, standard deviation of the relative error, and estimated ellipse parameters are demonstrated in Table 2. It can be found that, for each noise level σ, the HyperLS method obtains the highest accuracy, and the proposed method (α0=HyperLS) is the suboptimal. It outperforms about 30% which corresponds to the DLS method while causes a little performance reduction by 4% to HyperLS. Figures 2(a) and 2(b) demonstrate the mean and standard deviation of the relative error obtained with the tested approaches, respectively. It should be pointed out that though the DLS method indicates a more competitive stability compared with the proposed method, an obvious performance improvement has been gained by our ℓ1 fitting model.(2)
In the second experiment, take the ellipse parameters unchanged instead of the noise type with Laplace whose meanμ=0 and standard deviation σ hold the same as the first experiment (in this case, 64 points from 256 are selected randomly polluted by Laplace noise; an example is shown in Figure 1(b) with μ=0,σ=25). In order to illustrate the convergence behavior of the proposed algorithm, we plot the functional energy calculated by equation (5) which varies with the number of iterations as shown in Figure 3. From the figure, we can see that the proposed method (α0=DLS) can work well in a large wide parameter space; with the increasing of η, the convergent speed becomes slower gradually. Empirically, when the number of the iterations approaches 300, a satisfactory output will be gained by the proposed method. For a total run of 100 trials at per Laplace noise level σ, the mean, standard deviation of the relative error, and estimated ellipse parameters are demonstrated in Table 3. It can be found that the proposed method achieves the best performance at each noise level except for σ=0.5 and even outperforms the robust RANSAC method. Figures 2(c) and 2(d) are the mean and standard deviation of the relative error obtained with the tested approaches, respectively, from which it can be declared that the RANSAC method is very robust to Laplace outliers for different noise levels; meanwhile, the proposed and the RANSAC method are far superior to the other algorithms in this case.(3)
In the third experiment, we characterized a point on an ellipseα=Xc=72,Yc=64,Rx=70,Ry=50,θ=30° by its angle with respect to the canonical Cartesian coordinate system and formed eleven groups, namely, 0°–30°, 0°–60°, 0°–90°, 0°–120°, 0°–150°, 0°–180°, 0°–210°, 0°–240°, 0°–270°, 0°–300°, and 0°–330°, as shown in Figure 4. For each group, we generated 100 ellipses, and for each ellipse, we sampled 256 points. Two kinds of noise are simulated including Gaussian and Laplace both of which have mean μ=0 and standard deviation σ=5. Figures 5(a) and 5(b) give the estimated means and standard deviation of the relative error for the Gaussian polluted ellipse fragment, while Figures 5(c) and 5(d) correspond to its Laplace counterpart. From Figure 5, we can find that, for the Gaussian ellipse fragment, the SampsonLS and the proposed method (α0=HyperLS) get the lowest relative error, while for Laplace outliers, the proposed method (α0=HyperLS) and the RANSAC method take a significant promotion in accuracy as expected. Either for Gaussian or Laplace, the DLS and ElliFit methods have good stability.Figure 1
An example of simulated ellipse data. (a) Ellipse data with Gaussian noise. (b) Ellipse data with Laplace outlier.
(a)(b)Table 2
Mean and standard deviation of the relative error and estimated ellipse parameters on simulated Gaussian noise data with tested methods.
MethodsNoise levelσRelative errorXcYcRxRyθDLS0.50.23%/0.1872.00/0.0464.01/0.0570.01/0.0550.00/0.0530.00/0.1452.43%/0.7871.96/0.4664.00/0.4469.85/0.5750.85/0.5330.24/1.33106.53%/1.6171.92/0.8864.01/1.0070.05/0.9852.94/0.9929.40/2.861512.61%/2.2372.15/1.4663.84/1.6871.43/1.5955.80/1.4929.23/4.372019.61%/2.9372.11/1.9264.26/1.9773.35/1.8559.33/2.1130.50/6.262527.02%/3.3872.26/2.9064.29/2.7476.51/2.2362.75/2.4431.04/8.88HyperLS0.50.21%/0.1672.00/0.0464.01/0.0570.01/0.0549.99/0.0530.00/0.1452.03%/0.6571.96/0.4664.00/0.4569.96/0.6150.05/0.5430.25/1.38104.28%/1.3871.91/0.9264.00/1.0470.14/1.3050.11/1.1629.27/3.24157.49%/2.5372.17/1.5863.81/1.8571.35/2.6950.11/1.9329.02/5.682011.56%/3.4972.12/2.2564.29/2.3673.18/4.2250.73/3.3030.64/9.652517.69%/5.8272.23/4.0564.31/3.4678.44/6.8950.48/3.8430.50/14.51SampsonLS0.50.23%/0.1671.99/0.0464.01/0.0570.01/0.0549.99/0.0529.99/0.1452.40%/0.7871.96/0.4663.99/0.4569.71/0.5549.37/0.5630.27/1.28107.98%/2.4071.89/0.9864.09/1.0969.12/1.3147.03/1.5329.67/3.021520.51%/5.6271.94/2.2964.02/2.1269.76/3.0640.79/3.5030.22/6.542049.30%/12.9573.19/6.5864.12/4.5379.35/10.1926.23/10.9329.27/10.092569.01%/11.0772.21/27.8153.12/96.88106.86/100.5323.59/33.3930.32/14.70ElliFit0.50.23%/0.1472.00/0.0464.01/0.0570.02/0.0549.99/0.0529.97/0.1453.36%/0.8071.96/0.4764.00/0.4471.33/0.6149.84/0.5227.10/1.251011.56%/1.7771.91/1.0164.00/0.9676.42/1.4149.25/1.0620.30/2.181522.31%/2.5772.28/1.8363.90/1.6386.60/2.9648.76/1.3515.35/2.882032.76%/3.6072.40/3.4064.17/2.02100.37/6.0349.30/1.9412.50/3.272544.58%/4.8972.30/6.9764.18/2.71121.54/11.8550.32/2.3110.65/3.53RANSAC0.51.22%/0.3871.99/0.2763.99/0.2769.97/0.3649.96/0.3430.08/0.7356.68%/2.3572.18/1.5564.32/1.4570.68/2.2150.21/1.8230.39/4.961014.49%/4.7772.04/3.5864.23/3.6473.12/4.8450.10/4.2829.10/11.671525.43%/11.0571.89/7.0264.29/8.0677.11/11.5349.59/12.4930.50/17.602035.94%/15.7773.63/22.7566.36/11.8686.19/29.4451.30/17.0330.57/21.582551.86%/20.7558.89/97.7550.42/129.4495.55/73.2788.45/176.1533.40/22.94Proposed (α0=DLS)0.50.26%/0.1572.00/0.0564.01/0.0670.01/0.0750.00/0.0629.99/0.1752.96%/1.3172.09/0.6664.18/0.5869.56/0.8350.77/0.7529.95/2.24106.63%/1.9772.18/1.3764.21/1.0269.37/1.5452.24/1.4528.29/4.341510.77%/3.0072.27/1.51263.95/1.6570.72/1.6954.85/1.8329.03/4.522016.82%/3.7972.31/1.9464.35/1.9872.26/2.0058.00/2.3330.27/5.892523.89%/3.9772.32/2.7664.33/2.4875.06/2.2661.31/2.5230.39/8.10Proposed (α0=HyperLS)0.50.39%/0.2572.01/0.0964.01/0.0970.00/0.1350.00/0.1230.02/0.2852.34%/0.9572.05/0.5564.09/0.5069.81/0.6749.89/0.6530.05/1.79104.84%/1.7772.14/1.1964.15/1.0669.94/1.4349.65/1.2528.74/3.72157.78%/2.5972.27/1.5963.98/1.9671.15/2.6249.62/2.2128.93/5.652011.75%/3.8072.32/2.4564.47/2.2872.94/4.3549.95/3.6830.47/9.432517.87%/6.3972.63/3.6164.61/3.2778.39/7.0848.95/4.5330.40/14.06Figure 2
The mean and standard deviation of the relative error vary with different noise levelsσ. (a) The mean of the relative error varies with different Gaussian noise σ. (b) The standard deviation of the relative error varies with different Gaussian noise σ. (c) The mean of the relative error varies with different Laplace noise σ. (d) The standard deviation of the relative error varies with different Laplace noise σ.
(a)(b)(c)(d)Figure 3
The convergence curve of energy function varies withη.Table 3
Mean and standard deviation of the relative error and estimated ellipse parameters on simulated Laplace outlier data with tested methods.
MethodsNoise levelσRelative errorXcYcRxRyθDLS0.50.16%/0.1272.00/0.0264.00/0.0270.00/0.0350.00/0.0330.01/0.0651.18%/0.4771.99/0.2963.98/0.2469.99/0.3450.23/0.2929.85/0.79102.54%/0.9971.91/0.5463.96/0.4769.99/0.6750.67/0.5729.92/2.14155.43%/2.3572.06/1.0264.01/1.1970.00/1.3551.80/1.3830.07/4.90207.78%/3.1672.00/1.5064.04/1.6470.35/2.1452.80/1.9730.94/6.142511.96%/4.2171.71/2.3164.25/2.5170.87/2.5854.54/2.1532.08/10.98HyperLS0.50.15%/0.1272.00/0.0264.00/0.0270.00/0.0350.00/0.0330.01/0.0651.10%/0.4971.99/0.2963.98/0.2470.03/0.3550.02/0.2829.85/0.80102.40%/0.9971.91/0.5463.96/0.4870.12/0.7449.87/0.5529.92/2.27155.28%/3.0372.05/1.0663.99/1.3070.25/1.9749.86/1.3630.10/5.65207.96%/4.4871.99/1.6964.02/1.8370.98/4.0849.42/2.3231.33/7.772513.32%/9.1671.80/2.7464.54/4.5172.98/8.7448.96/3.0432.77/14.60SampsonLS0.50.17%/0.1272.00/0.0264.00/0.0270.00/0.0350.00/0.0330.01/0.0651.05%/0.4872.01/0.2964.00/0.2369.97/0.3349.85/0.2829.90/0.65103.08%/2.3672.00/0.8063.93/0.9169.78/0.7749.12/1.1130.21/1.88156.69%/4.1172.14/1.7564.36/2.0569.54/1.3147.93/1.8130.01/3.662010.34%/5.6071.91/2.3864.12/2.7769.88/1.7546.28/2.7630.47/5.112515.09%/7.7771.38/2.5164.10/3.5070.56/2.5843.80/4.3929.15/6.23ElliFit0.50.13%/0.1172.00/0.0264.00/0.0270.00/0.0349.99/0.0330.00/0.0651.37%/0.5571.99/0.2963.98/0.2470.37/0.3749.96/0.2828.98/0.80103.72%/1.4471.91/0.5563.96/0.4771.48/0.8049.67/0.5726.89/1.99158.35%/2.7772.08/1.1064.01/1.1773.84/1.9349.29/1.1623.15/3.382013.41%/5.0372.05/1.7364.05/1.7077.93/5.0748.62/1.7320.59/4.492520.12%/7.3171.64/3.0264.27/2.4584.23/8.0148.32/2.0618.25/8.54RANSAC0.50.66%/0.5171.99/0.2264.01/0.2069.98/0.2649.98/0.2330.00/0.5251.39%/0.6372.04/0.4464.04/0.3670.02/0.5150.02/0.4429.95/0.97101.59%/0.7072.03/0.4764.05/0.4269.99/0.5049.97/0.4830.05/1.16151.57%/0.6672.07/0.4763.98/0.4169.99/0.4749.99/0.5129.88/1.09201.61%/0.7872.00/0.4864.05/0.4570.05/0.5249.97/0.5329.95/1.00251.56%/0.7872.00/0.4564.05/0.4170.02/0.5149.96/0.5130.08/1.08Proposed (α0=DLS)0.50.14%/0.1272.00/0.0064.00/0.0070.00/0.0150.00/0.0030.00/0.0150.12%/0.1072.00/0.0064.00/0.0070.00/0.0150.00/0.0030.00/0.01100.18%/0.1272.00/0.0164.00/0.0070.00/0.0150.00/0.0030.00/0.01150.17%/0.2272.00/0.0163.99/0.0970.00/0.0150.01/0.0930.00/0.09200.20%/0.3972.00/0.0264.02/0.1369.99/0.0650.03/0.1829.98/0.13251.62%/4.4472.07/0.8164.29/1.5070.04/0.9550.57/1.6329.50/3.73Proposed (α0=HyperLS)0.50.42%/0.2472.00/0.1064.01/0.0969.99/0.1150.01/0.1130.03/0.2650.30%/0.2072.00/0.0864.00/0.0670.00/0.0950.00/0.0829.98/0.19100.29%/0.1772.00/0.0864.01/0.0769.98/0.1149.99/0.0829.96/0.20150.38%/0.3372.02/0.1064.02/0.0969.94/0.1649.99/0.0929.87/0.37200.70%/0.9872.05/0.1864.10/0.2869.85/0.4550.01/0.3029.71/0.90251.44%/3.1772.08/0.8764.18/0.8469.74/1.1450.07/1.0729.22/3.44Figure 4
An example of four different regions of an ellipse that were sampled in simulations. (a)0°–30°. (b) 0°–150°. (c) 0°–240°. (d) 0°–330°.Figure 5
The relative error on different ellipse fragment data. (a) The mean of the relative error varies with different Gaussian noiseσ. (b) The standard deviation of the relative error varies with different Gaussian noise σ. (c) The mean of the relative error varies with different Laplace noise σ. (d) The standard deviation of the relative error varies with different Laplace noise σ.
(a)(b)(c)(d)


### 3.2. Ellipse Fitting with Natural Data

Selective laser melting is one of the crucial steps in additive manufacturing (AM). The fusion area contour plays a very important role in geometrical quality control for AM [27]. In our project, the levelset method [28] is used to extract the profile of the part. Figure 6(a) is a frame of the image captured with a CCD camera in the fusion area. In order to highlight the visual quality, a subimage is zoomed in Figure 6(b), and its contour extract results are shown in Figures 6(c) and 6(d). It can be easily seen from Figure 6(c) that there are several bumps that appeared in the outline, owing to which, the estimated ellipse center Xc and the major semiaxis produced an obvious offset towards the outlier excluding our ℓ1 fitting model as shown in Figure 7. It may can be declared that corresponding to the ℓ2-norm based methods, though the proposed ℓ1-norm-based model may lead to a slight performance degradation in the Gaussian outlier, it turns out to be a more robust estimator for Laplacian and Laplacian-like abrupt degradation data.Figure 6
Fusion area image of SLM. (a) The original fusion area image of SLM. (b) Subimage of (a). (c) Contour extract results with levelset. (d) Highlight of the contour on the original image.Figure 7
Ellipse fitting of the fusion area image of SLM.


## 3.1. Ellipse Fitting with Synthetic Data

In this section, experiments on three types of simulated ellipse data including Gaussian noise, Laplace outlier, and ellipse fragment are conducted to evaluate the performance of the proposed method.(1)
In the first experiment, 256 data points were sampled from an ellipseα=Xc=72,Yc=64,Rx=70,Ry=50,θ=30° according to a uniform sampling in angle. The noise is stochastic additive Gaussian one with mean μ=0 and standard deviation σ=0.5,5,10,15,20,25, where the noise level σ is equivalent to 1%,10%,20%,30%,40%,50% of the length of the ellipse minor semiaxis Ry. For this kind of degradation, 100% data points are polluted. Figure 1(a) gives an example of simulated ellipse points corroded with Gaussian noise with μ=0,σ=5. For a total run of 100 trials at per noise level σ, the mean, standard deviation of the relative error, and estimated ellipse parameters are demonstrated in Table 2. It can be found that, for each noise level σ, the HyperLS method obtains the highest accuracy, and the proposed method (α0=HyperLS) is the suboptimal. It outperforms about 30% which corresponds to the DLS method while causes a little performance reduction by 4% to HyperLS. Figures 2(a) and 2(b) demonstrate the mean and standard deviation of the relative error obtained with the tested approaches, respectively. It should be pointed out that though the DLS method indicates a more competitive stability compared with the proposed method, an obvious performance improvement has been gained by our ℓ1 fitting model.(2)
In the second experiment, take the ellipse parameters unchanged instead of the noise type with Laplace whose meanμ=0 and standard deviation σ hold the same as the first experiment (in this case, 64 points from 256 are selected randomly polluted by Laplace noise; an example is shown in Figure 1(b) with μ=0,σ=25). In order to illustrate the convergence behavior of the proposed algorithm, we plot the functional energy calculated by equation (5) which varies with the number of iterations as shown in Figure 3. From the figure, we can see that the proposed method (α0=DLS) can work well in a large wide parameter space; with the increasing of η, the convergent speed becomes slower gradually. Empirically, when the number of the iterations approaches 300, a satisfactory output will be gained by the proposed method. For a total run of 100 trials at per Laplace noise level σ, the mean, standard deviation of the relative error, and estimated ellipse parameters are demonstrated in Table 3. It can be found that the proposed method achieves the best performance at each noise level except for σ=0.5 and even outperforms the robust RANSAC method. Figures 2(c) and 2(d) are the mean and standard deviation of the relative error obtained with the tested approaches, respectively, from which it can be declared that the RANSAC method is very robust to Laplace outliers for different noise levels; meanwhile, the proposed and the RANSAC method are far superior to the other algorithms in this case.(3)
In the third experiment, we characterized a point on an ellipseα=Xc=72,Yc=64,Rx=70,Ry=50,θ=30° by its angle with respect to the canonical Cartesian coordinate system and formed eleven groups, namely, 0°–30°, 0°–60°, 0°–90°, 0°–120°, 0°–150°, 0°–180°, 0°–210°, 0°–240°, 0°–270°, 0°–300°, and 0°–330°, as shown in Figure 4. For each group, we generated 100 ellipses, and for each ellipse, we sampled 256 points. Two kinds of noise are simulated including Gaussian and Laplace both of which have mean μ=0 and standard deviation σ=5. Figures 5(a) and 5(b) give the estimated means and standard deviation of the relative error for the Gaussian polluted ellipse fragment, while Figures 5(c) and 5(d) correspond to its Laplace counterpart. From Figure 5, we can find that, for the Gaussian ellipse fragment, the SampsonLS and the proposed method (α0=HyperLS) get the lowest relative error, while for Laplace outliers, the proposed method (α0=HyperLS) and the RANSAC method take a significant promotion in accuracy as expected. Either for Gaussian or Laplace, the DLS and ElliFit methods have good stability.Figure 1
An example of simulated ellipse data. (a) Ellipse data with Gaussian noise. (b) Ellipse data with Laplace outlier.
(a)(b)Table 2
Mean and standard deviation of the relative error and estimated ellipse parameters on simulated Gaussian noise data with tested methods.
MethodsNoise levelσRelative errorXcYcRxRyθDLS0.50.23%/0.1872.00/0.0464.01/0.0570.01/0.0550.00/0.0530.00/0.1452.43%/0.7871.96/0.4664.00/0.4469.85/0.5750.85/0.5330.24/1.33106.53%/1.6171.92/0.8864.01/1.0070.05/0.9852.94/0.9929.40/2.861512.61%/2.2372.15/1.4663.84/1.6871.43/1.5955.80/1.4929.23/4.372019.61%/2.9372.11/1.9264.26/1.9773.35/1.8559.33/2.1130.50/6.262527.02%/3.3872.26/2.9064.29/2.7476.51/2.2362.75/2.4431.04/8.88HyperLS0.50.21%/0.1672.00/0.0464.01/0.0570.01/0.0549.99/0.0530.00/0.1452.03%/0.6571.96/0.4664.00/0.4569.96/0.6150.05/0.5430.25/1.38104.28%/1.3871.91/0.9264.00/1.0470.14/1.3050.11/1.1629.27/3.24157.49%/2.5372.17/1.5863.81/1.8571.35/2.6950.11/1.9329.02/5.682011.56%/3.4972.12/2.2564.29/2.3673.18/4.2250.73/3.3030.64/9.652517.69%/5.8272.23/4.0564.31/3.4678.44/6.8950.48/3.8430.50/14.51SampsonLS0.50.23%/0.1671.99/0.0464.01/0.0570.01/0.0549.99/0.0529.99/0.1452.40%/0.7871.96/0.4663.99/0.4569.71/0.5549.37/0.5630.27/1.28107.98%/2.4071.89/0.9864.09/1.0969.12/1.3147.03/1.5329.67/3.021520.51%/5.6271.94/2.2964.02/2.1269.76/3.0640.79/3.5030.22/6.542049.30%/12.9573.19/6.5864.12/4.5379.35/10.1926.23/10.9329.27/10.092569.01%/11.0772.21/27.8153.12/96.88106.86/100.5323.59/33.3930.32/14.70ElliFit0.50.23%/0.1472.00/0.0464.01/0.0570.02/0.0549.99/0.0529.97/0.1453.36%/0.8071.96/0.4764.00/0.4471.33/0.6149.84/0.5227.10/1.251011.56%/1.7771.91/1.0164.00/0.9676.42/1.4149.25/1.0620.30/2.181522.31%/2.5772.28/1.8363.90/1.6386.60/2.9648.76/1.3515.35/2.882032.76%/3.6072.40/3.4064.17/2.02100.37/6.0349.30/1.9412.50/3.272544.58%/4.8972.30/6.9764.18/2.71121.54/11.8550.32/2.3110.65/3.53RANSAC0.51.22%/0.3871.99/0.2763.99/0.2769.97/0.3649.96/0.3430.08/0.7356.68%/2.3572.18/1.5564.32/1.4570.68/2.2150.21/1.8230.39/4.961014.49%/4.7772.04/3.5864.23/3.6473.12/4.8450.10/4.2829.10/11.671525.43%/11.0571.89/7.0264.29/8.0677.11/11.5349.59/12.4930.50/17.602035.94%/15.7773.63/22.7566.36/11.8686.19/29.4451.30/17.0330.57/21.582551.86%/20.7558.89/97.7550.42/129.4495.55/73.2788.45/176.1533.40/22.94Proposed (α0=DLS)0.50.26%/0.1572.00/0.0564.01/0.0670.01/0.0750.00/0.0629.99/0.1752.96%/1.3172.09/0.6664.18/0.5869.56/0.8350.77/0.7529.95/2.24106.63%/1.9772.18/1.3764.21/1.0269.37/1.5452.24/1.4528.29/4.341510.77%/3.0072.27/1.51263.95/1.6570.72/1.6954.85/1.8329.03/4.522016.82%/3.7972.31/1.9464.35/1.9872.26/2.0058.00/2.3330.27/5.892523.89%/3.9772.32/2.7664.33/2.4875.06/2.2661.31/2.5230.39/8.10Proposed (α0=HyperLS)0.50.39%/0.2572.01/0.0964.01/0.0970.00/0.1350.00/0.1230.02/0.2852.34%/0.9572.05/0.5564.09/0.5069.81/0.6749.89/0.6530.05/1.79104.84%/1.7772.14/1.1964.15/1.0669.94/1.4349.65/1.2528.74/3.72157.78%/2.5972.27/1.5963.98/1.9671.15/2.6249.62/2.2128.93/5.652011.75%/3.8072.32/2.4564.47/2.2872.94/4.3549.95/3.6830.47/9.432517.87%/6.3972.63/3.6164.61/3.2778.39/7.0848.95/4.5330.40/14.06Figure 2
The mean and standard deviation of the relative error vary with different noise levelsσ. (a) The mean of the relative error varies with different Gaussian noise σ. (b) The standard deviation of the relative error varies with different Gaussian noise σ. (c) The mean of the relative error varies with different Laplace noise σ. (d) The standard deviation of the relative error varies with different Laplace noise σ.
(a)(b)(c)(d)Figure 3
The convergence curve of energy function varies withη.Table 3
Mean and standard deviation of the relative error and estimated ellipse parameters on simulated Laplace outlier data with tested methods.
MethodsNoise levelσRelative errorXcYcRxRyθDLS0.50.16%/0.1272.00/0.0264.00/0.0270.00/0.0350.00/0.0330.01/0.0651.18%/0.4771.99/0.2963.98/0.2469.99/0.3450.23/0.2929.85/0.79102.54%/0.9971.91/0.5463.96/0.4769.99/0.6750.67/0.5729.92/2.14155.43%/2.3572.06/1.0264.01/1.1970.00/1.3551.80/1.3830.07/4.90207.78%/3.1672.00/1.5064.04/1.6470.35/2.1452.80/1.9730.94/6.142511.96%/4.2171.71/2.3164.25/2.5170.87/2.5854.54/2.1532.08/10.98HyperLS0.50.15%/0.1272.00/0.0264.00/0.0270.00/0.0350.00/0.0330.01/0.0651.10%/0.4971.99/0.2963.98/0.2470.03/0.3550.02/0.2829.85/0.80102.40%/0.9971.91/0.5463.96/0.4870.12/0.7449.87/0.5529.92/2.27155.28%/3.0372.05/1.0663.99/1.3070.25/1.9749.86/1.3630.10/5.65207.96%/4.4871.99/1.6964.02/1.8370.98/4.0849.42/2.3231.33/7.772513.32%/9.1671.80/2.7464.54/4.5172.98/8.7448.96/3.0432.77/14.60SampsonLS0.50.17%/0.1272.00/0.0264.00/0.0270.00/0.0350.00/0.0330.01/0.0651.05%/0.4872.01/0.2964.00/0.2369.97/0.3349.85/0.2829.90/0.65103.08%/2.3672.00/0.8063.93/0.9169.78/0.7749.12/1.1130.21/1.88156.69%/4.1172.14/1.7564.36/2.0569.54/1.3147.93/1.8130.01/3.662010.34%/5.6071.91/2.3864.12/2.7769.88/1.7546.28/2.7630.47/5.112515.09%/7.7771.38/2.5164.10/3.5070.56/2.5843.80/4.3929.15/6.23ElliFit0.50.13%/0.1172.00/0.0264.00/0.0270.00/0.0349.99/0.0330.00/0.0651.37%/0.5571.99/0.2963.98/0.2470.37/0.3749.96/0.2828.98/0.80103.72%/1.4471.91/0.5563.96/0.4771.48/0.8049.67/0.5726.89/1.99158.35%/2.7772.08/1.1064.01/1.1773.84/1.9349.29/1.1623.15/3.382013.41%/5.0372.05/1.7364.05/1.7077.93/5.0748.62/1.7320.59/4.492520.12%/7.3171.64/3.0264.27/2.4584.23/8.0148.32/2.0618.25/8.54RANSAC0.50.66%/0.5171.99/0.2264.01/0.2069.98/0.2649.98/0.2330.00/0.5251.39%/0.6372.04/0.4464.04/0.3670.02/0.5150.02/0.4429.95/0.97101.59%/0.7072.03/0.4764.05/0.4269.99/0.5049.97/0.4830.05/1.16151.57%/0.6672.07/0.4763.98/0.4169.99/0.4749.99/0.5129.88/1.09201.61%/0.7872.00/0.4864.05/0.4570.05/0.5249.97/0.5329.95/1.00251.56%/0.7872.00/0.4564.05/0.4170.02/0.5149.96/0.5130.08/1.08Proposed (α0=DLS)0.50.14%/0.1272.00/0.0064.00/0.0070.00/0.0150.00/0.0030.00/0.0150.12%/0.1072.00/0.0064.00/0.0070.00/0.0150.00/0.0030.00/0.01100.18%/0.1272.00/0.0164.00/0.0070.00/0.0150.00/0.0030.00/0.01150.17%/0.2272.00/0.0163.99/0.0970.00/0.0150.01/0.0930.00/0.09200.20%/0.3972.00/0.0264.02/0.1369.99/0.0650.03/0.1829.98/0.13251.62%/4.4472.07/0.8164.29/1.5070.04/0.9550.57/1.6329.50/3.73Proposed (α0=HyperLS)0.50.42%/0.2472.00/0.1064.01/0.0969.99/0.1150.01/0.1130.03/0.2650.30%/0.2072.00/0.0864.00/0.0670.00/0.0950.00/0.0829.98/0.19100.29%/0.1772.00/0.0864.01/0.0769.98/0.1149.99/0.0829.96/0.20150.38%/0.3372.02/0.1064.02/0.0969.94/0.1649.99/0.0929.87/0.37200.70%/0.9872.05/0.1864.10/0.2869.85/0.4550.01/0.3029.71/0.90251.44%/3.1772.08/0.8764.18/0.8469.74/1.1450.07/1.0729.22/3.44Figure 4
An example of four different regions of an ellipse that were sampled in simulations. (a)0°–30°. (b) 0°–150°. (c) 0°–240°. (d) 0°–330°.Figure 5
The relative error on different ellipse fragment data. (a) The mean of the relative error varies with different Gaussian noiseσ. (b) The standard deviation of the relative error varies with different Gaussian noise σ. (c) The mean of the relative error varies with different Laplace noise σ. (d) The standard deviation of the relative error varies with different Laplace noise σ.
(a)(b)(c)(d)


## 3.2. Ellipse Fitting with Natural Data

Selective laser melting is one of the crucial steps in additive manufacturing (AM). The fusion area contour plays a very important role in geometrical quality control for AM [27]. In our project, the levelset method [28] is used to extract the profile of the part. Figure 6(a) is a frame of the image captured with a CCD camera in the fusion area. In order to highlight the visual quality, a subimage is zoomed in Figure 6(b), and its contour extract results are shown in Figures 6(c) and 6(d). It can be easily seen from Figure 6(c) that there are several bumps that appeared in the outline, owing to which, the estimated ellipse center Xc and the major semiaxis produced an obvious offset towards the outlier excluding our ℓ1 fitting model as shown in Figure 7. It may can be declared that corresponding to the ℓ2-norm based methods, though the proposed ℓ1-norm-based model may lead to a slight performance degradation in the Gaussian outlier, it turns out to be a more robust estimator for Laplacian and Laplacian-like abrupt degradation data.Figure 6
Fusion area image of SLM. (a) The original fusion area image of SLM. (b) Subimage of (a). (c) Contour extract results with levelset. (d) Highlight of the contour on the original image.Figure 7
Ellipse fitting of the fusion area image of SLM.


## 4. Conclusions

In conclusion, a novel directℓ1-norm-based ellipse fitting model is presented in this study. It not only works well with the Gaussian outlier but also Laplacian degradation. Comparison experiments suggest that the proposed method can mitigate a wide variety of artifacts regardless of the noise type which is a very challenging issue for other state-of-the-art algorithms. Benefited from the standard ℓ2, HyperLS estimator, and split Bregman iteration, its convergence behavior is tested to verify its efficacy.



---

*Source: 1317349-2020-07-11.xml*