il 2004
ed p-0,
on the
jn, this
will be
2t
>»
search
and all
to four
ion has
> about
yminant
ng the
ve been
y begun
s. Then
mulated
rections
togram-
derived
togram.
to make
le peaks.
,»pancies
] as one
k angle.
ked sets
'archical
for each
shold to
rarchical
1sed and
d length.
"s angle
ented by
nh
ents. (a)
90-dgree
shold.
y assume
> grid is
licular to
even if a
the two
rching all
have no
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004
perpendicular pair in region of interest. That is so called '*90-
degree filtering". Figure 3b is the result for 90-degree filtering.
After 90-dgree filtering, we make a length threshold. If the
length of a perpendicular pair is less than 1 percent of region's
total length of line segments, that pair is eliminated. Figure 3c
represents the filtered histogram in which the bin counts are the
total number of pixels (length summation of line segments) and
it is used for determine dominant direction of region. By this
algorithm, we can expect non-road and non-building roof edges
to be ignored.
From the Figure 3c, this region has four dominant directions
about 0°, 45°, 90°, 135°, by intuitive inspection. We need
mathematically separate it to determine the number of
dominant direction. We used a hierarchical histogram-
clustering method to determine the dominant angle set. After
making dominant angle sets, we can calculate a representative
angle for each set by following equations.
S 9, xn,
Oum =
Y»
Where n; is the length of line. As a consequence, the study area
has four dominant directions, and the angles are 2.9°, 42.2°,
02.5°, md 132.15.
2.3 Image Splitting with Quadtree Data Structure
The objective of Image splitting in this paper is to partition an
image into regions until all regions have their own single pair
of dominant directions. To partition the image, we applied the
quadtree data structure. The following basic formulation is very
similar to Gonzalez’ (1992) Region-Oriented Segmentation
method.
Let R represent the whole image region and it is divided into n
sub regions liker Rj, R» ..... R, such that
(a) X
EI
i=l
(b) R; is a rectangular region, i=1,2,..... n,
(c) RAR; is null set for all / and j, i 7 j,
(d) P(R;) =TRUE if this region has only one pair of dominant
direction.
Region is subdivided into four disjointed quadrants region if
P(R;) =FALSE. That means the R; region has more than one pair
of dominant direction. This splitting technique has a convenient
representation form called the quadtree. Quadtree concept is
represented in Figure 4.
j=1 cos a den
ñ
2
2
R | Ri | R (Re) (Re)
e | tiit. * : «C CSS.
| Rut | Ru E C NONE D d s
Ri Ru Re), [Ra } [Ru {Ra} (Re } (Ro) (Re
Re | Re »
Figure 4. Concept for Quadtree image splitting
Let the size of the entire image be m x n. First, calculate the
entire image (R)'s dominant directions and if the entire region
has only one pair of dominant directions, then image splitting is
stopped. Otherwise, this region is subdivided into disjoint four
quadrant regions (Rj, R» R;, R;). Second, if each A; has only
one pair of dominant directions, then splitting is stopped.
Otherwise, each region is subdivided again into four quadrant
disjoint rectangular regions of which size is m/2 x n/2. This
process proceeds until all regions have their own pair of
dominant directions or the region reaches a lower threshold
limit. The region threshold can be predefined as a city block
size (MiNpioex). The region segmentation result is shown in
Figure 5. The red rectangle is the region which has one pair of
dominant directions and the yellow region denote that dominant
directions are not determined and splitting is stopped because
the minimum size threshold has been reached. The reason why
those regions don’t have one pair of dominant directions is
usually due to lack of line segments. In such cases of too few
line segments, we skip 90 degree filtering and proceed to
histogram clustering.
t
|
i
SE
Im
E
Figure 5. Image segmentation based on road directions
3. The position of the line on the road
Each region from the quadtree has its own two dominant road
directions and, as mentioned above, those directions are parallel
with road and building edges. Let's imagine two virtual needles
that penetrate the two dimension edge image spaces and a
compare a measure for both needles. We define a free passage
to quantify this concept. Specifically, a needle which meets
many edges will have a small free passage measure, whereas a
needle which meets few or no edges will have a large free
passage measure. Figure 6 illustrate the “needle piercing"
process through an edge image. Because of the analogy with
needle, we call this process the “Acupuncture Method”.
Scan and count
the edge pixel
Pei n e LU a Ill —
Needle fe . CE D II += e E =
Needens 7 7 = = ell qM mE Cm REC
ERUIT
|] u a) PE
Figure 6. Penetrating needles on the edge image
Replacing the needles as line equations on the edge image
aligned with the dominant directions, and stepping exhaustively
across the edge image, we can compute a free passage measure
for each candidate line. We denote the two dominant directions
64 and 6,. The free passage measure for a fixed dominant
direction and a given p is generated by following steps. Before
implementing the steps, the range of p is defined as
Pmin = Min (1, NL:cos0)
Pmax = Max (NS"sin0, NL-cos0 + NS'sin0 )
Pmin S p S P max
