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

• US 7,440,616 B2
• Filed: 03/23/2005
• Issued: 10/21/2008
• Est. Priority Date: 09/21/2004
• Status: Expired due to Fees

• 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/088,618
• Publication Number:
  US 20060062463A1
• Time in Patent Office: 1,308 Days
• Field of Search: 382/181, 382185-189, 382/203, 382/209, 382/218, 382/224, 382/225, 382/199, 382/284
• 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
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

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 chart recognizer for recognizing a hand-drawn chart from closed containers and unclosed connectors recognized in ink input, wherein closed containers are formed from closed boundaries;

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

a connected container recognizer operably coupled to the chart recognizer for recognizing a hand-drawn chart having connected containers, wherein the connected containers are recognized when the connected containers partially overlap such that boundaries of the connected containers intersect and such that a first portion of each of the connected containers is enclosed within at least one of the other connected containers while a second portion of each of the connected containers remains outside of the at least one of the other connected containers.

2. The system of claim 1 further comprising a curve recognizer operably coupled to the chart recognizer for recognizing a hand-drawn chart having a curve.

3. The system of claim 1 further comprising a chart detector operably coupled to the chart 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.

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

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

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

7. The system of claim 5 wherein the shape recognizer comprises a connector recognizer operably coupled to the shape recognizer.

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

9. 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, wherein performing container detection for each container within the ink input includes at least;

performing connected container recognition that includes determining that at least two connected containers have boundaries which intersect, such that at least a first connected container and a second connected container only partially overlap to thereby forming an overlapping portion common to each of the first and second connected containers, while each of the first and second connected containers includes an additional portion not common to the other connected container;

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

performing chart recognition for containers recognized within the ink input.

10. The method of claim 9 further comprising performing shape recognition for each connector detected within the ink input.

11. The method of claim 10 further comprising performing chart recognition for containers and connectors recognized within the ink input.

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

13. The method of claim 9 wherein performing chart recognition comprises performing connectivity-based recognition to recognize a hand-drawn chart having connected areas.

14. The method of claim 9 wherein performing chart recognition comprises performing connected container recognition to recognize a hand-drawn chart having connected containers.

15. The method of claim 14 wherein performing connected container recognition to recognize a hand-drawn chart having connected containers comprises performing connected container recognition to recognize a hand-drawn chart having intersecting containers.

16. The method of claim 14 wherein performing connected container recognition to recognize a hand-drawn chart having connected containers comprises performing connected container recognition to recognize a hand-drawn chart having a container included entirely within another container.

17. The method of claim 9 wherein performing chart recognition comprises performing curve recognition to recognize a hand-drawn chart having a curve.

18. The method of claim 17 wherein performing curve recognition to recognize a hand-drawn chart having a curve comprises performing curve recognition to recognize a hand-drawn chart having a line.

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

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

an ink input reception mechanism for receiving a hand-drawn diagram;

a container detector for detection of each container within the ink input;

a connector detector for detection of each connector within the ink input;

a connected container recognizer, wherein the connected container recognizer is configured to recognize at least partially overlapping hand-drawn containers in which boundaries defining closed containers intersect and such that a portion of each overlapping closed container is in common with at least one other overlapping closed container while a portion of each overlapping closed container is also not in common to the same overlapping closed container sharing the overlapping portion;

a shape recognizer for recognition of each container and each connector detected within the ink input; and

a chart recognizer for recognition for containers and connectors recognized within the ink input, wherein the chart recognizer includes at least;

means for recognizing a hand-drawn Venn diagram.

21. The system of claim 20, wherein the means for recognizing a hand-drawn Venn diagram is configured to perform a method comprising:

for each container in the diagram, group the container into a cluster with all other containers that intersect with the container;

for each cluster, determine whether the cluster includes more than two containers;

for each cluster determined to include more than two containers;

compare a first ratio to a first threshold, wherein the first ratio is between a size of a largest container in the cluster and a smallest ratio in the cluster;

determine a distance between a center of each container in the cluster and a barycenter of the diagram, and determine a maximum distance and minimum distance;

compare a second ratio to a second threshold, wherein the second ratio is between the maximum distance and the minimum distance;

sort each container in the cluster clockwise around the barycenter; and

determine whether each container in the cluster intersects a previous container and a subsequent container.