Application of grammatical parsing to visual recognition tasks

• US 7,639,881 B2
• Filed: 06/13/2005
• Issued: 12/29/2009
• Est. Priority Date: 06/13/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shilman, Michael, Viola, Paul A.
• Primary Examiner(s): Strege; John B
• Application Number:
  US11/151,708
• Publication Number:
  US 20060280370A1
• Time in Patent Office: 1,660 Days
• Field of Search: 382/226, 382/112, 382/180, 382/181, 382/229, 382/209
• US Class Current: 382/226
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing

Abstract

Image recognition is utilized to facilitate in scoring parse trees for two-dimensional recognition tasks. Trees and subtrees are rendered as images and then utilized to determine parsing scores. Other instances of the subject invention can incorporate additional features such as stroke curvature and/or nearby white space as rendered images as well. Geometric constraints can also be employed to increase performance of a parsing process, substantially improving parsing speed, some even resolvable in polynomial time. Additional performance enhancements can be achieved in yet other instances of the subject invention by employing constellations of integral images and/or integral images of document features.

Claims

1. A computer implemented system including a processor communicatively coupled to a memory that facilitates recognition of 2-dimensional images, comprising:

a receiving component that receives an input associated with a two-dimensional structure; and

a grammar component that utilizes image recognition to facilitate in grammatically parsing the input wherein the grammar component utilizes a constellation of integral images to facilitate in parsing the input, the constellation of integral images representing a physical orientation of features in the input, the physical orientation of the features include at least one of vertical alignment of bounding boxes in the input or horizontal alignment of text lines in the input.

2. The system of claim 1, the grammar component employs the image recognition to facilitate in scoring at least one parse tree and/or subtree associated with the input.

3. The system of claim 1, the grammar component renders at least one tree and/or subtree as an image to facilitate in parsing the input.

4. The system of claim 1, the grammar component renders a stroke curvature and/or a nearby white space as an image to facilitate in parsing the input.

5. The system of claim 1, the grammar component employs at least one geometric constraint to facilitate in parsing the input in polynomial time.

6. The system of claim 1, the grammar component utilizes at least one integral image of at least one feature of the input to facilitate in parsing the input.

7. The system of claim 1, the two-dimensional structure comprising an equation and/or a document layout.

8. The system of claim 1, the grammar component utilizes a grammatical parsing process based on, at least in part, a discriminative grammatical model.

9. The system of claim 1, the grammar component employs at least one classifier to facilitate in recognizing and/or scoring an image.

10. The system of claim 9, the grammar component employs the classifier to facilitate in determining a grammatical cost parse tree and/or a sub-parse tree.

19. The system of claim 1, wherein each of the integral images includes a plurality of pixels, wherein each of integral images stores all values up and to the left of one or more pixels in the corresponding plurality of pixels.

11. A method for facilitating recognition of 2-dimensional images, comprising:

receiving an input associated with a two-dimensional structure; and

utilizing image recognition of at least a constellation of integral images to facilitate in grammatically parsing the input, each of the integral images includes a plurality of pixels, wherein each of integral images stores all values up and to the left of one or more pixels in the corresponding plurality of pixels.

12. The method of claim 11 further comprising:

rendering a stroke curvature and/or a nearby white space as an image to facilitate in parsing the input.

13. The method of claim 11 further comprising:

employing at least one geometric constraint to facilitate in parsing the input in polynomial time.

14. The method of claim 11 further comprising:

employing at least one integral image of at least one feature of the input to facilitate in parsing the input.

15. The method of claim 11 further comprising:

parsing the input based on a grammatical cost function;

the grammatical cost function derived, at least in part, via a machine learning technique that incorporates image recognition to facilitate in determining an optimal parse from a global search.

16. The method of claim 11, the grammatical parsing process based on a discriminative grammatical model.

17. The method of claim 11, the two-dimensional structure comprising an equation and/or a document layout.

20. The method of claim 11, wherein the constellation of integral images representing a physical orientation of features in the input, the physical orientation of the features include at least one of vertical alignment of bounding boxes in the input or horizontal alignment of text lines in the input.

18. A system that facilitates recognition of 2-dimensional images, comprising:

means for receiving an input associated with a two-dimensional structure; and

means for grammatically parsing the input utilizing, at least in part, image recognition of at least a constellation of integral images to facilitate in a parsing process, the constellation of integral images representing a physical orientation of features in the input, the physical orientation of the features include at least one of vertical alignment of bounding boxes in the input or horizontal alignment of text lines in the input.