Fast CJK character recognition

• US 8,971,630 B2
• Filed: 06/19/2012
• Issued: 03/03/2015
• Est. Priority Date: 04/27/2012
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Development LLC
• Inventors: Chulinin, Yuri
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US13/527,239
• Publication Number:
  US 20130286030A1
• Time in Patent Office: 987 Days
• Field of Search: None
• US Class Current: 382/182
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/15 Cutting or merging image elements, e.g. region growing, watershed or clustering-based techniques
• CPC Class Codes: G06V 30/18181 Graphical representation, e.g. directed attributed graph

Abstract

Methods are described for determining an optimal path for creating a scheme for dividing a text line of Chinese, Japanese or Korean (CJK) characters into character cells prior to applying classifiers and recognizing characters. Gaps between characters are found as a window is moved down the text line. Finding gaps may involve finding 4-connected paths. A histogram is built based on distances from start of window to a respective gap. The window is moved to the end of each gap after each gap is found and distances measured. Process is repeated until window reaches the end of the text line and all gaps found. A linear division graph (LDG) is constructed according to detected gaps. Penalties for certain distances are applied. An optimum path is one with a minimal penalty sum and can be used as a scheme for dividing text lines into character cells.

Claims

1. A method for facilitating recognition of glyph-based characters in an electronic image, the electronic image including representations of glyph-based characters, the method comprising:

identifying a line of glyph-based character representations in the electronic image;

isolating a plurality of glyph-based character representations from the line of glyph-based character representations;

loading a set of glyph-based character patterns into a computer memory;

loading the plurality of glyph-based character representations into the computer cache; and

recognizing the plurality of glyph-based character representations as a batch using the set of glyph-based character patterns of the computer memory while one or more of the plurality of character representations are in the computer cache.

2. The method of claim 1, wherein the plurality of glyph-based character representations is whole line of glyph-based character representations.

3. The method of claim 1, wherein the plurality of glyph-based character representations is a part of a line of glyph-based character representations.

4. The method of claim 1, wherein isolating the plurality of glyph-based character representations includes:

detecting character gaps in the line of glyph-based character representations;

creating a histogram of distances for the detected character gaps;

constructing a graph according to the detected character gaps;

assigning a penalty to arcs of the graph wherein the penalty is based in part on the histogram of distances; and

selecting a path in the graph associated with the character cells based on said penalty and arcs of the graph.

5. The method of claim 4, wherein the graph is a linear division graph (LDG), which is constructed by performing steps including:

isolating values substantially near maxima values in the histogram of distances, wherein the isolated values are associated with respective detected character gaps;

creating arcs for each detected character gap;

assigning a penalty to the arcs;

creating paths for the LDG;

calculating aggregate penalties for each path associated with the LDG based on the penalties assigned to the arcs; and

selecting a desired path from among the paths associated with the LDG based on the aggregate penalties associated with the paths.

6. The method of claim 4, wherein the character gap is a 4-connected path.

7. The method of claim 4, wherein the desired path is a path associated with a smallest value of absolute values of the aggregate penalties.

8. The method of claim 4, wherein the method further comprises:

determining whether the line of glyph-based character representations includes non-CJK characters by detecting whether any of the arcs associated with the desired path have been assigned a second type penalty.

9. The method of claim 1, wherein the set of glyph-based character patterns is a subset of a macro-set of glyph-based character patterns, wherein the macro-set of glyph-based character patterns are a set of glyph-based character patterns in a storage medium of a device performing said method.

10. The method of claim 1, wherein the computer memory is a network-accessible random access memory.

11. The method of claim 1, wherein the computer memory is a random access memory of a device performing the method.

12. A device for detecting the boundaries of characters in an electronic image, the electronic image including representations of characters, the device comprising:

a processor; and

a memory configured with processor-executable instructions which, when executed by the processor, implement a method, the method comprising;

identifying a line of glyph-based character representations in the electronic image;

isolating a plurality of glyph-based character representations;

loading a set of character patterns into the memory;

loading the plurality of glyph-based character representations into the cache; and

recognizing the plurality of glyph-based character representations with the set of character patterns while one or more of the plurality of glyph-based character representations are in the cache.

13. The device of claim 12, wherein isolating the first plurality of glyph-based character representations includes:

detecting character gaps in the line of glyph-based character representations;

creating a histogram of distances for the detected character gaps; and

constructing a linear division graph (LDG) according to the detected character gaps by performing steps including;

isolating values substantially near maxima values in the histogram of distances, wherein the isolated values are associated with respective detected character gaps;

creating arcs for each detected character gap;

assigning a penalty to the arcs;

creating paths associated with the LDG;

calculating aggregate penalties for each path associated with the LDG based on the penalties assigned to the arcs; and

selecting a desired path from among the paths associated with the LDG based on the aggregate penalties associated with the paths.

14. The device of claim 13, wherein creating the histogram of distances for the detected character gaps includes:

[1] setting a window width for the line of glyph-based character representations;

[2] orienting the window at a current target location associated with the line of glyph-based character representations;

[3] using the detected character gaps, creating a histogram for the window; and

[4] repeating steps [1], [2] and [3] for each identified gap.

15. The device of claim 13, wherein the desired path is a path associated with a smallest value of absolute values of the aggregate penalties.

16. The device of claim 12, wherein the assigning of a penalty to the arcs includes assigning a first type penalty or a second type penalty to a respective arc based upon a position of the arc relative to a designated region in the histogram.

17. One or more physical non-transitory computer accessible media encoded with instructions for performing a method, the method comprising:

identifying a line of glyph-based character representations in the electronic image;

isolating a plurality of glyph-based character representations;

loading a set of glyph-based character patterns into a computer memory;

loading the plurality of glyph-based character representations into the computer cache; and

recognizing the plurality of glyph-based character representations with the set of glyph-based character patterns while one or more of the plurality of glyph-based character representations are in the computer cache.

18. The one or more physical non-transitory computer accessible media of claim 17, wherein the method further comprises:

detecting character gaps in the line of glyph-based character representations;

creating a histogram of distances for the detected character gaps;

constructing a graph according to the detected character gaps;

assigning a penalty to arcs of the graph wherein the penalty is based in part on the histogram of distances; and

selecting a path in the graph associated with the character cells based on said penalty and arcs of the graph.

19. The one or more physical non-transitory computer accessible media of claim 18, wherein the graph is a linear division graph (LDG), which is constructed by performing steps including:

isolating values substantially near maxima values in the histogram of distances, wherein the isolated values are associated with respective detected character gaps;

creating arcs for each detected character gap;

assigning a penalty to the arcs;

creating paths for the LDG;

calculating aggregate penalties for each path associated with the LDG based on the penalties assigned to the arcs; and

selecting a desired path from among the paths associated with the LDG based on the aggregate penalties associated with the paths.