Character recognition system and method multi-bit curve vector processing

• US 4,177,448 A
• Filed: 06/26/1978
• Issued: 12/04/1979
• Est. Priority Date: 06/26/1978
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Brayton, Robert K.
• Primary Examiner(s): Thesz, Joseph M.
• Application Number:
  US05/919,535
• Time in Patent Office: 526 Days
• Field of Search: 340/146.3 AE, 340/146.3 AC, 340/146.3 AQ, 340/146.3 D, 340/146.3 Q, 340/146.3 T
• US Class Current: 382/160
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G06V 10/40 Extraction of image or video features
• CPC Class Codes: G06V 10/75 Organisation of the matching processes, e.g. simultaneous or sequential comparisons of image or video features; Coarse-fine approaches, e.g. multi-scale approaches; using context analysis; Selection of dictionaries
• CPC Class Codes: G06V 30/192 using simultaneous comparisons or correlations of the image signals with a plurality of references
• CPC Class Codes: G06V 30/194 References adjustable by an adaptive method, e.g. learning

Abstract

An automatic character recognition system and method for identifying an unknown character which is one of a class of known characters. The system is set up using known specimen characters from a large character training set which must first be selected based on the use to which the character recognition will be put. Using the selected set, features and shapes of the character vocabulary in the set are obtained using selected feature scan parameters, are processed as a plurality of representative and normalized pieces of curves and are then stored in the form of binary coded representations. The system set-up also includes selecting and storing canonic shape parameters. The canonic shapes are separate pieces or segments of lines and curves which are selected on the basis that their shapes can be found as component parts or within a significant number of the characters within the character set. Having selected a character training set, selected and stored feature scan parameters and selected and stored canonic shape parameters, the system set-up procedure is completed. The next procedure is referred to as "system training" in which the individual characters within the large character training set are processed with the prior knowledge of the identity of each character being processed. This consists of an individual curve following for each of the plurality of characters on the character set and recording the path coordinates resulting from the curve following operation. The path coordinates are matched against the stored canonic shape parameters and the "best match" features are encoded. Statistical tables are then formed based on the best match relationships between the known training characters and the canonic shapes. The character recognition system is now capable of hereinafter operating with and identifying unknown characters belonging to the recognition space character set. In this procedure, the unknown character is examined using feature scan parameters to extract the features from the unknown character, providing complex vectors of the measured path coordinates of the extracted features which are matched against the stored canonic shape parameters by computing complex inner products, and a best match feature is determined.

Finally, a plurality of row vectors are extracted from the statistical tables and combined to form a product vector. The largest component of the product vector is selected, and the column index j of the maximum component is noted. The unknown character is then identified as being a member of the character membership class whose column index is j.

Claims

1. In an automatic character recognition system for identifying an unknown character wherein said unknown character is one of a class of a plurality of known characters, a scanning and training structure including:

means for storing a binary indicia a plurality of separate segments of character shapes, said separate segments being conformable to segments included within the shapes of said characters within said plurality of known characters, said binary encoded separate segments being referred to as canonic shapes and each being identified in said storage means by a binary encoded shape index number,

means for processing and manifesting a first known character from said character class in a digital matrix format of stored binary indicia,

means connected to said processing and manifesting means for digitally scanning said stored first known character indicia using a first set of selected scan parameters, said selected scan parameters designating a specific start position, scan length, scan binary indicia transition and direction for said scanning function, said digital scanning function producing a first binary encoded path vector in the form of a multi-bit binary word including the starting coordinates of said scan and a plurality of further binary coordinates of said known character along the selected length of said scan,

means connected to said digital scanning and encoding means and to said binary indicia storing means for performing the complex inner product function of said binary encoded path vector and each of said stored canonic shapes to produce a plurality of complex numbers encoded in binary form, one for each complex inner product performed with each canonic shape, each of said binary encoded complex inner product numbers including a magnitude value representative of the similarity between said binary encoded path vector and each of said canonic shapes, and an angle value representative of the angular offset of the encoded path vector relative to each of said canonic shapes,

means connected to said complex inner product function means for determining the magnitude of each of said encoded complex inner product number and selecting the largest magnitude number and recording the shape index of the canonic shape which produced said largest magnitude complex inner product number,

means connected to said magnitude determining means for encoding at least said recorded shape index and said angle value within an N bit vector,

at least a first storage plane means including a separate storage column for each of different one of said characters in said class of a plurality of characters and 2^N storage rows for each different one of possible N bit vectors,

and means connected to said N bit vector encoding means and said first storage plane means of entering a first storage indicia into said at least first storage plane means at a discrete storage location corresponding to the column associated with said first known character and to the row associated with said encoded N bit vector associated with said recorded shape index and angle value.

2. In said automatic character recognition system according to claim 1,

said processing and manifesting means including a character memory storage means for storing a character in a digital matrix format of horizontal and vertical binary storage elements and means for determining the boundaries of the character stored in said digital matrix,

and wherein said digital scanning means includes a curve follower structure which operates in accordance with a selected scan parameter designating a specific start position at one of the sides of said horizontal and vertical digital matrix format and scans in one of said horizontal and vertical directions until a binary indicia of said stored character is detected, and follows the binary indicia of said stored character along the character for a character segment length designated by said selected scan parameter to produce said binary encoded path vector in the form of a multi-bit binary word.

3. In an automatic character recognition system according to claim 1, a scanning and training structure further including a plurality of k of said storage plane means,

wherein said digital scanning means repeatedly scans said first known character indicia k times, each of said k scans being performed using a different set of selected scan parameters for producing k binary encoded path vectors in the form of k separate milti-bit binary words,

wherein said complex inner product function performing means performs the complex inner product function of each of said k binary encoded path vectors and each of said stored canonic shapes to produce k separate pluralities of complex numbers encoded in binary form, each one of said k separate pluralities of encoded complex numbers including an encoded complex number for each complex inner product performed with each canonic shape and a separate different one of said k binary encoded path vectors, each of said binary encoded complex inner product numbers including a magnitude value representative of the similarity between its associated one of said k binary encoded path vectors and each of said canonic shapes, and an angle value representative of the angular offset of its associated one of said k binary encoded path vectors relative to each of said canonic shapes,

wherein said magnitude determining and recording means and said shape index and angle value encoding means provide a plurality of k separate of N bit vectors, one for each of said k different scans, said k separate N bit vectors being representative of the shape index and angle value of the largest magnitude inner complex number produced by each of said k scan path vectors and said plurality of canonic shapes,

and wherein said storage indicia entering means enters a separate storage indicia into each of said k storage planes at discrete storage locations corresponding to the column associated with said first known character and to the row associated with each of said separate encoded N bit vectors associated with said recorded shape index and angle value produced relative to each of said separate k scans using a different set of selected scan parameters.

4. In an automatic character recognition system according to claim 3, a scanning and training structure wherein said manifesting and processing means processes and manifests a plurality of different known characters from said character class in sequence and wherein said operation functions of said scanning and training structure are repeated for each of said different known characters of said plurality to produce storage indicia in each of said k storage planes at discrete storage locations corresponding to the columns associated with of said plurality of different known characters and to the rows associated with said recorded shape indicies and angle values produced relative to each of said separate k scans using different sets of selected scan parameters for said plurality of different known characters.

5. An automatic character recognition system including a scanning and training structure according to claim 4 wherein said plurality of different known characters processed and manifested are handwritten alphanumeric characters from a character class of said handwritten alphanumeric characters.

6. In an automatic character recognition system according to claim 4, means for identifying an unknown character of said class of a plurality of known characters after said scanning and training operation, including:

means for entering said unknown character into said processing and manifesting means for manifesting said unknown character in a digital matrix format of stored battery indicia,

means for repeatedly digitally scanning said stored unknown character indicia k separate times using a k different sets of selected scan parameters one for each separate scan, each of said selected scan parameters designating a specific start position, scan length, binary indicia transition and direction for said scanning function, said digital scanning function producing a k binary encoded path vectors in the form of k multi-bit binary words including the starting coordinates of each of said scans and a plurality of further binary coordinates of said unknown character along said selected lengths of each of said scans,

wherein said complex inner product function performing means performs the complex inner product function of each of said k binary encoded path vectors produced by scanning said unknown character and each of said stored canonic shapes to produce k separate pluralities of complex numbers encoded in binary form, each one of said k separate pluralities of encoded complex numbers including an encoded complex number for each complex inner product performed with each canonic shape and a separate different one of said k binary encoded path vectors, each of said binary encoded complex inner product numbers including a magnitude value representative of the similarity between its associated one of said k binary encoded path vectors and each of said canonic shapes, and an angle value representative of the angular offset of its associated one of said k binary encoded path vectors relative to each of said canonic shapes,

wherein said magnitude determining and recording means and said shape index and angle value encoding means provide a plurality of k separate N bit vectors, one for each of said k different scans of said unknown character, said k separate N bit vectors being representative of the shape index and angle value of the largest magnitude inner complex number produced by each of said k scan path vectors and said plurality of canonic shapes, and

wherein said first of said k separate N bit vectors specifies a specific row of the first one of said k storage planes, said second of said N bit vectors specifies a specific row of the second one of said k storage planes, and so on to said kth N bit vector which specifies a specific row of the kth one of said storage planes,

means for obtaining and storing the contents of each of said specified k rows, one from each of said k storage planes, specified by each of said k-N bit vectors,

means for performing the product vector of the value of the first column location contents of each of said specified k rows, and for the values of each of the succeeding column locations of each of the other specified k rows to produce a plurality of products vector components, one for each column location of said rows,

means for determining and selecting the largest one of said components of said product vector and storing the column location of said largest product vector component, and means for indicating the known character associated with said one selected column location associated with said largest product vector component, said unknown character being recognized as said known character.

7. In a character recognition method for identifying an unknown character wherein said unknown character is one of a class of a plurality of known characters, a plurality of scanning and training steps including:

the step of storing in binary indicia a plurality of separate segments of character shapes, said separate segments being conformable to segments included within the shapes of said characters within said plurality of known characters, said binary encoded separate segments being referred to as canonic shapes and each being identified in said storage means by a binary encoded shape index number,

the steps of processing and manifesting a first known character from said character class in a digital matrix format of stored binary indicia,

the step of digitally scanning said stored first known character indicia using a first set of selected scan parameters, said selected scan parameters designating a specific start position, scan length, binary indicia transition and direction for said scanning step, said digital scanning step producing a first binary encoded path vector in the form of a multi-bit binary word including the starting coordinates of said scan and a plurality of further binary coordinates of said known characters along the selected length of said scan,

the step of performing the complex inner product function of said binary encoded path vector and each of said stored canonic shapes to produce a plurality of complex numbers encoded in binary form, one for each complex inner product performed with each canonic shape, each of said binary encoded complex inner product numbers including a magnitude value representative of the similarity between said binary encoded path vector and each of said canonic shapes, and an angle value representative of the angular offset of the encoded path vector relative to each of said canonic shapes,

the steps of determining the magnitude of each of said encoded complex under product number and selecting the largest magnitude number and recording the shape index of the canonic shape which produced said largest magnitude complex inner product number,

the step of encoding at least said recorded shape index and said angle value within an N bit vector,

the step of providing at least a first storage plane means including a separate storage column for each of different one of said characters in said class of a plurality of characters and 2^N storage rows for each different one of possible N bit vectors,

and the step of entering a first storage indicia into said at least first storage plane means at a discrete storage location corresponding to the column associated with said first known character and to the row associated with said encoded N bit vector associated with said recorded shape index and angle value.

8. A character recognition method according to claim 7, including said plurality of scanning and training steps, wherein said step of providing at least a first storage plane means includes the providing of a plurality of k of said storage plane means,

wherein said step of digital scanning includes the steps or repeatedly scanning said first known character indicia k times, each of said k scans being performed using a different set of selected scan parameters for producing k binary encoded path vectors in the form of k separate multi-bit binary words,

wherein said step of performing said complex inner product function includes the steps of performing the complex inner product function of each of said k binary encoded path vectors and each of said stored canonic shapes to produce k separate plurality of complex numbers encoded in binary form, each one of said k separate plurality of encoded complex numbers including an encoded complex number for each complex inner product performed with each canonic shape and a separate different one of said k binary encoded path vectors, each of said binary encoded complex inner product numbers including a magnitude value representative of the similarity between its associated one of said k binary encoded path vectors and each of said canonic shapes, and an angle value representative of the angular offset of its associated one of said k binary encoded path vectors relative to each of said canonic shapes,

wherein said steps of determining and recording said magnitude and encoding said shape index and angle value includes the steps of providing of k separate N bit vectors, one for each of said k different scans, said k separate N bit being representative of the shape index and angle value of the largest magnitude inner complex number produced by each of said k scan path vectors and said plurality of canonic shapes,

and wherein said step of entering storage indicia includes the steps of entering a separate storage indicia into each of said k storage planes at discrete storage locations corresponding to the column associated with said first known character and to the row associated with each of said separate encoded N bit vectors associated with said recorded shape index and angle value produced relative to each of said separate k scans using a different set of selected scan parameters.

9. A character recognition method according to claim 8 including said plurality of scanning and training steps wherein said manifesting and processing step includes the steps of processing and manifesting a plurality of different known characters from said character class in sequence and wherein said plurality of said scanning and training steps are repeated for each of said different known characters of said plurality to produce storage indicia in each of said k storage planes at discrete storage locations corresponding to the columns associated with of said plurality of different known characters and to the rows associated with said recorded shape indicies and angle values produced relative to each of said separate k scans using different sets of selected scan parameters for said plurality of different known characters.

10. A character recognition method according to claim 9, further including steps for identifying an unknowncharacter of said class of a plurality of known characters after said plurality of scanning and training steps are performed, including:

the steps of processing and manifesting said unknown character in a digital matrix format of stored binary indicia,

the steps of repeatedly digitally scanning said stored unknown character indicia k separate using a k different sets of selected scan parameters one for each separate scan, each of said selected scan parameters designating a specific start position, scan length, binary indicia transition and direction for said scanning function, said digital scanning function producing a k binary encoded path vectors in the form of k multi-bit binary words including the starting coordinates of each of said scans and a plurality of further binary coordinates of said unknown character along said selected lengths of each of said scans,

the steps of performing the complex inner product function of each of said k binary encoded path vectors produced by scanning said unknown character and each of said stored canonic shapes to produce k separate pluralities of complex numbers encoded in binary form, each one of said k separate pluralities of encoded complex numbers including an encoded complex number for each complex inner product performed with each canonic shape and a separate different one of said k binary encoded path vectors, each of said binary encoded complex inner product numbers including a magnitude value representative of the similarity between its associated one of said k binary encoded path vectors and each of said coanonic shapes, and an angle value representative of the angular offset of its associated one of said k binary encoded path vectors relative to each of said canonic shapes,

wherein said magnitude determining and recording steps and said shape index and angle value encoding steps are performed on each of said k separate pluralities of complex numbers to provide a plurality of k separate N bit vectors, one for each of said k different scans of said unknown character, said k separate N bit vectors being representative of the shape index and angle value of the largest magnitude inner complex number produced by each of said k scan path vectors and said plurality of canoic shapes, and

wherein said first of said k separate N bit vectors produced by said determining, recording and encoding steps specifies a specific row of the first one of said k storage planes, said second of said N bit vectors specifies a specific row of the second one of said k storage planes, and so on to said kth N bit vector which specifies a specific row of the kth one of said storage planes,

the step of obtaining and storing the contents of each of said specified k rows, one from each of said k storage planes, specified by each of said k-N bit vectors,

the steps of performing the product vector of the value of the first column location contents of each of said specified k rows, and for the values of each of the succeeding column locations of each of the other specified k rows to produce a plurality of products vector components, one for each column location of said rows,

the steps of determining and selecting the largest one of said components of said product vector and storing the column location of said largest product vector component, and the step of indicating the known character associated with said one selected column location associated with said largest product vector component, said character being recognized as said known character.