Matching geometric objects

• US 6,532,304 B1
• Filed: 10/21/1998
• Issued: 03/11/2003
• Est. Priority Date: 10/21/1998
• Status: Expired due to Term

• Current Assignee: Tomtom North America Incorporated (TomTom NV)
• Original Assignee: Tele Atlas North America (TomTom NV)
• Inventors: Liu, Hongche, Kuttikkad, Shyam
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): Dastouri, Mehrdad
• Application Number:
  US09/176,243
• Time in Patent Office: 1,602 Days
• Field of Search: 382/203, 382/218, 382/219, 382/220, 382/199, 345/126, 345/441, 345/442
• US Class Current: 382/203
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A system is disclosed for identifying matching arcs in sets of geometric objects, such as a pair of electronic maps, without relying on attributes being assigned to the arcs. An arc in a first set of geometric objects is identified as matching an arc in a second set of geometric objects, when the arc in the first set is co-bounded on both sides by polygons which match the corresponding co-bounding polygons of the arc in the second set. A determination is made of which polygons in the first set of geometric objects match polygons in the second set of geometric objects, by computing and comparing a set of similarity metrics. Examples of characteristics for which similarity metrics are determined include, proximity, area, shape and rotation. Each similarity metric is determined in an isolated fashion, so that no other metric is reflected in the metric being measured.

Claims

1. A computer implemented method for determining a degree of similarity between a first geometric object and a second geometric object on separate maps of the same geographic region, said method comprising the steps of:

(a) determining a set of similarity metrics for said first geometric object and said second geometric object such that no other metric is reflected in the metric being measured, wherein said step (a) includes the step of determining a proximity similarity metric for inclusion in said set of similarity metrics and wherein determining said proximity similarity metric includes the steps of;

computing a first centroid for said first geometric object;

computing a second centroid for said second geometric object;

determining a displacement between said first centroid and said second centroid; and

calculating said proximity similarity metric based on said displacement without translating said first centroid of said first geometric object and said second centroid of said second geometric object to a common point; and

(b) determining said degree of similarity based on said set of similarity metrics.

2. The method of claim 1, wherein said step (a) further includes the step of:

determining an area similarity metric for inclusion in said set of similarity metrics.

3. The method of claim 2, wherein said step (a) further includes the step of:

determining a shape similarity metric for inclusion in said set of similarity metrics.

4. The method of claim 3, wherein said step (a) further includes the step of:

determining a rotation similarity metric for inclusion in said set of similarity metrics.

5. The method of claim 4, wherein said step of determining said area similarity metric includes the steps:

generating a first set of vectors for said first geometric object;

generating a second set of vectors for said second geometric object;

determining a first area value for said first geometric object based on said first set of vectors; and

determining a second area value for said second geometric object based on said second set of vectors.

6. The method of claim 5, wherein said step of generating said first set of vectors includes the steps of:

selecting N number of points along a perimeter of said first geometric object;

generating a first set of preliminary vectors, wherein each vector in said set of preliminary vectors extends from said centroid of said first geometric object to one said N number of points; and

subtracting the centroid from a start point and an end point for each vector in said set of preliminary vectors to obtain said first set of vectors.

7. The method of claim 5, wherein said step of determining said area similarity metric further includes the step of:

calculating said area similarity metric based on said first area value and said second area value.

8. The method of claim 5, wherein said step of determining a shape similarity metric includes the steps of:

normalizing said first set of vectors to obtain a first set of normalized vectors;

normalizing said second set of vectors to obtain a second set of normalized vectors; and

generating a set of shape measures, wherein each shape measure in said set of shape measures is based on a comparison of said first set of normalized vectors and said second set of normalized vectors at a different rotation.

9. The method of claim 8, wherein said step of determining a shape similarity metric further includes the steps of:

selecting a shape measure in said set of shape measures to be said shape similarity metric, wherein said selected shape measure is smaller than all other shape measures in said set of shape measures.

10. The method of claim 9, wherein said step of determining said rotation similarity metric includes the step of:

determining a rotation measure based on angular differences between corresponding vectors in said first set of vectors and said second set of vectors, wherein said angular differences are determined with said first set of vectors and said second set of vectors having a rotational relationship corresponding to a rotation corresponding to said selected shape measure.

11. The method of claim 10, wherein said step of determining said rotation similarity metric includes the steps of:

calculating said rotation similarity metric based on said rotation measure.

12. The method of claim 1, wherein said set of similarity metrics determined in said step (a) includes a proximity similarity metric, an area similarity metric, a shape similarity metric, and a rotation similarity metric.

13. The method of claim 12, wherein said step (b) includes the step of:

calculating the product of said proximity similarity metric, said area similarity metric, said shape similarity metric, and said rotation similarity metric.

14. A computer implemented method for identifying a pair of matching arcs, wherein a first arc in said pair resides in a first set of geometric objects and a second arc in said pair resides in a second set of geometric objects, said method comprising the steps of:

(a) determining a degree of similarity for each possible combination of one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects, wherein said step (a) includes the steps of;

determining a set of similarity metrics for each of said possible combinations; and

determining said degree of similarity for each of said possible combinations based on said set of similarity metrics;

(b) identifying pairs of geometric objects based on said degrees of similarity determined in said step (a); and

(c) identifying said pair of matching arcs based on said pairs of geometric objects identified in said step (b), wherein said step (c) includes the steps of;

determining whether said first arc is co-bounded on a first side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects; and

determining whether said first arc is co-bounded on a second side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects.

15. The method of claim 14, wherein said step (b) includes the steps of:

selecting one of said possible combinations; and

determining whether a degree of similarity determined for said selected one of said possible combinations has a degree of similarity at least meeting a predetermined threshold.

16. The method of claim 15, wherein said step (b) further includes the step of:

pairing a first geometric object in said first set of geometric objects with a second geometric object in said second set of geometric objects, wherein a degree of similarity for a combination of said first geometric object and said second geometric object, as determined in said step (a), is not less than a degree of similarity, as determined in said step (a), for any combination of geometric objects containing either said first geometric object or said second geometric object.

17. The method of claim 16, wherein said set of similarity metrics determined in said step (a) includes a proximity similarity metric, an area similarity metric, a shape similarity metric, and a rotation similarity metric.

18. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for determining a degree of similarity between a first geometric object and a second geometric object on separate maps of the same geographic region, said method comprising the steps of:

(a) determining a set of similarity metrics for said first geometric object and said second geometric object, wherein said step (a) includes the step of determining a proximity similarity metric for inclusion in said set of similarity metrics and wherein determining said proximity similarity metric includes the steps of;

computing a first centroid for said first geometric object;

computing a second centroid for said second geometric object;

determining a displacement between said first centroid and said second centroid; and

calculating said proximity similarity metric based on said displacement without translating said first centroid of said first geometric object and said second centroid of said second geometric object to a common point; and

(b) determining said degree of similarity based on said set of similarity metrics.

19. The processor readable storage medium of claim 18, wherein said step (a) includes the steps of:

determining an area similarity metric for inclusion in said set of similarity metrics;

determining a shape similarity metric for inclusion in said set of similarity metrics; and

determining a rotation similarity metric for inclusion in said set of similarity metrics.

20. The processor readable storage medium of claim 19, wherein said step of determining said area similarity metric includes the steps:

generating a first set of vectors for said first geometric object;

generating a second set of vectors for said second geometric object;

determining a first area value for said first geometric object based on said first set of vectors; and

determining a second area value for said second geometric based on said second set of vectors.

21. The processor readable storage medium of claim 20, wherein said step of determining a shape similarity metric includes the steps of:

normalizing said first set of vectors to obtain a first set of normalized vectors;

normalizing said second set of vectors to obtain a second set of normalized vectors; and

generating a set of shape measures, wherein each shape measure in said set of shape measures is based on a comparison of said first set of normalized vectors and said second set of normalized vectors at a different rotation.

22. The processor readable storage medium of claim 21, wherein said step of determining a shape similarity metric further includes the steps of:

selecting a shape measure in said set of shape measures to be said shape similarity metric, wherein said selected shape measure is smaller than all other shape measures in said set of shape measures.

23. The processor readable storage medium of claim 22, wherein said step of determining said rotation similarity metric includes the step of:

determining a rotation measure based on angular differences between corresponding vectors in said first set of vectors and said second set of vectors, wherein said angular differences are determined with said first set of vectors and said second set of vectors having a rotational relationship corresponding to a rotation corresponding to said selected shape measure.

24. The processor readable storage medium of claim 19, wherein said step (b) includes the step of:

calculating the product of said proximity similarity metric, said area similarity metric, said shape similarity metric, and said rotation similarity metric.

25. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for identifying a pair of matching arcs, wherein a first arc in said pair resides in a first set of geometric objects and a second arc in said pair resides in a second set of geometric objects, said method comprising the steps of:

(a) determining a degree of similarity for each possible combination of one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects, wherein said step (a) includes the steps of;

determining a set of similarity metrics for each of said possible combinations; and

determining said degree of similarity for each of said possible combinations based on said set of similarity metrics;

(b) identifying pairs of geometric objects based on said degrees of similarity determined in said step (a); and

(c) identifying said pair of matching arcs based on said pairs of geometric objects identified in said step (b), wherein said step (c) includes the steps of;

determining whether said first arc is co-bounded on a first side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects; and

determining whether said first arc is co-bounded on a second side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects.

26. The processor readable storage medium of claim 25, wherein said step (b) includes the steps of:

selecting one of said possible combinations; and

determining whether a degree of similarity determined for said selected one of said possible combinations has a degree of similarity at least meeting a predetermined threshold.

27. The processor readable storage medium of claim 26, wherein said step (b) further includes the step of:

pairing a first geometric object in said first set of geometric objects with a second geometric object in said second set of geometric objects, where in a degree of similarity for a combination of said first geometric object and said second geometric object, as determined in said step (a), is not less than a degree of similarity, as determined in said step (a), for any combination of geometric objects containing either said first geometric object or said second geometric object.

28. The processor readable storage medium of claim 27, wherein said set of similarity metrics determined in said step (a) includes a proximity similarity metric, an area similarity metric, a shape similarity metric, and a rotation similarity metric.

29. An apparatus for determining a degree of similarity between a first geometric object and a second geometric object on separate maps of the same geographic region, said apparatus comprising:

a processor; and

a processor readable storage medium, in communication with said processor, said processor readable storage medium storing code for programming said processor to perform the steps of;

(a) determining a set of similarity metrics for said first geometric object and said second geometric object, wherein said step (a) includes the step of determining a proximity similarity metric for inclusion in said set of similarity metrics and wherein determining said proximity similarity metric includes the steps of;

computing a first centroid for said first geometric object;

computing a second centroid for said second geometric object;

determining a displacement between said first centroid and said second centroid; and

calculating said proximity similarity metric based on said displacement without translating said first centroid of said first geometric object and said second centroid of said second geometric object to a common location; and

(b) determining said degree of similarity based on said set of similarity metrics.

30. The apparatus of claim 29, wherein said step (a) includes the step of:

determining an area similarity metric for inclusion in said set of similarity metrics;

determining a shape similarity metric for inclusion in said set of similarity metrics; and

determining a rotation similarity metric for inclusion in said set of similarity metrics.

31. The apparatus of claim 30, wherein said step of determining said area similarity metric includes the steps:

generating a first set of vectors for said first geometric object;

generating a second set of vectors for said second geometric object;

determining a first area value for said first geometric object based on said first set of vectors; and

determining a second area value for said second geometric based on said second set of vectors.

32. The apparatus of claim 31, wherein said step of determining a shape similarity metric includes the steps of:

normalizing said first set of vectors to obtain a first set of normalized vectors;

normalizing said second set of vectors to obtain a second set of normalized vectors; and

generating a set of shape measures, wherein each shape measure in said set of shape measures is based on a comparison of said first set of normalized vectors and said second set of normalized vectors at a different rotation.

33. The apparatus of claim 32, wherein said step of determining a shape similarity metric further includes the steps of:

selecting a shape measure in said set of shape measures to be said shape similarity metric, wherein said selected shape measure is smaller than all other shape measures in said set of shape measures.

34. The apparatus of claim 33, wherein said step of determining said rotation similarity metric includes the steps of:

determining a rotation measure based on angular differences between corresponding vectors in said first set of vectors and said second set of vectors, wherein said angular differences are determined with said first set of vectors and said second set of vectors having a rotational relationship corresponding to a rotation corresponding to said selected shape measure.

35. An apparatus for identifying a pair of matching arcs, wherein a first arc in said pair resides in a first set of geometric objects and a second arc in said pair resides in a second set of geometric objects, said apparatus comprising:

a processor; and

a processor readable storage medium, in communication with said processor, said processor readable storage medium storing code for programming said processor to perform the steps of;

(a) determining a degree of similarity for each possible combination of one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects, wherein said step (a) includes the steps of;

determining a set of similarity metrics for each of said possible combinations; and

determining said degree of similarity for each of said possible combinations based on said set of similarity metrics; and

(b) identifying pairs of geometric objects based on said degrees of similarity determined in said step (a); and

(c) identifying said pair of matching arcs based on said pairs of geometric objects identified in said step (b), wherein said step (c) includes the steps of;

determining whether said first arc is co-bounded on a first side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects; and

determining whether said first arc is co-bounded on a second side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects.

36. The apparatus of claim 35, wherein said step (b) includes the steps of:

selecting one of said possible combinations; and

determining whether a degree of similarity determined for said selected one of said possible combinations has a degree of similarity at least meeting a predetermined threshold.

37. The apparatus of claim 36, wherein said step (b) further includes the step of:

pairing a first geometric object in said first set of geometric objects with a second geometric object in said second set of geometric objects, wherein a degree of similarity for a combination of said first geometric object and said second geometric object, as determined in said step (a), is not less than a degree of similarity, as determined in said step (a), for any combination of geometric objects containing either said first geometric object or said second geometric object.

38. The apparatus of claim 37, wherein said set of similarity metrics determined in said step (a) includes a proximity similarity metric, an area similarity metric, a shape similarity metric, and a rotation similarity metric.

39. A computer implemented method for identifying a pair of matching arcs, wherein a first arc in said pair resides in a first set of geometric objects and a second arc in said pair resides in a second set of geometric objects, said method comprising the steps of:

(a) determining a degree of similarity for each possible combination of one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects, wherein said step (a) includes the steps of;

determining a set of similarity metrics for each of said possible combinations; and

determining said degree of similarity for each of said possible combinations based on said set of similarity metrics;

(b) identifying pairs of geometric objects based on said degrees of similarity determined in said step (a), wherein each pair of geometric objects includes one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects; and

(c) identifying said pair of matching arcs based on said pairs of geometric objects identified in said step (b), wherein said step (c) includes the steps of;

determining whether said first arc is co-bounded on a first side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects; and

determining whether said first arc is co-bounded on a second side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects.

40. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for identifying a pair of matching arcs, wherein a first arc in said pair resides in a first set of geometric objects and a second arc in said pair resides in a second set of geometric objects, said method comprising the steps of:

(a) determining a degree of similarity for each possible combination of one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects, wherein said step (a) includes the steps of;

determining a set of similarity metrics for each of said possible combinations; and

determining said degree of similarity for each of said possible combinations based on said set of similarity metrics;

(b) identifying pairs of geometric objects based on said degrees of similarity determined in said step (a), wherein each pair of geometric objects includes one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects; and

(c) identifying said pair of matching arcs based on said pairs of geometric objects identified in said step (b), wherein said step (c) includes the steps of;

determining whether said first arc is co-bounded on a first side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects; and

determining whether said first arc is co-bounded on a second side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects.

41. An apparatus for identifying a pair of matching arcs, wherein a first arc in said pair resides in a first set of geometric objects and a second arc in said pair resides in a second set of geometric objects, said apparatus comprising:

a processor; and

a processor readable storage medium, in communication with said processor, said processor readable storage medium storing code for programming said processor to perform the steps of;

(a) determining a degree of similarity for each possible combination of one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects, wherein said step (a) includes the steps of;

determining a set of similarity metrics for each of said possible combinations; and

determining said degree of similarity for each of said possible combinations based on said set of similarity metrics;

(b) identifying pairs of geometric objects based on said degrees of similarity determined in said step (a), wherein each pair of geometric objects includes one geometric object from said first set of geometric objects and one geometric object from said second set of geometric objects; and

(c) identifying said pair of matching arcs based on said pairs of geometric objects identified in said step (b), wherein said step (c) includes the steps of;

determining whether said first arc is co-bounded on a first side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects; and

determining whether said first arc is co-bounded on a second side by a geometric object in said first set of geometric objects that has been identified in said step (b) as a geometric object in a pair of geometric objects.