International Archives of the
The process has three steps; line segment extraction, dominant
direction detection and image splitting with quadtree data
structure.
2.1 Line Segment Extraction
Calculating a road’s dominant road direction Starts from
extracting the line segments from the edge image since most of
the roads in the urban area are line-shaped and edge detection is
the most common method for extracting meaningful
discontinuities imagery. We can't say extracted line segments
from edges are all belonging to roads, because so many features
in urban areas have also line shape edges. In addition, building
edges and road edges are often parallel. So we can use most of
the line shaped edges for calculating road directions even
though they correspond for non-road features.
To extract the line segments, the Canny operator is applied to
track all edges. Since the file size of modern imagery are quite
large, we downsampled the imagery to work at reduced
resolution. By reducing the resolution, much information is lost
but to determine only the region's dominant direction, using a
reduced resolution image is sufficient. The image for our study
area and its detected edges are shown in Figure 1. The binary
image for the canny detected edges is shown in Figure Ib, with
black pixels represents the edges. Those edge pixels are for
buildings, roads, trees, cars, and other features.
(a) (b)
Figure 1: Image for study area and its edges. (a) Aerial image
over Purdue Campus (b) Detected edges with reduced
resolution image by canny algorithm
Figure 2. Extracted line segments with proposed algorithm
To get line-shaped edges (line segments), we propose following
method. We use polar coordinate, which use p-0, to
parameterize the line.
First, we examine the search window, of size 20 x 20 pixel.
This search window will adjoin ones by 3 pixels. Next, all
components are 8-connected labeled to determine pixel groups
466
Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
and each group's pixel elements p-0. Based on calculated p-0,
pixels in the group are checked whether all pixels are on the
line equation or not. If all pixels are on the line equation, this
group is treated as “straight line”. If not, the group will be
eliminated.
Conditions for being treated as straight line are as follows;
- Length of group is more than limit
- At least one pixel of group touches the boundary of search
window
- p-0 are calculated by using any two pixels in the group and all
pixels should lie on this line (Tolerance is 1 pixel).
Extracted line segments are shown in Figure 2.
22 Dominant Direction Detection
We will subdivide an image block (parent region) into four
quadrant image blocks (child regions) if the parent region has
more than two dominant road directions. To decide about
splitting or not, we must calculate the number of dominant
directions in the region of interest. For determining the
dominant direction in the scene, several approaches have been
studied. Getting dominant directions in a scene is usually begun
by straight line detection for most of the research groups. Then
each line's gradient is calculated and line length is accumulated
into a histogram. The problem is selecting dominant directions
in this histogram.
Sohn and Dowman (2001) used a. hierarchical histogram-
clustering method to obtain dominant direction. They derived
line angle information and quantized it into a histogram.
Corresponding line length of each angle is accumulated to make
many pixels contribute more to determine dominant angle peaks.
Once the highest peak angle is obtained, angle discrepancies
less than angle thresholds from peak angle are checked as one
set. Their geometries are modified to conform to the peak angle.
In subsequent searching, these modified and the checked sets
are ignored. In this paper, we propose a modified hierarchical
histogram-clustering method. We calculate the angle for each
line, eliminate some lines with 90-degree filtering, threshold to
make angle-pixel on histogram and then apply hierarchical
histogram-clustering.
To calculate each line's angle, the Hough transform is used and
Figure 3a is the result of calculating all line's angle and length.
In Figure 3a and Figure 3b, circles represent each line's angle
from 0 to 90 degree on the X axis, and length is represented by
the Y axis.
p ———— T
prior
Figure 3. Angle — length relationship for line segments. (a)
Angle and length for all line segments. (b) Result after 90-dgree
filtering. (c) Histogram after 90-dgree filtering and threshold.
Our region of interest is an urban area and we already assume
that urban roads form a kind of grid pattern. The grid is
composed of two main directions which are perpendicular to
each other. Also, because we searched a wide area, even if a
certain line segment has a perpendicular segment, the two
segments may have no relationship with the grid. Searching all
line directions, we eliminated the lines that have no
Inter
perp
degr
Afte
leng
total
repr
total
it is
algo
to be
Fron
abot
matt
dom
clus!
mak
angl
Whe
has
92.5
2.3]
The
imag
of di
quad
simi
metl
Let
sub i
(a) x
4
(b) A
(c) A
(d) /
direc
Regi
P(R;
of dc
repre
repre
Lett
entire
has 0
stop
quad
one
Othe
disjo
