Real-time structured light range scanning of moving scenes

• US 6,754,370 B1
• Filed: 08/14/2000
• Issued: 06/22/2004
• Est. Priority Date: 08/14/2000
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Inventors: Rusinkiewicz, Szymon M., Hall-Holt, Olaf A.
• Primary Examiner(s): Mariam, Daniel
• Assistant Examiner(s): Patel, Shefali
• Application Number:
  US09/639,716
• Time in Patent Office: 1,408 Days
• Field of Search: 382/106, 382/107, 382/154, 356/3-22, 356/3.01
• US Class Current: 382/106
• CPC Class Codes: G01B 11/25 by projecting a pattern, e.g. one or more lines, moiré fringes on the object G01B11/255 takes precedence ; image analysis for depth or shape recovery G06T7/50
• CPC Class Codes: G01C 3/00 Measuring distances in line of sight; Optical rangefinders tapes, chains or wheels for measuring length G01B3/00; active triangulation systems, i.e. using the transmission and reflection of electromagnetic waves other than radio waves, G01S17/48
• CPC Class Codes: G06T 7/521 from laser ranging, e.g. using interferometry; from the projection of structured light

Abstract

A method for range scanning consists of projecting a sequence of radiation patterns onto a scene, capturing images of the scene, determining correspondences between image features and projection pattern features, and computing a range image of the scene by triangulation of the correspondences. Novel projection patterns allow tracking of pattern features between images, so that range images can be computed for moving scenes in real time. Global assumptions about surface continuity or reflectivity of the scene are not required for successful range scanning. Projection patterns may be based on two-stripe codes, parallel stripes of bright and dark intensity. In two-stripe coded patterns, pattern features are the boundaries between stripes, which take on values of either on-on, on-off, off-on, or off-off. A particular boundary'"'"'s value over the entire pattern sequence defines its code, used to determine correspondences between the boundary image and its location in the projection pattern. The method is also useful for obtaining three-dimensional models of static objects. The object is slowly rotated while being imaged, and all resulting range images are aligned and merged to form the three-dimensional model. A system implementing the method can be mounted on a robot or vehicle for navigation in unknown environments.

Claims

1. A method for real-time range scanning of a scene, the method comprising:

a) projecting a sequence of N radiation patterns onto said scene, each radiation pattern comprising a set of pattern features at fixed projection positions, wherein the pattern features are boundaries in the radiation patterns, and wherein a sequence of N matching pattern features in a corresponding set of N of said radiation patterns defines a code for one of the fixed projection positions, wherein N is a minimum number of radiation patterns required to provide unique codes;

b) using an image detector, capturing a current image of said scene, wherein said current image comprises a set of current image features corresponding to said pattern features, and wherein the current image features are boundaries in the current image;

c) identifying matching image features in a distinct image, wherein the matching image features are boundaries in the distinct image matching at least one of the current image features;

d) determining current image feature positions for some of the current image features from said code, said current image and at least one differently-timed images; and

e) computing ranges for positions of said some of the current image features by geometrical analysis of said current image feature positions and said fixed projection positions.

2. The method of claim 1 wherein each fixed projection position has a unique code.

3. The method of claim 1 wherein said distinct image is a previous image corresponding to a preceding pattern.

4. The method of claim 1 wherein said code is determined from said current image and previous images corresponding to a multiplicity of preceding patterns.

5. The method of claim 1 wherein said code is determined from said current image and subsequent images corresponding to a multiplicity of succeeding patterns.

6. The method of claim 1 wherein said geometrical analysis comprises triangulation.

7. The method of claim 1 wherein said radiation patterns comprise acoustic radiation patterns.

8. The method of claim 1 wherein said radiation patterns comprise electromagnetic radiation patterns.

9. The method of claim 8 wherein said electromagnetic radiation patterns comprise radiation selected from the group consisting of visible light, infrared light, and x-ray radiation.

10. The method of claim 1 wherein said code is defined in part by changes in light intensity levels across said boundaries.

11. The method of claim 1 wherein said code is defined in part by changes in RGB values across said boundaries.

12. The method of claim 1 wherein said boundaries are stripe boundaries.

13. The method of claim 1 wherein said boundaries are uniformly spaced in said radiation patterns.

14. The method of claim 13 wherein said positions of said boundaries are in part determined by a resolution of said image detector.

15. The method of claim 1 wherein a difference between a position of one of said current image features and a position of a matching image feature is below a threshold distance.

16. The method of claim 1 further comprising estimating a spatially varying surface reflectivity of said scene.

17. The method of claim 1 further comprising selecting said radiation patterns in part in dependence on a computational efficiency of steps (c), (d), and (e).

18. The method of claim 1 wherein said radiation patterns comprise electrons.

19. The method of claim 1 wherein said boundaries comprise pixel boundaries between substantially uniform regions in said radiation pattern.

20. The method of claim 1 wherein said boundaries are pixel boundaries between individual pixels.

21. The method of claim 1 wherein said boundaries are boundaries between collections of pixels.

22. A program storage device accessible by a computer in communication with an image detector, said program storage device tangibly embodying a program of instructions executable by said computer to perform method steps for real-time range scanning of a scene, said method steps comprising:

a) receiving a current image of said scene from said image detector, wherein;

i) said scene is projected with a sequence of N radiation patterns, each radiation pattern comprising a set of pattern features at fixed projection positions, wherein the pattern features are boundaries in the radiation pattern, and wherein a sequence of N matching pattern features in a corresponding set of N of said radiation patterns defines a code for one of the fixed projection positions wherein N is a minimum number of radiation patterns required to provide unique codes; and

ii) said current image comprises a set of current image features corresponding to said pattern features wherein the current image features are boundaries in the current image;

b) identifying matching image features in a distinct image, wherein the matching image features are boundaries in the distinct image matching at least one of the current image features;

c) determining current image feature positions for some of the current image features, from said code, said current image and at least one differently-timed image; and

d) computing ranges for positions of said some of the current image features by geometrical analysis of said current image feature positions and said fixed projection positions.

23. The program storage device of claim 22 wherein said method steps further comprise instructing said projector to project said sequence of radiation patterns.

24. The program storage device of claim 22 wherein each fixed projection position has a unique code.

25. The program storage device of claim 22 wherein said distinct image is a previous image corresponding to a preceding pattern.

26. The program storage device of claim 22 wherein said code is determined from said current image and previous images corresponding to a multiplicity of preceding patterns.

27. The program storage device of claim 22 wherein said code is determined from said current image and subsequent images corresponding to a multiplicity of succeeding patterns.

28. The program storage device of claim 22 wherein said geometrical analysis comprises triangulation.

29. The program storage device of claim 22 wherein said radiation patterns comprise acoustic radiation patterns.

30. The program storage device of claim 22 wherein said radiation patterns comprise electromagnetic radiation patterns.

31. The program storage device of claim 30 wherein said electromagnetic radiation patterns comprise radiation selected from the group consisting of visible light, infrared light, and x-ray radiation.

32. The program storage device of claim 22 wherein said code is defined in part by changes in light intensity levels across said boundaries.

33. The program storage device of claim 22 wherein said code is defined in part by changes in RGB values across said boundaries.

34. The program storage device of claim 22 wherein said boundaries are stripe boundaries.

35. The program storage device of claim 22 wherein said boundaries are uniformly spaced in said radiation patterns.

36. The program storage device of claim 35 wherein said positions of said boundaries are in part determined by a resolution of said image detector.

37. The program storage device of claim 22 wherein a difference between a position of one of said current image features and a position of a matching image feature is below a threshold distance.

38. The program storage device of claim 22 wherein said method steps further comprise estimating a spatially varying surface reflectivity of said scene.

39. The program storage device of claim 22 wherein said method steps further comprise selecting said radiation patterns in part in dependence on a computational efficiency of steps (b), (c), and (d).

40. The program storage device of claim 22 wherein said boundaries comprise pixel boundaries between substantially uniform regions in said radiation pattern.

41. The program storage device of claim 22 wherein said boundaries are pixel boundaries between individual pixels.

42. The program storage device of claim 22 wherein said boundaries are boundaries between collections of pixels.

43. A real-time range scanning system comprising:

a) a projector configured to project a sequence of N radiation patterns onto a scene, each radiation pattern comprising a set of pattern features at fixed projection positions, wherein the pattern features are boundaries in the radiation pattern, and wherein a sequence of N matching pattern features in a corresponding set of N of said radiation patterns defines a code for one of the fixed projection positions, wherein N is a minimum number of radiation patterns required to provide unique codes;

b) an image detector for capturing a current image of said scene, wherein said current image comprises a set of current image features corresponding to said pattern features, and wherein the current image features are boundaries in the current image; and

c) a data processor in communication with said image detector, configured to;

i) identify matching image features in a distinct image, wherein the matching image features are boundaries in the distinct image matching at least one of the current image features;

ii) determine current image feature positions for some of the current image features, from said code, said current image and at least one differently-timed image; and

iii) compute ranges for positions of said some of the current image features by geometrical analysis of said current image feature positions and said fixed projection positions.

44. The range scanning system of claim 43 wherein said data processor is further configured to instruct said projector to project said sequence of radiation patterns.

45. The range scanning system of claim 43 wherein each fixed projection position has a unique code.

46. The range scanning system of claim 43 wherein said distinct image is a previous image corresponding to a preceding pattern.

47. The range scanning system of claim 43 wherein said code is determined from said current image and previous images corresponding to a multiplicity of preceding patterns.

48. The range scanning system of claim 43 wherein said code is determined from said current image and subsequent images corresponding to a multiplicity of succeeding patterns.

49. The range scanning system of claim 43 wherein said geometrical analysis comprises triangulation.

50. The range scanning system of claim 43 wherein said radiation patterns comprise acoustic radiation patterns.

51. The range scanning system of claim 43 wherein said radiation patterns comprise electromagnetic radiation patterns.

52. The range scanning system of claim 51 wherein said electromagnetic radiation patterns comprise radiation selected from the group consisting of visible light, infrared light, and x-ray radiation.

53. The range scanning system of claim 43 wherein said code is defined in part by changes in light intensity levels across said boundaries.

54. The range scanning system of claim 43 wherein said code is defined in part by changes in RGB values across said boundaries.

55. The range scanning system of claim 43 wherein said boundaries are stripe boundaries.

56. The range scanning system of claim 43 wherein said boundaries are uniformly spaced in said radiation patterns.

57. The range scanning system of claim 56 wherein said positions of said boundaries are in part determined by a resolution of said image detector.

58. The range scanning system of claim 43 wherein a difference between a position of one of said current image features and a position of a matching image feature is below a threshold distance.

59. The range scanning system of claim 43 wherein said data processor is further configured to estimate a spatially varying surface reflectivity of said scene.

60. The range scanning system of claim 43 wherein said data processor is further configured to select said radiation patterns in part in dependence on a computational efficiency of said data processor with respect to steps (i), (ii), and (iii).

61. The range scanning system of claim 43 wherein said radiation patterns comprise electrons.

62. The range scanning system of claim 43 wherein said boundaries comprise pixel boundaries between substantially uniform regions in said radiation pattern.

63. The range scanning system of claim 43 wherein said boundaries are pixel boundaries between individual pixels.

64. The range scanning system of claim 43 wherein said boundaries are boundaries between collections of pixels.

65. A method for real-time range scanning of a scene, the method comprising:

a) projecting a sequence of radiation patterns onto said scene, each radiation pattern comprising a set of parallel stripes defining projected pattern features at fixed projection positions, wherein the pattern features are stripe boundaries in the radiation patterns, wherein a sequence of N matching stripe boundaries at each fixed projection position in a set of N of said radiation patterns defines a code for said fixed projection position;

b) using an image detector, capturing a current image of said scene, wherein said current image comprises a set of image stripe boundaries corresponding to said projected stripe boundaries;

c) identifying each current image stripe boundary with a matching image stripe boundary in a previous image;

d) determining fixed projection positions for some of the image stripe boundaries from said code, said current image and at least one preceding images, thereby identifying a fixed projection position corresponding to some of the current image stripe boundaries; and

e) computing ranges for said some of the current image stripe boundaries by geometrical analysis of said current image stripe boundary and said corresponding fixed projection position.

66. The method of claim 65 wherein each fixed projection position has a unique code.

67. The method of claim 65 wherein said projected stripe boundaries are uniformly spaced.

68. The method of claim 67 wherein spacing between said projected stripe boundaries is in part determined by a resolution of said image detector.

69. The method of claim 65 wherein said stripe boundaries comprise pixel boundaries between adjacent stripes in said radiation pattern.

70. A method for range scanning a three-dimensional scene, the method comprising:

a) projecting a sequence of differently-timed radiation patterns onto the scene, wherein the radiation patterns comprise, at predetermined projection positions, pattern features coded in time according to a code, wherein the pattern features are stripe boundaries in the radiation patterns;

b) detecting image patterns produced by reflection of the projected sequence of radiation patterns from the scene, wherein the image patterns comprise image boundaries coded in time according to the code;

c) processing the image patterns using the code to determine image positions of the image boundaries coded in time according to the code; and

d) computing range information for the scene using the image positions determined using the code.