Capturing and aligning multiple 3-dimensional scenes

• US 8,879,828 B2
• Filed: 06/29/2012
• Issued: 11/04/2014
• Est. Priority Date: 06/29/2011
• Status: Active Grant

• Current Assignee: Matterport, Inc
• Original Assignee: Matterport, Inc
• Inventors: Bell, Matthew, Gausebeck, Dave
• Primary Examiner(s): Desire, Gregory M
• Application Number:
  US13/539,252
• Publication Number:
  US 20130004060A1
• Time in Patent Office: 858 Days
• Field of Search: 345/420, 345/630, 382/154
• US Class Current: 382/154
• CPC Class Codes: G01S 17/86 Combinations of lidar systems with systems other than lidar, radar or sonar, e.g. with direction finders
• CPC Class Codes: G01S 17/89 for mapping or imaging
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 19/20 Editing of 3D images, e.g. changing shapes or colours, aligning objects or positioning parts
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20221 Image fusion; Image merging
• CPC Class Codes: G06T 2219/2004 Aligning objects, relative positioning of parts
• CPC Class Codes: G06T 2219/2012 Colour editing, changing, or manipulating; Use of colour codes
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06T 7/38 Registration of image sequences
• CPC Class Codes: H04N 13/204 using stereoscopic image cameras stereoscopic photography G03B35/00
• CPC Class Codes: H04N 13/257 Colour aspects
• CPC Class Codes: H04N 13/271 wherein the generated image signals comprise depth maps or disparity maps

Abstract

The capture and alignment of multiple 3D scenes is disclosed. Three dimensional capture device data from different locations is received thereby allowing for different perspectives of 3D scenes. An algorithm uses the data to determine potential alignments between different 3D scenes via coordinate transformations. Potential alignments are evaluated for quality and subsequently aligned subject to the existence of sufficiently high relative or absolute quality. A global alignment of all or most of the input 3D scenes into a single coordinate frame may be achieved. The presentation of areas around a particular hole or holes takes place thereby allowing the user to capture the requisite 3D scene containing areas within the hole or holes as well as part of the surrounding area using, for example, the 3D capture device. The new 3D captured scene is aligned with existing 3D scenes and/or 3D composite scenes.

Claims

1. A method, comprising:

receiving, by a system comprising a processor, three dimensional data for a plurality of three dimensional scenes, the three dimensional data comprising geometric information for features respectively included in the three dimensional scenes;

generating, by the system, a plurality of alignment schemes between two or more of the plurality of three dimensional scenes based on the three dimensional data using a spatial transformation;

evaluating, by the system, the plurality of alignment schemes based on quality of alignment of the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes; and

selecting, by the system, an alignment scheme of the plurality of alignment schemes associated with a higher quality of alignment with respect to other alignment schemes of the plurality of alignment schemes.

2. The method of claim 1, further comprising:

generating, by the system, a composite three dimensional scene based on the alignment scheme using the two or more of the plurality of three dimensional scenes, wherein the composite three dimensional scene comprises a merged set of features based on combined features of the two or more of the plurality of three dimensional scenes.

3. The method of claim 2, the method further comprising:

generating, by the system, new alignment schemes between the composite three dimensional scene and one or more other three dimensional scenes of the plurality of three dimensional scenes based on the three dimensional data and geometric information for the merged set of features.

4. The method of claim 3, further comprising:

evaluating, by the system, the new alignment schemes based on quality of alignment of the composite three dimensional scene and the one or more other three dimensional scenes as aligned with respect to each of the new alignment schemes;

selecting, by the system, a new alignment scheme of the new alignment schemes associated with a higher quality of alignment with respect to other new alignment schemes of the new alignment schemes; and

generating, by the system, a new composite three dimensional scene based on the new alignment scheme using the composite three dimensional scene and the one or more other three dimensional scenes.

5. The method of claim 1, wherein the three dimensional data further comprises appearance information for the features respectively included in the three dimensional scenes, and wherein the evaluating the plurality of alignment schemes comprises comparing geometric information and appearance information for features included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes.

6. The method of claim 5, wherein the evaluating the plurality of alignment schemes further comprises:

determining quality of alignment scores for the plurality of alignment schemes, respectively, based on the comparing, and wherein the selecting the alignment scheme comprises selecting the alignment scheme based in part on a quality of alignment score associated therewith.

7. The method of claim 6, wherein the determining the quality of alignment scores comprises determining the quality of alignment scores based on consideration of existence of known empty space in the two or more of the plurality of three-dimensional scenes.

8. The method of claim 6, wherein the determining the quality of alignment scores comprises determining the quality of alignment scores based on types of the features included in the two or more of the plurality of three dimensional scenes.

9. The method of claim 6, wherein the selecting the alignment scheme comprises selecting the alignment scheme based on association of the alignment scheme with a quality of alignment score above a threshold value.

10. The method of claim 6, wherein the determining the quality of alignment scores comprises determining the quality of alignment scores based on similarities in geometric location and physical appearance of the features respectively included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes.

11. The method of claim 6, wherein the determining the quality of alignment scores comprises determining the quality of alignment scores based on at least one of:

similarity in position of the features included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes,

similarity of luminous intensity of the features included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes,

similarity of color of the features included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes,

similarity of distribution of local normal vectors of the features included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment schemes, or

similarity of local curvature of the features included in the two or more of the plurality of three dimensional scenes as aligned with respect to each of the plurality of alignment scheme.

12. The method of claim 1, further comprising, applying a local optimization process to one or more of the plurality of alignment schemes that improves the quality of the alignment of the two or more of the plurality of three dimensional scenes.

13. The method of claim 1, further comprising, applying a non-rigid alignment process following the generating the plurality of alignment schemes.

14. The method of claim 1, further comprising:

receiving, by the system, orientation information of a device that captured the three dimensional data for the plurality of three dimensional scenes; and

generating, by the system, the plurality of alignment schemes based on the orientation information.

15. The method of claim 1, further comprising:

receiving, by the system, position information of a device that captured the three dimensional data for the plurality of three dimensional scenes; and

generating, by the system, the plurality of alignment schemes based on the position information.

16. The method of claim 1, further comprising, rejecting alignment schemes of the plurality of alignment schemes that fail to surpass a quality of alignment threshold.

17. The method of claim 1, wherein the generating the plurality of alignment schemes comprises matching first points or regions of one of the plurality of the three dimensional scenes with second points or regions of another one of the plurality of three dimensional scenes based on similarity in at least one of appearance or geometric location of features respectively included in the first and second points or regions.

18. The method of claim 17, further comprising:

selecting the first points or regions based on inclusion of distinctive features relative to other features of the one of the plurality of three dimensional scenes.

19. The method of claim 1, wherein the plurality of three dimensional scenes correspond to different perspectives of a physical environment captured from one or more capture devices at different locations.

20. A system, comprising:

a memory to store executable instructions; and

a processor, coupled to the memory, that facilitates execution of the executable instructions to perform operations, comprising;

generating alignment schemes between two or more three dimensional scenes of a plurality of three dimensional scenes of a physical space based in part on positions of data points respectively associated with the two or more three dimensional scenes;

determining scores for the alignment schemes, respectively, based on quality of alignment of the two or more three dimensional scenes as aligned based on each of the alignment schemes; and

selecting an alignment scheme of the alignment schemes based in part on association of the alignment scheme with a higher score with respect to other ones of the alignment schemes.

21. The system of claim 20, wherein the operations further comprise:

generating a composite three dimensional scene based on the alignment scheme using the two or more three dimensional scenes.

22. The system of claim 20, wherein the generating the alignment schemes comprises identifying correlations between the data points based on the positions of the data points relative to one another.

23. The system of claim 20, wherein the determining the scores comprises, for each of the alignment schemes, scoring the alignment schemes based on correlations between the positions of the data points relative to one another.

24. The system of claim 20, wherein the operations further comprise:

generating the alignment schemes between the two or more three dimensional scenes based in part on appearance information respectively associated with the data points.

25. The system of claim 24, wherein the determining the scores comprises, for each of the alignment schemes, scoring the alignment schemes based on correlations between the data points based on the appearance information.

26. The system of claim 20, wherein the determining the scores comprises scoring the alignment schemes based on consideration of existence of known empty space in the two or more three dimensional scenes.

27. The system of claim 20, wherein the selecting the alignment scheme comprises selecting the alignment scheme based on association of the alignment scheme with a score above a threshold value.

28. The system of claim 20, wherein the generating the alignment schemes comprises selecting the two or more three dimensional scenes based on correlations between the positions of the data points relative to one another and appearance information respectively associated with the data points.

29. The system of claim 20, wherein the generating the alignment schemes comprises matching first points or regions of one of the plurality of the three dimensional scenes with second points or regions of another one of the plurality of three dimensional scenes based on similarity in position or appearance of features respectively included in the first and second points or regions.

30. The system of claim 29, wherein the operations further comprise:

selecting the first points or regions based on inclusion of distinctive features relative to other features of the one of the plurality of three dimensional scenes.

31. The system of claim 20, wherein the operations further comprise:

receiving orientation information identifying orientations of a device that captured the plurality of three dimensional scenes at respective times the device captured the three dimensional scenes; and

generating the alignment schemes based on the orientation information.

32. The system of claim 20, wherein the operations further comprise:

receiving position information identifying positions of a device that captured the plurality of three dimensional scenes at respective times the device captured the three dimensional scenes; and

generating the alignment schemes based on the position information.

33. The system of claim 20, wherein the plurality of three dimensional scenes corresponds to different perspectives of the physical space.

34. The system of claim 33, wherein the different perspectives of the physical space are captured from one or more capture devices at different locations.

35. A computer-readable storage device comprising executable instructions that, in response to execution, cause a device comprising a processor to perform operations comprising:

generating alignment schemes between two or more three dimensional scenes of a plurality of three dimensional scenes of a physical space based on geometric information and appearance information for features respectively associated with the two or more three dimensional scenes;

determining scores for the alignment schemes, respectively, based on quality of alignment of the two or more three dimensional scenes as aligned based on each of the alignment schemes; and

selecting an alignment scheme of the alignment schemes based in part on association of the alignment scheme with a higher score with respect to other ones of the alignment schemes.

36. The computer-readable storage device of claim 35, the operations further comprising:

generating a composite three dimensional scene based on the alignment scheme using the two or more three dimensional scenes.

37. The computer-readable storage device of claim 35, wherein the generating the alignment schemes comprises identifying correlations between the features based on the geometric information and the appearance information.

38. The computer-readable storage device of claim 35, wherein the determining the scores comprises, for each of the alignment schemes, scoring the alignment schemes based on correlations between the features based on the geometric information and the appearance information.

39. The computer-readable storage device of claim 35, wherein the determining the scores comprises scoring the alignment schemes based on weights associated with different types of the features, respectively.

40. The computer-readable storage device of claim 39, wherein background features are afforded a lower weight than foreground features.

41. The computer-readable storage device of claim 35, wherein the determining the scores comprises scoring the alignment schemes based on consideration of existence of known empty space in the two or more three dimensional scenes.

42. The computer-readable storage device of claim 35, wherein the selecting the alignment scheme is based on association of the alignment scheme with a score above a threshold value.

43. The computer-readable storage device of claim 35, wherein the generating the alignment schemes comprises selecting the two or more three dimensional scenes based on correlations between the features based on the geometric information and the appearance information respectively associated with the features.

44. The computer-readable storage device of claim 35, wherein the generating the alignment schemes comprises matching first points or regions of one of the plurality of the three dimensional scenes with second points or regions of another one of the plurality of three dimensional scenes based on similarity in position or appearance of features respectively included in the first and second points or regions.

45. The computer-readable storage device of claim 44, the operations further comprising:

selecting the first points or regions based on inclusion of distinctive features relative to other features of the one of the plurality of three dimensional scenes.

46. The computer-readable storage device of claim 35, the operations further comprising:

receiving orientation information identifying orientations of a device that captured the plurality of three dimensional scenes at respective times the device captured the three dimensional scenes; and

generating the alignment schemes based on the orientation information.

47. The computer-readable storage device of claim 35, the operations further comprising:

receiving position information identifying positions of a device that captured the plurality of three dimensional scenes at respective times the device captured the three dimensional scenes; and

generating the alignment schemes based on the position information.