Method and apparatus for automatic linear object identification using identified terrain types in images

• US 7,894,675 B2
• Filed: 03/10/2008
• Issued: 02/22/2011
• Est. Priority Date: 07/18/2003
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Skoblick, Richard, Phurrough, Larry, Wiedemann, Melissa, Gratsch, Colleen Flynn, Lee, Harry C.
• Primary Examiner(s): ZARKA, DAVID PETER
• Application Number:
  US12/073,809
• Publication Number:
  US 20080317345A1
• Time in Patent Office: 1,079 Days
• Field of Search: 382/199
• US Class Current: 382/199
• CPC Class Codes: G06V 20/13 Satellite images
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A method and apparatus are provided for identifying linear objects in an image. Terrain types in the image are identified, and a gradient vector image, which identifies a gradient magnitude value and a gradient direction value for each pixel of the image, is generated from the image. Lines in the gradient vector image are identified using the identified terrain types in each portion of the image. It is determined whether the identified lines are perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image. Lines among the identified line are eliminated which are determined to not be perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image. Linear objects are identified using the remaining identified lines which have not been eliminated.

Claims

1. A method for identifying linear objects in an image comprising:

identifying, in a processor of a computer processing device, terrain types in the image;

generating, in the processor, a gradient vector image from the image, the gradient vector image identifying a gradient magnitude value and a gradient direction value for each pixel of the image;

identifying, in the processor, lines in the gradient vector image using the identified terrain types in each portion of the image;

determining, in the processor, whether the identified lines are perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image;

eliminating, in the processor, lines among the identified lines which are determined to not be perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image; and

identifying, in the processor, linear objects using the remaining identified lines which have not been eliminated.

2. The method of claim 1, wherein the step of identifying lines using the identified terrain types comprises:

applying the identified terrain types to the gradient vector image;

determining a threshold based on mean gradient magnitudes for each individual identified terrain type; and

eliminating pixels in the gradient vector image having a gradient magnitude not greater than the threshold for the identified terrain type associated with the eliminated pixels.

3. The method of claim 2, wherein the step of identifying lines further comprises:

comparing each remaining pixel that has not been eliminated in the gradient vector image to neighboring pixels; and

eliminating a remaining pixel if the gradient magnitude value of the remaining pixel is less than the gradient magnitude value of one of the neighboring pixels.

4. The method of claim 3, wherein a pixel is determined to be a neighboring pixel based on the gradient direction value of the remaining pixel.

5. The method of claim 3, further comprising:

grouping pixels in a line with the same gradient direction value into a region, wherein the grouping accounts for errors in a respectively corresponding gradient direction value of the grouped pixels.

6. The method of claim 5, further comprising:

dividing the region into a plurality of subregions if the region is greater than a predetermined number of pixels; and

determining a straight line approximation for at least one of the subregions, wherein the straight line approximation is based on a calculated slope and center of mass for the at least one of the subregions.

7. The method of claim 6, further comprising:

determining a slope, endpoints, Y-intercept, and length of each of the identified lines or straight line approximations; and

storing the slope, endpoints, Y-intercept, and length of each of the identified lines or straight line approximations.

8. The method of claim 7, wherein the determination of whether identified lines are collinear or parallel to another line among the identified lines in the gradient vector image comprises:

comparing each identified line or determined straight line approximation to every other identified line or determined straight line approximation with a similar stored slope to determine (i) whether the identified line or determined straight line approximation is a predetermined distance from other identified lines or straight line approximation with a similar stored slope, (ii) whether the identified line or determined straight line approximation is antiparallel to the other identified lines or determined straight line approximations with a similar stored slope, and (iii) whether the identified line or determined straight line approximation and the other identified lines or determined straight line approximations with a similar stored slope possess gradient magnitudes within a predetermined tolerance.

9. The method of claim 8, wherein the determination of whether identified lines are parallel to another line among the identified lines in the gradient vector image comprises:

determining whether each identified line or determined straight line approximation is within the same terrain type as the other identified line or determined straight line approximation, wherein if the lines are not within the same terrain type, the lines are determined not to be parallel.

10. The method of claim 1, further comprising:

grouping identified lines determined to be parallel into a parallel line group; and

dividing identified lines in each parallel line group into parallel line pairs based on a respective length of the lines.

11. The method of claim 10, wherein the linear objects are identified using the parallel line pairs.

12. A non-transitory computer-readable recording medium having a computer program recorded thereon that causes a computer to automatically identify linear objects in an image, the program causing the computer to perform operations comprising:

identifying terrain types in the image;

generating a gradient vector image from the image, the gradient vector image identifying a gradient magnitude value and a gradient direction value for each pixel of the image;

identifying lines in the gradient vector image using the identified terrain types in each portion of the image;

determining whether the identified lines are perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image;

eliminating lines among the identified lines which are determined to not be perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image; and

identifying linear objects using the remaining identified lines which have not been eliminated.

13. The non-transitory computer-readable recording medium of claim 12, wherein the wherein the operation of identifying lines using the identified terrain types comprises:

applying the identified terrain types to the gradient vector image;

determining a threshold based on mean gradient magnitudes for each individual identified terrain type; and

eliminating pixels in the gradient vector image having a gradient magnitude not greater than the threshold for the identified terrain type associated with the eliminated pixels.

14. An apparatus for identifying linear objects in an image, comprising:

a memory configured to store the image; and

a processor configured to;

identify terrain types in the image;

generate a gradient vector image from the image, the gradient vector image identifying a gradient magnitude value and a gradient direction value for each pixel of the image;

identify lines in the gradient vector image using the identified terrain types in each portion of the image;

determine whether the identified lines are perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image;

eliminate lines among the identified lines which are determined to not be perpendicular, collinear, or parallel to another line among the identified lines in the gradient vector image; and

identify linear objects using the remaining identified lines which have not been eliminated.

15. The apparatus of claim 14, wherein the processor in identifying the lines using the identified terrain types is configured to:

apply the identified terrain types to the gradient vector image;

determine a threshold based on mean gradient magnitudes for each individual identified terrain type; and

eliminate pixels in the gradient vector image having a gradient magnitude not greater than the threshold for the identified terrain type associated with the eliminated pixels.