Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2002-09-24
2003-05-27
Black, Thomas G. (Department: 3663)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S226000, C342S357490, C342S450000, C702S094000, C702S150000, C702S179000, C356S139030
Reexamination Certificate
active
06571173
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to data representations of geographic features and more particularly, relates to a way to measure how closely one three-dimensional space curve matches another three-dimensional space curve.
BACKGROUND OF THE INVENTION
There exist applications where it is desirable to compare and match data represented as three-dimensional space curves. One such application is measurement of geographic database accuracy. This application involves measuring how closely a database representation of a geographic feature matches the actual shape of the geographic feature. Another application which requires comparison of three-dimensional space curves is three-dimensional map matching (vehicle positioning). In a map matching application, one way to determine the position of a moving vehicle with respect to a map database is to find the best match between the vehicular path, as determined by processing sensor data, and the database representation of the paths that form the road network upon which the vehicle is traveling.
Currently, geographic features are often represented in two-dimensions in map databases. For example, some of the two-dimensional map data may be represented in both longitudinal and latitudinal directions, but not necessarily in the altitudinal direction. Nevertheless, processing two-dimensional data for map-matching or map database accuracy evaluation can be time consuming and computationally intensive.
To provide a more accurate database representation and/or utilize available sensor information, geographic features may also be represented as three-dimensional space curves in map databases. For example, using modern sensors, some geographic features or vehicular paths may now be represented in three dimensions, i.e., using longitudinal, latitudinal, and altitudinal components. With more information to process than with traditional two-dimensional systems, however, methods for processing three-dimensional space curves may introduce even more complexity, and can be more computationally intensive than systems which utilize two-dimensional data. Applications using three-dimensional data might require alternative methods for comparing and matching the space curves.
Accordingly, there exists a need to compare and match a three-dimensional space curve to another three-dimensional space curve in a computationally efficient manner.
SUMMARY OF THE INVENTION
To address these and other objectives, the exemplary embodiments provide methods for comparing and quantifying the degree of shape similarity between space curves in three-dimensional space.
According to an exemplary embodiment, tangent vectors are determined at corresponding locations along first and second three-dimensional space curves. A first difference between the angles made by a projection onto a plane of each tangent vector at corresponding locations with an axis within the plane is computed. A second difference between the angles made by the tangent vectors at corresponding locations and the plane is computed. A variance is computed of pairs comprised of corresponding first and second angle differences from a constant. The variance is an indication of how closely the first and second space curves match.
According to another exemplary embodiment, a three-dimensional space curve representation of a vehicle trajectory is compared to a three-dimensional space curve representation of a road. Tangent vectors are computed at corresponding locations along the three-dimensional space curve representations. The degree of similarity between the representations may be determined as described in the first exemplary embodiment.
In yet another exemplary embodiment, database accuracy is determined. A three-dimensional space curve representation of a geographic feature is compared to a more accurate three-dimensional space curve representation of the same geographic feature. Tangent vectors are computed at corresponding locations along the three-dimensional space curve representations. The degree of similarity between the representations may be determined as described in the first exemplary embodiment.
The exemplary embodiments provide a quantitative measure of the similarity between a pair of space curves in three-dimensional space. They are effective tools for comparing three dimensional space curves while being simple, intuitive and computationally non-intensive. The exemplary embodiments are particularly useful for map matching in in-vehicle navigation systems as well as for other applications that require accurate positioning of the vehicle with respect to the underlying map data referenced by the system. Additionally, they are useful in measuring and/or evaluating the accuracy of a geographic database.
REFERENCES:
patent: 4144571 (1979-03-01), Webber
patent: 5065348 (1991-11-01), Kuragano et al.
patent: 5596494 (1997-01-01), Kuo
patent: 5742924 (1998-04-01), Nakayama
patent: 5848377 (1998-12-01), Wong
patent: 5969665 (1999-10-01), Yufa
patent: 6088663 (2000-07-01), Wang
patent: 6263089 (2001-07-01), Otsuka et al.
patent: 6389333 (2002-05-01), Hansman et al.
Black Thomas G.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corporation
Shutter Jon D.
LandOfFree
Three-dimensional space curve comparison using spatial angle... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Three-dimensional space curve comparison using spatial angle..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three-dimensional space curve comparison using spatial angle... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030737