ACCURACY-BASED SIGNIFICANT POINT DERIVATION FROM DENSE 3D POINT CLOUDS FOR TERRAIN MODELING

• US 20130144565A1
• Filed: 12/01/2011
• Published: 06/06/2013
• Est. Priority Date: 12/01/2011
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Rahmes, Mark, Akbari, Morteza, Miller, Stephan W., Houser, Jeffrey W.
• Granted Patent: US 8,793,107 B2
• Time in Patent Office: Days
• US Class Current: 703/1
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering

Abstract

Method includes calculating a mean z coordinate value for points within the point cloud. An initial set of points is selected which have z coordinate values which deviate from the mean by at least an initial value. Thereafter, a triangulated irregular network (TIN) is constructed using the initial set of points. The method continues by determining if there is a significant point that exists among the points contained within an x, y extent of each triangle. If so, the TIN is updated to include the initial set of points and any significant points determined to exist within the triangles that form the TIN. Thereafter, the method continues by repeating the determining and the updating steps until there are no additional significant points found within the triangles.

Claims

1. A method for using a computer processor to derive significant points from a point cloud containing data representing a physical surface and defined within a three dimensional coordinate system, comprising:

calculating a mean z coordinate value for a plurality of points having x, y and z coordinates within said three-dimensional coordinate systems;

using said computer processor to select from said point cloud data, an initial set of points having z coordinate values which deviate from said mean by at least an initial value;

constructing with said computer processor a triangulated irregular network (TIN) using said initial set of points, said TIN composed of a plurality of triangles;

using said computer processor to determine if there is a significant point that exists among said plurality of points contained within an x, y extent of each said triangle;

updating said TIN with said computer processor to include said initial set of points and any significant points determined to exist within said plurality of triangles; and

repeating said determining and said updating steps until there are no significant points found within said triangles.

2. The method according to claim 1 wherein said determining step further comprises identifying a point as a significant point only if it has a z coordinate value that deviates from a plane of said triangle within which the x, y position of said point is contained, by an amount which is greater than or equal to all other of said plurality of points within said x, y extent of said triangle.

3. The method according to claim 2 wherein said determining step further comprises identifying a point as a significant point only if it has a z coordinate value that deviates from a plane of said triangle within which the x, y position of said point is contained, by an amount exceeding an allowable vertical error (AVE) limit.

4. The method according to claim 1, further comprising calculating a root mean square error (RMSE) for said point cloud data based on a plurality of control points which comprise more accurate measurements, as compared to said point cloud data, of z coordinate values at locations within the x, y extent of said point cloud.

5. The method according to claim 4, further comprising calculating with said computer processor a vertical error value for said TIN based on said RMSE value, and a standard score corresponding to a user selected portion of said point cloud that is used to form said TIN.

6. The method according to claim 4, further comprising using said computer processor to determine a portion of said point cloud data that is necessary to form said TIN based on said RMSE value and a user selected allowable vertical error (AVE) value for said TIN.

7. The method according to claim 4, further comprising generating with said computer processor a table including a plurality of allowable vertical error values for said TIN and a corresponding plurality of portion values, each of said plurality of portion values specifying a portion of said point cloud data necessary to provide said TIN with respective ones of said plurality of allowable vertical error values based on said RMSE.

8. The method according to claim 7, further comprising generating said TIN based on a portion value determined in accordance with a user selected one of said allowable vertical error values presented in said table.

9. The method according to claim 1, said updating step further comprising using said computer processor to apply a Delaunay constraint to said TIN.

10. The method according to claim 1, wherein said point cloud data represents a terrain and said z coordinate represents an elevation of said terrain.

11. The method according to claim 1, comprising thinning said point cloud data by using said computer processor to exclude from a final data set any of said plurality of points that are not included in at least one of said initial set of points and said significant points.

12. The method according to claim 1, further comprising:

determining a relative significance value for each of said plurality of points in said point cloud, said relative significance value determined based on a deviation of each said point from said mean z coordinate value; and

storing said plurality of points in an ordered database having an order defined by said relative significance values.

13. The method according to claim 12, further comprising selecting a portion of said plurality of points for use in forming said TIN, said portion defined as a sub-set of said points in said ordered database having a range of relative significance values determined in accordance with a user selection.

14. A system for deriving significant points from a point cloud containing data representing a surface and defined within a three dimensional coordinate system, comprising a computer processor configured for performing the steps of:

calculating a mean z coordinate value for a plurality of points having x, y and z coordinates within said three-dimensional coordinate systems;

selecting from said point cloud data, an initial set of points having z coordinate values which deviate from said mean by at least an initial value;

constructing a triangulated irregular network (TIN) using said initial set of points, said TIN composed of a plurality of triangles;

determining if there is a significant point that exists among said plurality of points contained within an x, y extent of each said triangle;

updating said TIN to include said initial set of points and any significant points determined to exist within said plurality of triangles;

repeating said determining and said updating steps until there are no significant points found within said triangles.

15. The system according to claim 14 wherein said determining step further comprises identifying a point as a significant point only if it has a z coordinate value that deviates from a plane of said triangle within which the x, y position of said point is contained, by an amount which is greater than or equal to all other of said plurality of points within said x, y extent of said triangle.

16. The system according to claim 15 wherein said determining step further comprises identifying a point as a significant point only if it has a z coordinate value that deviates from a plane of said triangle within which the x, y position of said point is contained, by an amount exceeding an allowable vertical error (AVE) limit.

17. The system according to claim 14, wherein said computer processor is further configured to calculate a root mean square error (RMSE) for said point cloud data based on a plurality of control points which comprise more accurate measurements, as compared to said point cloud data, of z coordinate values at locations within the x, y extent of said point cloud.

18. The system according to claim 17, wherein said computer processor is further configured to calculate a vertical error value for said TIN based on said RMSE value, and a standard score corresponding to a user selected portion of said point cloud that is used to form said TIN.

19. The system according to claim 17, wherein said computer processor is further configured to determine a portion of said point cloud data that is necessary to form said TIN based on said RMSE value and a user selected allowable vertical error (AVE) value for said TIN.

20. The system according to claim 17, wherein said computer processor is further configured to generate a table including a plurality of allowable vertical error values for said TIN and a corresponding plurality of portion values, each of said plurality of portion values specifying a portion of said point cloud data necessary to provide said TIN with respective ones of said plurality of allowable vertical error values based on said RMSE.

21. The system according to claim 20, wherein said computer processor is further configured to generate said TIN based on a portion value determined in accordance with a user selected one of said allowable vertical error values presented in said table.

22. The system according to claim 14, wherein said updating step further comprising applying a Delaunay constraint to said TIN.

23. The system according to claim 14, wherein said point cloud data represents a terrain and said z coordinate represents an elevation of said terrain.

24. The system according to claim 14, wherein said computer processor is further configured to thin said point cloud data by excluding from a final data set any of said plurality of points that are not included in at least one of said initial set of points and said significant points.

25. The system according to claim 14, wherein said computer processor is further configured to:

determine a relative significance value for each of said plurality of points in said point cloud, said relative significance value determined based on a deviation of each said point from said mean z coordinate value; and

store said plurality of points in an ordered database having an order defined by said relative significance values.

26. The system according to claim 25, wherein said computer processor is further configured to select a portion of said plurality of points for use in forming said TIN, said portion defined as a sub-set of said points in said ordered database having a range of relative significance values determined in accordance with a user selection.

27. A machine-readable storage device having stored thereon sequences of instructions that, when executed by a machine, cause the machine to perform actions which derive significant points from a point cloud containing data representing a physical surface and defined within a three dimensional coordinate system, the actions comprising:

calculating a mean z coordinate value for a plurality of points having x, y and z coordinates within said three-dimensional coordinate systems;

using said computer processor to select from said point cloud data, an initial set of points having z coordinate values which deviate from said mean by at least an initial value;

constructing with said computer processor a triangulated irregular network (TIN) using said initial set of points, said TIN composed of a plurality of triangles;

using said computer processor to determine if there is a significant point that exists among said plurality of points contained within an x, y extent of each said triangle;

updating said TIN with said computer processor to include said initial set of points and any significant points determined to exist within said plurality of triangles; and

repeating said determining and said updating steps until there are no significant points found within said triangles.