e disparity limit: disparity is the displacement along 
the epipolar line of the corresponding points. The 
object space always has limited depth, this 
means, the disparity changing on the images also 
has limited range. The introduction of disparity 
limit can significantly reduces the search range of 
matching, therefore reduce the processing time. 
The efficiency of candidate matching depends on 
two aspects: guaranteeing that the all the possible 
matching pairs of lines are in the result of 
candidate matching, and performing the task as 
quick as possible. Our experiments have turned 
out that disparity limit is a very important 
parameter for the success of final matching. 
e orientation: the orientation difference of two 
corresponding lines is not only due to the camera 
geometry, but also to the original direction of 
object line. In our algorithm, we set the maximal 
allowable orientation difference between the two 
corresponding lines in order to eliminate wrong 
line pairs. 
In this step, one line on the image can be assigned to 
more than one corresponding lines on the other image. 
4. BACK-PROJECTION 
After the candidate matching is finished, the image line 
pairs are back-projected into the object space (or scene 
space). Two cases must be considered, that is, on 
whether the image lines are horizontal or not, with 
respect to stereo camera base line. For the non- 
horizontal lines, the back project principle is described 
in Fig.1. In the figure 1, let O-XYZ be the object space 
coordinate system fixed on the ground (scene), S’- 
x’y’z’ and S"-x"y"z" be the left and right camera 
coordinate system with the origin at the focus point of 
the camera and z’,z" coinciding with the optical axis (z’ 
and z" are not shown in the figure). The (a’b’) and 
(a"b") are the candidate image line pair respectively on 
the left and right images. W' is the plane formed by left 
camera focus point and image line (a’b’), similarly with 
W". For image line pair (a’b’) and (a"b"), We define 
the corresponding object line as L. Very often, the 
result from line detection is not perfect, so we can not 
assume the detected lines from image are complete. 
Also due to the limited resolution of image and the error 
in the parameters of camera geometry, the two ray lines 
from the corresponding image points can not be assumed 
to mathematically intersect in the object space. To avoid 
such drawback, we use the intersection of two planes 
W' and W" to get the equation of object line 
corresponding to image lines (a’b’) and (a"b"). 
In the practice, we calculate the coordinates of point A’, 
A", B', B', put the central point of A’ and A" as the 
starting point of line L, the central point of point B' and 
B" as the ending point of line L. 
536 
  
  
  
  
  
Fig.1 Back project for non-horizontal lines 
  
  
  
  
  
Fig.2 Back projection for horizontal lines 
When the image lines are horizontal, the above method 
would obviously fails. Another method should be used, 
as illustrated in Fig.2., where A’ is chosen as the most 
closed point to both ray (s’a’) and (s"a"), similarly with 
A". 
5. GENERAL GEOMETRIC CONSTRAINTS OF 
SCENES 
The concept of geometric constraints has been used by 
a number of researchers!^?, Their ideas mainly concern 
the geometric constraints on camera geometry, actually 
the extension of epipolar line constraints. This kind of 
conditions have been taken care by our algorithm in the 
image space. What we propose in this article about 
GGCS is totally different, which is related to the 
property of objects in the scene. 
An explanation of general geometric constraints of 
scenes (GGCS) 
The idea of utilizing GGCS is to derive as much as 
possible geometric constraints to globally improve the 
matching quality. The primitives used in the matching 
(alse in the image analysis) are the intensity, point, 
straight line, curve, shape, etc. The GGCS concerns the 
geometric constraints on these primitives themselves as 
well as the constraints on the relationship between the 
primitives. So the constraints can be unary, binary, and 
N-nary. All the these constraints are depicted in object 
space. 
IQ 
an 
of 
seg 
seg 
der 
tas] 
res 
me 
Be 
can 
im: 
tog 
spa 
Suc