초록 ▼

A method and apparatus for the identification of spatial patterns that occur in two or more scenes or maps. Each pattern comprises a set of points in a spatial coordinate system collectively represented by the geometrical figure formed by connecting all point pairs by straight lines. The pattern rec

A method and apparatus for the identification of spatial patterns that occur in two or more scenes or maps. Each pattern comprises a set of points in a spatial coordinate system collectively represented by the geometrical figure formed by connecting all point pairs by straight lines. The pattern recognition process is one of recognizing congruent geometrical figures. Two geometrical figures are congruent if all the lines in one geometrical figure are of the same length as the corresponding lines in the other. This concept is valid in a spatial coordinate system of any number of dimensions. In two- or three-dimensional space, a geometrical figure may be considered as a polygon or polyhedron, respectively. Using the coordinates of the points in a pair of congruent geometrical figures, one in a scene and the other in a map, a least squares error transformation matrix may be found to map points in the scene into the map. Using the transformation matrix, the map may be updated and extended with points from the scene. If the scene is produced by the sensor system of a vehicle moving through an environment containing features at rest, the position and orientation of the vehicle may be charted, and, over a series of scenes, the course of the vehicle may be tracked. If the scenes are produced by a sensor system at rest, then moving objects and patterns in the field of view may be tracked.

대표청구항 ▼

A pattern recognition system comprising: means for periodically generating a scene comprising a plurality of data points, each said data point comprising the position of and a unique identifier assigned to a point in space; means for prestoring a map comprising a plurality of said data points repres

A pattern recognition system comprising: means for periodically generating a scene comprising a plurality of data points, each said data point comprising the position of and a unique identifier assigned to a point in space; means for prestoring a map comprising a plurality of said data points representing reference points; means for determining a coordinate transformation matrix between said scene and said map, said determining means including: means for recognizing a geometrical figure in said scene that is exclusively congruent with another geometrical figure in said map, said recognizing means including: means for generating a list of matched lines, including: means for calculating the length of the straight line between any two said data points; means for determining if a said straight line in said scene matches another said straight line in said map in length within the limits of accuracy of said generating means; means for systematically searching for said matched lines; and means for storing said matched lines according to said identifiers of their terminations; and means for searching said list of matched lines for a geometrical figure in said scene that is exclusively congruent with a geometrical figure in said map; and means for computing said coordinate transformation matrix from the relative displacements in position and orientation between said congruent geometrical figures.