Character reader

• US 4,630,308 A
• Filed: 07/20/1984
• Issued: 12/16/1986
• Est. Priority Date: 08/04/1983
• Status: Expired due to Fees

• Current Assignee: Fuji Electric Corporate Research & Development, Ltd. (Fuji Electric Systems Company Limited)
• Original Assignee: Fuji Electric Company Limited (Fuji Electric Systems Company Limited), Fuji Electric Corporate Research & Development, Ltd. (Fuji Electric Systems Company Limited)
• Inventors: Hongo, Yasuo
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Todd, Jacqueline
• Application Number:
  US06/633,114
• Time in Patent Office: 879 Days
• Field of Search: 382/27, 382/30, 382/33, 382/34
• US Class Current: 382/198
• CPC Class Codes: G06V 10/751 Comparing pixel values or logical combinations thereof, or feature values having positional relevance, e.g. template matching

Abstract

In the particular embodiment of the invention described in the specification, the identity of an unknown character is determined by comparing matrices representing the unknown character with matrices representing known characters and determining the deviation beween matrices for the unknown and each known character. To obtain the matrices to be compared, a transformation chain is expressed in terms of horizontal, vertical and diagonal vectors, permitting all types of transformation chains to be used. Two-dimensional memory units having superposed shift registers are used in comparing matrices to determine minimum deviation.

Claims

1. A pattern recognition apparatus comprising:

(a) means for scanning an unknown pattern and providing a video signal corresponding to an image of the unknown pattern;

(b) binary encoding means for dividing the image into an array of pixel elements and converting the video signals into binary values using a threshold level, each of the binary values corrsponding to a respective one of the pixel elements;

(c) feature extracting means for converting the binary vlaues corresponding to the pixel elements into segments corresponding to the image, each segment being a horizontal series of pixel elements having a first binary value;

(d) memory means for storing the segments corresponding to the image and data representing a pluraltiy of standard patterns K, the data representing each one of the standard patterns comprising;

(i) a standard bit matrix B_S^K (i,j) derived by dividing an image of the standard pattern into a specified array of meshes, each one of the meshes corresponding to a respective element of the matrix B_S^K (i,j), each element of the matrix having the first or a second binary value depending respectively upon whether or not a portion of the standard pattern is present in the corresponding mesh, the matrix B_S^K (i,j) being reducible to a corresponding cluster expression matrix having mask elements, blank elements, and transformation elements of a transformation chain,

(ii) a mask bit matrix B_M^K (i.j) having elements corresponding to respectivel ones of the meshes of the specified array, each element of the matrix B_M^K (i,j) having the second or the first binary value depending respectively upon whether or not the element is a mask element,

(iii) transformation bit matrices D₁, D₂, D₃, D₄, D₅, D₆, D₇ and D₈ each having elements of a first binary value if the elements of D₁ to D₈ correspond respectively to a present transformation element at the left end of a horizontal transformation chain, at the lower left end of a diagonal transformation chain, at the lower end of a vertical transformation chain, at the lower right end of a diagonal transformation chain, at the right end of a horizontal transformation chain, at the upper right end of a diagonal transformation chain, and at the upper end of a vertical transformation chain, at the upper left end of a diagonal transformation chain;

e. operating means for performing preprogrammed operations on the data stored in the memory means inclduing;

(i) means for comparing a width and a height of the unknown pattern with the width and height of a search frame,

(ii) means for dividing the image of the unknown pattern into the specified array of meshes and deriving a bit matrix B(i,j) of the image having elements corresponding to reapective ones of the meshes of the specified array, each element of the matrix B(i,j) having the first or the second binary value depending respectively upon whether or not a portion of the unknown pattern is present in the corresponding mesh,

(iii) means for matching the unknown pattern to one of the standard patterns by computing the deviation D^K (B) between the unknown pattern and each one of the standard patterns, the deviation D^K (B) being computed by performing a prescribed operation on at least a corresponding block of the matrix B(i,j) and the matrices B_S^K (i,j), B_M^K (i,j), D₁ to D₈, representing each one of the standard patterns wherein the prescribed operation is defined as ##EQU3## where D^K is a transformation matrix operator comprising transformation bit matrices D₁ to D₈ for the standard pattern K.

2. A pattern recognition apparatus according to claim 1, wherein the prescribed operation is performed to identify one of the standard patterns providing the smallest deviation d₁ and another one of the standard patterns providing the second smallest deviation d₂ and wherein the unknown pattern is matched to the one of the standard patterns providing the smallest deviation d₁, if d₁ and d₂ satisfy the criteria

3. In a pattern recognition apparatus comprising

(a) means for scanning an unknown pattern and providing a video signal corresponding to an image of the unknown pattern;

(b) binary encoding means for dividing the image into an array of pixel elements and converting the video signals into binary values using a threshold level, each of the binary values corresponding to a respectivel one of the pixel elements;

(c) feature extracting means for converting the binary values corresponding to the pixel elements into segments corresponding to the image, each segment being a horizontal series of pixel elements having a first binary value;

(d) storing means for storing the segments corresponding to the image;

(e) operating means for performing preprogrammed operations on the segments corresponding to the image including;

(i) means for comparing a width and a height of the unknown pattern with the width and height of a search frame;

(ii) means for dividing the image of the unknown pattern into a specified array of meshes and deriving a bit matrix B(i,j) of the image having elements corresponding to respective ones of meshes of the specified array, each element of the matrix B(i,j) having the first or a second binary value depending respectively upon whether or not a portion of the unknown pattern is present in the corresponding mesh;

a deviation calculation unit, comprising;

first memory means for storing the data respresenting a pluraltiy of standard bit matrices B_S^K (i,j) for each one of a plurality of standard patterns K, said standard bit matrix being derived by dividing an image of the standard pattern into specified array of meshes, each one of the meshes corresponding to a respective element of the matrix B_S^K (i,j), each element of the matrix having the first or the second binary value depending respectively upon whether or not a portion of the standard pattern is present in the corresponding mesh, the matrix B_S^K (i,j) being reducible to a corresponding cluster expression matrix having mask elements, blank elements, and transformation elements of a transformation chain;

second memory means for storing the data representing a mask bit matrix B (i,j) for each one of the standard patterns, said mask bit matrix B (i,j) having elements corresponding to respecitve ones of the meshes of the specified array, each element of the matrix B (i,j) having the second or the first binary value depending respectively upon whether or not the element is a mask element;

third memory means for storing transformation bit matrices D₁, D₂, D₃, D₄, D₅, D₆, D₇ and D₈, for each of the stanrdar patterns, where each matrix has elements of a first binary value if the elements of D₁ to D₈ correspond respectively to a present transformation element at the left end of a horizontal transformation chain, at the lower left end of a diagonal transformation chain, at the lower end of a vertical transformation chain, at the lower right end of a diagonal transformation chain, at the right end of a horizontal transformation chain, at the upper right end of a diagonal transformation chain, at the upper end of a vertical transformation chain, at the upper left end of a diagonal transformation chain;

fourth memory means for storing said bit matrix B(i,j) for the unknown pattern;

deviation calculating means for matching the unknown pattern to one of the standard patterns by computing the deviation D^K (B) between the unknown pattern and each of the standard patterns, the deviation D^K (B) being computed by performing a prescribed operation on at least a corresponding block of the matrix B(i,j) and the matrices B_S^K (i,j), B_M^K (i,j) and D₁ to D₈ representing each one of the standard patterns, wherein the prescribed operation is defined as ##EQU4## where D^K is a transformation operator comprising transformation matrices D₁ to D₈ for the stanrdard pattern K.

4. The deviation calculation unit of claim 3, wherein said deviation calculating means includes:

transformation calculating means and for performing the prescribed operation B_M^K (i,j)·

D^K (B(i,j)), l-1 times, said calculating means including

(i) means for logically AND-ing said transformation bit matrices with said bit matrix B(i,j) to obtain eight distinct values,

(ii) means for logically OR-ing said distinct values to obtain a ninth value,

(iii) means for logically AND-ing said ninth value with said mask matrix B_M^K (i,j) to obtain a tenth value,

(iv) means for substituting said bit matrix B(i,j) with said tenth value, where l represents the length of the transformation chain of the standard pattern K;

and gating means for logically XOR-ing said tenth value with said standard bit matrix to obtain the deviation D_K (B) between the unknown pattern and the standard pattern.

5. The deviation calculation unit of claim 3, wherein said transformation calculating means includes a plurality of two-dimensional memory means, each including a pluraltiy of shift registers of a predetermined capacity, arranged to successively read out data resulting from logically AND-ing the transformation matrices D₁ to D₈ with the bit matrix B(i,j) of the unknown character.