METHODS AND SYSTEMS FOR PROCESSING OF IMAGES OF MATHEMATICAL EXPRESSIONS

• US 20160063323A1
• Filed: 04/06/2015
• Published: 03/03/2016
• Est. Priority Date: 09/02/2014
• Status: Active Grant

• Current Assignee: ABBYY Development LLC
• Original Assignee: ABBYY Development LLC
• Inventors: Masalovitch, Anton, Isupov, Dmitry
• Granted Patent: US 9,858,506 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. An optical-symbol-recognition system comprising:

one or more processors;

one or more memories; and

computer instructions, stored in one or more of the one or more memories that, when executed by one or more of the one or more processors, control the optical-symbol-recognition system to process an image containing a mathematical expression by

applying blocking to the image containing the mathematical expression to decompose the image into an ordered set of symbol variants,

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

using the most probable path and ordered set of symbol variants to generate an encoded mathematical expression equivalent to the mathematical expression contained in the image, and

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

2. The optical-symbol-recognition system of claim 1 wherein applying blocking to the image containing the mathematical expression to decompose the image into an ordered set of symbol variants, further comprises:

setting a blocking-direction indication to indicate horizontal blocking;

horizontally blocking the image into sub-images at a first level; and

recursively

for each sub-image at a current level,

applying one or more symbol-recognition methods to the currently considered sub-image, and

when the one or more symbol-recognition methods fail to identify the sub-image as a single-symbol-containing sub-image, setting the blocking-direction indication opposite to the current blocking direction represented by the blocking-direction indication, advancing an indication of the current level, and recursively applying blocking to the sub-image using the blocking-direction indication and current-level indication.

3. The optical-symbol-recognition system of claim 1 wherein the candidate paths corresponding to the ordered set of symbol variants each comprises one or more arcs, each arc encompassing an ordered subset of the ordered set of symbol variants.

4. The optical-symbol-recognition system of claim 3 wherein each arc of each candidate path is associated with a weight.

5. The optical-symbol-recognition system of claim 4 wherein a weight is computed for each candidate path as the sum of the weights associated with the arcs of the candidate path.

6. The optical-symbol-recognition system of claim 5

wherein the lower the weight computed for a candidate path, the more probable the candidate path;

and

wherein selecting, from among candidate paths corresponding to the ordered set of symbol variants, a most probable path further includes selecting, as the most probable path, the candidate path having a lowest computed weight.

7. The optical-symbol-recognition system of claim 5

wherein the higher the weight computed for a candidate path, the more probable the candidate path;

and

wherein selecting, from among candidate paths corresponding to the ordered set of symbol variants, a most probable path further includes selecting, as the most probable path, the candidate path having a highest computed weight.

8. The optical-symbol-recognition system of claim 1 wherein blocking is applied to an image or sub-image by:

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

coalescing overlapping white-space stripes in the set of identified white-space stripes to produce a set of non-overlapping white-space stripes; and

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

9. The optical-symbol-recognition system of claim 8 wherein white-space stripes with directions equal to, or within a threshold angular displacement from, a direction orthogonal to a blocking direction each further comprises:

a stripe with parallel sides, the sides having directions equal to an angle of intersection with the indicated blocking direction, that spans an image or sub-image that contains less than a threshold number of pixels, or less than a threshold area, corresponding to symbols within the image.

10. The optical-symbol-recognition system of claim 8 wherein coalescing overlapping white-space stripes in the set of identified white-space stripes to produce a set of non-overlapping white-space stripes further comprises:

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

coalescing together intersecting white-space stripes of each group that have the same direction; and

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

11. A method, implemented as computer instructions stored in one or more memories of an optical-symbol-recognition system that additionally includes one or more processors, that converts an image or sub-image containing a mathematical expression into an encoded mathematical expression equivalent to the mathematical expression contained in the image or sub-image, the method comprising:

applying blocking to the image containing the mathematical expression to decompose the image into an ordered set of symbol variants,

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

using the most probable path and ordered set of symbol variants to generate an encoded mathematical expression equivalent to the mathematical expression contained in the image, and

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

12. The method of claim 11 wherein applying blocking to the image containing the mathematical expression to decompose the image into an ordered set of symbol variants, further comprises:

setting a blocking-direction indication to indicate horizontal blocking;

horizontally blocking the image into sub-images at a first level; and

recursively

for each sub-image at a current level,

applying one or more symbol-recognition methods to the currently considered sub-image, and

when the one or more symbol-recognition methods fail to identify the sub-image as a single-symbol-containing sub-image, setting the blocking-direction indication opposite to the current blocking direction represented by the blocking-direction indication, advancing an indication of the current level, and recursively applying blocking to the sub-image using the blocking-direction indication and current-level indication.

13. The method of claim 11 wherein the candidate paths corresponding to the ordered set of symbol variants each comprises one or more arcs, each arc encompassing an ordered subset of the ordered set of symbol variants.

14. The method of claim 13

wherein each arc of each candidate path is associated with a weight;

and

wherein a weight is computed for each candidate path as the sum of the weights associated with the arcs of the candidate path.

15. The method of claim 14

wherein the lower the weight computed for a candidate path, the more probable the candidate path;

and

wherein selecting, from among candidate paths corresponding to the ordered set of symbol variants, a most probable path further includes selecting, as the most probable path, the candidate path having a lowest computed weight.

16. The method of claim 14

wherein the higher the weight computed for a candidate path, the more probable the candidate path;

and

wherein selecting, from among candidate paths corresponding to the ordered set of symbol variants, a most probable path further includes selecting, as the most probable path, the candidate path having a highest computed weight.

17. The method of claim 11 wherein blocking is applied to an image or sub-image by:

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

coalescing overlapping white-space stripes in the set of identified white-space stripes to produce a set of non-overlapping white-space stripes; and

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

18. The method of claim 17 wherein white-space stripes with directions equal to, or within a threshold angular displacement from, a direction orthogonal to a blocking direction each further comprises:

a stripe with parallel sides, the sides having directions equal to an angle of intersection with the indicated blocking direction, that spans an image or sub-image that contains less than a threshold number of pixels, or less than a threshold area, corresponding to symbols within the image.

19. The method of claim 17 wherein coalescing overlapping white-space stripes in the set of identified white-space stripes to produce a set of non-overlapping white-space stripes further comprises:

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

coalescing together intersecting white-space stripes of each group that have the same direction; and

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

20. Computer instructions, stored in one or more memories of an optical-symbol-recognition system that additionally includes one or more processors, that, when executed on one or more of the one or more processors, converts an image or sub-image containing a mathematical expression into an encoded mathematical expression equivalent to the mathematical expression contained in the image or sub-image by:

applying blocking to the image containing the mathematical expression to decompose the image into an ordered set of symbol variants,

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

using the most probable path and ordered set of symbol variants to generate an encoded mathematical expression equivalent to the mathematical expression contained in the image, and

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