Automatic chain-based conflation of digital maps

• US 5,546,107 A
• Filed: 04/05/1994
• Issued: 08/13/1996
• Est. Priority Date: 04/05/1994
• Status: Expired due to Term

• Current Assignee: Tele Atlas North America (TomTom NV)
• Original Assignee: Etak, Inc. (TomTom NV)
• Inventors: Rodny, Uri, White, Marvin S. Jr., Deretsky, Zachary Y.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US08/222,965
• Time in Patent Office: 861 Days
• Field of Search: 395/600, 340/995, 364/420
• US Class Current: 707/695
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

The method of the present invention which employs conflation is based on pairing chains of arcs in order to determine the matching intersections between them. The chains are formed a priori in each map by using both attributes and geometric properties of the arcs. The intersections of chains are treated as relations, stored in a simple external custom relational database. The matching procedure is a set of the standard operations on RDBMS, as well as the sieving out of all possible ambiguous identifications. As a result, both maps become partitioned by the chains into much smaller pairwise matched areas called wards. The positional and semantic information from the matched chains is mapped onto the merged map. The mapping is performed by a general nonlinear transformation function. The transformation is then extended to the mapping of the unmatched content of wards onto the ultimate map. Any combination of geometry and attribute can be selected from either of a pair of matched wards for inclusion in the merged ward.

Claims

1. A method of making a third digital map C from first and second digital maps A and B comprising the steps of:

a. creating an initial version of map C by importing into map C all cells present in map A together with their attributes;

b. matching chains of 1-cells in the map A and chains of 1-cells in the map B so as to create a corresponding pair of isomorphic factor-graphs;

c. importing unmatched 0-cells belonging to matched chains of 1-cells from map B into map C;

d. importing non-interfering unmatched 1-cells from map B into map C;

e. importing attributes of matched 0-cells and 1-cells from map B into map C according to user supplied criteria;

f. importing attributes into map C of said 1-cells from map B which were imported into map C in step d; and

g. importing attributes for 2-cells according to said user supplied criteria.

2. A method according to claim 1 wherein said matching step b comprises the steps of:

a. looking at all 1-cells on both maps A and B separately;

b. starting with a first 1-cell, looping through a list of all suitable attributes of each of said 1-cells to find another 1-cell with a same value connected to a first end of said first 1-cell;

c. if such a 1-cell is found, extending the chain up to a point where there are no more identically attributed 1-cells or more than one 1-cell is found having the same attribute value;

d. repeating steps (b) and (c) with respect to the 0-cell at a second end of said first 1-cell;

e. labeling specifically each 1-cell added to said chain to prevent said added 1-cells from being processed twice; and

f. generating a chain file of chain-records, each chain-record comprising a list of all the 1-cells added to said chain, each chain-record having a unique chain-record number and the following format;

space="preserve" listing-type="equation"><

attribute value>

<

A/B map>

<

first point on the chain>

<

last point on the chain>

.

3. A method according to claim 2 further comprising the steps of:

a. labeling each chain-record in a chain-file with a group number; and

b. if two chains have different attribute values which nevertheless may be considered to be identical, labeling each of the chain-records corresponding thereto with the same group number.

4. A method according to claim 3 further comprising the step of:

placing all 0-cells on created chains in two dot-files having the following format;

space="preserve" listing-type="equation"><

cell identifier>

<

group number>

<

chain number>

<

cell index>

,

where the <

cell index>

is a sequential index of a 0-cell in the chain.

5. A method according to claim 4 further comprising the step of:

if a b 0-cell in a dot-file belongs to two different chains, forming a record of a grid file having the following format;

space="preserve" listing-type="equation"><

amended group2>

<

A/B>

<

chain1 chain2>

. . . <

index1 index2>

<

cell id>

.

6. A method according to claim 5, further comprising the steps of:

a. if there are records in a grid file, one from map A and one from map B with the same pair of groups, forming a track-file by combining pairs of records of grid-files wherein records in the grid files of each of the maps has the following format;

space="preserve" listing-type="equation"><

group1 group2>

<

A>

<

chainA1 chainA2>

. . . <

indexA1 indexA2>

<

cell A>

space="preserve" listing-type="equation"><

group1 group2>

<

B>

<

chainB1 chainB2>

. . . <

indexB1 indexB2>

<

cell B>

;

the two track-records corresponding to the same intersection have the following format;

space="preserve" listing-type="equation"><

chainA1 chainB1>

<

indexA1 index B1>

<

cell A cell B>

space="preserve" listing-type="equation"><

chainA2 chainB2>

<

indexA2 index B2>

<

cell A cell B>

;

b. labeling those chains which belong to more than one group in order to prevent formation of numerous false potential matches; and

c. sorting the resulting track-file lexicographically.

7. A method according to claim 1 wherein said matching step b comprises the step of:

building an isomorphism between two subsets of 0-cells by several successive runs of different filtering procedures which reject certain potential matches if they are recognized as invalid.

8. A method according to claim 7, comprising the steps of:

a. recognizing multiple intersections of a chain from map A and a chain from map B;

b. detecting a mutual orientation of potentially matchable chains; and

c. rejecting potential 0-cell matches which do not agree with the orientation.

9. A method according to claim 7, comprising the step of:

rejecting track-file records when the distance between potentially matched 0-cells from maps A and B exceed a certain threshold.

10. A method according to claim 7, comprising the step of:

rejecting all but one of multiple matches of 0-cells within a chain.

11. A method according to claim 7, comprising the step of:

if a part of a chain in map A is potentially matched to more than one other chain in map B, rejecting all but the longest such chain.

12. A method according to claim 7, comprising the step of:

rejecting all but one of the multiple matches on maps A and B.

13. A method according to claim 7, comprising the step of:

recognizing potential 0-cell matches with non-monotone indices.

14. A method according to claim 7, comprising the step of:

rejecting all potential matches which have been rejected by any preceding modules.

15. A method according to claim 7, comprising the step of:

rejecting all 0-cell matches at which chains on either map A or B intersect in their internal parts.

16. A method according to claim 7, comprising the steps of:

in cases wherein endpoints of chains from maps A and B are not found in a track-file, testing the dangling parts of the chains for possible matching by

a. means of a geometric verification; and

b. an ambiguity check.

17. A method according to claim 7, comprising the steps of:

a. identifying chains from maps A and B with a single potential match; and

b. determining if the match is identical with an actual match on another chain.

18. A method according to claim 7 comprising the steps of:

a. creating 0-dim and 1-dim factor-graphs for each of maps A and B;

b. marking the factor-graphs identically; and

c. storing the factor-graphs in corresponding files of the matched chains.

19. A method according to claim 7 comprising the steps of:

selecting potentially matchable single 1-cells, as distinguished from chains, from both maps A and B using only geometric properties of the cells, i.e. bounding boxes and distances.

20. A method according to claim 7 comprising the steps of:

creating files of bounding boxes of the unmatched 1-cells from both the A and B maps.

21. A method according to claim 7 comprising the steps of:

a. normalizing box sizes by dividing them by a threshold; and

b. putting them in a box file.

22. A method according to claim 7 comprising the steps of:

a. producing a list of potentially matching 1-cells by comparing boxes read from a box-file; and

b. placing the resulting lists in a parabox-file.

23. A method according to claim 7 comprising the steps of:

a. computing distances between potentially matching 1-cells; and

b. selecting one distance which gives the minimum distance.

24. A method according to claim 7 comprising the step of:

transforming selected pairs of the unmatched 1-cells into trivial single-cell chains.

25. A method according to claim 7 comprising the steps of:

a. selecting the matched chains one by one;

b. traversing each selected chain in a certain direction;

c. once the traversing step arrives at a matched 0-cell, choosing the next matched chain as the leftmost of the possible continuations;

d. when a loop is closed, checking that the order and orientation of the loops from both maps A and B are identical; and

e. removing the chains which violate an order and orientation identity from a list of the matched chains.

26. A method according to claim 7 comprising the step of:

a. if an isomorphism between factor-2-cells can be defined, verifying that the isomorphic loops of factor-1-cells contain inside themselves sets of the other (or none) isomorphic loops;

b. rejecting the loops which do not meet the conditions of paragraph (a) above.

27. A method according to claim 7 comprising the step of:

a. determining which factor-2-cells are isomorphic; and

b. storing isomorphic factor-2-cells in a so-called file of wards.

28. A method according to claim 1 wherein said importing step d comprises the step of importing non-interfering unmatched 1-cells from map B into map C which, except for a predetermined portion of their respective ends, are, when the 1-cells are imported into map C, at least a predetermined distance from any adjacent 1-cell in the map C.

29. A method according to claim 28 wherein said importing step d comprises the step of utilizing a modified Bresenham algorithm for wide lines.

30. A method according to claim 29 wherein said step of utilizing a modified Bresenham algorithm for wide lines comprises the step of generating an array of square boxes which are superimposed in map C on the 1-cells imported from map A into map C, each of said boxes corresponding to a predetermined area.

31. A method according to claim 30 wherein said step of generating an array of square boxes which are superimposed in map C on the 1-cells imported from map A into map C, comprises the step of importing the array of boxes in map C into map B to identify the unmatched 1-cells in map B which will not interfere with the 1-cells from map A, each of said boxes corresponding to a predetermined area.

32. A method of making a third digital map C from a first digital map A and a second digital map B, maps A and B including 0-cells, 1-cells and 2-cells, the 0-cells, 1-cells and 2 cells having associated attributes, the method comprising the steps of:

creating an initial version of map C by in, porting into map C 0-cells, 1-cells and 2-cells present in map A together with the associated attributes;

creating chains of 1-cells of map A such that each chain includes 1-cells having a similar attribute;

creating chains of 1-cells of map B such that each chain includes 1-cells having a similar attribute;

matching said chains of 1-cells of map A with said chains of 1-cells of map B;

importing non-interfering unmatched 1-cells from map B into map C;

importing attributes of matched 1-cells and non-interfering unmatched 1-cells from map B into map C according to user supplied criteria; and

importing attributes for 2-cells from map B to map C according to said user supplied criteria.

33. A method according to claim 32, further including the steps of:

importing unmatched 0-cells belonging to matched chains of 1-cells from map B into map C; and

importing attributes of said unmatched 0-cells belonging to matched chains from map B to map C.

34. A method according to claim 32, wherein the step of creating chains of 1-cells of map A comprises the steps of:

starting with a first 1-cell of map A to create a first chain;

adding to said first chain a second 1-cell that has suitable attributes and is connected to a first end of said first 1-cell via a 0-cell; and

continuing to add additional 1-cells to said first chain until no more 1 cells remain with suitable attributes and connections, each of said added additional 1-cells having suitable attributes and being connected to an end of a 1-cell previously added to said first chain.

35. A method according to claim 32, wherein further including the step of:

determining that an unmatched 1-cell is non-interfering by determining that said unmatched 1-cell, except for a predetermined portion of both ends of said unmatched 1-cell, is a predetermined distance from any adjacent 1-cell in map c.

36. A method according to claim 32 wherein said step of importing non-interfering unmatched 1-cells from map B into map C comprises the step of utilizing a modified Bresenham algorithm for wide lines.

37. A method according to claim 36 wherein said step of utilizing a modified Bresenham algorithm for wide lines comprises the step of generating an array of square boxes which are superimposed on map C on the 1-cells imported from map A into map C, each of said boxes corresponding to a predetermined area.

38. A method according to claim 37 wherein said step of generating an army of square boxes which are superimposed on map C on the 1-cells imported from map A into map C, comprises the step of importing the army of boxes in map C into map B to identify the unmatched 1-cells in map B which will not interfere with the 1-cells from map A, each of said boxes corresponding to a predetermined area.

39. A method of making a third digital map C from a first digital map A and a second digital map B, maps A and B including 0-cells, 1-cells and 2-cells, the cells having attributes, the method comprising the steps of:

creating an initial version of map C by importing into map C 0-cells, 1-cells and 2-cells present in map A together with the attributes;

creating chains of 1-cells of map A such that each chain includes 1-cells having a similar attribute;

creating chains of 1-cells of map B such that each chain includes 1-cells having a similar attribute;

matching said chains of 1-cells of map A with said chains of 1-cells of map B;

determining that an unmatched 1-cell is non-interfering by determining that said unmatched 1-cell, except for a predetermined portion of both ends of said unmatched 1-cell, is a predetermined distance from any adjacent 1-cell in map C;

importing non-interfering unmatched 1-cells from map B into map C;

importing unmatched 0-cells belonging to matched chains of 1-cells from map B into map C;

importing attributes of said unmatched 0-cells belonging to matched chains from map B to map C;

importing attributes of matched 1-cells and non-interfering unmatched 1-cells from map B into map C according to said user supplied criteria; and

importing attributes for 2-cells from map B to map C according to said user supplied criteria.

40. A method according to claim 39, wherein the step of creating chains of 1-cells of map A comprises the steps of:

starting with a first 1-cell of map A to create a first chain;

adding to said first chain a second 1-cell that has suitable attributes and is connected to a first end of said first 1-cell via a 0-cell; and

continuing to add additional 1-cells to said first chain until no more 1 cells remain with suitable attributes and connections, each of said added additional 1-cells having suitable attributes and being connected to an end of a 1-cell previously added to said first chain.