System and method for shape recognition of hand-drawn objects

• US 20050063592A1
• 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: Li, Yantao, Xu, Xun, Wang, Jian, Lin, Zhouchen
• Granted Patent: US 7,324,691 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• 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/422 Technical drawings; Geographical maps

Abstract

A system and method for shape recognition of hand-drawn objects is provided. A shape recognizer may recognize a drawing such as a diagram or chart from ink input by recognizing closed containers and/or unclosed connectors in the drawing. The closed containers may represent any number of shapes that may be recognized including circles, ellipses, triangles, quadrilaterals, pentagons, hexagons, and so forth. The unclosed connectors may be any type of connector including lines, curves, arrows, and so forth. Polylines may be used to approximate a skeleton of a connector for handling continuation strokes, overlapping strokes and over-tracing strokes of the skeleton. 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 recognizing a hand-drawn shape, comprising:

a shape recognizer for receiving ink input;

a container recognizer operably coupled to the shape recognizer for recognizing a closed container within ink input; and

a connector recognizer operably coupled to the shape recognizer for recognizing a connector within ink input.

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

3. The system of claim 2 further comprising a chart detector operably coupled to the ink parser for grouping drawing strokes.

4. The system of claim 3 wherein the chart detector comprises a container detector operably coupled to the chart detector.

5. The system of claim 3 wherein the chart detector comprises a connector detector operably coupled to the chart detector.

6. The system of claim 1 wherein the container recognizer comprises an ellipse/circle classifier operably coupled to the container recognizer.

7. The system of claim 1 wherein the container recognizer comprises a polygon classifier operably coupled to the container recognizer.

8. The system of claim 1 wherein the container recognizer comprises a triangle classifier operably coupled to the container recognizer.

9. The system of claim 1 wherein the container recognizer comprises a quadrilateral classifier operably coupled to the container recognizer.

10. The system of claim 1 wherein the connector recognizer comprises a skeleton recognizer operably coupled to the connector recognizer.

11. The system of claim 1 wherein the connector recognizer comprises an arrowhead recognizer operably coupled to the connector recognizer.

12. The system of claim 1 wherein the closed container comprises a circle.

13. The system of claim 1 wherein the closed container comprises an ellipse.

14. The system of claim 1 wherein the closed container comprises a triangle.

15. The system of claim 1 wherein the closed container comprises a quadrilateral.

16. The system of claim 1 wherein the connector comprises an arrow.

17. The system of claim 1 wherein the connector comprises a line.

18. The system of claim 1 wherein the connector comprises a curve.

19. The system of claim 1 wherein the container comprises text.

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

21. A method for recognizing a hand-drawn shape, comprising:

receiving ink input;

performing container recognition for each container within the ink input; and

performing connector recognition for each connector within the ink input.

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

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

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

25. The method of claim 21 wherein performing container recognition comprises performing a roundness test.

26. The method of claim 21 wherein performing container recognition comprises performing ellipse/circle recognition.

27. The method of claim 21 wherein performing container recognition comprises performing polygon recognition.

28. The method of claim 21 wherein performing container recognition comprises performing triangle recognition.

29. The method of claim 21 wherein performing container recognition comprises performing quadrilateral recognition.

30. The method of claim 21 wherein performing container recognition comprises calculating a convex hull of strokes belonging to a container.

31. The method of claim 21 wherein performing container recognition comprises calculating a thinness ratio P_ch²/A_ch, where P_ch and A_ch represent a perimeter and an area of a convex hull around strokes of the container.

32. The method of claim 26 wherein performing ellipse/circle recognition comprises determining a minimum bounding rectangle around strokes of the container.

33. The method of claim 32 further comprising scaling the strokes to make the minimum bounding rectangle become a square.

34. The method of claim 27 wherein performing polygon recognition comprises determining a maximal inscribed polygon within a convex hull around strokes of the container.

35. The method of claim 27 wherein performing polygon recognition comprises calculating an area ratio A_n/A_ch, where A_n represents an area of a maximal inscribed n-sided polygon within a convex hull around the strokes of the container and A_ch represents an area of the convex hull around the strokes of the container.

36. The method of claim 27 wherein performing polygon recognition comprises choosing an n-sided polygon with a least number of edges and with an area ratio A_n/A_ch greater than a threshold.

37. The method of claim 27 wherein performing polygon recognition comprises refining edges of a recognized polygon.

38. The method of claim 21 wherein performing connector recognition comprises breaking strokes of the connector into pieces at cusps.

39. The method of claim 21 wherein performing connector recognition comprises classifying skeleton strokes of the connector from arrowhead strokes of the connector.

40. A computer-readable medium having computer-executable instructions for performing the method of claim 21.