Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2002-04-29
2003-10-21
Beaulieu, Yonel (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
Reexamination Certificate
active
06636804
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data representations of geographic features in a geographic database and more particularly, the present invention relates to a method for determining geographic feature association between the geographic features of one geographic database and the geographic features of another geographic database.
A geographic database contains data that represents some of the physical features in a geographic region. Located in the geographic region are physical features, such as road networks, points of interest (including businesses, municipal facilities, etc.), lakes, rivers, railroads, municipalities, etc. The road network includes, among other things, roads and intersections located in the geographic region. Each road in the geographic region is composed of one or more road segments that represent a portion of the road. Generally, the geographic database that represents the geographic region contains at least one database record (also referred to as “entity” or “entry”) for each road segment in the geographic region.
The need to establish an association between geographic features represented in one database with the geographic features represented in another database arises in various applications relating to the use of the data representations of the geographic features. Some of these applications include measuring geographic database accuracy, detecting geographic database changes and geographic database conflation. For instance, measuring geographic database accuracy evaluates how closely a representation of the geographic features (e.g., sampled road segments) match the actual geographic features (e.g., ground truth road segments).
One method for associating the geographic features of two geographic databases is to visually identify which geographic feature of a second geographic database most likely corresponds to one of the geographic features of a first geographic database. Typically, a map containing the graphical representation of the geographic features of the first database for a particular region is plotted over a map containing the graphical representation of the geographic features of the second database for the same region. If a geographic feature of the first geographic database is at a similar location and has a similar shape as a geographic feature of the second geographic database, for example, the two features nearly overlap, the two features are selected as being associated. This visual identification of the associated feature pairs is performed over the entire plotted region. Furthermore, this visual identification process needs to be performed for each of the numerous geographic regions represented in the databases which can be very time consuming and labor intensive.
Accordingly, there exists a need for an improved way to determine an association between the geographic features of two geographic databases.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention includes a method of determining geographic feature association between geographic features of a first geographic database and a second geographic database. An m×n proximity matrix G is built comprising a proximity value element for each of the m features of the first geographic database compared to each of the n features of the second geographic database. A singular value decomposition of the proximity matrix G is computed into a form G=TDU
T
where T is an m×m orthogonal matrix, U is an n×n orthogonal matrix, and D is a m×n diagonal matrix having a plurality of diagonal elements. The singular value decomposition is converted into an association matrix P by forming a matrix E by replacing each of the diagonal elements of the diagonal matrix with one and computing the association matrix P using the following product P=TEU
T
. An associated feature pair is identified. The associated feature pair comprises the feature in the first geographic database and the feature of the second geographic database that is a largest element in both one of the rows and one of the columns of the association matrix P.
REFERENCES:
patent: 5590261 (1996-12-01), Sclaroff et al.
patent: 2003/0055759 (2003-03-01), Conkwright et al.
Pilu, Maurizio,Digital Media Department, HP Laboratories Bristol, HPL-97-96, “Uncalibrated Stereo Correspondence by Singular Value Decomposition”, presented atComputer Vision&Pattern Recognition, Puerto Rico. (Jun., 1997).
Henrichsen, A. and de Jager, G., Department of Electrical Engineering, University of Cape Town, Rondebosch 7701, So. Africa, “Point Matching in Uncalibrated Images”, Technical Paper,Pattern Recognition Association of South Africa, PRASA (2000).
Beaulieu Yonel
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corp.
Shutter Jon D.
LandOfFree
Method for associating the features of two geographic databases does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for associating the features of two geographic databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for associating the features of two geographic databases will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136832