Distance sorting algorithm for matching patterns

• US 20050047661A1
• Filed: 08/27/2004
• Published: 03/03/2005
• Est. Priority Date: 08/29/2003
• Status: Active Grant

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Maurer, Donald E.
• Granted Patent: US 7,379,598 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

The invention provides methods and systems for performing a matching function between a first pattern and a second pattern. This technique involves creating a set of all distance measurements between pairs of points in the first pattern and all distance measurements between pairs of points in the second pattern. This set is then partitioned into subsets of nearly equal distance elements. Those subsets containing at least one element derived from each pattern determine possible line segment matches which are then analyzed mathematically to determine the partial transform that maps the associated points of the first pattern into the points of the second pattern. The resulting set of partial transforms is then reviewed to determine matched line segments between the two patterns.

Claims

1. A pattern matching method for performing a comparison of a first pattern with a second pattern, said method comprising the steps of:

obtaining a first set of points in the first pattern and a second set of points in the second pattern;

creating a set of distance measurements of line segments formed between at least some of possible pairs of points in the first set and at least some of possible pairs of points in the second set;

partitioning the distance measurement set into subsets of approximately equal distance elements where each subset contains at least one element derived from each pattern;

determining possible line segment matches from each of said subsets; and

utilizing said possible line segment matches to determine a result of said comparison.

2. The method of claim 1 wherein said determining step comprises:

mathematically analyzing each of the elements in a subset to determine a collection of partial transforms, where each said partial transform maps the associated pair of points of the first pattern into a pair of points of the second pattern; and

,

repeating said analyzing step for each subset wherein each determined collection of partial transforms is combined to yield a total set of partial transforms.

3. The method of claim 2 wherein said determining step further comprises:

reviewing the total set of partial transforms to determine a specific optimal transform that maps the most pairs of points of the first pattern into pairs of points in the second pattern; and

,

determining that each pair of points in the first pattern mapped by said specific optimal transform into a pair of points in the second pattern corresponds to matched line segments.

4. The method of claim 3 wherein the elements of said total set of partial transforms contains both real and imaginary parts and where said reviewing step further comprises analyzing these parts separately.

5. The method of claim 3 wherein said determining step further comprises concluding no optimal partial transform exists if said most pairs of mapped points of any partial transform does not attain some minimum number.

6. The method of claim 2 wherein said determining step further comprises:

analyzing the total set of partial transforms to determine a specific optimal transform; and

,

determining that each pair of points in the first pattern mapped by said optimal transform into a pair of points in the second pattern corresponds to matched line segments.

7. The method of claim 6 wherein said analyzing step comprises performing a least squares minimization analysis.

8. The method of claim 1 wherein at least one of the patterns comprises a stored template.

9. The method of claim 1 wherein at least one of the patterns is obtained by a sensor device.

10. The method of claim 1 wherein said obtaining step comprises determining feature points from at least one of the patterns.

11. A computer-readable medium, comprising instructions for performing a comparison of a first pattern with a second pattern, said method comprising the steps of:

obtaining a first set of points in the first pattern and a second set of points in the second pattern;

creating a set of distance measurements of line segments formed between at least some of possible pairs of points in the first set and at least some of possible pairs of points in the second set;

partitioning the distance measurement set into subsets of approximately equal distance elements where each subset contains at least one element derived from each pattern;

determining possible line segment matches from each of said subsets; and

utilizing said possible line segment matches to determine a result of said comparison.

12. The computer-readable medium of claim 11 wherein said determining step comprises:

mathematically analyzing each of the elements in a subset to determine a collection of partial transforms, where each said partial transform maps the associated pair of points of the first pattern into a pair of points of the second pattern; and

,

repeating said analyzing step for each subset wherein each determined collection of partial transforms is combined to yield a total set of partial transforms.

13. The computer-readable medium of claim 12 wherein said determining step further comprises:

reviewing the total set of partial transforms to determine a specific optimal transform that maps the most pairs of points of the first pattern into pairs of points in the second pattern; and

,

determining that each pair of points in the first pattern mapped by said specific optimal transform into a pair of points in the second pattern corresponds to matched line segments.

14. The computer-readable medium of claim 13 wherein the elements of said total set of partial transforms contains both real and imaginary parts and where said reviewing step further comprises analyzing these parts separately.

15. The computer-readable medium of claim 12 wherein said determining step further comprises:

analyzing the total set of partial transforms to determine a specific optimal transform; and

,

determining that each pair of points in the first pattern mapped by said optimal transform into a pair of points in the second pattern corresponds to matched line segments.

16. The computer-readable medium of claim 15 wherein said analyzing step comprises performing a least squares minimization analysis.

17. An apparatus for performing a comparison of a first pattern with a second pattern, said apparatus comprising:

a means for obtaining a first set of points in the first pattern and a second set of points in the second pattern;

a means for creating a set of distance measurements of line segments formed between at least some of possible pairs of points in the first set and at least some of possible pairs of points in the second set;

a means for partitioning the distance measurement set into subsets of approximately equal distance elements where each subset contains at least one element derived from each pattern;

a means for determining possible line segment matches from each of said subsets; and

a means for utilizing said possible line segment matches to determine a result of said comparison.

18. The apparatus of claim 17 wherein said means for determining comprises:

a means for mathematically analyzing each of the elements in a subset to determine a collection of partial transforms, where each said partial transform maps the associated pair of points of the first pattern into a pair of points of the second pattern; and

,

a means for repeating said analyzing step for each subset wherein each determined collection of partial transforms is combined to yield a total set of partial transforms.

19. The apparatus of claim 18 wherein said means for determining further comprises:

a means for analyzing the total set of partial transforms to determine a specific optimal transform; and

,

a means for determining that each pair of points in the first pattern mapped by said optimal transform into a pair of points in the second pattern corresponds to matched line segments.

20. The apparatus of claim 19 wherein said means for analyzing comprises a means for performing a least squares minimization analysis.