Freeform digital ink annotation recognition

• US 7,574,048 B2
• Filed: 09/03/2004
• Issued: 08/11/2009
• Est. Priority Date: 09/03/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wei, Zile, Shilman, Michael, Bargeron, David M.
• Primary Examiner(s): Le; Brian Q
• Assistant Examiner(s): Park; Edward
• Application Number:
  US10/934,306
• Publication Number:
  US 20060050969A1
• Time in Patent Office: 1,803 Days
• Field of Search: 382/187
• US Class Current: 382/187
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/171 by use of digital ink
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/1444 Selective acquisition, locating or processing of specific regions, e.g. highlighted text, fiducial marks or predetermined fields

Abstract

The present invention leverages classification type detectors and/or context information to provide a systematic means to recognize and anchor annotation strokes, providing reflowable digital annotations. This allows annotations in digital documents to be archived, shared, searched, and easily manipulated. In one instance of the present invention, an annotation recognition method obtains an input of strokes that are grouped, classified, and anchored to underlying text and/or points in a document. Additional instances of the present invention utilize linguistic content, domain specific information, anchor context, and document context to facilitate in correctly recognizing an annotation.

Claims

1. A computer-implemented system that facilitates recognition, comprising:

at least one processor configured to execute the following computer-executable components;

a component that receives at least one input containing digital ink strokes;

a computer-executable recognition component that identifies and groups at least a subset of the digital ink strokes from the input into at least one recognized annotation;

a computer-executable classification component executing from a computer memory employing at least one type detector that classifies the recognized annotation into at least one type of a group of extensible types, the at least one type detector determines a best idealized version of the subset of the digital ink strokes of the at least one recognized annotation determined according to the at least one type using stroke features that capture similarity of the subset of the digital ink strokes with an idealized version of an annotation associated with the at least one type detector;

a resolution component that facilitates the recognition of the subset of the digital ink strokes by maximizing a number of explained strokes, maximizing an overall confidence, and minimizing a number of hypotheses for the input, the resolution component optimizes recognition of the annotation via employment of an energy function given by;

$\begin{array}{c}E=<br><br>\underset{i}{\sum <br><br>}<br><br>{\mathrm{confidence}}_i+\mathrm{\alpha <br><br>}<br><br><br><br>\mathrm{explained}<br><br><br><br>\mathrm{strokes}<br><br>-\\ <br><br>\mathrm{\beta <br><br>}<br><br><br><br>\mathrm{hypotheses}<br><br>\end{array}$

where α and

β

are empirically-determined weights.

2. The computer-implemented system of claim 1, the computer-executable recognition component recognizes the annotation in real-time.

3. The computer-implemented system of claim 1, the computer-executable recognition component employs background processes to obtain the recognized annotation.

4. The computer-implemented system of claim 1, the at least one type detector includes at least one of a horizontal range type detector, a vertical range type detector, a connector type detector, a symbol type detector, a writing type detector, a drawing type detector, or a container type detector.

5. The computer-implemented system of claim 1 further comprising an anchoring component that anchors the annotation to an appropriate portion of the input.

6. The computer-implemented system of claim 5 further comprising a reflow component that employs annotation anchor points to automatically and logically reflow an annotation when the input is manipulated.

7. The computer-implemented system of claim 1, the input further comprising a document context relating to the digital ink strokes.

8. The computer-implemented system of claim 7, the at least one type detector compares the fit of the best idealized version of the at least a subset of the digital ink strokes with the document context using context features to facilitate in recognizing at least one annotation.

9. The computer-implemented system of claim 7, the document context comprising a tree structure.

10. The computer-implemented system of claim 1, the computer-executable recognition component further provides an annotation indicator for the recognized annotation to identify a recognized annotation location when the input is summarized.

11. The computer-implemented system of claim 1 further comprising a linguistic analysis component that employs a linguistic context of the input to facilitate the computer-executable recognition component in proper recognition of at least one annotation.

12. The computer-implemented system of claim 1, the computer-executable recognition component further employs domain specific information to facilitate in determining at least one recognized annotation.

13. The computer-implemented system of claim 12, the domain specific information comprising at least one selected from the group consisting of user specific information, professional genre information, and annotation guideline information.

14. The computer-implemented system of claim 1 further comprising an action determination component that determines at least one action indicated by the recognized annotation, the action comprising one of performing deletions in, capitalizing, changing, or adding to at least a portion of the input other than the digital ink strokes.

15. The computer-implemented system of claim 1, the resolution component further employs dynamic program to facilitate in a resolution of the energy function.

16. A computer readable medium having stored thereon computer executable instructions for implementing components of the computer-implemented system of claim 1.

17. A method for facilitating computer-implemented recognition, comprising:

employing a processor to execute computer executable instructions stored in memory to perform the following acts;

receiving at least one input containing digital ink strokes;

identifying and grouping at least a subset of the digital ink strokes from the input into at least one recognized annotation;

classifying the recognized annotation into at least one type of a group of extensible types based in part on the output of at least one computer-executable type detector;

determining with the at least one computer-executable type detector a best idealized version of the subset of the digital ink strokes of the at least one recognized annotation, the best idealized version is determined according to the at least one type using stroke features that determine similarity of the subset of the digital ink strokes of the at least one recognized annotation to an idealized version of an annotation associated with the at least one computer executable type detector;

recognizing the annotation associated with the subset of the digital ink strokes by maximizing a number of explained strokes, maximizing an overall confidence, and minimizing a number of hypotheses for the input, wherein the recognition of the annotation is optimized via employment of an energy function given by;

$E=\underset{i}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{confidence}}_i+\mathrm{\alpha <br><br>}<br><br><br><br><br><br>\mathrm{explained}<br><br><br><br>\mathrm{strokes}<br><br>-\mathrm{\beta <br><br>}<br><br><br><br><br><br>\mathrm{hypotheses}<br><br>$

where α and

β

are empirically-determined weights.

18. The method of claim 17, the identifying and grouping of the subset of the digital ink strokes to form a recognized annotation occurring in real-time.

19. The method of claim 17, the group of extensible types including at least one selected from the group consisting of horizontal range type, vertical range type, container type, connector type, symbol type, writing type, or drawing type.

20. The method of claim 17, the computer-executable type detector comprising at least one selected from the group consisting of horizontal range type detector, vertical range type detector, container type detector, connector type detector, symbol type detector, writing type detector, and drawing type detector.

21. The method of claim 17 further comprising:

employing machine learning to facilitate in classifying the annotation.

22. The method of claim 17 further comprising:

anchoring the annotation to an appropriate portion of the input.

23. The method of claim 22 further comprising:

employing an annotation anchor point to automatically and logically reflow an annotation when the input is manipulated.

24. The method of claim 17, the input comprising at least one selected from the group consisting of digital information from a digital writing device and digital information from a scanned input.

25. The method of claim 17, the input further comprising a document context relating to the digital ink strokes.

26. The method of claim 25 further comprising:

comparing the fit of the best idealized version of the at least a subset of the digital ink strokes with the document context using context features to facilitate in recognizing at least one annotation.

27. The method of claim 25, the document context comprising a tree structure.

28. The method of claim 17 further comprising:

providing an annotation indicator for the recognized annotation to identify a recognized annotation location when the input is summarized.

29. The method of claim 17 further comprising:

employing a linguistic context of the input to facilitate in proper recognition of at least one annotation.

30. The method of claim 17 further comprising:

utilizing domain specific information to facilitate in determining at least one recognized annotation.

31. The method of claim 30, the domain specific information comprising at least one selected from the group consisting of architectural diagrams and geographic maps.

32. The method of claim 17 further comprising:

recognizing annotations on at least one media type selected from the group consisting of a typewritten text, a photographic image, a geometric vector graphics image, a digital ink handwriting, and a digital ink drawing.

33. The method of claim 17 further comprising:

determining at least one action indicated by the recognized annotation.

34. The method of claim 17 further comprising:

employing a plurality of candidate annotations to facilitate in recognizing an annotation.

35. The method of claim 17 further comprising:

utilizing one or more of a stylistic or non-stylistic characteristic of the digital ink strokes to facilitate in recognizing the annotation.

36. The method of claim 35, the stylistic characteristic comprising at least one selected from the group consisting of a color of a digital ink stroke, a thickness of a digital ink stroke, a pen tip style employed to create a digital ink stroke, a transparency level of a digital ink stroke, and a viscosity level of a digital ink stroke.

37. The method of claim 35, the non-stylistic characteristic comprising at least one selected from the group consisting of a timestamp on a digital ink stroke and a serial number on a pen tip cursor utilized to create a digital ink stroke.

38. The method of claim 17 further comprising:

providing searchable recognized annotations based, at least in part, on digital ink strokes.

39. The method of claim 17 further comprising:

utilizing dynamic programming to facilitate in a resolution of the energy function.

40. A device employing the method of claim 17 comprising at least one selected from the group consisting of a computer, a server, and a handheld electronic device.

41. A system that facilitates recognition, comprising:

means for receiving at least one input containing digital ink strokes;

means for storing the received input;

means for identifying and grouping at least a subset of the digital ink strokes from the input into at least one recognized annotation by maximizing a number of explained strokes, maximizing an overall confidence, and minimizing a number of hypotheses for the input, wherein the recognition of the annotation is optimized via employment of an energy function given by;

$E=\underset{i}{\overset{}{\sum <br><br>}}<br><br><br><br>{\mathrm{confidence}}_i+\mathrm{\alpha <br><br>}<br><br><br><br><br><br>\mathrm{explained}<br><br><br><br>\mathrm{strokes}<br><br>-\mathrm{\beta <br><br>}<br><br><br><br><br><br>\mathrm{hypotheses}<br><br>$

where α and

β

are empirically-determined weights;

means for classifying the recognized annotation into at least one type of a group of extensible types based in part on the output of at least one type detector;

means for determining a best idealized version of the at least a subset of the digital ink strokes of the at least one recognized annotation according to the at least one type using stroke features of the at least a subset of the digital ink strokes that facilitate in determining similarity of the best idealized version to an idealized version of an annotation associated with the at least one type detector; and

means for comparing the fit of the best idealized version of the at least a subset of the digital ink strokes with contextual features associated with the at least one input.