the 
and 
mo, 
1ave 
(1) 
(2) 
Boehm, Jan 
   
ERR 
  
  
m 
  
(a) surface fitting using im- (b) plot of mean curvature (c) plot of Gaussian curvature (d) local coordinate system 
plicit coordinate system across the sphere across sphere aligned to surface normal 
Figure 5: Curvature on a sphere. The images display the z (depth) values. The superimposed marking indicate the areas 
where mean and Gaussian Curvature have correct values. The quality of curvature estimation can be greatly increased 
when a local coordinate system for surface fitting is used which is aligned to the normal of the surface. 
3 DERIVING FEATURES FROM RANGE IMAGES 
3.1 Curvature 
As for the CAD model the curvature has also to be computed for the range image. Several schemes have been proposed for 
curvature estimation. Some techniques were developed especially for triangulated surfaces. However, these techniques 
usually use only a very small neighborhood of the inspected point and therefore deliver unreliable results. Other methods 
assume raster organization of the data. The simplest uses convolution to determine the derivatives needed to compute H 
and K. However, second order derivatives are susceptible to noise. More elaborate techniques fit second order bivariate 
polynomials of the form z = f(x,y) to the data using least squares techniques. The fitting is done in a small rectangular 
neighborhood of the point. Using the coefficients of the polynomial the derivatives are computed analytically. The results 
are then stored for the center pixel of the window which is moved over the data. 
A very fast implementation of this approach has been reported by Paul J. Besl (Besl, 1988). He formulated the surface 
fitting process as a series of convolutions thus speeding up processing. Two reasons prevented us from using his approach: 
First the range image is assumed to be equally spaced in x and y direction. Unfortunately, due to the nature of most sensors 
the distance in x and y of two neighbor pixels is not constant across the image, but is usually dependent on the z value. 
The second reason concerns the coordinate system of the data to be fit. Every result of a 3D measurement is stored in 
a certain coordinate system usually determined during sensor calibration. Let us call this coordinate system the implicit 
coordinate system. For range images it is quite typical for x and y to lie in the image plane and z perpendicular to it, 
for example pointing towards the viewer. When a function of the form z = f(x,y) is fit to the data the error criterion 
Y f(zi,yi) — zi)? is minimized. It is important to notice that the residuals of the regression are taken along the z axis. 
They do not necessarily represent the orthogonal distance of the point to the estimated surface. The more the surface 
normal deviates from the z axis, the less the residuals represent true geometric distances. This leads to errors in surface 
fitting. 
One way to solve this problem is to use implicit polynomials of the form F(z,y,z) — 0. However true orthogonal 
distance regression of implicit polynomials is a non-linear process as shown by Nicholas J. Redding (Redding, 2000). 
Our way to overcome the problem is to transform the points to a local coordinate system which has its z axis aligned to 
the local Normal vector as proposed in (Flynn and Jain, 1989). This also requires additional computations. First the local 
normal vector has to be estimated. Second all the data points within the window have to be transformed. Figures 5(a) 
through (c) show some experiments with a synthetic sphere. At the center of the sphere the surface normal is in alignment 
to the z axis of the implicit coordinate system. Therefore the local surface fitting is correct and so are the derived values 
for mean and Gaussian curvature. But towards the edge of the sphere Gaussian curvature starts to deviate greatly from the 
theoretical value. This can be prohibited with the proposed method of local transformation as shown in figure 5(d). 
32 Classification 
After mean and Gaussian curvature have been computed for each valid pixel in the range image, the output from the CAD 
System is used for classification of the range image. A simple minimum distance classification has been implemented. 
At the beginning all the pixels are unclassified. Then each pixel of the range image is transformed into a feature vector 
p = (H;, K;) in HK space. The distance of this feature vector to each of the features derived from the CAD model is 
  
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B5. Amsterdam 2000. 79