Pattern recognition apparatus and a pattern recognition method

• US 4,651,341 A
• Filed: 09/13/1983
• Issued: 03/17/1987
• Est. Priority Date: 09/14/1982
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nakashima, Masato, Tsukahara, Hiroyuki, Koezuka, Tetsuo, Inagaki, Takefumi
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/531,563
• Time in Patent Office: 1,281 Days
• Field of Search: 382/34, 382/33, 382/37, 382/48, 382/8, 382/42, 382/47, 382/56, 382/22, 382/31, 382/54, 381/41, 381/42, 381/43
• US Class Current: 382/222
• CPC Class Codes: G01B 11/024 by means of diode-array scanning
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: H01L 2224/05599 Material
• CPC Class Codes: H01L 2224/45144 Gold (Au) as principal constituent
• CPC Class Codes: H01L 2224/48 of an individual wire connector
• CPC Class Codes: H01L 2224/8513 using marks formed on the semiconductor or solid-state body
• CPC Class Codes: H01L 24/45 of an individual wire connector
• CPC Class Codes: H01L 24/48 of an individual wire connector
• CPC Class Codes: H01L 24/78 Apparatus for connecting with wire connectors
• CPC Class Codes: H01L 24/85 using a wire connector wire bonding in general B23K20/004
• CPC Class Codes: H01L 2924/00014 the subject-matter covered by the group, the symbol of which is combined with the symbol of this group, being disclosed without further technical details
• CPC Class Codes: H01L 2924/01024 Chromium [Cr]
• CPC Class Codes: H01L 2924/01057 Lanthanum [La]
• CPC Class Codes: H01L 2924/01061 Promethium [Pm]
• CPC Class Codes: H01L 2924/01079 Gold [Au]
• CPC Class Codes: H01L 2924/01082 Lead [Pb]
• CPC Class Codes: H01L 2924/01088 Radium [Ra]
• CPC Class Codes: H01L 2924/14 Integrated circuits

Abstract

A pattern recognition apparatus and method, the apparatus comprising a correlation calculating circuit for calculating first correlations between each part of a image pattern data and a reference pattern data, the first correlation being expressed as R(X), where X is a variable factor representing a region storing the part of the image pattern data, and also comprising a second correlation calculating circuit for recognizing the position of a pattern most identical to the reference pattern by emphasizing the maximum value of the first correlations by converting each of the first correlations R(X) into a second correlation expressed as [R(X)-R(X-α)]-[R(X+α)-R(X)], where α is a predetermined value determined in accordance with the size of the reference pattern data.

Claims

1. A pattern recognition apparatus comprising:

an image pickup section for picking up an image of patterns;

a pretreated circuit for converting an output signal of said image pickup section into image pattern data consisting of binary-coded signals;

a pattern memory circuit having N×

M addresses for storing N×

M bits of said image pattern data, where M and N are integers;

a reference pattern memory circuit having at least n×

m addresses for storing reference pattern data consisting of n×

m bits of a reference pattern, where m and n are integers smaller than M and N respectively;

a first correlation calculating circuit for calculating first correlations between sub-images each consisting of n×

m bits of said image pattern data and said reference pattern data, respectively, each of said first correlations being expressed as R(X), where X is a variable factor representing a memory region storing one of said image pattern data sub-images in said pattern memory circuit; and

a second correlation calculating means for recognizing the position of a pattern most identical to said reference pattern, by emphasizing the maximum value of said first correlations by converting each of said first correlations R(X) into a second correlation expressed as [R(X)-R(X-α

)]-[R(X+α

)×

R(X)], where α

is a predetermined value determined in accordance with the size of said reference pattern data.

2. A pattern recognition apparatus as set forth in claim 1, wherein, said first correlation calculating circuit comprises;

a first n-bit shift register for storing n bits of one of said parts, said n bits being output from a column of said pattern memory circuit, said column having addresses from (X, Y+y) to (X+n, Y+y), where X, Y, and y are variable integers under the conditions 1≦

X≦

N-n, 1≦

Y≦

M-m, and 1≦

y≦

m;

a second n-bit shift register for storing n bits of said reference pattern data, said n bits being output from a column of said reference pattern memory, said column having addresses from (1, y) to (n, y);

a matching-bit detecting circuit for detecting coincidences between said n bits of said image pattern data stored in said first n-bit shift register and said n bits of said reference pattern data stored in said second n-bit shift register in a bit-to-bit fashion, so as to provide matching-bit signals with respect to said n bits of said image pattern data;

a first adder for summing the number of said matching-bit signals with respect to said column having addresses from (X, Y+y) to (X+n, Y+y);

a second adder for adding the output of said first adder to a previously-obtained number of matching-bit signals with respect to columns having addresses from (X, Z) to (X+n, Z), where Z represents a variable integer smaller than the integer Y+y, so as to provide a first correlation between m×

y bits of said image pattern data stored in the addresses from (X, Y) to (X+n, Y+y) in said one of said parts stored in said pattern memory circuit and n×

y bits of said reference pattern data stored in the addresses (1,

     1) to (n, y) of said reference memory circuit; and

a line memory circuit having a plurality of first-correlation storing regions for storing the outputs of said second adder, said correlation storing regions being adapted to store the resultant first correlations R(1), R(2), ---, R(X), ---, R(N-n), respectively, where R(X) is the first correlation with respect to n×

m bits of said image pattern data in the addresses from (X, Y) to (X+n, Y+m).

3. A pattern recognition apparatus as set forth in claim 2, wherein said first n-bit shift register and said second n-bit shift register each comprises n locations each for storing one bit.

4. A pattern recognition apparatus as set forth in claim 3, wherein, said matching-bit detecting circuit comprises ENOR circuits, each of said ENOR circuits having a first input connected to one of said locations in said first n-bit shift register and a second input connected to one of said locations in said second n-bit shift register, said one of said locations in said first n-bit shift register corresponding to said one of said locations in said second n-bit shift register.

5. A pattern recognition apparatus as set forth in claim 4, wherein, said first correlation calculating circuit further comprises a memory control circuit for controlling the input operation and the output operation of said line memory circuit, whereby the outputs of said line memory circuit are supplied to said second adder after said first adder outputs said number of said matching-bit signals.

6. A pattern recognition apparatus as set forth in claim 5, wherein, said first correlation calculating circuit further comprises a data register for temporarily storing the outputs of said second adder or of said line memory circuit.

7. A pattern recognition apparatus as set forth in any one of claims 1 through 6, wherein said position recognizing means comprises a first subtracting circuit for calculating [R(X)-R(x-α

)], a second subtracting circuit for calculating [R(X+α

)-R(X)], and a third subtracting circuit for subtracting the output of said second subtracting circuit from the output of said first subtracting circuit.

8. A pattern recognition apparatus as set forth in claim 7, wherein said second correlation calculating means further comprises a maximum-value storing register for storing the maximum value of the outputs of said third subtracting circuit, and a comparator for comparing each output from said third subtracting circuit with said maximum value previously stored in said maximum-value storing register, so as to provide a trigger to said maximum-value storing register to update the contents of said maximum-value storing register into the output of said comparator when the output value of said third subtracting circuit is greater than the stored maximum value.

9. A pattern recognition apparatus as set forth in claim 8 further comprising a data compaction circuit inserted between said pretreatment circuit and said pattern memory circuit, for compacting a predetermined number of neighboring bits of said binary-coded signals into a single bit, the sign of said single bit being determined in accordance with the number of "1" or "0" signals in said neighboring bits, so as to provide compacted image pattern data to said pattern memory circuit.

10. A pattern recognition apparatus as set forth in claim 9, further comprising:

an address register for storing an address of said image pattern data in response to said trigger from said comparator, whereby, said address register is adapted to store the address of the image pattern data which provides the maximum value at the output of said third subtracting circuit;

a view-window determining circuit connected to the output of said address register, for calculating the position of a view window for taking out a small sub-image of said image pattern data from said pretreatment circuit, said small sub-image including the data which provides the maximum value stored in said maximum-value storing register after all bits of said first sub-image of said image pattern data are processed by said first correlation calculating circuit and by said second correlation calculating means, the calculation of the position of said view window being carried out by using said address stored in said address register; and

a middle-point detecting circuit connected to the output of said view window determining circuit, for detecting the middle point of a pattern in said small sub-image.

11. A pattern recognition method comprising the steps of:

picking up an image of patterns,

converting the picked-up image into image pattern data consisting of binary-coded signals,

storing N×

M bits of said image pattern data, where M and N are integers;

storing reference pattern data consisting of at least n×

m bits of a reference pattern, where m and n are integers smaller than M and N, respectively;

calculating first correlations between sub-images each consisting of n×

m bits of said image pattern data and said reference pattern data, respectively each of said first correlations being expressed as R(X), where X is a variable factor representing a region storing one of said second parts; and

recognizing the position of a pattern most identical to said reference pattern, by emphasizing the maximum value of said first correlations by converting each of said first correlations R(X) into a second correlation expressed as [R(X)-R(X-α

)]-[R(X+α

)-R(X)], where α

is a predetermined value determined in accordance with the size of said reference pattern data.

12. A pattern recognition method as set forth in claim 11, wherein said step of calculating first correlations comprises the steps of:

storing n bits of one of said parts into a first n-bit shift register, said n bits being output from a column in said one of said parts having addresses from (X, Y+y) to (X+n, Y+y), where X, Y, and y are variable integers under the conditions 1≦

X≦

N-n, 1≦

Y≦

M-m, and 1≦

y≦

m;

storing n bits of said reference pattern data into a second n-bit shift register, said n bits being output from a column in said reference pattern data having addresses from (1, y) to (n, y);

detecting coincidences between said stored n bits of said image pattern data and said stored n bits of said reference pattern data in a bit-to-bit fashion, so as to provide matching-bit signals with respect to said n bits of said image pattern data;

summing the number of said matching-bit signals with respect to said column in said one of said parts;

adding the result of said first adding to a previously-obtained number of matching-bit signals with respect to columns having addresses from (X, Z) to (X+n, Z), where Z represents a variable integer smaller than the integer Y+y, so as to provide a first correlation between n×

y bits of said image pattern data having addresses from (X, Y) to (X+n, Y+y) in said one of said parts and n×

y bits of said reference pattern data; and

storing the result of said adding step into a plurality of correlation storing regions for storing the resultant correlations R(1), R(2), ---R(X), --- R(N-n), respectively, where R(X) is the first correlation with respect to n×

m bits of said image pattern data in the address from (X, Y) to (X+n, Y+m).

13. A pattern recognition method as set forth in claim 12, wherein said step of recognizing the position of a pattern comprises the steps of:

storing the maximum value of said correlations;

comparing each of said second correlations with said maximum value which has previously been stored; and

updating said stored maximum value to equal said second correlations when said second correlation is greater than said stored maximum value.

14. A pattern recognition method as set forth in claim 13, wherein, said step of converting the picked-up image into image pattern data consisting of binary-coded signals is followed by the step of:

compacting a predetermined number of neighboring bits of said binary-coded signals into a single bit, the sign of said single bit being determined in accordance with the number of "1" or "0" signals in said neighboring bits, so as to provide compacted image pattern data.

15. A pattern recognition method as set forth in claim 14, wherein said step of updating said stored maximum value into said second correlation is followed by the step of:

storing an address of said image pattern data into an address register when said image pattern data provides the maximum value of said second correlations;

calculating the position of a view window for taking out a small sub-image of said image pattern data from said pretreatment circuit, said small sub-image including the data which provides the maximum value of said second correlations after all bits of said first sub-image of said image pattern data are processed in said step of calculating first correlations and in said step of recognizing the position of a pattern; and

detecting a middle point of a pattern in said small sub-image.