Grouping writing regions of digital ink

• US 20080260241A1
• Filed: 04/20/2007
• Published: 10/23/2008
• Est. Priority Date: 04/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ye, Ming, Sutanto, Herry, Raghupathy, Sashi
• Granted Patent: US 8,407,589 B2
• Time in Patent Office: Days
• US Class Current: 382/159
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 40/171 by use of digital ink
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction
• 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 method for grouping writing regions of digital ink receives processed digital ink that comprises writing regions. A relationship can be generated between a plurality of the writing regions. A feature set can be determined that is associated with the plurality of the writing regions. The plurality of the writing regions can be grouped based on the feature set.

Claims

1. A computer-implemented method for grouping writing regions of digital ink, said method comprising:

receiving processed digital ink that comprises writing regions;

generating a relationship between a plurality of said writing regions;

determining a feature set associated with said plurality of said writing regions; and

grouping said plurality of said writing regions based on said feature set.

2. The computer-implemented method as recited in claim 1, wherein said feature set is selected from the group consisting of a distance between said plurality of said writing regions, a measure of presence of an object located between said plurality of said writing regions, an angle difference between said plurality of said writing regions, a horizontal relationship of said plurality of said writing regions, a vertical relationship of said plurality of said writing regions, a temporal relationship between said plurality of said writing regions, a line count of each of said plurality of said writing regions, a combined width of said plurality of said writing regions, a width of each of said plurality of said writing regions, and a measure of presence of a drawing of said processed digital ink that contains said plurality of said writing regions.

3. The computer-implemented method as recited in claim 1, wherein said grouping comprises:

utilizing a machine learning technique.

4. The computer-implemented method as recited in claim 3, wherein said machine learning technique is selected from the group consisting of a decision tree, an AdaBoost decision tree, a neural network, a support vector machine, and a machine learning classification technique.

5. The computer-implemented method as recited in claim 1, wherein said generating comprises:

generating a neighborhood graph.

6. The computer-implemented method as recited in claim 1, further comprising:

generating an alternative hypothesis related to said plurality of said writing regions

7. The computer-implemented method as recited in claim 1, further comprising:

grouping a digital typed text with said grouped plurality of said writing regions.

8. A computer-readable medium having computer-executable instructions for performing a method for grouping writing regions of digital ink, said instructions comprising:

constructing a neighborhood graph utilizing a plurality of writing regions, said writing regions are formed from digital ink;

determining a characteristic associated with a pair of writing regions of said plurality of writing regions; and

utilizing said characteristic to determine whether to merge said pair of writing regions.

9. The computer-readable medium of claim 8, further comprising computer-executable instructions for:

generating a merge hypothesis based on said characteristic.

10. The computer-readable medium of claim 8, wherein said computer-executable instructions for performing said utilizing said characteristic further comprises computer executable instructions for:

utilizing a machine learning technique.

11. The computer-readable medium of claim 8, wherein said digital ink comprises a digital ink stroke that originated in real-time.

12. The computer-readable medium of claim 8, further comprising computer-executable instructions for:

merging said pair of writing regions to produce a new writing region.

13. The computer-readable medium of claim 12, further comprising computer-executable instructions for:

determining whether to merge said new writing region with typed text.

14. The computer-readable medium of claim 12, further comprising computer-executable instructions for:

determining how to update said new writing region to incorporate an edit of said digital ink.

15. A system for grouping writing regions of digital ink, said system comprising:

a neighborhood graph module configured for receiving processed digital ink that comprises writing regions, said neighborhood graph module configured for constructing a neighborhood graph associated with a plurality of said writing regions;

a feature extractor module coupled with said neighborhood graph module, said feature extractor module configured for receiving said neighborhood graph and configured for utilizing said neighborhood graph to determine a feature set associated with a pair of said writing regions; and

a classifier module coupled to said feature extractor module, said classifier module configured for receiving said feature set and configured for determining a merge of said pair of said writing regions using said feature set.

16. The system of claim 15, further comprising:

a hypothesis handling module coupled to said classifier module, said hypothesis handling module configured for receiving a confidence associated with said determining said merge of said pair.

17. The system of claim 16, wherein said hypothesis handling module is further configured for merging said pair of said writing regions to produce a new writing region.

18. The system of claim 15, wherein said classifier module is configured for being programmed with a parameter that was determined utilizing labeled data.

19. The system of claim 15, further comprising:

an initialization module configured for receiving said processed digital ink, said initialization module configured for creating writing regions, said initialization module coupled to output said created writing regions to said neighborhood graph module.

20. The system of claim 15, further comprising:

a hypothesis handling module coupled with said neighborhood graph module and said classifier module, said hypothesis handling module configured for generating and processing alternative grouping hypotheses.