Multi-resolution trend metric for shape comparison and applications thereof
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
21 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.- View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
-
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.
-
Specification