air of
1)
For a
Zo 18
ST) is
(1) at
)
ration
led in
ch the
'TTOFS.
ntical
edure
ming
ormal
ndard
red as
in the
outlier
lean”
ed to
ed by
nown
rence
s data
alized
ctable
er the
Zhu Xu
assumption that no more than one outlier is present. Although, statistics for multiple outlier detection do exist, they are
not practical because we do not know a priori how many outliers are in presence and where they are. Practical strategies
for multiple outlier detection seem to fall into two categories: first, iteratively performing single-case outlier detection,
of which a typical example is the iterative data snooping proposed by Kok (1984); second, combining outlier detection
techniques with robust estimation, of which a typical example is the data snooping based on residuals resulting from L;
(norm) estimation proposed by Gao et. al. (1992). If outlier detection techniques are to be used for our purpose of
detecting local deformation of DEMs, a computationally efficient strategy is desired since local deformation of DEMs
means hundreds to thousands of outliers to the matching process. We will return to this subject later.
The robust approach employs estimators relatively insensitive to outliers to produce reliable estimates. Outliers could
be discovered as those having large residuals resulting from the robust estimation. Two important concepts related with
a robust estimator are the breakdown point and the relative efficiency. The breakdown point of an estimator is the
smallest fraction of outlier contamination that can cause the estimates arbitrarily biased [Rousseeuw and ILeroy 1987].
For example, the breakdown point of least squares estimator is 0 since a single outlier can (but does not necessarily)
make the result invalid. As another example, the median as a one-dimensional location estimator has a breakdown point
of 0.5, the highest achievable value. The relative efficiency of an estimator is defined as the ratio between the lowest
achievable variance (the Cramer-Rao bound) for the estimated parameters and the actual variance provided by the
estimator [Meer et. al. 1991] [Huang 1990]. For examples, LS estimator has a relative efficiency of 1 in the presence of
normally distributed errors and the median as a one-dimensional location estimator has a relative efficiency of 0.637. If
we use a certain robust estimator to robustify the LZD algorithm for the purpose of detecting local deformation, the
breakdown point and relative efficiency of the estimator are of great concern for the following two reasons. The
breakdown point gives a referential value of the largest deformation percentage that can be treated like this since a
larger deformation percentage could make the estimated parameters unreliable. We call this percentage the largest
detectable deformation percentage. In addition, the higher the relative efficiency of the estimator is, the more precise the
estimated parameters could be and therefore the smaller the size of detectable local deformation could be. It should be
noted that there is a trade-off between estimators with high breakdown points and those with high efficiency [Kumar
and Hanson 1994] [Huang 1990].
3.2 Robust Matching Algorithms
Three robust estimators are employed to robustify the LZD matching algorithms. The first one belongs to the M-
estimators developed by Huber (1981) and other statisticians [Hampel et al. 1986]. M-estimators minimize the sum of a
symmetric, positive-definite function of residuals, © (r;), which has a unique minimum at r; = 0. The LS estimator is a
special case of M-estimators, where 2(r;) = rj. To be robust, the #(r;) function of an M-estimator, which is the
derivative of 2 (r;) with respect to r;, must be bounded. To obtain high efficiency, #(r;) should be linear in the range
near where r;= 0. For computational consideration (i.e. to be scale equivariant), residuals used in M-estimators must be
standardized by means of some estimate of standard deviation of observations. Many M-estimators are constructed to
be robust on the one hand and fairly efficient on the other hand, such as Huber's estimator, Hampel's three-part-
redescending estimator and Turkey's biweight estimator (see Hampel et. al. 1986). These M-estimators have high
efficiencies, typically more than 0.9 [Kumar and Hanson 1994] [Huang 1990]. As a result, if the matching algorithms
are robustified with these M-estimators, we are likely to detect local deformation of small size. However, M-estimators
have breakdown points less than //(p--/), where p is the number of parameters to be estimated [Meer et. al. 1991]
(Rigorously, M-estimators have breakdown points of 0 in presence of high leverage outliers [Rousseeuw and Leroy
1987]. We assume no such outliers exist in our surface matching process. This assumption is experimentally shown to
be satisfied.). In our case of surface matching, p is 6 and the breakdown point is consequently less than 1/7(^0.143).
As we will see, this upper bound is a little bit exceeded and we will analyze the reason. In computation, M-estimators
are usually converted to iterations of reweighted least squares, where weights are determined as »(u) — V(u)/u and are
updated during iterations according to the updated residuals and estimate of standard deviation of observations.
We use Turkey's biweight estimator and the associated weight function is:
(6)
Fact lu c
w(u) =
"EP
where u;—r/ ?and c is a tuning constant and is standard deviation of observations. For M-estimators, it is important
to use a robust estimate of ©. In our study, Cis computed as
6 =1.4826 med
which is fairly robust with a breakdown point of 0.5 [Rousseeuw and Leray 1987]. The constant 1.4826 is used to
achieve consistency at normal error distribution. To make the robust estimator incorporated with the LZD matching
algorithms, the only change required is to replace the weight p; in equation (5.1) by p; X w(uj). The resultant matching
algorithms are called LZD m.
lj
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 1003
