Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
1997-07-18
2001-05-08
Bella, Matthew C. (Department: 2621)
Image analysis
Applications
3-d or stereo imaging analysis
C382S285000, C250S201400
Reexamination Certificate
active
06229913
ABSTRACT:
BACKGROUND OF THE INVENTION
I. Field of the Invention
The present invention relates to techniques for mapping a three-dimensional structure or object from two-dimensional images, and more particularly relates to techniques employing active illumination to retrieve depth information.
II. Description of the Related Art
A pertinent problem in computational vision is the recovery of three-dimensional measurements of a structure from two-dimensional images. There have been many proposed solutions to this problem that can be broadly classified into two categories; passive and active. Passive techniques such as shape from shading and texture attempt to extract structure from a single image. Such techniques are still under investigation and it is expected they will prove complementary to other techniques but cannot serve as stand-alone approaches. Other passive methods, such as stereo and structure from motion, use multiple views to resolve shape ambiguities inherent in a single image. The primary problem encountered by these methods has proved to be correspondence and feature tracking. In addition, passive algorithms have yet to demonstrate the accuracy and robustness required for high-level perception tasks such as object recognition and pose estimation.
Hitherto, high-quality three-dimensional mapping of objects has resulted only from the use of active sensors based on time of flight or light striping. From a practical perspective, light stripe range finding has been the preferred approach. In structured environments, where active radiation of a scene is feasible, it offers a robust yet inexpensive solution to a variety of problems. However, it has suffered from one inherent drawback, namely, speed. To achieve depth maps with sufficient spatial resolution, a large number (say, N) of closely spaced stripes are used. If all stripes are projected simultaneously it is impossible to associate a unique stripe with any given image point, a process that is necessary to compute depth by triangulation. The classical approach is to obtain multiple images, one for each stripe. The requirement for multiple images increases the required time for mapping.
Focus analysis has a major advantage over stereo and structure from motion, as two or more images of a scene are taken under different optical settings but from the same viewpoint, which, in turn, circumvents the need for correspondence or feature tracking. However, differences between the two images tend to be very subtle and previous solutions to depth from defocus have met with limited success as they are based on rough approximations to the optical and sensing mechanisms involved in focus analysis.
Fundamental to depth from defocus is the relationship between focused and defocused images.
FIG. 1
shows the basic image formation geometry. All light rays that are radiated by object point P and pass through aperture A, having an aperture diameter a, are refracted by the lens to converge at point Q on the focus image plane I
f
. For a thin lens, the relationship between the object distance d, focal length of the lens f, and the image distance d
i
is given by the Gaussian lens law:
1
d
+
1
d
i
=
1
f
Each point on an object plane that includes point P is projected onto a single point on the image plane I
f
, causing a clear or focused image to be formed. If, however, a sensor plane such as I
1
or I
2
, does not coincide with the image focus plane and is displaced from it, the energy received from P by the lens is distributed over a patch on the sensor plane. The result is a blurred image of P. It is clear that a single image does not include sufficient information for depth estimation as two scenes defocused to different degrees can produce identical image elements. A solution to depth is achieved by using two images formed on image planes I
1
and I
2
separated by a known physical distance &bgr;. The problem is reduced to analyzing the relative blurring of each scene point in the two images and computing the distance &agr; to the focused image for each image point. Then, using d
i
=&ggr;−&agr;, the lens law (1) yields depth d of the scene point. Simple as this procedure may appear, several technical problems emerge when implementing a method of practical value.
First, there is the problem of determining relative defocus. In frequency domain, blurring can be viewed as low-pass filtering of the scene texture. Relative blurring can thus in principle be estimated by frequency analysis. However, the local object texture is unknown and variable. Since the effect of blurring is frequency dependent, it is not meaningful to investigate the net blurring of the entire collection of frequencies that constitute scene texture. This observation has forced investigators to use narrow-band filters that isolate more or less single frequencies and estimate their relative attenuation due to defocus in two or more images. Given that the dominant frequencies of the scene are unknown and possibly spatially varying, one is forced to use complex filtering techniques that add to the complexity of the process. This complexity makes the approach impractical for any real-time application.
A second problem with the depth from defocus technique is with respect to textureless surfaces. If the imaged surface is textureless (a white sheet of paper, for instance) defocus and focus produce identical images and any number of filters would prove ineffective in estimating relative blurring. Particularly in structured environments this problem can be addressed by projecting an illumination pattern on the scene of interest, i.e. forcing scene texture. Indeed, illumination projection has been suggested in the past for both depth from defocus and depth from pattern size distortion under perspective projection.
For example, Girod et al., “Depth From Defocus of Structured Light,” Proceedings of the SPIE—The Int'l Soc'y for Optical Eng'g, vol. 1194, pp. 209-215 (1990) discloses the use of a structured light source in a depth from defocus range sensing system. Girod projects a structured light pattern (evenly spaced vertical lines) through a large aperture lens onto the object surface. Girod detects a single image which has image characteristics derived from the defocussing effects of the large aperture light source. Girod also suggests use of an anisotropic aperture, e.g., a slit or T-shaped aperture, in connection with the light source to produce orthogonal patterns that can be compared to remove systemic errors due to the limited depth of field of the camera.
Similarly, A. Pentland et al., “Simple Range Cameras Based on Focal Error,” J. Optical Soc'y of America, vol. 11, pp. 2925-34 (1994) discloses a structured light sensor which projects a pattern of light (evenly spaced vertical lines) via a simple slide projector onto a scene, measures the apparent blurring of the pattern, and compares it to the known (focused) original light pattern to estimate depth.
Notably, these proposed solutions rely on evaluating defocus from a single image. As a result, they do not take into account variations in the defocus evaluation that can arise from the natural textural characteristics of the object.
When considering a multiple image system, the relation between magnification and focus must be taken into account. In the imaging system shown in
FIG. 1
, the effective image location of point P moves along ray R as the sensor plane is displaced. Accordingly the defocused image formed on plane I
1
is larger than the focused image that would be formed on plane I
f
and both of these images are larger than that formed on plane I
2
. This causes a shift in image coordinates of P that in turn depends on the unknown scene coordinates of P. This variation in image magnification with defocus manifests as a correspondence-like problem in depth from defocus since it is necessary to compare the defocus of corresponding image elements in image planes I
1
and I
2
to estimate blurring. This problem has been underemphasized in much of the previous work where a precise focus-magni
Nayar Shree
Noguchi Minori
Wantanabe Masahiro
Baker & Botts L.L.P.
Bella Matthew C.
The Trustees of Columbia University in the City of New York
LandOfFree
Apparatus and methods for determining the three-dimensional... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and methods for determining the three-dimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and methods for determining the three-dimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2478129