1 Introduction

Baarda (1968) by his pioneering work introduced outlier tests to geodesy. He assumed the variance factor, i.e. the variance of unit weight, of the linear model to be known. Thus, the test statistic of his data snooping follows by the normalized residual having the normal distribution. Pope (1976) started from an estimated variance factor and derived as test statistic the studentized residual with the \(\tau \)-distribution. Koch (1983), (1999, p. 302) and Kok (1984) showed that the tests for multiple outliers can be derived by the mean-shift model, cf. (Baarda (1967), p. 21), Beckman and Cook (1983). Applied to searching for one outlier, it leads to the data snooping or the \(\tau \)-test.

Baarda (1968) also introduced the concept of reliability. He looked at the alternative hypothesis of his test that the outlier is not equal to zero in contrast to the null hypothesis that the outlier equals zero. Different choices for alternative hypotheses for outlier tests were discussed by Lehmann (2013).

The non-central \(\chi ^2\)-distribution follows for the alternative hypothesis of Baarda’s test. He determined the non-centrality parameter by setting the power of the test to a fixed value, generally 0.80, which means the probability of rejecting a false null hypothesis is 0.80. In case of one outlier, the expression for the non-centrality parameter can be solved for the detectable outlier. Thus, a measure of reliability is obtained.

This measure was called marginally detectable outlier by Kok (1982) and is now named the minimal detectable bias (MDB), cf. (Teunissen (2000), p. 102). The MDB is a scalar for one outlier. It is generalized for multiple outliers to a unit vector with as many components as there are outliers to be searched for. The vector indicates the positions of the outliers within the observations, and it is multiplied by a scalar with the same expression as the MDB for one outlier, cf. Knight et al. (2010), Teunissen and de Bakker (2013). The MDB is defined for all combinations of the observations with respect to the number of outliers. It depends on the submatrix of the matrix of reliabilities of the observations, which follows from the reliabilities of those observations to be assumed as falsified by outliers.

Bounds for the MDB were computed by solving eigenvalue problems, thus obtaining measures of reliability, cf. (Teunissen (2000), p. 105), Knight et al. (2010). The non-centrality parameter of the \(\chi ^2\)-distribution, on which the MDB depends, can be expressed by a quadratic form and therefore by a hyperellipsoid, the axes of which result from the eigenvalues (Teunissen 1986). The MDB is also a function of the size of the test, i.e. the level of significance, which for practical applications is set to 0.001, cf. Staff of the Geodetic Computing Center (1982).

Measures of reliability for multiple outliers shall be derived here. As known, multiple outlier testing is difficult to successfully apply. Furthermore, if a certain number of outliers is searched for and all combinations of this number within the observations are tested, different outliers may produce identical residuals and therefore identical test statistics (Baselga 2011). This does not cause a problem here as the magnitudes of the detectable outliers are important, their distributions among the observations are less of a concern.

Estimated variance factors are assumed here, the test statistics are therefore \(F\)-distributed. In addition, the size of the test is not fixed to 0.001 but depends on the number of observations out of the following reason. If one outlier is searched in the observations, all observations have to be tested. To keep the size of the overall test constant, for instance 0.05, the size of the test of the individual observation is depending on the number of measurements. This has been shown by Pope (1976). Instead of computing the size of the test for the individual observation, Lehmann (2012) applied Monte Carlo methods to compute percentage points for maximal normalized and studentized residuals.

In case of multiple outliers, all combinations of the observations with respect to the number of outliers have to be tested. Like the non-centrality parameter of the \(\chi ^2\)-distribution, the non-centrality parameter of the \(F\)-distribution can be represented by a quadratic form. The eigenvector of the quadratic form which belongs to the smallest eigenvalue leads to the detectable outliers. The minimum of these values among all combinations gives the MDBs, the minimal detectable outliers. Instead of generalizing the MDB for one outlier, it is derived here for multiple outliers.

The method is applied to data of a laser scanner. A bell-shaped surface represented by the tensor product of B-splines is determined by laser scanning. MDBs are computed and introduced into the alternative hypotheses of the outlier tests. The powers of the tests are determined by a Monte Carlo method from 100,000 random variates of the observations.

The paper is organized as follows: Sect. 2 recalls the method of multiple outlier testing in a mean-shift model. Section 3 derives the minimal detectable outliers. Section 4 deals with fitting a B-spline surface to the measurements of a laser scanner. Minimal detectable outliers are computed in Sect. 5 for the surface fitting and Sect. 6 gives the conclusions.

2 Multiple outlier testing

Let the linear model

$$\begin{aligned}&\varvec{X} \varvec{\beta }= E(\varvec{y}) = \varvec{y} + \varvec{e} \quad \text {with}\quad E(\varvec{e}) = \varvec{0} \nonumber \\&\text {and}\quad D(\varvec{y}) = D(\varvec{e}) = \sigma ^2\varvec{P}^{-1} \end{aligned}$$
(1)

be given, where \(\varvec{X}\) denotes the \(n \times u\) matrix of known coefficients with rank \(\varvec{X}=u\), \(\varvec{\beta }\) denotes the \(u \times 1\) vector of unknown parameters, \(\varvec{y}\) the \(n \times 1\) vector of observations, \(\varvec{e}\) the \(n \times 1\) vector of errors, \(\sigma ^2\) the unknown variance factor and \(\varvec{P}\) the \(n \times n\) positive definite weight matrix of the observations. The unknown parameters \(\varvec{\beta }\) are estimated by \(\hat{\varvec{\beta }}\) with

$$\begin{aligned} \hat{\varvec{\beta }} = (\varvec{X}'\varvec{PX})^{-1} \varvec{X}'\varvec{Py}, \end{aligned}$$
(2)

the vector \(\hat{\varvec{e}}\) of the residuals follows with

$$\begin{aligned} \hat{\varvec{e}} = -(\varvec{I}-\varvec{X}(\varvec{X}'\varvec{PX})^{-1} \varvec{X}'\varvec{P}) \varvec{y}, \end{aligned}$$
(3)

its covariance matrix \(D(\hat{\varvec{e}})\) with

$$\begin{aligned} D(\hat{\varvec{e}}) = \sigma ^2 \varvec{Q}_e =\sigma ^2(\varvec{P}^{-1} -\varvec{X}(\varvec{X}'\varvec{PX})^{-1} \varvec{X}') \end{aligned}$$
(4)

and the quadratic form \(\Omega \) of the residuals with

$$\begin{aligned} \Omega = \varvec{y}'(\varvec{P}-\varvec{P}\varvec{X}(\varvec{X}'\varvec{PX})^{-1} \varvec{X}' \varvec{P})\varvec{y}. \end{aligned}$$
(5)

The mean-shift model results from augmenting (1) by the \(r \times 1\) vector \(\varvec{\epsilon }\) of unknown outliers and the \(n \times r\) matrix \(\varvec{Z}\) of known coefficients, cf. (Koch (1999), p. 208) for a linear model with a matrix \(\varvec{X}\) of coefficients not of full rank,

$$\begin{aligned} |\varvec{X}, \varvec{Z}| \left| \begin{array}{c} \varvec{\beta }\\ \varvec{\epsilon }\end{array} \right| = E(\varvec{y}) \quad \text {with}\quad D(\varvec{y}) = \sigma _{\epsilon }^2 \varvec{P}^{-1} \end{aligned}$$
(6)

where \(\sigma _{\epsilon }^2\) denotes the unknown variance factor of the mean-shift model. Let’s assume that a test for \(r\) outliers has to be derived. The number \(r\) can be arbitrarily chosen but should reflect the number of outliers which is expected in the observations. The outliers are ordered in a sequence starting with \(\varvec{y} = (y_i)\) at the observation \(y_k\) and are called \(\Delta y_k\), \(\Delta y_{k+1},\ldots ,\) \(\Delta y_{k+r-1}\). They are subtracted from the observations \(y_k, y_{k+1}, \ldots , y_{k+r-1}\). Thus,

$$\begin{aligned} \varvec{\epsilon }&= |\Delta y_k, \Delta y_{k+1},\ldots , \Delta y_{k+r-1}|' \quad \text {and} \nonumber \\ \varvec{Z}&= |\varvec{e}_k, \varvec{e}_{k+1}, \ldots , \varvec{e}_{k+r-1}| \end{aligned}$$
(7)

with

$$\begin{aligned} \varvec{e}_l = |0,\ldots ,0,1,0,\ldots ,0|' \end{aligned}$$
(8)

where the \(l\)th component with \(l\in \{k, k+1,\ldots , k+r-1\}\) gets the value 1. The estimate \(\hat{\varvec{\epsilon }}\) of \(\varvec{\epsilon }\) follows by

$$\begin{aligned} \hat{\varvec{\epsilon }} = \varvec{SZ}'\varvec{P} \varvec{Q}_e \varvec{P} \varvec{y} = - \varvec{S} \varvec{Z}' \varvec{P} \hat{\varvec{e}} \end{aligned}$$
(9)

with

$$\begin{aligned} \varvec{S} = (\varvec{Z}'\varvec{PQ}_e\varvec{PZ})^{-1}. \end{aligned}$$
(10)

The matrix \(\varvec{Q}_e \varvec{P}\) is called redundancy matrix, cf. (Koch (1999), p. 305), Guo et al. (2011), because the \(i\)th diagonal element of \(\varvec{Q}_e \varvec{P}\) gives the contribution of the observation \(y_i\) to the redundancy \(n-u\)

$$\begin{aligned} \hbox {tr}(\varvec{Q}_e\varvec{P}) = \hbox {tr}(\varvec{I}-\varvec{X}(\varvec{X}'\varvec{PX})^{-1} \varvec{X}'\varvec{P}) = n-u. \end{aligned}$$
(11)

The multiple outlier test is defined by the null hypothesis \(H_0\) that all outliers \(\varvec{\epsilon }\) are equal to zero against the alternative hypothesis \(H_1\) that outliers \(\bar{\varvec{\epsilon }}\) are present

$$\begin{aligned} H_0 : \varvec{\epsilon }= \varvec{0} \quad \text {versus}\quad H_1 : \varvec{\epsilon }= \bar{\varvec{\epsilon }} \ne \mathbf{0}. \end{aligned}$$
(12)

This hypothesis is introduced into the linear model (6) as special case of a general linear hypothesis. It gives the test statistic \(T\) by, cf. (Koch (1999), p. 302),

$$\begin{aligned} T = \frac{R/r}{(\Omega -R)/(n-u-r)} \end{aligned}$$
(13)

with

$$\begin{aligned} R = \hat{\varvec{\epsilon }}' \varvec{S}^{-1} \hat{\varvec{\epsilon }} = \hat{\varvec{e}}' \varvec{PZ} \varvec{S} \varvec{Z}' \varvec{P} \hat{\varvec{e}}. \end{aligned}$$
(14)

In case the null hypothesis is true, \(T\) has the \(F\)-distribution

$$\begin{aligned} T \sim F(r,n-u-r). \end{aligned}$$
(15)

The null hypothesis is rejected if

$$\begin{aligned} T > F_{1-\alpha ;r,n-u-r} \; \end{aligned}$$
(16)

where \(\alpha \) denotes the size of the test and \(F_{1-\alpha ;r,n-u-r}\) the upper \(\alpha \)-percentage point of the \(F\)-distribution. It is defined by

$$\begin{aligned} \int _0^{F_{1-\alpha ;r,n-u-r}} F(r,n-u-r)dT = 1-\alpha \end{aligned}$$
(17)

where \(F(r,n-u-r)\) now denotes the density function of the \(F\)-distribution. Thus,

$$\begin{aligned} \int _{F_{1-\alpha ;r,n-u-r}}^{\infty } F(r,n-u-r)dT = \alpha \end{aligned}$$
(18)

gives the probability \(\alpha \) of the Type I error.

In case the alternative hypothesis is true, \(T\) has the non-central \(F\)-distribution

$$\begin{aligned} T \sim F'(r,n-u-r,\lambda ) \end{aligned}$$
(19)

with the non-centrality parameter \(\lambda \)

$$\begin{aligned} \lambda = \bar{\varvec{\epsilon }}' \varvec{S}^{-1} \bar{\varvec{\epsilon }} / \sigma _\epsilon ^2 \end{aligned}$$
(20)

and

$$\begin{aligned} \sigma _\epsilon ^2 = (\Omega -R)/(n-u-r). \end{aligned}$$
(21)

The probability of the Type II error of the test is computed by

$$\begin{aligned} P \hbox {(Type II error)}&= \int _0^{F_{1-\alpha ;r,n-u-r}} F'(r,n-u-r,\lambda )dT \nonumber \\&= 1-\beta \end{aligned}$$
(22)

where \(F'(r,n-u-r,\lambda )\) now denotes the density of the non-central \(F\)-distribution. The probability of rejecting a false null hypothesis is given by the power \(\beta \) of the test. The test by (13) is a uniformly most powerful invariant (UMPI) test, cf. (Arnold (1981), p. 108), (Kargoll (2008), p. 37). It maximizes the power within the class of unbiased, invariant tests.

If \(r\) outliers are searched in \(n\) observations, \(q\) test statistics have to be computed by the combination of \(r\)th order

$$\begin{aligned} {n \atopwithdelims ()r} = q. \end{aligned}$$
(23)

Let \(\alpha \) be the size of testing the \(q\) combinations. The probability of the type I error of this test then results with (16) from

$$\begin{aligned} P(T_1 > F_{1-\alpha ;r,n-u-r} \; \cup T_2 > F_{1-\alpha ;r,n-u-r} \; \cup \ldots \nonumber \\ \cup \; T_q > F_{1-\alpha ;r,n-u-r}) = \alpha . \end{aligned}$$
(24)

By applying the Bonferroni inequality, cf. (Arnold (1981), p. 195), we get

$$\begin{aligned}&P(T_1 > F_{1-\alpha ;r,n-u-r}) + P(T_2 > F_{1-\alpha ;r,n-u-r} + \ldots \nonumber \\&\quad + P(T_q > F_{1-\alpha ;r,n-u-r}) \ge \alpha \quad \end{aligned}$$
(25)

because of the relation which holds for \(l\ne m\) and \(l,m\in \{1,2,\ldots ,q\}\), cf. (Koch (2007), p. 7),

$$\begin{aligned}&P(T_l > F_{1-\alpha ;r,n-u-r} \; \cup T_m > F_{1-\alpha ;r,n-u-r})\\&\quad = P(T_l > F_{1-\alpha ;r,n-u-r}) + P(T_m > F_{1-\alpha ;r,n-u-r})\\&\qquad - P(T_l > F_{1-\alpha ;r,n-u-r} \; \cap T_m > F_{1-\alpha ;r,n-u-r}). \end{aligned}$$

It follows approximately from (25)

$$\begin{aligned} P(T_i < F_{1-\alpha ;r,n-u-r}) = 1-\alpha /q. \end{aligned}$$
(26)

Thus, the \(i\)th among the \(q\) combinations has to be tested with the size \(\alpha /q\) to obtain \(\alpha \) as size of the test for all \(q\) combinations. For such a test, the upper percentage point of the \(F\)-distribution in (17) needs to be replaced by \(F_{1-\alpha /q;r,n-u-r}\) so that instead of (18) the Type I error follows from

$$\begin{aligned} \int _{F_{1-\alpha /q;r,n-u-r}}^{\infty } F(r,n-u-r)dT = \alpha /q. \end{aligned}$$
(27)

By applying (26), the null hypothesis is accepted more often than by the inequality (25) as the upper percentage point is greater than the percentage point which results from the inequality.

3 Minimal detectable outliers

The ability of a parameter estimation to detect outliers has been called reliability by Baarda (1968). He started from the alternative hypothesis of his outlier test and determined the non-centrality parameter of the non-central \(\chi ^2\)-distribution by assuming a fixed value for the power of the test, 0.80 is generally taken. The alternative hypothesis \(H_1\) with the non-central \(F\)-distribution is used here. Furthermore, one of the \(q\) combinations is tested with the size \(\alpha /q\) so that the upper percentage point \(F_{1-\alpha /q;r,n-u-r}\) in (27) is applied, which follows from (17) by

$$\begin{aligned} \int _0^{F_{1-\alpha /q;r,n-u-r}} F(r,n-u-r)dT = 1-\alpha /q. \end{aligned}$$
(28)

The non-centrality parameter \(\lambda \) in (20) is determined by \(\lambda _0\) with fixing the power \(\beta \) of the test to \(\beta =0.80\)

$$\begin{aligned} \lambda _0 = \lambda (1-\alpha /q;r,n-u-r,\beta =0.80). \end{aligned}$$
(29)

The power \(\beta \) follows from (22) by

$$\begin{aligned} \int _0^{F_{1-\alpha /q;r,n-u-r}} F'(r,n-u-r,\lambda _0)dT = 1-\beta \end{aligned}$$
(30)

so that \(\lambda _0\) is computed as the \((1-\beta )\)-percentage point \(F'_{1-\beta ; r,n-u-r,\lambda _0}\) of the non-central \(F\)-distribution. The integral in (28) and the integral in (30) with \(\lambda _0\) being known are integrated over the identical domain \([0,\) \(F_{1-\alpha /q;r,n-u-r}]\), therefore

$$\begin{aligned} F'_{1-\beta ; r,n-u-r,\lambda _0} = F_{1-\alpha /q;r,n-u-r}. \end{aligned}$$
(31)

The cumulative distribution functions of the \(F\)-distribution and of the non-central \(F\)-distribution are computed by the series expansion of the incomplete beta function, cf. (Koch (1999), p. 116). To obtain the percentage points, approximate values are chosen and then iteratively corrected in nested intervals (Gaida and Koch 1985), also called binary search (Schader and Schmid 1986).

We now look at the \(q\) combinations with respect to the \(r\) outliers. Let \(\bar{\varvec{\epsilon }}_j\) with \(j\in \{k, k+1,\ldots , k+r-1\}\) be one \(r\times 1\) vector of outliers. The non-centrality parameter \(\lambda _0\) can then be expressed with (10), (12) and (20) by the quadratic form

$$\begin{aligned} \lambda _0 = \bar{\varvec{\epsilon }}_j' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} \bar{\varvec{\epsilon }}_j / \sigma _\epsilon ^2. \end{aligned}$$
(32)

It shall be minimized subject to the condition \(\bar{\varvec{\epsilon }}_j' \bar{\varvec{\epsilon }}_j=1\), cf. (Golub and van Loan (1984), p. 267),

$$\begin{aligned} \bar{\varvec{\epsilon }}_j' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} \bar{\varvec{\epsilon }}_j / \sigma _\epsilon ^2 \rightarrow \text {min for } \bar{\varvec{\epsilon }}_j' \bar{\varvec{\epsilon }}_j=1. \end{aligned}$$
(33)

Let the eigenvector \(\bar{\varvec{\epsilon }}_{jm}\) belonging to the smallest eigenvalue of the symmetric matrix \(\varvec{Z}'\varvec{PQ}_e\varvec{PZ}\) give the minimum

$$\begin{aligned} \bar{\varvec{\epsilon }}_{jm}' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} \bar{\varvec{\epsilon }}_{jm} / \sigma _\epsilon ^2 = \text {min for } \bar{\varvec{\epsilon }}_{jm}' \bar{\varvec{\epsilon }}_{jm}=1. \end{aligned}$$
(34)

The smallest value of \(\bar{\varvec{\epsilon }}_{jm}' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} \bar{\varvec{\epsilon }}_{jm}\) is then determined among all \(q\) combinations. To find it, we get by the factor \(f\) since the quadratic form (34) has to be equal to \(\lambda _0\) from (32)

$$\begin{aligned} \lambda _0 = f\bar{\varvec{\epsilon }}_{jm}' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} f\bar{\varvec{\epsilon }}_{jm} / \sigma _\epsilon ^2. \end{aligned}$$
(35)

Solving for \(f\), we obtain the expression which has to be minimized

$$\begin{aligned} f = \sqrt{\frac{\lambda _0 \sigma _\epsilon ^2}{\bar{\varvec{\epsilon }}_{jm}' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} \bar{\varvec{\epsilon }}_{jm}}}. \end{aligned}$$
(36)

Let the minimum be attained with \(\bar{\varvec{\epsilon }}_{lm}\), we then find the MDBs, the minimal detectable biases or the minimal detectable outliers by, cf. Knight et al. (2010), Teunissen and de Bakker (2013),

$$\begin{aligned} MDB = f\bar{\varvec{\epsilon }}_{lm} = \sqrt{\frac{\lambda _0 \sigma _\epsilon ^2}{\bar{\varvec{\epsilon }}_{lm}' \varvec{Z}'\varvec{PQ}_e\varvec{PZ} \bar{\varvec{\epsilon }}_{lm}}} \bar{\varvec{\epsilon }}_{lm} \nonumber \\ \text { for }\ \bar{\varvec{\epsilon }}_{lm}' \bar{\varvec{\epsilon }}_{lm}=1. \end{aligned}$$
(37)

They give a measure for the reliability of the parameter estimation.

The matrix \(\varvec{PQ}_e\varvec{P}\) is therefore called the reliability matrix \(\varvec{R}\) of the observations

$$\begin{aligned} \varvec{R} = \varvec{PQ}_e\varvec{P} = (r_{ij}), \end{aligned}$$
(38)

although Proszynski (2010) denotes the redundancy matrix \(\varvec{Q}_e \varvec{P}\) in (11) as reliability matrix. The \(r\times r\) submatrix \(\varvec{Z}'\varvec{PQ}_e\varvec{PZ}\) in (37) is found with \(\varvec{Z}\) from (7) by

(39)

The MDB for \(r=1\) follows from (37) with

$$\begin{aligned} MDB = \sqrt{\frac{\lambda _0 \sigma _\epsilon ^2}{r_{mm}}}. \end{aligned}$$
(40)

where \(r_{mm}\) denotes the minimal diagonal element of the reliability matrix \(\varvec{PQ}_e \varvec{P}\). The non-centrality parameter \(\lambda _0\) for the non-central \(\chi ^2\)-distribution with \(\alpha =0.001\) and \(1-\beta =0.20\) is obtained from, cf. Baarda (1968), Koch (1983),

$$\begin{aligned} \lambda _0 = 4.13^2 = 17.05. \end{aligned}$$
(41)

If in addition to the MDBs, maximal detectable outliers shall be computed, the eigenvector belonging to the largest eigenvalue is then used to find the maximum of (36) among the \(q\) combinations. The maximal detectable outliers have not been determined here.

4 B-spline surface

A B-spline surface in three-dimensional space is a function of two parameters which are called \(\xi _1\) and \(\xi _2\). It is obtained by the tensor product of the two B-spline basis functions \(N_{i_1q_1}(\xi _1)\) and \(N_{i_2q_2}(\xi _2)\) of degrees \(q_1\) and \(q_2\) with, cf. (Piegl and Tiller (1997), p. 34),

$$\begin{aligned} \varvec{s} (\xi _1, \xi _2) = \sum _{i_1=0}^{I_1-1} \sum _{i_2=0}^{I_2-1} N_{i_1q_1}(\xi _1) N_{i_2q_2}(\xi _2) \varvec{p}_{i_1 i_2} \end{aligned}$$
(42)

and

$$\begin{aligned} \varvec{s} (\xi _1, \xi _2) = \left| \begin{array}{c} x(\xi _1) \\ y(\xi _1, \xi _2) \\ z(\xi _2) \end{array} \right| \end{aligned}$$
(43)

where the \(3\,\times \,1\) vector \(\varvec{s} (\xi _1, \xi _2)\) denotes points with the rectangular coordinates \(x, y\) and \(z\). The coordinates \(y\) with respect to a \(x, z\) plane represent the B-spline surface. The three coordinates are measured by a laser scanner and the coordinates \(y\) are fitted to the B-spline surface. The points

$$\begin{aligned}&\varvec{p}_{i_1 i_2} = |x_{i_1}, y_{i_1 i_2}, z_{i_2}|' \quad \text {with} \nonumber \\&i_1 \in \{0,\ldots ,I_1-1\}, i_2 \in \{0,\ldots ,I_2-1\} \end{aligned}$$
(44)

are the unknown control points, which the B-spline surface approximately follows.

The B-spline basis functions \(N_{i_1q_1}(\xi _1)\) and \(N_{i_2q_2}(\xi _2)\) are computed by a recursion formula due to Cox (1972) and de Boor (1972) for the interval \(\xi _1 \in [\xi _{1j},\xi _{1j+1})\) where \(\xi _{1j}\) denotes a knot. The B-spline basis functions \(N_{i_1q_1}(\xi _1)\) form polynomial segments for the intervals \([\xi _{1j},\xi _{1j+1})\). If \(\xi _1\) lies outside \([\xi _{1j},\xi _{1j+1})\), then \(N_{i_1q_1}(\xi _1)=0\). The segments are therefore locally controlled. The same holds true for \(N_{i_2q_2}(\xi _2)\). Thus, the B-spline surface is built up by patches of bivariate polynomials, which are locally determined.

The numbers \(r_1\) and \(r_2\) of polynomial segments in the \(x\) and \(z\) directions follow from the numbers \(t_1+1\) and \(t_2+1\) of knots by, cf. Koch (2011),

$$\begin{aligned} r_1=t_1-2q_1, \quad r_2=t_2-2q_2 \end{aligned}$$
(45)

and the numbers \(I_1\) and \(I_2\) of control points in \(x\) and \(z\) directions by

$$\begin{aligned} I_1=t_1-q_1, \quad I_2=t_2-q_2. \end{aligned}$$
(46)

Let the rectangular coordinates \(x\), \(y\) and \(z\) be measured for \(n_p=e_1 \times e_2\) points \(\varvec{s} (\xi _{1a_1}, \xi _{2a_2})\), where \(\xi _{1a_1}\) with \(a_1 \in \{1,\ldots ,e_1\}\) and \(\xi _{2a_2}\) with \(a_2\in \{1,\ldots ,e_2\}\) denote the location parameters which shall be given. Equation (42) then leads to a linear relation between the unknown control points \(\varvec{p}_{i_1 i_2}\) and the measured points \(\varvec{s} (\xi _{1a_1},\xi _{2a_2})\), therefore to the linear model (1). The observation equations for estimating \(\varvec{p}_{i_1 i_2}\) are obtained by

$$\begin{aligned}&\sum _{i_1=0}^{I_1-1} \sum _{i_2=0}^{I_2-1} N_{i_1q_1}(\xi _{1a_1}) N_{i_2q_2}(\xi _{2a_2}) \varvec{p}_{i_1 i_2} \nonumber \\&\quad = \varvec{s}(\xi _{1a_1}, \xi _{2a_2}) + \varvec{e} (\xi _{1a_1}, \xi _{2a_2}) \quad \text {with} \nonumber \\&D(\varvec{y}) = \varvec{P} = \sigma ^2 \text {diag}(1/\sigma _1^2,\dots ,1/\sigma _{n_p}^2) \quad \text {and} \nonumber \\&\quad a_1\in \{1,\ldots ,e_1\}, a_2\in \{1,\ldots ,e_2\} \end{aligned}$$
(47)

where \(\varvec{e} (\xi _{1a_1}, \xi _{2a_2})\) denotes the vector of errors of the coordinates \(\varvec{s}(\xi _{1a_1}, \xi _{2a_2})\), which are assumed as being independent. The \(n_p\times 1\) vector \(\varvec{y}\) contains as components the \(y_i\) coordinates of the points \(\varvec{s}(\xi _{1a_1}, \xi _{2a_2})\), and the \(n_q\times n_p\) matrix \(\varvec{P}\) gives the weights by means of the variances \(\sigma _{i}^2\) for the coordinates \(y_i\). The standard deviations given in (58) for the coordinates \(x\) and \(z\) are much smaller than the ones for \(y\) so that they are assumed as fixed. We obtain \(e_1 e_2\) linear equations from (47) for determining \(I_1I_2\) unknown control points.

The observation equations (47) are expressed by a matrix notation which in turn is represented by the Kronecker product, cf. (Koch (1999), p. 41),

$$\begin{aligned} (\varvec{N}(\xi _2) \otimes \varvec{N}(\xi _1)) \text {vec}\varvec{D} = \text {vec}\varvec{S} + \text {vec}\varvec{E} \end{aligned}$$
(48)

where the \(e_1\times I_1\) matrix \(\varvec{N}(\xi _1)\) of B-spline basis functions is obtained by

(49)

and accordingly the \(e_2\times I_2\) matrix \(\varvec{N}(\xi _2)\). The \(I_1\times I_2\) matrix \(\varvec{D}\) of unknown control points is defined by

(50)

and with

$$\begin{aligned} \varvec{s} (\xi _{1a_1}, \xi _{2a_2}) = \varvec{s}_{a_1 a_2} \end{aligned}$$
(51)

the \(e_1\times e_2\) matrix \(\varvec{S}\) of given points by

(52)

The \(e_1\times e_2\) matrix \(\varvec{E}\) of errors is obtained with replacing \(\varvec{s}\) by \(\varvec{e}\) in (51) and (52). The matrix \(\varvec{D}\) and \(\varvec{S}\) contains as elements \(3\times 1\) vectors, the three coordinates of the points.

The simultaneous least squares estimate \(\text {vec}\hat{\varvec{D}}\) of \(\text {vec}\varvec{D}\) for the unknown control points results with (48) by

$$\begin{aligned}&\text {vec}\hat{\varvec{D}} = [(\varvec{N}(\xi _2) \otimes \varvec{N}(\xi _1))' \varvec{P} (\varvec{N}(\xi _2) \otimes \varvec{N}(\xi _1))]^{-1} \nonumber \\&\qquad \qquad \quad (\varvec{N}(\xi _2) \otimes N(\xi _1))' \varvec{P} \text {vec} \varvec{S}. \end{aligned}$$
(53)

The vector \(\text {vec}\hat{\varvec{E}}\) of residuals follows from (48) by

$$\begin{aligned} \text {vec}\hat{\varvec{E}} = (\varvec{N}(\xi _2) \otimes \varvec{N}(\xi _1)) \text {vec}\hat{\varvec{D}} - \text {vec}\varvec{S}. \end{aligned}$$
(54)

Let the \(n_p\times 1\) vector \(\hat{\varvec{e}}\) collect the residuals for the coordinates \(y_i\) from \(\text {vec}\hat{\varvec{E}}\). The estimate \(\hat{\sigma }^2\) of the variance factor \(\sigma ^2\) in (1) then follows by

$$\begin{aligned} \hat{\sigma }^2 = \hat{\varvec{e}}' \hat{\varvec{e}} / (e_1 e_2 - I_1 I_2). \end{aligned}$$
(55)

The lofting method (Koch 2009) estimates the unknown control points more efficiently than (53). However, it cannot be applied because of the weight matrix \(\varvec{P}\).

5 Numerical example

The rectangular coordinates \(x_i\) and \( z_i\) with \(i\in \{1, \ldots ,\) \(n_p\}\) of a grid of 26 rows and 28 columns with \(n_p=26\times 28=728\) points together with the coordinates \(y_i\), which represent a bell-shaped surface, were measured by the laser scanner HDS 3000, see Fig. 1. The blue colors of the points indicate high intensities of the reflected laser beams. The coordinates refer to the local coordinate system of the instrument with the \(x\)-axis lying horizontally, the \(y\)-axis coinciding with the center of the lines of sight and the \(z\) axis pointing to the zenith. The scans start at the lower left corner of the grid from negative to positive \(z\) values with increasing \(x\) values and end at the upper right corner. The distances between the points on the surface are about 1 cm, the shortest \(y\) coordinate is 501 cm.

Fig. 1
figure 1

Points representing the bell-shaped surface from coordinates \(x\), \(y\), \(z\) measured by the laser scanner. One minimal detectable outlier lies at point 355, two at points 356 and 406, three at 34, 355 and 406

Full size image

To determine the standard deviations of the observed coordinates, the points of the grid were measured in addition with \(n_w=15\) repetitions. With the mean \(\bar{x}_i\) of the repeatedly measured coordinates \(x_{ij}\) for \(i\in \{1, \ldots , n_p\}, j\in \{1, \ldots , n_w\}\) from

$$\begin{aligned} \bar{x}_i = \frac{1}{n_w} \sum _{j=1}^{n_w} x_{ij}, \end{aligned}$$
(56)

we compute the variance \(\sigma _{x_i}^2\) of \(x_i\) by

$$\begin{aligned} \sigma _{x_i}^2 = \frac{1}{n_w-1} \sum _{j=1}^{n_w} (x_{ij} - \bar{x}_i)^2 \end{aligned}$$
(57)

and accordingly \(\sigma _{y_i}^2\) and \(\sigma _{z_i}^2\) as well as the standard deviations \(\sigma _{x_i}\), \(\sigma _{y_i}\), \(\sigma _{z_i}\) by taking the square roots. The mean values \(\bar{\sigma }_{x_i}\), \(\bar{\sigma }_{y_i}\) and \(\bar{\sigma }_{z_i}\) of the \(n_w\) standard deviations are obtained with

$$\begin{aligned} \bar{\sigma }_{x_i}=0.016\,\text {cm}, \, \bar{\sigma }_{y_i}=0.097\,\text {cm}, \, \bar{\sigma }_{z_i}=0.003\,\text {cm}. \end{aligned}$$
(58)

As mentioned in Sect. 4, the B-spline surface (42) is fitted by a least squares adjustment to the \(y\) coordinates. The more knots are introduced, which means the more polynomial segments and the more unknown control points because of (45) and (46), the better the fit. The number of knots is chosen such that the variances for the coordinates \(y\) are not degraded. This is accomplished if the variance factor \(\sigma ^2\) is estimated from (55) by \(\sqrt{\hat{\sigma }^2} \approx 1\). With 13 knots in the direction of \(z\), 14 knots in the direction of \(x\) and \(q_1=q_2=3\), the number of unknown control points is 90 and the estimate from (55)

$$\begin{aligned} \sqrt{\hat{\sigma }^2} = 1.080. \end{aligned}$$
(59)

Due to the local property of the B-splines, the more polynomial segments are chosen, the more difficult becomes the detection of outliers as the coordinates \(y\) do not control each other. On the other hand because of the local property, evenly distributed outliers do not much affect the estimation of the control points.

To determine by (37) the MDBs, one, two and three outliers have been assumed, i.e. \(r\in \{1,2,3\}\), see first column of Table 1. Depending on \(q\) in (23), the submatrix (39) following from the reliability matrix (38) has to be determined. The variance \(\sigma _\epsilon ^2\) is also needed in (37), it follows with (5) and (14) from (21). The non-centrality parameter \(\lambda _0\) in (37) is computed with \(\beta = 0.80\) as the (1\(-\beta \))-percentage point of the non-central \(F\)-distribution from (30). It follows from the upper percentage point (28) of the \(F\)-distribution with size \(\alpha /q\) for the test of the individual observation. The size of the outlier test (12) is chosen as \(\alpha = 0.05\). The numbers \(q\) of combinations to be tested are obtained from (23) with \( n=n_p=728\) for \(r\in \{1,2,3\}\). They are given in the second column of Table 1 together with the values for the size \(0.05/q\). The upper percentage points (28) and the non-centrality parameters \(\lambda _0\) follow in the third column ofTable 1.

Table 1 Number \(r\) of outliers, combinations \(q\) and size 0.05/\(q\) of the tests, upper percentage points and non-centrality parameter \(\lambda _0\), minimal detectable outliers with magnitudes and points, standard deviation \(\sqrt{\hat{\sigma }^2}\), test statistic \(T\), power \(\beta \) from 100,000 generated coordinates \(y_i\), factor for minimal detectable outliers, test statistic \(T\) and power \(\beta \)
Full size table

The quadratic form (32) is minimized with computing the eigenvalues and eigenvectors by the Jacobi method, cf. (Golub and van Loan (1984), p. 295). The smallest value of (36) is determined among the \(q\) combinations. As can be recognized in Table 1, the number \(q\) of combinations increases rapidly with the number \(r\) of outliers. Instead of systematically searching the minimum of (36) for large numbers of \(q\), one could randomly seek for \(r\) outliers among the \(n_p\) coordinates \(y_i\) to which points the minimum is moving. The search can then be restricted to the vicinity of these points. The minimum leads to the MDBs from (37). Their magnitudes and the numbers of the points where they occur are presented in the following two columns of Table 1. The points are also shown in Fig. 1. The numbering of the points follows the sequence of the scans from the lower left corner of the grid to the upper right corner.

The MDB from (40) with \(\lambda _0\) from (41) of Baarda (1968) equals 0.223 cm. The difference against 0.262 in Table 1 is caused by applying the \(F\)-distribution instead of the \(\chi ^2\)-distribution and by the size 0.05/728\(=\)0.686e\(-\)06 of the test instead of 0.001.

The MDBs are introduced as outliers with positive signs for the coordinates \(y_i\) at the points where they occur. One could have selected the sign such that the standard deviations \(\sqrt{\hat{\sigma }^2}\) for the surface fit increase. This has not been tried to avoid the impression of manipulating the data. The sixth column in Table 1 shows \(\sqrt{\hat{\sigma }^2}\).

The MDBs give the outliers for the alternative hypothesis \(H_1\) in (12). To find out whether the false null hypothesis \(H_0\) for such a case is on the average rejected with a power of 0.80, independent normally distributed errors with zero expectations and standard deviations \(\sigma _{y_i}\) from (57) times \(\sqrt{\hat{\sigma }^2}\) from Table 1 are added to the coordinates \(y_i\) plus outliers, cf. (Koch (2007), p. 197), to obtain 100,000 random variates of the coordinates \(y_i\) and to compute the test statistics \(T\) from (13). The average percent of rejecting the false null hypothesis, i.e. the power \(\beta \), is thus determined.

By introducing in case of \(r=1\) the MDB for point 355 as outlier, \(\sqrt{\hat{\sigma }^2}\) increases from 1.080 of (59) to 1.102. The test statistic \(T=25.78\) given in the sixth column of Table 1 is larger than the upper percentage point of 16.06 of the third column of Table 1. The null hypothesis that the outlier is equal to zero is therefore rejected. However, a power \(\beta =0.268\) is only reached for the minimal detectable outlier of point 355 as shown in Table 1. The reason might be the local property of the B-splines as mentioned after (59). Furthermore, the \(\text {MDB}=0.262\) cm is quite optimistic. The standard deviation from (58) times \(\sqrt{\hat{\sigma }^2}\) of Table 1 is \(\bar{\sigma }_{y_i} \sqrt{\hat{\sigma }^2} =0.107\) cm. This standard deviation has to be multiplied by only 2.45 to obtain the \(\text {MDB}=0.262\). The factor of 3.00 according to the \(3\sigma \)-rule would have allowed a better detection of the outlier.

In case of \(r=2\) outliers, the standard deviation \(\sqrt{\hat{\sigma }^2}\) in Table 1 drops from 1.102 to 1.097. As the MDBs for points 356 and 406 are introduced as outliers with positive signs, they improve the surface fit by reducing the residuals of the coordinates \(y_i\) of these points. The test statistic \(T=10.15\) is smaller than the percentage point 15.86 and the null hypothesis is accepted. The power \(\beta =0.000\) therefore follows. By introducing three outliers, \(\sqrt{\hat{\sigma }^2}\) in Table 1 increases to 1.100 but it is still smaller than 1.102. The test statistic \(T=8.651\) is smaller than the percentage point 15.66. The null hypothesis is accepted and the power is \(\beta =0.000\).

The seventh column of Table 1 shows together with the test statistic \(T\) the factors by which the MDBs have to be enlarged in order to obtain the power \(\beta =0.80\) for 100,000 random variates for the coordinates \(y_i\). In case of two and three outliers, the effects of improving the surface fits by adding positive MDBs have to be compensated by enlarging the MDBs so that the outliers act as outliers. The necessary factors of 1.94 and 2.22 approximate the factor of 2.45 given above to obtain the \(\text {MDB}=0.262\) cm from the standard deviation. This explains the increase of the MDBs to obtain \(\beta =0.80\).

6 Conclusions

Starting from a linear model with an unknown variance factor, the mean-shift model is presented for multiple outlier testing. The test statistic, which has the \(F\)-distribution, and the non-centrality parameter, in case the alternative hypothesis is true, are given. Outliers are searched for all combinations of the observations with respect to the number of outliers. To keep the size of the outlier test constant, the test of the individual observations has to depend on the number of combinations. The power of the test is set to 0.80.

The non-centrality parameter is computed as the (1\(-\)0.80)-percentage point of the non-central \(F\)-distribution. It is a function of a quadratic form, which is minimized by computing the eigenvalues and eigenvectors. The smallest minimum among all combinations gives the MDBs, the minimal detectable outliers.

The method is applied to the reconstruction of a bell-shaped surface measured by a laser scanner. The MDBs of one, two and three outliers are determined together with the points where they occur. The MDBs are introduced as given outliers into the alternative hypothesis of the outlier test so that the null hypothesis is false. A Monte Carlo method checks whether on the average the false null hypotheses are rejected with a power of 0.80. It turns out that this is not the case. The MDBs have to be multiplied by 1.32 for one, 1.94 for two and 2.22 for three outliers. The reasons for enlarging the MDBs are outlined.