Methods and systems for processing of images of mathematical expressions

• US 9,858,506 B2
• Filed: 04/06/2015
• Issued: 01/02/2018
• Est. Priority Date: 09/02/2014
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Development LLC
• Inventors: Isupov, Dmitry, Masalovitch, Anton
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US14/679,219
• Publication Number:
  US 20160063323A1
• Time in Patent Office: 1,002 Days
• Field of Search: 382200, 382203, 382204, 382310
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

The current document is directed to methods and systems that convert document images containing mathematical expression into corresponding electronic documents. In one implementation, an image or sub-image containing a mathematical expression is recursively partitioned into blocks separated by white-space stripes. Horizontal and vertical partitioning are alternately and recursively applied to the image or sub-image containing a mathematical expression until the lowest-level blocks obtained by partitioning correspond to symbols recognizable by character-recognition methods. Graph-based analysis of the recognized symbols provides a basis for encoding an equivalent representation of the mathematical expression contained in the image or sub-image.

Claims

1. A system comprising:

one or more electronic memories that store instructions for automated optical symbol recognition; and

one or more processors to execute the instructions to;

apply blocking to an image stored in at least one of the memories to decompose the image into an ordered set of symbol variants, wherein the image depicts a mathematical expression, and wherein, to apply blocking to the image, the processors are further to execute the instructions to;

set a blocking-direction indication to indicate one of a horizontal blocking-direction or a vertical blocking-direction;

set a current-level indication to indicate a first level;

block the image into sub-images at a level according to the current-level indication and in a direction according to the blocking-direction indication; and

recursively for each sub-image in the sub-images at the level, apply one or more symbol-recognition methods to the sub-image;

select a most probable path from among candidate paths corresponding to the ordered set of symbol variants;

use the most probable path and the ordered set of symbol variants to generate an encoded mathematical expression equivalent to the mathematical expression; and

store the encoded mathematical expression in one or more of the memories.

2. The system of claim 1, wherein, to apply blocking to the image, the processors are further to execute the instructions to:

recursively for each sub-image in the sub-images at the level, in response to a failure of the application of the symbol-recognition methods to identify the sub-image as a single-symbol-containing sub-image, set the blocking-direction indication to the other of the horizontal blocking direction or the vertical blocking direction, advance the current-level indication to a next level, and recursively apply blocking to the sub-image using the blocking-direction indication and the current-level indication.

3. The system of claim 1, wherein the candidate paths corresponding to the ordered set of symbol variants each comprise one or more arcs, and wherein each of the arcs encompasses an ordered subset of the ordered set of symbol variants.

4. The system of claim 3, wherein each of the arcs is associated with an arc weight, and wherein the most probable path is selected based on the arc weight of one or more of the arcs.

5. The system of claim 4, wherein a path weight is computed for each candidate path among the candidate paths as a sum of the arc weight associated with each of the arcs of the candidate path, and wherein the most probable path is selected based on the path weight of one or more of the candidate paths.

6. The system of claim 5, wherein a probability of the candidate path being the most probable path is inversely related to the path weight of the candidate path, and wherein, to select the most probable path, the processors are further to execute the instructions to select the candidate path having the path weight that is lowest as the most probable path.

7. The recognition system of claim 5, wherein a probability of the candidate path being the most probable path is directly related to the path weight of the candidate path, and wherein, to select the most probable path from among the candidate paths corresponding to the ordered set of symbol variants, the processors are further to execute the instructions to select the candidate path having the path weight that is highest as the most probable path.

8. The system of claim 1, wherein, to apply blocking to the image, the processor are further to execute the instructions to:

identify white-space stripes with directions equal to, or within a threshold angular displacement from, a direction orthogonal to a blocking direction;

coalesce overlapping ones of the white-space stripes to produce non-overlapping white-space stripes; and

use the non-overlapping white-space stripes as block borders to partition the image into two or more blocks along the blocking direction.

9. The system of claim 8, wherein the white-space stripes comprise a stripe with parallel sides, wherein the sides have directions equal to an angle of intersection with the blocking direction, and wherein the stripe spans the image that contains less than a threshold number of pixels, or less than a threshold area, corresponding to symbols within the image.

10. The system of claim 8, wherein, to coalesce the overlapping ones of the white-space stripes, the processors are further to execute the instructions to:

identify one or more groups of two or more of the white-space stripes that are mutually intersecting or that are each separated from another one of the white-space stripes in the group by less than a threshold distance;

coalesce intersecting ones of the white-space stripes of each group among the groups that have a same direction; and

select a white-space stripe from each group among the groups that has a direction equal to a direction of one or more of the whites-pace stripes with a greatest total area in the group.

11. A method comprising:

applying, by one or more processors that execute instructions stored in one or more memories for automated optical symbol recognition, blocking to an image stored in at least one of the memories to decompose the image into an ordered set of symbol variants, wherein the image depicts a mathematical expression;

selecting, by the processors, a most probable path from among candidate paths corresponding to the ordered set of symbol variants, wherein the candidate paths corresponding to the ordered set of symbol variants each comprise one or more arcs, wherein each of the arcs encompasses an ordered subset of the ordered set of symbol variants, wherein each of the arcs is associated with an arc weight, and wherein the most probable path is selected based on the arc weight of one or more of the arcs;

using the most probable path and the ordered set of symbol variants to generate an encoded mathematical expression equivalent to the mathematical expression; and

storing the encoded mathematical expression in one or more of the memories.

12. The method of claim 11, wherein applying blocking to the image further comprises:

setting a blocking-direction indication to indicate one of a horizontal blocking direction or a vertical blocking-direction;

setting a current-level indication to indicate a first level;

blocking the image into sub-images at a level according to the current-level indication and in a direction according to the blocking-direction indication; and

recursively for each sub-image in the sub-images at the current level;

applying one or more symbol-recognition methods to the sub-image; and

in response to a failure of the application of the symbol-recognition methods to identify the sub-image as a single-symbol-containing sub-image, setting the blocking-direction indication to the other of the horizontal-blocking direction or the vertical-blocking direction, advancing the current-level indication, and recursively applying blocking to the sub-image using the blocking-direction indication and the current-level indication.

13. The method of claim 11, wherein a path weight is computed for each candidate path among the candidate paths as a sum of the arc weight associated with each of the arcs of the candidate path.

14. The method of claim 13, wherein a probability of the candidate path being the most probable path is inversely related to the path weight of the candidate path, and wherein selecting the most probable path further comprises selecting the candidate path having the path weight that is lowest as the most probable path.

15. The method of claim 13, wherein a probability of the candidate path being the most probable path is directly related to the path weight of the candidate path, and wherein selecting the most probable path further comprises selecting the candidate path having the path weight that is highest as the most probable path.

16. The method of claim 11, wherein applying blocking to the image further comprises:

identifying white-space stripes with directions equal to, or within a threshold angular displacement from, a direction orthogonal to a blocking direction;

coalescing overlapping ones of the white-space stripes to produce non-overlapping white-space stripes; and

using the non-overlapping white-space stripes as block borders to partition the image into two or more blocks along the blocking direction.

17. The method of claim 16, wherein the white-space stripes comprise a stripe with parallel sides, wherein the sides have directions equal to an angle of intersection with the blocking direction, and wherein the stripe spans the image that contains less than a threshold number of pixels, or less than a threshold area, corresponding to symbols within the image.

18. The method of claim 16, wherein coalescing the overlapping ones of the white-space stripes further comprises:

identifying one or more groups of two or more of the white-space stripes that are mutually intersecting or that are each separated from another one of the white-space stripes in the group by less than a threshold distance;

coalescing intersecting ones of the white-space stripes of each group among the groups that have a same direction; and

selecting a white-space stripe from each group among the groups that has a direction equal to a direction of one or more of the whites-pace stripes with a greatest total area in the group.

19. Computer A non-transitory computer-readable storage medium having stored therein instructions that, when executed by one or more processors, cause the processors to:

apply, by the processors that execute the instructions for automated optical symbol recognition, blocking to an image stored in at least one of one or more memories to decompose the image into an ordered set of symbol variants, wherein the image depicts a mathematical expression;

select, by the processors, a most probable path from among candidate paths corresponding to the ordered set of symbol variants, wherein the candidate paths corresponding to the ordered set of symbol variants each comprise one or more arcs, wherein each of the arcs encompasses an ordered subset of the ordered set of symbol variants, wherein each of the arcs is associated with an arc weight, and wherein the most probable path is selected based on the arc weight of one or more of the arcs;

use the most probable path and the ordered set of symbol variants to generate an encoded mathematical expression equivalent to the mathematical expression; and

store the encoded mathematical expression in one or more of the memories.