Formula detection engine

• US 9,928,225 B2
• Filed: 01/23/2012
• Issued: 03/27/2018
• Est. Priority Date: 01/23/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lazarevic, Milos, Raskovic, Milos, Obuljen, Aljosa, Petrovic Tankovic, Vanja
• Primary Examiner(s): Paula, Cesar
• Assistant Examiner(s): Faber, David
• Application Number:
  US13/521,318
• Publication Number:
  US 20130205200A1
• Time in Patent Office: 2,255 Days
• CPC Class Codes: G06F 16/5846 using extracted text
• CPC Class Codes: G06F 16/5854 using shape and object relationship
• CPC Class Codes: G06F 40/151 Transformation
• 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/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A formula detection engine and associated method. The formula detection engine locates formulas within a fixed format document portion by identifying formula seeds. The formula detection engine creates and expands a boundary around the formula seed to define a formula area. To eliminate overlap with surrounding normal text, the formula area is divided into multiple formula areas based on vertical position and horizontal spacing between the formula elements. After being vertically ordered, horizontally overlapping formula areas are merged to reconstruct the formula as a flowable element.

Claims

1. A method for converting a fixed format document containing a formula into a flow format document, the method comprising the acts of:

detecting a formula seed of a formula in data parsed from a page of a fixed format document, wherein the formula seed comprises a text element that carries an indication of being part of a formula;

creating a formula area bounding the detected formula seed;

expanding the formula area to include one or more mathematical elements that are detected on the page based on a proximity to the detected formula seed, wherein together the detected formula seed and the included one or more mathematical elements comprise a plurality of captured elements;

placing the plurality of captured elements into one or more groups based on a vertical position of the plurality of captured elements relative to a line of normal text that overlaps the formula area;

creating a new formula area around each of the one or more groups;

splitting each new formula area based on a horizontal spacing between the captured elements in the new formula area;

selecting a set of split formula areas based on an overlap of the split formula areas; and

merging the split formula areas within the set into a single formula for display on a single line of a page of a flow format document.

2. The method of claim 1 characterized in that the act of detecting a formula seed in a fixed format document further comprises the act of detecting at least one of a mathematical keyword, a mathematical symbol, and a mathematical operator in the fixed format document.

3. The method of claim 2 characterized in that the act of detecting a formula seed in a fixed format document further comprises the act of detecting text proximate to at least one of the mathematical keyword, the mathematical symbol, and the mathematical operator as being within the formula area.

4. The method of claim 3 characterized in that the act of detecting text proximate to at least one of the mathematical keyword, the mathematical symbol, and the mathematical operator as being within the formula area further comprises the act of detecting text as being within the formula area based on the relative position of the text to at least one of the mathematical keyword, the mathematical symbol, and the mathematical operator.

5. The method of claim 1 characterized in that the act of detecting a formula seed in a fixed format document further comprises the act of detecting text in the fixed format document rendered in a mathematical font.

6. The method of claim 1, wherein selecting the set of split formula areas is further based on a vertical position of each of the split formula areas.

7. The method of claim 6, wherein selecting the set of split formula areas further comprises placing split formula areas in the set when a vertical separation distance between two successively ordered split formula areas does not exceed a selected distance threshold.

8. The method of claim 1, wherein the horizontal spacing between the captured element in the new formula area is based on a selected distance threshold.

9. The method of claim 8, wherein the selected distance threshold varies based on a type of the one or more mathematical elements.

10. The method of claim 1, wherein selecting a set of split formula areas is based on a horizontal overlap of the split formula areas.

11. A system for converting a fixed format document containing a mathematical formula into a flow format document, the system comprising:

a document processor; and

a memory including computer executable instructions which, when executed by a computer, is operable to;

detect the mathematical formula in the fixed format document;

convert fixed format elements making up the mathematical formula into flow format elements arranged to substantially preserve the meaning of the mathematical formula, comprising steps to;

detect a formula seed of a formula in data parsed from a page of a fixed format document, the formula seed comprising a text element that carries an indication of being part of a formula;

create a formula area bounding the detected formula seed;

expand the formula area to include one or more mathematical elements that are detected on the page based on a proximity to the detected formula seed, wherein together the detected formula seed and the included one or more mathematical elements comprise a plurality of captured elements;

place the plurality of captured elements into one or more groups based on a vertical position of the plurality of captured elements relative to a horizontal position of a line of normal text on the page that overlaps the formula area;

create a new formula area around each of the one or more groups;

split each new formula area based on a horizontal spacing between the captured elements in the new formula area;

select a set of split formula areas based on an overlap of the split formula areas; and

merge the split formula area within the set into a single formula for display on a single line of a page of a flow format document.

12. The system of claim 11 characterized in that the document processor is further operable to detect at least one of a mathematical keyword, a mathematical symbol, and a mathematical operator in the fixed format document.

13. The system of claim 11 characterized in that the document processor is further operable to detect the fixed format elements corresponding to the mathematical formula based on the relative position of one of the fixed format elements to at least one of the mathematical keyword, the mathematical symbol, the mathematical operator, and another of the fixed format elements.

14. The system of claim 11 characterized in that the document processor is further operable to detect a mathematical font in the fixed format document.

15. The system of claim 14 characterized in that the document processor is further operable to detect fixed format elements rendered in the mathematical font.

16. The system of claim 11 characterized in that the document processor is further operable to detect the fixed format elements corresponding to the mathematical formula based on the relative positions of the fixed format elements.

17. The system of claim 11 characterized in that the document processor is further operable to group the fixed format elements based on the vertical position of the fixed format elements relative to a reference position within a formula area containing the mathematical formula.

18. The system of claim 11 characterized in that the document processor is further operable to:

detect a line of text aligned with the mathematical formula; and

group the fixed format elements based on the offsets of the fixed format elements relative to the position of the line of text.

19. A hardware computer storage media containing computer executable instructions which, when executed by a computer, perform a method of converting a fixed format document containing a mathematical formula into a flow format document, the method comprising the acts of:

opening the fixed format document containing the mathematical formula;

detecting a formula seed of a formula in data parsed from a page of the fixed format document, wherein the formula seed comprises a text element that carries an indication of being part of the mathematical formula;

creating a formula area bounding the detected formula seed;

expanding the formula area to include one or more mathematical elements that are detected on the page based on a proximity to the detected formula seed, wherein together the detected formula seed and the included one or more mathematical elements comprise a plurality of captured elements;

placing the plurality of captured elements into one or more groups based on a vertical position of the plurality of captured elements relative to a line of normal text that overlaps the formula area;

creating a new formula area around each of the one or more groups;

splitting each new formula area based on a horizontal spacing between the captured elements in the new formula area;

selecting a set of split formula area based on an overlap of the split formula areas; and

merging the split formula areas within the set into a single formula for display on a single line of a page of a flow format document.

20. The hardware computer storage media of claim 19 characterized in that the act of detecting fixed format elements corresponding to the mathematical formula further comprises the acts of:

detecting at least one of a math symbol, a math operator, a math keyword, and a math font in the fixed format document; and

identifying the fixed format elements proximate to at least one of a math symbol, a math operator, and a math keyword in the fixed format document as being within a formula area; and

identifying the fixed format elements rendered in the mathematical font as being within the formula area.

21. The hardware computer storage media of claim 20 characterized in that the act of detecting the fixed format elements corresponding to the mathematical formula further comprises the act of identifying the fixed format elements in the formula area that are at least partially horizontally aligned with another fixed format element in the formula area as corresponding to the mathematical formula.