Pattern recognition method and apparatus

Claim 2

A pattern recognition method comprising the steps of sensing an image of an area of patterns (1); converting and storing the sensed image as N x M bits of binary coded image pattern data, where M and N are integers; calculating first correlations between parts (ID), each consisting of n x m bits where n and m are integers smaller than N and M respectively, in the image pattern data and n x m bits of reference pattern data (RD), each of the first correlations being expressed as R(X), where X is a variable factor representing a region of the image pattern data; and 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 + a) - R(X)], where a is a predetermined value determined in accordance with the size of the reference pattern data whereby the position of a pattern in the sensed image most identical to the reference pattern can be recognized.

Claim 3

A pattern recognition method according to claim 1, wherein the step of calculating first correlations comprises the steps of comparing n bits of one of the parts (ID) of the image pattern data corresponding to a column in the one of the'parts having addresses from (X, Y + y) to (X + n, Y + y), where X, Y, and y are variable integers satisfying the conditions 1 < x ≦ N - n, 1 ≦ Y ≦ M - m, and 1 ≦ y ≦ m, with nbitsofthe reference pattern data (RD), the n bits corresponding to a column in the reference pattern data having addresses from (l,y) to (n, y); detecting coincidences between the n bits of the image pattern data and the n bits of the reference pattern data in a bit-to-bit fashion; summing the number of detected coincidences with respect to the column in the one of the parts of the image pattern data; adding the result of this summation to a previously-obtained summation of detected coincidences 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 x y bits of the image pattern data having addresses from (X, Y) to (X + n, + y) in the one of the parts and n x y bits of the reference pattern data; and storing the results of the adding step.

Claim 4

A pattern recognition method according to claim 1 or claim 2, -further comprising comparing each of the second correlations with a maximum value which has previously been stored; and updating the stored maximum value with the second correlation when the second correlation is greater than the stored maximum value.

Claim 5

A method according to claim 1 or claim 2, further comprising adding the first and second correlations; comparing the added first and second correlations with a stored preset value; and updating the stored value with the result of adding the first and second correlations if the result is greater than the stored value.

Claim 6

A pattern recognition method according to claim 3 or claim 4, wherein the updating step is followed by the step of storing an address of the image pattern data corresponding to the maximum value stored; calculating the position of a view window for taking out a small part of the image pattern data, the small part including the data which provides the maximum stored value after all bits of the first part of the image pattern data are processed in the steps of calculating first and second correlations; and detecting a middle point of a pattern in the small part.

Claim 7

A pattern recognition method according to any of the preceding claims, wherein the image pattern data is compacted, the step of converting the sensed image into binary-coded image pattern data comprising preliminary binary-coding followed by the step of compacting a predetermined number of neighbouring bits of the preliminary binary-coded data into a single bit, the value of the single bit being determined in accordance with the number of "1" of "0" bits in the neighbouring bits, so as to provide compacted image pattern data,

Claim 8

Pattern recognition apparatus comprising image sensing means (2) for sensing an image of an area of patterns (1); pretreatment means (5) for converting the output! of the image sensing means (2) into binary-coded image pattern data; a pattern memory (9) having N x M addresses for storing N x M bits of the image pattern data, where M and N are integers; a reference pattern memory (12) having at least n x m addresses for storing reference pattern data consisting of n x m bits of a reference pattern, where m and n are integers smaller than M and N, respectively; first correlation calculating means (10) for calculating first correlations between parts each consisting of n x m bits in the image pattern data and the reference pattern data, each of the first correlations being expressed as R(X), where X is a variable factor representing a region storing one of the parts in the pattern memory (9); and a second correlation calculating means (16) for converting each of the first correlations R(X) into a second correlation expressed as [R(X) - R(X - α)] -R(X + a) - R(X)], where a is a predetermined value determined in accordance with the size of the reference pattern data, whereby the position of a pattern most identical to the reference pattern can be recognized by emphazing the maximum value of the first correlations.

Claim 9

Pattern recognition apparatus comprising image sensing means (2) for sensing an image of an area of patterns (1); pretreatment means (5) for converting the output! of the image sensing means (2) into binary-coded image pattern data; a pattern memory (9) having N x M addresses for storing N x M bits of the image pattern data, where M and N are integers; a reference pattern memory (12) having at least n x m addresses for storing reference pattern data consisting of n x m bits of a reference pattern, where m and n are integers smaller than M and N, respectively; first correlation calculating means (10) for calculating first correlations between parts each consisting of n x m bits in the image pattern data and the reference pattern data, each of the first correlations being expressed as R(X), where X is a variable factor representing a region storing one of the parts in the pattern memory (9); and a second correlation calculating means (16) for converting each of the first correlations R(X) into a second correlation expressed as [R(X) - R(X - α)] -R(X + a) - R(X)], where a is a predetermined value determined in accordance with the size of the reference pattern data, whereby the position of a pattern most identical to the reference pattern can be recognized by emphazing the maximum value of the first correlations.

Claim 10

Pattern recognition apparatus according to claim 7, wherein the first correlation calculating means (10) comprises a first n-bit shift register (22) for storing n bits of one of the parts, the n bits being output from a column of the pattern memory (9), the column having addresses from (X, Y + y) to (X + n, Y + y), where X, Y, and y are variable integers satisfying the conditions 1< X < N - n, 1 < Y < M - m, and I < y < m; a second n-bit shift register (23) for storing n bits of the reference pattern data, the n bits being output from a column of the reference pattern memory (14), the column having addresses from (1, y) to (n, y); a matching-bit detecting circuit (24) for detecting coincidences between the n bits of the image pattern data stored in the first n-bit shift register (22) and the n bits of the reference pattern data stored in the second n-bit shift register (23) in a bit-to-bit fashion, so as to provide matching-bit signals with respect to the n bits of the image pattern data; a first adder (25) for summing the number of matching-bit signals with respect to the column having addresses from (X, Y + y) to (X + n, Y + y); a second adder (27) for adding the output of the 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 x y bits of the image pattern data stored in the addresses from (X, Y) to (X + n, Y + y) in the one of the parts stored in the pattern memory (9) and n x y bits of the reference pattern data stored in the addresses (1, 1) to (n, y) of the reference memory circuit (14); and a line memory circuit (29) having a plurality of first-correlation storing regions (29-1 ... 29-(N-nr) for storing the outputs of the second adder (27), the correlation storing regions being adapted to store the resultant first correlations R(l), R(2), ---, R(X), ---, R(N - n), respectively, where R(X) is the first correlation with respect to n x m bits of the image pattern data in the addresses from (X,Y) to (X + n, Y + m).

Claim 11

Pattern recognition apparatus according to claim 8, wherein the first and second n-bit shift registers (22, 23) each comprises n locations each for storing one bit.

Claim 12

Pattern recognition apparatus according to claim 9, wherein the matching-bit detecting circuit (24) comprises ENOR circuits, each of the ENOR circuits having a first input connected to one of the locations in the first n-bit shift register (22) and a second input connected to the corresponding location in the second n-bit shift register (23).

Claim 13

Pattern recognition apparatus according to any of claims 8 to 10, wherein the first correlation calculating means (10) further comprises a memory control means (28) for controlling the input operation and the output operation of the line memory circuit (29), whereby the outputs of the line memory circuit are supplied to the second adder (27) after the first adder (25) outputs the number of matching-bit signals.

Claim 14

Pattern recognition apparatus according to any of claims 8 to 11, wherein the first correlation calculating means (10) further comprises a data register (26) for tetnporarily storing the outputs of the second adder (27) or of the line memory circuit (29).

Claim 15

Pattern recognition apparatus according to any of claims 7 to 12, wherein-the second correlation calculating means (16) comprises a first subtracting circuit (31) for calculating [R(X) - R(x - α)], a second subtracting circuit (32) for calculating [R(X + a) - R(X)], and a third subtracting circuit (33) for subtracting the output of the second subtracting circuit (32) from the output of the first subtracting circuit (31).

Claim 16

Pattern recognition apparatus according to any of claims 7 to 13, further comprising maximum-value storing means for storing the maximum value of the outputs of the second correlation calculating means (16), and a comparator for comparing each output from the second correlation calculating - means (16) with the maximum value previously stored in the maximum-value storing means, so as to provide a trigger to the maximum-value storing means to update the contents of the maximum-value storing means with the output of the second correlation calculating means when the output value of the second correlation calculating means is greater than the stored maximum value.

Claim 17

Pattern recognition apparatus according to any of claims 7 to 13, further comprising adding means (15) for adding the outputs from the first and second correlation calculating means (10, 16); maximum value storing means (17) for storing the maximum output from the adding means (15); and a comparator (18) for comparing the output from the adding means (15) with the maximum value previously stored by the storing means (17) so as to provide a trigger to the storing means (17) to update the contents of the storing means (17), with the output of the adding means when the output of the adding means is greater than the stored value.

Claim 18

Pattern recognition apparatus according to claim 14 or claim 15, further comprising an address register (19) for storing an address of the image pattern data in response to the trigger from the comparator; a view-window determining circuit (20), connected to the output of the address register (19),for calculating the position of a view window for taking out a small part of the image pattern data, the small part including the data which provides the maximum value stored invthe maximum-value storing means after all bits of the first part of the image pattern data are processed by the first correlation calculating circuit (10) and by the second correlation calculating means (16), the calculation of the position of the view window being carried out by using the address stored in the address register (19); and a middle-point detecting circuit (21) connected to the output of the view window determining circuit (20), for detecting the middle point of a pattern in the small part.

Claim 19

Pattern recognition apparatus according to any of claims 7 to 16, further comprising data compaction means (7) inserted between the pretreatment circuit (5) and the pattern memory (9), for compacting a predetermined number of neighbouring bits of the binary-coded data into a single bit, the sign of the single bit being determined in accordance with the number of "1" or "0" bits in the neighbouring bits, so as to provide compacted image pattern data to the pattern memory (9).