Data processing: measuring – calibrating – or testing – Measurement system – Dimensional determination
Reexamination Certificate
2001-06-08
2004-11-16
Barlow, John (Department: 2863)
Data processing: measuring, calibrating, or testing
Measurement system
Dimensional determination
Reexamination Certificate
active
06820032
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data acquisition, and more particularly to scanning a region.
DESCRIPTION OF THE RELATED ART
Many scientific and engineering tasks involve scanning a region, such as an image 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 recognition and location tasks in machine vision and motion control systems, among others.
In a typical scanning system a computer system is coupled to a camera which is operable to acquire optical or image information from a target object. 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 camera and the target object to perform the scan.
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. Examples of such goals include:
(a) Travel in the shortest time from a given point A of a space to another point B of the space.
(b) Travel the shortest path from a given point A of a space to another point B of the space.
(c) Travel a path through a space such that any point in the space is within a specified distance of the path. In other words, the space or geometry must be scanned completely or almost completely.
(d) Same as (c) but the path or trajectory may go outside of the originally given space.
(e) All the above cases but with curvature constraints added.
A more complicated situation may occur when the underlying geometry of the space is unknown and a scanning strategy must be applied to explore the structure of the space.
The tasks (a) and (b) are well-understood and classical design tools (optimal control) are available. Tasks (c) and (d) belong to a class of coverage path planning problems where a path must be determined guaranteeing that an agent will pass over every point in a given environment. Typical applications 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. Most coverage planners are still based on heuristics and the smoothness of the developed trajectories is rarely an issue.
Choset and Pignon (See Howie Choset, Philippe Pignon, Coverage Path Planning: The Boustrophedon Cellular Decomposition) have developed a boustrophedon decomposition that generalizes the concept of exact cellular decomposition and which results in a union of non-intersecting regions composing the target geometry. The coverage path planning problem is solved in elementary cells and the derived sub-paths are concatenated appropriately. The resulting schemes are essentially based on combinations of back-and-forth motions, i.e., lines are the building blocks of these strategies.
There are many other coverage algorithms, as well. In almost all 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.
FIGS.
1
A-D—Prior Art Scanning Paths
FIGS. 1A-D
illustrate various scanning paths, according to the prior art. It should be noted that the physical characteristics of a scanning apparatus may place restrictions on what scanning paths may be suitable for a given application. As described below, various prior art scanning schemes may be appropriate for particular applications, but may not be generally applicable due to high curvatures and/or severe start/stop requirements.
FIG.
1
A—Peano Curve Space-filling Path
Scanning given geometric objects in two- or higher-dimensional spaces is a well-studied topic in the mathematical literature. Space-filling curves or umbrella surfaces have often been regarded as pathological objects. Indeed, such structures are generally inappropriate for real scanning scenarios. Although space-filling is achieved in a very mathematical sense, the curves themselves are unrealizable from a motion control standpoint as they are extremely irregular.
FIG. 1A
illustrates a space-filling path known as a Peano Curve. As may be seen, although the Peano Curve fills the space, the complexity and extreme curvature of the path make it a poor solution for motion control applications.
Moreover, accurate space-filling is often neither attainable nor desirable in motion planning. What is needed are trajectories that pass within a specified distance of any point of the region of interest at any given time.
FIG.
1
B—Boustrophedon Scanning Path
One widely used scanning strategy is referred to as the boustrophedon path or “way of the ox”. An example of this approach is presented in FIG.
1
B. The chief advantages of the boustrophedon path are the simplicity of the definition and the possibility to fill gaps in further loops. However, there are significant drawbacks to this scheme. In particular, the scanning cannot be done continuously because of curvature problems. For example, at each end of a long scan line, two 90 degree turns must be made. Such abrupt changes in motion are problematic for most motion control systems. Theoretically, the average arrival time is much worse than the strategies of the present invention, described below. The drawbacks of the boustrophedon approach are even more dramatic when searching for small objects of unknown size.
FIG.
1
C—Archimedes Spiral Scanning Path
The other widely used scanning strategy in practical applications is based on an Archimedes spiral.
FIG. 1C
illustrates one example of an Archimedes Spiral-based scanning path. As
FIG. 1C
demonstrates, the curvature is unbalanced, with high curvature near the center of the spiral, and low curvature near the outer edges. Additionally, this approach clearly lends itself to scanning circular regions, and is therefore unsuitable for non-circular scan regions. Other drawbacks similar to those of boustrophedon paths also apply to the Archimedes Spiral scheme, such as fixed scanning resolution or path width, which may not be suitable when scanning for small objects. Moreover, as may be seen in
FIG. 1C
, much time is spent scanning regions away from the center of the region.
FIG.
1
D—Rectangular Spiral Scanning Path
FIG. 1D
illustrates a scanning scheme which utilizes features of both the boustrophedon and the spiral path approach. As
FIG. 1D
shows, the path comprises concentric straight-line path segments which spiral outward from the center of the region. This scheme, however, suffers from some of the shortcomings of its predecessors. For example, similar to the boustrophedon approach, there are discontinuities in the path at each corner, leading to sudden accelerations of the scanning apparatus. Furthermore, the path resolution is fixed, as with the Archimedes Spiral, and may therefore be unsuitable for objects of various or unknown sizes.
In almost all practically relevant cases, scanning schemes for more complicated geometries are based on boustrophedon paths or on other combinations of lines. This is pa
Chandhoke Sundeep
Nair Dinesh
Rajagopal Ram
Ting Joseph
Wenzel Lothar
Barlow John
Hood Jeffrey C.
Lau Tung S
Meyertons Hood Kivlin Kowert & Goetzel P.C.
National Instruments Corporation
LandOfFree
System and method for scanning a region using conformal mapping 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 scanning a region using conformal mapping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for scanning a region using conformal mapping will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320298