International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004 
  
Figure 4. Point heights along the long-section and the 
interpolated elevation of the centerline 
4. DELAUNAY-TRIANGULATION 
The other way to get vehicle points is using Delaunay- 
triangulation. Figure 5 shows the calculated triangles on the test 
area. 
The grayscale image is color-coded for the triangle slopes: 
hence this can be the basis of vehicle segmentation. This 
method is accurate, precise, and less sensitive for errors. 
  
    
745730 746740 746750 746760 748770 7486790 
Figure 5. Result of the Delaunay-triangulation and the grayscale 
image, representing triangles slope 
Using Delaunay-triangulation for the initial data set, the non- 
regular network of triangles can be created; this method 
minimizes data loss caused by interpolation, however, it is hard 
to handle this network. The creation. of these triangles is 
automatic, therefore, the special characteristics of the road, 
vehicles and landmarks cannot be considered. 
158 
The method presented here is based on triangulation. The 
gradients of the triangles are very dissimilar, but there are only 
slight differences between the heights of points in neighboring 
triangles. 
First, we calculate the slope angle of each triangle to a reference 
plane that is practically the approximate position of the road 
surface; this value in radians is linked to the center of gravity of 
the triangles. This is still insufficient information to separate 
vehicles because triangles contain also points reflected from the 
surface of the road, therefore, resulting in very different slope 
angles. In the test data, the horizontal distance between points is 
generally less than the distance from the road surface and the 
points reflected back from vehicles. The perimeter of a triangle 
gives information about the slope of it; if both the slope and the 
perimeter of a triangle is big, then the triangle most likely 
belongs to the boundary of a vehicle. Using the centerline of the 
road and lane parameters, triangles at the sides of lanes could be 
filtered out. 
A vehicle is found, if the bordering triangles are tend to have 
slope angles in the same direction, like the walls of a tent, and 
there is a space between these "walls". The vehicle envelope 
can be achieved, fitting a polygon on the points found (only 
vertically), one for higher ones, one for the lower ones. which 
are on the same level as the road. Separating points for these 
two polygons could be achieved using heights; inside the higher 
level polygon -as a fence- including points fitting on polygon 
we could get the vehicle points. The extensions of vehicles 
could also help filter out some wrong triangles. (See Figure 3 
for vertical, Figure 4 for horizontal triangle errors) (Sederberg 
ct al. 1985). 
5. CLASSIFICATION 
The segmentation of vehicles from this pre-processed data is 
based on the remaining triangles. First. the distances between 
each pair of observation points are calculated. These can be 
used to compute the hierarchical cluster information based on 
the single linkage algorithm. Then. we could define clusters for 
each vehicle using the resulting cluster-tree. 
For each cluster representing a vehicle we make a principal 
component analysis, to get eigenvectors, which stretches a 
coordinate system. The length of the vectors carries information 
about the dimensions of the vehicle, while the orientation has 
about the moving direction. 
In the introduction we mentioned the potential of using image- 
processing techniques for segmentation. 
  
Figure 6. Intensity image of the surface 
The intensity of pixels is derived from their height, after 
creating the covering surface (Figure 6.). The network is regular 
rectangular, the pixel size should be less than the minimal 
distance between the points in the point cloud. We used bilinear 
interpolation for calculating the pixel values. 
Internati 
  
[t is easie 
original 
threshold 
the road, 
road poir 
In Figur 
connectei 
neighbor 
classes; e 
This pap 
LiDAR p 
The com 
shown in 
Thresl 
Triang 
hm 2e 
Image 
LI — A 
  
In Figur: 
Because 
operates 
provides 
algorithn 
technique 
F 
(Red -' 
The resul 
segmenta 
to result |