Patent US4891762A successfully refreshed from Google Patents.
US4891762A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for tracking, mapping and recognition of spatial patterns
Assignee: Individual
•
Filing: 1988-02-09
•
Granted: 1990-01-02
•
Expires: 2008-02-09
Abstract
Abstract 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.
Inventors
- 👤 Nicholas P. Chotiros
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 09:34
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/20; G06T7/246; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751; G06V10/7515
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
215 words
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.
Claim 2
Dependent Claim
215 words
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.
Claim 3
Dependent Claim
482 words
A navigational system comprising: means for periodically generating a scene comprising a plurality of data points, each said data point possibly representing a feature in the environment, said generating means including: sensing means for periodically sensing the presence and position of said features; means for consolidating groups of said sensed features that are too closely clustered to be reliably resolved by said sensing means including: means for identifying clusters of two or more sensed features that occupy a spaced too small to be reliably resolved by said sensing means; and means for replacing each said cluster by a single sensed feature located at the center of said cluster; and means for storing a data point to represent each said sensed feature, said data point comprising its position and a unique identifier; means for prestoring a map comprising a plurality of data points representing reference features; 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 sensing means; means for systematically searching for said matched lines; and means for storing said matched lines according to said identifiers of their terminations; means for reducing said list of matched lines, said reducing means including: means for accumulating a tally of the number of said pairs of matched lines that a said data point in said scene shares with a said data point in said map, for all combinations thereof; means for generating a list of likely matched points, including means for pairing each said data point in said scene with the data point in said map with which it shares the largest said tally; means for pairing each said data point in said map with the data point in said scene with which it shares the largest said tally; and means for storing said point pairs in said list of likely matched points in a systematic manner according to their said identifiers; and means for eliminating from said list of matched lines those matched lines that do not connect any two pairs of said likely matched points; 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; and means for updating the position and heading of said navigational system from said coordinate transformation matrix.
Claim 4
Dependent Claim
482 words
A navigational system comprising: means for periodically generating a scene comprising a plurality of data points, each said data point possibly representing a feature in the environment, said generating means including: sensing means for periodically sensing the presence and position of said features; means for consolidating groups of said sensed features that are too closely clustered to be reliably resolved by said sensing means including: means for identifying clusters of two or more sensed features that occupy a spaced too small to be reliably resolved by said sensing means; and means for replacing each said cluster by a single sensed feature located at the center of said cluster; and means for storing a data point to represent each said sensed feature, said data point comprising its position and a unique identifier; means for prestoring a map comprising a plurality of data points representing reference features; 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 sensing means; means for systematically searching for said matched lines; and means for storing said matched lines according to said identifiers of their terminations; means for reducing said list of matched lines, said reducing means including: means for accumulating a tally of the number of said pairs of matched lines that a said data point in said scene shares with a said data point in said map, for all combinations thereof; means for generating a list of likely matched points, including means for pairing each said data point in said scene with the data point in said map with which it shares the largest said tally; means for pairing each said data point in said map with the data point in said scene with which it shares the largest said tally; and means for storing said point pairs in said list of likely matched points in a systematic manner according to their said identifiers; and means for eliminating from said list of matched lines those matched lines that do not connect any two pairs of said likely matched points; 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; and means for updating the position and heading of said navigational system from said coordinate transformation matrix.
Claim 5
Dependent Claim
14 words
A navigational system of claim 2 wherein said sensing means comprises a sonar set.
Claim 6
Dependent Claim
14 words
A navigational system of claim 2 wherein said scene and map are digitally stored.
Claim 7
Dependent Claim
67 words
A navigational system of claim 2 including a map updating means comprising: means to detect new data points that, through said coordinate transformation matrices, consistently map into coincident locations in said map and to add said new data points to said map; and means to detect the consistent absence in said scenes of data points in said map and to remove said data points from said map.
References Cited (Backward Citations)
US3879728A
Cited
US3992707A
Cited
US4514733A
Cited
US4164728A
Cited
US4179693A
Cited
US4754493A
Cited
US4192004A
Cited
US4590608A
Cited
US4494200A
Cited
US4396903A
Cited
US4490719A
Cited
US4602336A
Cited
US4700307A
Cited
US4635203A
Cited
US4736436A
Cited
US4715005A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-01-01 | 1993-07-03 | 1994-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-01-01 | 1997-07-03 | 1998-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-01-01 | 2001-07-03 | 2002-01-02 | $7700.00 | Window Closed / Lapsed |