Image analysis – Applications – Range or distance measuring
Reexamination Certificate
2000-08-14
2004-06-22
Mariam, Daniel (Department: 2621)
Image analysis
Applications
Range or distance measuring
C382S107000, C356S003000
Reexamination Certificate
active
06754370
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to non-contact methods for obtaining three-dimensional or range measurements of objects. More particularly, it relates to a structured light (or other radiation) range scanner using projected patterns that permit real-time range measurements of moving scenes with minimal surface continuity and reflectivity assumptions.
BACKGROUND ART
The ability to determine the distance to objects or surfaces in a three-dimensional spatial scene is becoming increasingly important in many fields, such as computer graphics, virtual and augmented reality, robot navigation, manufacturing, object shape recognition, and medical diagnostics. A large variety of non-contact techniques have been developed to obtain range images, two-dimensional arrays of numbers that represent the distance or depth from the imaging instrument to the imaged object. A range image measures the location of each point on an object's surface in three-dimensional space. Active range scanning methods include time-of-flight, depth from defocus, and projected-light triangulation. Triangulation-based methods, such as structured light range scanning, are applicable to a wider range of scene scales and have lower hardware costs than other active methods.
Devices that obtain range images by triangulation methods are known as range scanners. A typical prior art structured light range scanning system
10
is illustrated in
FIG. 1. A
light projector
12
projects a plane of light
14
onto a three-dimensional object
16
to be imaged, creating a narrow stripe. The image of each illuminated point of object
16
is detected by a camera
18
at a particular two-dimensional location on the camera image plane
20
. The intersection of the known illumination plane
14
with a camera line of sight uniquely determines a point on the object surface. Provided that the relative geometry of the camera and projector is accurately known, the three-dimensional locations of surface points of object
16
can be determined through triangulation. Obtaining a range image of the entire scene requires scanning of the light plane
14
in time, a relatively time-consuming process, and currently not feasible for moving scenes or real-time data acquisition.
In order to speed up the imaging process and eliminate mechanical scanning, two-dimensional projected light patterns have been used. Rather than a single plane, a number of distinct planes are projected onto the scene; the image obtained therefore contains range information for the entire scene, and not just a small slice of it. Such illumination patterns introduce a new problem: identifying correspondences between image positions and pattern positions. When only a single light plane is projected, an illuminated part of the image must correspond to the projected plane. If a number of planes are projected, however, a camera pixel receiving light originating from the projector may correspond to any one of the projected planes, and it is necessary to determine the responsible plane.
Highly reliable identification of light planes with minimal assumptions about the nature of the scene can be achieved by time multiplexing, i.e., by sequentially projecting several different illumination patterns. The sequence of intensity values received at each camera pixel defines a unique code that identifies a location of the projection pattern, therefore allowing triangulation to be performed. Range data can be computed after the full sequence of projection patterns has been captured by the camera. A large number of pattern systems have been developed for a variety of scene constraints, each one having different advantages applicable to different types of scenes. Two constraints applicable to static scenes are the surface continuity and reflectivity of the scene. A surface reflectivity assumption refers to the similarity of reflectivity of adjacent surface regions in the scene. If the scene is of uniform color, then it is much easier to obtain information from the reflected intensities. Spatially varying reflectivities require different decision thresholds for different pixels of the detector. For example, consider a pattern that contains three different projected light intensities. The same projected intensity results in different reflected and imaged intensities when reflected from different scene locations, and a decision about the detected intensity level requires at least some knowledge of the reflectivity of the corresponding scene surface. Similar considerations apply to the surface continuity of a scene. Scenes with high surface continuity, i.e., smoothly changing surfaces, such as human forms, allow correlation of pattern features across large distances. Low-surface-continuity scenes, however, require that codes be ascertained from nearby pixels, without requiring information from far-away detector pixels.
One well-known system of time-modulated illumination patterns uses binary Gray codes, projecting a series of stripes that decrease in width in sequential patterns. An early use of Gray codes is described in K. Sato and S. Inokuchi, “Three-Dimensional Surface Measurement by Space Encoding Range Imaging,”
J. Robotic Systems,
2, 27-39, 1985, and a large number of variations are available in the art. A sequence of Gray coded patterns, each projected at a particular time t
i
, is shown in FIG.
2
. Each pattern can be thought of as a bit plane for a Gray code, considering a shaded stripe as a 0 bit and a white stripe as a 1 bit. For example, the scene surface that receives light at the location marked with the center of an X sees the bit code 1 1 1 0 1. As long as the scene does not move, a particular camera pixel (or multiple pixels) receives light reflected from this particular scene surface over the duration of the projection sequence, and the detected 1 1 1 0 1 code is used to determine the projector location corresponding to this camera pixel. The number of patterns needed is determined by the desired resolution, which may itself be determined by the camera or projector. For a maximum of N distinguishable horizontal positions, a Gray coded pattern requires log
2
N patterns.
Structured light patterns based on Gray codes are very robust and widely used. They require virtually no assumptions about the scene reflectivity or surface continuity. Correspondences are determined using only single-pixel information, and pixel thresholds can be determined initially by projecting all-dark and all-bright patterns. However, a relatively large number of patterns is needed, demanding that the scene remain static for the duration of the pattern sequence. Thus if real-time range data is needed, or moving scenes are imaged, a different pattern system is required.
One approach for imaging moving scenes is to use a “one-shot” system of projection patterns. A single pattern is continually projected, and range information is obtained for each camera image. Provided that the scene movement is not so rapid as to cause motion blur in the captured images, one-shot systems can be used to obtain range data for moving scenes. The drawback of one-shot systems is that they are limited to scenes having relatively constant reflectivity and a high amount of continuity. For example, color projector patterns have been used in which each projector pixel transmits light with a distinct ratio among the red, green, and blue (RGB) or hue, saturation, and intensity (HSI) color components. The detected RGB or HSI value at each camera pixel determines the correspondence between the camera pixel location and projector pixel location. In a different system, the pattern consists of a continual fade from black to white, with detected gray-scale intensity values used to determine the responsible projector pixels. Both of these patterns require a relatively constant and known reflectivity for all locations within the scene. An alternative one-shot system projects a repetitive pattern such as a grid. An example of such a method is described in M. Proesmans et al., “One-Shot Active 3D Shape Acquisition
Hall-Holt Olaf A.
Rusinkiewicz Szymon M.
Lumen Intellectual Property Services Inc.
Mariam Daniel
Patel Shefali
The Board of Trustees of The Leland Stanford Junior University
LandOfFree
Real-time structured light range scanning of moving scenes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Real-time structured light range scanning of moving scenes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Real-time structured light range scanning of moving scenes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3353144