Method and system for data extraction from images of semi-structured documents

1. A method of extracting data from one or more fields in an image of a document, the method comprising:

obtaining a text representation of the image of the document;

constructing a graph for storing one or more features values of one or more text fragments in the text representation of the image of the document and one or more links between the one or more text fragments;

computing one or more features of the one or more text fragments and the one or more links using a cascade classification;

generating one or more hypotheses about the one or more text fragments belonging to the one or more fields in the image of the document;

generating one or more combinations of the one or more hypotheses;

selecting a combination of the one or more hypotheses; and

extracting data from the one or more fields in the image of the document based on the selected combination of the one or more hypotheses.

2. The method of claim 1 , wherein the text representation of the image of the document is a result of an optical character recognition (OCR).

3. The method of claim 1 , wherein the graph comprises nodes, edges and features values of the nodes and the edges and wherein constructing the graph further comprises:

matching the node of the graph to words, word combinations, or word fragments of the text representation of the image of the document; and

connecting the nodes in a linear order by the edges.

4. The method of claim 1 , wherein computing the one or more features of the one or more text fragments and the one or more links comprises receiving the features values of the one or more text fragments and the one or more links.

5. The method of claim 1 , wherein the computing the one or more features of the one or more text fragments and the one or more links comprises:

selecting a procedure for the computing of the one or more features of the one or more text fragments and the one or more links;

running the selected procedure to compute at least one of the features for the one or more text fragments or the one or more links; and

modifying the graph based on the computed at least one feature of the features for the one or more text fragments or the one or more links.

6. The method of claim 5 , wherein the modifying of the graph comprises one or more of:

merging nodes, splitting nodes, removing edges, adding edges, changing features values of the nodes, and changing the features values of the edges.

7. The method of claim 1 , wherein the generating the one or more hypotheses about the one or more text fragments belonging to the one or more fields in the image of the document is at least in part based on the computed one or more features of the one or more text fragments and the one or more links.

8. The method of claim 1 , wherein the selecting of the combination of the one or more hypotheses is based on a computed quality of the one or more combinations of the one or more hypotheses.

9. The method of claim 8 , wherein the selecting of the combination of the one or more hypotheses based on the computed quality of the one or more combinations of the one or more hypotheses comprises:

for each combination of the one or more hypotheses:

computing cumulative metric of confidences for the combination of the one or more hypotheses; and

computing cumulative metric of fines for the combination of the one or more hypotheses; and

selecting the combination of the one or more hypotheses with a highest computed quality,

wherein the computed quality is at least in part based on the cumulative metric of confidences and the cumulative metric of fines.

10. The method of claim 1 , wherein the selecting of the combination of the one or more hypotheses is based on comparing a feature vector of one combination of the one or more hypotheses with a feature vector of another combination of the one or more hypotheses.

11. The method of claim 5 , wherein the running of the selected procedure further comprises using one or more electronic dictionaries.

12. The method of claim 5 , wherein the running of the selected procedure further comprises using a reduced alphabet.

13. The method of claim 1 , wherein the image of the document is a sales receipt or a business card.

14. The method of claim 1 , wherein computing the one or more features of the one or more text fragments and the one or more links further comprises:

combining easily confused characters from a first alphabet into groups based on OCR error statistic;

selecting a meta-representative character for each of the groups;

constructing a reduced alphabet using the meta-representative characters of the groups;

converting the text representation of the image of the document using the reduced alphabet; and

converting one or more electronic dictionaries using the reduced alphabet.

15. The method of claim 14 , wherein the computing the one or more features of the one or more text fragments and the one or more links further comprises searching for a word from the converted text representation of the image of the document in the one or more converted electronic dictionaries.

16. A method of extracting data from one or more fields in an image of a document using a reduced alphabet, the method comprising:

combining, by a processor, easily confused characters from a first alphabet into groups based on OCR error statistic;

selecting, by the processor, a meta-representative character for each of the groups;

constructing, by the processor, a reduced alphabet using the meta-representative characters of the groups.

17. The method of claim 16 further comprising, converting, by the processor, one or more electronic dictionaries using the reduced alphabet.

18. The method of claim 17 further comprising converting, by the processor, text representation of the image of the document using the reduced alphabet.

19. The method of claim 18 further comprising, computing one or more features of one or more text fragments and one or more links between the text fragments using the converted text representation of the image of the document and the one or more converted electronic dictionaries.