A Closed-Form Error Model of Straight Lines for Improved Data Association and Sensor Fusing

Abstract

Linear regression is a basic tool in mobile robotics, since it enables accurate estimation of straight lines from range-bearing scans or in digital images, which is a prerequisite for reliable data association and sensor fusing in the context of feature-based SLAM. This paper discusses, extends and compares existing algorithms for line fitting applicable also in the case of strong covariances between the coordinates at each single data point, which must not be neglected if range-bearing sensors are used. Besides, in particular, the determination of the covariance matrix is considered, which is required for stochastic modeling. The main contribution is a new error model of straight lines in closed form for calculating quickly and reliably the covariance matrix dependent on just a few comprehensible and easily-obtainable parameters. The model can be applied widely in any case when a line is fitted from a number of distinct points also without a priori knowledge of the specific measurement noise. By means of extensive simulations, the performance and robustness of the new model in comparison to existing approaches is shown.

1. Introduction

Contour points acquired by active sensors using sonar, radar or LiDAR [1], or extracted from image data [2,3], are a key source of information for mobile robots in order to detect obstacles or to localize themselves in known or unknown environments [4,5]. For this purpose, often, geometric features are extracted from raw data since in contrast to detailed contours, features are uniquely described just by a limited set of parameters, and their extraction works as additional filtering in order to improve reliability when dealing with sensor noise and masking [6]. However, the performance of feature-based localization or SLAM strongly depends on exact the determination of a feature vector y from measured raw data. Moreover, especially for data association, as well as for sensor fusing, not only the feature parameters are needed, but also a reliable estimation of their uncertainty is required. Generally, in the case of non-linear multi-sensor fusing, likelihood-based models can be applied (see [7]), which employ Bayesian filtering [8] or the calculation of entropies [9] to quantify uncertain information. Alternatively, especially for localization and map building, sensor fusing often is achieved with a Kalman filter (EKF). For this purpose, the covariance matrix R is required, which encapsulates the variances of the single elements in y and their dependencies.

This will be obvious if one looks at the standard algorithm for updating an estimated system state $\widehat{x}$ typically by means of EKF; compare [10,11,12]: new measurements y are plausible if their deviations from expected measurements $\widehat{y}=h\left(\widehat{x}\right)$ dependent on the in general non-linear measurement model $h\left(\widehat{x}\right)$ are within a limited range. For exact calculation of this limit, usually the Mahalanobis metric is applied (see [11,13]), which considers the covariance matrix S of the innovation $\nu =y-\widehat{y}$ with $S=R+H·\widehat{P}·H^T$ dependent on R, the covariance matrix $\widehat{P}$ of the system state and using $H=\nabla h\left(\widehat{x}\right)$. A new measurement y will be considered to relate to an already known feature vector $\widehat{y}$ if its distance is below a given threshold $r_{th}$ with ${\nu }^T{S}^{-1}\nu <r_{th}^2$. Only in this case, the system state vector $\widehat{x}$ can be updated by means of $\Delta \widehat{x}=K·\nu$ using the Kalman gain $K=\widehat{P}·H^T·S$, again depending on the covariance matrix R of the measurements, while otherwise $\widehat{x}$ and $\widehat{P}$ are expanded by the new feature.

Thus, for reliable map building, errors in the step of data association should be strictly avoided by means of exact knowledge of the covariance matrix at each measurement, since otherwise, multiple versions of certain features would be included in the map, while other features erroneously are ignored.

Particularly in artificial environments, straight lines in a plane are frequently used as features, since these are defined by just two parameters and can be clearly and uniquely determined. In contrast to point features, lines in images are almost independent of illumination and perspective, and a number of measurements can be taken along their length to localize them accurately and to distinguish them from artifacts [14]. Moreover, already, a single line enables a robot to determine its orientation and perpendicular distance, which clearly improves localization accuracy. Thus, many tracking systems have been proposed based on line features, either using range-bearing scans [15,16] or applying visual servoing (see [17,18]), and also, recently, this approach has been successfully implemented [19,20,21]. However, due to missing knowledge of the covariance matrix, for data association, often, suboptimal solutions like the Euclidean distance in Hough space [15] or other heuristics are used [22].

Obviously, fitting data to a straight line is a well-known technique, addressed in a large number of papers [23,24,25] and textbooks [26,27,28]. In [29], a recent overview of algorithms in this field is outlined. As shown in [30,31], if linear regression is applied to data with uncertainties in the x- and y-direction, always both coordinates must be considered as random variables. In [32], Arras and Siegwart suggest an error model for range-bearing sensors including a covariance matrix, affected exclusively by noise in the radial direction. Pfister et al. introduce weights into the regression algorithm in order to determine the planar displacement of a robot from range-bearing scans [33]. In [34], a maximum likelihood approach is used to formulate a general strategy for estimating the best fitted line from a set of non-uniformly-weighted range measurements. Furthermore, merging of lines and approximating the covariance matrix from an iterative approach is considered. In [30], Krystek and Anton point out that the weighting factors of the single measurements depend on the orientation of a line, which therefore can only be determined numerically. This concept has been later extended to the general case with covariances existing between the coordinates of each data point [35].

Since linear regression is sensitive with respect to outliers, split-and-merge algorithms must be applied in advance, if a contour consists of several parts; see [36,37]. In cases of strong interference, straight lines can still be identified by Hough-transformation (compare [38,39,40]), or alternatively, RANSAC algorithms can be applied; see [41,42]. Although these algorithms work reliably, exact determination of line parameters and estimating their uncertainties still requires linear regression [43].

In spite of a variety of contributions in this field, a straightforward, yet accurate algorithm for determining the covariance matrix of lines reliably, quickly and independently of the a priori mostly unknown measurement noise is missing. In Section 4, such a model in closed-form is proposed depending on just a few clearly-interpretable and easily-obtainable parameters. Besides its low complexity and great clarity, the main advantage of the covariance matrix in closed form results from the fact that it can be calculated from the same data points as used for line fitting without the need to provide additional reliability information of the measurements, which in many cases is not available.

Beforehand, in the next two paragraphs, existing methods for the linear regression and calculation of the covariance matrix are reviewed with certain extensions focusing on the usage of range-bearing sensors, which cause strong covariances between the x- and y-coordinates. Based on these theoretical foundations, Section 5 exhibits detailed simulation results in order to compare the precision and robustness of the presented algorithms.

2. Determination of the Accurate Line Parameters

In 2D-space, each straight line is uniquely described by its perpendicular distance d from the origin and by the angle $\varphi$ between the positive x-axis and this normal line; see Figure 1. In order to determine these two parameters, the mean squared error $MSE$ considering the perpendicular distances of N measurement points from the fitted line needs to be minimized. For this purpose, each perpendicular distance ${\rho }_i$ of point i is calculated either from polar or with $x_i=r_i\cos {\theta }_i$ and $y_i=r_i\sin {\theta }_i$ alternatively in Cartesian coordinates as:

$${\rho }_i=d_i-d=r_i\cos ({\theta }_i-\varphi )-d=x_i\cos \varphi +y_i\sin \varphi -d$$

(1)

Then, $MSE$ is defined as follows dependent on $\varphi$ and d:

$$MSE(\varphi ,d)=\sum _{i=1}^N{\left(s_i{\rho }_i\right)}^2$$

(2)

In (2), optional scaling values $s_i$ are included in order to consider the individual reliability of each measurement point. By calculating the derivatives of (2) with respect to $\varphi$ and d and setting both to zero, the optimum values of these parameters can be analytically derived assuming all $s_i$ to be constant, i.e., independent of $\varphi$ and d. The solution has been published elsewhere (compare [32]), and in the Appendix of this paper, a straightforward derivation is sketched, yielding for $\varphi$ and d:

$$\varphi =\frac{1}{2}·atan2\left(-2{\sigma }_{xy},{\sigma }_y^2-{\sigma }_x^2\right)$$

(3)

$$d=\overline{x}\cos \varphi +\overline{y}\sin \varphi$$

(4)

The function $atan2\left(\right)$ means the four quadrant arc tangent, which calculates $\varphi$ always in the correct range. If d becomes negative, its modulus must be taken, and the corresponding $\varphi$ has to be altered by plus or minus $\pi$. In these equations, $\overline{x}$ and $\overline{y}$ denote the mean values of all N measurements $x_i$ and $y_i$, while ${\sigma }_x^2$, ${\sigma }_y^2$ and ${\sigma }_{xy}$ denote the variances and the covariance:

$${\sigma }_x^2=\frac{1}{N}\sum _{i=1}^N{w}_i{\left(x_i-\overline{x}\right)}^2$$

(5)

$${\sigma }_y^2=\frac{1}{N}\sum _{i=1}^N{w}_i{\left(y_i-\overline{y}\right)}^2$$

(6)

$${\sigma }_{xy}=\frac{1}{N}\sum _{i=1}^N{w}_i\left(x_i-\overline{x}\right)\left(y_i-\overline{y}\right)$$

(7)

$$\overline{x}=\frac{1}{N}\sum _{i=1}^N{w}_i{x}_i$$

(8)

$$\overline{y}=\frac{1}{N}\sum _{i=1}^N{w}_i{y}_i$$

(9)

In (5)–(9), normalized weighting factors $w_i$ are used with $\frac{1}{N}{\sum }_{i=1}^N{w}_i=1$ and $0\le w_i\le 1$, calculated dependent on the chosen scaling values $s_i$:

$$w_i=\frac{s_i^2}{\frac{1}{N}{\sum }_{i=1}^N{s}_i^2}$$

(10)

As pointed out in [35], for accurate line matching, the scaling values $s_i$ must not be assumed to be constant since in general, they depend on $\varphi$. This can be understood from Figure 2, which shows for one measurement point i the error ellipse spanned by the standard deviations ${\sigma }_{x,i}$ and ${\sigma }_{y,i}$, while the rotation of the ellipse is caused by the covariance ${\sigma }_{xy,i}$.

Apparently, as a measure of confidence, only the deviation ${\sigma }_{\rho ,i}$ perpendicular to the line is relevant, while the variance of any data point parallel to the fitted line does not influence its reliability. Thus, the angle $\varphi$ given in (3) will only be exact, if the error ellipse equals a circle, which means that all measurements exhibit the same standard deviations in the x- as in the y-direction, and no covariance exists. Generally, in order to determine optimum line parameters with arbitrary variances and covariance of each measurement i, in Equation (2) the inverse of ${\sigma }_{\rho ,i}$ dependent on $\varphi$ has to be used as scaling factor $s_i$, yielding:

$$MSE\left(\varphi \right)=\sum _{i=1}^N\frac{{\rho }_i^2\left(\varphi \right)}{{\sigma }_{\rho ,i}^2\left(\varphi \right)}$$

(11)

In this formula, which can only be solved numerically, the variance ${\sigma }_{\rho ,i}^2$ needs to be calculated dependent on the covariance matrix of each measurement point i. In the case of line fitting from range-bearing scans, the covariance matrix ${\underline{R}}_{r\theta ,i}$ can be modeled as a diagonal matrix since both parameters $r_i$ and ${\theta }_i$ are measured independently, and thus, their covariance ${\sigma }_{r\theta ,i}$ equals zero:

$${\underline{R}}_{r\theta ,i}=\left(\begin{array}{cc}{\sigma }_{r,i}^2& 0\\ 0& {\sigma }_{\theta ,i}^2\end{array}\right)$$

(12)

Typically, this matrix may also be considered as constant, thus independent of index i, assuming that all measured radii and angles are affected by the same noise, i.e., ${\underline{R}}_{r\theta ,i}\approx {\underline{R}}_{r\theta }$.

With known variances ${\sigma }_{r,i}^2$ and ${\sigma }_{\theta ,i}^2$ and for a certain $\varphi$, now ${\sigma }_{\rho ,i}^2$ is determined by evaluating the relation between ${\rho }_i$ and the distances $d_i$ of each data point with $1\le i\le N$. According to (1) and with the distance d written as the mean of all $d_i$, it follows:

$${\rho }_i=d_i-\frac{1}{N}\sum _{j=1}^N{d}_j=\left(\frac{N-1}{N}\right)d_i-\frac{1}{N}\sum _{\begin{array}{c}j=1\\ (j\ne i)\end{array}}^N{d}_j$$

(13)

Since noise-induced variations of all distances $d_i$ are uncorrelated with each other, now the variance ${\sigma }_{\rho ,i}^2$ is calculated by means of summing over all variances ${\sigma }_{d,i}^2$:

$${\sigma }_{\rho ,i}^2={\left(\frac{N-1}{N}\right)}^2{\sigma }_{d,i}^2+\frac{1}{N^2}\sum _{\begin{array}{c}j=1\\ (j\ne i)\end{array}}^N{\sigma }_{d,j}^2$$

(14)

In order to derive ${\sigma }_{d,i}^2$, changes of $d_i$ with respect to small deviations of $r_i$ and ${\theta }_i$ from their expected values ${\overline{r}}_i$ and ${\overline{\theta }}_i$ are considered with $d_i={\overline{d}}_i+\Delta d_i$, $r_i={\overline{r}}_i+\Delta r_i$ and with ${\theta }_i={\overline{\theta }}_i+\Delta {\theta }_i$:

$$\Delta d_i=\Delta d_i^r+\Delta d_i^{\theta }$$

(15)

The terms on the right side of (15) can be determined independently of each other, since $\Delta r_i$ and $\Delta {\theta }_i$ are assumed to be uncorrelated. With $d_i=r_i·\cos ({\theta }_i-\varphi )$, it follows:

$$\Delta d_i^r=\Delta r_i·\cos ({\overline{\theta }}_i-\varphi )$$

(16)

and:

$$\Delta d_i^{\theta }={\overline{r}}_i\left[\cos ({\overline{\theta }}_i-\varphi +\Delta {\theta }_i)-\cos ({\overline{\theta }}_i-\varphi )\right]\approx -{\overline{r}}_i\left[\frac{\Delta {\theta }_i^2}{2}\cos ({\overline{\theta }}_i-\varphi )+\Delta {\theta }_i\sin ({\overline{\theta }}_i-\varphi )\right]$$

(17)

In the last line, the addition theorem was applied for cos$({\overline{\theta }}_i-\varphi +\Delta {\theta }_i)$, and for small variations, the approximations cos$(\Delta {\theta }_i)\approx 1-\frac{\Delta {\theta }_i^2}{2}$ and sin$(\Delta {\theta }_i)\approx \Delta {\theta }_i$ are valid.

The random variables $\Delta r_i$ and $\Delta {\theta }_i$ are assumed to be normally distributed with variances ${\sigma }_{r,i}^2$ and ${\sigma }_{\theta ,i}^2$. Thus, the random variable $\Delta {\theta }_i^2$ exhibits a ${\chi }^2$-distribution with variance $2{({\sigma }_{\theta ,i}^2)}^2$ (see [44]), and the variance of $d_i$ is calculated from (15)–(17) as the weighted sum with ${\overline{r}}_i$ and ${\overline{\theta }}_i$ approximately replaced by $r_i$ and ${\theta }_i$, respectively:

$${\sigma }_{d,i}^2=\left({\sigma }_{r,i}^2+\frac{{({\sigma }_{\theta ,i}^2)}^2}{2}\right){\cos }^2({\theta }_i-\varphi )+{\sigma }_{\theta ,i}^2{\sin }^2({\theta }_i-\varphi )$$

(18)

When applying this algorithm, a one-dimensional minimum search of $MSE$ according to (11) needs to be executed, yielding the optimum $\varphi$ of the straight line. For this purpose, ${\sigma }_{\rho ,i}^2$ is inserted from (14) considering (18) and ${\rho }_i$ is determined according to (1) by calculating d from (4) and (8)–(10) with $s_i=1/{\sigma }_{\rho ,i}$.

Obviously, numerical line fitting can also be accomplished if measurements are available in Cartesian coordinates $x_i$ and $y_i$. In this case, the covariance matrix ${\underline{R}}_{xy,i}$ of each measurement point must be known, defined as:

$${\underline{R}}_{xy,i}=\left(\begin{array}{cc}{\sigma }_{x,i}^2& {\sigma }_{xy,i}\\ {\sigma }_{xy,i}& {\sigma }_{y,i}^2\end{array}\right)$$

(19)

Furthermore, the partial derivatives of $d_i$ according to (1) with respect to $x_i$ and $y_i$ need to be calculated:

$${\underline{J}}_{d,i}=\left(\begin{array}{cc}\frac{\partial d_i}{\partial x_i}& \frac{\partial d_i}{\partial y_i}\end{array}\right)=\left(\begin{array}{cc}\cos \varphi & \sin \varphi \end{array}\right)$$

(20)

Then, ${\sigma }_{d,i}^2$ follows dependent on ${\underline{R}}_{xy,i}$ and ${\underline{J}}_{d,i}$:

$${\sigma }_{d,i}^2={\underline{J}}_{d,i}·{\underline{R}}_{xy,i}·{\left({\underline{J}}_{d,i}\right)}^T={\sigma }_{x,i}^2{\cos }^2\varphi +{\sigma }_{xy,i}\sin \varphi \cos \varphi +{\sigma }_{y,i}^2{\sin }^2\varphi$$

(21)

If raw data stem from a range-bearing scan, ${\underline{R}}_{xy,i}$ can be calculated from ${\underline{R}}_{r\theta ,i}$ by exploiting the known dependencies between the polar and Cartesian plane. For this purpose, the Jacobian matrix ${\underline{J}}_{xy,i}$ is determined:

$${\underline{J}}_{xy,i}=\left(\begin{array}{cc}\frac{\partial x_i}{\partial r_i}& \frac{\partial x_i}{\partial {\theta }_i}\\ \frac{\partial y_i}{\partial r_i}& \frac{\partial y_i}{\partial {\theta }_i}\end{array}\right)=\left(\begin{array}{cc}\cos {\theta }_i& -r_i\sin {\theta }_i\\ \sin {\theta }_i& r_i\cos {\theta }_i\end{array}\right)$$

(22)

Then, the covariance matrix ${\underline{R}}_{xy,i}$ will depend on ${\underline{R}}_{r\theta ,i}$, if small deviations from the mean value of the random variables $r_i$ and ${\theta }_i$ and a linear model are assumed:

$${\underline{R}}_{xy,i}={\underline{J}}_{xy,i}·{\underline{R}}_{r\theta ,i}·{\left({\underline{J}}_{xy,i}\right)}^T$$

(23)

According to (23), generally a strong covariance ${\sigma }_{xy,i}$ in ${\underline{R}}_{xy,i}$ must be considered, if measurements are taken by range-bearing sensors.

By means of applying (21)–(23) instead of (18) for searching the minimum of $MSE$ dependent on $\varphi$, the second order effect regarding $\Delta {\theta }_i$ is neglected. This yields almost the same formula as given in [35], though the derivation differs, and in [35], additionally, the variance of d is ignored assuming ${\sigma }_{\rho ,i}^2={\sigma }_{d,i}^2$, which according to (14) is only asymptotically correct for large N.

Finally, it should be noted that the numerical determination of $\varphi$ according to (11) means clearly more complexity compared to the straightforward solution according to Equation (3). Later, in Section 5, it will be analyzed under which conditions this additional computational effort actually is required.

3. Analytic Error Models of Straight Lines

In the literature, several methods are described to estimate errors of $\varphi$ and d and their mutual dependency. Thus, the covariance matrix $R_{d\varphi }$ must be known, defined as:

$${\underline{R}}_{d\varphi }=\left(\begin{array}{cc}{\sigma }_d^2& {\sigma }_{d\varphi }\\ {\sigma }_{d\varphi }& {\sigma }_{\varphi }^2\end{array}\right)$$

(24)

For this purpose, a general method in nonlinear parameter estimation is the calculation of the inverse Hessian matrix at the minimum of $MSE$. Details can be found in [30,35], while in [45], it is shown that this procedure may exhibit numerical instability. In Section 5, results using this method are compared with other approaches.

Alternatively, in [32,46], an analytic error model is proposed based on fault analysis of the line parameters. In this approach, the effect of variations of each single measurement point defined by ${\underline{R}}_{xy,i}$ with respect to the covariance matrix of the line parameters ${\underline{R}}_{d\varphi }$ is considered, based on (3) and (4). Thereto, the Jacobian matrix ${\underline{J}}_{d\varphi ,i}$ with respect to $x_i$ and $y_i$ is determined, defined as:

$${\underline{J}}_{d\varphi ,i}=\left(\begin{array}{cc}\frac{\partial d}{\partial x_i}& \frac{\partial d}{\partial y_i}\\ \frac{\partial \varphi }{\partial x_i}& \frac{\partial \varphi }{\partial y_i}\end{array}\right)$$

(25)

With this matrix, the contribution of a single data point i to the covariance matrix between d and $\varphi$ can be written as:

$${\underline{R}}_{d\varphi ,i}={\underline{J}}_{d\varphi ,i}·{\underline{R}}_{xy,i}·{\underline{J}}_{d\varphi ,i}^T$$

(26)

For determining the partial derivatives of d in (25), Equation (4) is differentiated after expanding it by (8) and (9), yielding:

$$\frac{\partial d}{\partial x_i}=w_i\frac{\cos \varphi }{N}+\left(\overline{y}\cos \varphi -\overline{x}\sin \varphi \right)\frac{\partial \varphi }{\partial x_i}$$

(27)

$$\frac{\partial d}{\partial y_i}=w_i\frac{\sin \varphi }{N}+\left(\overline{y}\cos \varphi -\overline{x}\sin \varphi \right)\frac{\partial \varphi }{\partial y_i}$$

(28)

Differentiating $\varphi$ according to (3) with respect to $x_i$ gives the following expression with $u=-2{\sigma }_{xy}$ and $v={\sigma }_y^2-{\sigma }_x^2$:

$$\frac{\partial \varphi }{\partial x_i}=\frac{1}{2(u^2+v^2)}\left(\frac{\partial u}{\partial x_i}v-\frac{\partial v}{\partial x_i}u\right)$$

(29)

The partial derivation of u in (29) is calculated after expanding it with (7) and (8) as:

$$\frac{\partial u}{\partial x_i}=-\frac{2}{N}·\frac{\partial }{\partial x_i}\left(\sum _{i=1}^N{w}_i{x}_i{y}_i-\overline{y}\sum _{i=1}^N{w}_i{x}_i\right)=-\frac{2w_i}{N}\left(y_i-\overline{y}\right)$$

(30)

while partial derivation of v with (5), (6) and (8) yields:

$$\frac{\partial v}{\partial x_i}=-\frac{1}{N}·\frac{\partial }{\partial x_i}\left(\sum _{i=1}^N{w}_i{x}_i^2-\frac{1}{N}{\left(\sum _{i=1}^N{w}_i{x}_i\right)}^2\right)=-\frac{2w_i}{N}\left(x_i-\overline{x}\right)$$

(31)

Finally, after substituting all terms with u and v in (29), it follows:

$$\frac{\partial \varphi }{\partial x_i}=w_i\frac{\left({\sigma }_x^2-{\sigma }_y^2\right)\left(y_i-\overline{y}\right)-2{\sigma }_{xy}\left(x_i-\overline{x}\right)}{N\left({\left({\sigma }_x^2-{\sigma }_y^2\right)}^2+4{\sigma }_{xy}^2\right)}$$

(32)

Correspondingly, for the partial derivative of $\varphi$ with respect to $y_i$, the following result is obtained:

$$\frac{\partial \varphi }{\partial y_i}=w_i\frac{\left({\sigma }_x^2-{\sigma }_y^2\right)\left(x_i-\overline{x}\right)+2{\sigma }_{xy}\left(y_i-\overline{y}\right)}{N\left({\left({\sigma }_x^2-{\sigma }_y^2\right)}^2+4{\sigma }_{xy}^2\right)}$$

(33)

Now, after inserting (27), (28), (32) and (33) into (25), the covariance matrix of d and $\varphi$ (24) is calculated by summing over all N data points since the noise contributions of the single measurements can be assumed to be stochastically independent of each other:

$${\underline{R}}_{d\varphi }=\sum _{i=1}^N{\underline{R}}_{d\varphi ,i}=\sum _{i=1}^N{\underline{J}}_{d\varphi ,i}·{\underline{R}}_{xy,i}·{\underline{J}}_{d\varphi ,i}^T$$

(34)

Equation (34) enables an exact calculation of the variances ${\sigma }_d^2$, ${\sigma }_{\varphi }^2$ and of the covariance ${\sigma }_{d\varphi }$ as long as the deviations of the measurements stay within the range of a linear approach, and as long as Equations (3) and (4) are valid. In contrast to the method proposed in [35], no second derivatives and no inversion of the Hessian matrix are needed, and thus, more stable results can be expected.

However, both algorithms need some computational effort especially for a large number of measurement points. Moreover, they do not allow one to understand the effect of changing parameters on $R_{d\varphi }$, and these models can only be applied, if for each data point, the covariance matrix ${\underline{R}}_{xy,i}$ is available. Unfortunately, for lines extracted from images, this information is unknown, and also, in the case of using range-bearing sensors, only a worst case estimate of ${\sigma }_r$ is given in the data sheet, while ${\sigma }_{\theta }$ is ignored.

4. Closed-Form Error Model of a Straight Line

In this section, a simplified error model in closed form is deduced, which enables a fast, clear and yet, for most applications, sufficiently accurate calculation of the covariance matrix ${\underline{R}}_{d\varphi }$ in any case when line parameters d and $\varphi$ have been determined from a number of discrete data points.

Thereto, first, the expected values of the line parameters d and $\varphi$, denoted as $\overline{d}$ and $\overline{\varphi }$, are assumed to be known according to the methods proposed in Section 2 with $\overline{d}\approx d$ and $\overline{\varphi }\approx \varphi$. Besides, for modeling the small deviation of d and $\varphi$, the random variables $\Delta d$ and $\Delta \varphi$ are introduced. Thus, with $d=\overline{d}+\Delta d$ and $\varphi =\overline{\varphi }+\Delta \varphi$, it follows for the variances and the covariance:

$${\sigma }_d^2={\sigma }_{\Delta d}^2{\sigma }_{\varphi }^2={\sigma }_{\Delta \varphi }^2{\sigma }_{d\varphi }={\sigma }_{\Delta d\Delta \varphi }$$

(35)

Next, $\Delta d$ and $\Delta \varphi$ shall be determined dependent on a random variation of any of the N measured data points. For this purpose, Figure 3 is considered, which shows the expected line parameters and the random variables $\Delta d$ and $\Delta \varphi$.

In order to derive expressions for $\Delta d$ and $\Delta \varphi$ depending on the random variables ${\rho }_i$, Figure 4 shows an enlargement of the rectangular box depicted in Figure 3 along the direction of the line $\tilde{x}$.

First, the effect of variations of any ${\rho }_i$ on $\Delta \varphi$ is considered. Since $\Delta \varphi$ is very small, this angle may be replaced by its tangent, which defines the slope $\Delta m$ of the line with respect to the direction $\tilde{x}$. Here, only ${\rho }_i$ is considered as random variable, but not ${\tilde{x}}_i$. Thus, the standard formula for the slope of a regression line can be applied (see, e.g., [26] Chapter 2), which will minimize the mean squared distance in the direction of $\rho$, if all ${\tilde{x}}_i$ are assumed to be exactly known:

$$\Delta \varphi \approx tan\left(\Delta \varphi \right)=\Delta m=\frac{{\sigma }_{\rho \tilde{x}}}{{\sigma }_{\tilde{x}}^2}=\frac{{\displaystyle \sum _i}{\rho }_i·{\tilde{x}}_i}{{\displaystyle \sum _i}{\tilde{x}}_i^2}$$

(36)

Now, in order to calculate the variance of $\Delta \varphi$, a linear relation between $\Delta \varphi$ and each ${\rho }_i$ is required, which is provided by the first derivation of (36) with respect to ${\rho }_i$:

$$\frac{\partial \Delta \varphi }{\partial {\rho }_i}=\frac{{\tilde{x}}_i}{{\displaystyle \sum _i}{\tilde{x}}_i^2}$$

(37)

Then, the variance of $\Delta \varphi$ dependent on the variance of ${\rho }_i$ can be specified. From (37), it follows:

$${\sigma }_{\Delta \varphi ,i}^2={\sigma }_{\rho ,i}^2·{\left(\frac{\partial \Delta \varphi }{\partial {\rho }_i}\right)}^2={\sigma }_{\rho ,i}^2·\frac{{\tilde{x}}_i^2}{{\left({\displaystyle \sum _i}{\tilde{x}}_i^2\right)}^2}$$

(38)

If ${\sigma }_{\rho ,i}^2$ is assumed to be approximately independent of i, it may be replaced by ${\sigma }_{\rho }^2$ and can be estimated from (2) with ${\rho }_i$ taken from (1) and setting all $s_i$ to $1/N$:

$${\sigma }_{\rho ,i}^2\approx {\sigma }_{\rho }^2=\frac{1}{N}\sum _{i=1}^N{\rho }_i{(\varphi ,d)}^2$$

(39)

It should be noted that for a bias-free estimation of ${\sigma }_{\rho }^2$ with (39), the exact line parameters $\varphi$ and d must be used in (1), which obviously are not available. If instead, estimated line parameters according to Section 2 are taken, e.g., by applying (3) and (4), calculated from the same data as used in (39), an underestimation of ${\sigma }_{\rho }^2$ especially for small N can be expected, since $\varphi$ and d are determined by minimizing the variance of $\rho$ of these N data points. This is referred to later.

Next, from (38), the variance of $\Delta \varphi$ results as the sum over all N data points, since all ${\rho }_i$ are independent of each other:

$${\sigma }_{\Delta \varphi }^2=\sum _i{\sigma }_{\Delta \varphi ,i}^2\approx {\sigma }_{\rho }^2·\frac{{\displaystyle \sum _i}{\tilde{x}}_i^2}{{\left({\displaystyle \sum _i}{\tilde{x}}_i^2\right)}^2}={\sigma }_{\rho }^2·\frac{1}{{\displaystyle \sum _i}{\tilde{x}}_i^2}$$

(40)

Equations (40) with (35) and (39) enables an exact calculation of ${\sigma }_{\varphi }^2$ dependent on the N data points of the line.

However, from (40), a straightforward expression can be derived, which is sufficiently accurate in most cases and enables a clear understanding of the influencing parameters on ${\sigma }_{\varphi }^2$; compare Section 5. For this purpose, according to Figure 3, the length L of a line segment is determined from the perpendicular distance d and from the angles ${\theta }_1$ and ${\theta }_N$ of the first and N-th data point, respectively:

$$L=d·\left|tan(\varphi -{\theta }_N)-tan(\varphi -{\theta }_1)\right|$$

(41)

Furthermore, a constant spacing $\Delta \tilde{x}$ between adjacent data points is assumed:

$$\Delta \tilde{x}\approx \frac{L}{N-1}.$$

(42)

Applying this approximation, the sum over all squared ${\tilde{x}}_i$ can be rewritten, yielding for even N as depicted in Figure 4:

$$\sum _i{\tilde{x}}_i^2\approx 2·\sum _{i=1}^{N/2}{\left[\frac{\Delta \tilde{x}}{2}(2i-1)\right]}^2=\Delta {\tilde{x}}^2·\sum _{i=1}^{N/2}\frac{{(2i-1)}^2}{2}$$

(43)

The last sum can be transformed into closed form as:

$$\sum _{i=1}^{N/2}\frac{{(2i-1)}^2}{2}=\frac{\frac{N}{2}\left(4{\left(\frac{N}{2}\right)}^2-1\right)}{6}=\frac{N(N^2-1)}{12}$$

(44)

With N odd, the sum must be taken twice from 1–$\frac{N-1}{2}$, since in this case, the central measurement point has no effect on ${\sigma }_{\Delta \varphi ,i}^2$, yielding:

$$\sum _i{\tilde{x}}_i^2\approx 2·\sum _{i=1}^{\frac{(N-1)}{2}}{[\Delta \tilde{x}·i]}^2=\Delta {\tilde{x}}^2·\sum _{i=1}^{\frac{(N-1)}{2}}2·i^2$$

(45)

Again, the last sum can be written in closed form, which gives the same result as in (44):

$$\sum _{i=1}^{\frac{(N-1)}{2}}2·i^2=\frac{\frac{N-1}{2}\left(\frac{N-1}{2}+1\right)\left(2·\frac{N-1}{2}+1\right)}{3}=\frac{N(N^2-1)}{12}$$

(46)

Finally, by substituting (43) with (44) or (45) with (46) into (40) and regarding (35), as well as (42), a simple analytic formula for calculating the variance of $\varphi$ is obtained, just depending on L, N and the variance of $\rho$:

$${\sigma }_{\varphi }^2\approx {\sigma }_{\rho }^2·\frac{12}{L^2·N}·\frac{N-1}{N+1}\stackrel{N\gg 1}{\approx }{\sigma }_{\rho }^2·\frac{12}{L^2·N}$$

(47)

The last simplification in (47) overestimates ${\sigma }_{\varphi }^2$ a little bit for small N. Interestingly, this error compensates quite well for a certain underestimation of ${\sigma }_{\rho }^2$ according to (39), assuming that the line parameters $\varphi$ and d are determined from the same data as ${\sigma }_{\rho }^2$; see Section 5.

Next, in order to deduce the variance ${\sigma }_d^2$, again, Figure 3 is considered. Apparently, the first part of the random variable $\Delta d$ is strongly correlated with $\Delta \varphi$ since any mismatch in $\varphi$ is transformed into a deviation $\Delta d$ by means of the geometric offset $x_{off}$ with:

$$\Delta d^{\varphi }=-x_{off}·\Delta \varphi$$

(48)

Actually, with a positive value for $x_{off}$, as depicted in Figure 3 the correlation between $\Delta d$ and $\Delta \varphi$ becomes negative, since positive values of $\Delta \varphi$ correspond to negative values of $\Delta d$. According to Figure 3, $x_{off}$ is determined from $\varphi$ and d, as well as from ${\theta }_1$ and ${\theta }_N$:

$$x_{off}=\frac{d}{2}·\left[tan(\varphi -{\theta }_N)+tan(\varphi -{\theta }_1)\right]$$

(49)

Alternatively, $x_{off}$ can be taken as the mean value from all N data points of the line segment:

$$x_{off}=\frac{d}{N}·\sum _{i=1}^{N}tan(\varphi -{\theta }_i)$$

(50)

Nevertheless, it should be noted that $\Delta d$ is not completely correlated with $\Delta \varphi$, since also in the case $x_{off}=0$, the error $\Delta d$ will not be zero.

Indeed, as a second effect, each single ${\rho }_i$ has a direct linear impact on the variable $\Delta d$. For this purpose, in Figure 4, the random variable $\Delta d^{\rho }$ is depicted, which describes a parallel shift of the regression line due to variation in ${\rho }_i$, calculated as the mean value over all ${\rho }_i$:

$$\Delta d^{\rho }=\frac{1}{N}·\sum _i{\rho }_i$$

(51)

Combining both effects, variations in d can be described as the sum of two uncorrelated terms, $\Delta d^{\varphi }$ and $\Delta d^{\rho }$:

$$\Delta d=\Delta d^{\varphi }+\Delta d^{\rho }=-x_{off}·\Delta \varphi +\frac{1}{N}·\sum _i{\rho }_i$$

(52)

This missing correlation between $\Delta \varphi$ and the sum over all ${\rho }_i$ is also intuitively accessible: if the latter takes a positive number, it will not be possible to deduce the sign or the modulus of $\Delta \varphi$. From (52) and with $E(\Delta d^{\varphi }·\Delta d^{\rho })=0$, $E(\Delta d^{\varphi })=0$ and $E(\Delta d^{\rho })=0$, the variance ${\sigma }_d^2$ can be calculated as:

$${\sigma }_d^2=E({[\Delta d]}^2)=E({[\Delta d^{\varphi }]}^2)+E({[\Delta d^{\rho }]}^2)=x_{off}^2·E({[\Delta \varphi ]}^2)+\frac{1}{N^2}·E\left({\left[\sum _i{\rho }_i\right]}^2\right)$$

(53)

$$\approx x_{off}^2·{\sigma }_{\varphi }^2+\frac{1}{N}·{\sigma }_{\rho }^2$$

(54)

In the last step from (53) to (54), again, the independence of the single measurements from each other is used; thus, the variance of the sum of the N data points approximates N-times the variance ${\sigma }_{\rho }^2$.

Finally, the covariance between $\varphi$ and d needs to be determined. Based on the definition, it follows with ${\sigma }_{d\varphi }={\sigma }_{\Delta d\Delta \varphi }$:

$${\sigma }_{d\varphi }=E(\Delta d·\Delta \varphi )=E(\Delta d^{\varphi }·\Delta \varphi )+E(\Delta d^{\rho }·\Delta \varphi )=-x_{off}·E({[\Delta \varphi ]}^2)=-x_{off}·{\sigma }_{\varphi }^2$$

(55)

By means of (47), (54) and (55), now, the complete error model in closed form is known, represented by the covariance matrix ${\underline{R}}_{d\varphi }$ given as:

$${\underline{R}}_{d\varphi }\approx {\sigma }_{\rho }^2·\left(\begin{array}{cc}\frac{12·x_{off}^2}{L^2·N}+\frac{1}{N}& \frac{-12·x_{off}}{L^2·N}\\ \frac{-12·x_{off}}{L^2·N}& \frac{12}{L^2·N}\end{array}\right)$$

(56)

Applying this error model is easy since no knowledge of the variances and covariance for each single measurement is needed, which in practice is difficult to acquire. Instead, just the number N of preferably equally-spaced points used for line fitting, the variance ${\sigma }_{\rho }^2$ according to (39), the length L of the line segment calculated with (41) and its offset $x_{off}$ according to (49) or (50) must be inserted.

5. Simulation Results

The scope of this section is to compare the presented algorithms for linear regression and error modeling based on statistical evaluation of the results. Segmentation of raw data is not considered; if necessary, this must be performed beforehand by means of well-known methods like Hough transformation or RANSAC; compare Section 1. Thus, for studying the performance reliably and repeatably, a large number of computer simulations was performed, applying a systematic variation of parameters within a wide range, which would not be feasible if real measurements are used.

For this purpose, straight lines with a certain perpendicular distance d from the origin and within a varying range of normal angles $\varphi$ have been specified. Each of these lines is numerically described by a number of N points either given in Cartesian ($x_i,y_i$) or in polar ($r_i$${\theta }_i$) coordinates. In order to simulate the outcome of a real range-bearing sensor as much as possible, the angular coordinate was varied between ${\theta }_1$ and ${\theta }_N$. To each measurement, a certain amount of normally-distributed noise with ${\sigma }_x$, ${\sigma }_y$ and ${\sigma }_{xy}$ or alternatively with ${\sigma }_r$ and ${\sigma }_{\theta }$ was added. Further, for each $\varphi$, a number of $N_s=1000$ sets of samples was generated, in order to allow statistical evaluation of the results. The first simulation was performed with $N=40$ equally-spaced points affected each by uncorrelated noise in the x- and y-direction with standard deviations ${\sigma }_x={\sigma }_y=5$ cm. This is a typical situation when a line is calculated from binary pixels, and in Figure 5a, a bundle of the simulated line segments is shown. The deviations ${\Delta }_{\varphi }$ and ${\Delta }_d$ taken as the mean value over all $N_s$ samples of the estimated $\varphi$ and d from their true values, respectively, are depicted in Figure 5b,c, comparing four algorithms as presented in Section 2: The triangles mark the outcome of Equations (3) and (4) with all weights set to one, whereas the squares are calculated according to the same analytic formulas, but using individual weighting factors applying (10) with $s_i=1/{\sigma }_{\rho ,i}$. The perpendicular deviations ${\sigma }_{\rho ,i}$ are determined according to (14) and (21) with $\varphi$ taken from (3) without weights. Obviously, in this example, all triangles coincide with the squares since each measurement i is affected by the same noise and thus for any $\varphi$, all weighting factors are always identical. The blue lines in Figure 5b,c show the results when applying the iterative method according to (11) with the minimum of $MSE$ found numerically. For this purpose, ${\sigma }_{\rho ,i}^2$ is inserted from (14) considering (21) and ${\rho }_i$ is taken from (1) and d is calculated from (4), (8)–(10) with $s_i=1/{\sigma }_{\rho ,i}$. The black lines (KA) depict the deviations of d and $\varphi$ obtained according to Krystek and Anton in [35]. Both numerical algorithm yield the same results, which is not surprising, since the variances ${\sigma }_{\rho ,i}^2$ used as weighting factors are all identical. Further, here, the analytical algorithms provide exactly the same performance as the numerical ones, since for ${\sigma }_x={\sigma }_y$. the weighting factors show no dependency on $\varphi$, and for that case, the analytical formulas are optimal.

The lower subfigures depict the parameters of the covariance matrix ${\underline{R}}_{d\varphi }$, again as a function of $\varphi$ comparing different methods. Here, the circles represent numerical results obtained from the definitions of variance and covariance by summing over all $N_s$ passes with $1\le k\le N_s$, yielding $d_k$ and ${\varphi }_k$, respectively:

$${\sigma }_d^2=\frac{1}{N_s}\sum _{k=1}^{N_s}{\left(d_k-d\right)}^2$$

(57)

$${\sigma }_{\varphi }^2=\frac{1}{N_s}\sum _{k=1}^{N_s}{\left({\varphi }_k-\varphi \right)}^2$$

(58)

$${\sigma }_{d\varphi }=\frac{1}{N_s}\sum _{k=1}^{N_s}\left(d_k-d\right)\left({\varphi }_k-\varphi \right)$$

(59)

Since these numerical results serve just as a reference for judging the accuracy of the error models, in the formulas above, the true values for d and $\varphi$ have been used. The required line parameters $d_k$ and ${\varphi }_k$ in (57)–(59) can be estimated with any of the four described methods, since minor differences in $d_k$ and ${\varphi }_k$ have almost no effect on the resulting variances and the covariance. The blue lines in Figure 5d–f show the results of the analytic error model as described in Section 3, and the black lines represent the outcomes of the algorithm from Krystek and Anton [35], while the red lines corresponds to the model in closed-form according to (56) in Section 4 with L and $x_{off}$ taken from (41) and (49), respectively. Interestingly, although the theoretical derivations differ substantially, the results match very well, which especially proves the correctness of the simplified model in closed-form. Since this model explicitly considers the effect of the line length L and of the geometric offset $x_{off}$, the behavior of the curves can be clearly understood: The minimum of L will occur if $\varphi$ equals the mean value of ${\theta }_{min}$ and ${\theta }_{max}$, i.e., at $\varphi ={55}^{\circ }$, and exactly at this angle, the maximum standard deviation ${\sigma }_{\varphi }$ occurs. Further, since L linearly depends on $\varphi$, a quadratic dependence of ${\sigma }_{\varphi }$ on $\varphi$ according to (47) can be observed. With respect to Figure 5e, the minimum of ${\sigma }_d$ also appears at $\varphi ={55}^{\circ }$ corresponding to $x_{off}=0$. At this angle, according to (54), the standard deviation of d is given as ${\sigma }_d\approx {\sigma }_{\rho }/\sqrt{N}=5/\sqrt{40}=0.79$, while the covariance ${\sigma }_{\rho d}$ calculated according to (55) and with it the correlation coefficient shown in Figure 5f vanish.

When comparing the results, one should be aware that in the simulations of the analytic error models, the exact variances ${\sigma }_{x_i}^2$, ${\sigma }_{y_i}^2$ and ${\sigma }_{x{y}_i}$ are used; thus, in practice, the achievable accuracies will be worse. On the other hand, when applying the new error model in closed-form, the variance ${\sigma }_{\rho }^2$ is calculated as the mean value of all ${\rho }_i^2$ from the actual set of N data points according to (39), and hence, is always available.

Nevertheless, if in this equation, the estimated line parameters $\varphi$ and d are used, which are calculated, e.g., according to (3) and (4) using the same measurements as in (39), no unbiased ${\sigma }_{\rho }^2$ can be expected. This is reasoned from the fact that for each set of N data points, the mean quadratic distance over all ${\rho }_i^2$ is minimized in order to estimate $\varphi$ and d. Thus, the numeric value of ${\sigma }_{\rho }^2$ will always be smaller than its correct value calculated with the exact line parameters. This effect can be clearly observed from Figure 6, which shows for the same simulation parameters as depicted in Figure 5a the dependency of ${\sigma }_{\rho }^2$ on the number of points on the line N, averaged over $N_s$ sets of samples: only in the case of using the exact line parameters in (39), which obviously are only available in a simulation, actually the correct ${\sigma }_{\rho }^2=25$ cm${}^2$ is obtained as shown by the triangles. If however, in each run, ${\sigma }_{\rho }^2$ is calculated with the estimated $\varphi$ and d as indicated by the squares, a clear deviation especially at low N occurs. Only asymptotically for large N when $\varphi$ converges to its exact value, the correct ${\sigma }_{\rho }^2$ is reached. Fortunately, this error can be compensated quite well by means of multiplying ${\sigma }_{\rho }^2$ with a correction factor $c=\frac{N+1}{N-1}$ as shown by the dashed line in Figure 6. Due to the strongly non-linear relation between $\varphi$ and any ${\rho }_i$, this correction works much better than simply exchanging in (39) the divisor N by $N-1$ as often used in statistics. Since c is the inverse of the term neglected in the approximation of ${\sigma }_{\varphi }^2$ in (47), the closed-form of the covariance matrix ${\underline{R}}_{d\varphi }$ according to (56) yields almost unbiased results also for small N if ${\sigma }_{\rho }^2$ is calculated according to (39) with estimated line parameters $\varphi$ and d. Although not shown here, the proposed bias compensation works well for a large range of measurement parameters. For a reliable determination of ${\sigma }_{\rho }^2$ from N data points of a line segment, N should be at least in the order of 10.

Figure 7 shows the results when simulating a range-bearing scan with a constant angular offset $\Delta \theta =({\theta }_{max}-{\theta }_{min})/(N-1)$ between adjacent measurements. Each measurement is distorted by adding normally-distributed noise with standard deviations ${\sigma }_r=5$cm and ${\sigma }_{\theta }=0.1^{\circ }$. This is a more challenging situation, since now that the measurements are not equispaced, each data point exhibits individual variances ${\sigma }_{x,i}$, ${\sigma }_{y,i}$ dependent on $\varphi$, and moreover, a covariance ${\sigma }_{xy,i}$ exists. As can be seen, the errors of the estimated $\varphi$ and d as depicted in Figure 7b,c exhibit the same order of magnitude as before; yet, both analytic results differ slightly from each other and are less accurate compared to the numerical solutions. Both numerical methods yield quasi-identical results, since for the chosen small noise amplitudes, the differences between both algorithms have no impact on the resulting accuracy.

Regarding the error models, Figure 7d–f reveal that in spite of unequal distances between the measurement points and varying ${\sigma }_{\rho ,i}$, the results of the closed-form model match well with the analytic and numeric results. Only ${\sigma }_d$ shows a certain deviation at steep and flat lines with $\varphi$ below ${30}^{\circ }$ or above ${80}^{\circ }$. This is related to errors in $x_{off}$, since in this range of $\varphi$, the points on the lines measured with constant $\Delta \theta$ have clearly varying distances, and thus, (49) yields just an approximation of the effective offset of the straight line.

The next Figure 8 shows the results with the models applied to short lines measured in the angular range of ${30}^{\circ }\le \theta \le {40}^{\circ }$ with $N=20$, while all other parameters are identical to those depicted in Figure 7a. As can be seen from Figure 8b,c, now, the analytical algorithms based on (3) and (4) are no longer adequate since these, independent of applying weights or not, yield much higher errors than the numerical approaches. All error models however still provide accurate results. Actually, the closed-form model even yields better accuracy than before, since the distances of the data points on the line between adjacent measurement and also ${\sigma }_{\rho ,i}$ are more uniform compared to the simulations with long lines.

In order to check the limits of the models, Figure 9 depicts the results when applying large angular noise with ${\sigma }_{\theta }=2^{\circ }$. In this extreme case, also the numerical algorithms show systematic errors dependent on $\varphi$ since the noise of ${\rho }_i$ can no longer be assumed to be normally distributed. However, according to Figure 8b,c the iterative method as presented in Section 2 shows clear benefits in comparison to the KA algorithm proposed in [35], caused by the more accurate modeling of ${\sigma }_{{\rho }_i}$.

With respect to the outcome of the noise models in Figure 9d–f, now, only the analytic algorithm as presented in Section 3 still yields reliable results, while the KA-method based on matrix inversion reveals numerical instability. Due to the clear uneven distribution of measurements along the line, also the simplified error model in this case shows clear deviations, although at least the order of magnitude is yet correct.

Finally, Figure 10 shows typical results, if the sensor noise is not exactly known. In this example, the radial standard deviation was assumed to be 10 cm, whereas the exact value, applied when generating the measurements, was only 5 cm. The simulation parameters correspond to those in Figure 7, only the number of data points has been reduced to $N=10$. According to Figure 10b,c, now, for calculating $\varphi$ and d, the numerical methods yield no benefit over the analytical formulas with or without weights. Due to the only approximately known variance, the analytic error model, as well as the KA-method in Figure 10d–f reveal clear deviations from the reference results. Only the model in closed-form is still accurate, since it does not require any a priori information regarding sensor noise. In addition, these results prove the bias-free estimation of ${\sigma }_{\rho }^2$ with (39) also if N is low, as depicted in Figure 6.

6. Conclusions

In this study, the performance of linear regression is evaluated, assuming both coordinates as random variables. It is shown that, especially with range-bearing sensors, frequently used in mobile robotics, a distinct covariance of the noise in the x- and y-direction at each measurement point exists. In this case, analytical formulas assuming identical and uncorrelated noise will only provide accurate line parameters $\varphi$ and d if the detected line segments are sufficiently long and the noise level stays below a certain limit. If these prerequisites are not fulfilled and if the sensor noise is known, numerical algorithms should be applied, which consider the reliability of each measurement point as a function of $\varphi$. For this, the performance of prior work can be improved by means of modeling the independence of the single data points exactly and by paying attention also to second order effects of the angular noise.

The main focus of this paper is on the derivation of the covariance matrix ${\underline{R}}_{d\varphi }$ of straight lines. This information has a crucial impact on the performance of SLAM with line features, since for both, data association and sensor fusing, ${\underline{R}}_{d\varphi }$ must be estimated precisely. For this purpose, the first analytical error models are reviewed, which however need exact knowledge of the measurement noise, although in many applications, this is not available. In addition, these approaches require high computational effort and do not allow one to comprehend the effect of measurement parameters on the resulting accuracy of an estimated straight line. Thus, a new error model in closed form is proposed, depending only on two geometric parameters, as well as on the number of points of a line segment. Besides, a single variance must be known, which is determined easily and reliably from the same measurements as used for line fitting. By means of this model, the covariance matrix can be estimated quickly and exactly. Moreover, it allows one to adapt measurement conditions in order to achieve the maximum accuracy of detected line features.