Pattern aligning method, verifying method, and verifying device

• US 8,229,250 B2
• Filed: 02/10/2009
• Issued: 07/24/2012
• Est. Priority Date: 03/31/2008
• Status: Active Grant

• Current Assignee: Fujitsu Frontech Limited (Fujitsu Limited), Fujitsu Limited
• Original Assignee: Fujitsu Frontech Limited (Fujitsu Limited), Fujitsu Limited
• Inventors: Suzuki, Tomoharu, Eguchi, Shinichi
• Primary Examiner(s): Kassa, Yosef
• Application Number:
  US12/368,506
• Publication Number:
  US 20090245593A1
• Time in Patent Office: 1,260 Days
• Field of Search: 382/28, 382/289, 382/294, 382/296, 358/537, 358/540, 358/450
• US Class Current: 382/294
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

A pattern alignment method performs alignment of the comparison source pattern or the comparison target pattern that has been subjected to the angle-scale conversion with the comparison source pattern. Angular deviations and scale factors between the comparison source pattern and the comparison target pattern are computed separately, after angle and scale conversion, the measured template matching is performed. Therefore, parallel-displacement alignment can be made faster and precise alignment is possible. Template matching processing can be minimized, and aligning can be performed precisely and rapidly.

Claims

1. A pattern alignment method, comprising:

a first step of calculating an angle, scale, center point x coordinate, and center point Y coordinate, for each of a comparison source pattern and a comparison target pattern;

a second step of calculating an angle deviation between the comparison source pattern and the comparison target pattern, from the angle and scale for the comparison source pattern and the comparison target pattern;

a third step of calculating scale ratios of the comparison source pattern and the comparison target pattern, from the center point X coordinates and center point Y coordinates of the comparison source pattern and the comparison target pattern;

a fourth step of performing angle and scale conversion of the comparison source pattern or the comparison target pattern, using the angle and ratios; and

a fifth of, by using template matching, performing alignment of the comparison source pattern or the comparison target pattern that has been subjected to the angle-scale conversion with the comparison source pattern or the comparison target pattern that has not been subjected to the angle-scale conversion.

2. The pattern alignment method according to claim 1, wherein the first step comprises a step of calculating the angle, scale, center point X coordinate, and center point Y coordinate, for each of a plurality of the comparison source patterns and a plurality of the comparison target patterns;

and the second step comprises a step of calculating the angle deviations from each of angles and scales of the plurality of comparison source patterns and the plurality of comparison target patterns;

and the third step comprises a step of calculating the ratios from the center point X coordinates and center point Y coordinates of the plurality of comparison source patterns and the plurality of comparison target patterns.

3. The pattern alignment method according to claim 1, further comprising:

a step of converting a comparison source curve pattern into a linear comparison source pattern; and

a step of converting a comparison target curve pattern into a linear comparison target pattern.

4. The pattern alignment method according to claim 1, wherein the second step comprises:

a step of creating a first angle distribution in which scales of the comparison source pattern are angle frequencies and of creating a second angle distribution in which scales of the comparison target pattern are angle frequencies; and

a step of calculating the angle deviation from the first and second angle distributions.

5. The pattern alignment method according to claim 4, wherein the step of creating angle distributions comprises a step of weighting, by a weighting function, the scales of the comparison source pattern and the comparison target pattern to be converted into the frequencies.

6. The pattern alignment method according to claim 1, wherein the third step comprises:

a step of calculating scale shape contexts of each of the comparison source pattern and the comparison target pattern from the center point X coordinates and center point Y coordinates of the comparison source pattern and the comparison target pattern; and

a step of calculating a scale ratio from mean values of each of elements of each of the scale shape contexts.

7. The pattern alignment method according to claim 1, wherein the fifth step comprises a step of parallel-displacement aligning the comparison source pattern or the comparison target pattern that has been subjected to the angle-scale conversion, to the comparison source pattern or the comparison target pattern that has not been not subjected to the angle-scale conversion.

8. A pattern verifying method, comprising:

a first step of calculating an angle, scale, center point X coordinate, and center point Y coordinate, for each of a comparison source pattern and a comparison target pattern;

a second step of calculating an angle deviation between the comparison source pattern and the comparison target pattern, from the angle and scale for the comparison source pattern and the comparison target pattern;

a third step of calculating scale ratios of the comparison source pattern and the comparison target pattern, from the center point X coordinates and center point Y coordinates of the comparison source pattern and the comparison target pattern;

a fourth step of performing angle and scale conversion of the comparison source pattern or the comparison target pattern, using the angle and ratio;

a fifth step of, by using template matching, performing alignment of the comparison source pattern or the comparison target pattern that has been subjected to the angle-scale conversion with the comparison source pattern or the comparison target pattern that has not been subjected to the angle-scale conversion; and

a sixth step of calculating similarity of the aligned comparison source pattern and the comparison target pattern, and performing verifying.

9. The pattern verifying method according to claim 8, wherein the first step comprises a step of calculating the angle, scale, center point X coordinate, and center point Y coordinate, for each of a plurality of the comparison source patterns and a plurality of the comparison target patterns;

the second step comprises a step of calculating angle deviations from each of angles and scales of the plurality of comparison source patterns and the plurality of comparison target patterns; and

the third step comprises a step of calculating the ratios from the center point X coordinates and center point Y coordinates of the plurality of comparison source patterns and the plurality of comparison target patterns.

10. The pattern verifying method according to claim 8, further comprising:

a step of converting a comparison source curve pattern into a linear comparison source pattern; and

a step of converting a comparison target curve pattern into a linear comparison target pattern.

11. The pattern verifying method according to claim 8, wherein the second step comprises:

a step of creating a first angle distribution in which scales of the comparison source pattern are angle frequencies and of creating a second angle distribution in which scales of the comparison target pattern are angle frequencies; and

a step of calculating the angle deviation from the first and second angle distributions.

12. The pattern verifying method according to claim 11, wherein the step of creating angle distributions comprises a step of weighting, by a weighting function, the scales of the comparison source pattern and the comparison target pattern to be converted into the frequencies.

13. The pattern verifying method according to claim 8, wherein the third step comprises:

a step of calculating scale shape contexts of each of the comparison source pattern and the comparison target pattern from the center point X coordinates and center point Y coordinates of the comparison source pattern and the comparison target pattern; and

a step of calculating a scale ratio from mean values of each of elements of each of the scale shape contexts.

14. The pattern verifying method according to claim 8, wherein the fifth step comprises a step of parallel-displacement aligning the comparison source pattern or the comparison target pattern that has been subjected to the angle-scale conversion, to the comparison source pattern or the comparison target pattern that has not been subjected to the angle-scale conversion.

15. A pattern verifying device, comprising:

an acquisition unit which acquires a comparison target pattern; and

a verifying unit which matches a comparison source pattern with the comparison target pattern, wherein

the verifying unit calculates an angle, scale, center point X coordinate, and center point Y coordinate for each of the comparison source pattern and the comparison target pattern, calculates an angle deviation between the comparison source pattern and the comparison target pattern from the angle and scale of the comparison source pattern and the comparison target pattern, and calculates the scale ratio of the comparison source pattern and the comparison target pattern from the center point X coordinate and center point Y coordinate of the comparison source pattern and the comparison target pattern,

and wherein the verifying unit angle-scale converts the comparison source pattern or the comparison target pattern using the angle and ratio, aligns, by template matching, the comparison source pattern or the comparison target pattern that has been subjected to angle-scale conversion, and the comparison source pattern or the comparison target pattern that has not been subjected to angle-scale conversion, and calculates the similarity of the comparison source pattern and the comparison target pattern after the alignment to perform verifying.

16. The pattern verifying device according to claim 15, wherein the verifying unit calculates angles, scales, center point X coordinates, and center point Y coordinates for each of a plurality of the comparison source patterns and a plurality of the comparison target patterns;

calculates the angle deviations from each of the angles and scales of the plurality of comparison source patterns and the plurality of comparison target patterns; and

calculates the ratios from the center point X coordinates and center point Y coordinates of the plurality of comparison source patterns and the plurality of comparison target patterns.

17. The pattern verifying device according to claim 15, wherein the verifying unit converts a comparison source curve pattern into a linear comparison source pattern, and converts a comparison target curve pattern into a linear comparison target pattern.

18. The pattern verifying device according to claim 15, wherein the verifying unit creates a first angle distribution in which the scales of the comparison source pattern are angle frequencies, creates a second angle distribution in which the scales of the comparison target pattern are angle frequencies, and calculates the angle deviation from the first and second angle distributions.

19. The pattern verifying device according to claim 18, wherein the verifying unit weights the scales of the comparison source pattern and the comparison target pattern by a weighting function, and converts the frequencies.

20. The pattern verifying device according to claim 15, wherein the verifying unit calculates scale shape contexts of each of the comparison source pattern and the comparison target pattern from the center point X coordinates and center point Y coordinates of the comparison source pattern and the comparison target pattern, and calculates the scale ratio from mean values of each of elements of each of the scale shape contexts.

21. The pattern verifying device according to claim 15, wherein the verifying unit parallel-displacement aligns the comparison source pattern or the comparison target pattern that has been subjected to the angle-scale conversion, to the comparison source pattern or the comparison target pattern that has not been subjected to the angle-scale conversion.

22. The pattern verifying device according to claim 15, wherein the comparison source pattern and the comparison target pattern are biometrics pattern, and the verifying is biometrics authentication.