Figure 3: The road edges of sequential stereo-pairs were automatically extracted by the 
described algorithm. 
4. FOLLOWING OF ROAD EDGES 
This procedure is used to trace almost vertical lines in 
digital images. We assume that a starting point is available; 
it can be found by manual selection on the computer 
monitor, or by edge extraction as described previously. 
The objective of this procedure is to follow a line, such as 
the edge of the road, in an image-pair from the bottom to 
the top or along a sequence of images at the same 
horizontal line. In our extended version we can get 3- 
dimensional coordinates of the edge points in object space. 
This algorithm could be directly implemented in the GPS- 
Van to automatically trace the edges through the image 
sequence while the vehicle is moving. 
As the lines to be followed in the road images are 
almost vertical, we only need to check the horizontal off-set 
of the feature when we move from one scan-line to the 
next. For this purpose the least squares image matching 
technique was modified. We have to solve for only one 
horizontal shift parameter per line. Equation (3) gives the 
gray-value equation which can be written for each pixel of 
the matching window. This window should be rectangular 
with a larger horizontal extension; we could limit this 
rectangle to only one line of pixels. 
F(x,yi) = gx, yx) + 8x(x9, Yi) dx (3) 
Le template window at line i, 
g(x2, yi.)....... search window at an approximate 
horizontal location (x?) at line k, 
8x(X%, Yk)..... gray-value derivative in the x-direction, 
I unknown shift parameter. 
122 
  
  
  
Figure 4: Following the edge of a road in one image. 
Figure 4 shows the basic procedure of tracking a road 
edge starting at the lowest line of the image. First, we 
define a template at the position of the known edge (x, yi) (f 
- window) and match it to another window (g), which is a 
few pixels above the original (scan-line k). As a result, we 
get the offset (dx) of the center of the template in the search 
area. This gives us our next template position. Basically, 
the displayed pair of windows (f and g) is just shifted 
towards the top by a few lines. At this location the 
matching is repeated. As we solve for only one parameter 
(dx) the solution of the normal equations is done by a 
simple division. If the correlation coefficient between 
template and matching window is too small after modeling, 
line following is terminated this means that the two 
windows show different gray-value patterns, or if the 
computed precision of the horizontal shift parameter is too 
large, which indicates an unreliable match. This happens at 
the upper half of the image, where the contrast of the road 
edge is fading. 
et 65 vt A 
cat gas anui v ale ss tmd RR 
N A a