Pattern matching method, program and semiconductor device manufacturing method

• US 20060110042A1
• Filed: 10/21/2005
• Published: 05/25/2006
• Est. Priority Date: 10/21/2004
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Yamazaki, Yuichiro, Onishi, Atsushi, Mitsui, Tadashi
• Granted Patent: US 8,036,445 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10056 Microscopic image
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/0006 using a design-rule based approach
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 10/757 Matching configurations of points or features

Abstract

A pattern matching method includes: detecting an edge of a pattern in a pattern image obtained by imaging the pattern; segmenting the detected pattern edge to generate a first segment set consisting of first segments; segmenting a pattern edge on reference data which serves as a reference for evaluating the pattern to generate a second segment set consisting of second segments; combining any of the segments in the first segment set with any of the segments in the second segment set to define a segment pair consisting of first and second segments; calculating the compatibility coefficient between every two segment pairs in the defined segment pairs; defining new segment pairs by narrowing down the defined segment pairs by calculating local consistencies of the defined segment pairs on the basis of the calculated compatibility coefficients and by excluding segment pairs having lower local consistencies; determining an optimum segment pair by repeating the calculating the compatibility coefficient and the defining new segment pairs by narrowing down the segment pairs; calculating a feature quantity of a shift vector that links the first and second segments making up the optimum segment pair; and performing position matching between the pattern image and the reference data on the basis of the calculated feature quantity of the shift vector.

Claims

1. A pattern matching method comprising:

detecting an edge of a pattern in a pattern image obtained by imaging the pattern;

segmenting the detected pattern edge to generate a first segment set consisting of first segments;

segmenting a pattern edge on reference data which serves as a reference for evaluating the pattern to generate a second segment set consisting of second segments;

combining any of the segments in the first segment set with any of the segments in the second segment set to define a segment pair consisting of first and second segments;

calculating a compatibility coefficient between every two segment pairs in the defined segment pairs;

defining new segment pairs by narrowing down the defined segment pairs by calculating local consistencies of the defined segment pairs on the basis of the calculated compatibility coefficients and by excluding segment pairs having lower local consistencies;

determining an optimum segment pair by repeating the calculating the compatibility coefficient and the defining new segment pairs by narrowing down the segment pairs;

calculating a feature quantity of a shift vector that links the first and second segments making up the optimum segment pair; and

performing position matching between the pattern image and the reference data on the basis of the calculated feature quantity of the shift vector.

2. The pattern matching method according to claim 1,

wherein the calculating the compatibility coefficient includes:

defining a rectangle surrounding each of the segments in the first segment set to generate a first circumscribed rectangle;

defining a rectangle surrounding each of the segments in the second segment set to generate a second circumscribed rectangle; and

defining a shift vector running from each vertex of the first circumscribed rectangle of the two segment pairs to the corresponding vertex of the second circumscribed rectangle and defining the compatibility coefficient by using the distance between the two rectangles defined by the shift vectors.

3. The pattern matching method according to claim 1,

wherein the segmentation of the pattern edge is performed by using a straight line or a function curve as the minimum unit.

4. The pattern matching method according to claim 1,

wherein the segmenting the pattern edge includes determining the curvature of the pattern edge by using a chain code.

5. The pattern matching method according to claim 1, further comprising:

rounding corner portions in the reference data.

6. The pattern matching method according to claim 1,

wherein the defining the segment pairs includes checking the relative positional relation between the first segments;

and

the calculating the compatibility coefficient further includes, if there are first segments that are substantially parallel to each other, setting the compatibility coefficient of the substantially parallel first segments to a value smaller than the value of the compatibility coefficient between first segments that are in other positional relations with each other.

7. The pattern matching method according to claim 1,

wherein the generating the first segment set includes storing information about first connectivity representing whether or not the generated first segments are connected with each other before the segmentation;

the generating the second segment set includes storing information about second connectivity representing whether or not the generated second segments are connected with each other before the segmentation; and

the calculating the compatibility coefficient further includes comparing the first connectivity with the second connectivity and, if they do not agree with each other, setting the compatibility coefficient to a value smaller than the value of compatibility coefficient that is set in the case where the first connectivity agrees with the second connectivity.

8. The pattern matching method according to claim 1,

wherein the feature quantity of the shift vector is an average or a median.

9. A program which causes a computer to perform a pattern matching method, the pattern matching method comprising:

detecting an edge of a pattern in a pattern image obtained by imaging the pattern;

segmenting the detected pattern edge to generate a first segment set consisting of first segments;

segmenting a pattern edge on reference data which serves as a reference for evaluating the pattern to generate a second segment set consisting of second segments;

combining any of the segments in the first segment set with any of the segments in the second segment set to define a segment pair consisting of first and second segments;

calculating a compatibility coefficient between every two segment pairs in the defined segment pairs;

defining new segment pairs by narrowing down the defined segment pairs by calculating local consistencies of the defined segment pairs on the basis of the calculated compatibility coefficients and by excluding segment pairs having lower local consistencies;

determining an optimum segment pair by repeating the calculating the compatibility coefficient and the defining new segment pairs by narrowing down the segment pairs;

calculating a feature quantity of a shift vector that links the first and second segments making up the optimum segment pair; and

performing position matching between the pattern image and the reference data on the basis of the calculated feature quantity of the shift vector.

10. The program according to claim 9,

wherein the calculating the compatibility coefficient includes:

defining a rectangle surrounding each of the segments in the first segment set to generate a first circumscribed rectangle;

defining a rectangle surrounding each of the segments in the second segment set to generate a second circumscribed rectangle; and

defining a shift vector running from each vertex of the first circumscribed rectangle of the two segment pairs to the corresponding vertex of the second circumscribed rectangle and defining the compatibility coefficient by using the distance between the two rectangles defined by the shift vectors.

11. The program according to claim 9,

wherein the segmentation of the pattern edge is performed by using a straight line or a function curve as the minimum unit.

12. The program according to claim 9,

wherein the segmenting the pattern edge includes determining the curvature of the pattern edge by using a chain code.

13. The program according to claim 9,

wherein the pattern matching method further comprises rounding corner portions in the reference data.

14. The program according to claim 9,

wherein the defining the segment pairs includes checking the relative positional relation between the first segments;

and

the calculating the compatibility coefficient further includes, if there are first segments that are substantially parallel to each other, setting the compatibility coefficient of the substantially parallel first segments to a value smaller than the value of the compatibility coefficient between first segments that are in other positional relations with each other.

15. The program according to claim 9,

wherein the generating the first segment set includes storing information about first connectivity representing whether or not the generated first segments are connected with each other before the segmentation;

the generating the second segment set includes storing information about second connectivity representing whether or not the generated second segments are connected with each other before the segmentation; and

the calculating the compatibility coefficient further includes comparing the first connectivity with the second connectivity and, if they do not agree with each other, setting the compatibility coefficient to a value smaller than the value of compatibility coefficient that is set in the case where the first connectivity agrees with the second connectivity.

16. A semiconductor device manufacturing method, comprising a pattern matching method including:

detecting an edge of a pattern in a pattern image obtained by imaging the pattern;

segmenting the detected pattern edge to generate a first segment set consisting of first segments;

segmenting a pattern edge on reference data which serves as a reference for evaluating the pattern to generate a second segment set consisting of second segments;

combining any of the segments in the first segment set with any of the segments in the second segment set to define a segment pair consisting of first and second segments;

calculating a compatibility coefficient between every two segment pairs in the defined segment pairs;

defining new segment pairs by narrowing down the defined segment pairs by calculating local consistencies of the defined segment pairs on the basis of the calculated compatibility coefficients and by excluding segment pairs having lower local consistencies;

determining an optimum segment pair by repeating the calculating the compatibility coefficient and the defining new segment pairs by narrowing down the segment pairs;

calculating a feature quantity of a shift vector that links the first and second segments making up the optimum segment pair; and

performing position matching between the pattern image and the reference data on the basis of the calculated feature quantity of the shift vector.

17. The semiconductor device manufacturing method according to claim 16,

wherein the calculating the compatibility coefficient includes:

defining a rectangle surrounding each of the segments in the first segment set to generate a first circumscribed rectangle;

defining a rectangle surrounding each of the segments in the second segment set to generate a second circumscribed rectangle; and

defining a shift vector running from each vertex of the first circumscribed rectangle of the two segment pairs to the corresponding vertex of the second circumscribed rectangle and defining the compatibility coefficient by using the distance between the two rectangles defined by the shift vectors.

18. The semiconductor device manufacturing method according to claim 16,

wherein the segmentation of the pattern edge is performed by using a straight line or a function curve as the minimum unit.

19. The semiconductor device manufacturing method according to claim 16,

wherein the defining the segment pairs includes checking the relative positional relation between the first segments;

and

the calculating the compatibility coefficient further includes, if there are first segments that are substantially parallel to each other, setting the compatibility coefficient of the substantially parallel first segments to a value smaller than the value of the compatibility coefficient between first segments that are in other positional relations with each other.

20. The semiconductor device manufacturing method according to claim 16,

wherein the generating the first segment set includes storing information about first connectivity representing whether or not the generated first segments are connected with each other before the segmentation;

the generating the second segment set includes storing information about second connectivity representing whether or not the generated second segments are connected with each other before the segmentation; and

the calculating the compatibility coefficient includes comparing the first connectivity with the second connectivity and, if they do not agree with each other, setting the compatibility coefficient to a value smaller than the value of compatibility coefficient that is set in the case where the first connectivity agrees with the second connectivity.