Method and system for line extraction in digital ink

• US 7,630,551 B2
• Filed: 11/21/2007
• Issued: 12/08/2009
• Est. Priority Date: 02/26/2003
• Status: Expired due to Fees

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Napper, Jonathon Leigh, Lapstun, Paul, Koubaroulis, Dimitrios
• Primary Examiner(s): Chawan; Sheela C
• Application Number:
  US11/944,404
• Publication Number:
  US 20080304748A1
• Time in Patent Office: 748 Days
• Field of Search: 382/186, 382/187, 382/189, 382/203, 382/179, 382/177, 382/178, 382/226, 382/311, 382/202, 382/296, 382/298, 382/309, 715/863, 715/209, 715/273, 715/268, 715/255, 345/179, 345/173
• US Class Current: 382/179
• CPC Class Codes: G06V 30/333 Preprocessing; Feature extraction

Abstract

A method and system of line extraction in a digital ink sequence of handwritten text data points is provided in which a stroke sequence comprised of a sequence of strokes is obtained, the strokes are segmented into a sequence of substrokes by applying a stroke segmentation algorithm, angular differences between neighboring groups of substrokes, in the sequence of substrokes, are calculated, and the positions of the extrema of the angular differences are determined, thereby identifying the substrokes at line breaks and enabling line extraction.

Claims

1. A method of line extraction in a digital ink sequence, said digital ink sequence being generated by an input device used to write handwritten text, the method including the steps of:

receiving, in a processor communicating with the input device, a stroke sequence comprised of a sequence of strokes;

segmenting the strokes into a sequence of substrokes by applying a stroke segmentation algorithm;

calculating a centroid for each substroke;

using each centroid to calculate

angular differences between neighbouring groups of substrokes, in the sequence of substrokes; and

,

determining the positions of the extrema of the angular differences, said extrema corresponding to substrokes at line breaks, thereby enabling line extraction in the stroke sequence,

wherein substrokes are grouped about a selected substroke into a temporally preceding group of substrokes and a temporally subsequent group of substrokes, the centroid of the temporally preceding group and the temporally subsequent group being used to calculate the angular difference at the selected substroke.

2. The method as claimed in claim 1, wherein a centroid is calculated for each substroke, the centroids being used to calculate angular differences between neighbouring groups of substrokes, in the sequence of substrokes.

3. The method as claimed in claim 1, wherein substrokes are grouped about a selected substroke into a preceding group of N substrokes and a subsequent group of N substrokes, the centroid of the preceding group and the following group used to calculate the angular difference at the selected substroke.

4. The method as claimed in claim 1, wherein the extrema are the maxima or minima of the sequence of angular differences as a function of substroke sequence order.

5. The method as claimed in claim 1, wherein the stroke segmentation algorithm includes the steps of:

smoothing stroke data points;

computing a relative angle for each line segment connecting successive stroke data points;

segmenting the stroke into candidate substrokes if the difference between successive relative angles is greater than a preset threshold; and

,

merging candidate substrokes into a substroke if the angular direction of successive candidate substrokes is less than a threshold angle.

6. The method as claimed in claim 1, wherein the stroke sequence undergoes pre-processing.

7. The method as claimed in claim 6, wherein pre-processing includes removing data points that are less than a threshold distance from a preceding data point in the digital ink sequence.

8. The method as claimed in claim 6, wherein pre-processing includes removing strokes that are less than a threshold length dimension compared to neighbouring strokes.

9. The method as claimed in claim 1, wherein the stroke sequence undergoes post-processing.

10. The method as claimed in claim 9, wherein post-processing includes removing any line breaks between substrokes of a parent stroke.

11. A system for line extraction in a digital ink sequence of handwritten text data points, the system comprising:

(1) an input device to obtain a stroke sequence comprised of a sequence of strokes;

(2) a processor in communication with the input device and adapted to;

(A) segment the strokes into a sequence of substrokes by applying a stroke segmentation algorithm;

(B) calculate a centroid for each substroke;

(C) calculate angular differences between neighbouring substrokes, or groups of substrokes, in the sequence of substrokes; and

,

(D) determine the positions of the extrema of the angular differences, said extrema corresponding to substrokes at line breaks, thereby enabling line extraction in the stroke sequence,

wherein said processor is further adapted to group substrokes about a selected substroke into a temporally preceding group of substrokes and a temporally subsequent group of substrokes, the centroid of the temporally preceding group and the temporally subsequent group being used to calculate the angular difference at the selected substroke.