Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-01-25
2001-09-04
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C707S793000
Reexamination Certificate
active
06285805
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to determining the distance between a query point and one or more non-convex shapes in either two or three dimensions. More specifically, the invention relates to determining the position of a query point maneuvering in proximity to non-convex shapes in the following areas: robotics, image processing, global positioning, computer graphics.
BACKGROUND OF THE INVENTION
Polygonal shapes (curves and surfaces) are common choices for representing 2D and 3D models in the manufacturing, architectural, Geographic Information Systems, geoscience, warfare simulation, medical imaging, robotics, and entertainment industries.
It is frequently necessary to determine accurately the shortest distance to and closest point on such a shape from a given point or shape: this is important for instance in robotics in order to predict whether collisions between shapes are about to occur.
A shape typically is represented by either a polygonal curve or a polygonal surface. A polygonal curve has vertices connected by edges. A polygonal surface typically is represented by a triangular mesh which has vertices connected by triangles and edges. For a more detailed description, see U.S. patent application Ser. No. 006,771 entitled COMPRESSED REPRESENTATION OF CHANGING MESHES AND METHOD TO DECOMPRESS, filed Jan. 14, 1998 by G. Taubin and A. Gueziec, U.S. patent application Ser. No. 023,757, entitled PROGRESSIVE MULTI-LEVEL TRANSMISSION AND DISPLAY OF TRIANGULAR MESHES by A. Gueziec, G. Taubin and F. Lazarus, and U.S. patent application Ser. No. 976,247 entitled PROGRESSIVE COMPRESSION OF CLUSTERED MULTI-RESOLUTION POLYGONAL MODELS all of which are herein incorporated by reference in their entirety.
A query point is a point for which it is sought to compute the distance and closest point on one or more polygonal surfaces.
The problem of finding the shortest distance and closest point is very related to the problem of detecting intersections between shapes, because intersections are locations where such distances are zero. The problem of detecting intersections were recently studied by Ming Lin in “Efficient Collision Detection for Animation and Robotics”, PhD Thesis, University of California, Berkeley, 1993, and by J. Klosowski et al., in “Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPS” in IEEE Transactions on Visualization and Computer Graphics, Vol 4. No. 1, January-March 1998, pages 21-36, all of which are herein incorporated by reference in their entirety. Other related work is described in the Lin and Klosowski's publications.
Ming Lin proposes a solution to find the shortest distance between a point and a convex shape and between two convex shapes. To generalize his solution to non-convex shapes, it is necessary to decompose non-convex shapes into convex shapes, which not only is known as a delicate operation by anyone versed in the field (there may be a high number of convex-subparts), but increases significantly the computational complexity of the method, because the computations must be performed on each shape separately. Another related method for finding closest pairs of points on convex shapes is described in U.S. Pat. No. 5,675,720 METHOD FOR SEARCHING FOR POINTS OF CLOSEST APPROACH AND PREPROCESSING METHOD THEREFOR. As with Ming Lin's method, this method does not easily generalize to solving the problem of finding a closest point on a non-convex shape. Klosowski's work does not generally apply to the problem of finding the closest point, but relates to finding the closest point as applied to an intersection or a touching.
Spatial data structures called quad-trees and Octrees can be used to solve a version of the same problem called Nearest Object location problem. For details, see p 228-9 of Applications of Spatial Data Structures, by H. Samet, Addison Wesley 1989. This problem is different because the shortest distance and closest point are not required in finding the closest object.
In U.S. Pat. No. 5,715,166 APPARATUS FOR THE REGISTRATION OF THREE-DIMENSIONAL SHAPES (which is herein incorporated by reference in its entirety), P. Besl and N. Mc Kay compute the distance from a query point to a three dimensional polygonal shape composed of triangles by computing the distances between the query point and each individual triangle (that is inside a min-max box defined in the vicinity of the query point) and by taking the minimum of the distances. This computation is expensive because the distance to each triangle composing, the shape is computed.
PROBLEMS WITH THE PRIOR ART
Although the prior art methods are useful for computing distances between points and convex shapes, they fail to provide a satisfactory solution to the problem of determining accurately the shortest distance and closest point on a non-convex shape. Such methods require segmenting the shape in convex parts (including the Besl and Mc Kay method, wherein convex parts are triangles), solving separate instances of the problem on each convex part, and integrating the results obtained for each convex part: these operations are costly and can present significant challenges (such as segmenting a shape in a relatively small number of parts).
OBJECTS OF THE INVENTION
An object of this invention is an improved system and method for determining the distance from a query point to one or more convex or non convex-shapes.
Another object of this invention is all improved system and method for determining distances between convex or non-convex shapes.
SUMMARY OF THE INVENTION
The present invention is a computer system and method for determining the closest point on a shape (2 dimensional or 3 dimensional surface) to any general query point. The system has one or more central processing units (CPUs), one or more memories, and one or more geometric model portions stored in one or more of the memories. The geometric model portions have a plurality of line segments (and alternatively in 3 dimensions, polygons), each of the line segments (polygons) being between a first and a second endpoint (having a polygon boundary). The line segments and end points (polygons and polygon boundaries) are connected to form a shape (in 3 dimensions, a surface) with one or more parameters. Parameters can include geometric position, time, temperature, pressure, flow, color, texture, or any other descriptive value.
A multiresolution process creates one or more models of the shape (surface). The models have a hierarchy of resolutions. Each model has one or more model line segments (model polygons) that approximate one or more of the line segments (polygons). Each model line segment (model polygons) is associated with an error.
A distance process, for every model line segment (polygon), determines a distance between a closest point on one or more of the model line segments (polygon) and a query point. The distance represents one or a combination of two or more of the parameters. The process further determines a confidence level in terms of an upper bound and a lower bound of an envelope enclosing the segment (polygon). The closest point is within the envelope—the upper bound representing an upper limit of the parameter in the envelope determined by an upper error of the respective model containing the model line segment and the lower bound representing a lower limit of the parameter in the envelope determined by a lower error of the respective model.
A priority process orders the model line segments (polygons) according to their respective lower bounds and if a maximum error for every one of the model line segments is less than a threshold. The priority process also selects the smallest distance as the minimum distance between the query point and the shape.
REFERENCES:
patent: 5189709 (1993-02-01), Wang et al.
patent: 5566292 (1996-10-01), Krembs
patent: 5655063 (1997-08-01), Crocker
patent: 5715166 (1998-02-01), Besl et al.
patent: 5892515 (1999-04-01), Kobayashi et al.
patent: 6104404 (2000-08-01), Masuda et al.
patent: 6108006 (2000-08-01), Hoppe
patent: 6128767 (2000-10-01), Chapma
Boudreau Leo
F. Chau & Associates LLP
International Business Machines Corp.
Patel Kanji
LandOfFree
System and method for finding the distance from a moving... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for finding the distance from a moving..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for finding the distance from a moving... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438065