Method of compressing digital ink

• US 7,650,033 B2
• Filed: 10/06/2008
• Issued: 01/19/2010
• Est. Priority Date: 11/16/2001
• Status: Expired due to Fees

• Current Assignee: Silverbrook Research Pty Limited
• Original Assignee: Silverbrook Research Pty Limited
• Inventors: Napper, Jonathon Leigh
• Primary Examiner(s): Rogers; Scott A
• Application Number:
  US12/246,478
• Publication Number:
  US 20090046936A1
• Time in Patent Office: 470 Days
• Field of Search: 382/186, 382/187, 382/189, 382/195, 382/197, 382/198, 382/201, 382/202, 382/203, 382/232, 382/238, 382/241, 382/242, 382/243, 382/188, 382/200, 382/244, 345/173, 345/178, 345/179
• 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: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A method of compressing a digital ink input including a sequence of strokes is provided in which each stroke is represented as a series of digital words representing x and y co-ordinates, at least one reference co-ordinate of each stroke is expressed in absolute terms, and a co-ordinate other than the at least one reference co-ordinate is expressed as an offset from a preceding co-ordinate. The co-ordinate other than the at least one reference co-ordinate is represented as a combination of an estimate determined from the previous m co-ordinates and a residual error value.

Claims

1. A method of compressing a digital ink input including a sequence of strokes input at an input device of a processing system, the method comprising the steps of, carried out by a processor of the processing system:

representing each stroke input at the input device as a series of digital words representing x and y co-ordinates;

expressing at least one reference co-ordinate of each stroke in absolute terms; and

expressing a co-ordinate other than the at least one reference co-ordinate as an offset from a preceding co-ordinate,

wherein the co-ordinate other than the at least one reference co-ordinate is represented as a combination of an estimate determined from the previous m co-ordinates and a residual error value, and

the estimate is calculated from the previous m co-ordinates using the formula;

${\widetilde{\mathrm{\alpha <br><br>}}}_n=\underset{i=1}{\overset{m}{\sum <br><br>}}<br><br>c_i<br><br>{\mathrm{\alpha <br><br>}}_{n-i}$

where c_i are coefficients selected to model characteristics of the digital ink, and α

represents either an x or a y co-ordinate.

2. The method of claim 1, further comprising the step of calculating the estimate using a linear prediction algorithm.

3. A method as claimed in claim 1 wherein m is 2, and a co-ordinate may be defined:

α

_n=C₁α

<sub>n−

1</sub>+C₂α

<sub>n−

2.</sub>

4. A method as claimed in claim 3 wherein C₁>

0 and C₂<

0.

5. A method as claimed in claim 4 wherein:

1≦

C₁≦

3 and

−

2≦

C₂≦

1.

6. A method as claimed in claim 5 wherein C₁=2 and C₂=−

1.

7. A method as claimed in any one of claims 3 to 6 wherein the coefficient values (C_i) for x co-ordinates are different to the coefficients for y co-ordinates.

8. A method as claimed in claim 7 wherein for x co-ordinates:

C₁=1.857

C₂=−

0.856, and

for y co-ordinates;

C₁=1.912

C₂=−

0.913.

9. A method as claimed in claim 1 wherein m is 3, and a given co-ordinate may be defined:

{tilde over (α

)}_n=c₁α

<sub>n−

1</sub>+c₂α

<sub>n−

2</sub>+c₃α

<sub>n−

3.</sub>

10. A method as claimed in claim 9 wherein C₁>

0 and C₂<

0 and C₃<

1.

11. A method as claimed in claim 9 or 10 wherein the coefficient values (C_i) for x co-ordinates are different to the coefficients for y co-ordinates.

12. A method as claimed in claim 11 wherein for x co-ordinates:

C₁=1.799

C₂=−

0.722

C₃=−

0.078, and

for y co-ordinates;

C₁=2.009

C₂=−

1.107

C₃=−

0.098.

13. A method as claimed in claim 1, further comprising the steps of discarding the estimate, and storing the residual error.