Data processing: measuring – calibrating – or testing – Measurement system – Performance or efficiency evaluation
Reexamination Certificate
2001-06-25
2003-09-02
Hoff, Marc S. (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Performance or efficiency evaluation
C702S167000, C702S180000, C702S188000, C702S194000
Reexamination Certificate
active
06615158
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of measurement and data acquisition, and more particularly to the analysis of a surface of an object by generation or mapping of a point set on a Riemannian manifold or surface of the object and analyzing data values on the mapped point set to characterize the object.
DESCRIPTION OF THE RELATED ART
Many scientific and engineering tasks involve exploring, i.e., sampling or scanning, a region, such as an image, surface, or object, to acquire data characterizing the region. Examples of such tasks include parts inspection for automated manufacturing systems, alignment tasks for automated assembly systems, and detection, recognition, and location tasks in machine vision and motion control systems, among others. Another application relates to the determination of integrals of smooth functions defined on Riemannian geometries embedded in R
n
, i.e., in multi-dimensional real-space, via sums of function values at well-chosen sampling points. Yet another domain application relates to the exploration and characterization of unknown spaces.
In a typical sampling or scanning system a computer system is coupled to a sensor, such as a camera, which is operable to acquire optical, image, or other information from a target object or surface. The computer system may take any of various forms. The system may also include hardware and corresponding software which is operable to move one or both of the sensor and the target object to perform the scan or measurement. In robotics and motion planning an understanding of the underlying geometry of space is important. Various techniques have been developed to scan regions under various constraints or toward specific goals. In many cases the geometry is known in advance and a specific goal is desired, such as object recognition and/or characterization. In others the space in question may not be characterized, i.e., the nature of the space may be unknown. Exploration of such a space may involve goals such as determining the dimensionality and structure of a space with unknown underlying geometry, or finding critical points of a high-dimensional space.
Typical applications of scanning spaces of known geometry include, but are not limited to: mine-countermeasure missions, continental shelf oceanographic mapping, contamination cleanup, floor scrubbing, crop plowing, non-destructive testing, and bridge inspections, among others. Many of these applications attempt efficient coverage of the space, and so involve determining a coverage plan for the scan region. Most coverage planners are still based on heuristics and the smoothness of the developed trajectories is rarely an issue.
There are many coverage algorithms. In many cases the goal is to guide a robot or sensor to explore or to act within an environment. See, for example, J. Colgrave, A. Branch, “A Case Study of Autonomous Household Vacuum Cleaner”, AIAA/NASA CIRFFSS, 1994. See also M. Ollis, A. Stentz, “First Results in Vision-Based Crop Line Tracking”, IEEE International Conference on Robotics and Automation, 1996.
One promising method in motion planning is based on Morse functions. These procedures look at the critical points of a Morse function to denote the topological changes in a given space. See, for example, Howie Choset, Ercan Acar, Alfred A. Rizzi, Jonathan Luntz, “Exact Cellular Decompositions in Terms of Critical Points of Morse Functions”. See also Ercan U. Acar, Howie Choset, “Critical Point Sensing in Unknown Environments”. However, Morse functions find their primary use with regard to the scanning of un-smooth surfaces, and so are not generally useful for many applications.
Exploration tasks often relate to characterization of unknown spaces. One approach to efficient exploration of a surface or space is based upon Low Discrepancy Sequences (LDS), described below in some detail. However, current techniques generally involve generation of LDSs in simple Euclidean spaces, which may not be appropriate for more complex applications.
Therefore, improved systems and methods are desired for generating a sampling point set, such as a Low Discrepancy Sequence, in a region or on a manifold or surface of an object.
SUMMARY OF THE INVENTION
The present invention comprises various embodiments of a system, method, and memory medium for analyzing a surface, wherein the surface may be a surface of an object, a region, and/or an n-dimensional volume. The surface may also be a Riemannian manifold or an n-dimensional space describing degrees of freedom of an object or device, such as a motion device, e.g., a robotic arm. The method may involve generating a point set or sequence on the surface, acquiring data or taking measurements of the surface at these sample points, and analyzing the measured data to characterize the surface.
The method may include generating a sequence, such as a Low Discrepancy Sequence, within a region or space in which the surface is defined. The sequence may be used for characterizing the surface, such as a high-dimensional space, or for motion planning. Embodiments of the invention include a method for generating a Low Discrepancy Sequence in a Riemannian manifold, e.g., on an n-dimensional surface.
Specifically, an embodiment of the method is described in which a Low Discrepancy Sequence is generated on an n-dimensional space, for example, a unit square, then mapped to the manifold or surface. It is also contemplated that other sequences of points may be mapped in a similar manner, and that regions other than the unit n-square may be used. In one embodiment, the manifold may be a Riemannian manifold. In other words, the manifold may be characterized by a distance-like metric.
In one embodiment, data may be received describing a surface which is defined in a bounded n-dimensional space, also referred to as a bounded n-space. In one embodiment, the bounded n-dimensional space may comprise a unit square. In another embodiment, the bounded n-dimensional space may comprise a unit cube. As mentioned above, in various other embodiments, the bounded n-dimensional space may comprise other geometries, including unit hyper-cubes, or unit n-cubes of dimensionalities greater than 3, as well as n-dimensional rectangles, spheres, or any other geometrical region. In one embodiment, the surface may further be embedded in an m-dimensional space, where m>n. In other words, the surface may be parameterized in terms of a higher dimensional space according to an embedding function x( ).
The received data may include a Riemannian metric characterizing the surface or manifold. In one embodiment, the surface may comprise an image, and the received data may further comprise an intensity function describing the image, e.g., describing pixel information of the image.
A diffeomorphism f of the bounded n-space may be determined. As is well known in the art, a diffeomorphism may be considered a mapping between two spaces which preserves differentiability of a mapped function.
An inverse transform f
−1
of the determined diffeomorphism may be computed. Then, a plurality of points in the bounded n-space may be selected or determined. In one embodiment, the plurality of points may comprise a Low Discrepancy Sequence. It should be noted that although selection of a Low Discrepancy Sequence of points is an exemplary use of the method, any other point set may be used as desired.
In response to the selection of the plurality of points, the plurality of points may be mapped onto the surface via x(f
−1
) to generate a mapped plurality of points, e.g., a mapped Low Discrepancy Sequence. Note that the function x(f
−1
) may be a functional concatenation of the embedding function x( ) and the inverse transform of the diffeomorphism, f
−1
.
The surface may be sampled or measured using at least a subset of the mapped plurality of points. In other words, measurements may be made at one or more of the mapped plurality of points, thereby generating one or more samples of the surface.
Finally, the generated samples of the surface may b
Nair Dinesh
Rajagopal Ram
Wenzel Lothar
Hoff Marc S.
Hood Jeffrey C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
National Instruments Corporation
Suarez Felix
LandOfFree
System and method for analyzing a surface by mapping sample... 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 analyzing a surface by mapping sample..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for analyzing a surface by mapping sample... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3058297