Language-independent and segmentation-free optical character recognition system and method

• US 5,933,525 A
• Filed: 04/10/1996
• Issued: 08/03/1999
• Est. Priority Date: 04/10/1996
• Status: Expired due to Term

• Current Assignee: Raytheon BBN Technologies Corp. (Rtx Corporation)
• Original Assignee: BBN Corporation (Verizon Communications Inc.)
• Inventors: Makhoul, John I., Schwartz, Richard M.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/630,162
• Time in Patent Office: 1,210 Days
• Field of Search: 382/192, 382/187, 382/228, 382/312, 382/323, 382/224, 382/185-186, 382/139, 382/230
• US Class Current: 382/186
• CPC Class Codes: G06V 30/2276 with probabilistic networks, e.g. hidden Markov models

Abstract

A language-independent and segment free OCR system and method comprises a unique feature extraction approach which represents two dimensional data relating to OCR as one independent variable (specifically the position within a line of text in the direction of the line) so that the same CSR technology based on HMMs can be adapted in a straightforward manner to recognize optical characters. After a line finding stage, followed by a simple feature-extraction stage, the system can utilize a commercially available CSR system, with little or no modification, to perform the recognition of text by and training of the system. The whole system, including the feature extraction, training, and recognition components, are designed to be independent of the script or language of the text being recognized. The language-dependent parts of the system are confined to the lexicon and training data. Furthermore, the method of recognition does not require pre-segmentation of the data at the character and/or word levels, neither for training nor for recognition. In addition, a language model can be used to enhance system performance as an integral part of the recognition process and not as a post-process, as is commonly done with spell checking, for example.

Claims

1. An optical character recognition system for recognizing each character of a text, comprising:

means for (a) determining the position of each line of characters of the text, (b) scanning each line of text by scanning said text in successive frames of a predetermined height and width independent of the script and language of said text, and (c) generating data representing all of the optically scanned characters of the text as a function of a single independent variable in one direction, said variable being a function of a feature vector representing a plurality of elements, each element being a function of the percentile height below which a prespecified percentage of black pixels lies;

means for providing a probabilistic paradigm so as to determine each of said characters of said text from said data.

2. The optical character recognition system of claim 1, wherein:

said means for generating data representing optically scanned text as a function of a single independent variable comprises means for scanning said text line by line in the same direction as said line.

3. The optical character recognition system of claim 2 wherein:

said means for scanning said text line by line in the same direction as said line includes means for scanning said text in successive frames of a predetermined height and width independent of the script and language of said text, but a function of the font size of the characters.

4. The optical character recognition system of claim 3, wherein:

said means for scanning said text in successive frames of a predetermined height and width independent of the script and language of said text includes means for scanning said text so that said frames overlap.

5. The optical character recognition system of claim 4, wherein:

said means for scanning said text in successive frames of a predetermined height and width independent of the size, shape and width of the font of said text includes means for dividing said frame into a plurality of cells.

6. The optical character recognition system of claim 5, further including:

means for dividing said frame into a plurality of cells so that said cells are aligned along an axis perpendicular to the direction of scanning said text.

7. The optical character recognition system of claim 6, wherein:

said means for dividing said frame into a plurality of cells divides said cells so that said cells are overlapping.

8. The optical character recognition system of claim 3, further including:

means for dividing each of said frames into an array of pixels, and wherein

said means for generating data representing optically scanned text as a function of a single independent variable includes means for generating the data as a function of the intensity in each of said pixels in each of said frames.

9. The optical character recognition system of claim 8, further including means for dividing said frame into a plurality of cells so that said cells are aligned along an axis perpendicular to the direction of scanning said text;

and means for determining the percentage of said pixels below a predetermined threshold within each of said cells relative to the total number of pixels below a predetermined threshold within said frame.

10. The optical character recognition system of claim 9, wherein said means for determining the percentage of said pixels below a predetermined threshold within each of said cells relative to the total number of cells below a predetermined threshold within said frame includes means for determining the percentile of said pixels below a predetermined threshold within each of said cells relative to the total number of pixels between said cell and one referenced end of said frame.

11. The optical character recognition system of claim 5, wherein

said means for generating data representing optically scanned text as a function of a single independent variable also includes means for generating the data as a function of the derivative across the dimensions of a feature vector.

12. The optical character recognition system of claim 5, wherein

said means for generating data representing optically scanned text as a function of a single independent variable also includes means for generating the data as a function of the derivative of each feature across adjacent frames.

13. The optical character recognition system of claim 6, wherein

said means for generating data representing optically scanned text as a function of a single independent variable also includes means for generating the data as a function of the local slope and correlation across a window comprising a plurality of said cells.

14. The optical character recognition system of claim 1, wherein

said means for providing a probabilistic paradigm so as to determine said text from said data includes means for providing a 1D hidden Markov model for each of the characters to be recognized.

15. The optical character recognition system of claim 14, wherein

each of said hidden Markov models is defined by a plurality of states.

16. The optical character recognition system of claim 15, wherein

the number of states for each of said hidden Markov models is the same.

17. The optical character recognition system of claim 15, wherein

the parameters for each of said states of each hidden Markov model is context dependent.

18. The optical character recognition system of claim 14, further including means for defining a context-dependent character model for each possible character of said text.

19. The optical character recognition system of claim 1, wherein

said means for providing a probabilistic paradigm so as to determine said text from said data includes a language model.

20. The optical character recognition system of claim 19, wherein

said language model is an n-gram model.

21. The optical character recognition system of claim 20, wherein

said language model is a bigram model.

22. The optical character recognition system of claim 20, wherein

said language model is a trigram model.

23. An optical character recognition system according to claim 1, wherein each of said frames is divided into a plurality of cells, and said means for generating data includes means for determining the vertical derivative of intensity in the vertical direction across said cells.

24. An optical character recognition system according to claim 23, wherein each of said frames is divided into a plurality of cells, and said means for generating data includes means for determining the vertical derivative of intensity in the vertical direction across said cells, wherein said horizontal and vertical derivatives of intensity provide a measure of boundaries between the light and dark portions of the text.

25. An optical character recognition system according to claim 1, wherein said frames are overlapping, and said means for generating data includes means for determining the horizontal derivative of intensity in the horizontal direction across overlapping frames.

26. An optical character recognition system according to claim 1, wherein each of said frames is divided into a plurality of cells, and said means for generating data includes means for determining the local slope and correlation of any line within a window of a plurality of such cells so as to determine the angle of said line.

27. An optical character recognition system according to claim 1, wherein each of said characters is an Arabic character.

28. An optical character recognition system according to claim 1, wherein each of said characters is a Chinese character.

29. A method of recognizing text regardless of the script or language of the text and without segmenting the text by character or word, said method comprising:

scanning successive frames of a predetermined height and width of each line of the text in the direction of each line so as to generate data relating to all of the characters of the text independent of the script or language of the text, wherein the data is a function of a single independent variable in one direction, said variable being a function of a feature vector representing a plurality of elements, each element being a function of the percentile height below which a prespecified percentage of black pixels lies; and

determining from the data each character of text based upon a predetermined probabilistic paradigm.

30. A method according to claim 29, wherein each of said characters is an Arabic character.

31. A method according to claim 29, wherein each of said characters is a Chinese character.

32. An optical character recognition system for recognizing each character of a text, comprising:

means for (a) determining the position of each line of characters of the text and (b) scanning each line of text;

data generating means for generating data representing all of the optically scanned characters of the text as a function of a single independent variable in one direction, said data generating means comprising scanning means for scanning said text (a) line by line in the same direction as said line and (b) in successive frames of a predetermined height and width independent of the script and language of said text, but a function of the font size of the characters;

means for dividing each of said frames into an array of pixels;

means for dividing said frame into a plurality of cells so that said cells are aligned along an axis perpendicular to the direction of scanning said text;

means for determining the percentage of said pixels below a predetermined threshold within each of said cells relative to the total number of pixels below a predetermined threshold within said frame; and

means for providing a probabilistic paradigm so as to determine each of said characters of said text from said data;

wherein said data generating means includes means for generating the data as a function of the intensity in each of said pixels in each of said frames.

33. An optical character recognition system for recognizing each character of a text, comprising:

means for (a) determining the position of each line of characters of the text and (b) scanning each line of text;

data generating means for generating data representing all of the optically scanned characters of the text as a function of a single independent variable in one direction, said data generating means comprising scanning means for scanning said text (a) line by line in the same direction as said line, (b) in successive frames of a predetermined height and width independent of the script and language of said text, but a function of the font size of the characters, (c) so that the frames overlap and (d) each of said frames is divided into a plurality of cells; and

means for providing a probabilistic paradigm so as to determine each of said characters of said text from said data, wherein

said means for generating data representing optically scanned text as a function of a single independent variable also includes means for generating the data as a function of the derivative across the dimensions of a feature vector.

34. An optical character recognition system according to claim 33, further including said scanning means including means for dividing each said frame into a plurality of cells.

35. An optical character recognition system for recognizing each character of a text, comprising:

means for (a) determining the position of each line of characters of the text and (b) scanning each line of text;

data generating means for generating data representing all of the optically scanned characters of the text as a function of a single independent variable in one direction, said data generating means comprising scanning means for scanning said text (a) line by line in the same direction as said line, (b) in successive frames of a predetermined height and width independent of the script and language of said text, but a function of the font size of the characters, and (c) so that the frames overlap; and

means for providing a probabilistic paradigm so as to determine each of said characters of said text from said data, wherein

said data generating means includes means for generating the data as a function of the derivative of each feature across adjacent frames.

36. An optical character recognition system for recognizing each character of a text, comprising:

means for (a) determining the position of each line of characters of the text and (b) scanning each line of text;

data generating means for generating data representing all of the optically scanned characters of the text as a function of a single independent variable in one direction, said data generating means comprising scanning means for scanning said text (a) line by line in the same direction as said line, (b) in successive frames of a predetermined height and width independent of the script and language of said text, but a function of the font size of the characters, (c) so that the frames overlap, and (d) so that each frame is divided into a plurality of cells so that said cells are aligned along an axis perpendicular to the direction of scanning said text; and

means for providing a probabilistic paradigm so as to determine each of said characters of said text from said data;

wherein said data generating means includes means for generating the data as a function of the local slope and correlation across a window comprising a plurality of said cells.