System and method for connectivity-based recognition of a hand-drawn chart in ink input

• US 7,409,088 B2
• Filed: 03/23/2005
• Issued: 08/05/2008
• Est. Priority Date: 09/21/2004
• 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 G
• Application Number:
  US11/089,288
• Publication Number:
  US 20060062465A1
• Time in Patent Office: 1,231 Days
• Field of Search: 382/181, 382185-189, 382/203, 382/209, 382/218, 382224-226, 382/199
• US Class Current: 382/186
• 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 recognition of hand-drawn charts in ink input is provided. A chart recognizer may be provided that may recognize a hand-drawn diagram or chart in ink input. The chart recognizer may include a connectivity-based recognizer for recognizing a hand-drawn chart having connected areas such as a pie chart, a connected container recognizer for recognizing a hand-drawn chart having connected containers such as a cycle diagram, and a curve recognizer for recognizing a hand-drawn chart having a curve. The connected container recognizer may also recognize a hand-drawn chart having intersecting containers such as a Venn diagram or a hand-drawn chart having a container that may include another container such as a target diagram.

Claims

1. A computer system for recognizing a hand-drawn chart in ink input, comprising:

a connectivity-based recognizer for recognizing a hand-drawn chart from closed containers and unclosed connectors recognized in ink input;

a pie chart recognizer operably coupled to the connectivity-based recognizer for recognizing a hand-drawn pie chart having connected areas;

a bar chart recognizer operably coupled to the connectivity-based recognizer for recognizing a hand-drawn bar chart having connected areas; and

a pyramid diagram recognizer operably coupled to the connectivity-based recognizer for recognizing a hand-drawn pyramid diagram having connected areas.

2. The system of claim 1 further comprising a chart detector operably coupled to the connectivity-based recognizer for receiving ink input, the chart detector comprising a container detector for detecting the closed containers within ink input and a connector detector for detecting the unclosed connectors within ink input.

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

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

5. The system of claim 4 wherein the shape recognizer comprises a container recognizer operably coupled to the shape recognizer.

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

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

8. A method in a computer system for recognizing a hand-drawn chart in ink input, comprising:

receiving ink input;

performing container detection for each container within the ink input;

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

performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas, wherein performing the connectivity-based recognition includes at least one of;

performing pie chart recognition;

or

performing bar chart recognition.

9. The method of claim 8 further comprising generating a drawing for each hand-drawn chart recognized within the ink input.

10. The method of claim 8 further comprising performing content detection for the connected areas of the hand-drawn chart and performing shape refinement of the recognized containers of the hand-drawn chart.

11. The method of claim 8 wherein performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas comprises building a connectivity graph of each connected area detected within the ink input.

12. The method of claim 11 wherein performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas further comprises performing pie chart recognition.

13. The method of claim 12 wherein performing pie chart recognition comprises:

finding the connected areas that share a vertex;

finding edges not shared by the connected areas;

determining that the edges not shared by the connected areas form a recognizable circle; and

determining that the edges from the vertex to the recognizable circle form line segments.

14. The method of claim 11 wherein performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas further comprises performing bar chart recognition.

15. The method of claim 14 wherein performing bar chart recognition comprises:

determining that the connected areas are rectangles;

determining the difference of direction between the rectangular connected areas;

classifying the edges of the rectangular connected areas that are perpendicular to the direction of the rectangular connected areas into two groups; and

determining that the edges in one of the groups form a line segment.

16. The method of claim 11 wherein performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas further comprises performing pyramid diagram recognition.

17. The method of claim 16 wherein performing pyramid diagram recognition comprises:

finding the connected areas of the connectivity graph;

finding edges not shared by the connected areas;

determining that the edges not shared by the connected areas form a recognizable triangle; and

determining that one of the connected areas forms a recognizable triangle and that the other connected areas each form a trapezoid.

18. The method of claim 11 wherein building a connectivity graph comprises:

simplifying polylines of drawing strokes;

merging at least two polylines;

determining an intersection point of polylines;

merging at least two vertices of the polylines; and

mapping the polylines of the drawing strokes to edges of the connectivity graph.

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

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

means for receiving ink input;

means for performing container detection for each container within the ink input;

means for performing shape recognition for each container detected within the ink input;

means for performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas; and

at least one of the following;

means for recognizing a hand-drawn pie chart having connected areas; and

means for recognizing a hand-drawn bar chart having connected areas.

21. A method in a computer system for recognizing a hand-drawn chart in ink input, comprising:

receiving ink input;

performing container detection for each container within the ink input;

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

performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas by at least building a connectivity graph of each connected area detected within the ink input, wherein building the connectivity graph comprises;

simplifying polylines of drawing strokes;

merging at least two polylines;

determining an intersection point of polylines;

merging at least two vertices of the polylines; and

mapping the polylines of the drawing strokes to edges of the connectivity graph.

22. A method in a computer system for recognizing a hand-drawn chart in ink input, comprising:

receiving ink input;

performing container detection for each container within the ink input;

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

performing connectivity-based recognition upon the containers recognized within the ink input for recognition of a hand-drawn chart having connected areas by at least performing pyramid diagram recognition, and wherein performing pyramid diagram recognition comprises;

finding the connected areas of the connectivity graph;

finding edges not shared by the connected areas;

determining that the edges not shared by the connected areas form a recognizable triangle; and

determining that one of the connected areas forms a recognizable triangle and that the other connected areas each form a trapezoid.