Shape comparison using a rotational variation metric and applications thereof

• US 6,728,392 B1
• Filed: 01/30/2001
• Issued: 04/27/2004
• Est. Priority Date: 01/30/2001
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Joshi, Rajashri
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/772,586
• Time in Patent Office: 1,183 Days
• Field of Search: 382/100, 382/103, 382/104, 382/105, 382/106, 382/107, 382/174, 382/201, 382/209, 382/212, 382/199, 382/203, 382/219, 382/237, 382/274, 701/19, 701/20, 701/27, 701/28, 701/118, 701/119, 701/213, 340/988, 340/989, 340/990, 205/972, 345/442
• US Class Current: 382/104
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

A method for comparing geometric shapes to each other is disclosed. The method includes determination of a rotational variation metric. The shapes to be compared are scaled so that their lengths are equal and tangent vectors at corresponding locations along the geometric shapes are determined. The angle between each pair of corresponding tangent vectors for each of these locations is then plotted as a function of the length along the geometric shapes. The variation around the mean angle between the tangent vectors for the locations along the geometric shapes being compared is the rotational variation coefficient. This process defines a rotational variation metric which indicates how closely the two geometric shapes match. The rotational variation metric can be used in various geographic applications, including vehicle positioning, sign recognition, and evaluating geographic database accuracy.

Claims

1. A method of comparing first and second geometric shapes wherein at least one of the geometric shapes represents a geographic feature to indicate how closely the geometric shapes match, the method comprising:

scaling the first and second geometric shapes to have equal lengths;

determining tangent vectors at a plurality of corresponding locations along first and second geometric shapes;

computing the angle between the tangent vectors determined at each of the corresponding locations;

computing a deviation of the angles from a constant; and

using the deviation as a rotational variation metric to indicate how closely the first and second geometric shapes match.

2. The method of claim 1 further comprising:

constructing a plot of the angle between the tangent vectors as a function of the length along one of the shapes.

3. The method of claim 2 further comprising:

computing the variance of the plot around a mean value.

4. The method of claim 1 further comprising:

designating the first of the geometric shapes as a reference shape and the second of the geometric shapes as a non-reference shape.

5. The method of claim 1 wherein the first geometric shape represents a vehicle trajectory and the second geometric shape represents a path of a road segment.

6. The method of claim 1 wherein the first geometric shape represents a detected outline of a sign and the second geometric shape represents a template of a shape of a road sign.

7. The method of claim 1 wherein the first geometric shape represents a data representation of a road and the second geometric shape represents a ground truth representation of a road.

8. A vehicle positioning method comprising:

determining a trajectory of a vehicle;

determining tangent vectors at a plurality of locations along said trajectory;

determining tangent vectors at corresponding of the plurality of locations along data representations of paths of a plurality of roads upon which the vehicle may be located;

determining the angle between the tangent vectors determined for the trajectory and the corresponding tangent vectors determined for each of the data representations of the paths of the plurality of roads to determine a rotational variation coefficient associated with each of the data representations of the paths of the plurality of roads with respect to the trajectory; and

determining that the vehicle is located on that road for which the rotational variation coefficient is smallest.

9. A method of evaluating the accuracy of a database that represents geographic features, the method comprising:

for data that represent geographic features having shape, determining tangent vectors at a plurality of locations along a data representation of the shape of a geographic feature;

determining tangent vectors at corresponding of the plurality of locations along a representation of an actual shape of the geographic feature;

determining the angle between the tangent vectors determined for the data representation of the shape of a geographic feature and the corresponding tangent vectors determined for the actual shape of the geographic feature; and

determining the variation of the angle around its mean value for the data representation of the shape of a geographic feature and the actual shape of the geographic feature,

whereby the variation is used as a rotational variation metric to indicate how closely the data representation of the shape of the geographic feature matches the actual shape of the geographic feature.

10. The method of claim 9 wherein the geographic feature is a road.

11. A method of comparing geometric shapes that represent geographic features, the method comprising:

determining a rotational variation metric from the geometric shapes, wherein the rotational variation metric is formed by;

scaling the shapes to be compared to have equal lengths;

selecting corresponding starting points on each of the geometric shapes;

at each of a plurality of corresponding locations along each of said shapes, determining a tangent vector;

for each corresponding location, determining the angle between corresponding pairs of tangent vectors;

plotting the angle between the tangent vectors as a function of length along one of the shapes; and

determining the variance of the plot around its mean value.

12. The method of claim 11 wherein one of said geometric shapes is a historical trajectory of a vehicle for a finite time.

13. The method of claim 12 wherein the other of said geometric shapes is a path of a road as represented by data contained in a map database.

14. The method of claim 11 wherein one of said geometric shapes is a detected sign object.

15. The method of claim 14 wherein the other of said geometric shapes is a sign shape template.

16. The method of claim 11 wherein one of said geometric shapes is a sampled road segment.

17. The method of claim 16 wherein the other of said geometric shapes is a ground truth road segment.