Image-domain script and language identification

• US 8,233,726 B1
• Filed: 11/27/2007
• Issued: 07/31/2012
• Est. Priority Date: 11/27/2007
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Popat, Ashok, Brevdo, Eugene
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US11/945,978
• Time in Patent Office: 1,708 Days
• Field of Search: 382/177, 382182-189, 382224-228, 382/321, 382/229, 382/230
• US Class Current: 382/230
• CPC Class Codes: G06V 30/2445 Alphabet recognition, e.g. Latin, Kanji or Katakana

Abstract

Disclosed herein is a method, computer system and computer program product for identifying a writing system associated with a document image containing one or more words written in the writing system. Initially, a document image fragment is identified based on the document image, wherein the document image fragment contains one or more pixels from one or more of the words in the document image. A set of sequential features associated with the document image fragment is generated, wherein each sequential feature describes one dimensional graphic information derived from the one or more pixels in the document image fragment. A classification score for the document image fragment is generated responsive at least in part to the set of sequential features, the classification score indicating a likelihood that the document image fragment is written in the writing system. The writing system associated with the document image is identified based at least in part on the classification score for the document image fragment.

Claims

1. A computer-implemented method of identifying a writing system associated with a document image containing one or more words written in the writing system, the method comprising:

identifying a document image fragment based on the document image, wherein the document image fragment contains one or more pixels from one or more of the words in the document image;

generating a set of sequential features associated with the document image fragment, wherein each sequential feature describes one dimensional graphic information derived from the one or more pixels in the document image fragment;

identifying a plurality of n-grams based on the set of sequential features, wherein each n-gram comprises an ordered subset of sequential features;

generating a classification score for the document image fragment based at least in part on a frequency of occurrence of the n-grams in sets of sequential features associated with known writing systems, the classification score indicating a likelihood that the document image fragment is written in the writing system; and

identifying the writing system associated with the document image based at least in part on the classification score for the document image fragment.

2. The method of claim 1, wherein there are a plurality of writing systems, a set of classification scores indicating likelihoods that the document image fragment is associated with ones of the plurality of writing systems is generated, and the writing system associated with the document image is identified based at least in part on the set of classification scores.

3. The method of claim 1, further comprising:

selecting a writing system dictionary based on the writing system associated with the document image; and

performing optical character recognition on the document image based on the writing system dictionary.

4. The method of claim 1, further comprising:

identifying a plurality of document image fragments based on a plurality of documents;

generating a plurality of sets of sequential features associated with the plurality of document image fragments;

generating a plurality of sets of classification scores for the plurality of document image fragments responsive at least in part to the sets of sequential features;

generating a set of combined classification scores wherein each combined classification score is based on a set of classification scores indicating the likelihood that the plurality of document image fragments are written in a writing system of the set of writing systems; and

identifying a first writing system associated with the plurality of document images based on the set of combined classification scores.

5. The method of claim 4, further comprising:

associating a reliability score with each document image fragment, wherein the reliability score indicates a quality of the document image fragment; and

generating the set of combined classification scores based on weighting the plurality of sets of classification scores for each document image fragment by the reliability score associated with the document image fragment.

6. The method of claim 4, further comprising:

generating a plurality of pair-wise penalty values based on the set of writing systems, wherein each pair-wise value indicates a penalty for misclassifying a second writing system of the set of writing systems as a third writing system of the set of writing systems; and

weighting the plurality of combined classification scores for each document image fragment based on the plurality of pair-wise penalty values.

7. The method of claim 1, wherein generating a set of sequential features further comprises:

determining a plurality of sets of ordered connected components based on the document image fragment, wherein each connected component comprises a set of pixels corresponding to a glyph in the document image fragment;

determining, for each connected component, a set of similarity values between the connected component and a set of equivalent connected components, wherein each equivalent component represents at least a first glyph and is associated with a categorical value;

associating a categorical value with each connected component based on the set of similarity values; and

generating the set of sequential features, wherein each sequential feature comprises the categorical value associated with an ordered connected component.

8. The method of claim 7, wherein determining, for each connected component, a set of similarity values between the connected component and a set of equivalent connected components comprises:

modifying the connected component by removing one or more pixels above a specified intensity value from the set of pixels using a morphological thinning algorithm.

9. The method of claim 1, further comprising:

identifying a set of ordered pixel columns based on the document image fragment wherein each ordered pixel column is comprised of a set of cells and each cell comprises a set of pixels;

determining a set of values for each ordered pixel column in the set, wherein each value is based on one or more intensity values of one or more pixels of the set of pixels in one or more cells of the set of cells; and

generating the set of sequential features comprising the set of values.

10. The method of claim 1, further comprising:

generating a plurality of conditional probability values associated with the plurality of n-grams, wherein each conditional probability value is based at least in part on a frequency of occurrence of an n-gram in the plurality of sets of sequential features associated with known writing systems; and

generating the classification score based on the plurality of conditional probability values.

26. The method of claim 1, wherein at least some of the n-grams in the plurality include overlapping ones of the sequential features.

27. The method of claim 1, wherein identification of the plurality of n-grams includes generating the plurality of n-grams according to a sliding window scheme, wherein each generated n-gram in the plurality differs from at least one other n-gram in the plurality by one feature.

28. The method of claim 10, wherein a conditional probability value for a first n-gram is determined based at least in part on observations for one or more other n-grams in the sets of sequential features associated with the known writing systems, wherein the one or more other n-grams precede the first n-gram in the plurality of n-grams.

11. A non-transitory computer-readable storage medium encoded with executable computer program code for identifying a writing system associated with a document image containing one or more words written in the writing system, the program code comprising:

program code for identifying a document image fragment based on the document image, wherein the document image fragment contains one or more pixels from one or more of the words in the document image;

program code for generating a set of sequential features associated with the document image fragment, wherein each sequential feature describes one dimensional graphic information derived from the one or more pixels in the document image fragment;

program code for identifying a plurality of n-grams based on the set of sequential features, wherein each n-gram comprises an ordered subset of sequential features;

program code for generating a classification score for the document image fragment based at least in part on a frequency of occurrence of the n-grams in sets of sequential features associated with known writing systems, the classification score indicating a likelihood that the document image fragment is written in the writing system; and

program code for identifying the writing system associated with the document image based at least in part on the classification score for the document image fragment.

12. The medium of claim 11, wherein there are a plurality of writing systems, a set of classification scores indicating likelihoods that the document image fragment is associated with ones of the plurality of writing systems is generated, and the writing system associated with the document image is identified based at least in part on the set of classification scores.

13. The medium of claim 11, further comprising:

program code for selecting a writing system dictionary based on the writing system associated with the document image; and

program code for performing optical character recognition on the document image based on the writing system dictionary.

14. The medium of claim 11, further comprising:

program code for identifying a plurality of document image fragments based on a plurality of documents;

program code for generating a plurality of sets of sequential features associated with the plurality of document image fragments;

program code for generating a plurality of sets of classification scores for the plurality of document image fragments responsive at least in part to the sets of sequential features;

program code for generating a set of combined classification scores wherein each combined classification score is based on a set of classification scores indicating the likelihood that the plurality of document image fragments are written in a writing system of the set of writing systems; and

program code for identifying a first writing system associated with the plurality of document images based on the set of combined classification scores.

15. The medium of claim 14, further comprising:

program code for associating a reliability score with each document image fragment, wherein the reliability score indicates a quality of the document image fragment; and

program code for generating the set of combined classification scores based on weighting the plurality of sets of classification scores for each document image fragment by the reliability score associated with the document image fragment.

16. The medium of claim 14, further comprising:

program code for generating a plurality of pair-wise penalty values based on the set of writing systems, wherein each pair-wise value indicates a penalty for misclassifying a second writing system of the set of writing systems as a third writing system of the set of writing systems; and

program code for weighting the plurality of combined classification scores for each document image fragment based on the plurality of pair-wise penalty values.

17. The medium of claim 11, wherein program code for generating a set of sequential features further comprises:

program code for determining a plurality of sets of ordered connected components based on the document image fragment, wherein each connected component comprises a set of pixels corresponding to a glyph in the document image fragment;

program code for determining, for each connected component, a set of similarity values between the connected component and a set of equivalent connected components, wherein each equivalent component represents at least a first glyph and is associated with a categorical value;

program code for associating a categorical value with each connected component based on the set of similarity values; and

program code for generating the set of sequential features, wherein each sequential feature comprises the categorical value associated with an ordered connected component.

18. The medium of claim 17, wherein program code for determining, for each connected component, a set of similarity values between the connected component and a set of equivalent connected components comprises:

program code for modifying the connected component by removing one or more pixels above a specified intensity value from the set of pixels using a morphological thinning algorithm.

19. The medium of claim 11, further comprising:

program code for identifying a set of ordered pixel columns based on the document image fragment wherein each ordered pixel column is comprised of a set of cells and each cell comprises a set of pixels;

program code for determining a set of values for each ordered pixel column in the set, wherein each value is based on one or more intensity values of one or more pixels of the set of pixels in one or more cells of the set of cells; and

program code for generating the set of sequential features comprising the set of values.

20. The medium of claim 11, further comprising:

program code for generating a plurality of conditional probability values associated with the plurality of n-grams, wherein each conditional probability value is based at least in part on a frequency of occurrence of an n-gram in the plurality of sets of sequential features associated with known writing systems; and

program code for generating the classification score based on the plurality of conditional probability values.

21. A computer system for identifying a writing system associated with a document image containing one or more words written in the writing system, the system comprising:

a non-transitory computer-readable storage medium encoded with executable computer program code comprising;

a segmentation module adapted to identify a document image fragment based on the document image, wherein the document image fragment contains one or more pixels from one or more of the words in the document image;

a feature extraction module adapted to generate a set of sequential features associated with the document image fragment, wherein each sequential feature describes one dimensional graphic information derived from the one or more pixels in the document image fragment;

a feature classification module adapted to;

identify a plurality of n-grams based on the set of sequential features, wherein each n-gram comprises an ordered subset of sequential features; and

generate a classification score for the document image based at least in part on a frequency of occurrence of the n-grams in sets of sequential features associated with known writing systems, the classification score indicating a likelihood that the document image fragment is written in the writing system; and

an optical character recognition module adapted to identify the writing system associated with the document image based at least in part on the classification score for the document image fragment; and

a processor for executing the computer program code.

22. The system of claim 21, wherein the optical character recognition module is further adapted to:

select a writing system dictionary based on the writing system associated with the document image; and

perform optical character recognition on the document image based on the writing system dictionary.

23. The system of claim 21, wherein the feature extraction module is further adapted to:

determine, for each of a plurality of connected components of the document image fragment, a set of similarity values between the connected component and a set of equivalent connected components, wherein each equivalent component represents at least a first glyph and is associated with a categorical value;

associate a categorical value with each connected component based on the set of similarity values; and

generate the set of sequential features, wherein each sequential feature comprises the categorical value associated with an ordered connected component.

24. The system of claim 21, wherein the feature extraction module is further adapted to:

identify a set of ordered pixel columns based on the document image fragment wherein each ordered pixel column is comprised of a set of cells and each cell comprises a set of pixels;

determine a set of values for each ordered pixel column in the set, wherein each value is based on one or more intensity values of one or more pixels of the set of pixels in one or more cells of the set of cells; and

generate the set of sequential features comprising the set of values.

25. The system of claim 21, wherein the feature classification module is further adapted to:

generate a plurality of conditional probability values associated with the plurality of n-grams, wherein each conditional probability value is based at least in part on a frequency of occurrence of an n-gram in the plurality of sets of sequential features associated with known writing systems; and

generate the classification score based on the plurality of conditional probability values.