118 
4. Segmentation. Regions with a high correlation result belong to objects located in the separation surface. These 
objects are extracted by applying a threshold to the correlation values. Although the segmentation is very simple, 
results show that it is sufficient. 
5. Texture Analysis. A correct correlation result can only be obtained if there exists enough texture in the image. 
Low texture may result in an incorrect but acceptable correlation measure, which must be eliminated by a texture 
analysis, that excludes low textured regions. 
6. Reaction. The Robot may stop or change its path, a mobile robot may slow down. 
Steps 1. to 5. must be processed in real time. In order to allow a dynamic change of the separation surface, the real time 
part is superimposed by a process which controls the change of the separation surface and recalculates the necessary 
parameters. All except the selection process are low level functions that must be performed on the whole image and 
therefore are candidates for a processing on a specialized image processor. 
3. SOFTWARE IMPLEMENTATION 
In order to prove the feasibility of our method and to obtain first results we implemented the method in software, using 
real images and the same cameras as for the planned hardware implementation. The software was developed with the 
image processing development tool KHOROS”. Preliminary examinations (Rechsteiner et al., 1994) showed that the 
binary correlation method according to Nishihara (Nishihara, 1984) and a correlation based on direction information are 
well suited for this application. 
3.1 Calculation of Transformation Parameters 
For the prototype implementation we calculate the parameters for the geometric transformation without complete cali- 
bration of the cameras. In the case of the separation surface being a plane (a.X -- bY -- Z — d) and of arbitrarily placed 
cameras with the homogeneous projective matrix Mi; and M» it can be shown, that the image transformation is described 
by a homogeneous 3x3 transformation matrix P: 
X X 
$1U1 Y 32U2 Y pi pi pia 
b, =} sim | = Mi z |; ba = | soava | = M2 Z => b=lfÿi Pa ps|^ Ph (1) 
31 1 82 1 pai p32 ps3 
Measuring at least 8 points on the desired separation plane an over-determined linear equation system is obtained and 
is solved with a least square technique (singular value decomposition). 
In future we will completely calibrate (intrinsic and extrinsic parameters and first order of radial distortion) the cameras 
in order to be able to calculate the transformation parameters from an analytical description of a separation surface. In 
addition, taking the radial distortion parameters into consideration will improve the results. 
3.2 Algorithms 
The method consists of a few, very efficient algorithms, especially chosen for a processing in real time. 
3.2.1 Geometric image transformation. Bilinear interpolation on four neighbouring pixels is used. Experiments 
showed that the error introduced by a nearest neighbour transformation is much higher than the error introduced by 
using bilinear interpolation. Due to the small baseline of the camera-rig compared to the object distance, the scale factor 
of the geometric transformation is about 1.0, therefore a neighbourhood of only four pixels is sufficient. 
3.2.2 Prefiltering and Correlation. Two different methods (Nishihara and Sobel-direction correlation) to compare 
images were implemented. Both methods consist of two processing steps (filtering, correlation) and work on image data 
preprocessed with a kind of highpass filter. As a consequence, the correlation result is very independent of the mean 
greylevel in the images. The necessary prefiltering depends on the correlation method, the system noise and the aimed 
thickness of the separation surface. It consists of a lowpass filter which decreases the influence of noise and a filter to 
preprocess the data for the subsequent correlation. 
Nishihara: For the binary correlation according to Nishihara the image is prefiltered with a Laplace-Gauss FIR filter 
with coefficients LoG(i, j) where r? — (i — n)? + (5 — n)? is the distance from the filter mask center, and w defines 
the band-limit of the filter (eq. 2). The exact filter has an infinite mask size. We chose the mask size such that 
the largest coefficient at the edge is smaller than 0.5959 of the center weight, which results in a size of n — 11. For 
correlation only the sign (rs, ss = +1) of the Laplace-Gauss filtered images is used: 
= ar? (-4:2) = 
LoG(1, 3) — (x — 2) e\ vi), CN = > ro(u, v) ss(u,v) (2) 
u,v 
  
*Khoros is a registered trademark of Khoral Research, Inc., New Mexico 
IAPRS, Vol. 30, Part 5W1, ISPRS Intercommission Workshop “From Pixels to Sequences”, Zurich, March 22-24 1995