nes 
  
nethod 
used, 
e most 
y with 
S OF 
sed by 
yncern 
tually 
ind of 
in the 
about 
lo the 
nts of 
ich as 
ve the 
tching 
point, 
ns the 
ves as 
en the 
y, and 
object 
GGCS for lines 
Unary constraints : 
orientation of line; 
length of line; 
etc. 
Binary constraints : 
1). Collinearity. 
Collinearity means that two lines have same 
mathematical equation. It is easy to see that the starting 
points and ending point for two lines are not necessarily 
to be the same for the collinearity. 
2). Overlapping. 
Two lines are said to be overlapping if they are collinear 
and have common range. 
3). Connectivity. 
Two lines are connected if lines are mathematically 
intersected and the intersecting point is within the 
starting point and ending point for both lines. 
4). Coplanarity. 
Two lines are coplanarity if they are on the same plane. 
5). Parallel. 
The general attributes to describe the relationship of two 
lines can be summarized as following: 
distance between a pair of lines (shortest distance) 
distance between the endpoints of two line segments 
(including shortest distance between the endpoints 
of two line 
segments as well as longest distance) 
distance between the midpoints of two line 
segments 
distance from a line to the origin, and 
distance from a line to an endpoints of a line 
segment. 
overlapping range 
intersecting angle 
coordinates of intersecting point 
difference of lengths 
What type of GGCS should be used is task and scene 
dependent. The generation of suitable GGCS for specific 
task, specific scenes or objects will initialize other 
research issues, that is, the generic modelling, learning 
mechanism, and related man-machine interface, etc. 
6. FINAL MATCHING IN OBJECT SPACE 
Because in the image space, it is allowed that one line 
can be matched with more than one lines on the other 
image, we need to implement the uniqueness constraints 
together with GGCS and other constraints in object 
space. 
Such problem is a typical consistent labelling or 
537 
constrained satisfaction problem which was formulated 
by Haralick and Shapiro. In our current algorithm, 
we use the relaxation techniques which is frequently 
used in the computer vision community. 
We assign each candidate object line (i) a label LB(i) 
which ranges from 0 to 1.0 . After the relaxation, the 
line with label "1" means a true scene line, while a "0" 
indicate a false line. The initial label value for each line 
is bound in the image space matching (e.g. from 
similarity measurement of contrast). The label value is 
then updated in the iteration by the following formula. 
LB()**! = (1.0 + 06) LB()* 4 o,a 
- B,(b; + b,) - B,c 2) 
where 
LB(i)** is updated label value 
LB(i)* is old label value 
k is the number of iteration 
0, is the coefficient for increment from old label 
0, is the coefficient for increment from GGCS 
B, is the coefficient for decrease from uniqueness 
constraints. 
B, is the coefficient for decrease from ordering 
constraints. 
a is the measure for the GGCS 
b,,b, is the measure for uniqueness constraint 
c is the measure for ordering constraint 
7. EXPERIMENTAL RESULTS 
Experiment on simulated data 
  
  
  
Fig.4 Simulated left and right images (lines)