Identification of 3D surface points using context-based hypothesis testing

• US 20050216237A1
• Filed: 03/08/2005
• Published: 09/29/2005
• Est. Priority Date: 03/10/2004
• Status: Active Grant

• Current Assignee: Leica Geosystems AG (Hexagon AB)
• Original Assignee: Leica Geosystems AG (Hexagon AB)
• Inventors: Wheeler, Mark Damon, Bukowski, Richard William, Kung, Jonathan Apollo, Adachi, Jeffrey Minoru, Downs, Laura Michele
• Granted Patent: US 7,643,966 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

Abstract

A computer model of a physical structure (or object) can be generated using context-based hypothesis testing. For a set of point data, a user selects a context specifying a geometric category corresponding to the structure shape. The user specifies at least one seed point from the set that lies on a surface of the structure of interest. Using the context and point data, the system loads points in a region near the seed point(s), and determines the dimensions and orientation of an initial surface component in the context that corresponds to those points. If the selected component is supported by the points, that component can be added to a computer model of the surface. The system can repeatedly find points near a possible extension of the surface model, using the context and current surface component(s) to generate hypotheses for extending the surface model to these points. Well-supported components can be added to the surface model until the surface of the structure of interest has been modeled as far as is well-supported by the point data.

Claims

1. A method of modeling a physical structure, comprising the steps of:

allowing a user to select a context, corresponding to the physical structure, and at least one seed point from a set of point data corresponding to a surface of the structure;

using the context to select local points near the at least one seed point and determine dimensions and orientation of an initial surface component that models the local points, the initial surface component being added to a working model of the physical structure; and

using the context to determine a set of extension points near an area of possible extension of the initial surface component.

2. A method according to claim 1, further comprising:

using the context and the initial surface component to determine a set of extension hypotheses to be tested against the set of extension points to determine any additional surface components to be added to the working model.

3. A method according to claim 2, further comprising:

adding the additional surface components to the working model until a final model of the structure is generated.

4. A method according to claim 3, further comprising:

adjusting the initial surface component and any other model components to correspond to the additional surface components.

5. A method according to claim 1, further comprising:

displaying the set of point data to the user.

6. A method according to claim 3, further comprising:

displaying the working model to the user and updating the working model after the addition of the initial surface component and any additional surface component.

7. A method according to claim 1, further comprising:

allowing the user to specify the type of the initial surface component corresponding to the at least one seed point.

8. A method according to claim 1, further comprising:

allowing the user to interrupt the modeling method at any time.

9. A method according to claim 1, further comprising:

obtaining the set of point data corresponding to the physical structure.

10. A method according to claim 9, wherein:

the step of obtaining the set of point data includes using a scanning LIDAR system to capture the set of point data.

11. A method according to claim 9, wherein:

the step of obtaining point data includes combining data from multiple sources including at least one of LIDAR scanners, Global Positioning System (GPS), photogrammetry, mechanical digitizers, and 3-D point data sources.

12. A method according to claim 1, wherein:

the context selected by the user includes information selected from the group consisting of a set of possible surface components, rules for component connections, rules for component extensions, and ranges of allowed dimensions.

13. A method according to claim 3, further comprising:

saving the final model to a database.

14. A method according to claim 3, further comprising:

displaying the final model to the user.

15. A method according to claim 3, further comprising:

displaying a description of the final model to the user, the description containing a list of surface component types, as well as corresponding positions, orientations, and dimensions.

16. A method according to claim 1, further comprising:

using spatial queries to locate the adjacent points near the at least one seed point.

17. A method according to claim 2, further comprising:

using a random sample consensus approach to determine the initial surface component and any additional surface components.

18. A method according to claim 1, further comprising:

using spatial queries to locate the set of extension points.

19. A method according to claim 2, further comprising:

allowing the density of points used to determine the additional components to be limited based on the scale of the initial surface component and any additional surface components.

20. A method according to claim 1, further comprising:

allowing the user to modify the context by at least one of specifying new surface components and removing existing surface components from the context.

21. A method according to claim 1, wherein:

the context includes surface components selected from the group consisting of elbows, straight pipe, tees, flanges, reducers, valves, square tiles, and elongated planks.

22. A method according to claim 1, wherein:

.

the context includes rules for connecting surface components.

23. A method according to claim 22, wherein:

the rules for connection include rules selected from the group consisting of co-axial connections, common diameter connections, coplanar connections, and orthogonal connections.

24. A method according to claim 2, wherein:

the set of extension hypotheses includes hypotheses selected from the group consisting of coplanar adjacent tiles, occlusions followed by coplanar floor tiles, perpendicular wall tiles defining either walls or ledges, an end hypothesis, a continuing straight tube, an elbow, a tee, and a wall tile.

25. A method according to claim 1, wherein:

the set of points includes points that lie on more than one surface.

26. A method of modeling a physical structure, comprising the steps of:

obtaining a set of point data corresponding to the physical structure;

allowing a user to select a context, corresponding to the physical structure, and at least one seed point from the set of point data;

selecting an initial surface component that models point data near the at least one seed point, the initial surface component being added to a working model of the physical structure; and

iteratively adding additional surface components to the working model by using the context to determine a set of extension points near an area of possible extension of the working model, the context, initial surface component, and any additional surface components being used to determine a set of component hypotheses for extending the surface, the set of extension hypotheses being tested against the set of extension points whereby supported components are added to the working model, the initial surface component and any additional surface components of the working model being adjusted to correspond to the newly added supported components.

27. A method according to claim 26, wherein:

the set of point data is obtained from laser scan data

28. A method according to claim 26, wherein:

the step of obtaining the set of point data includes combining data from multiple sources including one or more of LIDAR scanners, Global Positioning System (GPS), photogrammetry, mechanical digitizers, or 3-D point data sources.

29. A method according to claim 26, wherein:

the step of selecting the initial surface component includes using a spatial query to form a set of local points near the seed point, testing each component in the selected context against the local points, and selecting the surface component that best models the local points.

30. A method according to claim 26, wherein:

the step of selecting the initial surface component includes allowing the user to select the initial component from the context, using a spatial query to form a set of local points near the seed point, and determining the position, orientation, and dimensions of the surface component that best models the local points.

31. A computer program product for modeling a physical structure, the computer program product comprising:

computer readable program code for allowing a user to select a context corresponding to the physical structure;

computer readable program code for selecting at least one seed point from a set of point data corresponding to a surface of the structure;

computer readable program code for using local points near the at least one seed point to determine dimensions and orientation of an initial surface component that models the local points, and adding the initial surface component to a working model of the physical structure;

computer readable program code for iteratively adding additional surface components to the working model, each iteration using the context to determine a set of extension points near an area of possible extension of the working model, the context, initial surface component, and any additional surface components being used to determine a set of component hypotheses for extending the surface, the set of extension hypotheses being tested against the set of extension points such that supported surface components are added to the working model, the initial surface component and any additional components of the working model being adjusted to correspond to newly added supported surface components, until a final model of structure is generated.

32. A system for modeling a physical structure, comprising:

a database containing a set of surface contexts, each surface context containing a list of potential surface components;

a user interface in communication with the database and allowing a user to select a context from the set of surface contexts, corresponding to the physical structure, and at least one seed point, from a set of point data corresponding to a surface of the structure;

a processing station operable to receive the selected context and at least one seed point from the user interface, the processing station further operable to;

use adjacent points near the at least one seed point to determine dimensions and orientation of an initial surface component that forms a working model of the adjacent points; and

iteratively adding additional surface components to the working model, each iteration using the context to determine a set of extension points near an area of possible extension of the working model, the context, initial surface component, and any additional surface components being used to determine a set of component hypotheses for extending the surface, the set of extension hypotheses being tested against the set of extension points such that supported surface components are added to the working model, the initial surface component and any additional components of the working model being adjusted to correspond to newly added supported surface components until a final model of structure is generated.

33. A system according to claim 32, wherein:

the user interface is operable to display the set of point data to the user.

34. A system according to claim 32, wherein:

the user interface is operable to display the working model to the user and update the working model after the addition of the initial surface component and any additional surface component.

35. A system according to claim 32, wherein:

the user interface is operable to allow the user to specify the type of the initial surface component corresponding to the at least one seed point.

36. A system according to claim 32, wherein:

the user interface is operable to allow the user to interrupt the modeling method at any time.

37. A system according to claim 32, wherein:

the processing station is operable to obtain the set of point data corresponding to the physical structure.

38. A system according to claim 32, further comprising:

a scanning LIDAR system in communication with the processing station and operable to capture the set of point data.

39. A system according to claim 32, wherein:

the processing station is operable to save the final model to a database.

40. A system according to claim 32, wherein:

the user interface is operable to display the final model to the user.

41. A system according to claim 32, wherein:

the user interface is operable to display a description of the final model to the user, the description containing a list of surface component types, as well as corresponding positions, orientations, and dimensions.

42. A system according to claim 32, wherein:

the processing station is operable to use spatial queries to locate the adjacent points near the at least one seed point.

43. A system according to claim 32, wherein:

the processing station is operable to use a random sample consensus approach to determine the initial surface component and any additional surface components.

44. A system according to claim 32, wherein:

the processing station is operable to use spatial queries to locate the set of extension points.

45. A system according to claim 32, wherein:

the processing station is operable to allow the density of points from the set of points, used to determine the additional components, to be limited based on the scale of the initial surface component.

46. A system according to claim 32, wherein:

the user interface is operable to allow the user to modify the context by at least one of specifying new surface components and removing existing surface components from the context.

47. A method of modeling a physical structure, comprising the steps of:

scanning the physical structure to acquire a set of point data corresponding to the physical structure;

displaying the set of point data to a user and allowing a user to select a context, corresponding to the physical structure, and at least one seed point, from a set of point data corresponding to a surface of the structure;

using the context to select local points near the at least one seed point and determine dimensions and orientation of an initial surface component that models the adjacent points, the initial surface component being added to a working model of the physical structure;

using the context to determine a set of extension points near an area of possible extension of the initial surface component;

using the surface model and the context to determine a set of hypotheses for extending the surface, the set of hypotheses being tested against the set of extension points to determine any supported surface components to be added to the working model; and

adding supported surface components to the working model and adjusting the initial surface component and any other model components to correspond to the newly added supported surface components until a final model of the structure is generated.

48. A method according to claim 47, wherein:

the physical structure is scanned using at least one of LIDAR scanning, GPS, photogrammetry, mechanical digitizers, and 3-D point data sources.