Distance sorting algorithm for matching patterns

• US 7,379,598 B2
• Filed: 08/27/2004
• Issued: 05/27/2008
• Est. Priority Date: 08/29/2003
• Status: Expired due to Fees

• Current Assignee: Johns Hopkins University
• Original Assignee: Johns Hopkins University
• Inventors: Maurer, Donald E.
• Primary Examiner(s): Bella; Matthew C.
• Assistant Examiner(s): CHU, RANDOLPH I
• Application Number:
  US10/928,286
• Publication Number:
  US 20050047661A1
• Time in Patent Office: 1,369 Days
• Field of Search: 382/209, 382/218, 382/219
• US Class Current: 382/209
• 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 and mathematically analyzing each of the elements in a subset to determine a collection of partial transforms, where each said partial transform maps an 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 and 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

, further 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 the possible line segment matches,

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.

2. The method of claim 1, 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.

3. The method of claim 1, 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.

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

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

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

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

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

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 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 and 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 the possible line segment matches; and

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

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.

9. The computer-readable medium of claim 8, 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.

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