Method and tool for recognizing a hand-drawn table

• US 8,634,645 B2
• Filed: 03/28/2008
• Issued: 01/21/2014
• Est. Priority Date: 03/28/2008
• Status: Active Grant

• Current Assignee: Smart Technologies ULC (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Smart Technologies ULC (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Xing, Zhaohui
• Primary Examiner(s): Park, Chan S
• Assistant Examiner(s): Thomas, Mia M
• Application Number:
  US12/058,234
• Publication Number:
  US 20090245645A1
• Time in Patent Office: 2,125 Days
• Field of Search: 382/181, 382/185, 382/186, 382/187, 382/188, 382/189, 382/312, 382/314, 345/156, 345/443
• US Class Current: 382/186
• CPC Class Codes: G06F 40/177 of tables; using ruled lines
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

A computerized method of recognizing an input hand-drawn table formed by freeform line objects comprises transforming each freeform line object of the table into one of a vertical line segment and a horizontal line segment, generating a grid system based on the vertical and horizontal line segments and converting the generated grid system into a table object.

Claims

1. A computerized method of recognizing an input hand-drawn table formed by freeform line objects, said method comprising:

transforming each freeform line object of said table into one of a vertical line segment and a horizontal line segment;

generating a grid system based on the vertical and horizontal line segments; and

converting the generated grid system into a table object,

wherein said transforming comprises, for each freeform line object;

determining the start point and end point of the freeform line object;

generating a temporary line segment extending between the determined start point and end point;

determining the orientation of said temporary line segment;

based on the determined orientation, creating one of said vertical line segment and horizontal line segment;

for each created horizontal line segment, determining whether it overlaps with an existing horizontal line segment and, if so, merging the created and existing horizontal line segments; and

for each created vertical line segment, determining whether it overlaps with an existing vertical line segment and, if so, merging the created and existing vertical line segments,

wherein said transforming further comprises;

comparing each created horizontal line segment with a horizontal line segment list to determine if it overlaps with an existing horizontal line segment;

if not, adding the created horizontal line segment to the list and, if so, performing the merging;

comparing each created vertical line segment with a vertical line segment list to determine if it overlaps with an existing vertical line segment; and

if not, adding the created vertical line segment to the list and, if so, performing the merging, and

wherein said transforming further comprises, prior to said comparing to determine overlap;

examining each horizontal line segment to determine if it is within a threshold vertical distance of an existing horizontal line segment in the horizontal line segment list;

if so, performing said comparing to determine overlap and, if not, bypassing the overlap comparing and adding the horizontal line segment to the list;

examining each vertical line segment to determine if it is within a threshold horizontal distance of an existing vertical line segment in the vertical line segment list; and

if so, performing said comparing to determine overlap and, if not, bypassing the overlap comparing and adding the vertical line segment to the list.

2. The method of claim 1 wherein said grid system is generated based on deemed intersections of the horizontal and vertical line segments.

3. The method of claim 2 wherein said grid system generating comprises:

selecting pairs of adjacent vertical and adjacent horizontal line segments; and

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, determining the intersection points therebetween thereby to yield four corner coordinates of each grid in the grid system.

4. The method of claim 3 wherein said grid system generating comprises:

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, arranging the vertical and horizontal line segments into different combinations, each combination comprising one vertical line segment and one horizontal line segment; and

for each combination, calculating the intersection point between the vertical and horizontal line segments thereby to calculate said corner coordinates.

5. The method of claim 4 further comprising calculating an effective intersection point for each combination of non-intersecting vertical and horizontal line segments that are within a threshold separation distance.

6. The method of claim 3 wherein said converting comprises using the four corner coordinates of each grid to define corners of a corresponding cell of said table object.

7. The method of claim 6 wherein said grid system generating comprises:

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, arranging the vertical and horizontal line segments into different combinations, each combination comprising one vertical line segment and one horizontal line segment; and

for each combination, calculating the intersection point between the vertical and horizontal line segments thereby to calculate said corner coordinates.

8. The method of claim 6 wherein said transforming further comprises:

for each created horizontal line segment, determining whether it overlaps with an existing horizontal line segment and, if so, merging the created and existing horizontal line segments; and

for each created vertical line segment, determining whether it overlaps with an existing vertical line segment and, if so, merging the created and existing vertical line segments.

9. The method of claim 1 further comprising:

detecting input non-freeform line objects that are within the table object; and

inserting the detected non-freeform line objects as table object content.

10. The method of claim 9 wherein during said inserting, each detected non-freeform line object is placed into a corresponding cell of said table object as table cell content.

11. The method of claim 10 wherein said detecting comprises determining non-freeform line objects having designated locations positioned within a cell of the table object.

12. The method of claim 10 further comprising processing the table object based on the table cell content placed in the table object.

13. The method of claim 12, wherein processing the table object comprises:

recognizing the content in a first table cell as a predetermined processing indicator;

processing the content in one or more table cells differing from said first table cell according to the recognized processing indicator; and

replacing the content in said first table cell with the result of the processing.

14. The method of claim 13 wherein the content in the first table cell is a hand-drawn object.

15. The method of claim 14 wherein said processing indicator is a mathematical plus sign and wherein the result of the processing is a summation.

16. A computerized method of recognizing an input hand-drawn table formed by freeform line objects, said method comprising:

transforming each freeform line object of said table into one of a vertical line segment and a horizontal line segment;

generating a grid system based on the vertical and horizontal line segments wherein said grid system is generated based on deemed intersections of the horizontal and vertical line segments;

converting the generated grid system into a table object;

detecting input non-freeform line objects that are within the table object; and

inserting the detected non-freeform line objects as table object content, wherein during said inserting, each detected non-freeform table object is placed into a corresponding cell of said table object as table cell content;

calculating an effective intersection point for each combination of non-intersecting vertical and horizontal line segments that are within a threshold separation distance

wherein said grid system generating comprises;

selecting pairs of adjacent vertical and adjacent horizontal line segments; and

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, determining the intersection points therebetween thereby to yield four corner coordinates of each grid in the grid system

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, arranging the vertical and horizontal line segments into different combinations, each combination comprising one vertical line segment and one horizontal line segment; and

for each combination, calculating the intersection point between the vertical and horizontal line segments thereby to calculate said corner coordinates.

17. The method of claim 16 wherein said transforming comprises for each freeform line object:

examining the orientation of the freeform line object; and

creating one of the horizontal and vertical line segment representing the freeform line object based on the orientation thereof.

18. The method of claim 17 wherein said transforming further comprises for each freeform line object:

determining the start point and end point of the freeform line object;

generating a temporary line segment extending between the determined start point and end point;

determining the orientation of said temporary line segment; and

based on the determined orientation, creating one of said horizontal line segment and vertical line segment.

19. The method of claim 18 wherein said transforming further comprises:

for each created horizontal line segment, determining whether it overlaps with an existing horizontal line segment and, if so, merging the created and existing horizontal line segments; and

for each created vertical line segment, determining whether it overlaps with an existing vertical line segment and, if so, merging the created and existing vertical line segments.

20. The method of claim 19 wherein said grid system is generated based on deemed intersections of the horizontal and vertical line segments.

21. The method of claim 20 wherein said grid system generating comprises:

selecting pairs of adjacent vertical and adjacent horizontal line segments; and

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, determining the intersection points therebetween thereby to yield four corner coordinates of each grid in the grid system.

22. The method of claim 21 wherein said grid system generating comprises:

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, arranging the vertical and horizontal line segments into different combinations, each combination comprising one vertical line segment and one horizontal line segment; and

for each combination, calculating the intersection point between the vertical and horizontal line segments thereby to calculate said corner coordinates.

23. The method of claim 16 wherein said detecting comprises determining non-freeform line objects having designated locations positioned within a cell of the table object.

24. The method of claim 16 further comprising processing the table object based on the table cell content placed in the table object.

25. The method of claim 24 wherein processing the table object comprises:

recognizing the content in a first table cell as a predetermined processing indicator;

processing the content in one or more table cells differing from said first table cell according to the recognized processing indicator; and

replacing the content in said first table cell with the result of the processing.

26. The method of claim 25 wherein the content in the first table cell is a hand-drawn object.

27. The method of claim 26 wherein said processing indicator is a mathematical plus sign and wherein the result of the processing is a summation.

28. The method of claim 16 wherein said converting comprises using the four corner coordinates of each grid to define corners of a corresponding cell of said table object.

29. The method of claim 28 wherein said grid system generating comprises:

for each pair of adjacent vertical line segments and each pair of adjacent horizontal line segments, arranging the vertical and horizontal line segments into different combinations, each combination comprising one vertical line segment and one horizontal line segment; and

for each combination, calculating the intersection point between the vertical and horizontal line segments thereby to calculate said corner coordinates.

30. A non-transitory computer readable medium embodying computer program code for recognizing an input hand-drawn table formed by freeform line objects, said computer program code comprising:

program code for transforming each freeform line object of said table into one of a vertical line segment and a horizontal line segment;

program code for generating a grid system based on the vertical and horizontal line segments; and

program code for converting the generated grid system into a table object, wherein said program code for transforming comprises, for each freeform line object;

program code for determining the start point and end point of the freeform line object;

program code for generating a temporary line segment extending between the determined start point and end point;

program code for determining the orientation of said temporary line segment;

program code for, based on the determined orientation, creating one of said vertical line segment and horizontal line segment;

program code for, for each created horizontal line segment, determining whether it overlaps with an existing horizontal line segment and, if so, merging the created and existing horizontal line segments; and

program code for, for each created vertical line segment, determining whether it overlaps with an existing vertical line segment and, if so, merging the created and existing vertical line segments

wherein the program code for transforming further includes;

program code for comparing each created horizontal line segment with a horizontal line segment list to determine if it overlaps with an existing horizontal line segment;

if not, adding the created horizontal line segment to the list and, if so, performing the merging;

program code for comparing each created vertical line segment with a vertical line segment list to determine if it overlaps with an existing vertical line segment; and

if not, adding the created vertical line segment to the list and, if so, performing the merging, and

wherein said program code for transforming further comprises, prior to said comparing to determine overlap;

program code for examining each horizontal line segment to determine if it is within a threshold vertical distance of an existing horizontal line segment in the horizontal line segment list;

if so, performing said comparing to determine overlap and, if not, bypassing the overlap comparing and adding the horizontal line segment to the list;

program code for examining each vertical line segment to determine if it is within a threshold horizontal distance of an existing vertical line segment in the vertical line segment list; and

if so, performing said comparing to determine overlap and, if not, bypassing the overlap comparing and adding the vertical line segment to the list.

31. An interactive input system comprising:

a coordinate input device having a display surface on which an image is presented, said coordinate input device being responsive to user input; and

processing structure communicating with said coordinate input device and updating the image presented on said display surface to reflect user input, said processing structure executing a table recognition procedure when invoked to recognize a hand-drawn table entered on said coordinate input device and convert the recognized hand-drawn table into a table object, wherein during said hand-drawn table recognition, said processing structure transforms each freeform line object forming said hand-drawn table into one of a vertical line segment and a horizontal line segment, generates a grid system based on the vertical and horizontal line segments, converts the generated grid system into said table object, detects input non-freeform line objects that are within the table object and inserts the detected non-freeform line objects as table object content, wherein during said inserting, each detected non-freeform line object is placed into a corresponding cell of said table object as table cell content

wherein said processing structure further;

compares each created horizontal line segment with a horizontal line segment list to determine if it overlaps with an existing horizontal line segment;

if not, adds the created horizontal line segment to the list and, if so, performs a merging of the created and existing horizontal line segments;

compares each created vertical line segment with a vertical line segment list to determine if it overlaps with an existing vertical line segment; and

if not, adds the created vertical line segment to the list and, if so, performs a merging of the created and existing vertical line segments, and

wherein said processing structure further, prior to the comparing to determine overlap;

examines each horizontal line segment to determine if it is within a threshold vertical distance of an existing horizontal line segment in the horizontal line segment list;

if so, performs the comparing to determine overlap and, if not, bypasses the overlap comparing and adds the horizontal line segment to the list;

examines each vertical line segment to determine if it is within a threshold horizontal distance of an existing vertical line segment in the vertical line segment list; and

if so, performs the comparing to determine overlap and, if not, bypasses the overlap comparing and adds the vertical line segment to the list.

32. An interactive input system according to claim 31 wherein said processing structure invokes the table recognition procedure in response to user input.

33. A computerized method of recognizing an input hand-drawn table formed by freeform line objects, said method comprising:

transforming each freeform line object of said table into one of a vertical line segment and a horizontal line segment, wherein said transforming comprises, for each freeform line object;

determining the start point and end point of the freeform line object;

generating a temporary line segment extending between the determined start point and end point;

determining the orientation of said temporary line segment; and

based on the determined orientation, creating one of said vertical line segment and horizontal line segment;

generating a grid system based on the vertical and horizontal line segments;

converting the generated grid system into a table object;

detecting input non-freeform line objects that are within the table object; and

inserting the detected non-freeform line objects as table object content, wherein during said inserting, each detected non-freeform line object is placed into a corresponding cell of said table object as table cell content

wherein said transforming further comprises;

comparing each created horizontal line segment with a horizontal line segment list to determine if it overlaps with an existing horizontal line segment;

if not, adding the created horizontal line segment to the list and, if so, performing a merging of the created and existing horizontal line segments;

comparing each created vertical line segment with a vertical line segment list to determine if it overlaps with an existing vertical line segment; and

if not, adding the created vertical line segment to the list and, if so, performing a merging of the created and existing vertical line segments, and

wherein said transforming further comprises, prior to said comparing to determine overlap;

examining each horizontal line segment to determine if it is within a threshold vertical distance of an existing horizontal line segment in the horizontal line segment list;

if so, performing said comparing to determine overlap and, if not, bypassing the overlap comparing and adding the horizontal line segment to the list;

examining each vertical line segment to determine if it is within a threshold horizontal distance of an existing vertical line segment in the vertical line segment list; and

if so, performing said comparing to determine overlap and, if not, bypassing the overlap comparing and adding the vertical line segment to the list.

34. The method of claim 33 wherein said detecting comprises determining non-freeform line objects having designated locations positioned within a cell of the table object.

35. The method of claim 33 further comprising processing the table object based on the table cell content placed in the table object.

36. The method of claim 35 wherein processing the table object comprises:

recognizing the content in a first table cell as a predetermined processing indicator;

processing the content in one or more table cells differing from said first table cell according to the recognized processing indicator; and

replacing the content in said first table cell with the result of the processing.

37. The method of claim 36 wherein the content in the first table cell is a hand-drawn object.

38. The method of claim 37 wherein said processing indicator is a mathematical plus sign and wherein the result of the processing is a summation.