Apparatus and method for point cloud assembly

• US 6,701,006 B2
• Filed: 06/26/2002
• Issued: 03/02/2004
• Est. Priority Date: 06/26/2002
• Status: Expired due to Term

• Current Assignee: NextPat Limited
• Original Assignee: NextEngine, Inc.
• Inventors: Knighton, Mark S., Gao, Peisheng, Moore, Ronald W.
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US10/183,735
• Publication Number:
  US 20040001620A1
• Time in Patent Office: 615 Days
• Field of Search: 382/154, 382/282, 382/284, 382/294, 345/419, 345/427, 345/629, 345/630, 345/634
• US Class Current: 382/154
• CPC Class Codes: G06T 2200/04 involving 3D image data
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A method and apparatus for point cloud assembly are described. In one embodiment, the method includes the obtaining of a data set of a first point cloud and a data set of a second point cloud. Once obtained, a portion of geometry defined by each respective data set is identified, which substantially describes a similar geometric shape. Next, a transformation is computed, such that the portion of geometry in each data set aligns to substantially minimize alignment error. Finally, the computed transformation is applied to the first point cloud to register the first point cloud relative to the second point cloud. In one embodiment, identification of the geometric portion describing a substantially similar geometric shape may be performed utilizing geometric reference point information, image texture information or a combination thereof.

Claims

1. A method comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error;

applying the transformation to the first point cloud to register it relative to the second point cloud;

obtaining a data set of at least a third point cloud;

assigning one of the point clouds to be an anchor; and

applying a transformation to each other print cloud to register it relative to the anchor.

2. The method of claim 1 wherein:

each other point cloud is registered relative to the anchor by applying a single transformation.

3. The method of claim 1 wherein computing comprises:

generating values for a relative rotation of a portion of the identified geometry within the first and second point clouds respectively.

4. The method of claim 3 wherein computing comprises:

constructing a rotation matrix for the portion of geometry defined by each respective data set which describes the substantially similar geometric shape.

5. The method of claim 1 wherein computing comprises:

identifying a relative scale factor between a portion of the identified geometry within the first and second point clouds respectively.

6. The method of claim 1 wherein computing comprises:

generating values for a relative translation of a portion of the identified geometry within the first and second point cloud respectively.

7. The method of claim 1 wherein computing the transformation comprises:

calculating a geometric mean of a spatial distribution of the identified portion of geometry of at least one point cloud.

8. The method of claim 1 wherein computing the transformation comprises:

calculating a centroid of a spatial distribution of the identified portion of geometry of at least one point cloud.

9. The method of claim 1 wherein computing the transformation comprises:

combining calculations for a relative rotation, scale and translation of the identified portion of geometry of first and second point clouds respectively.

10. The method of claim 1 wherein the first and the second point clouds represent portions of a single physical object.

11. A method comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error;

apply the transformation to the first point cloud to register it relative to the second point cloud;

determining a cumulative relative misalignment of the first point cloud and the nth point cloud that results from successively aligning a plurality of point clouds where an nth point cloud joins with the first point cloud; and

adjusting the alignment of at least one preceding point cloud to compensate for the cumulative relative misalignment.

12. A method comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes substantially similar geometric shape;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error;

applying the transformation to the first point cloud to resister it relative to the second point cloud;

obtaining images containing texture corresponding to each of the point clouds;

identifying a portion of the texture associated with each respective data set that represents substantially the same surface;

computing an additional transformation of the first and second data sets such that the portions of texture associated with each data set align to substantially minimize texture alignment error; and

adjusting the transformation based on the additional transformation to improve registration of the first point cloud relative to the second point cloud.

13. A method comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error;

applying the transformation to the first point cloud to register it relative to the second point cloud;

obtaining a spatial relation of a portion of the data sets with respect to each other; and

bounding a range of possible solutions for the transformation according to what is known from the spatial relation.

14. A method comprising:

obtaining a data set of first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape including obtaining a spatial relation of an image capture device which captured at least one of the data sets with respect to an object represented in the data sets and bounding a range of possible solutions for the transformation according to what is known from the spatial relation;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error; and

applying the transformation to the first point cloud to register it relative to the second point cloud.

15. A method comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape including obtaining a spatial relation of an image capture device which captured at least one of the data sets with respect to an object represented in the data sets, and identifying an overlapping region according to what is known from the spatial relation;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error; and

applying the transformation to the first point cloud to register it relative to the second point cloud.

16. A method comprising:

obtaining an image containing texture for a portion of an object;

obtaining a data set of a first point cloud and a data set of a second point cloud corresponding to the portion of the object;

identifying a portion of the texture associated with each respective data set that represents substantially a same surface;

computing a relative transformation of the first and second data sets such that the portions of texture associated with each data set align to substantially minimize texture alignment error;

inferring a geometric transformation consistent with the texture transformation; and

applying the geometric transformation to the first point cloud to register it relative to the second point cloud.

17. The method of claim 16, further comprising:

obtaining a data set of at least a third point cloud;

assigning one of the point clouds to be an anchor;

applying a transformation to each other point cloud to register it relative to the anchor.

18. The method of claim 17 wherein:

each other point cloud is registered relative to the anchor by applying a single transformation.

19. The method of claim 16 wherein computing comprises:

generating values for a relative translation of the texture associated with each respective data set.

20. The method of claim 16 wherein computing comprises:

generating values for a relative rotation of the texture associated with each respective data set.

21. The method of claim 16 wherein computing comprises:

identifying a relative scale factor between the textures associated with each respective data set.

22. The method of claim 16 further comprising:

successively aligning a plurality of texture regions wherein an nth texture region joins with the textures associated with the first data set;

determining a cumulative relative misalignment of the texture associated with the first data set and the nth texture region; and

adjusting the alignment of at least one preceding texture region to compensate for a cumulative relative misalignment.

23. The method of claim 16 further comprising:

obtaining a spatial relation of a portion of the texture associated with the data sets with respect to each other; and

bounding a range of possible solutions for the transformation according to what is known from the spatial relation.

24. The method of claim 16 further comprising:

obtaining a spatial relation of an image capture device which captured at least one of the textures associated with the data sets with respect to an object represented in the textures; and

bounding a range of possible solutions for the transformation according to what is known from the spatial relation.

25. A method comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape;

computing a relative geometric transformation such that the portion of geometry in each respective data set align to substantially minimize alignment error;

obtaining an image containing texture for the portion of geometry in each respective data set;

identifying a portion of the texture associated with each respective data set that represents substantially a same surface;

computing a relative texture transformation of the first and second data sets such that the portions of texture associated with each data set align to substantially minimize texture alignment error;

adjusting the geometric transformation based on the texture transformation; and

applying the adjusted geometric transformation to the first point cloud to register it relative to the second point cloud.

26. A computer readable storage medium including program instructions that direct a computer to perform one or more operations when executed by a processor, the one or more operations comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape;

computing a transformation such that the portion of geometry in each data set align to substantially minimize alignment error;

applying the transformation to the first point cloud to register it relative to the second;

obtaining a data set of at least a third pint cloud;

assigning one of the point clouds to be an anchor; and

applying a transformation to each other pint cloud to register it relative to the anchor.

27. A computer readable storage medium including program instructions that direct a computer to perform one or more operations when executed by a processor, the one or more operations comprising:

obtaining an image containing texture for a portion of an object;

obtaining a data set of a first point cloud and a data set of a second point cloud corresponding to the portion of the object;

identifying a portion of the texture associated with each respective data set that represents substantially a same surface;

computing a relative transformation of the first and second data sets such that the portions of texture associated with each data set align to substantially minimize texture alignment error;

inferring a geometric transformation consistent with the texture transformation; and

applying the transformation to the first point cloud to register it relative to the second point cloud.

28. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

obtaining a data set of at least a third point cloud;

assigning one of the point clouds to be an anchor;

applying a transformation to each other point cloud to register it relative to the anchor.

29. The computer readable storage media of claim 28 containing instructions which when executed cause a digital processing system to perform a method further comprising.

each other point cloud is registered relative to the anchor by applying a single transformation.

30. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

generating values for a relative translation of the texture associated with each respective data set.

31. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

generating values for a relative rotation of the texture associated with each respective data set.

32. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

identifying a relative scale factor between the textures associated with each respective data set.

33. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

successively aligning a plurality of texture regions wherein an nth texture region joins with the textures associated with the first data set;

determining a cumulative relative misalignment of the texture associated with the first data set and the nth texture region; and

adjusting the alignment of at least one preceding texture region to compensate for a cumulative relative misalignment.

34. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

obtaining a spatial relation of a portion of the texture associated with the data sets with respect to each other; and

bounding a range of possible solutions for the transformation according to what is known from the spatial relation.

35. The computer readable storage media of claim 27 containing instructions which when executed cause a digital processing system to perform a method further comprising:

obtaining a spatial relation of an image capture device which captured at least one of the textures associated with the data sets with respect to an object represented in the textures; and

bounding a range of possible solutions for the transformation according to what is known from the spatial relation.

36. A computer readable storage medium including program instructions that direct a computer to perform one or more operations when executed by a processor, the one or more operations comprising:

obtaining a data set of a first point cloud and a data set of a second point cloud;

identifying a portion of geometry defined by each respective data set which describes a substantially similar geometric shape;

computing a relative geometric transformation such that the portion of geometry in each respective data set align to substantially minimize alignment error;

obtaining an image containing texture for the portion of geometry in each respective data set;

identifying a portion of the texture associated with each respective data set that represents substantially a same surface;

computing a relative texture transformation of the first and second data sets such that the portions of texture associated with each data set align to substantially minimize texture alignment error;

adjusting the geometric transformation based on the texture transformation; and

applying the adjusted geometric transformation to the first point cloud to register it relative to the second point cloud.