We consider the two-line fitting problem. True points lie on two straight lines and are observed with Gaussian perturbations. For each observed point, it is not known on which line the corresponding true point lies. The parameters of the lines are estimated.
This model is a restriction of the conic section fitting model because a couple of two lines is a degenerate conic section. The following estimators are constructed: two projections of the adjusted least squares estimator in the conic section fitting model, orthogonal regression estimator, parametric maximum likelihood estimator in the Gaussian model, and regular best asymptotically normal moment estimator.
The conditions for the consistency and asymptotic normality of the projections of the adjusted least squares estimator are provided. All the estimators constructed in the paper are equivariant. The estimators are compared numerically.
Consider a problem of estimation of two lines by perturbed observations of points that lie on the lines. Let the true points
The parameters
We consider both functional and structural models. In
In the structural model, The true lines defined by Eqs. ( The explicit parameterization has the advantage that the number of parameters is equal to the dimension of parameter space. (In [ In simulations, the confidence intervals for the coordinates of the intersection point of the two lines are obtained based on the asymptotic covariance matrix for the intersection point. For the projections the ALS2 estimator, that asymptotic covariance matrix can be evaluated without use of explicit line parameterization.
Let the true points
The points are observed with Gaussian perturbations, and the perturbed points are denoted as
The vector of coefficients in (
Similarly to the two-line fitting model, the
A couple of lines is a degenerate case of a conic section. Therefore, the conic section fitting model is an extension of the two-line fitting model.
We consider the adjusted least squares (ALS) estimator for unknown
Denote
The estimator
Equation (
The matrix
The strong consistency of the ALS2 estimator is proved in [
Denote
“Eventually” in the previous statement means that almost surely there exists
Denote the normalized version of the true parameter
Normalize the estimator of 1. 2. 3.
The methods of fitting an algebraic curve (or surface) to observed points can be classified as follows.
The criterion function for the OLS estimator is simple enough and can be adjusted so that the resulting estimator is consistent (under some conditions). Such an estimator is called the
In order to obtain parameters of two lines, the observed points are fitted with a conic section, and then the parameters of the conic section are used to obtain the parameters of two lines. There are some papers where this idea is used.
The problem of estimating the fundamental matrix for two-camera view is considered in [
In [
In [
A numerical algorithm for evaluation of the orthogonal regression estimator is presented in monograph [
The orthogonal regression is consistent in the single straight line fitting problem [
Let
The estimator
Let
In Section
The two-line fitting model is a restriction of the conic section fitting model. A couple of lines defined by the equation
The conic section ALS2 estimator provides estimation of the error variance
Denote by
There are two cases where the structural model is not identifiable. If the common distribution of the true points is concentrated on a straight line and on a single point (presumably not on the line), that is,
In order to estimate the parameters
Substituting the elements of the ALS2 estimator
If the conic section estimated by the ALS2 estimator is a hyperbola, then the “ignore-
Choose the sign ± in (
We need the notation
Now, we state the asymptotic normality of the “ignore-
The matrix
The estimators
Equation (
Perform one-step update of the estimator The normalization of the estimator
The sum of squared distances between each observed point and the closer of two lines is equal to
In the functional model, the orthogonal regression estimator is the maximum likelihood estimator. However, because the dimension of parameter space grows as the sample size is increasing, the orthogonal regression estimator may be inconsistent.
The estimator is constructed in the structural model, so it should be called the structural maximum likelihood estimator.
If a Gaussian distribution of a random point
If the distribution of a random point
The distribution of
The distribution of the observed points is also a mixture of two Gaussian distributions
The likelihood function for the sample of points with a mixture of two normal distributions is
One method of evaluating the maximum likelihood estimator is as follows:
Find the point of conditional minimum
Set
Find the estimates
The denominator
In order to make the statement of consistency easier, assume that
The
Introduce the 14-dimensional vectors whose elements are the monomials of coordinates of observed points:
Evaluate the average and sample covariance matrix of the vectors
Denote
Denote
In the structural model,
Consider the equation
In the rest of Section
The estimator is defined as a point where
The routines evaluating the RBAN-moment estimator and the estimator for its covariance matrix are developed without rigid theoretical basis; see Section
The similarity transformation of
The transformation of a sample of points acting elementwise is also denoted
Hereafter, we use vector notation: the observed points are denoted
The underlying statistical structure is
The statistical structure is invariant with respect to transformation
The statistical structure is similarity invariant if it is invariant with respect to all similarity transformations of the form (
In order to become similarity invariant, the underlying statistical structure needs some extension. We assume that the true points lie on two lines, which
The true lines
The true points
With these restrictions, the statistical structure is invariant with
Let
We treat
The transformation of the lines parameters and the transformation of
The estimator is called equivariant with respect to the transformation
In a fitting problem, an estimator for a “true figure” is called
In the two-line fitting problem, denote by
The similarity fitting equivariant estimator depends on geometry of the plane and does not depend on the Cartesian coordinate system used.
Because of (
Some troubles, which may arise during estimation, are not addressed yet.
The estimation may fail with small positive probability. For example, the conic section estimated with the ALS2 estimator is an ellipse with some positive probability, and if it is, then the “ignore-
The estimation may fail, for example, because the estimated line should be parallel to the
The optimization problem may have multiple extremal points. For the ALS2 estimator, it may occur that
In order to define the equivariance of an unreliable estimator, we allow that the estimators fail simultaneously in both sides of (
The equivariance of the ALS2 estimator in the conic section fitting problem is verified in [
In order to make the
The
The criterion function for the
Consider a further restriction of the mixture-of-two-normal-distributions model from Section
The statistical structure is invariant in scaling of the
Two samples, one of points
Let
A sample of the true points
a mixture of two singular normal distributions,
a discrete distribution,
a uniform distribution on two line segments.
Three distributions of the true points: a mixture of two singular normal distributions, a discrete distribution, and a uniform distribution on two line segments. For the first case, a sample of 1000 points is plotted, whereas for the second and third cases, the support of the distribution of the true points is plotted. For the first case, the distribution of the
These three distributions of true points are concentrated on the same two lines
For the same sample of true points
For each estimated couple of lines, the point of their intersection is found. The 100 estimates of intersection points are averaged, and their sample standard deviations are evaluated. For the ALS2-based estimators and the RBAN moment estimator, the standard errors of the estimators are also evaluated.
For computation of the
For computation of the
The EM algorithm is iterative. Once the
In case the criterion function
The knowledge or misspecification of the parameter
Average of estimated centers over 100 simulations, standard deviations over 100 simulations, and medians of estimated standard errors are presented in Tables
Means, standard deviations, and median standard errors of the estimates of intersection points for true points having mixture of singular normal distributions
Method | Means | Standard deviations | Standard errors | |||
True value | −0.08 | 0.31 | ||||
Ignore- |
−0.1098 | 0.2753 | 0.8611 | 0.3866 | 0.1918 | 0.1125 |
Update | −0.0820 | 0.2912 | 0.0706 | 0.0620 | 0.0437 | 0.0479 |
OR | 0.6533 | 3.4524 | 0.0877 | 0.6783 | ||
ML | −0.0795 | 0.3077 | 0.0326 | 0.0269 | ||
RBAN | 0.0647 | 0.3759 | 0.3563 | 0.2606 | 0.0350 | 0.0438 |
Ignore- |
−0.0909 | 0.3052 | 0.0646 | 0.0308 | 0.0601 | 0.0303 |
Update | −0.0796 | 0.3080 | 0.0127 | 0.0156 | 0.0124 | 0.0155 |
OR | 0.5492 | 3.1488 | 0.0175 | 0.1701 | ||
ML | −0.0776 | 0.3083 | 0.0103 | 0.0088 | ||
RBAN | −0.0789 | 0.3100 | 0.0126 | 0.0154 | 0.0127 | 0.0154 |
Ignore- |
−0.0799 | 0.3101 | 0.0211 | 0.0095 | 0.0188 | 0.0093 |
Update | −0.0801 | 0.3098 | 0.0037 | 0.0042 | 0.0039 | 0.0047 |
OR | 0.5606 | 3.2041 | 0.0063 | 0.0484 | ||
ML | −0.0801 | 0.3101 | 0.0030 | 0.0025 | ||
RBAN | −0.0801 | 0.3101 | 0.0038 | 0.0042 | 0.0039 | 0.0048 |
Ignore- |
−0.0799 | 0.3099 | 0.0151 | 0.0075 | 0.0147 | 0.0072 |
Update | −0.0795 | 0.3097 | 0.0052 | 0.0051 | 0.0052 | 0.0049 |
OR | −0.0792 | 0.3092 | 0.0050 | 0.0044 | ||
ML | −0.0794 | 0.3093 | 0.0048 | 0.0043 | ||
RBAN | −0.0797 | 0.3098 | 0.0063 | 0.0057 | 0.0052 | 0.0049 |
Means, standard deviations, and median standard errors of the estimates of intersection points for discrete distribution of the true points
Method | Means | Standard deviations | Standard errors | |||
True value | −0.08 | 0.31 | ||||
Ignore- |
−0.0699 | 0.3077 | 0.0263 | 0.0290 | 0.0241 | 0.0263 |
Update | −0.0722 | 0.3116 | 0.0197 | 0.0186 | 0.0203 | 0.0175 |
OR | −0.0755 | 0.3188 | 0.0148 | 0.0144 | ||
ML | −0.0958 | 0.3315 | 0.0131 | 0.0120 | ||
RBAN | −0.0717 | 0.3105 | 0.0209 | 0.0175 | 0.0205 | 0.0178 |
Ignore- |
−0.0783 | 0.3109 | 0.0092 | 0.0078 | 0.0080 | 0.0083 |
Update | −0.0785 | 0.3114 | 0.0071 | 0.0054 | 0.0065 | 0.0061 |
OR | −0.0721 | 0.3157 | 0.0048 | 0.0046 | ||
ML | −0.0931 | 0.3278 | 0.0043 | 0.0035 | ||
RBAN | −0.0786 | 0.3113 | 0.0071 | 0.0053 | 0.0065 | 0.0061 |
Ignore- |
−0.0798 | 0.3098 | 0.0031 | 0.0024 | 0.0026 | 0.0027 |
Update | −0.0799 | 0.3099 | 0.0025 | 0.0016 | 0.0021 | 0.0019 |
OR | −0.0715 | 0.3151 | 0.0017 | 0.0013 | ||
ML | −0.0932 | 0.3283 | 0.0013 | 0.0011 | ||
RBAN | −0.0799 | 0.3099 | 0.0024 | 0.0017 | 0.0021 | 0.0019 |
Ignore- |
−0.0796 | 0.3094 | 0.0033 | 0.0032 | 0.0036 | 0.0033 |
Update | −0.0798 | 0.3097 | 0.0030 | 0.0024 | 0.0033 | 0.0023 |
OR | −0.0782 | 0.3086 | 0.0021 | 0.0018 | ||
ML | −0.0786 | 0.3087 | 0.0019 | 0.0018 | ||
RBAN | −0.0796 | 0.3092 | 0.0030 | 0.0028 | 0.0033 | 0.0024 |
Means, standard deviations, and median standard errors of the estimates of intersection points for uniform distribution of the true points on two line segments
Method | Means | Standard deviations | Standard errors | |||
True value | −0.08 | 0.31 | ||||
Ignore- |
−0.0785 | 0.3122 | 0.0363 | 0.0274 | 0.0318 | 0.0301 |
Update | −0.0794 | 0.3140 | 0.0216 | 0.0258 | 0.0205 | 0.0290 |
OR | −0.0616 | 0.3127 | 0.0185 | 0.0167 | ||
ML | −0.0934 | 0.3118 | 0.0116 | 0.0111 | ||
RBAN | −0.0807 | 0.3126 | 0.0219 | 0.0293 | 0.0193 | 0.0292 |
Ignore- |
−0.0796 | 0.3107 | 0.0103 | 0.0103 | 0.0099 | 0.0095 |
Update | −0.0796 | 0.3110 | 0.0067 | 0.0103 | 0.0065 | 0.0094 |
OR | −0.0639 | 0.3087 | 0.0064 | 0.0049 | ||
ML | −0.0904 | 0.3106 | 0.0042 | 0.0033 | ||
RBAN | −0.0797 | 0.3107 | 0.0066 | 0.0104 | 0.0064 | 0.0095 |
Ignore- |
−0.0798 | 0.3098 | 0.0035 | 0.0030 | 0.0032 | 0.0030 |
Update | −0.0798 | 0.3098 | 0.0021 | 0.0029 | 0.0020 | 0.0030 |
OR | −0.0625 | 0.3085 | 0.0015 | 0.0014 | ||
ML | −0.0891 | 0.3107 | 0.0012 | 0.0011 | ||
RBAN | −0.0796 | 0.3097 | 0.0023 | 0.0030 | 0.0020 | 0.0030 |
Ignore- |
−0.0799 | 0.3100 | 0.0041 | 0.0032 | 0.0041 | 0.0035 |
Update | −0.0798 | 0.3101 | 0.0033 | 0.0032 | 0.0032 | 0.0034 |
OR | −0.0803 | 0.3103 | 0.0023 | 0.0021 | ||
ML | −0.0805 | 0.3101 | 0.0022 | 0.0020 | ||
RBAN | −0.0798 | 0.3100 | 0.0035 | 0.0033 | 0.0032 | 0.0034 |
Using the estimator
The parametric
The
Mean-square deviance of the intersection of the estimated lines from the true intersection point is presented in Table
Mean-square distances between estimated and true intersection points
Ignore- |
Update | OR | ML | RBAN | ||
1000 | 0.1 | 0.9403 | 0.0954 | 3.2978 | 0.0421 | 0.6124 |
10000 | 0.1 | 0.0722 | 0.0201 | 2.9127 | 0.0138 | 0.0199 |
100000 | 0.1 | 0.0230 | 0.0056 | 2.9645 | 0.0038 | 0.0056 |
1000 | 0.02 | 0.0168 | 0.0073 | 0.0067 | 0.0065 | 0.0084 |
1000 | 0.1 | 0.0403 | 0.0281 | 0.0228 | 0.0320 | 0.0284 |
10000 | 0.1 | 0.0121 | 0.0091 | 0.0118 | 0.0228 | 0.0090 |
100000 | 0.1 | 0.0039 | 0.0029 | 0.0101 | 0.0226 | 0.0029 |
1000 | 0.02 | 0.0046 | 0.0038 | 0.0036 | 0.0032 | 0.0042 |
1000 | 0.1 | 0.0453 | 0.0367 | 0.0310 | 0.0209 | 0.0365 |
10000 | 0.1 | 0.0145 | 0.0123 | 0.0181 | 0.0117 | 0.0123 |
100000 | 0.1 | 0.0046 | 0.0036 | 0.0177 | 0.0093 | 0.0037 |
1000 | 0.02 | 0.0052 | 0.0046 | 0.0031 | 0.0030 | 0.0048 |
For small errors, the
The parametric
For small errors (
Normalization of the estimator of
Comparison of two versions (equivariant (ev) and nonequivariant (ne)) of the updated before ignore-
Ver. | Means | Standard deviations | Standard errors | |||||
True value: | −0.08 | 0.31 | ||||||
1000 | 0.1 | ev | −0.082046 | 0.291175 | 0.070617 | 0.062003 | 0.043713 | 0.047939 |
ne | −0.044038 | 0.247382 | 0.251372 | 0.514473 | 0.038853 | 0.050167 | ||
10000 | 0.1 | ev | −0.079623 | 0.308039 | 0.012652 | 0.015582 | 0.012403 | 0.015471 |
ne | −0.085055 | 0.304177 | 0.015924 | 0.018695 | 0.012506 | 0.015550 | ||
100000 | 0.1 | ev | −0.080137 | 0.309780 | 0.003710 | 0.004173 | 0.003925 | 0.004749 |
ne | −0.080991 | 0.309386 | 0.003880 | 0.004255 | 0.003926 | 0.004742 | ||
1000 | 0.02 | ev | −0.079548 | 0.309703 | 0.005156 | 0.005131 | 0.005174 | 0.004891 |
ne | −0.079918 | 0.309508 | 0.005247 | 0.005149 | 0.005179 | 0.004918 | ||
1000 | 0.1 | ev | −0.072202 | 0.311648 | 0.019709 | 0.018553 | 0.020266 | 0.017500 |
ne | −0.071460 | 0.312230 | 0.020049 | 0.018740 | 0.020213 | 0.017457 | ||
10000 | 0.1 | ev | −0.078482 | 0.311377 | 0.007087 | 0.005371 | 0.006518 | 0.006066 |
ne | −0.078418 | 0.311436 | 0.007090 | 0.005387 | 0.006520 | 0.006054 | ||
100000 | 0.1 | ev | −0.079868 | 0.309929 | 0.002460 | 0.001647 | 0.002060 | 0.001900 |
ne | −0.079863 | 0.309934 | 0.002461 | 0.001647 | 0.002060 | 0.001901 | ||
1000 | 0.02 | ev | −0.079772 | 0.309728 | 0.002967 | 0.002376 | 0.003320 | 0.002344 |
ne | −0.079755 | 0.309732 | 0.002963 | 0.002375 | 0.003319 | 0.002339 | ||
1000 | 0.1 | ev | −0.079405 | 0.313977 | 0.021551 | 0.025759 | 0.020451 | 0.028992 |
ne | −0.078507 | 0.315350 | 0.022219 | 0.026091 | 0.020512 | 0.029115 | ||
10000 | 0.1 | ev | −0.079604 | 0.311024 | 0.006673 | 0.010337 | 0.006467 | 0.009389 |
ne | −0.079576 | 0.311176 | 0.006685 | 0.010349 | 0.006456 | 0.009372 | ||
100000 | 0.1 | ev | −0.079795 | 0.309802 | 0.002075 | 0.002919 | 0.001974 | 0.002994 |
ne | −0.079794 | 0.309818 | 0.002076 | 0.002921 | 0.001972 | 0.002992 | ||
1000 | 0.02 | ev | −0.079833 | 0.310081 | 0.003252 | 0.003249 | 0.003172 | 0.003418 |
ne | −0.079825 | 0.310097 | 0.003250 | 0.003249 | 0.003169 | 0.003411 |
Coverage probability and area of confidence ellipsoids (c.e.) for centers by the ALS2 estimator
Coverage probab. | Area of | Coverage probab. | Area of | ||||
80%, | 95%, | 95% c.e., | 80%, | 95%, | 95% c.e., | ||
% | % | % | % | ||||
1000 | 0.1 | 70.6 | 80.2 | 1449. | 70.0 | 79.2 | 1562. |
10000 | 0.1 | 79.4 | 93.8 | 236.2 | 79.6 | 92.9 | 259.4 |
100000 | 0.1 | 80.7 | 94.9 | 15.38 | 80.6 | 94.9 | 15.17 |
1000 | 0.02 | 80.4 | 95.1 | 15.95 | 78.0 | 94.1 | 19.86 |
1000 | 0.1 | 78.1 | 93.9 | 81.80 | 77.4 | 93.4 | 78.94 |
10000 | 0.1 | 81.1 | 95.6 | 12.34 | 80.9 | 95.8 | 12.39 |
100000 | 0.1 | 80.1 | 94.6 | 1.205 | 79.9 | 94.7 | 1.204 |
1000 | 0.02 | 81.0 | 94.9 | 1.984 | 81.3 | 95.2 | 1.988 |
1000 | 0.1 | 82.1 | 94.3 | 152.9 | 81.5 | 94.3 | 138.4 |
10000 | 0.1 | 81.0 | 96.6 | 20.36 | 80.3 | 96.3 | 18.92 |
100000 | 0.1 | 78.4 | 95.0 | 1.823 | 78.6 | 95.0 | 1.842 |
1000 | 0.02 | 78.7 | 94.7 | 2.926 | 78.5 | 94.1 | 3.041 |
There is a tendency that the equivariant version of the estimator is more accurate for small samples than the nonequivariant version. The two versions of the estimator are consistent and asymptotically equivalent. When the estimation is precise, the difference between the versions is negligible. When the estimation is imprecise, it is impossible to make inference which version is more accurate.
In [
The software developed here can be used to make numerical comparison of the estimates of the asymptotic covariance matrices. The data are generated as described in Section
The sample coverage probability and median (over 1000 ellipsoids) area of the confidence ellipsoids is presented in Table
Note that standard errors for coverage probability are
The strong consistency of the estimator follows from [
The strong consistency of
The conditions of consistency Theorem 1 in [
The most tedious is the condition
Denote
The matrix
Proposition
Consistence of the “ignore-
The consistency and asymptotic normality of the