Road extraction from images using template matching

• US 6,721,660 B2
• Filed: 08/19/2002
• Issued: 04/13/2004
• Est. Priority Date: 08/19/2002
• Status: Expired due to Fees

• Current Assignee: Korea Advanced Institute of Science and Technology
• Original Assignee: Korea Advanced Institute of Science and Technology
• Inventors: Kim, Taejung, Park, Seung-Ran
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): Gutierrez, Anthony
• Application Number:
  US10/223,897
• Publication Number:
  US 20040034473A1
• Time in Patent Office: 603 Days
• Field of Search: 702/5, 340/937
• US Class Current: 702/5
• CPC Class Codes: G06T 7/00 Image analysis
• CPC Class Codes: G06V 10/443 by matching or filtering

Abstract

A method of extracting a road from images photographed from an artificial satellite or aircraft, which includes a first step of calculating an orientation of an initial input coordinate after selection thereof, a second step of generating a template window which is inclined by the calculated orientation with respect to the initial input coordinate, a third step of generating an initial target window moved from the generated template window in a direction of the orientation of the input coordinate, a fourth step of calculating an origin point of the optimal target window and a new orientation thereof by performing template matching for the generated initial target window, a fifth step of generating a new initial target window moved from the calculated origin point in the a direction of the calculated new orientation and repeatedly performing the fourth step until all the images have been completely processed, and a sixth step of generating the road on a map by connecting the origin points obtained from the images with one another.

Claims

1. A method of extracting a road from an image photographed from an artificial satellite or aircraft, comprising:

a first step of calculating an orientation of an initial input coordinate after selecting a point on the road as the initial input coordinate;

a second step of generating a template window which is inclined by the calculated orientation with respect to the initial input coordinate;

a third step of generating an initial target window moved from the generated template window in a direction of the orientation of the initial input coordinate;

a fourth step of calculating an origin point of an optimal target window and a new orientation thereof by performing template matching for the generated initial target window;

a fifth step of generating a new initial target window moved from the calculated origin point in a direction of the calculated new orientation and repeatedly performing the fourth step for the generated new initial target window until the image has been completely processed; and

a sixth step of generating the road on a map by connecting the origin points obtained from the optimal target windows in the image with one another.

2. The method as claimed in claim 1 wherein the orientation calculation in the first step is accomplished by extracting line information within a predetermined region around the initial input coordinate and then calculating an orientation from the extracted line information.

3. The method as claimed in claim 1 wherein the orientation calculation in the first step is accomplished by calculating a slope of a line connecting two initial input coordinates selected by a user.

4. The method as claimed in claim 1 wherein the origin point of the target window and the orientation thereof in the fourth step are calculated in accordance with the following equation (5):

$\begin{array}{cc}\begin{array}{c}\mathrm{xtarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-y_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+s_1\\ \mathrm{ytarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+y_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+s_2\\ I=\text{\hspace{1em}<br><br>}<br><br>\mathrm{Ax}\\ I=\text{\hspace{1em}<br><br>}<br><br>\left\{f<br><br>\left(x_{\mathrm{template}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{,}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_{\mathrm{template}}\right)-g<br><br>\left(x_{\mathrm{target}},y_{\mathrm{target}}\right)\right\}\\ x^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{cccc}\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}& \mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_1& \mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_2& r_s\end{array}\right]\\ A^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{c}-\left({\mathrm{\delta <br><br>}}_x<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+{\mathrm{\delta <br><br>}}_y<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>x_{\mathrm{template}}+\left({\mathrm{\delta <br><br>}}_x<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-{\mathrm{\delta <br><br>}}_y<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>y_{\mathrm{template}}\\ {\mathrm{\delta <br><br>}}_x\\ {\mathrm{\delta <br><br>}}_y\\ 1\end{array}\right],\end{array}& \text{(5)}\end{array}$

where θ

is the orientation, (s₁,s₂) is a path along which the template window has been moved in the x- and y-axis directions, (x_template, y_template) is the origin point of the template window obtained based on the initial input coordinate, (x_{target, ytarget}) is the origin point of the target window which has been moved by a predetermined distance through the similarity transformation, δ

_x and δ

_y are rates of change in the brightness value at (x_target, y_target) in the x- and y-axis directions, a function ƒ

is a brightness function of the template window, a function g is a brightness function of the target window, and r_s is a difference between average brightness values of the template window and the target window.

5. The method as claimed in claim 1, wherein the origin point of the target window and the orientation thereof in the fourth step are calculated in accordance with the following equation (6):

$\begin{array}{cc}\begin{array}{c}\mathrm{xtarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-y_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\theta <br><br>}}_0\times <br><br>s_1\\ \mathrm{ytarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+y_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\theta <br><br>}}_0\times <br><br>s_1\\ I=\text{\hspace{1em}<br><br>}<br><br>\mathrm{Ax}\\ I=\text{\hspace{1em}<br><br>}<br><br>\left\{f<br><br>\left(x_{\mathrm{template}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{,}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_{\mathrm{template}}\right)-g<br><br>\left(\mathrm{xtarget},\mathrm{ytarget}\right)\right\}\\ x^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{ccc}\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}& \mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_1& r_s\end{array}\right]\\ A^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{c}-\left({\mathrm{\delta <br><br>}}_x<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+{\mathrm{\delta <br><br>}}_y<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>x_{\mathrm{template}}+\left({\mathrm{\delta <br><br>}}_x<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-{\mathrm{\delta <br><br>}}_y<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>y_{\mathrm{template}}\\ {\mathrm{\delta <br><br>}}_y\\ 1\end{array}\right],\end{array}& \text{(6)}\end{array}$

where θ

is the orientation of the calculated initial input coordinate, θ

₀ is the orientation of the initial target window, s₁ is a path along which the template window has been moved in the y-axis direction, (x_template, y_template) is the origin point of the template window obtained based on the initial input coordinate, (x_target, y_target) is the origin point of the target window which has been moved by a predetermined distance through the similarity transformation, δ

_y is a rate of change in the brightness value at (x_target, y_target) in the y-axis direction, a function ƒ

is a brightness function of the template window, a function g is a brightness function of the target window, and r_s is a difference between average brightness values of the template window and the target window.

6. A computer-readable recording medium in which a program is recorded, the program comprising instructions for causing a computer to implement extraction of a road from images photographed from an artificial satellite or aircraft, comprising:

a first step of calculating an orientation of an initial input coordinate after selection thereof;

a second step of generating a template window which is inclined by the calculated orientation with respect to the initial input coordinate;

a third step of generating an initial target window moved from the generated template window in a direction of the orientation of the input coordinate;

a fourth step of calculating an origin point of the optimal target window and a new orientation thereof by performing template matching for the generated initial target window;

a fifth step of generating a new initial target window moved from the calculated origin point in a direction of the calculated new orientation and repeatedly performing the fourth step until all the images have been completely processed; and

a sixth step of generating the road on a map by connecting the origin points obtained from the images with one another.

7. A method of extracting a road from images photographed from an artificial satellite or aircraft, comprising:

a first step of calculating an orientation of an initial input coordinate after selection thereof;

a second step of generating a template window which is inclined by the calculated orientation with respect to the initial input coordinate;

a third step of generating an initial target window moved from the generated template window in a direction of the orientation of the input coordinate;

a fourth step of calculating an origin point of the optimal target window and a new orientation thereof by performing template matching for the generated initial target window, the origin point of the target window and the orientation thereof calculated in accordance with the following equation;

$\begin{array}{c}\mathrm{xtarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-y_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+s_1\\ \mathrm{ytarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+y_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+s_1\\ I=\text{\hspace{1em}<br><br>}<br><br>\mathrm{Ax}\\ I=\text{\hspace{1em}<br><br>}<br><br>\left\{f<br><br>\left(x_{\mathrm{template}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{,}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_{\mathrm{template}}\right)-g<br><br>\left(\mathrm{xtarget},\mathrm{ytarget}\right)\right\}\\ x^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{cccc}\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}& \mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_1& \mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_2& r_s\end{array}\right]\\ A^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{c}-\left({\mathrm{\delta <br><br>}}_x<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+{\mathrm{\delta <br><br>}}_y<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>x_{\mathrm{template}}+\left({\mathrm{\delta <br><br>}}_x<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-{\mathrm{\delta <br><br>}}_y<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>y_{\mathrm{template}}\\ {\mathrm{\delta <br><br>}}_x\\ {\mathrm{\delta <br><br>}}_y\\ 1\end{array}\right],\end{array}$

where θ

is the orientation, (s₁,s₂) is a path along which the template window has been moved in the x- and y-axis directions, (x_template, y_template) is the origin point of the template window obtained based on the initial input coordinate, (x_target, y_target) is the origin point of the target window which has been moved by a predetermined distance through the similarity transformation, δ

_x and δ

_y are rates of change in the brightness value at (x_target, y_target) in the x- and y-axis directions, a function ƒ

is a brightness function of the template window, a function g is a brightness function of the target window, and r_s is a difference between average brightness values of the template window and the target window;

a fifth step of generating a new initial target window moved from the calculated origin point in a direction of the calculated new orientation and repeatedly performing the fourth step until all the images have been completely processed; and

a sixth step of generating the road on a map by connecting the origin points obtained from the images with one another.

8. A method of extracting a road from images photographed from an artificial satellite or aircraft, comprising:

a first step of calculating an orientation of an initial input coordinate after selection thereof;

a second step of generating a template window which is inclined by the calculated orientation with respect to the initial input coordinate;

a third step of generating an initial target window moved from the generated template window in a direction of the orientation of the input coordinate;

a fourth step of calculating an origin point of the optimal target window and a new orientation thereof by performing template matching for the generated initial target window, the origin point of the target window and the orientation thereof calculated in accordance with the following equation;

$\begin{array}{c}\mathrm{xtarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-y_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\theta <br><br>}}_0\times <br><br>s_1\\ \mathrm{ytarget}=\text{\hspace{1em}<br><br>}<br><br>x_{\mathrm{template}}<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+y_{\mathrm{template}}<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\theta <br><br>}}_0\times <br><br>s_1\\ I=\text{\hspace{1em}<br><br>}<br><br>\mathrm{Ax}\\ I=\text{\hspace{1em}<br><br>}<br><br>\left\{f<br><br>\left(x_{\mathrm{template}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{,}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_{\mathrm{template}}\right)-g<br><br>\left(\mathrm{xtarget},\mathrm{ytarget}\right)\right\}\\ x^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{ccc}\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}& \mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>s_1& r_s\end{array}\right]\\ A^T=\text{\hspace{1em}<br><br>}<br><br>\left[\begin{array}{c}-\left({\mathrm{\delta <br><br>}}_x<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}+{\mathrm{\delta <br><br>}}_y<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>x_{\mathrm{template}}+\left({\mathrm{\delta <br><br>}}_x<br><br>\cos <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}-{\mathrm{\delta <br><br>}}_y<br><br>\sin <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\theta <br><br>}\right)<br><br>y_{\mathrm{template}}\\ {\mathrm{\delta <br><br>}}_y\\ 1\end{array}\right],\end{array}$

where θ

is the orientation of the calculated initial input coordinate, θ

₀ is the orientation of the initial target window, s₁ is a path along which the template window has been moved in the y-axis direction, (x_template, y_template) is the origin point of the template window obtained based on the initial input coordinate, (x_target, y_target) is the origin point of the target window which has been moved by a predetermined distance through the similarity transformation, δ

_y is a rate of change in the brightness value at (x_target, y_target) in the y-axis direction, a function f is a brightness function of the template window, a function g is a brightness function of the target window, and r_s is a difference between average brightness values of the template window and the target window;

a fifth step of generating a new initial target window moved from the calculated origin point in a direction of the calculated new orientation and repeatedly performing the fourth step until all the images have been completely processed; and

a sixth step of generating the road on a map by connecting the origin points obtained from the images with one another.