Methods and processes for recognition of electronic ink strokes

• US 20080231635A1
• Filed: 03/23/2007
• Published: 09/25/2008
• Est. Priority Date: 03/23/2007
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Saund, Eric
• Granted Patent: US 7,907,141 B2
• Time in Patent Office: Days
• US Class Current: 345/440
• 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/347 Sampling; Contour coding; Stroke extraction
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

A method and process provides structure recognition to a node-link diagram formed by a plurality of digital ink strokes drawn on a canvas of an electronic device by an input device. The method and process include grouping related strokes into multiple hypotheses reflecting structure interpretations of the strokes in a group. Confidence scores are computed for the multiple hypotheses based on local evidence regarding the strokes of the stroke groups and surrounding strokes. Constraints are applied among the hypotheses, and a collectively high scoring assignment of accept/reject values of the hypotheses are determined under the applied constraints. The hypotheses with collectively high scoring assignments are accepted as a representation of the node-link diagram, where structure information is provided to the strokes of the node-link diagram, making the node-link diagram electronically editable.

Claims

1. A method of providing structure recognition to a node-link diagram:

formed by a plurality of digital ink strokes drawn on a canvas of an electronic device by an input device, the method comprising;

grouping related strokes into multiple hypotheses reflecting structured interpretation of the strokes in a group;

computing confidence scores for the multiple hypotheses based on local evidence regarding the strokes of the stroke groups and surrounding strokes;

applying constraints among the hypotheses;

searching for a collectively high scoring assignment of accept/reject values to hypotheses under the applied constraints; and

accepting the hypothesis with the collectively high scoring assignment as a representation of the node-link diagram, wherein structure information is provided to the strokes of the node-link diagram, making the node-link diagram electronically editable.

2. The method of claim 1, further including:

at least one of,

(i) adding digital ink strokes to the node-link diagram,

(ii) deleting digital ink strokes from the node-link diagram,

(iii) deleting formal object representations of textual items from the node-link diagram,

(iv) deleting formal object representations of graphical items from the node-link diagram,

(v) spatially transforming digital ink strokes of the node-link diagram,

(vi) spatially transforming formal object representations of textual items of the node-link diagram,

(vii) spatially transforming formal object representations of graphical items of the node-link diagram; and

performing incremental structure recognition of the node-link diagram.

3. The method of claim 2, wherein the incremental structure recognition includes:

generating new structure hypotheses due to the at least one of adding, deleting or spatially transforming;

one of,

(i) grouping the new structure hypotheses with existing structure hypotheses groups,

(ii) forming new structure hypotheses groups;

recognizing the affected groups; and

updating a hierarchical lattice formed from the accepted hypotheses.

4. The method of claim 1, wherein the step of searching for the accepted hypotheses from among the multiple hypotheses further includes:

searching a hypothesis lattice of the hypotheses by use of a search algorithm, wherein the algorithm seeks an optimal, near-optimal or best obtainable, global assignment score, wherein the global assignment score is an arithmetic combination of scores of hypotheses assigned an “

accept”

type value.

5. The method of claim 4, wherein the search algorithm is a tree search algorithm.

6. The method of claim 5, wherein the tree search algorithm is a depth-first tree algorithm.

7. The method of claim 5, wherein the tree search algorithm is a best-first tree search algorithm.

8. The method of claim 4, wherein the algorithm is constrained to assign “

accept/reject”

type values to hypotheses under a non-overlapping support constraint.

9. The method of claim 8, wherein searching to apply the “

accept/reject”

type values includes forcing one of a true or false state to at least one of the hypotheses.

10. The method of claim 1, wherein the digital ink strokes are one of (i) strokes of the node-link diagram, or (ii) strokes that are not part of the node-link diagram.

11. The method of claim 1, wherein the node-link diagram includes both text and graphics.

12. A computer readable medium having computer executed instructions for performing steps comprising:

grouping related strokes together into multiple hypotheses reflecting structure interpretations of the strokes in a group;

computing confidence scores for the multiple hypotheses based on local evidence regarding the strokes of the stroke groups and surrounding strokes;

applying constraints among the hypotheses;

searching for a collectively high scoring assignment of accept/reject values to hypotheses under the applied constraints; and

accepting the hypotheses with the collectively high scoring assignment as a representation of the node-link diagram, wherein structure information is provided to the ink strokes of the node-link diagram, making the node-link diagram electronically editable.

13. The computer readable medium method of claim 12, further including:

at least one of,

(i) adding digital ink strokes to the node-link diagram,

(ii) deleting digital ink strokes from the node-link diagram,

(iii) deleting formal object representations of textual items from the node-link diagram;

(iv) deleting formal object representations of graphical items from the node-link diagram;

(v) spatially transforming digital ink strokes;

(vi) spatially transforming formal object representations of textual items of the node-link diagram;

(vii) spatially transforming formal object representations of graphical items of the node-link diagram; and

performing incremental structure recognition of the node-link diagram.

14. The computer readable medium of claim 13, wherein the incremental structure recognition includes:

generating new structure hypotheses due to the at least one of adding, deleting or spatially transforming;

one of,

(i) grouping the new structure hypotheses with existing structure hypotheses groups,

(ii) forming new structure hypotheses groups;

recognizing the affected groups; and

updating a hierarchical lattice formed from the accepted hypotheses.

15. The computer readable medium according to claim 12, wherein the step of searching for the accepted hypotheses from among the multiple hypotheses further includes:

searching a hypothesis lattice of the hypotheses by use of a search algorithm, wherein the algorithm seeks an optimal or near-optimal global assignment score, wherein the global assignment score is an arithmetic combination of scores of hypotheses assigned the value “

accept.”

16. The computer readable medium of claim 15, wherein the algorithm is a tree search algorithm.

17. The computer readable medium of claim 16, wherein the tree search algorithm is a depth-first tree search algorithm.

18. The computer readable medium of claim 16, wherein the tree search algorithm is a best-first search algorithm.

19. The computer readable medium of claim 15, wherein the algorithm is constrained to assign “

accept/reject”

values to hypotheses under a non-overlapping support constraint.

20. The computer readable medium of claim 19, wherein searching to apply the “

accept/reject”

values includes forcing one of a true or false state to at least one of the hypotheses.

21. The computer readable medium of claim 12, wherein the digital ink strokes are one of (i) strokes of the node-link diagram, or (ii) strokes that are not part of the node-link diagram.

22. The computer readable medium to claim 12, wherein the node-link diagram includes both text and graphics.

23. A method for providing structure recognition to a node-link diagram formed by a plurality of electronic ink strokes drawn on a canvas of an electronic device by an input device, the method comprising:

grouping related strokes together as stroke groups;

forming multiple hypotheses reflecting structural interpretations for the stroke groups;

applying intrinsic confidence scores for the multiple hypotheses based on local evidence regarding the strokes of the stroke groups;

applying context-based confidence scores to the multiple hypotheses in accordance with interacting support between stroke groups;

applying constraints among the hypotheses;

searching for hypotheses having the an acceptable score; and

accepting the hypotheses to the node-link diagram, wherein structure information is provided to the ink strokes of the node-link diagram, making the node-link diagram electronically editable.