Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
2001-04-09
2004-12-28
Couso, Yon J. (Department: 2625)
Image analysis
Applications
3-d or stereo imaging analysis
C382S285000, C345S419000, C356S012000
Reexamination Certificate
active
06836562
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of computer graphics, and particularly to generating models of graphics objects from range images.
BACKGROUND OF THE INVENTION
Several techniques have been developed in research and industry for determining 3D geometry from a set of aligned range images, see Curlass “
From range scans to
3
D models
,” Comp. Graphics, Vol. 33, No. 4, 1999.
Recent work has shown that volumetric methods are robust to scanner noise and alignment uncertainty and provide good quality, water-tight models, see Curlass et al. “
A volumetric method for building complex models from range images
,” Proc. SIGGRAPH'96, pp. 303-312, 1996, Hilton et al. “
Reliable surface reconstruction from multiple range images
,” 4th Euro. Conf. Comp. Vis., pp. 117-126, 1996, and Wheeler “
Automatic modeling and localization for object recognition
”, Ph.D. Thesis, Carnegie Mellon University, 1996.
However, most of these methods suffer from limited resolution, large memory requirements and long processing time. In addition, these methods produce mesh models with an excessively large number of triangle.
These methods construct a range surface for each aligned range image, and fill a fixed resolution volumetric representation with signed distances from the range surfaces. The methods use various techniques to reduce the time required to fill and access the volumetric data, including run length encoding of the distance values, binary encoding of regions outside a bounded region of the surface, and a 3-color octree representation of the volume. The distance values from multiple scans can be combined probabilistically using order-independent, or incremental updating. These methods all build a triangle model of the iso-surface of the distance volume using a well known Marching Cubes technique, see Lorensen et al. in “
Marching Cubes: A High Resolution
3
D Surface Construction Algorithm
,” Proc. SIGGRAPH '87, pp. 163-169, 1987.
Constructing 3D range surfaces and computing distances from these iso-surfaces significantly increases computational requirements. If, instead, the distance field could be generated directly from 2D range images, model generation times could be greatly reduced.
However, range images do not provide true distance values. In the simplest case, a range image records the perpendicular projected distance from the object's surface to the image plane. The projected distance field is the same as the true distance field in only two special cases: throughout the distance field for a planar surface exactly parallel to the image plane, and at the surface where both true distances and the projected distances are zero for any surface.
Other than the first case, the projected distance field differs from the true distance field for points off the surface. This results in artifacts when projected distance fields from different viewpoints are combined.
Prior art described in U.S. patent application Ser. No. 09/206,071
“A Method for Estimating Volumetric Distance Maps from
2
D Depth Images
” filed by Frisken et al. on Dec. 4, 1999 showed that a 3D projected distance field can be corrected by dividing sampled distances by the magnitude of the local 3D gradient of the projected distance field. This results in a better approximation of the true distance field near the surface, yielding better results when combining projected distance fields. However, computing the 3D gradient of the projected distance field directly from sampled distance values can be prohibitively expensive since it can require six or more additional evaluations of the distance field per gradient.
Therefore, it is desired to determine corrective distance field gradients directly from range images rather than from 3D volumetric data.
SUMMARY OF THE INVENTION
The present invention provides a method for determining a 2D gradient magnitude image from a range image of an object from which the 3D gradient magnitude can be derived. The range image includes a plurality of intensity values at pixel locations. The intensity values correspond to distances to a surface of the object.
The method scales the range image so that a unit intensity value corresponds to a unit distance value. Then, for each pixel s
i,j
in the range image, the method determines a horizontal central difference dx, and a vertical central difference dy. Then, the 2D gradient magnitude at each pixel s
i,j
is set to one half of the square root of (dx
2
+dy
2
+4).
The magnitude of the gradient of a 3D projected distance field can then be determined at a 3D point p by perpendicularly projecting the point p onto a location (x, y) of the scaled range image, by interpolating the gradient magnitude at (x,y) from the corresponding 2D gradient magnitude image values near the location (x,y), and by setting the 3D gradient magnitude at p to the interpolated 2D gradient magnitude at (x,y).
REFERENCES:
patent: 5224208 (1993-06-01), Miller et al.
patent: 5548694 (1996-08-01), Frisken Gibson
patent: 5867592 (1999-02-01), Sasada et al.
patent: 6184887 (2001-02-01), Rohner
patent: 6262738 (2001-07-01), Gibson et al.
patent: 6396492 (2002-05-01), Frisken et al.
patent: 6469700 (2002-10-01), Munshi et al.
patent: 6724393 (2004-04-01), Perry et al.
patent: 2002/0130854 (2002-09-01), Perry et al.
patent: 2002/0130856 (2002-09-01), Perry et al.
patent: 2002/0130858 (2002-09-01), Perry et al.
patent: 2002/0130859 (2002-09-01), Perry et al.
Curless et al. “A Volumetric Method for Building Complex Models from Range Images”, In Proceedings of SIGGRAPH '96, pp. 303-312, 1996.
Wheeler et al. “Consensus Surfaces for Modeling 3D Objects from Multiple Range Images”.
Frisken Sarah F.
Perry Ronald N.
Brinkman Dirk
Carter Aaron
Couso Yon J.
Curtin Andrew J.
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
Method for determining the shape of objects directly from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining the shape of objects directly from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining the shape of objects directly from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3319774