Method and system for recognizing machine generated character glyphs in graphic images

• US 9,171,207 B1
• Filed: 03/11/2014
• Issued: 10/27/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Peter L. Olcott
• Original Assignee: Peter L. Olcott
• Inventors: Olcott, Peter L
• Primary Examiner(s): VILLECCO, JOHN M
• Application Number:
  US14/204,321
• Time in Patent Office: 595 Days
• Field of Search: 382/194, 382/176, 382/206
• US Class Current: 1/1
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/148 Segmentation of character regions
• CPC Class Codes: G06V 30/184 by analysing segments intersecting the pattern
• CPC Class Codes: G06V 30/19187 Graphical models, e.g. Bayesian networks or Markov models
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method and system for recognizing machine generated character glyphs in a graphic image that uses a deterministic finite automaton (DFA) to separately recognize the individual pixelcolumns of character glyphs and then combines these separate pixelcolumns together to form correctly recognized whole glyphs. This method and system can enable data to be automatically exchanged between applications where no alternative method of data interchange exists. The DFA minimizes its space requirements by storing the current input dimension of its state transition table as a sorted list of possible values that could be matched at the current state. This sorted list can then be binary searched for the current input pixel RGB value.

Claims

1. A method for creating a system for recognizing machine generated character glyphs in a graphic image, comprising:

creating a deterministic finite automaton (DFA) for recognizing individual pixel columns of machine generated character glyphs;

providing a means for combining the recognized individual pixel columns together such that whole character glyphs are correctly recognized wherein the DFA is created by the following steps;

collecting a set of pixel columns for each character glyph within a FontInstance;

sorting the collected pixel columns by their pixel RGB values;

merging identical prefixes of these character glyph pixel columns together;

generating and storing the DFA from the merged prefixes.

2. The method of claim 1, wherein the DFA is augmented such that the pixel columns recognized by the DFA are combined together to form correctly matched whole character glyphs by eliminating the recognized pixel columns that do not correctly form whole character glyphs.

3. The method of claim 2, wherein the DFA is augmented such that the whole character glyphs are validated against each other to eliminate erroneously matched glyphs.

4. The method of claim 1, wherein the DFA is used for the purpose of exchanging data between application programs.

5. A Method for recognizing machine generated character glyphs in a graphic image comprising:

creating a deterministic finite automaton (DFA) for recognizing individual pixel columns of machine generated character glyphs;

using the DFA to recognize the individual pixel columns of machine generated character glyphs;

combining the recognized individual pixel columns of machine generated character glyphs together into correctly matched whole glyphs.

6. The method of claim 5 wherein the DFA is created by collecting a set of pixel columns for each character glyph within a FontInstance and sorting the collected pixel columns by their pixel RGB values.

7. The method of claim 6 wherein identical prefixes of these character glyph pixel columns are merged together.

8. The method of claim 7 wherein the DFA is generated from these merged prefixes and stored.

9. The method of claim 6 wherein every overlapping glyph pixel column is collected.

10. The method of claim 8 wherein the DFA is represented as a Sparse Matrix.

11. The method of claim 9 wherein OverlapCodes are determined for overlapping glyphs.

12. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by eliminating the recognized pixel columns that do not form whole glyphs.

13. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by eliminating the recognized pixel columns that lack required corresponding OverlapCodes.

14. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by correcting erroneous glyph order.

15. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by eliminating erroneous horizontal substring glyphs.

16. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by eliminating erroneous invisible glyph boundary glyphs.

17. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by eliminating glyphs that do not pass pixelsbetween validation.

18. The method of claim 5 wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by eliminating erroneous vertical substring glyphs.

19. A Method for recognizing machine generated character glyphs in a graphic image comprising:

creating a deterministic finite automaton (DFA) for recognizing individual pixel columns of machine generated character glyphs;

using the DFA to recognize the individual pixel columns of machine generated character glyphs;

combining the recognized individual pixel columns of machine generated character glyphs together into correctly matched whole glyphs wherein the DFA is created by the following steps;

collecting a set of pixel columns for each character glyph within a FontInstance;

sorting the collected pixel columns by their pixel RGB values;

merging identical prefixes of these character glyph pixel columns together;

generating and storing the DFA from the merged prefixes.

20. A Method for recognizing machine generated character glyphs in a graphic image comprising:

creating a deterministic finite automaton (DFA) for recognizing individual pixel columns of machine generated character glyphs;

using the DFA to recognize the individual pixel columns of machine generated character glyphs;

combining the recognized individual pixel columns of machine generated character glyphs together into correctly matched whole glyphs;

wherein the recognized individual pixel columns of machine generated character glyphs are combined together into correctly matched whole glyphs by the following steps;

eliminating recognized pixel columns that do not form whole glyphs;

eliminating erroneous horizontal substring glyphs;

eliminating glyphs that do not pass pixelsbetween validation.