System and method for detecting a list in ink input

• US 7,295,708 B2
• Filed: 05/20/2004
• Issued: 11/13/2007
• Est. Priority Date: 09/24/2003
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Mariam; Daniel
• Application Number:
  US10/850,680
• Publication Number:
  US 20050063591A1
• Time in Patent Office: 1,272 Days
• Field of Search: 382/173, 382/176, 382/181, 382186-187, 382224-225, 715517-518, 715530-531
• 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 method for detecting a list in ink input, comprising:

receiving ink input;

performing list detection for a list within the ink input by at least performing list candidate identification for selecting a group of lines that may form a list within the ink input and setting a plurality of lines within the group of selected lines as candidates and selecting two list candidates for determining whether the two list candidates may be merged; and

generating a list structure as output.

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

a processor; and

system memory having computer-executable instructions and modules for implementing the method recited in claim 1, wherein the modules include;

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.

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

4. The system of claim 2 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.

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

6. The system of claim 2 wherein the bullet comprises an alphanumeric bullet.

7. The system of claim 2 wherein the bullet comprises a graphical bullet.

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

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

10. The method of claim 9 wherein performing indentation detection comprises indentation level clustering for grouping indentation levels.

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

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

13. The method of claim 12 wherein performing indentation detection comprises recalculating an average position of an indentation level.

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

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

16. The method of claim 14 wherein performing bullet detection comprises performing bullet partner detection for the line.

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

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

19. The method of claim 18 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.

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

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

22. The method of claim 14 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.

23. The method of claim 14 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.

24. The method of claim 23 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.

25. The method of claim 23 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.

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

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

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

29. The method of claim 26 wherein determining the structure of the list within the ink input comprises creating the structure of the list.

30. The method of claim 26 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.

31. The method of claim 30 wherein a valid list comprises a list with at least two bullets.

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

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

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

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

36. A computer-readable storage medium having stored computer-executable instructions for performing the method of claim 1.

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

receiving ink input;

performing list detection for a list within the ink input by at least performing indentation detection for detecting an indentation of a handwritten line within the ink input, and wherein performing indentation detection comprises indentation level clustering for grouping indentation levels; and

generating a list structure as output.

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

receiving ink input;

performing list detection for a list within the ink input by at least performing bullet detection to identify a bullet in a handwritten line within the ink input and 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; and

generating a list structure as output.

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

receiving ink input;

performing list detection for a list within the ink input by at least performing bullet detection to identify a bullet in each of a pair of handwritten lines within the ink input by determining features of the first word in the pair of lines and by determining the likelihood the pair of lines are bullet partners using the features of the first word in the pair of lines; and

generating a list structure as output.