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

• US 7,046,848 B1
• Filed: 08/21/2002
• Issued: 05/16/2006
• Est. Priority Date: 08/22/2001
• Status: Expired due to Term

• Current Assignee: Peter L. Olcott
• Original Assignee: Peter L. Olcott
• Inventors: Olcott, Peter L.
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): Alavi, Amir
• Application Number:
  US10/225,053
• Time in Patent Office: 1,364 Days
• Field of Search: 382/165, 382/176, 382/178, 382/181, 382/182, 382/184, 382/187, 382/190, 382/195, 382/198, 382/228, 382/284, 382/305, 358/1.11, 358/2.1, 345/574, 706/20, 706/48, 707/6, 707/104.1, 715/513, 715/515, 715/531, 717/104
• US Class Current: 382/176
• 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/274 Syntactic or semantic context, e.g. balancing
• CPC Class Codes: G06V 30/40 Document-oriented image-based pattern recognition

Abstract

A deterministic finite automaton uses binary search (and optionally hashing) method(s) of sparse matrix representation to recognize the graphical representations of characters or icons from a bitmap representation of the computer screen. This recognition can be applied to translate data from an unknown form of original specification (file format) into a known form of representation, such as HTML. Alternatively this recognition can be applied to another process that can “see” what is on the screen, and perform programmed actions, based on what it “sees”.

Claims

1. A method for constructing a deterministic finite automaton (DFA) for recognizing machine generated character glyphs in a graphic image, comprising:

collecting character glyphs of a font instance, including all combinations of overlapping glyphs;

merging the identical prefixes of these character glyphs together;

generating the DFA from the merged prefixes; and

storing the DFA in a sparse matrix representation.

2. The method of claim 1, wherein the DFA has been adapted to recognize character glyphs of differing colors and icons in a single pass over the graphic image data.

3. The method of claim 1, wherein the sparse matrix representation is implemented as at least one of:

binary search, hashing, and linear search.

4. The method of claim 1, wherein the DFA uses at least one of:

set intersection and glyph alignment in its recognition process.

5. The method of claim 1, wherein the DFA is used to translate a source file in source file format to a destination file in a destination file format using a graphic image of the source file.

6. The method of claim 1, wherein the DFA is used by a second program to control a first program on a first computer.

7. The method of claim 1, wherein the DFA has been adapted to recognize both character glyphs and icons using a single set of DFA states comprised of the merged identical prefixes of the character glyphs and the icons.

8. The method of claim 1, wherein the DFA has been adapted to ignore the background pixels of the graphic image during the DFA recognition process.

9. A method for translating a source file in a source file format to a destination file in a destination file format using a graphic image of the source file, comprising:

constructing a deterministic finite automaton (DFA) for recognizing machine generated character glyphs in a graphic image, comprising;

collecting character glyphs of a font instance, including all combinations of overlapping glyphs;

merging the identical prefixes of these character glyphs together;

generating the DFA from the merged prefixes; and

storing the DFA in a sparse matrix representation;

using the deterministic finite automaton (DFA) to translate the source file in the source file format into the destination file in the destination file format.

10. The method of claim 9, wherein the source file contains both text and graphic images.

11. The method of claim 9, wherein the translation step includes identifying rectangular regions of text.

12. A method for translating a source file in a source file format to a destination file in a destination file format using a graphic image of the source file, comprising:

constructing a deterministic finite automaton (DFA) for recognizing machine generated character glyphs in a graphic image, comprising;

collecting character glyphs of a font instance, including all combinations of overlapping glyphs;

merging the identical prefixes of these character glyphs together;

generating the DFA from the merged prefixes; and

storing the DFA in a sparse matrix representation;

using the deterministic finite automaton (DFA) to translate the source file in the source file format into the destination file in the destination file format wherein the destination file format is a page layout language.

13. The method of claim 12, wherein the page layout language is HTML or XML.

14. A method for second program to control a first program on a first computer comprising:

constructing a deterministic finite automaton (DFA) for recognizing machine generated character glyphs in a graphic image, comprising;

collecting character glyphs of a font instance, including all combinations of overlapping glyphs;

merging the identical prefixes of these character glyphs together;

generating the DFA from the merged prefixes; and

storing the DFA in a sparse matrix representation;

adapting the DFA to recognize icons and multiple font instances;

using the DFA by a second program to control a first program on a first computer.

15. A method for second program to control a first program on a first computer comprising:

constructing a deterministic finite automaton (DFA) for recognizing machine generated character glyphs in a graphic image, comprising;

collecting character glyphs of a font instance, including all combinations of overlapping glyphs;

merging the identical prefixes of these character glyphs together;

generating the DFA from the merged prefixes; and

storing the DFA in a sparse matrix representation;

adapting the DFA to recognize icons and multiple font instances;

using the DFA by a second program to control a first program on a first computer, wherein the second program is invoiced by a set of keystroke combinations.

16. A method for second program to control a first program on a first computer comprising:

constructing a deterministic finite automaton (DFA) for recognizing machine generated character glyphs and or icons in a graphic image, comprising;

collecting character glyphs and or icons;

merging the identical prefixes of these character glyphs and or icons together;

generating the DFA from the merged prefixes; and

storing the DFA in a sparse matrix representation;

using the DFA by a second program to control a first program on a first computer.

17. The method of claim 16, wherein the second program manipulates the first program by recognizing a graphical user interface (GUI) control element generated by the first program and operating the control element by simulating the effect of a hardware input device.

18. The method of claim 17, wherein the graphical user interface (GUI) control element is one of a button, a menu, a menu element, a dialog box, a control tab, and an application icon.

19. The method of claim 17, wherein the hardware input device is one of a keyboard, a mouse, a touch screen, a stylus pad, and a light pen.

20. The method of claim 16, wherein the control step includes capturing user actions upon one of more graphical user interface (GUI) control elements generated by the first program, and capturing corresponding portion is of the screen image of a sequence of actions that are to be repeated by the second program.

21. The method of claim 16, wherein the first computer is different from the second computer.

22. The method of claim 16, wherein the first computer is the same as the second computer.

23. The method of claim 16, wherein the control step includes inputting into the second program a sequence of user specified instructions from a computer language containing the instructions.

24. The method of claim 16, wherein the second program is invoked by a set of keystroke combinations.

25. The method of claim 24, wherein the second program uses the DFA to determine the context in which the second program was invoked, and takes different actions depending upon this context.

26. The method of claim 16, wherein the DFA contains a set of full color pixels of the glyph or icon to be recognized.

27. The method of claim 26, wherein the full color pixels include both foreground pixels and background pixels.