System and method for detecting a list in ink input

• US 20050063591A1
• Filed: 05/20/2004
• Published: 03/24/2005
• Est. Priority Date: 09/24/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Xianfang, Chen, Tongxian, Zou, Yu, Wu, Jiang, Wang, Jian, Lin, Zhouchen
• Granted Patent: US 7,295,708 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06F 40/171 by use of digital ink
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32
• 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 system and method for detection of a list in ink input is provided. A detector is provided that may detect a list such as a bulleted or numbered list of items in ink input. A group of lines may first be selected as a candidate list. Indentation level clustering and bullet detection may then be performed to determine the structure of the list. Bullet detection may be performed by detecting bullet partners, which are pairs of lines at the same indentation level that may begin with bullet candidates with similar features. The features of the bullet candidates in a pair of lines may be used to determine the likelihood of whether the pair of lines may be bullet partners. Finally, the structure of the list may be determined, including the relationship among the list items.

Claims

1. A computer system for detecting a list in ink input, comprising:

a list detector for receiving ink input;

an indentation detector operably coupled to the list detector for detecting an indentation of a handwritten line within ink input; and

a bullet detector operably coupled to the list detector for detecting a bullet in a handwritten line within ink input.

2. The system of claim 1 further comprising an ink parser operably coupled to the list detector for sending ink input to the list detector.

3. The system of claim 1 further comprising a list candidate detector operably coupled to the list detector for selecting a group of lines that may form a list within the ink input.

4. The system of claim 1 further comprising a list structure detector operably coupled to the list detector for providing the structure of a list within the ink input.

5. The system of claim 1 wherein the bullet comprises an alphanumeric bullet.

6. The system of claim 1 wherein the bullet comprises a graphical bullet.

7. A computer-readable medium having computer-executable components comprising the system of claim 1.

8. A method for detecting a list in ink input, comprising:

receiving ink input;

performing list detection for a list within the ink input; and

generating a list structure as output.

9. The method of claim 8 further comprising parsing the ink input to differentiate writing from drawing within the ink input.

10. The method of claim 8 wherein performing list detection comprises performing list candidate identification for selecting a group of lines that may form a list within the ink input.

11. The method of claim 8 wherein performing list detection comprises performing indentation detection for detecting an indentation of a handwritten line within the ink input.

12. The method of claim 8 wherein performing list detection comprises performing bullet detection to identify a bullet in a handwritten line within the ink input.

13. The method of claim 8 wherein performing list detection comprises determining the structure of the list within the ink input.

14. The method of claim 10 wherein performing list candidate identification comprises setting every line within the group of selected lines as a list candidate.

15. The method of claim 14 wherein performing list candidate identification comprises selecting two list candidates for determining whether the two list candidates may be merged.

16. The method of claim 10 wherein performing list candidate identification comprises merging two lines from the group of selected lines to form a list candidate.

17. The method of claim 15 wherein performing list candidate identification comprises merging the two list candidates to form a new list candidate.

18. The method of claim 17 wherein performing list candidate identification comprises merging the new list candidate with another list candidate.

19. The method of claim 11 wherein performing indentation detection comprises indentation level clustering for grouping indentation levels.

20. The method of claim 11 wherein performing indentation detection comprises performing k-mean clustering for grouping indentation levels.

21. The method of claim 11 wherein performing indentation detection comprises determining a distance from an indentation level of a line to an average indentation level.

22. The method of claim 11 wherein performing indentation detection comprises recalculating an average position of an indentation level.

23. The method of claim 12 wherein performing bullet detection comprises selecting the first word of the line in the list as a bullet candidate.

24. The method of claim 12 wherein performing bullet detection comprises performing bullet partner detection for the line.

25. The method of claim 12 wherein performing bullet detection comprises determining whether the line has a neighboring line as a bullet partner in a set of lines at the indentation level of the line and, if so, considering the first word of the line to be a bullet.

26. The method of claim 12 wherein performing bullet detection comprises determining whether the line has a bullet partner and, if not, determining whether a set of lines at an indentation level of the line has a subset of bullet partners.

27. The method of claim 26 further comprising determining whether the ratio of the number of lines in the subset of bullet partners to the number of lines in the indentation level set is higher than a threshold, and if so, considering the first word of the line to be a bullet.

28. The method of claim 26 further comprising determining whether the ratio of the number of lines in the subset of bullet partners to the number of lines in the indentation level set is higher than a threshold, and if not, considering the first word of the line not to be a bullet.

29. The method of claim 24 wherein performing bullet partner detection for the line comprises determining features of the first word in a pair of lines.

30. The method of claim 29 wherein determining features of the first word in the pair of lines comprises determining the differences in the heights and the widths of bounding boxes around the first word in the pair of lines.

31. The method of claim 30 further comprising:

determining the maximum of the widths of the bounding boxes;

determining the difference of the stroke lengths of the first word in the pair of lines; and

determining the distances between each first word and the next word in the pair of lines.

32. The method of claim 29 further comprising determining the likelihood the pair of lines are bullet partners using the features of the first word in the pair of lines.

33. The method of claim 32 further comprising determining whether the likelihood is higher than a threshold, and if so, considering the pair of lines to be bullet partners.

34. The method of claim 13 wherein determining the structure of the list within the ink input comprises identifying list items.

35. The method of claim 13 wherein determining the structure of the list within the ink input comprises determining the relationships among list items.

36. The method of claim 13 wherein determining the structure of the list within the ink input comprises creating the structure of the list.

37. The method of claim 13 wherein determining the structure of the list within the ink input comprises determining from the structure of the list that the list is a valid list.

38. The method of claim 37 wherein a valid list comprises a list with at least two bullets.

39. A computer-readable medium having computer-executable instructions for performing the method of claim 8.

40. A computer system for detecting a list in ink input, comprising:

means for receiving ink input;

means for performing list detection for a list within the ink input; and

means for generating a list structure as output.