Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1998-10-14
2002-03-26
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Feature extraction
C382S153000
Reexamination Certificate
active
06363173
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to determining the position and orientation of an object and, more particularly, to incrementally determining the position and orientation of a planar object to receive a load of material in an earthmoving environment.
BACKGROUND ART
As used in this patent specification the phrase “earthmoving machine” and various approximations thereof refer to excavators, wheel loaders, track-type tractors, compactors, motor graders, agricultural machinery, pavers, asphalt layers, and the like, which exhibit both (1) mobility over or through a work site, and (2) the capacity to alter the topography or geography of a work site with a tool or operative portion of the machine such as a bucket, shovel, blade, ripper, compacting wheel and the like.
While operating earthmoving machinery such as excavators, wheel loaders, and cranes for moving materials from one location to another, human operators visually determine the position and orientation of the object that is to receive the load and control the delivery of material accordingly. For example, in an earthmoving environment, an excavator is used to deliver material to the bed of a dump truck. The operator of the excavator visually determines the position and orientation of the truck bed to be loaded, and delivers the bucket of material to the desired location.
In some applications, autonomous loading and unloading operations take place. A system capable of determining, without the aid of a human operator, the position and orientation of an object that is to receive a load is often required in an autonomous loading system, especially in situations where the location of the loading point varies. Examples include loading systems for dump trucks, flat bed trucks, train cars, hoppers, barges, and cargo ships. In an earthmoving environment, the position and orientation of the object that receives the load, such as a dump truck, varies from one truck to the next as the beds of the trucks are filled and empty trucks arrive to replace them. If the earthmoving machinery is operating autonomously, information on the position and orientation of each truck to be loaded must be provided to the machinery's control system.
In the prior art, systems have been developed to recognize and identify objects. These systems, such as that disclosed in U.S. Pat. No. 5,471,541, issued Nov. 28, 1995 to Burtnyk, et al. typically match image data with models of objects with exact dimensions. The Burtnyk et al. patent utilizes range profiles and synthetic profiles derived from a model. This method also assumes that an approximate pose of the object is known. In some object recognition approaches, the model's pose (position and orientation) are continually updated as model features are matched to the data. See Faugeras and Hebert, “The Representation, Recognition, and Locating of 3-D Objects”, The International Journal of Robotics Research, Vol. 5, No. 3, pgs. 27-52. Fall 1986. Another approach to calculating a rigid model's pose is known as the Iterative Closest Point (I.C.P) method presented by Paul J. Besl and Neil D. McKay, in a paper entitled “A method for registration of 3-D shapes” published in IEEE Transactions On Pattern Analysis and Machine Intelligence, Vol. 14 (2), pp. 239-256, 1992. In this method, the data is transformed to fit the model by iteratively minimizing the distance between points in the model and points in the original data set to refine an initial approximate pose of the object. This method assumes that the points associated with the object have been segmented from other points in the scene.
U.S. Pat. No. 5,208,763, issued May 4, 1993 to Hong et al. discloses a method for determining position and orientation of mechanical objects that involves using Euclidean transformations to match the object with a model. U.S. Pat. No. 5,123,057 issued Jun. 16, 1992 to Verly et al. discloses a method using recursive procedures to match detected data to predetermined models and determine “degrees of match” between a subset of data to a subset of model parts. The highest “degrees of match” with the models are used to identify the object.
Bolles and Horaud developed an object recognition system known as 3DPO (three dimensional part orientation system) in which they used a strategy of locating the most promising feature in a three dimensional image of a jumble of parts and using this feature to suggest other features that could confirm their hypothesis and lead them to other features that could completely constrain the pose of an object. In this system they found discontinuities in a single scanline and linked these discontinuities together using a method known as edge chaining to form the linear features that they used to guide their search for objects. This work was presented in a technical paper authored by R. C. Bolles and P. Horaud entitled “3DPO: A Three Dimensional Part Orientation System”, The International Journal of Robotics Research, Vol. 5, No. 3, Fall 1986, pp. 3-26.
In some situations, it is desirable to recognize and locate objects of a certain type whose dimensions are known to vary. A method of determining the location, size, and orientation of these objects is therefore required. Further, in situations where several machines must work cooperatively and/or autonomously in an environment, it is important to be able to recognize and determine the location, size, and orientation of objects used for containing or hauling materials. Maximizing the productivity of an automated earth moving machine means that computational efficiency is important to process all the data needed to control the machine without time delays. A system that does not require a full scan of the object and the surrounding area is therefore desirable. It is also desirable to have the capability to track the movement of the objects once they have been recognized. A method and apparatus that may be deployed in a harsh environment, with sensor systems capable of supplying data of limited resolution and accuracy is also desired.
Accordingly, the present invention is directed to overcoming one or more of the problems as set forth above.
DISCLOSURE OF THE INVENTION
The present invention is a method and apparatus for recognizing and determining the location and orientation of an object using incremental range data from a scanning sensor. The present recognition method takes advantage of characteristics of data provided by scanning sensors along with the geometrical characteristics of objects that typically receive loads in an earthmoving environment, such as dump trucks. The data from a single scanline provided by a scanning sensor system is processed to determine if there are discontinuities in the scanline. Since a single scanline is acquired in a relatively short period of time, the geometric relationships of features in the scanline is preserved, even given sensor motion that is unmeasured. The present method also takes advantage of the fact that discontinuities in adjacent scanlines should be in close proximity to each other and should correspond to dominant features in a model of the object. The top and bottom edges of an object, such as a dump truck bed and prominent changes in the terrain, can be located as discontinuities in a single scan line. These discontinuities are used to form possible interpretations of the object's position and orientation. As more scanlines are received, discontinuities that are in close proximity are given similar labels. Lines are also fit to the discontinuities and are compared to edges in one or more models that are possible interpretations of the object. Geometric constraints derived from the model are used to eliminate unfeasible interpretations and to confirm feasible interpretations. If a feasible interpretation can be formed, then the object of interest is assumed to be recognized. The best interpretation, based on the number of scanlines used and the most model features found, is processed to determine the best position and orientation of the object. As scanlines are received, th
Lay Keith
Stentz Anthony
Azarian Seyed
Blackwell Sanders Peper & Martin
Carnegie Mellon University
Johns Andrew W.
LandOfFree
Incremental recognition of a three dimensional object does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Incremental recognition of a three dimensional object, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incremental recognition of a three dimensional object will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2823419