Application of grammatical parsing to visual recognition tasks

• US 20060280370A1
• Filed: 06/13/2005
• Published: 12/14/2006
• 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.
• Granted Patent: US 7,639,881 B2
• Time in Patent Office: Days
• US Class Current: 382/229
• 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 system that facilitates recognition, 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.

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 a constellation of integral images to facilitate in parsing the input.

7. 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.

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

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

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

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

12. A method for facilitating recognition, comprising:

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

utilizing image recognition to facilitate in grammatically parsing the input.

13. The method of claim 12 further comprising:

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

14. The method of claim 12 further comprising:

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

15. The method of claim 12 further comprising:

utilizing a constellation of integral images to facilitate in parsing the input.

16. The method of claim 12 further comprising:

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

17. The method of claim 12 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.

18. The method of claim 12, the grammatical parsing process based on a discriminative grammatical model.

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

20. A system that facilitates recognition, 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 to facilitate in a parsing process.