System and method for automated symbolic recognition including spatial reasoning

• US 7,227,995 B1
• Filed: 04/18/2003
• Issued: 06/05/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,483
• Time in Patent Office: 1,509 Days
• Field of Search: 382/186, 382/185, 382/198
• US Class Current: 382/186
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• CPC Class Codes: G06V 30/2268 using stroke segmentation
• CPC Class Codes: G06V 30/347 Sampling; Contour coding; Stroke extraction

Abstract

An automated symbolic recognition system and method includes a hierarchical hypothesis-and-verification technique during various stages of the handwriting recognition process, whereby a series of initial assessments are made based on the information availed upon them, and later during processing, they are validated or rejected depending on the degree in which preset milestones were satisfied and are followed by a sequence of alternative hypotheses in the event of failure of the latest hypothesis until they are satisfied.

Claims

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

(a) receiving digital information indicative of unrecognized alphanumeric symbols;

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

(c) generating a plurality of candidate lists of alphanumeric symbols;

(d) generating a reduced list of candidate alphanumeric symbols and confidence levels from the plurality of candidate lists based on one or more symbolic representations of each arcpoly of each unrecognized alphanumeric symbol, wherein the reduced candidate list contains candidates which are common to the plurality of candidate lists;

(e) determining a best candidate in the list of candidate alphanumeric symbols for each alphanumeric symbol;

(f) validating the best candidate; and

(g) if the best candidate cannot be validated, determining alternative sets of reduced candidate lists and repeating (b)-(f) until the alphanumeric symbol is recognized,

(h) wherein determining alternative sets of reduced candidate lists involves computing multi-phase symbolic reshaping including a phase comprising;

criteria-based region growing and splitting of arcpolys so that they better conform to a plurality of alphanumeric symbol models included in a stored candidate list; and

computing a multi-stage post-processing of arcpolys so that they better conform to a plurality of alphanumeric symbol models; and

(i) wherein the criteria based growing and splitting comprises;

computing row-based median and column-based median to derive a threshold used for grouping polyline points into cluster(s) of points;

detecting significant bends on adjoining lines or detecting significant line size(s) for arcpolys which comprise a (I) line and an arc, or (II) line and a line, and splitting them at a splitting point whereby the two arcpolys best conform to stored alphanumeric symbol models; and

detecting arcpolys which are significantly more extended than a half circle and splitting them at a splitting point whereby the two arcpolys best conform to stored alphanumeric symbol models.

2. The method of claim 1, wherein the determining of a best candidate is based on its inferred confidence level and the number of matched arcpolys.

3. The method of claim 1, wherein the determining alternative sets of reduced candidate lists includes selective reshaping of the arcpolys.

4. 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.

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

6. The method of claim 1, wherein the receiving of digital information is via one of:

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

7. The method of claim 1, wherein one or more arcpolys form a polyline and each unrecognized alphanumeric symbol is formed from one or more polylines.

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

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

10. The method of claim 1, additionally comprising storing a candidate list representative of a complete set of characters, wherein the reduced candidate lists are subsets of the stored candidate list, and wherein members of the stored candidate list are linked to symbolic representations derived from arcpolys via an inverse mapping.

11. The method of claim 1, wherein a list of primary features is computed for each arcpoly which describe the entire shape and orientation of the arcpoly.

12. The method of claim 1, wherein a set of variances comprising a set of arcpoly variance types, a set of counterpart dissimilarity values and a topological dissimilarity value per pair of arcpolys'"'"' relative location are devised.

13. The method of claim 1, wherein relational features are computed to derive the confidence levels between the unrecognized alphanumeric symbol and each candidate alphanumeric symbol.

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

15. The method of claim 1, additionally comprising computing a list of symbolic representations for each of the arcpolys of the unrecognized alphanumeric symbol.

16. The method of claim 1, wherein generating the plurality of candidate lists of alphanumeric symbols comprises:

generating at least one structurally determined list of candidate alphanumeric symbols; and

generating at least one topologically determined list of candidate alphanumeric symbols.

17. The method of claim 16, wherein generating the reduced list of candidate alphanumeric symbols from the plurality of candidate lists comprises:

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

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

generating the reduced list of candidate alphanumeric symbols via the intersection of the structurally and topologically determined lists of candidate alphanumeric symbols.

18. The method of claim 1, wherein automatically validating the best candidate comprises automatically validating the best candidate using multiple criteria including topological relations and criteria-based thresholding.

19. The method of claim 1, wherein validating the best candidate comprises automatically validating the best candidate.

20. 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 generating a plurality of candidate lists of alphanumeric symbols;

(d) means for generating a reduced list of candidate alphanumeric symbols and confidence levels from the plurality of candidate lists based on one or more symbolic representations of each arcpoly of the unrecognized alphanumeric symbol, wherein the reduced candidate list contains candidates which are common to the plurality of candidate lists;

(e) means for determining a best candidate in the list of candidate alphanumeric symbols;

(f) means for validating the best candidate; and

(g) if the best candidate cannot be validated, means for determining alternative sets of reduced candidate lists and repeatedly processing (b)-(f) until the alphanumeric symbol is recognized,

(h) wherein means for determining alternative sets of reduced candidate lists involves computing multi-phase symbolic reshaping including a phase comprising;

criteria-based region growing and splitting of arcpolys so that they better conform to a plurality of alphanumeric symbol models included in a stored candidate list; and

computing a multi-stage post-processing of arcpolys so that they better conform to a plurality of alphanumeric symbol models; and

(i) wherein means for determining the criteria based growing and splitting comprises;

computing row-based median and column-based median to derive a threshold used for grouping polyline points into cluster(s) of points;

detecting significant bends on adjoining lines or detecting significant line size(s) for arcpolys which comprise a (I) line and an arc, or (II) line and a line, and splitting them at a splitting point whereby the two arcpolys best conform to stored alphanumeric symbol models; and

detecting arcpolys which are significantly more extended than a half circle and splitting them at a splitting point whereby the two arcpolys best conform to stored alphanumeric symbol models.

21. The system of claim 20, wherein the means for determining of a best candidate is based on its inferred confidence level and the number of matched arcpolys.

22. The system of claim 20, wherein the means for determining alternative sets of reduced candidate lists includes selective reshaping of the arcpolys.

23. The system of claim 20, wherein the arcpolys are primarily computed by monitoring rotation changes and identifying the arcpoly when the rotation in one direction stops.

24. The system of claim 20, wherein the unrecognized alphanumeric symbol is either cursive or printed.

25. The system of claim 20, wherein the means for receiving digital information is one of:

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

26. The system of claim 20, wherein one or more arcpolys form a polyline and each unrecognized alphanumeric symbol is formed from one or more polylines.

27. The system of claim 20, wherein there are a plurality of unrecognized alphanumeric symbols that are sequentially received and recognized.

28. The system of claim 20, additionally comprising means for storing a candidate list representative of a complete set of characters, wherein the reduced candidate lists are subsets of the stored candidate list, and wherein members of the stored candidate list are linked to symbolic representations derived from arcpolys via an inverse mapping.

29. The system of claim 20, wherein the means for automatically validating the best candidate comprises means for automatically validating the best candidate using multiple criteria including topological relations and criteria-based thresholding.

30. The system of claim 20, wherein the means for generating the plurality of candidate lists of alphanumeric symbols comprises:

means for generating at least one structurally determined list of candidate alphanumeric symbols; and

means for generating at least one topologically determined list of candidate alphanumeric symbols.

31. The system of claim 30, wherein the means for generating the reduced list of candidate alphanumeric symbols from the plurality of candidate lists comprises:

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

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

means for generating the reduced list of candidate alphanumeric symbols via the intersection of the structurally and topologically determined lists of candidate alphanumeric symbols.

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

(a) a device configured to receive digital information indicative of an unrecognized alphanumeric symbol;

(b) a software module configured to compute one or more arcpolys of the unrecognized alphanumeric symbol;

(c) a software module configured to generate a plurality of candidate lists of alphanumeric symbols;

(d) a software module configured to generate a reduced list of candidate alphanumeric symbols and confidence levels from the plurality of candidate lists based on one or more symbolic representations of each arcpoly of the unrecognized alphanumeric symbol, wherein the reduced candidate list contains candidates which are common to the plurality of candidate lists;

(e) a software module configured to determine a best candidate in the list of candidate alphanumeric symbols;

(f) a software module configured to validate the best candidate; and

(g) if the best candidate cannot be validated, a software module configured to determine alternative sets of reduced candidate lists and repeatedly processing (b)-(f) until the alphanumeric symbol is recognized,

(h) wherein a software module configured to determine alternative sets of reduced candidate lists involves computing multi-phase symbolic reshaping including a phase comprising;

criteria-based region growing and splitting of arcpolys so that they better conform to a plurality of alphanumeric symbol models included in a stored candidate list; and

computing a multi-stage post-processing of arcpolys so that they better conform to a plurality of alphanumeric symbol models; and

(i) wherein a software module configured to determine the criteria based growing and splitting comprises;

computing row-based median and column-based median to derive a threshold used for grouping polyline points into cluster(s) of points;

detecting significant bends on adjoining lines or detecting significant line size(s) for arcpolys which comprise a (I) line and an arc, or (II) line and a line, and splitting them at a splitting point whereby the two arcpolys best conform to stored alphanumeric symbol models; and

detecting arcpolys which are significantly more extended than a half circle and splitting them at a splitting point whereby the two arcpolys best conform to stored alphanumeric symbol models.

33. The system of claim 32, wherein the software module configured to determine a best candidate is based on its inferred confidence level and the number of matched arcpolys.

34. The system of claim 32, wherein the software module configured to determine alternative sets of reduced candidate lists includes selective reshaping of the arcpolys.

35. The system of claim 32, wherein the arcpolys are primarily computed by monitoring rotation changes and identifying the arcpoly when the rotation in one direction stops.

36. The system of claim 32, wherein the unrecognized alphanumeric symbol is either cursive or printed.

37. The system of claim 32, wherein the device configured to receive digital information is one of:

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

38. The system of claim 32, wherein one or more arcpolys form a polyline and each unrecognized alphanumeric symbols is formed from one or more polylines.

39. The system of claim 32, wherein there are a plurality of unrecognized alphanumeric symbols that are sequentially received and recognized.

40. The system of claim 32, additionally comprising a software module configured to store a candidate list representative of a complete set of characters, wherein the reduced candidate lists are subsets of the stored candidate list, and wherein members of the stored candidate list are linked to symbolic representations derived from arcpolys via an inverse mapping.

41. The system of claim 40, wherein the symbolic representations comprise one or more pairs of logical and subclass symbols.

42. The system of claim 32, wherein the software module configured to automatically validate the best candidate comprises a software module configured to automatically validate the best candidate using multiple criteria including topological relations and criteria-based thresholding.

43. The system of claim 32, wherein the software module configured to generate the plurality of candidate lists of alphanumeric symbols comprises:

a software module configured to generate at least one structurally determined list of candidate alphanumeric symbols; and

a software module configured to generate at least one topologically determined list of candidate alphanumeric symbols.

44. The system of claim 43, wherein the software module configured to generate the reduced list of candidate alphanumeric symbols from the plurality of candidate lists comprises:

a software module configured to generate the at least one structurally determined list of candidate alphanumeric symbols based on structural features of the unrecognized alphanumeric symbol;

a software module configured to generate the at least one topologically determined list of candidate alphanumeric symbols based on topological features of the unrecognized alphanumeric symbol; and

a software module configured to generate the reduced list of candidate alphanumeric symbols via the intersection of the structurally and topologically determined lists of candidate alphanumeric symbols.

45. The system of claim 32, wherein the software module configured to validate the best candidate automatically validates the best candidate.