Method and apparatus for automatically extracting geospatial features from multispectral imagery suitable for fast and robust extraction of landmarks

• US 7,400,770 B2
• Filed: 11/08/2003
• Issued: 07/15/2008
• Est. Priority Date: 11/06/2002
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Brokish, Jeffrey, Keaton, Patricia Ann
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): Liew; Alex
• Application Number:
  US10/704,222
• Publication Number:
  US 20050100220A1
• Time in Patent Office: 1,711 Days
• Field of Search: None
• US Class Current: 382/191
• CPC Class Codes: G06T 2207/10036 Multispectral image; Hyperspectral image
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/20161 Level set
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

A system for automatically extracting geospatial features from multi-spectral imagery, suitable for fast and robust extraction of landmarks, is presented. The system comprises a computer system including a processor, a memory coupled with the processor, an input coupled with the processor for receiving imagery and user-provided geospatial features, and an output coupled with the processor for outputting the extracted landmarks. The computer system includes a region-growing system, an appending disjointed regions system, and an automatic reseeding system, which are configured to accurately and efficiently extract all regions within the input image that closely resemble the desired geospatial feature. The region-growing system is based on a level set technique, which allows for the fast and accurate extraction of a region evolved from a single user-provided seed point. By automatically reseeding the system when a growing region stops evolving, the system extracts all the desirable regions with minimum user intervention.

Claims

1. A method for automatically extracting geospatial features from multi-spectral imagery suitable for fast and robust extraction of landmarks evolved from a single seed point, the method comprising acts of:

receiving an image of an area of land;

receiving a seed point, wherein said seed point represents a part of a desired geospatial feature of the area of land;

iteratively growing a region about the seed point based on a level set technique, with the region representative of the desired geospatial feature, and wherein the growing of the region results in a grown region having edges and a boundary;

appending a selected grown region to a network of grown geospatial features;

automatically reseeding a point on the image, wherein said reseeding point represents a potentially disjointed region of the desired geospatial feature of the area of land;

iteratively performing the acts of growing a region about the seed point, appending, and reseeding, until either exhausting all likely candidates of potentially disjointed regions of the desired geospatial feature, or until reaching the boundaries of the image of an area of land; and

outputting the network of grown geospatial features;

whereby the outputs include the network of grown geospatial features, and any geometrical or spectral features extracted from the network of grown geospatial features.

2. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein in the act of receiving an image of an area of land, there are two types of input imagery consisting of multi-spectral input data, and panchromatic input data.

3. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 2, where the multi-spectral input data and the panchromatic input data are used to create a pan-sharpened image, and wherein the pan-sharpened image preserves the details provided by the panchromatic data, while allowing for the exploitation of color information provided by the four-band color multi-spectral data.

4. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 3, wherein in the act of receiving a seed point, the seed point is provided by a person using the method for automatically extracting geospatial features from multispectral imagery, where said person using the method is called “

a user” and

said received seed point is labeled “

user-provided seed point”

.

5. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 4, wherein, in the act of iteratively growing a region about the seed point, the region is grown using a level set technique, where the level set technique uses a speed function to control and stop the evolution of a growing region, and wherein the growing region has spectral uniformity and consistent texture.

6. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 5, wherein, in the act of iteratively growing a region about the seed point based on a level set technique, the level set technique speed function is defined in terms of features that include at least one of:

spectral uniformity;

consistent texture;

contrast with surrounding environment;

Transformed Vegetative Index mask (TVI mask); and

Water Index mask (WI mask).

7. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 6, wherein the TVI mask is a measurement of light reflectance, with specific values for the TVI mask in regions with vegetation, and other specific values for the TVI mask in man made regions, and where the TVI mask is formed by combining near infrared and red color band information.

8. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 7, wherein the WI mask is a measurement of light reflectance, with specific values for the WI mask in water regions, and other specific values for the WI mask in man made regions, and where the WI mask is formed by combining near infrared and green color band information.

9. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 8, further comprising an act of iteratively smoothing the edges of the grown region based on a level set technique in order to eliminate boundary irregularities in a boundary of the grown region, wherein the level set technique uses a speed function to control and stop the evolution of a growing region around the boundary irregularities of the grown region, and wherein the smoothing of the grown region results in a smoothed grown region.

10. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 9, wherein, in the act of iteratively smoothing the edges of the grown region, the speed function for the level set technique is defined in terms of a curvature measurement of the boundary of the grown region, wherein the boundary of the grown region has global properties that define an overall shape of the grown region, and wherein a finite number of iterations are performed in order to smooth out local irregularities in the boundary of the grown region, without changing the global properties of the boundary of the grown region.

11. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 10, further comprising an act of filtering the smoothed grown region with respect to geometrical characteristics of the desired geospatial feature, wherein the filtering of the smoothed grown region results in a filtered grown region, and wherein the filtered grown region has connectivity properties.

12. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 11, wherein the filtered grown region has a center line, and where the method further comprises an act of computing the center line of the filtered grown region, wherein the center line preserves the connectivity properties of the filtered grown region.

13. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 12, wherein, in the act of appending a selected grown region to a network of grown geospatial features, the selected grown region comprises the filtered grown region.

14. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 13, wherein when the filtered grown region reaches a “

dead end,”

the act of reseeding automatically searches an area about the “

dead end”

to find a new point in the image with similar characteristics to the user-provided seed point, in order to continue the growing of the region representative of the desired geospatial feature.

15. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 14, wherein the centerline of the filtered grown region has an orientation, and wherein the search region about the “

dead end”

consists of a “

cone shaped”

search region with an orientation determined by the orientation of the centerline of the filtered grown region, as the centerline approaches the “

dead end.”

16. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 15, wherein, in the act of reseeding, the characteristics used to compare the reseeding point with the user-provided seed point comprise:

textural properties of the image at the reseeding point and textural properties of the image at the user-provided seed point; and

distance from the reseeding point to an edge of a region grown out of the reseeding point, and distance from the user-provided seed point to an edge of the filtered grown region.

17. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 16, further comprising an act of computing geometrical features of the network of grown geospatial features, wherein the network of grown geospatial features has branches, and wherein the geometrical features of the network include at least one of:

centerlines, areas, lengths, widths, shapes, and roundness values of all the branches in the network.

18. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 17, wherein in the act of filtering the smoothed grown region the desired geospatial features are roads, where the width and length of the smoothed grown regions are used as criteria for accepting or rejecting the smoothed grown regions as real roads or false roads, and wherein the filtered grown regions contain only real roads.

19. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 18, further comprising the act of performing junction analysis, wherein filtered grown regions with centerlines that meet at appropriate angles within road intersections are accepted as real roads, and where filtered grown regions with centerlines that do not meet at appropriate angles within road intersections are considered false roads.

20. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 19, further comprising an act of checking junctions of real roads for shape regularity, wherein intersecting real roads having similar road shape properties are automatically linked.

21. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 20, wherein, in the act of growing a region about the seed point, the speed function for the level set technique, F(x,y), is defined by

$F$

( x , y ) = ( w ⁢

⁢

ⅇ

- 1 2 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) ⁢

∑

- 1 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) T + ( 1 - w ) ⁢

ⅇ

- 

H ⁡

( x , y ) - H 0 

) * 1 1 + 

∇

I ⁡

( x , y ) 

p * ⅇ

- 

TVI ⁡

( x , y ) - 0.8 

* ⅇ

- 

WI ⁡

( x , y ) - 0.9 

where;

the first term of the speed function located to the right of the equal sign denotes a spectral uniformity of the grown region;

the second term of the speed function located to the right of the equal sign denotes a consistent texture of the grown region;

the third term of the speed function located to the right of the equal sign denotes contrast of the grown region with a surrounding environment;

the fourth term of the speed function located to the right of the equal sign hinders growth of the grown region into vegetation regions;

the last term of the speed function located to the right of the equal sign hinders growth of the grown region into water regions;

ĉ

(x,y) denotes spectral values of the image at (x,y) location;

μ

₀ represents a vector containing spectral intensities of the image at the user-provided seed point location;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

parameter w determines relative weightings between the spectral uniformity and the entropy terms representing the texture of the grown region;

∇

I term denotes an image gradient which extracts strong edges between the boundary of the grown region and other regions;

Σ

denotes a diagonal covariance matrix which is a function of noise present in the image, where Σ

allows for tuning the sensitivity of the spectral uniformity term; and

parameter p is a function of contrast present in the image, where p allows for tuning the sensitivity of the contrast term.

22. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 21, wherein, in the act of iteratively smoothing the edges of the grown region, the grown region has a curvature value associated with its boundary, and wherein the curvature of the boundary of the grown region, κ

, and the speed function, F(x,y), are defined by

$\mathrm{\kappa <br><br>}=\frac{{\mathrm{\Phi <br><br>}}_{\mathrm{xx}}<br><br>{\mathrm{\Phi <br><br>}}_y^2-2<br><br>{\mathrm{\Phi <br><br>}}_x<br><br>{\mathrm{\Phi <br><br>}}_y<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{xy}}+{\mathrm{\Phi <br><br>}}_{\mathrm{yy}}<br><br>{\mathrm{\Phi <br><br>}}_x^2}{{\left({\mathrm{\Phi <br><br>}}_x^2+{\mathrm{\Phi <br><br>}}_y^2\right)}^{\frac{3}{2}}}$
F(x,y)=−

min(κ

(x,y),0)

where

Φ

denotes a level set function defined by Φ

(x,y)=±

d(x,y), where d(x,y) denotes smallest distance from a point (x,y) within the image to the boundary of the grown region, and the +/−

signs are chosen such that points inside the boundary have a negative distance sign, and such that points outside the boundary have a positive distance sign;

Φ

_x denotes the partial derivative of Φ

with respect to x coordinate;

Φ

_y denotes the partial derivative of Φ

with respect to y coordinate;

Φ

_xy denotes the partial derivatives of Φ

with respect to x and y coordinates;

Φ

_xx denotes the partial derivatives of Φ

with respect to x and x coordinates; and

Φ

_yy denotes the partial derivatives of Φ

with respect to y and y coordinates.

23. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 22, wherein, in the act of automatically reseeding a point on the image, the reseeding point is determined as a maximum likelihood point that lies within the “

cone shaped”

search region about the “

dead end”

that most closely satisfy

$\mathrm{SeedLH}<br><br>\left(x,y\right)=\mathrm{Exp}<br><br>\left\{-<br><br>\frac{{\left(\frac{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)+{\mathrm{\sigma <br><br>}}_0}{2}+{\left(\frac{H<br><br>\left(x,y\right)-H_0}{2}\right)}^2\right)}^2}{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)*{\mathrm{\sigma <br><br>}}_0}-1<br><br>\right\}*\mathrm{Exp}<br><br>\left\{-<br><br>\mathrm{e<br><br>}<br><br><br><br>\mathrm{dt}<br><br>\left(x,y\right)-d_0<br><br>\right\}$

where

SeedLH(x,y) denotes likelihood of a point (x,y) of being an appropriate reseeding point representing a part of the desired geospatial feature of the area of land;

σ

(x,y) denotes variance associated with the image at point (x,y);

σ

₀ denotes variance associated with the user-provided seed point;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

edt(x,y) (Euclidean Distance Transform) denotes a Euclidean distance between a pixel point (x,y) and a nearest edge of a region grown out of the pixel point (x,y); and

d₀ denotes estimated width of the previously filtered grown region which terminated on the “

dead end”

generating the current “

cone shaped”

search region.

24. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein in the act of receiving an image of an area of land, there are two types of input imagery consisting of multi-spectral input data, and panchromatic input data, and where the multi-spectral input data and the panchromatic input data are used to create a pan-sharpened image, wherein the pan-sharpened image preserves the details provided by the panchromatic data, while allowing for the exploitation of color information provided by the four-band color multi-spectral data.

25. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein in the act of receiving a seed point, the seed point is provided by either:

a person using the method for automatically extracting geospatial features from multispectral imagery, where said person using the method is called “

a user” and

said received seed point is labeled “

user-provided seed point”

;

or

an act generating automatically a likely seed point representing a part of the desired geospatial feature of the area of land.

26. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein, in the act of iteratively growing a region about a seed point, the region is grown using a level set technique, where the level set technique uses a speed function to control and stop the evolution of a growing region, and wherein the speed function is defined in terms of features that include at least one of:

spectral uniformity;

consistent texture;

contrast with surrounding environment;

Transformed Vegetative Index mask (TVI mask); and

Water Index mask (WI mask).

27. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein, in the act of iteratively growing a region about a seed point, the region is grown using a level set technique using a Transformed Vegetative Index mask (TVI mask) and Water Index mask (WI mask), where the TVI mask is formed by combining near infrared and red color band information, with specific values for the TVI mask in regions with vegetation, and other specific values for the TVI mask in man made regions, and where the WI mask is formed by combining near infrared and green color band information, with specific values for the WI mask in water regions, and other specific values for the WI mask in man made regions.

28. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, further comprising an act of iteratively smoothing the edges of the grown region in order to eliminate boundary irregularities in a boundary of the grown region, wherein the act of smoothing is based on a level set technique using a speed function to control and stop the evolution of a growing region around the boundary irregularities of the grown region, and wherein the smoothing of the grown region results in a smoothed grown region.

29. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 28, wherein, in the act of iteratively smoothing the edges of the grown region, the speed function for the level set technique is defined in terms of a curvature measurement of the boundary of the grown region, wherein the boundary of the grown region has global properties that define an overall shape of the grown region, and wherein a finite number of iterations are performed in order to smooth out local irregularities in the boundary of the grown region, without changing the global properties of the boundary of the grown region.

30. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 29, wherein, in the act of iteratively smoothing the edges of the grown region, the grown region has a curvature value associated with its boundary, and wherein the curvature of the boundary of the grown region, κ

, and the speed function, F(x,y), are defined by

$\mathrm{\kappa <br><br>}=\frac{{\mathrm{\Phi <br><br>}}_{\mathrm{xx}}<br><br>{\mathrm{\Phi <br><br>}}_y^2-2<br><br>{\mathrm{\Phi <br><br>}}_x<br><br>{\mathrm{\Phi <br><br>}}_y<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{xy}}+{\mathrm{\Phi <br><br>}}_{\mathrm{yy}}<br><br>{\mathrm{\Phi <br><br>}}_x^2}{{\left({\mathrm{\Phi <br><br>}}_x^2+{\mathrm{\Phi <br><br>}}_y^2\right)}^{\frac{3}{2}}}$
F(x,y)=−

min(κ

(x,y),0)

where

Φ

denotes a level set function defined by Φ

(x,y)=±

d(x,y), where d(x,y) denotes smallest distance from a point (x,y) within the image to the boundary of the grown region, and the +/−

signs are chosen such that points inside the boundary have a negative distance sign, and such that points outside the boundary have a positive distance sign;

Φ

_x denotes the partial derivative of Φ

with respect to x coordinate;

Φ

_y denotes the partial derivative of Φ

with respect to y coordinate;

Φ

_xy denotes the partial derivatives of Φ

with respect to x and y coordinates;

Φ

_xx denotes the partial derivatives of Φ

with respect to x and x coordinates; and

Φ

_yy denotes the partial derivatives of Φ

with respect to y and y coordinates.

31. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, further comprising an act of filtering the grown region with respect to geometrical characteristics of the desired geospatial feature, wherein the filtering of the grown region results in a filtered grown region, and wherein the filtered grown region has connectivity properties and a center line, where the center line preserves the connectivity properties of the filtered grown region.

32. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 31, wherein, in the act of appending a selected grown region to a network of grown geospatial features, the selected grown region comprises the filtered grown region.

33. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 31, wherein in the act of filtering the grown region the desired geospatial features are roads, where the width and length of the grown regions are used as criteria for accepting or rejecting the grown regions as real roads or false roads, and wherein the filtered grown regions contain only real roads.

34. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 33, further comprising the acts of:

performing junction analysis, wherein filtered grown regions with centerlines that meet at appropriate angles within road intersections are accepted as real roads, and where filtered grown regions with centerlines that do not meet at appropriate angles within road intersections are considered false roads; and

checking junctions of real roads for shape regularity, wherein intersecting real roads having similar road shape properties are automatically linked and appended to a network of grown roads.

35. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein, in the act of automatically reseeding a point on the image, the selected grown region has a center line, with the center line having an orientation, and where the method further comprises the acts of:

computing the center line of the selected grown region; and

when the selected grown region reaches a “

dead end,”

searching an area about the “

dead end”

to find a new point in the image with similar characteristics to the initial seed point, in order to continue the growing of the region representative of the desired geospatial feature, and wherein the search region about the “

dead end”

consists of a “

cone shaped”

search region with an orientation determined by the orientation of the centerline of the selected grown region, as the centerline approaches the “

dead end.”

36. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein, in the act of reseeding, the characteristics used to compare the reseeding point with the initial seed point comprise:

textural properties of the image at the reseeding point and textural properties of the image at the initial seed point; and

distance from the reseeding point to an edge of a region grown out of the reseeding point, and distance from the initial seed point to an edge of the grown region.

37. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, further comprising an act of computing geometrical features of the network of grown geospatial features, wherein the network of grown geospatial features has branches, and wherein the geometrical features of the network include at least one of:

centerlines, areas, lengths, widths, shapes, and roundness values of all the branches in the network.

38. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein, in the act of growing a region about the seed point, the region is grown using a level set technique that utilizes a speed function F(x,y) defined by

$F$

( x , y ) = ( w ⁢

⁢

ⅇ

- 1 2 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) ⁢

∑

- 1 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) T + ( 1 - w ) ⁢

ⅇ

- 

H ⁡

( x , y ) - H 0 

) * 1 1 + 

∇

I ⁡

( x , y ) 

p * ⅇ

- 

TVI ⁡

( x , y ) - 0.8 

* ⅇ

- 

WI ⁡

( x , y ) - 0.9 

where;

the first term of the speed function located to the right of the equal sign denotes a spectral uniformity of the grown region;

the second term of the speed function located to the right of the equal sign denotes a consistent texture of the grown region;

the third term of the speed function located to the right of the equal sign denotes contrast of the grown region with a surrounding environment;

the fourth term of the speed function located to the right of the equal sign hinders growth of the grown region into vegetation regions;

the last term of the speed function located to the right of the equal sign hinders growth of the grown region into water regions;

ĉ

(x,y) denotes spectral values of the image at (x,y) location;

μ

₀ represents a vector containing spectral intensities of the image at the user-provided seed point location;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

parameter w determines relative weightings between the spectral uniformity and the entropy terms representing the texture of the grown region;

∇

I term denotes an image gradient which extracts strong edges between the boundary of the grown region and other regions;

Σ

denotes a diagonal covariance matrix which is a function of noise present in the image, where Σ

allows for tuning the sensitivity of the spectral uniformity term; and

parameter p is a function of contrast present in the image, where p allows for tuning the sensitivity of the contrast term.

39. A method for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 1, wherein, in the act of automatically reseeding a point on the image, when a selected grown region reaches a “

dead end,”

the reseeding point is determined as a maximum likelihood point that lies within a “

cone shaped”

search region about the “

dead end”

that most closely satisfy

$\begin{array}{c}\mathrm{SeedLH}<br><br>\left(x,y\right)=<br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\frac{{\left(\frac{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)+{\mathrm{\sigma <br><br>}}_0}{2}+{\left(\frac{H<br><br>\left(x,y\right)-H_0}{2}\right)}^2\right)}^2}{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)*{\mathrm{\sigma <br><br>}}_0}-1<br><br>\right\}*\\ <br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\mathrm{e<br><br>}<br><br><br><br>\mathrm{dt}<br><br>\left(x,y\right)-d_0<br><br>\right\}\end{array}$

where

SeedLH(x,y) denotes likelihood of a point (x,y) of being an appropriate reseeding point representing a part of the desired geospatial feature of the area of land;

σ

(x,y) denotes variance associated with the image at point (x,y);

σ

₀ denotes variance associated with the initial seed point;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the initial seed point location;

edt(x,y) (Euclidean Distance Transform) denotes a Euclidean distance between a pixel point (x,y) and a nearest edge of a region grown out of the pixel point (x,y); and

d₀ denotes estimated width of the previously selected grown region which terminated on the “

dead end”

generating the current “

cone shaped”

search region.

40. A method for automatically extracting geospatial features from multi-spectral imagery suitable for fast and robust extraction of landmarks evolved from a single seed point, the method comprising acts of:

receiving an image of an area of land;

generating automatically likely seed points representing a part of a desired geospatial feature of the area of land;

iteratively growing a region about the seed point based on a level set technique, with the region representative of the desired geospatial feature, and wherein the growing of the region results in a grown region having edges and a boundary;

appending a selected grown region to a network of grown geospatial features;

automatically reseeding a point on the image, wherein said reseeding point represents a potentially disjointed region of the desired geospatial feature of the area of land;

iteratively performing the acts of growing a region about the seed point, appending, and reseeding, until either exhausting all likely candidates of potentially disjointed regions of the desired geospatial feature, or until reaching the boundaries of the image of an area of land; and

outputting the grown network representative of the desired geospatial feature;

whereby the outputs include the network of the grown geospatial feature, and any geometrical or spectral features extracted from the network of the grown geospatial feature.

41. A system for automatically extracting geospatial features from multi-spectral imagery suitable for fast and robust extraction of landmarks evolved from a single seed point, the system comprising:

a computer system including a processor, a memory coupled with the processor, an input coupled with the processor for receiving an image of an area of land and a seed point representing a part of a desired geospatial feature of the area of land, the computer system further comprising means, residing in its processor and memory for;

iteratively growing a region about the seed point based on a level set technique, with the region representative of the desired geospatial feature, and wherein the growing of the region results in a grown region having edges and a boundary;

appending a selected grown region to a network of grown geospatial features;

automatically reseeding a point on the image, wherein said reseeding point represents a potentially disjointed region of the desired geospatial feature of the area of land;

iteratively performing the means for growing a region about the seed point, the means for appending, and the means for reseeding, until either exhausting all likely candidates of potentially disjointed regions of the desired geospatial feature, or until reaching the boundaries of the image of an area of land; and

outputting the network of grown geospatial features;

whereby the outputs include the network of grown geospatial features, and any geometrical or spectral features extracted from the network of grown geospatial features.

42. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein in the means for receiving an image of an area of land, there are two types of input imagery consisting of multi-spectral input data, and panchromatic input data.

43. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 42, where the multi-spectral input data and the panchromatic input data are used to create a pan-sharpened image, and wherein the pan-sharpened image preserves the details provided by the panchromatic data, while allowing for the exploitation of color information provided by the four-band color multi-spectral data.

44. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 43, wherein in the means for receiving a seed point, the seed point is provided by a person using the system for automatically extracting geospatial features from multispectral imagery, where said person using the system is called “

a user” and

said received seed point is labeled “

user-provided seed point”

.

45. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 44, wherein, in the means for iteratively growing a region about the seed point, the region is grown using a level set technique, where the level set technique uses a speed function to control and stop the evolution of a growing region, and wherein the growing region has spectral uniformity and consistent texture.

46. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 45, wherein, in the means for iteratively growing a region about the seed point based on a level set technique, the level set technique speed function is defined in terms of features that include at least one of:

spectral uniformity;

consistent texture;

contrast with surrounding environment;

Transformed Vegetative Index mask (TVI mask); and

Water Index mask (WI mask).

47. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 46, wherein the TVI mask is a measurement of light reflectance, with specific values for the TVI mask in regions with vegetation, and other specific values for the TVI mask in man made regions, and where the TVI mask is formed by combining near infrared and red color band information.

48. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 47, wherein the WI mask is a measurement of light reflectance, with specific values for the WI mask in water regions, and other specific values for the WI mask in man made regions, and where the WI mask is formed by combining near infrared and green color band information.

49. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 48, further comprising a means for iteratively smoothing the edges of the grown region based on a level set technique in order to eliminate boundary irregularities in a boundary of the grown region, wherein the level set technique uses a speed function to control and stop the evolution of a growing region around the boundary irregularities of the grown region, and wherein the smoothing of the grown region results in a smoothed grown region.

50. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 49, wherein, in the means for iteratively smoothing the edges of the grown region, the speed function for the level set technique is defined in terms of a curvature measurement of the boundary of the grown region, wherein the boundary of the grown region has global properties that define an overall shape of the grown region, and wherein a finite number of iterations are performed in order to smooth out local irregularities in the boundary of the grown region, without changing the global properties of the boundary of the grown region.

51. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 50, further comprising a means for filtering the smoothed grown region with respect to geometrical characteristics of the desired geospatial feature, wherein the filtering of the smoothed grown region results in a filtered grown region, and wherein the filtered grown region has connectivity properties.

52. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 51, wherein the filtered grown region has a center line, and where the system further comprises a means for computing the center line of the filtered grown region, wherein the center line preserves the connectivity properties of the filtered grown region.

53. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 52, wherein, in the means for appending a selected grown region to a network of grown geospatial features, the selected grown region comprises the filtered grown region.

54. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 53, wherein when the filtered grown region reaches a “

dead end,”

the means for reseeding automatically searches an area about the “

dead end”

to find a new point in the image with similar characteristics to the user-provided seed point, in order to continue the growing of the region representative of the desired geospatial feature.

55. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 54, wherein the centerline of the filtered grown region has an orientation, and wherein the search region about the “

dead end”

consists of a “

cone shaped”

search region with an orientation determined by the orientation of the centerline of the filtered grown region, as the centerline approaches the “

dead end.”

56. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 55, wherein, in the means for reseeding, the characteristics used to compare the reseeding point with the user-provided seed point comprise:

textural properties of the image at the reseeding point and textural properties of the image at the user-provided seed point; and

distance from the reseeding point to an edge of a region grown out of the reseeding point, and distance from the user-provided seed point to an edge of the filtered grown region.

57. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 56, further comprising a means for computing geometrical features of the network of grown geospatial features, wherein the network of grown geospatial features has branches, and wherein the geometrical features of the network include at least one of:

centerlines, areas, lengths, widths, shapes, and roundness values of all the branches in the network.

58. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 57, wherein in the means for filtering the smoothed grown region the desired geospatial features are roads, where the width and length of the smoothed grown regions are used as criteria for accepting or rejecting the smoothed grown regions as real roads or false roads, and wherein the filtered grown regions contain only real roads.

59. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 58, further comprising the means for performing junction analysis, wherein filtered grown regions with centerlines that meet at appropriate angles within road intersections are accepted as real roads, and where filtered grown regions with centerlines that do not meet at appropriate angles within road intersections are considered false roads.

60. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 59, further comprising a means for checking junctions of real roads for shape regularity, wherein intersecting real roads having similar road shape properties are automatically linked.

61. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 60, wherein, in the means for growing a region about the seed point, the speed function for the level set technique, F(x,y), is defined by

$\begin{array}{c}F\end{array}$

( x , y ) = ⁢

( w ⁢

⁢

ⅇ

- 1 2 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) ⁢

Σ

- 1 ⁡

( c ^ ⁡

( x , y ) - μ

_ 0 ) T + ( 1 - w ) ⁢

ⅇ

- 

H ⁡

( x , y ) - H 0 

) * ⁢

1 1 + 

∇

I ⁡

( x , y ) 

p * ⅇ

- 

TV1 ⁡

( x , y ) - 0.8 

* ⅇ

- 

WI ⁡

( x , y ) - 0.9 

where;

the first term of the speed function located to the right of the equal sign denotes a spectral uniformity of the grown region;

the second term of the speed function located to the right of the equal sign denotes a consistent texture of the grown region;

the third term of the speed function located to the right of the equal sign denotes contrast of the grown region with a surrounding environment;

the fourth term of the speed function located to the right of the equal sign hinders growth of the grown region into vegetation regions;

the last term of the speed function located to the right of the equal sign hinders growth of the grown region into water regions;

ĉ

(x,y) denotes spectral values of the image at (x,y) location;

μ

₀ represents a vector containing spectral intensities of the image at the user-provided seed point location;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

parameter w determines relative weightings between the spectral uniformity and the entropy terms representing the texture of the grown region;

∇

I term denotes an image gradient which extracts strong edges between the boundary of the grown region and other regions;

Σ

denotes a diagonal covariance matrix which is a function of noise present in the image, where Σ

allows for tuning the sensitivity of the spectral uniformity term; and

parameter p is a function of contrast present in the image, where p allows for tuning the sensitivity of the contrast term.

62. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 61, wherein, in the means for iteratively smoothing the edges of the grown region, the grown region has a curvature value associated with its boundary, and wherein the curvature of the boundary of the grown region, κ

, and the speed function, F(x,y), are defined by

$\mathrm{\kappa <br><br>}=\frac{{\mathrm{\Phi <br><br>}}_{\mathrm{xx}}<br><br>{\mathrm{\Phi <br><br>}}_y^2-2<br><br>{\mathrm{\Phi <br><br>}}_x<br><br>{\mathrm{\Phi <br><br>}}_y<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{xy}}+{\mathrm{\Phi <br><br>}}_{\mathrm{yy}}<br><br>{\mathrm{\Phi <br><br>}}_x^2}{{\left({\mathrm{\Phi <br><br>}}_x^2+{\mathrm{\Phi <br><br>}}_y^2\right)}^{3/2}}$
F(x,y)=−

min(κ

(x,y),0)

where

Φ

denotes a level set function defined by Φ

(x,y)=±

d(x,y), where d(x,y) denotes smallest distance from a point (x,y) within the image to the boundary of the grown region, and the +/−

signs are chosen such that points inside the boundary have a negative distance sign, and such that points outside the boundary have a positive distance sign;

Φ

_x denotes the partial derivative of Φ

with respect to x coordinate;

Φ

_y denotes the partial derivative of Φ

with respect to y coordinate;

Φ

_xy denotes the partial derivatives of Φ

with respect to x and y coordinates;

Φ

_xx denotes the partial derivatives of Φ

with respect to x and x coordinates; and

Φ

_yy denotes the partial derivatives of Φ

with respect to y and y coordinates.

63. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 62, wherein, in the means for automatically reseeding a point on the image, the reseeding point is determined as a maximum likelihood point that lies within the “

cone shaped”

search region about the “

dead end”

that most closely satisfy

$\begin{array}{c}\mathrm{SeedLH}<br><br>\left(x,y\right)=<br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\frac{{\left(\frac{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)+{\mathrm{\sigma <br><br>}}_0}{2}+{\left(\frac{H<br><br>\left(x,y\right)-H_0}{2}\right)}^2\right)}^2}{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)*{\mathrm{\sigma <br><br>}}_0}-1<br><br>\right\}*\\ <br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\mathrm{e<br><br>}<br><br><br><br>\mathrm{dt}<br><br>\left(x,y\right)-d_0<br><br>\right\}\end{array}$

where

SeedLH(x,y) denotes likelihood of a point (x,y) of being an appropriate reseeding point representing a part of the desired geospatial feature of the area of land;

σ

(x,y) denotes variance associated with the image at point (x,y);

σ

₀ denotes variance associated with the user-provided seed point;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

edt(x,y) (Euclidean Distance Transform) denotes a Euclidean distance between a pixel point (x,y) and a nearest edge of a region grown out of the pixel point (x,y); and

d₀ denotes estimated width of the previously filtered grown region which terminated on the “

dead end”

generating the current “

cone shaped”

search region.

64. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein in the means for receiving an image of an area of land, there are two types of input imagery consisting of multi-spectral input data, and panchromatic input data, and where the multi-spectral input data and the panchromatic input data are used to create a pan-sharpened image, wherein the pan-sharpened image preserves the details provided by the panchromatic data, while allowing for the exploitation of color information provided by the four-band color multi-spectral data.

65. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein in the means for receiving a seed point, the seed point is provided by either:

a person using the system for automatically extracting geospatial features from multispectral imagery, where said person using the system is called “

a user” and

said received seed point is labeled “

user-provided seed point”

;

or

a means for generating automatically a likely seed point representing a part of the desired geospatial feature of the area of land.

66. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein, in the means for iteratively growing a region about a seed point, the region is grown using a level set technique, where the level set technique uses a speed function to control and stop the evolution of a growing region, and wherein the speed function is defined in terms of features that include at least one of:

spectral uniformity;

consistent texture;

contrast with surrounding environment;

Transformed Vegetative Index mask (TVI mask); and

Water Index mask (WI mask).

67. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein, in the means for iteratively growing a region about a seed point, the region is grown using a level set technique using a Transformed Vegetative Index mask (TVI mask) and Water Index mask (WI mask), where the TVI mask is formed by combining near infrared and red color band information, with specific values for the TVI mask in regions with vegetation, and other specific values for the TVI mask in man made regions, and where the WI mask is formed by combining near infrared and green color band information, with specific values for the WI mask in water regions, and other specific values for the WI mask in man made regions.

68. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, further comprising a means for iteratively smoothing the edges of the grown region in order to eliminate boundary irregularities in a boundary of the grown region, wherein the means for smoothing is based on a level set technique using a speed function to control and stop the evolution of a growing region around the boundary irregularities of the grown region, and wherein the smoothing of the grown region results in a smoothed grown region.

69. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 68, wherein, in the means for iteratively smoothing the edges of the grown region, the speed function for the level set technique is defined in terms of a curvature measurement of the boundary of the grown region, wherein the boundary of the grown region has global properties that define an overall shape of the grown region, and wherein a finite number of iterations are performed in order to smooth out local irregularities in the boundary of the grown region, without changing the global properties of the boundary of the grown region.

70. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 69, wherein, in the means for iteratively smoothing the edges of the grown region, the grown region has a curvature value associated with its boundary, and wherein the curvature of the boundary of the grown region, κ

, and the speed function, F(x,y), are defined by

$\mathrm{\kappa <br><br>}=\frac{{\mathrm{\Phi <br><br>}}_{\mathrm{xx}}<br><br>{\mathrm{\Phi <br><br>}}_y^2-2<br><br>{\mathrm{\Phi <br><br>}}_x<br><br>{\mathrm{\Phi <br><br>}}_y<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{xy}}+{\mathrm{\Phi <br><br>}}_{\mathrm{yy}}<br><br>{\mathrm{\Phi <br><br>}}_x^2}{{\left({\mathrm{\Phi <br><br>}}_x^2+{\mathrm{\Phi <br><br>}}_y^2\right)}^{3/2}}$
F(x,y)=−

min(κ

(x,y),0)

where

Φ

denotes a level set function defined by Φ

(x,y)=±

d(x,y), where d(x,y) denotes smallest distance from a point (x,y) within the image to the boundary of the grown region, and the +/−

signs are chosen such that points inside the boundary have a negative distance sign, and such that points outside the boundary have a positive distance sign;

Φ

_x denotes the partial derivative of Φ

with respect to x coordinate;

Φ

_y denotes the partial derivative of Φ

with respect to y coordinate;

Φ

_xy denotes the partial derivatives of Φ

with respect to x and y coordinates;

Φ

_xx denotes the partial derivatives of Φ

with respect to x and x coordinates; and

Φ

_yy denotes the partial derivatives of Φ

with respect to y and y coordinates.

71. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, further comprising a means for filtering the grown region with respect to geometrical characteristics of the desired geospatial feature, wherein the filtering of the grown region results in a filtered grown region, and wherein the filtered grown region has connectivity properties and a center line, where the center line preserves the connectivity properties of the filtered grown region.

72. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 71, wherein, in the means for appending a selected grown region to a network of grown geospatial features, the selected grown region comprises the filtered grown region.

73. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 71, wherein in the means for filtering the grown region the desired geospatial features are roads, where the width and length of the grown regions are used as criteria for accepting or rejecting the grown regions as real roads or false roads, and wherein the filtered grown regions contain only real roads.

74. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 73, further comprising the means for:

performing junction analysis, wherein filtered grown regions with centerlines that meet at appropriate angles within road intersections are accepted as real roads, and where filtered grown regions with centerlines that do not meet at appropriate angles within road intersections are considered false roads; and

checking junctions of real roads for shape regularity, wherein intersecting real roads having similar road shape properties are automatically linked and appended to a network of grown roads.

75. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein, in the means for automatically reseeding a point on the image, the selected grown region has a center line, with the center line having an orientation, and where the system further comprises the means for:

computing the center line of the selected grown region; and

when the selected grown region reaches a “

dead end,”

searching an area about the “

dead end”

to find a new point in the image with similar characteristics to the initial seed point, in order to continue the growing of the region representative of the desired geospatial feature, and wherein the search region about the “

dead end”

consists of a “

cone shaped”

search region with an orientation determined by the orientation of the centerline of the selected grown region, as the centerline approaches the “

dead end.”

76. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein, in the means for reseeding, the characteristics used to compare the reseeding point with the initial seed point comprise:

textural properties of the image at the reseeding point and textural properties of the image at the initial seed point; and

distance from the reseeding point to an edge of a region grown out of the reseeding point, and distance from the initial seed point to an edge of the grown region.

77. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, further comprising a means for computing geometrical features of the network of grown geospatial features, wherein the network of grown geospatial features has branches, and wherein the geometrical features of the network include at least one of:

centerlines, areas, lengths, widths, shapes, and roundness values of all the branches in the network.

78. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein, in the means for growing a region about the seed point, the region is grown using a level set technique that utilizes a speed function F(x,y) defined by

$\begin{array}{c}F\end{array}$

( x , y ) = ⁢

( w ⁢

⁢

ⅇ

- 1 2 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) ⁢

Σ

- 1 ⁡

( c ^ ⁡

( x , y ) - μ

_ 0 ) T + ( 1 - w ) ⁢

ⅇ

- 

H ⁡

( x , y ) - H 0 

) * ⁢

1 1 + 

∇

I ⁡

( x , y ) 

p * ⅇ

- 

TV1 ⁡

( x , y ) - 0.8 

* ⅇ

- 

WI ⁡

( x , y ) - 0.9 

where;

the first term of the speed function located to the right of the equal sign denotes a spectral uniformity of the grown region;

the second term of the speed function located to the right of the equal sign denotes a consistent texture of the grown region;

the third term of the speed function located to the right of the equal sign denotes contrast of the grown region with a surrounding environment;

the fourth term of the speed function located to the right of the equal sign hinders growth of the grown region into vegetation regions;

the last term of the speed function located to the right of the equal sign hinders growth of the grown region into water regions;

ĉ

(x,y) denotes spectral values of the image at (x,y) location;

μ

₀ represents a vector containing spectral intensities of the image at the user-provided seed point location;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

parameter w determines relative weightings between the spectral uniformity and the entropy terms representing the texture of the grown region;

∇

I term denotes an image gradient which extracts strong edges between the boundary of the grown region and other regions;

Σ

denotes a diagonal covariance matrix which is a function of noise present in the image, where Σ

allows for tuning the sensitivity of the spectral uniformity term; and

parameter p is a function of contrast present in the image, where p allows for tuning the sensitivity of the contrast term.

79. A system for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 41, wherein, in the means for automatically reseeding a point on the image, when a selected grown region reaches a “

dead end,”

the reseeding point is determined as a maximum likelihood point that lies within a “

cone shaped”

search region about the “

dead end”

that most closely satisfy

$\begin{array}{c}\mathrm{SeedLH}<br><br>\left(x,y\right)=<br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\frac{{\left(\frac{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)+{\mathrm{\sigma <br><br>}}_0}{2}+{\left(\frac{H<br><br>\left(x,y\right)-H_0}{2}\right)}^2\right)}^2}{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)*{\mathrm{\sigma <br><br>}}_0}-1<br><br>\right\}*\\ <br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\mathrm{e<br><br>}<br><br><br><br>\mathrm{dt}<br><br>\left(x,y\right)-d_0<br><br>\right\}\end{array}$

where

SeedLH(x,y) denotes likelihood of a point (x,y) of being an appropriate reseeding point representing a part of the desired geospatial feature of the area of land;

σ

(x,y) denotes variance associated with the image at point (x,y);

σ

₀ denotes variance associated with the initial seed point;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the initial seed point location;

edt(x,y) (Euclidean Distance Transform) denotes a Euclidean distance between a pixel point (x,y) and a nearest edge of a region grown out of the pixel point (x,y); and

d₀ denotes estimated width of the previously selected grown region which terminated on the “

dead end”

generating the current “

cone shaped”

search region.

80. A system for automatically extracting geospatial features from multi-spectral imagery suitable for fast and robust extraction of landmarks evolved from a single seed point, the system comprising means for:

receiving an image of an area of land;

generating automatically likely seed points representing a part of a desired geospatial feature of the area of land;

iteratively growing a region about the seed point based on a level set technique, with the region representative of the desired geospatial feature, and wherein the growing of the region results in a grown region having edges and a boundary;

appending a selected grown region to a network of grown geospatial features;

automatically reseeding a point on the image, wherein said reseeding point represents a potentially disjointed region of the desired geospatial feature of the area of land;

iteratively performing the means for growing a region about the seed point, appending, and reseeding, until either exhausting all likely candidates of potentially disjointed regions of the desired geospatial feature, or until reaching the boundaries of the image of an area of land; and

outputting the grown network representative of the desired geospatial feature;

whereby the outputs include the network of the grown geospatial feature, and any geometrical or spectral features extracted from the network of the grown geospatial feature.

81. A computer program product for automatically extracting geospatial features from multi-spectral imagery suitable for fast and robust extraction of landmarks evolved from a single seed point, the computer program product comprising means, stored on a computer readable medium for:

receiving an image of an area of land;

receiving a seed point, wherein said seed point represents a part of a desired geospatial feature of the area of land;

iteratively growing a region about the seed point based on a level set technique, with the region representative of the desired geospatial feature, and wherein the growing of the region results in a grown region having edges and a boundary;

appending a selected grown region to a network of grown geospatial features;

automatically reseeding a point on the image, wherein said reseeding point represents a potentially disjointed region of the desired geospatial feature of the area of land;

iteratively performing the means for growing a region about the seed point, the means for appending, and the means for reseeding, until either exhausting all likely candidates of potentially disjointed regions of the desired geospatial feature, or until reaching the boundaries of the image of an area of land; and

outputting the network of grown geospatial features;

whereby the outputs include the network of grown geospatial features, and any geometrical or spectral features extracted from the network of grown geospatial features.

82. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein in the means for receiving an image of an area of land, there are two types of input imagery consisting of multi-spectral input data, and panchromatic input data.

83. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 82, where the multi-spectral input data and the panchromatic input data are used to create a pan-sharpened image, and wherein the pan-sharpened image preserves the details provided by the panchromatic data, while allowing for the exploitation of color information provided by the four-band color multi-spectral data.

84. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 83, wherein in the means for receiving a seed point, the seed point is provided by a person using the computer program product for automatically extracting geospatial features from multispectral imagery, where said person using the computer program product is called “

a user” and

said received seed point is labeled “

user-provided seed point”

.

85. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 84, wherein, in the means for iteratively growing a region about the seed point, the region is grown using a level set technique, where the level set technique uses a speed function to control and stop the evolution of a growing region, and wherein the growing region has spectral uniformity and consistent texture.

86. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 85, wherein, in the means for iteratively growing a region about the seed point based on a level set technique, the level set technique speed function is defined in terms of features that include at least one of:

spectral uniformity;

consistent texture;

contrast with surrounding environment;

Transformed Vegetative Index mask (TVI mask); and

Water Index mask (WI mask).

87. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 86, wherein the TVI mask is a measurement of light reflectance, with specific values for the TVI mask in regions with vegetation, and other specific values for the TVI mask in man made regions, and where the TVI mask is formed by combining near infrared and red color band information.

88. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 87, wherein the WI mask is a measurement of light reflectance, with specific values for the WI mask in water regions, and other specific values for the WI mask in man made regions, and where the WI mask is formed by combining near infrared and green color band information.

89. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 88, further comprising a means for iteratively smoothing the edges of the grown region based on a level set technique in order to eliminate boundary irregularities in a boundary of the grown region, wherein the level set technique uses a speed function to control and stop the evolution of a growing region around the boundary irregularities of the grown region, and wherein the smoothing of the grown region results in a smoothed grown region.

90. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 89, wherein, in the means for iteratively smoothing the edges of the grown region, the speed function for the level set technique is defined in terms of a curvature measurement of the boundary of the grown region, wherein the boundary of the grown region has global properties that define an overall shape of the grown region, and wherein a finite number of iterations are performed in order to smooth out local irregularities in the boundary of the grown region, without changing the global properties of the boundary of the grown region.

91. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 90, further comprising a means for filtering the smoothed grown region with respect to geometrical characteristics of the desired geospatial feature, wherein the filtering of the smoothed grown region results in a filtered grown region, and wherein the filtered grown region has connectivity properties.

92. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 91, wherein the filtered grown region has a center line, and where the computer program product further comprises a means for computing the center line of the filtered grown region, wherein the center line preserves the connectivity properties of the filtered grown region.

93. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 92, wherein, in the means for appending a selected grown region to a network of grown geospatial features, the selected grown region comprises the filtered grown region.

94. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 93, wherein when the filtered grown region reaches a “

dead end,”

the means for reseeding automatically searches an area about the “

dead end”

to find a new point in the image with similar characteristics to the user-provided seed point, in order to continue the growing of the region representative of the desired geospatial feature.

95. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 94, wherein the centerline of the filtered grown region has an orientation, and wherein the search region about the “

dead end”

consists of a “

cone shaped”

search region with an orientation determined by the orientation of the centerline of the filtered grown region, as the centerline approaches the “

dead end.”

96. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 95, wherein, in the means for reseeding, the characteristics used to compare the reseeding point with the user-provided seed point comprise:

textural properties of the image at the reseeding point and textural properties of the image at the user-provided seed point; and

distance from the reseeding point to an edge of a region grown out of the reseeding point, and distance from the user-provided seed point to an edge of the filtered grown region.

97. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 96, further comprising a means for computing geometrical features of the network of grown geospatial features, wherein the network of grown geospatial features has branches, and wherein the geometrical features of the network include at least one of:

centerlines, areas, lengths, widths, shapes, and roundness values of all the branches in the network.

98. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 97, wherein in the means for filtering the smoothed grown region the desired geospatial features are roads, where the width and length of the smoothed grown regions are used as criteria for accepting or rejecting the smoothed grown regions as real roads or false roads, and wherein the filtered grown regions contain only real roads.

99. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 98, further comprising the means for performing junction analysis, wherein filtered grown regions with centerlines that meet at appropriate angles within road intersections are accepted as real roads, and where filtered grown regions with centerlines that do not meet at appropriate angles within road intersections are considered false roads.

100. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 99, further comprising a means for checking junctions of real roads for shape regularity, wherein intersecting real roads having similar road shape properties are automatically linked.

101. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 100, wherein, in the means for growing a region about the seed point, the speed function for the level set technique, F(x,y), is defined by

$\begin{array}{c}F\end{array}$

( x , y ) = ⁢

( w ⁢

⁢

ⅇ

- 1 2 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) ⁢

Σ

- 1 ⁡

( c ^ ⁡

( x , y ) - μ

_ 0 ) T + ( 1 - w ) ⁢

ⅇ

- 

H ⁡

( x , y ) - H 0 

) * ⁢

1 1 + 

∇

I ⁡

( x , y ) 

p * ⅇ

- 

TV1 ⁡

( x , y ) - 0.8 

* ⅇ

- 

WI ⁡

( x , y ) - 0.9 

where;

the first term of the speed function located to the right of the equal sign denotes a spectral uniformity of the grown region;

the second term of the speed function located to the right of the equal sign denotes a consistent texture of the grown region;

the third term of the speed function located to the right of the equal sign denotes contrast of the grown region with a surrounding environment;

the fourth term of the speed function located to the right of the equal sign hinders growth of the grown region into vegetation regions;

the last term of the speed function located to the right of the equal sign hinders growth of the grown region into water regions;

ĉ

(x,y) denotes spectral values of the image at (x,y) location;

μ

₀ represents a vector containing spectral intensities of the image at the user-provided seed point location;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

parameter w determines relative weightings between the spectral uniformity and the entropy terms representing the texture of the grown region;

∇

I term denotes an image gradient which extracts strong edges between the boundary of the grown region and other regions;

Σ

denotes a diagonal covariance matrix which is a function of noise present in the image, where Σ

allows for tuning the sensitivity of the spectral uniformity term; and

parameter p is a function of contrast present in the image, where p allows for tuning the sensitivity of the contrast term.

102. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 101, wherein, in the means for iteratively smoothing the edges of the grown region, the grown region has a curvature value associated with its boundary, and wherein the curvature of the boundary of the grown region, κ

, and the speed function, F(x,y), are defined by

$\mathrm{\kappa <br><br>}=\frac{{\mathrm{\Phi <br><br>}}_{\mathrm{xx}}<br><br>{\mathrm{\Phi <br><br>}}_y^2-2<br><br>{\mathrm{\Phi <br><br>}}_x<br><br>{\mathrm{\Phi <br><br>}}_y<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{xy}}+{\mathrm{\Phi <br><br>}}_{\mathrm{yy}}<br><br>{\mathrm{\Phi <br><br>}}_x^2}{{\left({\mathrm{\Phi <br><br>}}_x^2+{\mathrm{\Phi <br><br>}}_y^2\right)}^{3/2}}$
F(x,y)=−

min(κ

(x,y),0)

where

Φ

denotes a level set function defined by Φ

(x,y)=±

d(x,y), where d(x,y) denotes smallest distance from a point (x,y) within the image to the boundary of the grown region, and the +/−

signs are chosen such that points inside the boundary have a negative distance sign, and such that points outside the boundary have a positive distance sign;

Φ

_x denotes the partial derivative of Φ

with respect to x coordinate;

Φ

_y denotes the partial derivative of Φ

with respect to y coordinate;

Φ

_xy denotes the partial derivatives of Φ

with respect to x and y coordinates;

Φ

_xx denotes the partial derivatives of Φ

with respect to x and x coordinates; and

Φ

_yy denotes the partial derivatives of Φ

with respect to y and y coordinates.

103. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 102, wherein, in the means for automatically reseeding a point on the image, the reseeding point is determined as a maximum likelihood point that lies within the “

cone shaped”

search region about the “

dead end”

that most closely satisfy

$\begin{array}{c}\mathrm{SeedLH}<br><br>\left(x,y\right)=<br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\frac{{\left(\frac{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)+{\mathrm{\sigma <br><br>}}_0}{2}+{\left(\frac{H<br><br>\left(x,y\right)-H_0}{2}\right)}^2\right)}^2}{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)*{\mathrm{\sigma <br><br>}}_0}-1<br><br>\right\}*\\ <br><br>\mathrm{Exp}<br><br>\left\{-<br><br>\mathrm{e<br><br>}<br><br><br><br>\mathrm{dt}<br><br>\left(x,y\right)-d_0<br><br>\right\}\end{array}$

where

SeedLH(x,y) denotes likelihood of a point (x,y) of being an appropriate reseeding point representing a part of the desired geospatial feature of the area of land;

σ

(x,y) denotes variance associated with the image at point (x,y);

σ

₀ denotes variance associated with the user-provided seed point;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

edt(x,y) (Euclidean Distance Transform) denotes a Euclidean distance between a pixel point (x,y) and a nearest edge of a region grown out of the pixel point (x,y); and

d₀ denotes estimated width of the previously filtered grown region which terminated on the “

dead end”

generating the current “

cone shaped”

search region.

104. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein in the means for receiving an image of an area of land, there are two types of input imagery consisting of multi-spectral input data, and panchromatic input data, and where the multi-spectral input data and the panchromatic input data are used to create a pan-sharpened image, wherein the pan-sharpened image preserves the details provided by the panchromatic data, while allowing for the exploitation of color information provided by the four-band color multi-spectral data.

105. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein in the means for receiving a seed point, the seed point is provided by either:

a person using the computer program product for automatically extracting geospatial features from multispectral imagery, where said person using the computer program product is called “

a user” and

said received seed point is labeled “

user-provided seed point”

;

or

a means for generating automatically a likely seed point representing a part of the desired geospatial feature of the area of land.

106. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein, in the means for iteratively growing a region about a seed point, the region is grown using a level set technique, where the level set technique uses a speed function to control and stop the evolution of a growing region, and wherein the speed function is defined in terms of features that include at least one of:

spectral uniformity;

consistent texture;

contrast with surrounding environment;

Transformed Vegetative Index mask (TVI mask); and

Water Index mask (WI mask).

107. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein, in the means for iteratively growing a region about a seed point, the region is grown using a level set technique using a Transformed Vegetative Index mask (TVI mask) and Water Index mask (WI mask), where the TVI mask is formed by combining near infrared and red color band information, with specific values for the TVI mask in regions with vegetation, and other specific values for the TVI mask in man made regions, and where the WI mask is formed by combining near infrared and green color band information, with specific values for the WI mask in water regions, and other specific values for the WI mask in man made regions.

108. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, further comprising a means for iteratively smoothing the edges of the grown region in order to eliminate boundary irregularities in a boundary of the grown region, wherein the means for smoothing is based on a level set technique using a speed function to control and stop the evolution of a growing region around the boundary irregularities of the grown region, and wherein the smoothing of the grown region results in a smoothed grown region.

109. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 108, wherein, in the means for iteratively smoothing the edges of the grown region, the speed function for the level set technique is defined in terms of a curvature measurement of the boundary of the grown region, wherein the boundary of the grown region has global properties that define an overall shape of the grown region, and wherein a finite number of iterations are performed in order to smooth out local irregularities in the boundary of the grown region, without changing the global properties of the boundary of the grown region.

110. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 109, wherein, in the means for iteratively smoothing the edges of the grown region, the grown region has a curvature value associated with its boundary, and wherein the curvature of the boundary of the grown region, κ

, and the speed function, F(x,y), are defined by

$\mathrm{\kappa <br><br>}=\frac{{\mathrm{\Phi <br><br>}}_{\mathrm{xx}}<br><br>{\mathrm{\Phi <br><br>}}_y^2-2<br><br>{\mathrm{\Phi <br><br>}}_x<br><br>{\mathrm{\Phi <br><br>}}_y<br><br>{\mathrm{\Phi <br><br>}}_{\mathrm{xy}}+{\mathrm{\Phi <br><br>}}_{\mathrm{yy}}<br><br>{\mathrm{\Phi <br><br>}}_x^2}{{\left({\mathrm{\Phi <br><br>}}_x^2+{\mathrm{\Phi <br><br>}}_y^2\right)}^{3/2}}$
F(x,y)=−

min(κ

(x,y),0)

where

Φ

denotes a level set function defined by Φ

(x,y)=±

d(x,y), where d(x,y) denotes smallest distance from a point (x,y) within the image to the boundary of the grown region, and the +/−

signs are chosen such that points inside the boundary have a negative distance sign, and such that points outside the boundary have a positive distance sign;

Φ

_x denotes the partial derivative of Φ

with respect to x coordinate;

Φ

_y denotes the partial derivative of Φ

with respect to y coordinate;

Φ

_xy denotes the partial derivatives of Φ

with respect to x and y coordinates;

Φ

_xx denotes the partial derivatives of Φ

with respect to x and x coordinates; and

Φ

_yy denotes the partial derivatives of Φ

with respect to y and y coordinates.

111. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, further comprising a means for filtering the grown region with respect to geometrical characteristics of the desired geospatial feature, wherein the filtering of the grown region results in a filtered grown region, and wherein the filtered grown region has connectivity properties and a center line, where the center line preserves the connectivity properties of the filtered grown region.

112. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 111, wherein, in the means for appending a selected grown region to a network of grown geospatial features, the selected grown region comprises the filtered grown region.

113. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 111, wherein in the means for filtering the grown region the desired geospatial features are roads, where the width and length of the grown regions are used as criteria for accepting or rejecting the grown regions as real roads or false roads, and wherein the filtered grown regions contain only real roads.

114. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 113, further comprising the means for:

performing junction analysis, wherein filtered grown regions with centerlines that meet at appropriate angles within road intersections are accepted as real roads, and where filtered grown regions with centerlines that do not meet at appropriate angles within road intersections are considered false roads; and

checking junctions of real roads for shape regularity, wherein intersecting real roads having similar road shape properties are automatically linked and appended to a network of grown roads.

115. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein, in the means for automatically reseeding a point on the image, the selected grown region has a center line, with the center line having an orientation, and where the computer program product further comprises the means for:

computing the center line of the selected grown region; and

when the selected grown region reaches a “

dead end,”

searching an area about the “

dead end”

to find a new point in the image with similar characteristics to the initial seed point, in order to continue the growing of the region representative of the desired geospatial feature, and wherein the search region about the “

dead end”

consists of a “

cone shaped”

search region with an orientation determined by the orientation of the centerline of the selected grown region, as the centerline approaches the “

dead end.”

116. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein, in the means for reseeding, the characteristics used to compare the reseeding point with the initial seed point comprise:

textural properties of the image at the reseeding point and textural properties of the image at the initial seed point; and

distance from the reseeding point to an edge of a region grown out of the reseeding point, and distance from the initial seed point to an edge of the grown region.

117. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, further comprising a means for computing geometrical features of the network of grown geospatial features, wherein the network of grown geospatial features has branches, and wherein the geometrical features of the network include at least one of:

centerlines, areas, lengths, widths, shapes, and roundness values of all the branches in the network.

118. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein, in the means for growing a region about the seed point, the region is grown using a level set technique that utilizes a speed function F(x,y) defined by

$F$

( x , y ) = ( w ⁢

⁢

ⅇ

- 1 2 ⁢

( c ^ ⁡

( x , y ) - μ

_ 0 ) ⁢

Σ

- 1 ⁡

( c ^ ⁡

( x , y ) - μ

_ 0 ) T + ( 1 - w ) ⁢

ⅇ

- 

H ⁡

( x , y ) - H 0 

) * 1 1 + 

∇

I ⁡

( x , y ) 

p * ⅇ

- 

TVI ⁡

( x , y ) - 0.8 

* ⅇ

- 

WI ⁡

( x , y ) - 0.9 

where;

the first term of the speed function located to the right of the equal sign denotes a spectral uniformity of the grown region;

the second term of the speed function located to the right of the equal sign denotes a consistent texture of the grown region;

the third term of the speed function located to the right of the equal sign denotes contrast of the grown region with a surrounding environment;

the fourth term of the speed function located to the right of the equal sign hinders growth of the grown region into vegetation regions;

the last term of the speed function located to the right of the equal sign hinders growth of the grown region into water regions;

ĉ

(x,y) denotes spectral values of the image at (x,y) location;

μ

₀ represents a vector containing spectral intensities of the image at the user-provided seed point location;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the user-provided seed point location;

parameter w determines relative weightings between the spectral uniformity and the entropy terms representing the texture of the grown region;

∇

I term denotes an image gradient which extracts strong edges between the boundary of the grown region and other regions;

Σ

denotes a diagonal covariance matrix which is a function of noise present in the image, where Σ

allows for tuning the sensitivity of the spectral uniformity term; and

parameter p is a function of contrast present in the image, where p allows for tuning the sensitivity of the contrast term.

119. A computer program product for automatically extracting geospatial features from multi-spectral imagery as set forth in claim 81, wherein, in the means for automatically reseeding a point on the image, when a selected grown region reaches a “

dead end,”

the reseeding point is determined as a maximum likelihood point that lies within a “

cone shaped”

search region about the “

dead end”

that most closely satisfy

$\mathrm{SeedLH}<br><br>\left(x,y\right)=\mathrm{Exp}<br><br>\left\{-<br><br>\frac{{\left(\frac{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)+{\mathrm{\sigma <br><br>}}_0}{2}+{\left(\frac{H<br><br>\left(x,y\right)-H_0}{2}\right)}^2\right)}^2}{\mathrm{\sigma <br><br>}<br><br>\left(x,y\right)*{\mathrm{\sigma <br><br>}}_0}-1<br><br>\right\}*\mathrm{Exp}<br><br>\left\{-<br><br>\mathrm{e<br><br>}<br><br><br><br>\mathrm{dt}<br><br>\left(x,y\right)-d_0<br><br>\right\}$

where

SeedLH(x,y) denotes likelihood of a point (x,y) of being an appropriate reseeding point representing a part of the desired geospatial feature of the area of land;

σ

(x,y) denotes variance associated with the image at point (x,y);

σ

₀ denotes variance associated with the initial seed point;

H(x,y) denotes an entropy value of the image at point (x,y);

H₀ is an entropy value of the image at the initial seed point location;

edt(x,y) (Euclidean Distance Transform) denotes a Euclidean distance between a pixel point (x,y) and a nearest edge of a region grown out of the pixel point (x,y); and

d₀ denotes estimated width of the previously selected grown region which terminated on the “

dead end”

generating the current “

cone shaped”

search region.

120. A computer program product for automatically extracting geospatial features from multi-spectral imagery suitable for fast and robust extraction of landmarks evolved from a single seed point, the computer program product comprising means for:

receiving an image of an area of land;

generating automatically likely seed points representing a part of a desired geospatial feature of the area of land;

iteratively growing a region about the seed point based on a level set technique, with the region representative of the desired geospatial feature, and wherein the growing of the region results in a grown region having edges and a boundary;

appending a selected grown region to a network of grown geospatial features;

automatically reseeding a point on the image, wherein said reseeding point represents a potentially disjointed region of the desired geospatial feature of the area of land;

iteratively performing the means for growing a region about the seed point, appending, and reseeding, until either exhausting all likely candidates of potentially disjointed regions of the desired geospatial feature, or until reaching the boundaries of the image of an area of land; and

outputting the grown network representative of the desired geospatial feature;

whereby the outputs include the network of the grown geospatial feature, and any geometrical or spectral features extracted from the network of the grown geospatial feature.