next up previous contents
Next: Bias-Corrected Renormalization Fitting Up: Parameter Estimation Techniques: A Previous: Orthogonal distance fitting

Gradient Weighted Least-Squares Fitting


The least-squares method described in the last sections is usually called ordinary least-squares estimator (OLS). Formally, we are given n equations:


where tex2html_wrap_inline2917 is the additive error in the i-th equation with mean zero: tex2html_wrap_inline2921 , and variance tex2html_wrap_inline2923 . Writing down in matrix form yields




The OLS estimator tries to estimate tex2html_wrap_inline2527 by minimizing the following sum of squared errors:


which gives, as we have already seen, the solution as


It can be shown (see, e.g., [2]) that the OLS estimator produces the optimal estimate of tex2html_wrap_inline2527 , ``optimal'' in terms of minimum covariance of tex2html_wrap_inline2527 , if the errors tex2html_wrap_inline2917 are uncorrelated (i.e., tex2html_wrap_inline2933 ) and their variances are constant (i.e., tex2html_wrap_inline2935 ).

Now let us examine whether the above assumptions are valid or not for conic fitting. Data points are provided by some signal processing algorithm such as edge detection. It is reasonable to assume that errors are independent from one point to another, because when detecting a point we usually do not use any information from other points. It is also reasonable to assume the errors are constant for all points because we use the same algorithm for edge detection. However, we must note that we are talking about the errors in the points, but not those in the equations (i.e., tex2html_wrap_inline2917 ). Let the error in a point tex2html_wrap_inline2939 be Gaussian with mean zero and covariance tex2html_wrap_inline2941 , where tex2html_wrap_inline2943 is the 2 tex2html_wrap_inline2945 2 identity matrix. That is, the error distribution is assumed to be isotropic in both directions ( tex2html_wrap_inline2947 , tex2html_wrap_inline2949 ). In sec:Kalman, we will consider the case where each point may have different noise distribution. Refer to eq:A+C=1. We now compute the variance tex2html_wrap_inline2951 of function tex2html_wrap_inline2953 from point tex2html_wrap_inline2811 and its uncertainty. Let tex2html_wrap_inline2957 be the true position of the point, we have certainly


We now expand tex2html_wrap_inline2953 into Taylor series at tex2html_wrap_inline2961 and tex2html_wrap_inline2963 , i.e.,


Ignoring the high order terms, we can now compute the variance of tex2html_wrap_inline2953 , i.e.,


where tex2html_wrap_inline2967 is just the gradient of tex2html_wrap_inline2953 with respect to tex2html_wrap_inline2971 and tex2html_wrap_inline2973 , and


It is now clear that the variance of each equation is not the same, and thus the OLS estimator does not yield an optimal solution.

In order to obtain a constant variance function, it is sufficient to divide the original function by its gradient, i.e.,


then tex2html_wrap_inline2975 has the constant variance tex2html_wrap_inline2977 . We can now try to find the parameters tex2html_wrap_inline2527 by minimizing the following function:


where tex2html_wrap_inline2981 . This method is thus called Gradient Weighted Least-Squares, and the solution can be easily obtained by setting tex2html_wrap_inline2983 , which yields


Note that the gradient-weighted LS is in general a nonlinear minimization problem and a closed-form solution does not exist. In the above, we gave a closed-form solution because we have ignored the dependence of tex2html_wrap_inline2985 on tex2html_wrap_inline2527 in computing tex2html_wrap_inline2989 . In reality, tex2html_wrap_inline2985 does depend on tex2html_wrap_inline2527 , as can be seen in eq:derive. Therefore, the above solution is only an approximation. In practice, we run the following iterative procedure:


In the above, the superscript (k) denotes the iteration number.

next up previous contents
Next: Bias-Corrected Renormalization Fitting Up: Parameter Estimation Techniques: A Previous: Orthogonal distance fitting

Zhengyou Zhang
Thu Feb 8 11:42:20 MET 1996