3.2 Formation of Vertical Line Segments 
3.2.1 Vertical Line Grouping 
Line grouping is a complicated process since no prior knowledge is 
available to link isolated edges. In our case, a new grouping 
algorithm is designed based on the vertical line constraint. The main 
concern for grouping is how to achieve a trade-off on gap bridging. 
A strong linking process may produce many false line segments, 
while a weak linking process may lose many important line 
segments. 
It is observed that a vertical object of interest, such as a pole, has two 
vertical boundary lines. As shown in Figure 4, an ideal edge model 
of a vertical object, the edges located along the two boundary lines of 
the same object should have opposite edge directions and be within a 
certain distance. This presents a strong constraint for extraction of 
reliable vertical line features. Based upon the above analysis, the line 
grouping algorithm is composed of two phases: (1) grouping of 
primary line segments (to group the distinct line segments), and (2) 
grouping of secondary line segments (if the detected primary line is 
located on one side of the object boundary lines, the line segments 
parallel to this primary line are to be grouped). 
Phase 1: Grouping of primary line segments 
(1 .a) Scan the edge image from the left-top to the right-bottom, and 
find an unprocessed edge; 
(l.b) Take this edge point as a starting edge point, and construct a 
vertical “bridge” downwards, with a width of 3 pixels (shown 
in Figure 5). The length of the bridge is defined by the 
parameter “length of bridging gap”. In the first phase, only the 
distinct line segments are to be grouped, so that the length of 
bridging gap of 15 pixels is chosen. 
(l.c) If an edge is located in this bridge and its direction is the 
“same” (tolerance is ±15°) as that of the starting edge, this 
edge is recorded as a “compatible edge”, otherwise as an 
“incompatible edge”. 
Case 1: If the distance between a compatible and the starting 
point is less than half of the bridge length (8 pixels), link this 
edge to the starting point, take this edge as a new starting 
point, and go to (l.b). 
Case 2: If no compatible edge exists, but the number of 
compatible edges in this bridge is larger than the number of 
incompatible edges, link the closest compatible edge to the 
starting point, and take this edge as a new starting point. Go to 
(l.b). 
Case 3: If either of the two cases above is not found, go to step 
(l.a) and continue scanning. 
(l.d) Finally, if the length of the line segment composed of linked 
edges surpasses a threshold (50 pixels), the line segment is 
considered as a primary line segment and recorded into a line 
file. 
Phase 2: Grouping of secondary line segments 
The second phase focuses on the grouping of the line segments 
parallel to the primary line segments. This work is used to determine 
the conformance degree of the detected primary line segments. If 
parallel line segments are found, it is assumed that the primary line 
segment is likely located on the boundaries of a vertical object. 
According to the model of Figure 4, an associated line segment 
should have an opposite direction and be within a certain distance to 
the primary line segment. The grouping scheme is similar to the first 
phase except that the length of bridging gap is chosen differently. 
(2.a) Scan the surrounding area of a detected primary line segment 
within a range of ± 10 pixels, and find an edge whose 
direction is opposite to the direction of the primary line 
segment. The average direction value of the compatible edges 
composing the line segment is defined as the line direction. 
A Vertical Object 
An edge model 
Gray A 1 
value T 3 T 
.y=3> 
Edge magnitude 
i À 
o 
= * 
Edge direction 
Length of 
bridging gap 
Figure 4. An ideal edge model of a vertical object Figure 5. Budging grouping model 
Table 1. Representation of line segments 
ID No. 
Xs, Ys, Xe, Ye 
Length 
Number of edges 
Direction 
Stereo 
Parallel 
No. 5 
78 
37 
3° 
True 
True 
No. 6 
52 
18 
186° 
False 
False 
7A-4-3