Pattern matching apparatus

• US 6,804,387 B1
• Filed: 07/28/2000
• Issued: 10/12/2004
• Est. Priority Date: 08/27/1999
• Status: Expired due to Fees

• Current Assignee: Renesas Electronics Corporation
• Original Assignee: Renesas Technology Corporation (Renesas Electronics Corporation)
• Inventors: Ijichi, Toshiya, Sakaue, Yoshikazu
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US09/628,275
• Time in Patent Office: 1,537 Days
• Field of Search: 382/141, 382/149, 382/173, 382/181, 382/209, 382/217, 382/218, 382/220, 382/310, 382/151, 382/168, 382/274, 382/275, 382/278, 348/129, 348/94, 348/95, 348/135
• US Class Current: 382/141
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A pattern matching method comprising the steps of: computing matching scores while shifting a template picture in increments of four pixels so as to find a pixel corresponding to a maximum matching score; performing, starting from the pixel of the maximum matching score obtained in the matching score computing step, matching computations on each of an upper, a lower, a left-hand and a right-hand pixel surrounding the starting pixel in order to reach a pixel having a higher matching score than any other surrounding pixel; coming to a stop when the pixel with the highest matching score is reached; and adding to the highest matching score obtained in the computation performing step a correction value which takes into account the matching scores of the pixels adjacent to the highest matching score pixel, whereby matching score allowances due to dislocated pixels are corrected.

Claims

1. A pattern matching apparatus performing a pattern matching while comparing a template picture with a picture under inspection, said apparatus comprising:

maximum score detection means for shifting the template picture with respect to the picture under inspection in order to compute matching scores between the two pictures and thereby to detect a maximum score among the matching scores as well as a maximum position in which the maximum score is generated;

means for computing a correction value based on matching scores generated at positions adjacent to said maximum position; and

means for correcting said matching score by adding said maximum score with said correction value.

2. The pattern matching apparatus according to claim 1 wherein said maximum score detection means further comprising:

means for shifting the template so that said template skips a predetermined numbers of pixels, computing matching scores at individual shifted positions, and setting a position in which the greatest one among said matching scores is generated to a starting position;

means for shifting the template among positions corresponding to four pixels surrounding a starting position successively in order to compute matching scores at each of said positions;

means for setting, if any one of matching scores corresponding to said four pixels is greater than the matching score of said starting position, the position in which the greatest score is generated to a new starting position; and

means for setting, if the matching score of said starting position is greater than any of the matching scores corresponding to said four pixels, said matching score of said starting position to said maximum value as well as the starting position to said maximum position.

3. The pattern matching apparatus according to claim 1 wherein said maximum score detection means further comprising:

means for shifting the template so that said template skips a predetermined numbers of pixels, computing matching scores at individual shifted positions, and if a matching score equal to a predetermined value or more is detected setting a position in which the matching score in question is generated to a starting position;

means for shifting the template among positions corresponding to four pixels surrounding a starting position successively in order to compute matching scores at each of said positions;

means for setting, if any one of matching scores corresponding to said four pixels is greater than the matching score of said starting position, the position in which the greatest score is generated to a new starting position; and

means for setting, if the matching score of said starting position is greater than any of the matching scores corresponding to said four pixels, said matching score of said starting position to said maximum value as well as the starting position to said maximum position.

4. The pattern matching apparatus according to claim 1 wherein said correction value is given by a following expression:

correction value=const1×

{(matching score corresponding to one of adjacent positions in vertical direction)−

(matching score corresponding to the other of adjacent positions in vertical direction)}²+const2×

{(matching score corresponding to one of adjacent positions in horizontal direction)−

(matching score corresponding to the other of adjacent positions in horizontal direction)}² where, const1 and const2 represent a constant each.

5. The pattern matching apparatus according to claim 1 wherein said correction value is given by a following expression:

correction value=const3×

abs{(matching score corresponding to one of adjacent positions in vertical direction)−

(matching score corresponding to the other of adjacent positions in vertical direction)}+const4×

abs{(matching score corresponding to one of adjacent positions in horizontal direction)−

(matching score corresponding to the other of adjacent positions in horizontal direction)}

where, const3 and const4 represent a constant each, and abs denotes an absolute value.

6. A pattern matching apparatus performing a pattern matching while comparing a template picture with a picture under inspection, said apparatus comprising:

means for shifting the template so that said template skips a predetermined numbers of pixels, computing matching scores at individual shifted positions, and setting a position in which the greatest one among said matching scores is generated to a starting position;

means for shifting the template among positions corresponding to four pixels surrounding a starting position successively in order to compute matching scores at each of said positions;

means for setting, if any one of matching scores corresponding to said four pixels is greater than the matching score of said starting position, the position in which the greatest score is generated to a new starting position; and

means for setting, if the matching score of said starting position is greater than any of the matching scores corresponding to said four pixels, said matching score of said starting position to said maximum value as well as the starting position to said maximum position.

7. A pattern matching apparatus performing a pattern matching while comparing a template picture with a picture under inspection, said apparatus comprising:

means for shifting the template so that said template skips a predetermined numbers of pixels, computing matching scores at individual shifted positions, and if a matching score equal to a predetermined value or more is detected setting a position in which the matching score in question is generated to a starting position;

means for shifting the template among positions corresponding to four pixels surrounding a starting position successively in order to compute matching scores at each of said positions;

means for setting, if any one of matching scores corresponding to said four pixels is greater than the matching score of said starting position, the position in which the greatest score is generated to a new starting position; and

means for setting, if the matching score of said starting position is greater than any of the matching scores corresponding to said four pixels, said matching score of said starting position to said maximum value as well as the starting position to said maximum position.