System and method for shape recognition of hand-drawn objects

• US 7,324,691 B2
• Filed: 05/20/2004
• Issued: 01/29/2008
• Est. Priority Date: 09/24/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Xu, Xun, Li, Yantao, Wang, Jian, Lin, Zhouchen
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US10/850,718
• Publication Number:
  US 20050063592A1
• Time in Patent Office: 1,349 Days
• Field of Search: 382/181, 382185-189, 382/203, 382/209, 382/218, 382/224, 382/225
• 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 from a user, a hand-drawn ink input representing a diagram, flow chart, or both;

a container recognizer operably coupled to the shape recognizer for performing container recognition that identifies a plurality of closed containers within ink input; and

a connector recognizer operably coupled to the shape recognizer for identifying a connector within ink input that connects the plurality of closed containers, wherein the identifying of the connector includes identifying a skeleton stroke, an arrowhead stroke, or both, by breaking the connector into pieces at cusps, which are points of high curvature within the connector; and

a grouper operably coupled to the shape recognizer for grouping the plurality of containers with the connector by automatically adjusting one or more properties of at least one of the plurality of containers, the connector, or both, such that the plurality of containers and the connector are considered joined, thus allowing the user to create the diagram, flow chart, or both without concern for a stroke input order, a number of strokes used, or both.

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 at least one of the plurality of closed containers comprises a circle.

13. The system of claim 1 wherein at least one of the plurality of closed containers comprises an ellipse.

14. The system of claim 1 wherein at least one of the plurality of closed containers comprises a triangle.

15. The system of claim 1 wherein at least one of the plurality of closed containers 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 at least one of the plurality of containers 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 from a user, a hand-drawn ink input representing a diagram, flow chart, or both;

performing container recognition for identifying a plurality of containers within the ink input;

performing connector recognition for identifying at least one connector within the ink input for connecting the plurality of containers, wherein the identifying of the connector includes identifying a skeleton stroke, an arrowhead stroke, or both, by breaking the connector into pieces at cusps, which are points of high curvature within the connector; and

grouping the plurality of containers with the connector by automatically adjusting one or more properties of at least one of the plurality of containers, the connector, or both, such that the plurality of containers and the connector are considered joined, thus allowing the user to create the diagram, flow chart, or both without concern for a stroke input order, a number of strokes used, or both.

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 of the plurality of containers and the 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 26 wherein performing ellipse/circle recognition comprises determining a minimum bounding rectangle around strokes of the container.

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

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

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

31. The method of claim 29 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.

32. The method of claim 29 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.

33. The method of claim 29 wherein performing polygon recognition comprises refining edges of a recognized polygon.

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

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

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

37. 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.

38. The method of claim 21 wherein the properties are chosen from a type, location, orientation, shape, or size of the container, connector, or both.

39. The method of claim 21 wherein a cusp is identified by determining an angle for a non-ending point, which is a two line segment within the connector.

40. The method of claim 39 wherein the connector is broken into pieces when the angle for the non-ending point is less than some predefined threshold.

41. The method of claim 21 wherein the connector is smoothed prior to breaking the connector into pieces in order to avoid breaking the connector into too many meaningless pieces.

42. The method of claim 21 wherein the breaking of the connector into pieces is used to identify a skeleton stroke of the connector from an arrowhead stroke of the connector.

43. The method of claim 42 wherein the arrowhead stroke of the connector is identified by determining that a broken piece of the connector is a size less than a predetermined empirical threshold.

44. The method of claim 43 wherein the arrowhead stroke of the connector is also identified by determining that a distance to a point where the arrowhead stroke was broken from the skeleton of the connector is less than some predetermined threshold.

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

receiving a hand-drawn ink input;

performing container recognition for each container within the ink input, the container recognition comprising at least one of performing ellipse/circle recognition or performing polygon recognition, wherein the performing ellipse/circle recognition comprises determining a minimum bounding rectangle around strokes of the container and scaling the strokes to make the minimum bounding rectangle become a square, and wherein the performing polygon recognition comprises determining a maximal inscribed polygon within a convex hull around strokes of the container; and

performing connector recognition for each connector within the ink input.