Method for positional matching of images and system for testing products by using the same

• US 6,005,977 A
• Filed: 07/17/1996
• Issued: 12/21/1999
• Est. Priority Date: 07/20/1995
• Status: Expired due to Term

• Current Assignee: Airec Engineering Corp. (Government of Japan), Nippon Telegraph and Telephone Corporation
• Original Assignee: NIPPON TELEGRAPH & TELEPHONE CORP. N.T.T. FANET SYSTEMS CORP.
• Inventors: Shindo, Akira, Nunotani, Masakatsu, Tanimizu, Katsuyuki, Yamamoto, Tetsuya
• Primary Examiner(s): Coles, Edward L.
• Assistant Examiner(s): ROSENBLUM, DAVID J
• Application Number:
  US08/682,373
• Time in Patent Office: 1,252 Days
• Field of Search: 382/209, 382/149, 382/181, 382/294, 382/151, 382/147, 382/287, 382/289, 382/293, 382/319, 382/216, 382/112, 382/133, 382/134, 382/135, 382/136, 382/137, 382/141, 382/144 , 382/152, 355/53, 355/54, 358/526, 250/558
• US Class Current: 382/216
• CPC Class Codes: G06T 2207/20012 Locally adaptive
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30108 Industrial image inspection
• CPC Class Codes: G06T 7/337 involving reference images or patches
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

The present invention provides an image matching method which allows non-ear image positional shifts to be corrected on a real time basis, and an economical product testing system using this method. A two dimensional test image, consisting of pixels arranged as a matrix of bits distributed in both the vertical direction and the horizontal scanning direction, and an associated reference image are subjected to template matching at a cell matching arithmetic unit for each of line blocks consisting of a plurality of scan lines. The result of the template matching are quantitatively evaluated at an evaluation unit as being good or bad, and positional shifts are sequentially computed according to good evaluation results. Based on the positional shifts thus obtained, the comparative pixel addresses are accordingly corrected before the two images are compared at the comparator.

Claims

1. A method for positional matching of images, wherein image data of two images of an identical picture pattern are compared by using image data of one of the images as reference data, and positional shifting between the two images is compensated for when determining an identity of the images according to computed differences between them, characterized by that:

as ahorizontal scan line or a group of horizontal scan lines from an image are sequentally transfered, a positional shifting computing process and a positional matching compensation process based on the computed shifting are performed for each line block such that the position shifting computed by the positional shifting computing process for one line block may be different from the positional shifting computed for another line block, wherein a line block includes a single horizontal scan line or a predetermined number of consecutive horizontal scan lines with respect to the two images of a normally identical image pattern;

wherein if the positional shifting computed for a certain line block is greater than the preceding line block by more than a threshold value, the positional shifting of the certain line block is set equal to predetermined value.

2. A method for positional matching of images according to claim 1, wherein the positional shifting computing process comprises the steps of:

conducting a template matching with respect to the other image by using selected cells, obtained by dividing each of the line blocks of the reference image into a number of cells, as templates;

quantitatively evaluating the results of the template matching as being either good or bad; and

computing the positional shifting of the images according to the results of the template matching which are evaluated as being good.

3. A method for positional matching of images according claim 1, wherein the positional matching compensation process for each of the line blocks is conducted according to the positional shifting of one of the line blocks preceding the current line block or the positional shifting of one of the line blocks following the current line block.

4. A method for positional matching of images according to claim 2, wherein if there are a plurality of cells serving as templates or selected cells in a line block of the reference image, there are a plurality of good matching results, and a plurality of incidences of positional shifting are obtained for a corresponding line block of the other image, then, the result of the positional shifting computing process is given as an average of the incidences of positional shifting.

5. A method for positional matching of images, wherein image data of two images of an identical picture pattern are compared by using image data of one of the images as reference data, and positional shifting between the two images is compensated for when determining an identity of the two images according to computed differences between them, characterized by that:

as a horizontal scan line or a group of horizontal scan lines from an image are sequentially transferred, a positional shifting computing process and a positional matching compensation process based on the computed shifting are performed for each line block such that the positional shifting computed by the positional shifting computing process for one line block may be different from the positional shifting computed for another line block, wherein a line block includes a single horizontal scan line or a predetermined number of consecutive horizontal scan lines with respect to the two images of a nominally identical image pattern;

wherein the positional shifting computing process comprises the steps of;

dividing each line block of the reference image into a number of cells;

conducting a template matching on the reference image by using the cells as templates;

selecting those cells which are effective in computing positional shifting by quantitatively evaluating the results of the template matching;

classifying the selected cells into x-, y-, and xy- cells as those which are effective in detecting the shifting in x, y and both x and y directions, respectively, and registering them as such; and

conducting a template matching with respect to the other image by using the registered selected cells as templates, and computing positional shifting of the other image according to the result of the template matching.

6. A method for positional matching of images according to claim 5, wherein when a template matching is conducted for a certain line block with respect to the other image by using the cells or the selected cells of the reference image as templates, the address of each of the cells of the other image is compensated for according to the positional shifting of the preceding line block with respect to the cell or the selected cell of the reference image at the corresponding address.

7. A system for testing products by positional matching of images, comprising:

image capturing means for sequentially entering a horizontal scan line or a group of horizontal scan lines of an image of a product to be tested;

positional shifting computing means for computing positional shifting of an image based on cell matching conducted for each line block, each line block consisting of a prescribed number of adjacent horizontal scan lines of a test image and a reference image, the positional shifting computing means computing a positional shifting for each line block which may be different from the positional shifting computed for another line block, wherein if the positional shifting computed for a certain line block is greater than the preceding line block by more than a threshold value, the positional shifting of the certain line block is set equal to a predetermined value;

compensating means for compensating the positional shifting of the test image with respect to the reference image according to the positional shifting computed by the positional shifting computing means;

difference computing means for comparing the test image, for which the positional shifting was compensated, with the reference image and obtaining differences between them; and

judging means for judging whether each product is detective or not by determining the identity of the two images according to the computed differences between them;

the positional shifting of each line block being compensated for before determining the identity of the two images.

8. The system of claim 7, wherein the positional shifting computing means comprises:

template matching means for conducting a template matching with respect to the other image by using selected cells, obtained by dividing each of the line blocks of the reference image into a number of cells, as templates;

evaluating means for quantitatively evaluating the results of the template matching as being either good or bad; and

computing means for computing the positional shifting of the images according to the results of the template matching which are evaluated as being good.

9. The system of claim 7, wherein the positional matching compensation process for each line block is conducted according to the positional shifting of one of the line blocks preceding the current line block or the positional shifting of one of the line blocks following the current line block.

10. The system of claim 8, wherein if there are a plurality of cells serving as templates or selected cells in a line block of the reference image, there are a plurality of good matching results, and a plurality of incidences of positional shifting are obtained for a corresponding line block of the other image, then the result of the positional shifting computing process is given as an average of the incidences of positional shifting.

11. A system for testing products by positional matching of images, comprising:

image capturing means for sequentially entering a horizontal scan line or a group of horizontal scan lines of an image of a product to be tested;

positional shifting computing means for computing positional shifting of an image based on cell matching conducted for each line block, each line block consisting of a prescribed number of adjacent horizontal scan lines of a test image and a reference image, the positional shifting computing means computing a positional shifting for each line block which may be different from the positional shifting computed for another line block;

compensating means for compensating the positional shifting of the test image with respect to the reference image according to the positional shifting computed by the positional shifting computing means;

difference computing means for comparing the test image, for which the positional shifting was compensated, with the reference image and obtaining differences between them; and

judging means for judging whether each product is defective or not by determining the identity of the two images according to the computed differences between them;

the positional shifting of each line block being compensated for before determining the identity of the two images;

wherein the positional shifting computing means comprises;

dividing means for dividing each line block of the reference image into a number of cells;

reference template pattern matching means for conducting a template matching on the reference image by using the cells as templates;

selecting means for selecting those cells which are effective in computing positional shifting by quantitatively evaluating the results of the template matching;

classification means for classifying the selected cells into x-, y- and xy- cells as those which are effective in detecting the shifting in x, y and both x and y directions, respectively, and registering them as such; and

test template pattern matching means for conducting a template matching with respect to the other image by using the registered selected cells as templates, and computing positional shifting of the other image according to the result of the template matching.

12. The system of claim 11, wherein when a template matching is conducted for a certain line block with respect to the other image by using the cells or the selected cells of the reference image as templates, the address of each of the cells of the other image is compensated for according to the positional shifting of the preceding line block with respect to the cell or the selected cell of the reference image at the corresponding address.