System for matching nodes of spatial data sources

• US 6,408,085 B1
• Filed: 07/22/1998
• Issued: 06/18/2002
• Est. Priority Date: 07/22/1998
• Status: Expired due to Term

• Current Assignee: DigitalGlobe, Inc. (Galileo Parent, Inc.)
• Original Assignee: Space Imaging L.P.
• Inventors: Yuen, Patrick W.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): CHOOBIN, BARRY
• Application Number:
  US09/120,670
• Time in Patent Office: 1,427 Days
• Field of Search: 382/113, 382/159, 382/294, 382/293, 382/201, 395/600, 707/104.1
• US Class Current: 382/113
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• 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 system for matching nodes of different spatial data sources. The system matches or ties a node from one data source to another data source. The present invention uses a highly accurate exclusion technique for excluding potential corresponding nodes of a second data source. Potential corresponding nodes are selected using node degree comparison, adjacency, fourier descriptor analysis of shapes formed by connecting paths between a node under investigation and a secondary node associated with that node under investigation, an analysis of total length to secondary nodes, an angle analysis to eliminate reflections, a secondary node degree analysis, and a surrounding node correlation coefficient comparison. Using one or more of these techniques in various combinations can result in the selection of a potential corresponding node with a high degree of accuracy.

Claims

1. A process of tying a selected node of a first data source to a corresponding node of a second data source comprising the steps of:

generating trace coordinates between said selected node of said first data source and one or more secondary nodes of said first data source associated with said selected node;

generating trace coordinates between potential corresponding nodes of said second data source and one or more secondary nodes of said second data source associated with said potential corresponding nodes;

generating a fourier descriptor of said trace coordinates associated with said selected node;

generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes;

comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes;

tying said selected node to a single remaining node of said potential corresponding nodes that corresponds to said corresponding node.

2. The process of claim 1 further comprising the step of:

eliminating nonrelevant potential corresponding nodes that have a degree that is different from the degree of said selected node.

3. The process of claim 1 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by comparing total length measurements of said trace coordinates associated with said selected node with said trace coordinates associated with said potential corresponding nodes.

4. The process of claim 1 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by performing an angle analysis between said trace coordinates associated with said selected node and said trace coordinates associated with said potential corresponding nodes.

5. The process of claim 1 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by comparing the degree of secondary nodes associated with said selected node with the degree of secondary nodes associated with said potential corresponding nodes.

6. The process of claim 1 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by comparing correlation coefficients of nodes that surround said potential corresponding node.

7. The process of claim 2 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by comparing total length measurements of said trace coordinates associated with said selected node with said trace coordinates associated with said potential corresponding nodes.

8. The process of claim 3 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by performing an angle analysis between said trace coordinates associated with said selected node and said trace coordinates associated with said potential corresponding nodes.

9. The process of claim 4 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by comparing the degree of secondary nodes associated with said selected node with the degree of secondary nodes associated with said potential corresponding nodes.

10. The process of claim 5 further comprising the step of:

eliminating nonrelevant potential corresponding nodes by comparing correlation coefficients of nodes that surround said potential corresponding nodes.

11. The process of claim 1 wherein said step of generating trace coordinates between said selected node of said first data source and secondary nodes associated with said selected node further comprises the steps of:

(a) generating first trace coordinates from said selected node to an initial secondary node;

(b) storing said first trace coordinates;

(c) generating second trace coordinates from said initial secondary node back to said selected node;

(d) storing said second trace coordinates;

(e) repeating steps (a) through (d) for each secondary node associated with said selected node so that said trace coordinates between said selected node of said first data source and said secondary nodes have a first selected number of sampling points.

12. The process of claim 11 wherein said step of generating trace coordinates between said potential corresponding nodes and secondary nodes associated with said potential corresponding nodes further comprises the steps of:

(a) generating first trace coordinates from each of said potential corresponding nodes to an initial secondary node;

(b) storing said first trace coordinates;

(c) generating second trace coordinates from said initial secondary node back to each of said potential corresponding nodes;

(d) storing said second trade coordinates;

(e) repeating steps (a) through (d) for each secondary node associated with each of said potential corresponding nodes;

(f) resampling said trace coordinates between said potential corresponding nodes and secondary nodes so that said trace coordinates between said potential corresponding nodes and said secondary nodes have a second selected number of sampling points that is equal to said first selected number of sampling points.

13. The process of claim 1 wherein said steps of generating fourier descriptors comprises the steps of:

changing said trace coordinates into a series of complex numbers;

performing a fourier transformation on said series of complex numbers to generate a series of fourier descriptors;

eliminating higher order descriptors of said series of fourier descriptors to produce said fourier descriptors.

14. The process of claim 1 wherein said step of comparing further comprises:

generating correlation coefficients by correlating said fourier descriptors of said trace coordinate associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes;

eliminating nonrelevant potential corresponding nodes having a correlation coefficient associated with the selected node that is below at least one predetermined threshold.

15. The process of claim 4 wherein said step of eliminating nonrelevant potential corresponding nodes by performing an angle analysis comprises the steps of:

superimposing said select node with each of said potential corresponding nodes;

measuring acute angles formed between each branch of said trace coordinates associated with said selected node and said trace coordinates associated with each of said potential corresponding nodes;

determining the largest acute angle for each superimposed pair;

eliminating nonrelevant potential corresponding nodes whenever said largest acute angle falls below a predetermined number of degrees.

16. A computer system that is programmed to tie a selected node of a first data source to a corresponding node of a second data source by performing at least the following steps:

generating trace coordinates between said selected node of said first data source and one or more secondary nodes of said first data source associated with said selected node;

generating trace coordinates between potential corresponding nodes of said second data source and one or more secondary nodes of said second data source associated with said potential corresponding nodes;

generating fourier descriptors of said trace coordinates associated with said selected node;

generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes;

comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with each of said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes;

tying said selected node to a single remaining node of said potential corresponding nodes that corresponds to said corresponding node.

17. The computer system of claim 16 that is programmed to perform the additional following steps:

eliminating nonrelevant potential corresponding nodes by comparing total length measurements of said trace coordinates associated with said selected node with said trace coordinates associated with said potential corresponding nodes.

18. The computer system of claim 16 that is programmed to perform the additional following step:

eliminating nonrelevant potential corresponding nodes by performing an angle analysis between said trace coordinates associated with said selected node and said trace coordinates associated with said potential corresponding nodes.

19. The computer system of claim 16 that is programmed to perform the additional following step:

eliminating nonrelevant potential corresponding nodes by comparing the degree of secondary nodes associated with said selected node with the degree of secondary nodes associated with said potential corresponding nodes.

20. The computer system of claim 16 that is programmed to perform the additional following step:

eliminating nonrelevant potential corresponding nodes by comparing correlation coefficients of nodes that surround said potential corresponding node.

21. The computer system of claim 16 that is programmed such that the step of generating trace coordinates between said selected node of said first data source and secondary nodes includes the additional following steps:

(a) generating first trace coordinates from said selected node to an initial secondary node;

(b) storing said first trace coordinates;

(c) generating second trace coordinates from said initial secondary node back to said selected node;

(d) storing said second trace coordinates;

(e) repeating steps (a) through (d) for each secondary node associated with said selected node so that said trace coordinates between said selected node of said first data source and said secondary nodes have a first selected number of sampling points.

22. The computer system of claim 21 that is programmed such that the step of generating trace coordinates between said potential corresponding nodes and secondary nodes includes the additional following steps:

(a) generating first trace coordinates from each of said potential corresponding nodes to an initial secondary node;

(b) storing said first trace coordinates;

(c) generating second trace coordinates from said initial secondary node back to each of said potential corresponding nodes;

(d) storing said second trade coordinates;

(e) repeating steps (a) through (d) for each secondary node associated with each of said potential corresponding nodes;

(f) resampling said trace coordinates between said potential corresponding nodes and secondary nodes so that said trace coordinates between said potential corresponding nodes and said secondary nodes have a second selected number of sampling points that is equal to said first selected number of sampling points.

23. The computer system of claim 16 that is programmed such that the step of generating fourier descriptors includes the additional following steps:

changing said trace coordinates into a series of complex numbers;

performing a fourier transformation on said series of complex numbers to generate a series of fourier descriptors;

eliminating higher order descriptors of said series of fourier descriptors to produce said fourier descriptors.

24. The computer system of claim 16 that is programmed such that the steps of comparing further includes the additional following steps:

generating correlation coefficients by correlating said fourier descriptors of said trace coordinate associated with said selected node with said trace coordinates associated with said potential corresponding nodes;

eliminating nonrelevant potential corresponding nodes having a correlation coefficient associated with the selected node that is below at least one predetermined threshold.

25. The computer system of claim 18 that is programmed such that the step of eliminating nonrelevant potential corresponding nodes by performing angle analysis includes the additional following steps:

superimposing said selected node with each of said potential corresponding nodes;

measuring acute angle formed between each branch of said trace coordinates associated with said selected node and said trace coordinates associated with each of said potential corresponding nodes;

determining the largest acute angle for each superimposed pair;

eliminating nonrelevant potential corresponding nodes whenever said largest acute angle falls below a predetermined number of degrees.

26. A computer-readable medium that contains program code that is capable of causing a computer to perform a process of tying a selected node of a first data source to a corresponding node of a second data source in accordance with the following steps comprising:

generating trace coordinates between said selected node of said first data source and one or more secondary nodes of said first data source associated with said selected node;

generating trace coordinates between potential corresponding nodes of said second data source and one or more secondary nodes of said second data source associated with said potential corresponding nodes;

generating a fourier descriptor of said trace coordinates associated with said selected node;

generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes;

comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes of said potential corresponding nodes;

tying said selected node to a single remaining node of said potential corresponding nodes that corresponds to said corresponding node.

27. The storage medium of claim 26 wherein said program code is capable of causing said computer to perform the additional steps of:

eliminating nonrelevant potential corresponding nodes that have a degree that is different from the degree of said selected node.

28. The storage medium of claim 26 wherein said program code is capable of causing said computer to perform the additional steps of:

eliminating nonrelevant potential corresponding nodes by comparing total length measurements of said trace coordinates associated with said selected node with said trace coordinates associated with said potential corresponding nodes.

29. The storage medium of claim 26 wherein said program code is capable of causing said computer to perform the additional steps of:

eliminating nonrelevant potential corresponding nodes by performing an angle analysis between said trace coordinates associated with said selected node and said trace coordinates associated with said potential corresponding nodes.

30. The storage medium of claim 26 wherein said program code is capable of causing said computer to perform the additional steps of:

eliminating nonrelevant potential corresponding nodes by comparing the degree of secondary nodes associated with said selected node with the degree of secondary nodes associated with said potential corresponding nodes.

31. The storage medium of claim 26 wherein said program code is capable of causing said computer to perform the additional steps of:

eliminating nonrelevant potential corresponding nodes by comparing correlation coefficients of nodes that surround said potential corresponding node.

32. The storage medium of claim 26 wherein said program code is capable of causing said step of generating trace coordinates between said selected node of said first data source and secondary nodes to include the additional steps of:

(a) generating first trace coordinates from said selected node to an initial secondary node;

(b) storing said first trace coordinates;

(c) generating second trace coordinates from said initial secondary node back to said selected node;

(d) storing said second trace coordinates;

(e) repeating steps (a) through (d) for each secondary node associated with said selected node so that said trace coordinates between said selected node of said first data source and said secondary nodes have a first selected number of sampling points.

33. The storage medium of claim 32 wherein said program code is capable of causing said step of generating trace coordinates between said potential corresponding nodes and secondary nodes includes the additional steps of:

(a) generating first trace coordinates from each of said potential corresponding nodes to an initial secondary node;

(b) storing said first trace coordinates;

(c) generating second trace coordinates from said initial secondary node back to each of said potential corresponding nodes;

(d) storing said second trade coordinates;

(e) repeating steps (a) through (d) for each secondary node associated with each of said potential corresponding nodes;

(f) resampling said trace coordinates between said potential corresponding nodes and secondary nodes so that said trace coordinates between said potential corresponding nodes and said secondary nodes have a second selected number of sampling points that is equal to said first selected number of sampling points.

34. The storage medium of claim 26 wherein said program code is capable of causing said step of generating fourier descriptors to include the additional steps of:

changing said trace coordinates into a series of complex numbers;

performing a fourier transformation on said series of complex numbers to generate a series of fourier descriptors;

eliminating higher order descriptors of said series of fourier descriptors to produce said fourier descriptors.

35. The storage medium of claim 26 wherein said program code is capable of causing said step of comparing to include the additional steps of:

generating correlation coefficients by correlating said fourier descriptors of said trace coordinate associated with said selected node with said trace coordinates associated with said potential corresponding nodes;

eliminating nonrelevant potential corresponding nodes having a correlation coefficient associated with the selected node that is below at least one predetermined threshold.

36. The storage medium of claim 29 wherein said program code is capable of causing said step of performing angle analysis to include the additional steps of:

superimposing said selected node with each of said potential corresponding nodes;

measuring acute angles formed between each branch of said trace coordinates associated with said selected node and said trace coordinates associated with each of said potential corresponding nodes;

determining the largest acute angle for each superimposed pair;

eliminating nonrelevant potential corresponding nodes whenever said largest acute angle falls below a predetermined number of degrees.

37. A computer system that is programmed to tie a selected node of a first data source to a corresponding node of a second data source comprising:

means for generating trace coordinates between said selected node and one or more secondary nodes associated with said selected node;

means for generating trace coordinates between potential corresponding nodes of said second data source and one or more secondary nodes associated with said potential corresponding nodes;

means for generating fourier descriptors of said trace coordinates associated with said selected node;

means for generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes;

means for comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes;

means for tying said selected node to a single remaining node of said potential corresponding nodes that corresponds to said corresponding node.

38. The computer system of claim 37 further comprising:

means for eliminating nonrelevant potential corresponding nodes that have a degree that is different from the degree of said selected node.

39. The computer system of claim 37 further comprising:

means for eliminating nonrelevant potential corresponding nodes by comparing total length measurements of said trace coordinates associated with said selected node with said trace coordinates associated with said potential corresponding nodes.

40. The computer system of claim 37 further comprising:

means for eliminating nonrelevant potential corresponding nodes by performing an angle analysis between said trace coordinates associated with said selected node and said trace coordinates associated with said potential corresponding nodes.

41. The computer system of claim 37 further comprising:

means for eliminating nonrelevant potential corresponding nodes by comparing the degree of secondary nodes associated with said selected node with the degree of secondary nodes associated with said potential corresponding nodes.

42. The computer system of claim 37 further comprising:

means for eliminating nonrelevant potential corresponding nodes by comparing correlation coefficients of nodes that surround said potential corresponding note have been eliminated.

43. A process of associating a selected node of a first data source with a corresponding node of a second data source comprising the steps of:

identifying said selected node and one or more secondary nodes of said first data source;

identifying potential corresponding nodes and one or more secondary nodes of said second data source;

generating trace coordinates between said selected node and said secondary nodes of said first data source;

generating trace coordinates between potential corresponding nodes and said secondary nodes of said second data source;

generating a fourier descriptor of said trace coordinates associated with said selected node;

generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes; and

comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes, whereby a single remaining node of said potential corresponding nodes is identified as said corresponding node.

44. A computer system that is programmed to associate a selected node of a first data source with a corresponding node of a second data source comprising the steps of:

identifying said selected node and one or more secondary nodes of said first data source;

identifying potential corresponding nodes and one or more secondary nodes of said second data source;

generating trace coordinates between said selected node and said secondary nodes of said first data source;

generating trace coordinates between potential corresponding nodes and said secondary nodes of said second data source;

generating a fourier descriptor of said trace coordinates associated with said selected node;

generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes; and

comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes, whereby a single remaining node of said potential corresponding nodes is identified as said corresponding node.

45. A computer-readable medium that contains program code that is capable of causing a computer to perform a process of associating a selected node of a first data source with a corresponding node of a second data source comprising the steps of:

identifying said selected node and one or more secondary nodes of said first data source;

identifying potential corresponding nodes and one or more secondary nodes of said second data source;

generating trace coordinates between said selected node and said secondary nodes of said first data source;

generating trace coordinates between potential corresponding nodes and said secondary nodes of said second data source;

generating a fourier descriptor of said trace coordinates associated with said selected node;

generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes; and

comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes, whereby a single remaining node of said potential corresponding nodes is identified as said corresponding node.

46. A computer system that is programmed to associate a selected node of a first data source with a corresponding node of a second data source comprising the steps of:

means for identifying said selected node and one or more secondary nodes of said first data source;

means for identifying potential corresponding nodes and one or more secondary nodes of said second data source;

means for generating trace coordinates between said selected node and said secondary nodes of said first data source;

means for generating trace coordinates between potential corresponding nodes and said secondary nodes of said second data source;

means for generating a fourier descriptor of said trace coordinates associated with said selected node;

means for generating fourier descriptors of said trace coordinates associated with said potential corresponding nodes; and

means for comparing said fourier descriptors of said trace coordinates associated with said selected node with said fourier descriptors of said trace coordinates associated with said potential corresponding nodes to eliminate nonrelevant potential corresponding nodes of said potential corresponding nodes, whereby a single remaining node of said potential corresponding nodes is identified as said corresponding node.