METHODS AND SYSTEMS THAT USE HIERARCHICALLY ORGANIZED DATA STRUCTURE CONTAINING STANDARD FEATURE SYMBOLS IN ORDER TO CONVERT DOCUMENT IMAGES TO ELECTRONIC DOCUMENTS

• US 20160267323A1
• Filed: 06/18/2013
• Published: 09/15/2016
• Est. Priority Date: 06/18/2013
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Development LLC
• Inventors: Chulinin, Yury Georgievich
• Granted Patent: US 9,911,034 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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, each entry of which corresponds to one or more natural-language entities selected from among one or more morphemes, words, or phrases encoded as sequences of standard feature symbols; 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 of a block of text of an Arabic-like language,

identify images of lines of text within the received image of the block of text;

identify subimages within the image of the line of text corresponding to one or more of words and morphemes,

for each identified subimage,

identify sets of characters that represent candidate character-sequence representations of the subimage; and

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

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

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

2. The system of claim 1 wherein the Arabic-like language is one of:

Arabic;

Persian;

Pashto;

Urdu;

Devanagari;

Hindi;

Korean;

a Turkish language; and

a language instantiated in cursive writing.

3. The system of claim 1 wherein the image of the block of 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 sets of characters 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 sets of characters 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 hierarchical data structure, according to the sequence of feature symbols with associated parameters, to identify candidate nodes of the hierarchical data structure.

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

setting a penalty value to an initial value; and

recursively traversing the hierarchical data structure from the root node downward, accumulating a current penalty associated with each node in each traversal path through the hierarchical 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 that transforms a document image into an electronic document within a system having one or more processors, one or more electronic memories, and the hierarchically organized data structure, the method comprising:

receiving an image of a block of text of an Arabic-like language;

identifying images of lines of text within the received image of the block of text;

identifying subimages within the image of the line of text corresponding to one or more of words and morphemes;

for each identified subimage,

identifying sets of characters that represent candidate character-sequence representations of the subimage, and

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

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

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

12. The method of claim 11 wherein the Arabic-like language is one of:

Arabic;

Persian;

Pashto;

Urdu;

Devanagari;

Hindi;

Korean;

a Turkish language; and

a language instantiated in cursive writing.

13. The method of claim 11 wherein the image of the block of text is a digital encoding of a scanned or otherwise imaged a 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 sets of characters 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 sets of characters 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 hierarchical data structure, according to the sequence of feature symbols with associated parameters, to identify candidate nodes of the hierarchical data structure.

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

setting a penalty value to an initial value; and

recursively traversing the hierarchical data structure from the root node downward, accumulating a current penalty associated with each node in each traversal path through the hierarchical 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.