System and method for detecting a hand-drawn object in ink input

• US 7,352,902 B2
• Filed: 05/20/2004
• Issued: 04/01/2008
• Est. Priority Date: 09/24/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Yantao, Wang, Jian
• Primary Examiner(s): Mariam; Daniel
• Application Number:
  US10/850,948
• Publication Number:
  US 20050063594A1
• Time in Patent Office: 1,412 Days
• Field of Search: 382/181, 382186-189, 382202-203, 382/206, 382/209, 382224-225
• US Class Current: 382/206
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A system and method for detection of hand-drawn objects in ink input is provided. A detector may detect a drawing such as a diagram or chart from ink input by detecting closed containers and/or unclosed connectors in the drawing. An efficient grid-based approach may be used for fitting the ink strokes into an image grid with an appropriate size. A flood-fill algorithm may be used to detect the containers and connectors. A time order search may also be performed after a spatial search to handle overlapping of drawing strokes. Finally, content detection may be performed for each detected container. Once any containers and their associated content have been detected in the image grid, connector detection may be performed. By using the present invention, a user may draw diagrams and flow charts freely and without restrictions on the hand-drawn input.

Claims

1. A computer system for detecting a hand-drawn shape, comprising:

a chart detector for receiving ink input, the ink input comprising a hand-drawn shape;

an ink parser operably coupled to the chart detector for parsing the ink input to differentiate writing from drawing within the ink input, and sending the ink input to the chart detector;

a container detector operably coupled to the chart detector for detecting a closed container within the ink input; and

a connector detector operably coupled to the chart detector for detecting a connector within the ink input.

2. The system of claim 1 further comprising a shape recognizer operably coupled to the ink parser for recognizing a hand-drawn shape.

3. The system of claim 2 wherein the shape recognizer comprises a container recognizer operably coupled to the shape recognizer.

4. The system of claim 2 wherein the shape recognizer comprises a connector recognizer operably coupled to the shape recognizer.

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

6. A computer-implemented method for detecting a hand-drawn shape, comprising:

receiving ink input comprising a hand-drawn shape;

parsing the ink input to differentiate writing from drawing within the ink input;

performing container detection for each container within the ink input, the container detection finding strokes within the ink input that belong to a container; and

performing connector detection for each connector within the ink input, the connector detection finding strokes within the ink input which belong to a connector.

7. The method of claim 6 further comprising performing chart detection to identify strokes of a diagram within ink input.

8. The method of claim 6 further comprising performing shape recognition to recognize the shape of each container and each connector detected within the ink input.

9. The method of claim 8 further comprising generating a drawing with each container and each connector recognized within the ink input.

10. The method of claim 6 wherein performing container detection comprises performing a spatial search to detect containers.

11. The method of claim 6 wherein performing container detection comprises generating an image grid and positioning strokes from the input ink on the generated image grid.

12. The method of claim 6 wherein performing container detection comprises marking grids of an image grid that are intersected by strokes of the ink input positioned on the image grid.

13. The method of claim 6 wherein performing container detection comprises flood-filling outmost blank grids of an image grid until reaching marked grids that intersect with strokes of the ink input positioned on the image grid.

14. The method of claim 6 wherein performing container detection comprises flood-filling islands of blank grids of an image grid until reaching marked grids that intersect with strokes of the ink input positioned on the image grid.

15. The method of claim 6 wherein performing container detection comprises checking that container candidates are valid containers.

16. The method of claim 15 wherein checking that container candidates are valid containers comprises checking that all border grids which intersect with strokes of the container candidate positioned on an image grid are adjacent to flood-filled island grids.

17. The method of claim 15 wherein checking that container candidates are valid containers comprises removing any strokes of a container candidate positioned on an image grid that do not intersect a border grid in the image grid.

18. The method of claim 15 wherein checking that container candidates are valid containers comprises determining the container candidates are closed containers.

19. The method of claim 15 wherein checking that container candidates are valid containers comprises separating any drawing strokes that are shared between container candidates.

20. The method of claim 19 wherein separating any drawing strokes comprises computing the average distance of the points of the drawing strokes to the center of each candidate container that shares the drawing strokes and assigning a drawing stroke as belonging to the container candidate with the shortest average distance of the points of the drawing strokes to its center.

21. The method of claim 6 wherein performing container detection comprises performing a time order search to detect containers.

22. The method of claim 21 wherein performing a time order search comprises calculating a valid border ratio defined as a valid border length divided by a total border length, where a border comprises marked grids that intersect with strokes of the ink input positioned on an image grid.

23. The method of claim 21 wherein performing a time order search comprises calculating a valid area ratio defined as a valid region area divided by a total area, where the region area comprises an area within a border of marked grids that intersect with strokes of the ink input positioned on an image grid.

24. The method of claim 21 wherein performing a time order search comprises determining the containers from the strokes of the ink input by calculating the likelihood that a sequence of input strokes forms a container.

25. The method of claim 24 wherein calculating the likelihood that a sequence of input strokes forms a container comprises using dynamic programming to group the input strokes into segments where each segment forms a container.

26. The method of claim 6 wherein performing container detection comprises performing content detection to detect any content belonging to a container.

27. The method of claim 26 wherein performing content detection comprises determining the minimal bounding rectangle surrounding the content and calculating its area.

28. The method of claim 26 wherein performing content detection comprises calculating the intersection area ratio of the minimal bounding rectangle with each intersecting container and choosing the container with the largest intersection area ratio of the minimal bounding rectangle with each intersecting container.

29. The method of claim 6 wherein performing connector detection for each connector within the ink input comprises inflating containers whose borders are not adjacent with a grid intersecting unvisited strokes of the ink input positioned on an image grid.

30. The method of claim 29 wherein inflating containers comprises marking grids surrounding the borders of the containers until reaching a grid intersecting the unvisited strokes.

31. The method of claim 29 wherein inflating containers comprises marking grids surrounding the borders of the containers until reaching a border grid of another container.

32. The method of claim 6 wherein performing connector detection for each connector within the ink input comprises flood-filling grids intersecting unvisited strokes of the ink input positioned on an image grid.

33. The method of claim 6 wherein performing connector detection comprises checking that connector candidates are valid connectors.

34. The method of claim 33 wherein checking that connector candidates are valid connectors comprises verifying that the strokes of the connector candidate connect to a container.

35. The method of claim 33 wherein checking that connector candidates are valid connectors comprises verifying that the number of intersection points of the strokes of a connector candidate does not exceed the number of adjacent containers which the connector candidate may join.

36. The method of claim 35 wherein verifying that the number of intersection points of the strokes of a connector candidate does not exceed the number of adjacent containers which the connector candidate may join comprises using a sliding window that may be moved along the connector candidate.

37. A computer-readable medium having computer-executable instructions for performing the method of claim 6.

38. A computer system for detecting a hand-drawn shape, comprising:

means for receiving ink input comprising a hand-drawn shape;

means for detecting a closed container within the ink input;

means for classifying ellipses and circles;

means for classifying polygons; and

means for detecting a connector within the ink input.