9-11 Nov 1999 
  
  
  
  
ts. (a) Photograph of the 
ding from laser points using 
square and circle mark laser 
ne, spiral shows the perspec- 
:) interpolation of laser data 
iterpolation of laser data by 
International Archives of Photogrammetry and Remote Sensing, Vol. 32, Part 3W14, La Jolla, CA, 9-11 Nov. 1999 
Input range image 
  
Detect range edges 
  
Compute initial threshold for smooth regions 
Compute initial count for seed points 
| Extract smooth regions and seed points EEE 
I 
> 
  
  
  
  
  
  
| If seed not already covered | 
  
  
E Find best approximating model | 
  
  
  
| Expand entire image and prune | Update threshold 
and count 
A 
  
  
  
   
      
  
   
  
  
  
No 
  
Resolve ambiguities 
Remove isolated points 
Fill gaps 
Figure 4: Block diagram of complete robust surface perception 
scheme 
  
  
  
seed selection. For example [Besl, 1988] extracts connected 
regions from the HK-sign map (mean and Gaussian curva- 
tures), and erodes these regions until sufficiently small regions 
remain. By a seed point, we mean the center of the seed win- 
dow. In the RSE approach, first simple 2D edge detector is 
used to locate smooth regions. Points which are centers of 
the largest, contiguous regions, are identified. Finally, redun- 
dant seeds are eliminated. The procedure is implemented in 
a loop, starting with stringent criterias for smoothness and 
minimum size of smooth regions. These thresholds are de- 
creased in every iteration. Seed selection stops when all the 
data have been covered by at least one surface, except for 
isolated singletons and pairs, or when no smooth region left. 
5.5 Choosing best approximating model 
The next step is to choose the best approximating model from 
planar and biquadratic models for each seed point. In this 
subsection first the robust M-estimator, the Robust Sequen- 
tial Estimator (RSE), and the information theoretic model se- 
lection is introduced briefly followed by the description of the 
procedure used for selecting the best approximating model. 
Robust M-Estimator Robust estimators are more efficient 
(lower variance) than least squares (LS) if the errors are not 
normally distributed, as is the case in laser scanning. They 
are only slightly less effective than LS if the error has normal 
distribution. We use a maximum likelihood (M)-estimator 
as a robust estimator for the t distribution error model that 
we assume for the ALR data (Section 4). Unfortunately, the 
direct evaluation of maximum likelihood estimates from non- 
normal distributions becomes quite complicated. Therefore, 
estimates are obtained by using iteratively reweighted least 
squares (IRLS). Let p(c;) be any differentiable error density 
function which can be written in the form 
= Ei,2 
p(e) ao7'g{(&)°} (4) 
where o is the scale parameter, g{.} denotes a functional 
form, and. € = 2; — > 0j, is the i^^ actual error from 
eq.1. After computing the log-likelihood for 0 and o? we get 
a set of nonlinear equations. These nonlinear equations can 
be solved using IRLS. Rewriting the equations in matrix form 
X"W(s- X6) —0 (5) 
where W is a diagonal weight matrix whose elements depend 
on the residuals, since 
> ol 
wi = wi(f,07) = ZI oe (6) 
The resulting iterative scheme, after simplification, is given 
by 
Oi E Duis + (aT WA AX) IxTW, a = X6, 1) (7) 
For a t distribution having a degree of freedom f and scaled 
by a parameter c 
gl(ei/0)?] = [1 + d/(02) C 1n (8) 
Substituting this expression for g in (6) yields the individual 
weights: 
euh. 
aupres 
where the residual r; = =; — Bot Ojr;j. We use s in this 
(9) 
Wi 
expression to distinguish the (unknown) true value of the scale 
parameter, c, from an estimated value, s, used in computing 
the weights. These weights are then assigned to the diagonal 
elements of the weighting matrix, W, and (7) is used to 
update the parameters. 
Robust Sequential Estimator (RSE) The RSE is a robust 
extension of the sequential least squares (SLS) estimator. 
The RSE can be applied to any linear regression model of 
the type defined in (1). In the SLS algorithm, equal weights 
are assigned to every data point, while the RSE differentiates 
between valid data and outliers through its weighting mech- 
anism. That is, the RSE rejects any data point which fails to 
qualify as possibly valid for the current surface model. The 
RSE does not remove these data points from the data set en- 
tirely - just from the current surface. The estimation starts 
from an initial robust estimate of the surface parameters in 
a small neighborhood centered around a seed point. The 
parameters of the fitted surface are computed by IRLS with 
errors assumed to be t distributed. The RSE then adds the 
remaining data sequentially, assigning weights to each new 
observation based on the previous surface estimate. 
Information theoretic model selection We have to choose 
the best approximating model from a given set of models be- 
fore we can apply the RSE. Since models with more parame- 
ters fit the data better, the selection criteria should balance 
complexity with goodness of fit. The Akaike Information Cri- 
terion (AIC) is a powerful tool for choosing among differ- 
ent regression models. The asymptotically consistent AIC 
(CAlC)is a generalization of the Akaike Information Criterion 
(AIC) by making it asymptotically consistent and by penaliz- 
ing over parameterization more stringently to avoid modeling