Method for fixed-rotation and rotation-independent image correlation

• US 8,478,049 B2
• Filed: 04/29/2010
• Issued: 07/02/2013
• Est. Priority Date: 04/29/2009
• Status: Expired due to Fees

• Current Assignee: Coherix Incorporated
• Original Assignee: Coherix Incorporated
• Inventors: Davidson, Douglas
• Primary Examiner(s): Bayat, Ali
• Application Number:
  US13/265,426
• Publication Number:
  US 20120163721A1
• Time in Patent Office: 1,160 Days
• Field of Search: 382/190, 382/195, 382/199, 382/162, 382/166, 382/167, 358/518, 358/520, 358/521, 358/522, 358/523
• US Class Current: 382/199
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A circlet is defined as a compact angle representation expressing, at a given pixel comprised in the first image, the direction of change of pixel intensity. A method of locating a feature of interest includes the steps of: acquiring a first image of a feature of interest to a user; generating a learned circlet image from the first image; saving one or more sets of learned circlets corresponding to one or more selected probes; acquiring a second image of the feature of interest; generating a target circlet image from the second image; and correlating the learned circlet image and the target circlet image.

Claims

1. A method of correlating an image of a feature of interest, comprising:

acquiring a first image of a feature of interest;

generating a learned circlet image from the first image, wherein a circlet is defined as a compact angle representation expressing, at a given pixel comprised in the first image, the direction of change of pixel intensity;

saving one or more sets of learned circlets corresponding to one or more selected probes;

acquiring a second image of the feature of interest;

generating a target circlet image from the second image; and

correlating the learned circlet image and the target circlet image.

2. The method of claim 1, wherein generating a learned circlet image comprises determining an intensity gradient for each learned pixel.

3. The method of claim 1, wherein generating a learned circlet image comprises filtering the first image.

4. The method of claim 1, wherein a circlet is defined so as to express an angle in one byte of data.

5. The method of claim 1, wherein the step of generating a learned circlet image comprises calculating a circlet using the formula:

C_learned={Θ

_learned*255/360}+1, where C_learned is the learned circlet value, and learned edge direction angle Θ

_learned=atan 2 (G_learned-y, G_learned-x), where the angle is expressed in degrees and is defined to be a positive number.

6. The method of claim 1, wherein the step of generating a learned circlet image comprises using a lookup table to pre-calculate approximate circlet values.

7. The method of claim 6, wherein pre-calculating approximate circlet values comprises summing the directional components of a learned gradient.

8. The method of claim 1, wherein the step of generating a learned circlet image from the first image comprises the steps of:

filtering the first image;

generating a learned gradient image corresponding to the filtered first image; and

generating a learned circlet image comprising edgels from the learned gradient image.

9. The method of claim 8, wherein generating a learned gradient image comprises applying the Sobel edge detection algorithm.

10. The method of claim 8, wherein generating a learned gradient image comprises calculating a learned gradient image.

11. The method of claim 8, wherein generating a learned gradient image comprises determining the learned gradient image using a pre-calculated lookup table.

12. The method of claim 11, wherein generating a learned gradient image comprises using a pre-calculated lookup table to find the sum of the absolute values of the directional components of the learned gradient.

13. The method of claim 1, wherein the step of saving one or more sets of learned circlets comprises the steps of:

determining a learned non-maximum suppression image from the learned circlet image;

determining one or more edgel chains from the learned non-maximum suppression image;

selecting one or more primary probes from the edgels;

determining a consistency score for one or more edgels;

using the consistency scores, selecting one or more sets of secondary probes from the one or more learned edgels; and

saving one or more sets of learned circlets corresponding to the selected probes.

14. The method of claim 13, wherein the step of determining one or more edgel chains comprises the steps of:

thresholding at least one of the one or more edgel chains; and

extracting at least one of the one or more edgel chains from the learned non-maximum suppression image.

15. The method of claim 13, wherein the consistency score is configured to reflect learned gradient magnitude and learned circlet consistency.

16. The method of claim 13, wherein the step of determining a consistency score comprises:

eliminating all edgels of a length less than a parameter P₀;

for a selected edgel E₁, finding all edgels E₂ whose distance in edgels from E₁;

is no more than a parameter P₁;

calculating a consistency score by finding the edgel E₂ with the biggest difference in circlet value relative to E₁; and

subtracting from 256 the absolute value of the circlet difference between E₁ and E₂ to determine the consistency score.

17. The method of claim 1, wherein the step of generating a target circlet image comprises the steps of:

filtering the second image;

generating a target gradient image corresponding to the second image; and

generating a target circlet image comprising edgels from the target gradient image.

18. The method of claim 17, wherein generating a target gradient image comprises applying the Sobel edge detection algorithm.

19. The method of claim 1, wherein the step of correlating comprises the steps of:

determining the absolute values of the differences between the learned circlet values corresponding to a selected primary probe and the target circlet values;

determining the minimum circlet difference;

determining the sums of the circlet differences;

adding the minimum circlet difference to the circlet difference sums to generate a match quality parameter P for the primary probe;

determining if the match quality parameter P is less than a previously saved match quality parameter threshold, and if no, returning to determining absolute values step for different selected primary probe;

for at least one selected secondary probe, computing the sums |Δ

C|_sum of the circlet differences |Δ

C| between the secondary probe circlet values and the target circlet values;

adding the circlet difference sums |Δ

C|_sum for the selected primary and secondary probes to generate |Δ

C|_{probes sum}; and

setting the calculated value of |Δ

C|_{probes sum} equal to a best probes sum value |Δ

C|_{best probes sum} and generating a correlated target circlet image using the current probe set if no previous |Δ

C|_{best probes sum} was saved or if |Δ

C|_{probes sum} is less than the previously saved |Δ

C|_{best probes sum}.

20. The method of claim 19, wherein the step of determining the absolute values of the circlet differences comprises using a lookup table to pre-calculate approximate absolute circlet difference values.

21. The method of claim 19, wherein the step of determining the minimum circlet difference comprises using a lookup table to pre-calculate an approximate minimum circlet difference value.

22. The method of claim 1, wherein the step of correlating comprises the steps of:

selecting a set of one or more probes whose circlet values correspond to the target circlet values;

selecting a primary probe from the set of one or more probes;

determining the absolute values of the differences between the learned circlet values corresponding to the selected primary probe and the target circlet values;

determining the minimum circlet difference;

determining the sums of the circlet differences;

adding the minimum circlet difference to the circlet difference sums to generate a match quality parameter P for the selected primary probe;

determining if the match quality parameter P is less than a previously saved match quality parameter threshold, and if no, returning to determining absolute values step for different selected primary probe;

for at least one selected secondary probe, computing the sums |Δ

C|_sum of the circlet differences |Δ

C| between the secondary probe circlet values and the target circlet values;

adding the circlet difference sums |Δ

C|_sum for the selected primary and secondary probes to generate |Δ

C|_{probes sum}; and

setting the calculated value of |Δ

C|_{probes sum} equal to a best probes sum value |Δ

C|_{best probes sum} and generating a correlated target circlet image using the current probe set if no previous |Δ

C|_{best probes sum} was saved or if |Δ

C|_{probes sum} is less than the previously saved |Δ

C|_{best probes sum}.

23. The method of claim 22, wherein the step of determining the absolute values of the circlet differences comprises using a lookup table to pre-calculate approximate absolute circlet difference values.

24. The method of claim 22, wherein the step of determining the minimum circlet difference comprises using a lookup table to pre-calculate an approximate minimum circlet difference value.

25. A method of locating a feature of interest comprising the steps of:

acquiring a first image of a feature of interest;

filtering the first image;

generating a learned gradient image corresponding to the filtered first image;

generating a learned circlet image comprising edgels from the learned gradient image;

determining a learned non-maximum suppression image from the learned circlet image;

determining one or more edgel chains from the learned non-maximum suppression image;

determining a consistency score for one or more of the learned edgels;

using the consistency scores, selecting a set of primary probes from the one or more learned edgels;

using the consistency scores, selecting a set of secondary probes from the one or more learned edgels;

saving one or more sets of learned circlets corresponding to the selected probes;

selecting alternate primary probes;

acquiring a second image of the feature of interest;

filtering the second image;

generating a target gradient image corresponding to the filtered second image;

generating a target circlet image from the target gradient image; and

correlating the learned circlet image and the target circlet image.