Method and software-implemented apparatus for ground plane estimation in multi-dimensional data

• US 6,714,663 B1
• Filed: 11/09/1999
• Issued: 03/30/2004
• Est. Priority Date: 11/09/1999
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Bornowski, Arthur Steven
• Primary Examiner(s): Dastouri, Mehrdad
• Assistant Examiner(s): KIBLER, VIRGINIA M
• Application Number:
  US09/436,607
• Time in Patent Office: 1,603 Days
• Field of Search: 382/203, 382/291, 382/173, 382/106, 382/154, 356/3-22, 356/3.07, 356/5.04, 356/11, 250/559.31, 250/559.38, 701/4
• US Class Current: 382/106
• CPC Class Codes: A63F 2300/643 by determining the impact between objects, e.g. collision detection
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2207/10036 Multispectral image; Hyperspectral image
• CPC Class Codes: G06T 2207/30212 Military
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 7/11 Region-based segmentation

Abstract

A method for determining the reference plane in multi-dimensional data is disclosed. In one embodiment, the method includes (a) providing multi-dimensional imagery data, referred to as set A, including an array of pixels having object pixels marked; (b) range gating about at least a subset of the marked object pixels, including marking pixels outside the range gate to form an unmarked pixel subset of set A, referred to as subset B; (c) performing maximal z density analysis on subset B, including marking pixels outside the maximum density to form an unmarked pixel subset of subset B, referred to as subset C; (d) performing a local normal vector estimate on subset C, including marking pixels having a normal vector exceeding specified threshold L from nominal to form an unmarked pixel subset of subset C, referred to as subset D; (e) performing a first ground plane fit on subset D, each pixel producing residual value X, cumulatively known as residual set X; (f) analyzing residual X, including performing a residual density analysis and marking pixels whose residual value X exceeds specified threshold M to form an unmarked pixel subset of subset D, referred to as subset E; (g) performing a second ground plane fit on subset E, each pixel producing residual value Y, cumulatively known as residual set Y; (h) analyzing residual set Y, including marking pixels whose residual value Y exceeds specified threshold N to form an unmarked pixel subset of subset E, referred to as subset F; and (i) estimating the reference plane for subset F.

Claims

1. A method of determining the reference plane in multi-dimensional data comprising:

(a) providing multi-dimensional imagery data, referred to as set A, including an array of pixels having object pixels marked;

(b) range gating about at least a subset of the marked object pixels, including marking pixels outside the range gate to form an unmarked pixel subset of set A, referred to as subset B;

(c) performing a maximal z density analysis on subset B, including marking pixels outside the maximum density to form an unmarked pixel subset of subset B, referred to as subset C;

(d) performing a local normal vector estimate on subset C, including marking pixels having a normal vector exceeding specified threshold L from nominal to form an unmarked pixel subset of subset C, referred to as subset D;

(e) performing a first ground plane fit on subset D, each pixel producing residual value X, cumulatively known as residual set X;

(f) analyzing residual set X, including performing a residual density analysis and marking pixels whose residual value X exceeds specified threshold M to form an unmarked pixel subset of subset D, referred to a subset E.;

(g) performing a second ground plane fit on subset E, each pixel producing residual value Y, cumulatively known as residual set Y;

(h) analyzing residual set Y, including marking pixels whose residual value Y exceeds specified threshold N to form an unmarked pixel subset of subset E, referred to as subset F; and

(i) estimating the reference plane for subset F.

2. The method of claim 1, wherein the local normal vector estimate comprises a linear regression fit.

3. The method of claim 2, wherein the linear regression fit includes selecting a pixel within subset C and performing the linear regression on a subset of pixels within subset C comprising a three by three array of pixels centered around and including the selected pixel.

4. The method of claim 3, wherein the selected pixels are marked if beyond threshold M measured from the linear regression line.

5. The method of claim 1, wherein threshold L is 60 degrees from nominal flat ground.

6. The method of claim 1, wherein the first ground plane fit utilizes standard 37 linear regression.

7. The method of claim 1, wherein threshold M is 75%.

8. The method of claim 6, wherein threshold M is the percentage representing the smallest deviation from the regression line yielding the highest density of pixels.

9. The method of claim 1, wherein the specified threshold N is 0.5 meters.

26. A program storage device encoded with computer readable instruction for performing the operations recited in a specific one of claims 1-18 or 20-22.

10. A method of determining the reference plane in multi-dimensional data comprising:

(a) providing multi-dimensional imagery data, referred to as set A, including an array of pixels having object pixels marked;

(b) range gating about at least a subset of the marked object pixels, including marking pixels outside the range gate to form an unmarked pixel subset of set A, referred to as subset B;

(c) performing a local normal vector estimate on subset B, including marking pixels having a normal vector exceeding a specified vector threshold to form an unmarked pixel subset of subset B, referred to as subset C; and

(d) performing a ground plane fit on subset C.

11. The method of claim 10, further comprising:

(e) revising subset B by performing a maximal z density analysis on subset B, including marking pixels outside the maximum density to form unmarked pixel subset B.

12. The method of claim 10, wherein the local normal vector estimate comprises a linear regression fit performed on a subset of pixels within subset B.

13. The method of claim 12, wherein the subset of pixels within subset B comprises a three by three array of pixels.

14. The method of claim 10, wherein the vector threshold is 60 degrees from nominal flat ground.

15. The method of claim 10, wherein the ground plane fit produces a residual value for each unmarked pixel, further comprising:

(e) analyzing the residual values, including performing a residual density analysis and marking pixels whose residual value exceeds a specified threshold to form an unmarked pixel subset of subset C, referred to a subset D.

16. The method of claim 15, wherein the specified threshold is 75%.

17. The method of claim 15, wherein the specified threshold is approximately the lowest percentage yielding the highest density of residual values.

18. The method of claim 15, further comprising:

(e) estimating the reference plane for subset D.

19. A method for determining the reference plane in LADAR data in an automatic target recognition system, comprising:

removing a plurality of outliers from an array of three-dimensional imagery data to produce a local set of imagery data, including;

range gating a marked subset of the array of three-dimensional imagery data to produce the local set of imagery data; and

at least one of;

performing a maximal z density analysis to exclude from the local set of imagery data a plurality of data outside a maximum density;

performing a local normal vector estimate to exclude from the local set of imagery data a plurality of data exceeding a specified threshold from nominal; and

performing a linear ground plane fit of the local set of imagery data, and

iterating a residual, linear regression analysis to estimate the location of the reference plane in the local set of imagery data, each iteration including;

performing a linear best fit for a linear regression line;

excluding a plurality of data whose variance from the regression line exceeds a threshold to produce a respective residual data set; and

estimating the reference plane from the residual data set resulting from the iteration.

20. The method of claim 19, wherein the variance threshold is determined by a maximal z density analysis of the local set of imagery data.

21. The method of claim 19, wherein the variance or variable.

22. The method of claim 19, wherein estimating the reference plane includes performing a ground plane fit.

23. A method for determining the reference plane in LADAR data in an automatic target recognition system, comprising:

removing a plurality of outliers from an array of three-dimensional imagery data to produce a local set of imagery data, including range gating a marked subset of the array of three-dimensional imagery data to produce the local set of imagery data; and

iterating a residual, linear regression analysis to estimate the location of the reference plane in the local set of imagery data, each iteration including;

performing a linear best fit for a linear regression line;

excluding a plurality of data whose variance from the regression line exceeds a threshold to produce a respective residual data set, wherein the variance threshold is determined by a maximal z density analysis of the local set of imagery data; and

estimating the reference plane from the residual data set resulting from the iteration.

24. The method of claim 23, wherein the variance threshold is fixed or variable.

25. The method of claim 23, wherein estimating the reference plane includes performing a ground plane fit.