7A-2-4 
The above algorithm is relatively sensitive to the noise and may 
lead to over-segmentation. In practice, the image segmentation 
through watershed transformation depends largely on the 
selection of the regions with minima. We can then focus on 
gradient image with discriminative features. 
Figure 6. Results after a watershed transformation 
4. ROBUST EDGE SELECTION AND LINKING 
4.1 Morphological Edge Selection and Conditional Edge 
Aggregation 
So far, the detected edges are still represented by discrete edge 
points. They are to be aggregated and linked to form explicit 
edges/lines. A morphological edge selection algorithm was 
developed (Li et al., 1998). A morphological thinning 
transformation on a graph X (such as an image in Figure 6) 
yields a new graph 
x'=xom),i=ox-i ( 6 ) 
with the structure elements as 
• 1 0 
¿.=0 0 1 i -12(5,7, i plus2, clockwisly rotates^ 
0 0 • 
0 10 
¿=0 O 1 /=2,4,6,8, i plus2, clockwisly rotates^ 
0 0 0 
A cleaning transformation eliminates noise (short lines) by 
x'=(x'o{£; })©{£; };X, i=o,i, 7 
(7) 
where the structure elements are defined as 
2 2 2 
herelrepresnets either 0 or \ 
£=0 0 0 _/ 
0 0 0 1 = ®d»" ’>7, * plus 1, clockwisly rotates 
As a result, segments with lengths larger than a selected threshold 
are preserved by conditional dilation. At the refined resolution, 
the edge segments selected at the initial resolution are expanded 
by a so-called end-point conditional dilation. In this process, the 
end points are first searched through a hit-or-miss 
transformation; next, the selected end points are expanded in an 
image window (3 x 3); and finally, the expanded pixels, with 
intersection of edges at the refined resolution, are combined with 
the input edges. The procedure for conditional edge aggregation 
can be mathematically expressed as: 
X'=(Jx'0£;.)©{£;.};X 2 ' (8) 
/=0 
where X, andx^ represents selected edge graphs at the initial 
and the refined resolutions respectively, ® denotes the 
morphological hit-or-miss transformation, and the structure £ is 
0 0 0 
=0 0 0 i =0,1,-• -,7, i plus\, clockwisly rotates ^ 
0 1 0 
Figure 7 is the result of morphological edge selection and 
conditional edge aggregation based on Figure 6. 
"> '\ 
— - - ■ ^ ~V 
(a) (b) 
J-.r 4-_ - 
v 1 ^ 
~~ 1 
1 1 ' r — 
_ ni ~ L— 
(c) (d) 
Figure 7. Edge selection and aggregation results based on 
Figure 6 
4.2 Local Edge Linking 
Local edges are selected within a small window (e.g. 3 x 3 or 5 x 
5) in the image. If there is only a pair of end points in the 
window, they are connected directly. If there are more than two 
points, the pair of end points with the same gradient direction 
and the minimum interval is linked. The end points are acquired 
through a morphological hit-or-miss transformation with the 
structure element ^ defined in Equation (9) above. To avoid the 
time consuming task of point-to-point comparison for end-point 
match determination, our method performs a simultaneous 
dilation of all deleted end points in the direction of the contour 
(perpendicular to the gradient). The dilation is performed until 
each end point meets another end point moving in the same 
direction. 
4.3 Curve Fitting for Global Edge Linking 
If a priori information about the expected shapes of objects is 
available (e.g. an expected rectangle for a truck or house), fitting 
may be carried out directly based on the desired shape. A simple 
piecewise linear curve-fitting procedure is to iteratively fit the 
end points. In the first stage of the algorithm, end points are