2. LINEAR FEATURE EXTRACTION
We designed a new template matching algorithm based on the
following considerations. In images at Im resolution, road
centerlines are appeared as curvilinear features and have
distinctive brightness patterns compared to their surroundings.
And hence, we could apply template matching along the road
centerlines. Also we assumed that although there are geometric
distortions we could model the geometric transformation
between one point and the other on a road centerline as
similarity transformation. Hence, if we draw a rectangular
window centered on a point of a road centerline, we can define
the corresponding window at another point of a road centerline
by translating and rotating the rectangle (see figure 1)
Template Window 5
91
Target Window
Figure 1. The template and target window for road detection
We can express the relationship between a template and a target
window along a road centerline as below
=X
template cos 0 az y sin 0 * 5, — ssm Yomi ( 1)
X target template
5 T
) x sin + y
3 z—xY T
4 target ““remplate
cos +s, +scosb,, (2)
template
where 8
template
is the road orientation at the template point and s
the shift distance along perpendicular to 9, ,, . Here, s, and
s, are set to indicate the distance in x and y direction,
respectively, between the template and initial guess. They
remain constant through iteration. Least squares correlation
matching assuming this similarity transformation can be
derived (Kim et al., 2004)
Our road centerline tracking algorithm works as follows. First,
a user provides an input point on a road centerline. This point
will be used as the center of a template window. It is important
for a user to select a point on a road centerline in order to track
valid road centerlines. Next, we estimate the orientation of the
road. We tried two methods for estimating the orientation of
road at a user's input point: automatic and manual. The
automatic method was to apply automatic line extraction
method to the image and then to calculate the orientation of the
line segment nearby the initial input point. The manual method
was to get another input point from a user and to calculate the
orientation of the line connecting the two input points. Valid
line segments were extracted and valid road orientations were
estimated in most cases. However, in order to ensure our
algorithm can work for all times, we need the manual
alternative.
Next, based on the user input point on a road centerline and its
orientation, a template and initial target windows are generated.
A template window is defined whose center is at the user input
point and whose orientation is aligned to the road orientation.
An initial target window is generated by shifting the template
window to the direction of road.
Next, least squares correlation. maiching is applied. The
position and orientation of target window is updated iteratively.
582
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
Once matching is completed the location of a new road
centerline and its orientation are achieved (see figure 2). Then
our algorithm checks whether there are more points to consider
or not. If so, a new target window is defined by shifting the
matched target window further to the orientation of matched
target window.
The position of initial guess
Initial Target Window
Template Window
Matched Target Window
Position and orientation updated
Figure 2. The definition of initial target window and matched
target window
The procedure of least squares correlation matching and the
creation of new target window repeat. A series of least squares
correlation matching generate successive points on a road
centerline and in this way tracking road centerline is achieved
through least squares correlation matching (see figure 10).
Due to the nature of template matching scheme, one complete
road is sometimes extracted as several road segments. To
overcome this limitation, we have developed user-friendly post
processing algorithm for connecting, deleting and editing road
segments.
User can connect two split segments as one. Template matching
sometimes splits one road segment into two or more segments.
These segments are connected by user's manual selection and
connected segments are saved as identical segment.
Occasionally, template matching exposes to matching fail
points. In this case, a user selects a fail point, and then deletes
them. A user can also edit a road segment by inserting and
shifting additional match points to the segment.
3. BUILDING EXTRACTION
We designed a new building extraction algorithm based on line
analysis and template matching. We assume that a user will
provide a starting position of our algorithm. A user must click
one point which lies inside of a building object to be extracted.
This is not a very sophisticated requirement. But this is indeed
very useful for eliminating many ambiguities and false alarms
associated with fully automated approaches.
Our algorithm works in three parts. The first part is the
extraction of lines from the subimage centred on the user-given
initial position (as explained in section 3.1). The second part is
the estimation of the position and orientation of building
boundaries from lines and the generation of building rectangles
(see section 3.2). The third part is the template matching
(section 3.3). The previously extracted building boundaries are
defined as a template and a least squares matching is applied to
extract buildings with similar shapes.
Interna
Me
3.1. Li
To ext
image.
the us
algorit
The fo
on a bi
3.2 Es
The «
subim
orient
indivi
the ini
The e:
time, °
the dii
numb:
the m.
long s
Vot
oni
slid
Once
orient
match
templ
value
betwe
build;
also |
desig
We Te
hence
After
orien
this a
orien
by sl
the s
side