Multi-resolution trend metric for shape comparison and applications thereof

• US 6,560,531 B1
• Filed: 05/22/2001
• Issued: 05/06/2003
• Est. Priority Date: 05/22/2001
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Joshi, Rajashri
• Primary Examiner(s): Nguyen, Tan Q.
• Assistant Examiner(s): Tran, Dalena
• Application Number:
  US09/862,378
• Time in Patent Office: 714 Days
• Field of Search: 701/213, 701/208, 701/201, 701/205, 701/207, 701/209, 701/200, 701/210, 340/990, 340/995, 340/988, 731/78.R
• US Class Current: 701/208
• CPC Class Codes: G01C 21/30 Map- or contour-matching
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/003 Maps

Abstract

A method for comparing geometric shapes to each other is disclosed. When used for vehicle positioning, the present method determines which map path of several candidate map paths best matches an actual path traveled by the vehicle as measured by sensors. The vehicle path and each candidate map path are generalized to a given degree of generalization, thereby yielding an overall trend of the vehicle path and overall trends of each of the candidate map paths. The trend of the vehicle path is compared to the trend of each of the candidate map paths. Based on these comparisons, one or more candidate map paths may be eliminated. If more than one map path remains, the vehicle path and each of the remaining map paths are generalized again, this time to a lesser degree of generalization, and comparisons are made between the trend of the vehicle path and the trend of each of the remaining map paths. Based on these comparisons, one or more map paths may be eliminated. These steps are repeated until only a single map path remains. The vehicle is determined to be located on the road represented by the remaining map path. The multi-resolution trend metric concept can be applied to valuation of the accuracy of a geographic database. A generalized version of a sampled geographic feature is compared to one or more generalized versions of ground truth of the feature to determine how well the generalized versions match and how the shape error between the sampled and ground truth segments varies as a function of resolution.

Claims

1. A method for determining a position of a vehicle along a road, the method comprising the steps of:

forming a candidate pool that contains a plurality of candidate map paths, wherein each candidate map path is a data representation of a path along an actual road; and

wherein each candidate map path represents a possible path along which the vehicle has traveled; and

eliminating all but one of said plurality of candidate map paths from said candidate pool by repeatedly performing the steps of;

generalizing to a given degree of generalization a data representation of an actual vehicle path to form a generalized actual vehicle path;

generalizing to the given degree of generalization each candidate map path in said candidate pool to form a corresponding generalized candidate map path;

comparing each generalized candidate map path in the candidate pool to the generalized actual vehicle path;

eliminating from the candidate pool each generalized map path that does not match the generalized actual vehicle path to a defined degree; and

if more than one candidate map path remains in the candidate pool, decreasing the given degree of generalization for greater resolution in the generalized actual vehicle path and the generalized candidate map path.

2. The method of claim 1 wherein said step of comparing is performed by comparing curvature.

3. The method of claim 1 wherein said step of comparing is performed by computing areas between the generalized actual vehicle path and each generalized map path in said candidate pool and then comparing the areas.

4. The method of claim 1 wherein said step of comparing is performed by computing a rotational variation coefficient.

5. The method of claim 1 wherein the step of generalizing is performed using Douglas-Peucker generalization.

6. The method of claim 1 wherein the given degree of generalization to which the data representations of paths are generalized is given by a tolerance 2⁻

i.C where C is a constant and wherein i is incremented by 1 each time the given degree of generalization is decreased.

7. A method of comparing a first geometric shape to a plurality of candidate geometric shapes comprising:

forming a candidate pool that contains the plurality of candidate geometric shapes; and

eliminating all but one of said plurality of candidate geometric shapes from said candidate pool by repeatedly performing the steps of;

generalizing to a given degree of generalization a data representation of the first geometric shape to form a generalized first geometric shape;

generalizing to the given degree of generalization each candidate geometric shape in said candidate pool to form a corresponding generalized candidate geometric shape;

comparing each generalized candidate geometric shape in the candidate pool to the generalized first geometric shape;

eliminating from the candidate pool each generalized candidate geometric shape that does not match the generalized first geometric shape to a defined degree; and

if more than one candidate geometric shape remains in the candidate pool, decreasing the given degree of generalization for greater resolution in the generalized first geometric shape and the generalized candidate geometric shapes.

8. The method of claim 7 wherein the first geometric shape represents a trajectory of a vehicle and the plurality of candidate geometric shapes represent paths along roads in the vicinity of the vehicle, as represented by data in a map database.

9. The method of claim 7 wherein said step of comparing is performed by comparing curvature.

10. The method of claim 7 wherein said step of comparing is performed by computing areas between the generalized first geometric shape and each generalized candidate geometric shape in said candidate pool and then comparing the areas.

11. The method of claim 7 wherein said step of comparing is performed by computing a rotational variation coefficient.

12. The method of claim 7 wherein the step of generalizing is performed using Douglas-Peucker generalization.

13. The method of claim 7 wherein the given degree of generalization to which the data representations of paths are generalized is given by a tolerance 2⁻

i.C where C is a constant and wherein i is incremented by 1 each time the given degree of generalization is decreased.

14. A method of evaluating the accuracy of a sampled data representation of a geographic feature with respect to a ground truth representation of the geographic feature, the method comprising:

generalizing to a given degree of generalization the data representation of the geographic feature to form a generalized data representation of the geographic feature;

generalizing to the given degree of generalization the ground truth representation of the geographic feature to form a corresponding generalized ground truth representation of the geographic feature;

comparing the generalized ground truth representation of the geographic feature to the generalized data representation of the geographic feature; and

using a result of the comparison as a metric indicative of how well the data representation of the geographic feature matches the ground truth representation of the geographic feature.

15. The method of claim 14 wherein the geographic feature is a road segment.

16. The method of claim 14 wherein said step of comparing is performed by comparing curvature.

17. The method of claim 14 wherein said step of comparing is performed by computing areas between the generalized data representation of the geographic feature and the generalized ground truth representation of the geographic feature and then comparing the areas.

18. The method of claim 14 wherein said step of comparing is performed by computing a rotational variation coefficient.

19. The method of claim 14 wherein the step of generalizing is performed using Douglas-Peucker generalization.

20. The method of claim 14 wherein the data representation of the geographic feature and the ground truth representation of the geographic feature are generalized to several different degrees of generalization and comparisons are made between the generalization of the data representation of the geographic feature and the generalization of the ground truth representation of the geographic feature at each of these different levels of generalization.

21. A method of comparing a first geometric shape to a plurality of candidate geometric shapes comprising:

forming a candidate pool that contains the plurality of candidate geometric shapes; and

eliminating all but one of said plurality of candidate geometric shapes from said candidate pool by repeatedly performing the steps of;

reducing to a given degree of generalization a data representation of the first geometric shape to form a generalized first geometric shape illustrating trends in the first geometric shape;

reducing to the given degree of generalization each candidate geometric shape in said candidate pool to form a corresponding generalized candidate geometric shape illustrating trends in the candidate geometric shape;

comparing each generalized candidate geometric shape in the candidate pool to the generalized first geometric shape;

eliminating from the candidate pool each generalized candidate geometric shape that does not match the generalized first geometric shape to a defined degree; and

if more than one candidate geometric shape remains in the candidate pool, decreasing the given degree of generalization for greater resolution in the generalized first geometric shape and the generalized candidate geometric shapes.