ow AV tui pin —
c
Yandong Wang
3 HIERARCHICAL GROUPING OF LINE IMAGES
3.1 Generation of Hierarchy of Line Images
After the split-and-merge operation, most non-road lines are split into short line segments while those corresponding to
roads are usually maintained. Thus, non-road line features can be removed by a thresholding operation. However, the
selection of an appropriate threshold is a problem. High threshold can guarantee the elimination of most non-road line
features, but some short line segments corresponding to roads are also removed. Low threshold can keep most road
segments, but does not result in the deletion of non-road line segments efficiently. At the same time, the existence of
many non-road line segments makes the subsequent processing more complicated and may even cause unreliable
results. To solve this problem, several thresholds are used instead of a single threshold to generate a hierarchy of line
images. The line image at the top of hierarchy is generated using the largest threshold while the line image at the bottom
of the hierarchy corresponds to the smallest threshold. In the line image at the top of the hierarchy, main road segments
are retained, while most non-road line segments are removed. Most short line segments are retained in the image at the
bottom of the hierarchy, but some non-road segments are also retained. Hence, line images in the hierarchy complement
each other, and thus they can be combined to yield a more reliable road network from images.
3.2 Hierarchical Grouping of Line Images
Having generated a hierarchy of line images, line segments which are disconnected due to the effects of occlusions and
other factors need to be grouped to form a road network. It can be seen that line images in the hierarchy have different
characteristics. The line image at the top of the hierarchy possesses major line segments, most of which correspond to
roads, while the line image at the bottom of the hierarchy contains most detailed information of roads and some non-
road features as well. It might be easier to start grouping from the top of the hierarchy considering the simple structure
of the line image at this level. However, some road parts cannot be extracted correctly as short line segments are
removed in the line image at this level. Therefore, hierarchical grouping is proposed in this study, which commences
from the top of the hierarchy and proceeds to the bottom. In grouping at top level, a main structure of road network can
be formed reliably because non-road line features are removed in the line image at this level. In order to extract missing
road segments, grouping proceeds to the next lower level and the results of the grouping achieved so far are used as a
guide for grouping at this level. In this way, grouping is performed at each level until the lowest level of the hierarchy is
reached. When grouping is performed through the hierarchy, more details of the road network can be detected. As
grouping of line images is done hierarchically and the results of grouping at higher level is used at lower level, the
effects of non-road features can be greatly eliminated, and thus a more reliable road network can be extracted.
In the grouping of line segments, collinearity and proximity are two commonly used criteria (Vasudevan, et al, 1988).
When satellite and aerial images have simple structures, good grouping results can be achieved by using these two
criteria. However, these criteria alone cannot yield satisfactory results when images have complex structures. In order to
yield reliable grouping results, geometric and radiometric properties of features should be used (Henricsson, 1996;
Wang, 1999) and a fuzzy function can be used to evaluate the quality of different connections (Steger, et al, 1997). It is
assumed that two lines should be collinear in space and close to each other if they are two neighbouring segments
belonging to the same road. At the same time, they should have similar geometric and radiometric properties. Thus, a
grouping method similar to that used in Henricsson (1996), based on the similarity of geometric and radiometric
properties of lines, is used in this study. To evaluate the similarity of two lines, a function which is the product of four
similarity functions is defined, which has the following form:
S = S$, %S,%¢S x8, (1)
Where S,, S,, S, and S, are four functions describing similarities of lines in distance, spatial orientation, gray value and
gradient orientation respectively.
All of these four functions are defined by a Gaussian function. For example, S, is defined as:
Aaj Aa3
-( T + D )
S,=3 ^ : if Ae, «T,and Ad, <T, (2)
0
Where Ao, and Ao, are the differences of spatial orientations between two lines and their connections, and T, is the
corresponding threshold.
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 945
