System and method for automated symbolic recognition including evidence-based technique

• US 7,239,749 B1
• Filed: 04/18/2003
• Issued: 07/03/2007
• Est. Priority Date: 04/18/2003
• Status: Expired due to Fees

• Current Assignee: Kamran Reihani
• Original Assignee: Kamran Reihani
• Inventors: Reihani, Kamran
• Primary Examiner(s): Mancuso; Joseph
• Assistant Examiner(s): DULANEY, KATHLEEN YUAN
• Application Number:
  US10/419,482
• Time in Patent Office: 1,537 Days
• Field of Search: 382/187, 382/185, 382/186
• US Class Current: 382/186
• CPC Class Codes: G06V 30/373 using a special pattern or subpattern alphabet

Abstract

An automated symbolic recognition system and method includes an evidence-based technique to significantly reduce the alphanumeric candidate symbol list.

Claims

1. A method of automatically recognizing alphanumeric symbols, comprising:

(a) receiving digital information indicative of each unrecognized alphanumeric symbol;

(b) computing one or more arcpolys for each unrecognized alphanumeric symbol;

(c) identifying at least one of a set of structural and a set of topological features for each arcpoly of each unrecognized alphanumeric symbol;

(d) wherein a set of topological relationships for each pair of arcpolys each comprises a one-of-nine topological connection code and separation, and wherein topological relational features are also automatically classified;

(e) generating and storing a plurality of candidate lists representative of a complete set of characters; and

(f) generating a reduced list of candidate alphanumeric symbols from the plurality of candidate lists based on one or more symbolic representations of each arcpoly of the unrecognized alphanumeric symbol and the stored plurality of candidate lists so that the unrecognized alphanumeric symbol can be recognized, wherein the reduced candidate list contains candidates which are common to the plurality of candidate lists.

2. The method of claim 1, wherein the arcpolys are primarily computed by monitoring rotation changes and identifying the arcpoly when the rotation in one direction stops.

3. The method of claim 1, wherein the unrecognized alphanumeric symbol is either cursive or printed.

4. The method of claim 1, wherein the receiving of digital information is from one of:

a scanner, a memory, a storage device, a wired communication device, and a wireless communication device.

5. The method of claim 1, wherein one or more arcpolys form a polyline and the unrecognized alphanumeric symbol is formed from one or more polylines, one or more polylines are computed from the unrecognized alphanumeric symbol, and the reduced list of candidates is generated based on the symbolic representation of the unrecognized alphanumeric symbol.

6. The method of claim 1, wherein a plurality of unrecognized alphanumeric symbols are sequentially received and recognized.

7. The method of claim 1, wherein a reduced candidate list is a subset of a stored candidate list, and wherein the stored candidate list is associated with a plurality of symbolic representations derived from arcpolys via an inverse mapping.

8. The method of claim 1, wherein the identifying a set of structural features comprises computing a list of primary features for each arcpoly which describe the entire shape and orientation of the arcpoly.

9. The method of claim 5, wherein text line characteristics pertaining to the polylines and arcpolys are computed.

10. The method of claim 7, wherein the inverse mapping comprises establishing a set of links from each symbolic representation to each alphanumeric symbol in the stored candidate list.

11. The method of claim 1, wherein the reduced list of candidate alphanumeric symbols is generated by undergoing multiple series of elimination of candidate alphanumeric symbols.

12. The method of claim 11, wherein the first of the series of elimination of candidate alphanumeric symbols comprises eliminating those candidate symbols that do not match the structural and/or topological features of the unrecognized alphanumeric symbol.

13. The method of claim 12, wherein inverse mappings are established from each arcpoly'"'"'s structure to alphanumeric symbols in the stored candidate list and zero or more pairs of arcpolys'"'"' topological feature encodings as represented by connection codes and separation to alphanumeric symbols in the stored candidate list.

14. The method of claim 13, wherein one or more arcpolys form a polyline, and wherein the candidate alphanumeric symbols that are common to all arcpolys of all polylines form the reduced list of candidate alphanumeric symbols.

15. The method of claim 14, wherein the candidate alphanumeric symbols that are common to all topological feature encodings form the reduced list of candidate alphanumeric symbols.

16. The method of claim 15, wherein the intersection of the structural and topological reduced lists results is used to form a combined reduced list of candidate alphanumeric symbols.

17. The method of claim 11, wherein the second of the series of elimination of candidate alphanumeric symbols comprises detecting one or more one-to-one arcpoly symbolic representations mismatch between a member of the reduced candidate list and the unrecognized alphanumeric symbol.

18. The method of claim 11, wherein the topological features include separation of selected major points on arcpolys such that they better conform to a counterpart in the stored candidate list and wherein the third of the series of elimination of candidate alphanumeric symbols comprises detecting when any of the topological separations exceeds a predefined threshold.

19. The method of claim 1, wherein one or more sets of secondary relational features are computed for the unrecognized alphanumeric symbol and used to compute the alphanumeric dissimilarity value between each member of the reduced candidate list and the unrecognized alphanumeric symbol the alphanumeric dissimilarity value being indicative of the confidence level.

20. The method of claim 7, wherein each of the symbolic representation comprises a pair of logical and subclass symbols.

22. The method of claim 1, wherein generating the plurality of candidate lists representative of a complete set of characters comprises:

generating at least one structurally determined list of candidate alphanumeric symbols based on structural features of the unrecognized alphanumeric symbol; and

generating at least one topologically determined list of candidate alphanumeric symbols based on topological features of the unrecognized alphanumeric symbol.

23. The method of claim 22, wherein generating the reduced list of candidate alphanumeric symbols from the plurality of candidate lists comprises generating the reduced list of candidate alphanumeric symbols via the intersection of the structurally and topologically determined lists of candidate alphanumeric symbols.

21. A system for recognizing an alphanumeric symbol, comprising:

(a) means for receiving digital information indicative of an unrecognized alphanumeric symbol;

(b) means for computing one or more arcpolys of the unrecognized alphanumeric symbol;

(c) means for identifying at least one of a set of structural and a set of topological features of the arcpolys;

(d) wherein means for generating a set of topological relationships for each pair of arcpolys each comprises a one-of-nine topological connection code and separation, and wherein topological relational features are also automatically classified;

(e) means for generating and storing a plurality of candidate lists representative of a complete character set; and

(f) means for generating a reduced list of candidate alphanumeric symbols from the plurality of candidate lists based on one or more symbolic representations of each arcpoly of the unrecognized alphanumeric symbol and the plurality of stored candidate lists so that the unrecognized alphanumeric symbol can be recognized, wherein the reduced candidate list contains candidates which are common to the plurality of candidate lists.

24. The system of claim 21, wherein the means for generating and storing the plurality of candidate lists representative of a complete alphabet comprises:

means for generating at least one structurally determined list of candidate alphanumeric symbols based on structural features of the unrecognized alphanumeric symbol; and

means for generating at least one topologically determined list of candidate alphanumeric symbols based on topological features of the unrecognized alphanumeric symbol.

25. The system of claim 24, wherein the means for generating the reduced list of candidate alphanumeric symbols from the plurality of candidate lists comprises means for generating the reduced list of candidate alphanumeric symbols via the intersection of the structurally and topologically determined lists of candidate alphanumeric symbols.