Method and apparatus for merging multiple road map databases

• US 6,564,224 B1
• Filed: 03/30/2000
• Issued: 05/13/2003
• Est. Priority Date: 12/06/1999
• Status: Expired due to Term

• Current Assignee: TeleCommunication Systems Inc (Comtech Telecommunications Corporation)
• Original Assignee: Kivera, Inc. (Comtech Telecommunications Corporation)
• Inventors: Wu, Xiaoyi, Synghal, Rajiv K., Whitaker, James, Collier, W. Clayton
• Primary Examiner(s): Mizrahi, Diane D.
• Assistant Examiner(s): MOFIZ, APU M
• Application Number:
  US09/539,721
• Time in Patent Office: 1,139 Days
• Field of Search: 707/104.1, 707/6, 340/995, 701/200, 701/209, 701/211
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and apparatus for combining two dissimilar road map databases of a given geographic region are provided. The road map database differ in degree of coverage or accuracy of coverage, or both, of the geographic region. Each database includes data defining a plurality of roads. A first set of loops is defined from roads represented in a first of the two road map databases. For each of the first set of loops, a corresponding loop is identified from roads represented in a second of the two road map databases, to define a second set of loops. Each loop of the second set of loops may include one or more links, and each link represents a portion of a road represented in the second road map database. A set of output loops corresponding to the first set of loops is generated to form an output road map database. Links enclosed within loops of the second set of loops and not represented in the first road map database are then copied into the set of output loops, such that the output road map database represents a combination of the first road map database and the second road map database.

Claims

1. A machine-implemented method of combining two road map databases, the method comprising:

accessing a first road map database and a second road map database, the first and second road map databases having different degrees of coverage of a geographic region and having different coverage accuracies for the geographic region; and

defining, for the first road map database, a first set of loops including a first plurality of links representing portions of roads within the geographic region covered by the first road map database;

wherein each loop of the first database is formed by selecting a starting point and traversing a smallest possible number of intersecting links forming the tightest closed polygon leading back to the starting point;

defining, for the second road map database, a second set of loops including a second plurality of segments representing portions of road within the geographic region covered by the second road map database; and

matching loops of the first road map database with loops of the second road map database to generate an output road map database representing a combination of the first road map database and the second road map database.

2. A machine-implemented method as recited in claim further comprising the steps of:

identifying links enclosed within loops of the second road map database; and

copying the identified links into loops of the first road map database.

3. A method of combining two road map databases, the method comprising:

defining a first road map database as a set of first loops comprising links, each loop of the first set of loops formed by defining a starting point and forming the tightest closed polygon joining links from the starting point;

defining a second road map database as a second set of loops, each loop of the second set of loops defined to correspond to a single loop of the first set of loops;

identifying links included within each set of loops, the links representing portions of roads;

creating an output road map database to represent a combination of the first roadmap database and the second road map database, based on the identified differences in coverage.

4. A method of combining two road map databases, each including data defining a plurality of roads, the method comprising:

defining a first set of loops from roads represented in a first road map database, each loop of the first set of loops formed by defining a starting point, forming the tightest closed polygon joining links from the starting point;

for each of the first set of loops, identifying a corresponding loop from roads represented in a second road map database, to define a second set of loops, wherein each loop of the second second of loops may include one or more links, each link representing a portion of a road represented in the second road map database;

creating a set of output loops corresponding to the first set of loops to form an output road map database; and

copying links enclosed within loops of the second set of loops and not represented in the first road map database into the set of output loops, such that the output road map database represents a combination of the first road map database and the second road map database.

5. A method or combining two road map databases that have different coverage of the same geographic area, each including data defining a plurality of roads, the method comprising:

storing a first road map database and a second road map database, wherein the first and second road map databases have different degrees of coverage of a given geographic region;

defining a first set of loops from roads represented in a first roadmap database, wherein each loop of the first set of loops may contain one or more links, each link representing a portion of a road represented in the first road map database, and wherein each loop of the first database is formed by selecting a starting point and traversing a smallest possible number of intersecting links forming the tightest closed polygon leading back to the starting point;

matching each loop of the first set of loops with a loop of a second set of loops, the second set of loops defined from roads represented in the second road map database, wherein each loop of the second set of loops may contain one or more links, each link representing a portion of a road represented in the second road map database;

checking results of said matching for accuracy and correcting efforts in the results, if any;

defining an output road network as set of loops to corresponding to the first set of loops;

adjusting particular links of the second set of loops to correct for differences between the first road map database and the second road map database;

for each loop of the second set of loops, copying links of said loop that are not represented in the first road map database into the corresponding loop of the output road network, such that the output road network represents a combination of the first road map database and the second road map database.

6. A machine-implemented method of recited in claim 5, wherein the second road map database has more complete coverage of the geographic area than the first road map database but lower accuracy than the first road map database.

7. A machine-implemented method as recited in claim 5, further comprising, prior to said matching:

creating a first set of output map files from the first road map database, each of the first set of output map files corresponding to a different loop of the first set of loops, each of the first set of output map files indicating the link, if any, that are included without a region enclosing the corresponding loop of the first set of loops;

creating a second set of output map files for the second road map database, each of the second set of output map files corresponding to a loop of the first set of loops and including one or more links represented in the second road map database.

8. A machine-implemented method of matching data of a first road map database with data of a second road map database, the method comprising:

inputting data of the first road map database in the form of a first set of loops, each loop of the first set of loops including a plurality of links, and formed by selecting a starting point and traversing a smallest possible number of intersecting links the tightest closed polygon leading back to the starting point, wherein each link represents a portion of a road;

matching each loop of the first set of loops with a loop of a second set of loops corresponding to the second road map database, by

identifying a set of nodes, each node representing an intersection of two or more roads, the set of nodes including a plurality of nodes of the first road map database and a plurality of nodes of the second road map database, and

defining each loop of the second set of loops by identifying paths between nodes of the second road map database which match paths between corresponding nodes of the first road map database.

9. A machine-implemented method as recited in claim 8, wherein said identifying paths between nodes of the second road map database which match paths between corresponding nodes of the first road map database comprises using a set of heuristics to identify the paths.

10. A machine-implemented method of recited in claim 8, wherein said assigning a set of nodes comprises:

identify a plurality of control nodes of the first road map database, and identifying a plurality of control nodes of the second road map database, such that each control node of the second road map database corresponds to a control node of the first road map database.

11. A machine-implemented method as recited in claim 8, further comprising shifting particular links in the second set of map output file to correct for positional inconsistencies between the first road map database and the second road map database.

12. A machine-implemented method as recited in claim 8, further comprising correcting misalignments of particular links in the second set of map output files between adjacent loops of the road network to eliminate discontinuities in represented roads.

13. A method of matching data in a first road map database with data in a second road map database, the method comprising:

defining data of the first road map database as a first set of loops, each loop of the first set of loops including a plurality of segments, each segment representing a portion of a road, wherein each loop of the first road map database is formed by selecting a starting point and traversing a smallest possible number of intersecting links to form the tightest polygon to the starting point;

matching each loop of the first set of loops with a loop of a second set of loops corresponding to the second road map database said matching including

assigning a set of control nodes, each control note representing an intersection of two or more roads, wherein said assigning includes

identifying a plurality of control notes of the first road map database, and

identifying a plurality of control notes of the second road map database, such that each control node of the second road map database corresponds to a control node of the first road map database; and

defining the second set of loops by heuristically determining paths between control nodes of the second roadmap database which match paths between corresponding control nodes of the first road map database, each path including one or more links;

shifting particular links in the second set of map output files to correct for positional inconsistencies between the first road map database and the second road map database; and

correcting misalignments of particular links in the second set of map output files between adjacent loops of the road network to eliminate discontinuities in represented roads.

14. A method of combining two road map databases that have different coverage of the same geographic area, each including data defining a plurality of roads, the method comprising:

storing a first road map database and a second road map database, wherein the second road map database has more complete coverage of the geographic area than the first road map database but lower accuracy than the first road map database;

defining a first set of loops from road represented in the first roadmap database, wherein each loop may contain one or more links, each link representing a portion of a road, and wherein each loop of the first set of loops formed by defining a starting point and forming the tightest closed polygon joining links from the starting point;

extracting road map data from the first road map database and the second road map database, including

creating a first set of output map files from the first road map database, each of the first set of output map files corresponding to a different loop of the first set of loops, each of the first set of output map files indicating the links, if any, that are included within a region enclosing the corresponding loop of the first set of loops;

creating a second set of output map files from the second road map database, each of the second set of output map files corresponding to a loop of the first set of loops and including one or more links represented in the second road map database;

matching each loop of the first set of loops with a loop of a second set of loops corresponding to the second road map database, using the first set of output map files and the second set of output map files, wherein the second set of loops is defined by roads represented in the second road map database, wherein said matching includes

assigning a set of control notes, each control note representing an intersection of two or more road, wherein said assigning includes

identifying a plurality of control nodes of the first road map database, and

identifying a plurality of control nodes of the second road map database, such that each control node of the second road map database corresponds to a control node of the first road map database; and

defining the second set of loops by determining paths between control nodes of the second road map database which match paths between corresponding control nodes of the first road map database;

checking results of said matching for accuracy and correcting errors in the results, if any, wherein said checking and correcting include

automatically performing a first stage of said checking and correcting based on a predefined algorithm;

performing a second stage of said checking and correcting by receiving and implementing user inputs specifying corrections;

generating a road network from the loops defined by the first set of output map files;

adjusting particular links in the second set of map output files to correct for positional inconsistencies between the first road map database and the second road map database;

correcting misalignments of particular links in the second set of map output files between adjacent loops of the road network to eliminate discontinuities in represented roads;

for each loop of the second set of loops, copying the included links that are not represented in the first road map database into the corresponding loop in the road network; and

copying the road network into a new database representing both the first road map database and the second road map database.

15. An apparatus for combining two road map database, the apparatus comprising:

means for accessing a first road map database and second road map database, the first and second road map databases having different degrees of coverage of a geographic region and having different coverage accuracies for the geographic region; and

means for defining, for the first road map database, a first set of loops including a first plurality of links representing portions of roads within the geographic region covered by the first road map database;

wherein each loop of the first database is formed by selecting a starting point and traversing a smallest possible number of intersecting links forming the tightest closed polygon leading back to the starting point;

means for defining for the second road map database, a second set of loops including a second plurality of segments representing portions of roads within the geographic region covered by the second road map database; and

means for matching loops of the first road map database with loops of the second road map database to generate an output road map database representing a combination of the first road map database and the second road map database.

16. An apparatus for combining two road map database, each including data defining a plurality of roads, the apparatus comprising:

means for defining a first set of loops from roads represented in a first road map database;

means for defining a first road map database as a set of first loops comprising links, each loop of the first set of loops formed by defining a starting point and forming the tightest closed polygon joining links from the starting point;

means for defining a second road map database as, a second set of loops, each loop of the second set of loops defined to correspond to a single loop of the first set of loops;

means for identifying, for each of the first set of loops, a corresponding loop from roads represented in a second road map database, to define a second set of loops, wherein each loop of the second set of loops may include one or more links, each link representing a portion of a road represented in the second road map database;

means for creating a set of output loops corresponding to the first set of loops to form an output road map database; and

means for copying links enclosed within loops of the second set of loops and not represented in the first road map database into the set of output looks, such that the output road map database represents a combination of the first road map database and the second road map database.

17. A processor system comprising:

a processor;

a first storage facility coupled to the processor, the first storage facility storing a first road map database;

a second storage facility coupled to the processor, the second storage facility storing a second road map database, the first and second road map databases having different degrees of coverage of a geographic region and having different coverage accuracies for the geographic region; and

a third storage facility coupled to the processor, the third storage facility storing sequences of instructions which configure the processor to;

access the first road map database and the second road map database;

defining a first road map database as a set of first loops comprising links, each loop of the first set of loops formed by defining a starting point and forming the tightest closed polygon joining links from the starting point;

defining a second road map database as a second set of loops, each loop of the second set of loops defined to correspond to a single loop of the first set of loops;

identify links included within each set of loops, the links representing portions of roads;

identify differences in coverage between the first toad map database and the second road map database based on the sets of loops; and

create an output road map database to represent a combination of the first road map database and the second road map database, based on the identified differences in coverage.

18. A machine-readable storage medium storing a road map database of a geographic region, the road map database representing a computer-generated combination of a first road map database and a second road map database, the first road map database and the second road map database differing in degree of coverage and accuracy of coverage of the geographic region, the road map database including a plurality of loops, each loop defined as a plurality of links, each link representing a portion of a road represented in both the first road map database and the second road map database, the road map database further including a plurality of links enclosed within particular ones of said loops, wherein the plurality of links enclosed within particular ones of said loops include links that are represented in the second road map database but not the first road map database, and wherein each loop of a first set of loops of the first road map database are formed by defining a starting point and forming the tightest closed polygon joining links from the starting point.

19. An apparatus comprising:

means for inputting data of a first road map database as a first set of loops, each loop of the first road map database including a plurality of segments and formed by defining a starting point, forming the tightest closed polygon joining links from the starting point, each segment representing a portion of a road;

means for matching each loop of the first set of loops with a loop of a second set of loops corresponding to a second road map database, the means for matching including

means for assigning a set of control nodes, each control node representing an intersection of two or more roads, the set of control nodes including a plurality of control nodes of the first road map database and a plurality of control nodes of the second road map database, and

means for defining each loop of the second set of loops by identifying paths between control nodes of the second road map database which match paths between corresponding control nodes of the first road map database.