Character recognition method

• US 5,067,165 A
• Filed: 04/16/1990
• Issued: 11/19/1991
• Est. Priority Date: 04/19/1989
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Nishida, Hirobumi
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/508,727
• Time in Patent Office: 582 Days
• Field of Search: 382/40, 382/19, 382/25, 382/34, 382/37
• US Class Current: 382/195
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/196 using sequential comparisons of the image signals with a plurality of references
• CPC Class Codes: G06V 30/262 using context analysis, e.g. lexical, syntactic or semantic context

Abstract

A method for recognizing a character string made of alphanumeric characters comprises processes of providing a dictionary storing each alphanumeric character in a form of a graph including nodes and links, each of the nodes corresponding to the structural elements of the character and carrying an attribute representing thereof, each of the links representing the geometrical relationship which exists between the nodes connected by the link, extracting the structural elements together with the geometrical relationship existing therebetween from the character string read from the document starting from a starting location at one end of the character string, verifying that a corresponding structural element and geometrical relationship exist in the dictionary, predicting the structural elements and the geometrical relationship existing in the character string at a location immediately adjacent to the former location in the character string, based on the result of verification, and recognizing the character string by moving the location step by step consecutively along the character string towards the second end.

Claims

1. A method for recognizing a character string comprising one or more alphanumeric characters read from a document, said character string being defined by a first end and a second end, each of the alphanumeric characters comprising a plurality of structural elements disposed with a predetermined geometrical relationship so as to form the alphanumeric character, said method comprising the processes of:

(a) providing a dictionary having each alphanumeric character stored as a graph, the graph comprising nodes and links connecting the nodes;

(1) each of the nodes corresponding to one of the structural elements and carrying an attribute representative thereof; and

(2) each of the links representing the geometrical relationship which exists between the nodes which are connected by the link;

(b) reading a character string from a document;

(c) extracting one or more structural elements and a geometrical relationship existing therebetween from the character string read from the document, starting from a starting location of character recognition at the first end of the character string and proceeding consecutively to the second end of the character string;

(d) verifying that the structural elements and the geometrical relationship extracted in the process of extraction exist in the dictionary, wherein said step of verifying includes searching the dictionary;

(1) starting from a simple alphanumeric character having a small number of structural elements; and

(2) proceeding to complex alphanumeric characters having a large number of structural elements;

(e) predicting the structural elements and the geometrical relationship existing in the character string at a location immediately adjacent to the former location in the character string, based on the result of the process of verification, by assuming a candidate character; and

(f) recognizing the character string by moving the location step by step consecutively along the character string towards the second end, while repeatedly performing the processes of extraction, verification, and prediction in each of the steps.

2. A method as claimed in claim 1 in which said character string is defined by a left end and a right end respectively in correspondence to the first end and the second end, and said process of recognition is performed while moving by step, consecutively from the left end of the character string to the right end of the character string.

3. A method as claimed in claim 1 in which said dictionary stores the characters as a plurality of graphs each corresponding to a character, said plurality of graphs being arranged into a network comprising a plurality of network nodes and a plurality of directed network links connecting the network nodes, wherein each of said network nodes indicated by the directed network link, exiting from a previous network node, inlcudes all of the structural elements of the character corresponding to the previous network node, and each of the network links connecting the network nodes represents the difference between the characters corresponding to the network nodes connected by the network link.

4. A method as claimed in claim 3 in which said processes of extraction, verification, and prediction are performed along the directed network links, starting from an initial state.

5. A method as claimed in claim 4 in which said process of recognition comprises a process of evaluating a loss function indicative of failure of recognition each time the location of character recognition process for recognizing the character string moves one step, and a process of selecting the character string which minimizes the loss function.