Methods and processes for recognition of electronic ink strokes

• US 7,907,141 B2
• Filed: 03/23/2007
• Issued: 03/15/2011
• Est. Priority Date: 03/23/2007
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Saund, Eric
• Primary Examiner(s): Amini, Javid A
• Application Number:
  US11/726,796
• Publication Number:
  US 20080231635A1
• Time in Patent Office: 1,453 Days
• Field of Search: 345/468
• US Class Current: 345/468
• 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 digital ink strokes into multiple hypotheses reflecting structured interpretation of the digital ink strokes in a group, wherein;

structured interpretation of ink strokes comprises determining related ink strokes based on similarity of characteristics of the ink strokes;

a hypothesis represents an interpretation of the digital ink stroke groups as a specific object type;

computing confidence scores for the multiple hypotheses, each hypothesis having an intrinsic score and a support-context score, wherein;

the intrinsic score is based on similarity between digital ink strokes of the digital ink stroke group and defined criteria for the specific object type interpretation represented by the hypothesis;

the support-context score is based on the confidence score of surrounding digital ink strokes;

applying constraints among the hypotheses;

searching hypotheses under the applied constraints for a collectively high scoring assignment; 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 digital ink 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 he 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 hypotheses due to the at least one of adding, deleting or spatially transforming;

one of;

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

(ii) forming new 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 assignment 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) digital ink strokes of the node-link diagram, or (ii) digital ink 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 method of recognition of electronic ink strokes drawn on a canvas of an electronic device, the method comprising:

fragmenting ink strokes;

grouping related digital ink strokes based on similar characteristics of the ink strokes, each digital ink stroke being a member of at least one digital ink stroke group;

forming hypotheses of digital ink stroke groups, wherein a hypothesis represents a possible interpretation of the digital ink stroke group as a specific object type;

forming a lattice of hypotheses, wherein;

a complex by hypothesis is composed of at least one support hypothesis;

complex hypotheses represent interpretation of digital ink strokes as a complex object type;

a support hypothesis represents interpretation of digital ink strokes as simpler object type;

computing a confidence scores for each hypothesis, the confidence score having an intrinsic score and a support-context scores;

the intrinsic score is based on similarity between the digital ink strokes of the digital ink stroke groups and defined criteria for the specific object type interpretation represented by the hypothesis;

the support-context score of support hypotheses is assigned a predetermined value;

the support-context score of complex hypotheses is assigned a value equal to the minimum of the intrinsic score and the support-context confidence scores of the support hypotheses minus an epsilon value;

applying constraints among the hypotheses;

searching hypotheses under the applied constraints for a collectively high scoring confidence score; and

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

13. The 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 method of claim 13, wherein the incremental structure recognition includes:

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

one of;

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

(ii) forming new hypotheses groups;

recognizing the affected groups; and

updating a hierarchical lattice formed from the accepted hypotheses.

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

searching the lattice of 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 confidence scores of hypotheses assigned the value “

accept.”

16. The method of claim 15, wherein the algorithm is a tree search algorithm.

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

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

19. The method of claim 15, wherein the algorithm is constrained to assign “

accept/reject”

values to hypotheses under a non-overlapping support constraint.

20. The method 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 method of claim 12, wherein the digital ink strokes are one of (i) digital ink strokes of the node-link diagram, or (ii) digital ink strokes that are not part of the node-link diagram.

22. The method 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 electronic ink strokes together as electronic ink stroke groups;

forming multiple hypotheses reflecting structural interpretations for the electronic ink stroke groups, wherein;

structural interpretation comprises determining related electronic ink strokes based on similarity of characteristics of the electronic ink strokes;

a hypothesis represents an interpretation of the electronic ink stroke groups as a specific object type;

applying intrinsic confidence scores for the multiple hypotheses based on similarity between electronic ink strokes of the electronic ink stroke groups and defined criteria for the specific object type;

applying context-based confidence scores to the multiple hypotheses in accordance with interacting support between electronic ink 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 electronic ink strokes of the node-link diagram, making the node-link diagram electronically editable.