Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-05-22
2003-05-06
Nguyen, Tan Q. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S213000, C340S990000, C340S988000
Reexamination Certificate
active
06560531
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method for comparing geometric shapes to each other. One application of the present invention relates to a method for determining a position of a vehicle with respect to a road network. Another application of the present invention relates to a way to measure the relative accuracy of a data representation of a geographic feature.
The need to compare geometric shapes arises in various applications relating to the use of data representations of geographic features. Included among these applications are vehicle positioning (e.g., in navigation systems) and the measurement of geographic database accuracy. For instance, in a vehicle positioning application, one way to determine the position of a vehicle traveling along a road network is to find the best match between the historical vehicular path (as determined by processing data from sensors, such as GPS, inertial sensors, etc.) and the roads that form the road network upon which the vehicle is traveling (as represented by map data contained in a database that represents the road network). A conventional approach to vehicle positioning is to directly compare the shape of the historical vehicular path to each of a plurality of candidate map paths and then select that map path whose shape most closely resembles the vehicular path as the one on which the vehicle is located. The comparison can be accomplished using any of a number of pattern recognition techniques, such as cross-correlation. Generally, this approach provides satisfactory results. However, the comparison of one geometric shape to another can be computationally intensive. If the number of candidate map paths is relatively large, the determination of which candidate map path best matches the historical vehicular path can take a relatively long time. Accordingly, there exists a need for a way to determine a vehicle position with respect to the data representation of a road network that is less computationally intensive than prior approaches.
Another application that uses the comparison of geometric shapes is measurement of geographic database accuracy. A data representation of a geographic feature is called a sampled representation. A sampled representation of a geographic feature, such as a road, is accurate if it closely resembles ground truth. There exists a need for a way to compare a sampled data representation of a geographic feature to ground truth and to measure and quantify the accuracy (or equivalently, error) of the sampled representation.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention provides a method for comparing geometric shapes to each other. The method is referred to herein as the multi-resolution trend metric. The multi-resolution trend metric method can be used in various applications that require determining which one of several geometric shapes most closely resembles another geometric shape, or how closely two geographic shapes resemble each other.
One application in which the multi-resolution trend metric method can be used is vehicle positioning. When used for vehicle positioning, the method is a tool for determining which map path (i.e., which data representation of a portion of the road network located around a vehicle) of several candidate map paths best matches an actual path (as measured by sensors, e.g., GPS, inertial sensors) traveled by the vehicle. According to the multi-resolution trend metric method, 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. Then, 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 (thereby allowing more detail into the representations), 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 remaining map path is the path that best approximates the vehicle path and the vehicle is determined to be located on the map path, specifically at the leading end of this map path.
Another application to which the multi-resolution trend metric concept can be applied is evaluation of the accuracy of a geographic database. It is desirable to determine how well a sampled geographic feature follows ground truth. A generalized version of a sampled geographic feature is compared, using the multi-resolution trend metric, to a generalized version of ground truth of the feature to determine how well the generalized versions (i.e., the overall trends) match. This comparison can be a useful metric in comparing relative geometric accuracy. Furthermore, by performing this comparison for varying degrees of generalization, the error between the sampled and ground truth representations of the geographic feature can be determined as a function of resolution.
REFERENCES:
patent: 4963864 (1990-10-01), Iihoshi et al.
patent: 4970652 (1990-11-01), Nagashima
patent: 5016007 (1991-05-01), Iihoshi et al.
patent: 5283575 (1994-02-01), Kao et al.
patent: 5311173 (1994-05-01), Komura et al.
patent: 5422815 (1995-06-01), Hijikata
patent: 5774824 (1998-06-01), Streit et al.
patent: 6002981 (1999-12-01), Kreft
patent: 6023653 (2000-02-01), Ichimura et al.
patent: 6192312 (2001-02-01), Hummelsheim
patent: 6346942 (2002-02-01), Endo et al.
patent: 6385539 (2002-05-01), Wilson et al.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corporation
Nguyen Tan Q.
Shutter Jon D.
LandOfFree
Multi-resolution trend metric for shape comparison and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-resolution trend metric for shape comparison and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-resolution trend metric for shape comparison and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065407