Method and system for direct classification from three dimensional digital imaging

• US 7,046,841 B1
• Filed: 08/29/2003
• Issued: 05/16/2006
• Est. Priority Date: 08/29/2003
• Status: Expired due to Fees

• Current Assignee: James W. Dow
• Original Assignee: Aerotec, LLC
• Inventors: Corbitt, Thomas, McLaughlin, Robert A., Dow, James W.
• Primary Examiner(s): Ahmed, Samir
• Application Number:
  US10/651,666
• Time in Patent Office: 991 Days
• Field of Search: 382/154, 382/181, 382/195, 382/201, 382/204, 382/206, 382/224, 345/419, 345/420, 345/421, 345/427, 356/12, 356/5.01, 701/1, 701/4, 342/25
• US Class Current: 382/154
• CPC Class Codes: G01C 11/00 Photogrammetry or videogrammetry, e.g. stereogrammetry; Photographic surveying
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G01S 7/4802 using analysis of echo signal for target characterisation; Target signature; Target cross-section
• CPC Class Codes: G06V 20/64 Three-dimensional objects

Abstract

An automated system and/or method is disclosed for rapidly, accurately, and efficiently processing bulk three-dimensional digital image data of both path/corridor and area scenes to discriminate different structures or classifications of objects from within the image. The method first decomposes the three-dimensional digital imagery coordinate points into simple local structures and then extracts the globally complex structures from the local structures. The system and/or method incorporates procedures for sub-dividing the three-dimensional image data into rectilinear and/or ellipsoidal finite element cells, mathematically analyzing the contents (point coordinates) of each individual cell to classify/define the local structure, and extracting the globally complex structure or object from the image. The system and/or method applies accepted mathematical formulas to filter or classify large volumes of apparently random three-dimensional point coordinate spatial data into simpler structures and then to extract more globally complex objects generally encountered within the real world imagery scene being investigated.

Claims

1. A method for processing digital image data taken from a three-dimensional topographic scene including terrain to extract discrete objects, the method comprising:

locating waypoints to define a centerline and a bounded area to be analyzed;

defining the primary dimensional characteristics or attributes of the objects to be extracted from the image;

defining finite element cells having a width dependent on the area of interest, a length dependent on the dimension of the objects and terrain variation and a height dependent on the discrete objects;

mapping the finite element cells to a normalized coordinate base;

grouping the digital image data, in the form of scanned three-dimensional point (x, y, z) coordinate points in Cartesian coordinate reference frames, into the finite element cells by determining eigenvalues and eigenvectors associated with each cell;

classifying each of the three-dimensional points as simple local structures;

composing globally complex structures from the local structures; and

wherein spatial relationships of the three-dimensional coordinate points within each finite element cell are analyzed by calculating a 3×

3 covariance matrix where C_j,k is the element in row j, column k in the matrix, (x_i)_j is the coordinate of point i in dimension j, n is the number of points in the cell, N_j is a normalization constant, N_k is a second normalization constant, m_k is the mean value of the coordinates of the points in dimension k, and m_j is the mean value of the coordinates of the points in dimension j, such that;

$C_{j,k}=\frac{1}{n·<br><br>N_j·<br><br>N_k}·<br><br>\underset{i}{\sum <br><br>}<br><br>\left[{\left(x_i\right)}_j-m_j\right]·<br><br>\left[{\left(x_i\right)}_k-m_k\right]$

calculating the eigenvalues and eigenvectors of the matrix, each eigenvector {right arrow over (e)}and corresponding eigenvalue λ

satisfying the equation;

C·

{right arrow over (e)}=λ

·

{right arrow over (e)}

wherein C is a constant, and such that the three eigenvalues measure the spread of the data in the direction of the corresponding eigenvectors.

2. The method of claim 1 wherein the finite element cells are spherical.

3. The method of claim 1 wherein the finite element cells are rectilinear.

4. The method of claim 1 wherein the finite element cells are ellipsoidal.

5. The method of claim 1 wherein the three-dimensional coordinate data points are captured in an ordered sequence.

6. The method of claim 1 wherein the three-dimensional coordinate data points are captured in a random sequence.

7. The method of claim 1 wherein the objects include a natural object.

8. The method of claim 7 wherein the natural object is further classified as vegetation or ground.

9. The method of claim 1 wherein the objects include a man made object.

10. The method of claim 1 wherein a cell is classified as a bare-earth/ground element if it is characterized by two large eigenvalues.

11. The method of claim 1 wherein a cell is classified as vegetation if it is characterized by three large eigenvalues.

12. The method of claim 1 wherein the cell is classified as a man made structure if it is characterized by a single large eigenvalue.

13. The method of claim 1 wherein further finite element cells are selected based on the presence or absence of objects within existing previously defined cells.

14. A system for processing a three-dimensional digital image of topographic scenes to extract discrete objects, the system comprising:

a processor which accepts inputs of a three-dimensional digital image;

wherein the processor locates waypoints to define the primary dimensional characteristics or attributes of the objects to be extracted from the image;

wherein the processor defines finite element cells having a width dependent on the area of interest, a length dependent on the dimensions of the discrete objects and terrain variation and a height dependent on the discrete objects;

wherein the processor groups the digital image data, in the form of scanned three-dimensional point (x, y, z) coordinates in Cartesian coordinate reference frames, into the finite element cells;

the processor classifies each of the three-dimensional points as simple local structures;

wherein the processor composes globally complex structures from the local structures and wherein the spatial relationships of the three-dimensional coordinate points within each finite element cell are analyzed by calculating a 3×

3 covariance matrix, where C_j,k is the element in row j, column k in the matrix, (x_i)_j is the coordinate of point i in dimension j, n is the number of points in the cell, N_j is a normalization constant, N_k is a second normalization constant, m_k is the mean value of the coordinates of the points in dimension k, and m_j is the mean value of the coordinates of the points in dimension j, such that;

$C_{j,k}=\frac{1}{n·<br><br>N_j·<br><br>N_k}·<br><br>\underset{i}{\sum <br><br>}<br><br>\left[{\left(x_i\right)}_j-m_j\right]·<br><br>\left[{\left(x_i\right)}_k-m_k\right]$

calculating the eigenvalues and eigenvectors of the matrix, each eigenvector {right arrow over (e)} and corresponding eigenvalue λ

satisfying the equation;

C·

{right arrow over (e)}=λ

·

{right arrow over (e)}

wherein C is a constant, and such that the three eigenvalues measure the spread of the data in the direction of the corresponding eigenvectors.

15. The system of claim 14 further comprising a remote sensor capable of scanning an area and producing a digital 3-dimensional representation.

16. The system of claim 15 wherein the remote sensor is a Light Imaging Distance And Ranging instrument.

17. The system of claim 15 wherein the remote sensor is a synthetic aperture radar.

18. The system of claim 14 wherein the finite element cells are spherical.

19. The system of claim 14 wherein the finite element cells are rectilinear.

20. The system of claim 14 wherein the finite element cells are ellipsoidal.

21. The system of claim 14 wherein the three-dimensional coordinate data points are captured in an ordered sequence.

22. The system of claim 14 wherein the three-dimensional coordinate data points are captured in a random sequence.

23. The system of claim 14 wherein the object is classified as a natural object or a man made object.

24. The system of claim 23 wherein the natural object is further classified as ground or vegetation.

25. The system of claim 14 wherein a cell is classified as a bare-earth/ground element if it is characterized by two large eigenvalues.

26. The system of claim 14 wherein a cell is classified as vegetation if it is characterized by three large eigenvalues.

27. The system of claim 14 wherein the cell is classified as a man made structure if it is characterized by a single large eigenvalue.