The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part Bl. Beijing 2008 
972 
positions within the image, and the ranges are represented by 
the pixel values. 
In a recent paper we introduced a range image segmentation 
algorithm (Gorte, 2007), which groups adjacent pixels obtained 
from co-planar 3D points into segments. The adjacency of 
pixels can be obtained from a range image, whereas co 
planarity is derived from image gradients, taking the scan 
angles into account. The method is based on a parameterization 
of a plane with respect to the local coordinate system of the 
laser scanner, in which the scanner is at the origin (Fig. 1). 
Fig. 1: Parametric form of a plane in 3D. 
4. Computing the third parameter p of the normal vector 
using p=x cos #cos (fr+y sin 9 cos (f> + z sin <j) (see Fig. 
1). 
5. Image segmentation: On the basis of the three features 
from steps 2, 3 and 4, a quadtree based region-merging 
image segmentation (Gorte, 1998) is carried out to group 
adjacent pixels with similar feature values, i.e. pixels that 
are now expected to belong to the same plane in 3D, into 
segments. 
The entire method consists of 2d image processing operations: 
gradient filtering, image arithmetic and image segmentation, 
which makes the algorithm extremely fast compared to point 
cloud segmentations working in 3D. 
The segmentation algorithm attempts to group adjacent range 
image pixels into segments, as far as these pixels belong to the 
same plane. This is accomplished by estimating in each pixel 
the parameters of the normal vector of that plane. These 
parameters are: two angles 9 (horizontal) and <j> (vertical) and 
the length of the vector p. This is the perpendicular distance 
between the plane and the origin. 
The algorithm consists of the following steps: 
1. Computing gradient images gx and gy on the range image. 
These images denote at each row and column the change 
that occurs in the image value when moving one pixel 
horizontally and vertically respectively. 
2. Computing the angle A 9 = atan (gx/RAa) between the 
horizontal laser beam angle a and the horizontal normal 
vector angle 9 on the basis of the gradient in ¿-direction 
gx. A a is the angular resolution of the scanner in 
horizontal direction. Now the first parameter of the normal 
vector of the plane, the horizontal angle 9, is known. 
3. Computing the angle A</>' = atan (gy/RA/3) on the basis of 
the gradient in y-direction gy. A/3 is the angular resolution 
of the scanner in vertical direction. This yields (f>' (see Fig. 
2). To obtain the second parameter of the normal vector, 
the vertical angle </>, a correction has to be applied given 
by: 
tan </> 
tan </> 
u 
IT 
= cos (a-9) 
The computation is illustrated in Fig. 3. 
Fig. 2: The gradient determines the angle between the laser 
beam and the normal vector of a plane. 
Fig. 3: A laser beam L with a direction given by a and /?hitting 
a plane at range R, and the plane’s normal vector A with 
parameters 9, <j) and p.