Methods and systems that use hierarchically organized data structure containing standard feature symbols in order to convert document images to electronic documents

• US 9,911,034 B2
• Filed: 06/18/2013
• Issued: 03/06/2018
• Est. Priority Date: 06/18/2013
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Development LLC
• Inventors: Chulinin, Yury Georgievich
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US14/781,656
• Publication Number:
  US 20160267323A1
• Time in Patent Office: 1,722 Days
• Field of Search: 382182, 382185-187, 382224, 382226, 382229, 704 8, 704 9
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/244 using graphical properties, e.g. alphabet type or font
• CPC Class Codes: G06V 30/246 using linguistic properties, e.g. specific for English or German language
• CPC Class Codes: G06V 30/268 Lexical context
• 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

The current application is directed to methods and systems that convert document images, which contain Arabic text and text in other languages in which symbols are joined together to produce continuous words and portions of words, into corresponding electronic documents. In one implementation, a document-image-processing method and system to which the current application is directed employs numerous techniques and features that render efficiently computable an otherwise intractable or impractical document-image-to-electronic-document conversion. These techniques and features include transformation of text-image morphemes and words into feature symbols with associated parameters, efficiently identifying similar morphemes and words in an electronic store of standard-feature-symbol-encoded morphemes and words, and identifying candidate inter-character division points and corresponding traversal paths using the similar morphemes and words identified in the word store.

Claims

1. A system that transforms a document image into an electronic document, the system comprising:

one or more processors;

one or more electronic memories; and

a hierarchically organized data structure, stored in one or more of the one or more electronic memories, the hierarchically organized data structure comprising a plurality of entries corresponding to one or more natural-language entities selected from among one or more morphemes, words, or phrases encoded as sequences of standard feature symbols, wherein the plurality of entries are associated with a plurality of scores; and

computer instructions, digitally encoded and stored in one or more of the one or more electronic memories and executed on the one or more processors, that;

receive an image comprising text of a language;

identify a subimage within the image, the subimage corresponding to one or more of words and morphemes;

identify a set of character-sequences that represent candidate character-sequence representations of the subimage, wherein a character-sequence of the set is identified by traversing a path of the hierarchically organized data structure and accumulating a value for the character-sequence based on the scores on the path, wherein the value for the character-sequence in the set satisfies a predetermined threshold;

use the candidate character-sequence representations of the subimage as hypotheses regarding lexical identities of the subimage;

construct a portion of an electronic document corresponding to the received image of text using the hypotheses regarding the lexical identities of the subimage; and

store the constructed portion of the electronic document in one or more of the one or more electronic memories.

2. The system of claim 1 wherein the language comprises at least one of Arabic, Persian, Pashto, Urdu, Devanagari, Hindi, Korean, or a Turkish language.

3. The system of claim 1 wherein the image comprising text is a digital encoding of a scanned or otherwise imaged block of text that is stored in one or more of the one or more electronic memories.

4. The system of claim 1 wherein the computer instructions, executed on the one or more processors, identify the set of character-sequences that represent candidate character-sequence representations of the subimage by:

transforming the subimage into a sequence of feature symbols with associated parameters, each feature symbol associated with no, one, two, or more than two parameters and each feature symbol with associated parameters corresponding to a text-line feature;

storing the sequence of feature symbols with associated parameters in one or more of the one or more electronic memories;

using the sequence of feature symbols with associated parameters to identify candidate words, candidate morphemes, or candidate words and morphemes corresponding to the subimage that are encoded as sequences of standard feature symbols within the hierarchically organized data structure;

using the identified candidate words to determine and store, in one or more of the one or more electronic memories, probable inter-character division points and traversal paths for the subimage;

using the probable inter-character division points and traversal paths for the subimage to generate candidate traversal paths for the subimage; and

generating the set of character-sequences that represent candidate character-sequence representations of the subimage from the candidate traversal paths.

5. The system of claim 4 wherein the hierarchically organized data structure comprises:

a root node; and

direct and descendent nodes of the root node;

wherein

each descendent node is linked to a parent node by a link, the link representing a standard feature symbol, and

each node contains, or is associated with, at least one sequence of standard feature symbols.

6. The system of claim 5 wherein the computer instructions, executed on the one or more processors, use the sequence of feature symbols with associated parameters to identify candidate words, candidate morphemes, or candidate words and morphemes corresponding to the subimage that are encoded as sequences of standard feature symbols within the hierarchically organized data structure by:

traversing the hierarchically organized data structure, according to the sequence of feature symbols with associated parameters, to identify candidate nodes of the hierarchically organized data structure.

7. The system of claim 6 wherein the computer instructions, executed on the one or more processors, traverse the hierarchically organized data structure, according to the sequence of feature symbols with associated parameters, to identify candidate nodes of the hierarchically organized data structure by:

setting the value to a penalty value comprising an initial value; and

recursively traversing the hierarchically organized data structure from the root node downward, accumulating a current penalty associated with each node in each traversal path through the hierarchically organized data structure, to identify candidate nodes as those nodes for which the accumulated penalty value is less than a threshold penalty value.

8. The system of claim 7 wherein the current penalties include:

a substitution mismatch penalty;

an inversion mismatch penalty for reversing the order of two adjacent feature symbols with associated parameters or standard feature symbols;

a missing-feature-symbol mismatch penalty; and

a missing-standard-feature-symbol mismatch penalty.

9. The system of claim 6 wherein the computer instructions, executed on the one or more processors, use the identified candidate nodes to determine and store, in one or more of the one or more electronic memories, probable inter-character division points and traversal paths for the subimage by:

initializing a set of traversal-path pointers and a set of inter-character division points; and

for each identified candidate node,

for each sequence of standard feature symbols within the candidate node,

for each letter-separator standard feature symbol in the sequence of standard feature symbols,

determining a relative position within the subimage corresponding to the letter-separator standard feature symbol,

adding the determined relative position to the set of inter-character division points, and

adding a previous relative position and the determined relative position to the set of traversal-path pointers.

10. The system of claim 9 wherein the computer instructions, executed on the one or more processors, use the probable inter-character division points and traversal paths for the subimage to generate candidate traversal paths for the subimage by:

constructing possible traversal paths that traverse the subimage from a first end to a second end as a set of traversal steps, each traversal step corresponding to a traversal-path pointer from the traversal-path pointers.

11. A method comprising:

receiving, by one or more processors, an image comprising text of a language;

identifying a subimage within the image, the subimage corresponding to one or more of words and morphemes;

identifying a set of character-sequences that represent candidate character-sequence representations of the subimage, wherein a character-sequence of the set is identified by traversing a path of the hierarchically organized data structure and accumulating a value for the character-sequence based on the scores on the path, wherein the value for the character-sequence in the set satisfies a predetermined threshold;

using the candidate character-sequence representations of the subimage as hypotheses regarding the lexical identities of the subimage;

constructing a portion of an electronic document corresponding to the received image comprising text using the hypotheses regarding the lexical identities of the subimages; and

storing the constructed portion of the electronic document in one or more of the one or more electronic memories.

12. The method of claim 11 wherein the language is one of Arabic, Persian, Pashto, Urdu, Devanagari, Hindi, Korean, or a Turkish language.

13. The method of claim 11 wherein the image comprising text is a digital encoding of a scanned or otherwise imaged block of text that is stored in one or more of the one or more electronic memories.

14. The method of claim 11 wherein identifying the set of character-sequences that represent candidate character-sequence representations of the subimage further comprises:

transforming the subimage into a sequence of feature symbols with associated parameters, each feature symbol with associated parameters associated with no, one, two, or more than two parameters and each feature symbol with associated parameters corresponding to one, two, or more strokes, loops, diacritical marks, or other text-line features;

storing the sequence of feature symbols with associated parameters in one or more of the one or more electronic memories;

using the sequence of feature symbols with associated parameters to identify candidate words, candidate morphemes, or candidate words and morphemes corresponding to the subimage that are encoded as sequences of standard feature symbols within the hierarchically organized data structure;

using the identified candidate words to determine and store, in one or more of the one or more electronic memories, probable inter-character division points and traversal paths for the subimage;

using the probable inter-character division points and traversal paths for the subimage to generate candidate traversal paths for the subimage; and

generating the set of character-sequences that represent candidate character-sequence representations of the subimage from the candidate traversal paths.

15. The method of claim 14 wherein the hierarchically organized data structure comprises:

a root node; and

direct and descendent nodes of the root node;

wherein

each descendent node is linked to a parent node by a link, the link representing a standard feature symbol, and

each node contains, or is associated with, at least one sequence of standard feature symbols.

16. The method of claim 15 wherein using the sequence of feature symbols with associated parameters to identify candidate words, candidate morphemes, or candidate words and morphemes corresponding to the subimage that are encoded as sequences of standard feature symbols within the hierarchically organized data structure further comprises:

traversing the hierarchically organized data structure, according to the sequence of feature symbols with associated parameters, to identify candidate nodes of the hierarchically organized data structure.

17. The method of claim 16 wherein traversing the hierarchically organized data structure, according to the sequence of feature symbols with associated parameters, to identify candidate nodes of the hierarchically organized data structure further comprises:

setting the value to a penalty value comprising an initial value; and

recursively traversing the hierarchically organized data structure from the root node downward, accumulating a current penalty associated with each node in each traversal path through the hierarchically organized data structure, to identify candidate nodes as those nodes for which the accumulated penalty value is less than a threshold penalty value.

18. The method of claim 17 wherein the current penalties include:

a substitution mismatch penalty;

an inversion mismatch penalty for reversing the order of two adjacent feature symbols with associated parameters or standard feature symbols;

a missing-feature-symbol mismatch penalty; and

a missing-standard-feature-symbol mismatch penalty.

19. The method of claim 16 wherein using the identified candidate nodes to determine and store, in one or more of the one or more electronic memories, probable inter-character division points and traversal paths for the subimage further comprises:

initializing a set of traversal-path pointers and a set of inter-character division points; and

for each identified candidate node,

for each sequence of standard feature symbols within the candidate node,

for each letter-separator standard feature symbol in the sequence of standard feature symbols,

determining a relative position within the subimage corresponding to the letter-separator standard feature symbol,

adding the determined relative position to the set of inter-character division points, and

adding a previous relative position and the determined relative position to the set of traversal-path pointers.

20. The method of claim 19 wherein using the probable inter-character division points and traversal paths for the subimage to generate candidate traversal paths for the subimage further comprises:

constructing possible traversal paths that traverse the subimage from a first end to a second end as a set of traversal steps, each traversal step corresponding to a traversal-path pointer from the traversal-path pointers.