Grouping writing regions of digital ink

• US 9,317,492 B2
• Filed: 03/11/2013
• Issued: 04/19/2016
• Est. Priority Date: 04/20/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ye, Ming, Sutanto, Herry, Raghupathy, Sashi
• Primary Examiner(s): Dyer, Andrew
• Application Number:
  US13/793,077
• Publication Number:
  US 20140095992A1
• Time in Patent Office: 1,135 Days
• Field of Search: 715/262, 715/263, 715/268
• US Class Current: 1/1
• 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 system, comprising:

one or more processors; and

memory comprising instructions that when executed by at least one of the one or more processors perform a method for grouping writing regions of digital ink, the method comprising;

applying a prune-and-clone technique to digital ink to generate pruned digital ink by deep-copying at least a first structure and leaving at least a second structure as a shadow, wherein deep-copying the first structure includes copying ink stroke data of the first structure, wherein leaving the second structure as a shadow includes avoiding copying ink stroke data of the second structure, and wherein applying the prune-and-clone technique sets an upper-bound on an amount of structures entering a parser of digital ink by excluding shadowed structures from entering the parser;

determining a first writing region of the pruned digital ink and a second writing region of the pruned digital ink; and

determining whether to group the first writing region with the second writing region.

2. The system of claim 1, at least one of the first writing region or the second writing region comprising digital ink based upon input from a touch of a user.

3. The system of claim 1, at least one of the first writing region or the second writing region comprising digital ink based upon input from a stylus.

4. The system of claim 1, at least one of the first writing region or the second writing region comprising digital ink based upon input received via a digitizer.

5. The system of claim 1, the determining whether to group comprising determining a user intent to group the first writing region with the second writing region.

6. The system of claim 1, the determining whether to group the first writing region with the second writing region comprising using at least one of a decision tree, a neural network or a support vector machine.

7. A method comprising:

applying a prune-and-clone technique to digital ink to generate pruned digital ink by deep-copying at least a first structure and leaving at least a second structure as a shadow, wherein deep-copying the first structure includes copying ink stroke data of the first structure, wherein leaving the second structure as a shadow includes avoiding copying ink stroke data of the second structure, and wherein applying the prune-and-clone technique sets an upper-bound on an amount of structures entering a parser of digital ink by excluding shadowed structures from entering the parser;

determining a first writing region of the pruned digital ink and a second writing region of the pruned digital ink; and

determining whether to group the first writing region with the second writing region.

8. The method of claim 7, further comprising caching a time signature for at least one region.

9. The method of claim 8, further comprising calculating whether a shadow region and an ink line are adjacent in time based on the cached time signature.

10. The method of claim 7, further comprising merging tentative regions which contain at least one shadow segment produced by applying the prune-and-clone technique.

11. The method of claim 7, wherein the method treats typed text and digital ink lines homogeneously with regard to whether applications can request that regions are not to be split or merged.

12. The method of claim 7, wherein instances of determining whether to group writing regions occur during incremental sessions, and the instances process incremental changes that a user has made to a document.

13. The method of claim 7, wherein determining whether to group the first writing region with the second writing region comprises producing a merge versus no-merge decision and an associate confidence.

14. The method of claim 13, wherein producing the merge versus no-merge decision and associate confidence comprises determining whether there is a drawing structure lying between the writing regions.

15. A computer readable memory comprising at least one of the following:

a compact disc, a DVD, a magnetic disk, an optical disk, a random access memory, a flash drive, a register, a read only memory, a non-volatile memory, a disk drive, the computer readable memory further comprising instructions that when executed, perform an incremental method for grouping writing regions of digital ink, the method comprising;

applying a prune-and-clone technique to digital ink to generate pruned digital ink by deep-copying at least a first structure and leaving at least a second structure as a shadow, wherein deep-copying the first structure includes copying ink stroke data of the first structure, wherein leaving the second structure as a shadow includes avoiding copying ink stroke data of the second structure, and wherein applying the prune-and-clone technique sets an upper-bound on an amount of structures entering a parser of digital ink by excluding shadowed structures from entering the parser;

determining a first writing region of the pruned digital ink and a second writing region of the pruned digital ink; and

determining whether to group the first writing region with the second writing region, wherein instances of determining whether to group writing regions occur during incremental sessions, and the instances process incremental changes that a user has made to a document.

16. The computer readable memory of claim 15, wherein at least one of the first writing region or the second writing region comprise digital ink based upon input from at least one of the following:

a touch of a user, input from a stylus, or input received via a digitizer.

17. The computer readable memory of claim 15, wherein determining whether to group the first writing region with the second writing region comprises using at least one of the following:

an AdaBoost decision tree, a Hidden Markov Model technique, or a machine learning-based classification technique.

18. The computer readable memory of claim 15, wherein determining whether to group the first writing region with the second writing region comprises maintaining merge hypotheses which are sorted by their confidences.

19. The computer readable memory of claim 18, wherein the method comprises producing confidences based at least in part on determining at least one of the following:

a vertical distance between the writing regions, or whether there is a drawing structure lying between the writing regions.

20. The computer readable memory of claim 15, wherein the method provides text-centric support instead of treating typed text and digital ink lines homogeneously, the text-centric treatment permitting applications to request that typed text regions are not to be split or merged.