Optical character recognition method

Abstract

The optical character recognition method applies a first OCR engine to provide an identification of characters of at least a first type of characters and zones of at least a second type of characters in the character string image. A second OCR engine is applied on the zones of the at least second type of characters to provide an identification of characters of a second type of characters. The characters identified by the first OCR engine and by the second OCR engine are in a further step combined to obtain the identification of the characters of the character string image.

Claims

1. A method for identifying characters in a character string image, the method comprising: (i) applying a first Optical Character Recognition engine to provide an identification of characters of at least a first type of characters and zones of at least a second type of characters in the character string image, (ii) applying on the zones of the at least second type of characters a second Optical Character Recognition engine to provide an identification of characters of a second type of characters, and (iii) combining the characters identified by the first Optical Character Recognition engine and by the second Optical Character Recognition engine to obtain the identification of the characters of the character string image, wherein the first Optical Character Recognition engine comprises a segmentation of the character string image into segmentation parts, the segmentation of the character string image into segmentation parts comprising the steps of determining a first starting point coordinate of a pixel contrasting to a background, generating a list of potential character widths dependent on a maximum character width and on characteristics of the portion of the character string image corresponding to the maximum character width, and determining a second portion of the character string image corresponding to the first starting point coordinate and the first width on the list of potential character widths, and wherein the first Optical Character Recognition engine comprises, for each segmentation part, the steps of: (a) applying a first character classification to provide a first plurality of hypotheses on an at least one character represented by the segmentation part and a first plurality of probabilities associated with the first plurality of hypotheses, (b) verifying if the first plurality of hypotheses satisfies at least one condition, (c) if at least one condition is satisfied, applying a second character classification to provide a second plurality of hypotheses on the at least one character represented by the segmentation part and a second plurality of probabilities associated with the second plurality of hypotheses.

2. A method according to claim 1, wherein the first Optical Character Recognition engine uses a database of characters including characters of the first type of characters.

3. A method according to claim 2, wherein the first character classification uses a database of characters including characters of the first type of characters.

4. A method according to claim 3, wherein the first character classification is able to detect characters of at least another type of characters than the first type of characters.

5. A method according to claim 4, wherein the first type of characters is an Asian type of characters.

6. A method according to claim 4, wherein the second Optical Character Recognition engine uses a database of characters including characters of the second type of characters.

7. A method according to claim 6, wherein the second character classification uses a database of characters including characters of the second type of characters.

8. A method according to claim 7, wherein the second type of characters is a Latin type of characters.

9. A method according to claim 7, wherein the second type of characters is the Asian type of characters, the Arabic type of characters, the Hebrew type of characters, the Cyrillic type of characters, the Greek type of character or the hieroglyph type of characters.

10. A method according to claim 4, wherein the at least one condition is one of the following conditions all probabilities of the first plurality of hypotheses are below a given threshold; a hypothesis amongst the first plurality of hypotheses relates to a character of the first type of characters known to look like a character of the at least second type of characters; and a hypothesis with a probability higher than a given threshold amongst the first plurality of hypotheses relates to another type of characters than the first type of characters.

11. A method according to claim 3, wherein the first type of characters is the Latin type of characters, the Arabic type of characters, the Hebrew type of characters, the Cyrillic type of characters, the Greek type of character or the hieroglyph type of characters.

12. A method according to claim 1, wherein at least one of the first character classification and second character classification is a single character classification.

13. A method according to claim 1, wherein the zones of the at least second type of characters are groups of segmentation parts, and wherein at least one segmentation part of the groups of segmentation parts satisfies at least one of the following conditions: all probabilities of the first plurality of hypotheses provided by the first character classification for the at least one segmentation part are below a given threshold; a hypothesis amongst the first plurality of hypotheses for the at least one segmentation part relates to a character of the first type of characters known to look like a character of the at least second type of characters; a hypothesis amongst the first plurality of hypotheses for the at least one segmentation part relates to another type of characters than the first type of characters; and a character of the second type of characters was identified on the at least one segmentation part by the first Optical Character Recognition engine.

14. A method according to claim 1, wherein a zone of the at least second type of characters is a group of segmentation parts that includes at least two characters.

15. A method according to claim 1, wherein the first plurality of probabilities corresponds to a first scale of probability, the second plurality of probabilities corresponds to a second scale of probability, and the method comprises a step of transforming at least one of the first plurality of probabilities and second plurality of probabilities to scale the first or the second scales of probability in such a way that the first plurality of probabilities and the second plurality of probabilities can be compared, to obtain transformed first or second pluralities of probabilities.

16. A method according to claim 1, wherein the first Optical Character Recognition engine further comprises a step of making a contextual decision for the identification of characters of the at least first type of characters based on the first plurality of hypotheses from the first character classification and the first plurality of probabilities associated with the first plurality of hypotheses, and the second plurality of hypotheses from the second character classification and the second plurality of probabilities associated with the second plurality of hypotheses for all segmentation parts.

17. A method according to claim 16, wherein the step of making a contextual decision uses at least one of the decision support tools among decision graph, linguistic model, typographical model, and decision model based on n-gram model.

18. A computer program product embodied on a non-transitory computer usable storage medium for causing a computing device to identify characters in a character string image, comprising: (i) first computer code for applying a first Optical Character Recognition engine to provide an identification of characters of at least a first type of characters and zones of at least a second type of characters in the character string image, (ii) second computer code for applying on the zones of at least a second type of characters a second Optical Character Recognition engine to provide an identification of characters of a second type of characters, and (iii) third computer code for combining the characters identified by the first Optical Character Recognition engine and by the second Optical Character Recognition engine to obtain the identification of the characters of the character string image, wherein the first Optical Character Recognition engine comprises a segmentation of the character string image into segmentation parts, the segmentation of the character string image into segmentation parts comprising the steps of: determining a first starting point coordinate of a pixel contrasting to a background, generating a list of potential character widths dependent on a maximum character width and on characteristics of the portion of the character string image corresponding to the maximum character width, and determining a second portion of the character string image corresponding to the first starting point coordinate and the first width on the list of potential character widths, and wherein the first Optical Character Recognition engine comprises, for each segmentation part, the steps of: (a) applying a first character classification to provide a first plurality of hypotheses on an at least one character represented by the segmentation part and a first plurality of probabilities associated with the first plurality of hypotheses, (b) verifying if the first plurality of hypotheses satisfies at least one condition, and (c) if at least one condition is satisfied, applying a second character classification to provide a second plurality of hypotheses on the at least one character represented by the segmentation part and a second plurality of probabilities associated with the second plurality of hypotheses.

19. A method for identifying characters in a character string image, the method comprising the steps of: (A) segmenting of the character string image into segmentation parts, the segmentation of the character string image into segmentation parts comprising the steps of: determining a first starting point coordinate of a pixel contrasting to a background, generating a list of potential character widths dependent on a maximum character width and on characteristics of the portion of the character string image corresponding to the maximum character width, and determining a second portion of the character string image corresponding to the first starting point coordinate and the first width on the list of potential character widths, (B) for each segmentation part, the substeps of: (a) applying a first character classification to provide a first plurality of hypotheses on an at least one character represented by the segmentation part and a first plurality of probabilities associated with the first plurality of hypotheses, (b) verifying if the first plurality of hypotheses satisfies at least one condition, (c) if at least one condition is satisfied, applying a second character classification to provide a second plurality of hypotheses on the at least one character represented by the segmentation part and a second plurality of probabilities associated with the second plurality of hypotheses, and (C) making a contextual decision for the identification of the characters of the at least first type of characters based on the first plurality of hypotheses from the first character classification and the first plurality of probabilities associated with the first plurality of hypotheses, and the second plurality of hypotheses from the second character classification and the second plurality of probabilities associated with the second plurality of hypotheses for all segmentation parts.

20. A computer program product embodied on a non-transitory computer usable storage medium for causing a computing device to identify characters in a character string image, comprising: (A) first computer code for segmenting of the character string image into segmentation parts, the segmentation of the character string image into segmentation parts comprising the steps of: determining a first starting point coordinate of a pixel contrasting to a background, generating a list of potential character widths dependent on a maximum character width and on characteristics of the portion of the character string image corresponding to the maximum character width, and determining a second portion of the character string image corresponding to the first starting point coordinate and the first width on the list of potential character widths, (B) second computer code for applying, for each segmentation part, the substeps of: (a) a first character classification to provide a first plurality of hypotheses on an at least one character represented by the segmentation part and a first plurality of probabilities associated with the first plurality of hypotheses, (b) a verification if the first plurality of hypotheses satisfies at least one condition, (c) if at least one condition is satisfied, a second character classification to provide a second plurality of hypotheses on the at least one character represented by the segmentation part and a second plurality of probabilities associated with the second plurality of hypotheses, and (C) third computer code for making a contextual decision for the identification of the characters of the at least first type of characters based on the first plurality of hypotheses from the first character classification and the first plurality of probabilities associated with the first plurality of hypotheses, and the second plurality of hypotheses from the second character classification and the second plurality of probabilities associated with the second plurality of hypotheses for all segmentation parts.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) For a better understanding of the present invention, reference will now be made, by way of example, to the accompanying drawings in which:

(2) FIG. 1 shows a flowchart of an OCR method according to the state of the art.

(3) FIG. 2 shows a flowchart of an OCR engine according to the state of the art.

(4) FIG. 3 shows a flowchart of a combination step combining segmentation and single character classification according to an embodiment of the invention.

(5) FIG. 4 illustrates the resemblance between some Asian and Latin characters, the resemblance being used in an embodiment of the present invention.

(6) FIG. 5 illustrates a combined segmentation and single-character classification according to an embodiment of the present invention.

(7) FIG. 6 shows a flowchart of an OCR method according to an embodiment of the invention.

DESCRIPTION OF THE INVENTION

(8) The present invention will be described with respect to particular embodiments and with reference to certain drawings but the invention is not limited thereto. The drawings described are only schematic and are non-limiting. In the drawings, the size of some of the elements may be exaggerated and not drawn on scale for illustrative purposes.

(9) Furthermore, the terms first, second, third and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a sequential or chronological order. The terms are interchangeable under appropriate circumstances and the embodiments of the invention can operate in other sequences than described or illustrated herein.

(10) Furthermore, the various embodiments, although referred to as “preferred” are to be construed as exemplary manners in which the invention may be implemented rather than as limiting the scope of the invention.

(11) The term “comprising”, used in the claims, should not be interpreted as being restricted to the elements or steps listed thereafter; it does not exclude other elements or steps. It needs to be interpreted as specifying the presence of the stated features, integers, steps or components as referred to, but does not preclude the presence or addition of one or more other features, integers, steps or components, or groups thereof. Thus, the scope of the expression “a device comprising A and B” should not be limited to devices consisting only of components A and B, rather with respect to the present invention, the only enumerated components of the device are A and B, and further the claim should be interpreted as including equivalents of those components.

(12) The term character, as used herein refers to a symbol or sign used in writing like a grapheme, a logogram, an alphabetic letter, a typographical ligature, a numerical digit or a punctuation sign.

(13) The terms “designed for”, speaking about for example an OCR engine or a classification designed for a type of character, refer to the fact the OCR engine or classification has been optimized in order to be especially fast and accurate in the identification or classification of that type of character, which can be for example the Asian type of character, Latin type of character, Arabic type of character, . . . . An OCR engine or a classification designed for a type of characters uses a database including models of characters of that type of characters. All types of characters may include punctuation signs, numerical digits and symbols. An OCR engine or classification designed for a given kind of character may be able to identify or classify other kinds of characters, but, typically, an OCR engine designed for Asian character accurate in recognizing Latin characters than an OCR engine designed for Latin characters.

(14) The terms identification and ID as used herein refer to a recognition of one or several characters in machine-readable code to obtain a searchable string of characters. The identification or ID is an output of an OCR engine.

(15) The term classification as used herein refers to the generation of a plurality of hypotheses on the identification of one or several characters. Each identification hypothesis, or ID hypothesis, is associated with a probability that the identification hypothesis is correct, i.e., that the image or segmentation part that undergoes the classification indeed represents the character or group of characters of the identification hypothesis. Classification can be performed by a dedicated program called a classifier. A classification designed to classify characters one by one or ligatures is called single-character classification. The term “to classify” as used herein means “to realize a classification”. Even when the invention is described with embodiments comprising single-character classification, it should be understood that the scope of the present invention extends to other kinds of classification, including classification other than single-character.

(16) The terms hypotheses, ID hypotheses and identification hypotheses as used herein refer to alternative solutions for the identification of a character or group of characters. One or several hypotheses are the output of the classification and a decision has still to be made on determining the output of the OCR engine. An hypothesis corresponds to a predefined model of a character or a group of characters. The hypotheses can also be called alternatives or candidates.

(17) The terms atom and blob as used herein refer to the biggest part of an image that is made of touching pixels of a given color. For example, in a black and white image, an atom or blob is an ensemble of black pixels connected together by black pixels.

(18) The term contextual decision as used herein refers to decision based on the context of a character to decide on the identification of said character. For example, a whole word can be considered to decide on the identification of every letter of the word.

(19) FIG. 1 shows a flowchart of an OCR method 100 according to the state of the art. An image 101 of a string of characters is taken as input by an OCR engine 102. The OCR engine 102 processes the information contained in the image and provides an ID 103 of the characters of the string of characters of the image 101 as an output.

(20) FIG. 2 shows a flowchart of an OCR engine 102 according to the state of the art. The OCR engine 102 includes a step 201 that combines segmentation 202 and single character classification 203.

(21) The segmentation 202 is a division of the image of the string of characters 101 into segmentation parts that possibly correspond to characters. A segmentation part is a part of the image of the string of characters 101 that undergoes processes to determine if it represents a character, a group of characters, a pattern, . . . . Typically, many alternative divisions of the image of the string of characters are considered during the step 201 combining segmentation 202 and single character classification 203. If the image of the string of characters 101 is an image of a line of characters, a segmentation part is a part of that line of characters. Since a segmentation part is a part of an image, a segmentation part is itself an image.

(22) The single character classification 203 generates, for a segmentation part, one or several ID hypotheses with their associated probabilities. Typically, the single character classification 203 calculates, amongst a series of models of characters, which models have the highest probabilities to correspond to the character represented on the segmentation part.

(23) The single character classification 203 generates, in association with each ID hypothesis for a given segmentation part, a probability that this ID hypothesis is correct, i.e., a probability that the segmentation part actually represents this character. The probability can be for example a percentage or a likelihood weight.

(24) A character classification more general than “single-character classification” can be used in the OCR engine 102. It can identify group of characters (e.g. ligatures), patterns, logos, designs . . . .

(25) The combination step 201 uses alternatively segmentation 202 and single character classification 203 to generate a series of hypotheses 204A on the ID of the characters of the image of the string of characters 101 and associated probabilities 204B.

(26) The series of hypotheses 204A on the ID of the characters of the image of the string of characters 101, associated with their probabilities 204B, is then analyzed during a step of contextual decision 205 that determines, amongst the hypotheses on ID of the characters 204A, the hypothesis with the highest global probability for the full image of the string of characters 101. The hypothesis with the highest global probability is identified as the ID of the characters 103 and is the output of the OCR engine 102.

(27) FIG. 3 shows a flowchart of a step 390 combining segmentation and single character classification according to an embodiment of the invention. A segmentation 350 generates a segmentation part 351. In an embodiment of the present invention, the segmentation 350 is based on the detection of inter-character breaks or word breaks. In a further embodiment of the present invention, the segmentation 350 generates atoms, which are ensemble of pixels of a given color, and a segmentation part comprises one to five atoms. In still an other embodiment of the present invention, the segmentation 350 comprises the steps of: determining a first starting point coordinate of a pixel contrasting to a background, generating a list of potential character widths dependent on a maximum character width and on characteristics of the portion of the character string image corresponding to the maximum character width, and determining a second portion of the character string image corresponding to the first starting point coordinate and the first width on the list of potential character widths.

(28) The segmentation part 351 is then classified by a single character classification step 300 according to an embodiment of the invention.

(29) In the single character classification 300, the segmentation part 351 is first analyzed by a single character classification 301 designed for Asian characters to generate one or several hypotheses 302A on the ID of the character represented by the segmentation part 351 and associated probabilities 302B. In an embodiment of the invention, the probability is a number in the interval [0,1], where 1 indicates an excellent match between an ID hypothesis and the segmentation part 351 and 0 a very bad match between an ID hypothesis and the segmentation part 351. The one or several hypotheses 302A on the ID of the character and associated probabilities 302B are an output of the combination step 390.

(30) In an embodiment of the invention, the single character classification designed for Asian characters 301 does not include the possibility of recognizing Latin characters, and all hypotheses of 302A relate to Asian characters. In an embodiment of the invention, the single character classification designed for Asian characters 301 includes the possibility of recognizing Latin characters and hypotheses 302A relate to Asian or Latin characters.

(31) In an embodiment of the invention, the single character classification designed for Asian characters 301 includes a feature extraction step that generates a feature vector. The feature extraction step involves a Gabor filter that is a sinusoidal wave multiplied by a Gaussian function. The feature vector is used to generate the probabilities of models of characters of a predetermined list.

(32) A verification step 303 checks if the one or several hypotheses 302A on the ID of the character verifies at least one condition in a list of one or several conditions.

(33) In an embodiment of the present invention, one of the conditions of the list is that all probabilities 302B of the hypotheses 302A are below a given threshold. A high threshold means that the condition in the verification step 303 is easily satisfied and many segmentation parts 351 will be analyzed by the second single character classification 305 designed for Latin characters as will be described later, which increases the accuracy of the overall OCR method but decreases its speed. A low threshold means that the condition in the verification step 303 is not easily satisfied and not many segmentation parts 351 will be analyzed by the single character classification 305, which increases the speed of the method but decreases its accuracy. In an embodiment of the invention, the threshold is at 0.7, which is a trade-off between speed and accuracy.

(34) In an embodiment of the present invention, one of the conditions of the list in step 303 is that at least an hypothesis amongst the one or several hypotheses 302A relates to an Asian character known to look like a Latin character. FIG. 4 illustrates the resemblance between some Asian and Latin characters. The Asian character 501 (CJK Unified Ideograph 5DE5) looks like the 502 (Latin capital letter i). The right part of the Asian character 503 (CJK Unified Ideograph 5317) can be confound with a t 504. The Asian character 505 (CJK Unified Ideograph 52F2) looks like a 2 (digit two) 506. The Asian character 507 (CJK Unified Ideograph 8BB8) can be confound with the letters i and F 508. The Asian character 509 (Hangul Syllable i) can be confound with the letters o and l 510 (O and L in lower case). For example, the single character classification 301 designed for Asian characters may provide, for a given segmentation part 351, the Asian character 505 as hypothesis with a high probability even if the segmentation part actually represents the character 2. It is interesting for accuracy that such a segmentation part is analyzed by a single character classification designed for Latin characters.

(35) In an embodiment of the present invention, where the single character classification 301 designed for Asian characters includes the possibility of recognizing Latin characters, one of the conditions of the list is that an hypothesis amongst the hypotheses 302A relates to a Latin character.

(36) In an embodiment of the present invention, where the single character classification 301 designed for Asian characters includes the possibility of recognizing Latin characters, one of the conditions of the list is that an hypothesis of probability equal to higher than a threshold amongst the hypotheses 302A relates to a Latin character. In a further embodiment of the invention, the threshold is equal to 50%.

(37) In an embodiment of the present invention, where the single character classification 301 designed for Asian characters includes the possibility of recognizing Latin characters, one of the conditions of the list is that an hypothesis of highest probability amongst the hypotheses 302A relates to a Latin character.

(38) If at least one of the conditions of the list is satisfied at the verification step 303, the single character classification 300 continues with a single character classification 305 designed for Latin characters.

(39) The output of the single character classification 305 designed for Latin characters is one or several hypotheses 306A on a Latin ID of the character on the segmentation part 351, associated with weights 306B. In an embodiment of the present invention, weights 306B are numbers in the interval [0,255], where the number 0 indicates an excellent match between an ID hypothesis and the segmentation part 351 and the number 255 indicates a very bad match between an ID hypothesis and the segmentation part 351.

(40) In an embodiment of the present invention, a weight scaling step 307 is necessary to match the scale of the Latin weights W.sub.Latin 306B of the Latin ID hypotheses 306A to the scale of the Asian probabilities 302B of the Asian ID hypotheses 302A. A transformed Latin probability P.sub.Latin,transformed 308B is calculated by the formula

(41) $P_{\mathrm{Latin},\mathrm{transformed}}=\frac{1}{1+\exp \left(0.2*W_{\mathrm{Latin}}-2.6\right)}$

(42) The output of the weight scaling step 307 is the hypotheses 308A on Latin ID of the character on the segmentation part, which are the same as the Latin ID hypotheses 306A, but associated now with transformed Latin probabilities 308B that can be compared directly with the probabilities 302B that the hypotheses 302A on the Asian ID of the character are correct. The one or several hypotheses 308A on Latin ID of the character on the segmentation part with their associated probabilities 3086 are an output of the combination step 390.

(43) The location 312 of the segmentation part 351 that underwent the single character classification designed for Latin characters 305 is another output of the combination step 390.

(44) The combination step 390 then uses segmentation 350 to generate a next segmentation part 351.

(45) In an embodiment of the present invention, once the combination step 390 is performed on a full image of the string of character, to generate one or several hypotheses 302A on the Asian ID with their associated probabilities 302B and one or several hypotheses 308A on the Latin ID with their associated probabilities 308B on all segmentation parts, a step of contextual decision is performed in order to determine the combination of hypotheses 302A and 308A that provides the identification of the string of characters.

(46) In an embodiment of the present invention, at least one of the single character classifications 301 and 305, is performed by a single character classifier.

(47) In an embodiment of the present invention, the single-character classifications 301 and 305 are extended to classify groups of characters. In an embodiment of the present invention, the single-character classifications 301 and 305 are extended to classify ligatures.

(48) Even if FIG. 3 describes an embodiment of the invention where the first classification 301 is designed for Asian character recognition and the second classification 305 is designed for Latin character recognition, the invention can be used for other types of characters like Arabic characters, Cyrillic characters, Greek characters, Hebrew characters, hieroglyphs, etc. . . . .

(49) FIG. 5 illustrates a combined segmentation and single-character classification according to an embodiment of the present invention.

(50) The segmentation divides first the image of the string of characters 101 into four segmentation parts 602, 603, 604 and 605 to generate a first plurality 601 of segmentation parts. Then, the single character classification analyzes the first segmentation part 602 and generates n602 hypotheses C.sub.802-1 to C.sub.602-n602, each hypothesis C.sub.602-i having an associated probability P.sub.602-1. Then, the single character classification analyzes the second segmentation part 603 and generates n603 hypotheses C.sub.603-1 to C.sub.603-n603, each hypothesis C.sub.603-1 having an associated probability P.sub.603-i. The single character classification is repeated four times, since the first plurality 601 of segmentation parts contains four segmentation parts 602, 603, 604 and 605.

(51) Then, the segmentation divides the image of the string of characters 101 into six segmentation parts 607, 608, 609, 610, 611 and 612 to generate a second plurality 602 of segmentation parts. Then, the single character classification analyzes the first segmentation part 607 and generates n607 hypotheses C.sub.607-1 to C.sub.607-n607, each hypothesis C.sub.607-i having an associated probability P.sub.607-i. Then, the single character classification analyzes the second segmentation part 608 and generates n608 hypotheses C.sub.608-1 to C.sub.608-n608, each hypothesis C.sub.608-1 having an associated probability P.sub.608-1. The single character classification is repeated six times, since the second plurality 606 of segmentation parts contains six segmentation parts 607, 608, 609, 610, 611 and 612.

(52) The segmentation and the series of single character classifications are repeated a number of times to provide hypotheses on the ID of the characters.

(53) In an embodiment of the present invention, the process illustrated in FIG. 5 is used in combination with the flowchart of FIG. 3.

(54) FIG. 6 shows a flowchart of an OCR method 400 according to an embodiment of the invention. An image 401 of a string of characters is taken as input by a first OCR engine 402. In an embodiment of the invention, the image 401 of a string of characters is an horizontal line or part of an horizontal line. In another embodiment of the present invention, the image 401 of a string of characters is a vertical line or part of a vertical line.

(55) The first OCR engine 402 is designed for a first type of characters. In an embodiment of the invention, the first OCR engine 402 is designed for Asian characters. In an embodiment of the invention, the first OCR engine 402 is designed for Asian characters and includes the possibility of recognizing Latin characters. In an embodiment of the invention, the first OCR engine 402 uses a combination step 390 combining segmentation and single character classification using two single character classifiers as illustrated on FIG. 3. In an embodiment of the invention, the first OCR engine 402 uses a single character classification 300 as illustrated on FIG. 3. The first OCR engine 402 generates an ID 403 for characters of the first type and determines zones 404 of characters of another type in the image 401 of string of characters.

(56) In an embodiment of the invention, the zones 404 of characters of another type in the image 401 are zones where the first OCR engine 402 could not identify characters of the first type with a good level of confidence, the level of confidence being judged according to a predefined criterion.

(57) In a further embodiment of the invention, the zones 404 of characters of another type in the image 401 are ensembles of contiguous segmentation parts. In another embodiment of the invention, the zones 404 of characters of another type in the image 401 are ensembles of non-contiguous segmentation parts.

(58) In an embodiment of the invention, the zones 404 of characters of another type in the image 401 contain at least two characters. In an embodiment of the invention, the zones 404 of characters of another type in the image 401 contain at least two contiguous characters because the contextual decision step of the second OCR engine 405 is more accurate when working with at least two characters.

(59) In an embodiment of the invention, a zones 404 of characters of another type in the image 401 is no longer than a line of text. In an embodiment of the invention, a zones 404 of characters of another type in the image 401 is no longer than a column of text.

(60) In an embodiment of the present invention, the selection of zones 404 of characters of another type in the image 401 are as large as possible because the second OCR engine 405 is more accurate when working with large areas including many characters than with small areas including only one or a few characters.

(61) In an embodiment of the invention, the zones 404 of characters of another type in the image 401 are ensembles of segmentation parts, wherein at least one segmentation part satisfies at least one of the following conditions, which are checked by the first OCR engine 402: a character of the another type of characters than the first type of character was detected on the segmentation part by the first OCR engine 402; the probability of identification of the segmentation part by the first OCR engine 402 is below a threshold; the identification of the segmentation part corresponds to a character of the first type of character known to look like a character of another type of character; and a character of the second type of characters was identified on said segmentation part by the first OCR engine.

(62) The zones 404 of another type of characters are then processed by a second OCR engine 405. In an embodiment of the invention, the second OCR engine 405 is designed for a second type of characters. In an embodiment of the invention, the second OCR engine 405 is designed for Latin characters. In an embodiment of the invention, the second OCR engine 405 detects the language of the Latin characters. In an embodiment of the invention, the second OCR engine 405 uses English as default assumption for the language of the Latin characters. In an embodiment of the invention, the second OCR engine 405 uses a predetermined language for the language of the Latin characters. In an embodiment of the invention, the second OCR engine 405 is a multi-language OCR. In an embodiment of the invention, the second OCR engine 405 uses a combination step 390 combining segmentation and single character classification as illustrated on FIG. 3. In an embodiment of the invention, the second OCR engine 405 uses a single character classification 300 as illustrated on FIG. 3. In an embodiment of the invention, the second OCR engine 405 uses only one single character.

(63) The second OCR engine 405 generates an ID 406 for the characters of the second type. The output 407 of the OCR method 400 is a combination of the ID of the characters of the first type 403 and the ID of the characters of the second type 406 in an order corresponding to the position of the characters in the character string image 401.

(64) In an embodiment of the invention, at least one of the first OCR engine 402 and the second OCR engine 405 uses a pre-processing of the image of string of characters 401 to realize an image enhancement. In an embodiment of the invention, at least one of the first OCR engine 402 and the second OCR engine 405 uses a binarization of the image of string of characters 401 to separate the foreground and the background of the image of string of characters 401.

(65) In an embodiment of the present invention, contextual decisions based on decision graphs are used in at least one of the first OCR engine 402 and the second OCR engine 405. The output of the combination step combining segmentation and single character classification of the considered OCR engine, which is a series of hypotheses on the ID of the characters and probabilities associated with these hypotheses, is used to generate a first decision graph. In a decision graph, an arc is created for each hypothesis, associated with its segmentation part and its probability. An arc for a segmentation part starts at a node where ends the segmentation part just before said segmentation part on the image of string of characters 401, and ends at a node where start all the segmentation parts just after said segmentation part on the image of string of characters 401.

(66) Several decision models are then used to improve the identification accuracy. The decision models analyze the hypotheses emitted by the step combining segmentation and single character classification, and allocate to them additional identification probabilities that are added in the decision graph. The ID of the characters of the image of the string of characters taken as output of the considered OCR engine is determined by finding the path in the decision graph that maximizes the identification probability for the full string of characters.

(67) A first kind of decision model is a linguistic model. If the word “ornate” is present in the image of string of character to be identified, a combination step combining segmentation and single character classification can for example finds the word “omate” and the word “ornate” as hypotheses with similar probabilities because the letters rn taken together look like the letter m. A linguistic model using a dictionary is able to detect that the word “omate” does not exist, while the word “ornate” does.

(68) In an embodiment of the present invention, the linguistic model uses an n-gram model. If the word “TRESMEUR” is present in the image of string of character 401, a combination step combining segmentation and single character classification can for example finds the word “TRE5MEUR” and the word “TRESMEUR” as hypotheses with similar probabilities because the letters ‘S’ may look like the letter ‘5’ in a printed text. A linguistic model using a bigram (n-gram with n=2) model would prefer “TRESMEUR” if “ES” and “SM” have better probabilities of occurrence than “E5” and “5M”.

(69) Another kind of model used in an embodiment of the present invention is a typographical model. If the word “Loguivy” is present in the image of string of character 401, a combination step combining segmentation and single character classification can for example finds the word “Loguivy” and the word “Loguivv” as hypotheses with similar probabilities because the letters ‘y’ may look like the letter ‘v’ in a printed text. A typographic model using font metrics would prefer “Loguivy” because the position of the bottom of the final character corresponds more likely to the bottom position of a ‘y’ (in his model) than a ‘v’.

(70) In an embodiment of the present invention, the typographical model considers the position of the character in the image to check if sizes and positions are expected or not.

(71) These examples of linguistic and typographical models make clear the reason why it is advantageous that the zones 404 of characters of another type in the image 401 are as large as possible and contain at least two contiguous characters, since contextual models are more accurate when working on more characters.

(72) In an embodiment of the present invention, an OCR engine designed for Asian character considers a line of characters as the image of string of character for its input and a decision graph is generated for each line of characters. In an embodiment of the present invention, an OCR engine designed for Latin character considers a word as the image of string of character for its input and a decision graph is generated for each word.

(73) In an embodiment of the present invention, the second OCR engine determines zones of a third type of characters in the image 401 of string of character and a third OCR engine, designed for the third type of characters, processes the zones of the third type of characters. In a further embodiment of the invention, more types of characters are considered in a similar way, with OCR engines designed for different types of character working one after each other in cascade or in parallel with each other, and based on the fulfillment of given conditions, the overall OCR method will use more or less OCR engines to identify characters.

(74) An OCR method according to an embodiment of the present invention can be described as follows. The image of a line of characters, which are expected to be mainly Asian characters, is analyzed by a first OCR engine. The segmentation of the first OCR engine is a segmentation designed for Asian character. It divides the image of a line of characters into atoms and then generates segmentation parts that include between one and five atoms. A segmentation part is first analyzed by a single character classification designed for Asian characters but able to classify Latin characters, to generate one or several Asian hypotheses on said segmentation part, with their associated probabilities. The probabilities are number in the interval [0,1].

(75) The one or several Asian hypotheses are verified according to three conditions. If none of the conditions is satisfied, the one or several Asian hypotheses, with their associated probabilities, are taken as the single output of the single character classification, the conditions being: All the probabilities associated to the Asian hypotheses are below 0,7. One of the Asian hypotheses is actually a Latin character with a probability of at least 0,5. One of the Asian hypotheses is an Asian character that is known to look like a Latin character.

(76) If at least one of these conditions is satisfied, the segmentation part is then analyzed by a single character classification designed for Latin characters, to generate one or several Latin hypotheses on said segmentation part, with their associated weights. The weights, which are numbers in the interval [0,255] are transformed according to the formula

(77) $P_{\mathrm{Latin},\mathrm{transformed}}=\frac{1}{1+\exp \left(0.2*W_{\mathrm{Latin}}-2.6\right)}$
to generate probabilities that can be directly compared with the probabilities of Asian hypotheses.

(78) The outputs of the single character classification are then (1) one or several Asian hypotheses, with their associated probabilities; (2) one or several Latin hypotheses, with their associated probabilities; and (3) the locations of the one or several Latin hypotheses.

(79) Then, the process is repeated on a next segmentation part.

(80) Once all the segmentations parts of the image of the string of characters have been through the Asian single character classifier, and possibly through the Latin single character classifier, all the Asian hypotheses and their probabilities, and the Latin hypotheses and their probabilities are used to generate a first decision graph. Contextual decision designed for Asian characters, but able to manage Latin characters, is then applied to generate a second decision graph. The path along the second decision graph that maximizes the probability of identification of the full string of characters is taken as output of the first OCR engine. This path contains Asian characters and may contain also Latin characters.

(81) If this path contains Latin characters, i.e., if Latin characters are identified by the first OCR engine, the locations of zones of these Latin characters are transmitted to a second OCR engine, which is designed for Latin characters. Indeed, since these zones contain Latin characters, it is interesting, to improve accuracy, to apply there a full OCR engine designed for Latin characters, including contextual decision designed for Latin characters, which was not done so far. A zone is defined as the largest area of the image of the line of characters that contain only Latin characters. A zone contains at least two characters. It is preferable that these zones are as large as possible because the more characters are analyzed at once by the contextual decision methods, the more accurate these methods are. The second OCR engine identifies then the Latin characters on these zones.

(82) The Asian characters identified by the first OCR engine and the Latin characters identified by the second OCR engine are then ordered according to their location on the image of the string of characters, to be the identification of the characters of the image of the string of characters.