System and method for automated symbolic recognition including multi-phase symbolic reshaping

• US 7,218,782 B1
• Filed: 04/18/2003
• Issued: 05/15/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,480
• Time in Patent Office: 1,488 Days
• Field of Search: 382/198, 382/185, 382/186
• US Class Current: 382/186
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18162 related to a structural representation of the pattern
• CPC Class Codes: G06V 30/32 Digital ink

Abstract

An automated symbolic recognition system and method includes a three phase symbolic reshaping scheme during the symbol recognition process that includes: (a) deriving dissimilarity level from alphanumeric ID'"'"'s net topological variation and the integration of each of its arcpoly structural variation(s) signifying a reasonably accurate confidence level for the goodness of recognition, thus establishing a mechanism that derives dissimilarity level (or cost value) between image and database features including shape, size and topological relationship, (b) determining the reshaping or transformation of an arcpoly to another arcpoly by introducing variations to the original arcpoly to alter its shape and orientation and deriving at each step, the new cost value as a function of variation(s) present and imposed, and (c) determining the equivalent representation of an arcpoly by a succession of smaller and adjoining arcpoly(s) in order, or vice versa.

Claims

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

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

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

(c) computing at least one symbolic representation of the unrecognized alphanumeric symbol based on the arcpolys;

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

(e) generating a reduced list of candidate alphanumeric symbols and alphanumeric confidence levels from the plurality of candidate lists based on the symbolic representation of the unrecognized alphanumeric symbol and a stored candidate list, wherein the reduced candidate list contains candidates which are common to a plurality of candidate lists;

(f) determining a best candidate in the reduced list of candidate alphanumeric symbols and automatically validating the best candidate;

(g) if the best candidate cannot be validated, performing a multi-phase symbolic reshaping on the arcpolys so as to obtain a different symbolic representation of the unrecognized alphanumeric symbol so that the unrecognized alphanumeric symbol can be recognized;

(h) wherein the multi-phase symbolic reshaping includes 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 multi-phase symbolic reshaping comprises a phase of computing an alphanumeric dissimilarity value between each unrecognized alphanumeric symbol and stored candidate alphanumeric symbol, the alphanumeric dissimilarity value being indicative of the confidence level.

3. The method of claim 2, wherein computing an alphanumeric dissimilarity value comprises computing a symbolic representation for each arcpoly of an unrecognized alphanumeric symbol.

4. The method of claim 2, wherein the alphanumeric dissimilarity value is computed based at least on the sum of two or more of the following computed variances:

topological variance for all pairs of arcpoly(s) of the unrecognized alphanumeric symbol;

structural variance for all arcpoly(s) of the unrecognized alphanumeric symbol;

variance(s) pertaining to mismatched logical- and subclass-symbol pair(s) in reference to stored data representing missing symbol(s); and

variance(s) pertaining to mismatched logical- and subclass-symbol pair(s) in reference to image data representing extra image structure(s).

5. The method of claim 1, wherein a phase of the multi-phase symbolic reshaping for the unrecognized alphanumeric symbol comprises an ordered sequence of structural, topological and/or combined reshaping of each arcpoly, each time generating a new reduced alphanumeric candidate symbol list and dissimilarity value, until a candidate alphanumeric symbol is validated.

6. The method of claim 5, wherein reshaping of an arcpoly comprises applying at least one of:

multi-level unit rotations, changes in extreme points size, and depth size on the arcpoly, each time transforming the arcpoly into a new arcpoly having a new orientation and/or new shape.

7. The method of claim 6, wherein for each transformed arcpoly of an unrecognized alphanumeric symbol steps (b)–

(f) are repeated.

8. The method of claim 7, wherein arcpoly reshaping types comprise:

arc-to-arc rotation, line-to-line rotation, arc depth size variance, arc extreme points size variance, extra or missing arc extension(s) on each (or both) extreme point(s), line extreme points size variance, topological variance, and combined variances.

9. The method of claim 1, additionally comprising computing text-line characteristics for each polyline and arcpoly.

10. The method of claim 9, wherein the text line characteristics are selected from:

base line, core line, ascender line, and descender line levels, for one or more lines of text within the received digital information.

11. The method of claim 1 wherein the multi-stage post-processing comprises:

removing polyline jitters to achieve smoothing; and

merging adjoining arcpolys with equal direction of motion and minor direction change between a last line direction of a former arcpoly and a first line direction of a latter arcpoly such that the combined arcpoly has one direction of motion.

12. The method of claim 1, wherein the symbolic representation and the different symbolic representation together form an augmented symbolic representation.

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

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

15. The method of claim 14, 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.

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

17. A system for automatically recognizing alphanumeric symbols, 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 computing at least one symbolic representation of the unrecognized alphanumeric symbol based on the arcpolys;

(d) means for generating a plurality of candidate lists of alphanumeric symbols;

(e) means for generating a reduced list of candidate alphanumeric symbols and alphanumeric confidence levels from the plurality of candidate lists based on the symbolic representation of the unrecognized alphanumeric symbol and a stored candidate list, wherein the reduced candidate list contains candidates which are common to a plurality of candidate lists;

(f) means for determining a best candidate in the reduced list of candidate alphanumeric symbols and automatically validating the best candidate;

(g) means for performing a multi-phase symbolic reshaping on the arcpolys, if the best candidate cannot be validated, so as to obtain a different symbolic representation of the unrecognized alphanumeric symbol so that the unrecognized alphanumeric symbol can be recognized;

(h) wherein the means for multi-phase symbolic reshaping includes 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 means for 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.

18. The system of claim 17, wherein the multi-phase symbolic reshaping comprises means for computing an alphanumeric dissimilarity value between each unrecognized alphanumeric symbol and stored candidate alphanumeric symbol, the alphanumeric dissimilarity value being indicative of the confidence level.

19. The system of claim 18, wherein computing an alphanumeric dissimilarity value comprises means for computing a symbolic representation for each arcpoly of an unrecognized alphanumeric symbol.

20. The system of claim 18, wherein the alphanumeric dissimilarity value is computed based at least on the sum of two or more of the following computed variances:

topological variance for all pairs of arcpoly(s) of the unrecognized alphanumeric symbol;

structural variance for all arcpoly(s) of the unrecognized alphanumeric symbol;

variance(s) pertaining to mismatched logical- and subclass-symbol pair(s) in reference to stored data representing missing symbol(s); and

variance(s) pertaining to mismatched logical- and subclass-symbol pair(s) in reference to image data representing extra image structure(s).

21. The system of claim 17, wherein a phase of the means for multi-phase symbolic reshaping for the unrecognized alphanumeric symbol comprises an ordered sequence of structural, topological and/or combined reshaping of each arcpoly, each time generating a new reduced alphanumeric candidate symbol list and dissimilarity value, until a candidate alphanumeric symbol is validated.

22. The system of claim 17, wherein reshaping of an arcpoly comprises means for applying at least one of:

multi-level unit rotations, changes in extreme points size, and depth size on the arcpoly, each time transforming the arcpoly into a new arcpoly having a new orientation and/or new shape.

23. The system of claim 17, wherein for each transformed arcpoly of an unrecognized alphanumeric symbol means (b)–

(f) are repeatedly executed.

24. The system of claim 17, 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.

25. The system of claim 17, 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.

26. The system of claim 25, 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.

27. The system of claim 17, wherein the means for validating the best candidates automatically validates the best candidate.