Method and apparatus for compression of electronic ink

• US 6,101,280 A
• Filed: 01/03/1997
• Issued: 08/08/2000
• Est. Priority Date: 07/04/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Reynolds, David Everett
• Primary Examiner(s): Lee, Thomas D.
• Assistant Examiner(s): Chen, Wenpeng
• Application Number:
  US08/778,553
• Time in Patent Office: 1,313 Days
• Field of Search: 382/122, 382/120, 382/186, 382/187, 382/188, 382/241, 382/311, 382/119, 382/189, 382/199, 382/243, 382/185, 382/177, 382/203, 382/202, 382/123, 395/142
• US Class Current: 382/241
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

There is provided a lossy ink compression system aimed at low cost, high compression of ink on hand-held platforms. The present invention detects the critical cusp, or knot points in the ink and then resamples the smooth curves between successive cusp points discarding the dynamic information. The resampled data is then scaled to more closely match the display resolution. Finally, the data is delta coded and then packed for storage.

Claims

1. A method of compressing the size of a digital representation of handwriting comprising the steps of:

forming a digital representation of the handwriting by digitizing the handwriting as sequences of coordinate pairs representing traces of strokes of the handwriting having negligible width;

detecting knot points in said digital representation, said knot points being at local extrema or regions of high curvature of said handwriting;

identifying each digital representation connecting two knot points and not containing an intermediate knot point as a digital representation segment; and

resampling each said digital representation segment by polygonal approximation into a variable number of line segments connecting said knot points to create resampled data;

wherein the numbers and position of line segments created to polygonally approximate each digital representation segment between adjacent ones of said knot points is determined by static parameters of said digital representation segment independent of velocity information.

2. A method according to claim 1 comprising detecting knot points by detecting local extrema in said digital representation.

3. A method according to claim 1 comprising detecting knot points by detecting local velocity minima in said digital representation.

4. A method according to claim 1, further comprising the steps of:

low pass filtering said digital representation prior to locating said knot points;

removing artifacts produced by said step of locating;

rescaling said resampled data to create rescaled data;

coding said rescaled data to create coded data; and

packing said coded data to create packed data.

5. A method according to claim 4 wherein said step of coding comprises the steps of:

predicting the location of a next point on said digital representation and

encoding the difference between said predicted location of said next point and an actual location of said next point.

6. A method of decompressing a digital representation of handwriting compressed by a method according to claim 4, comprising the steps of:

unpacking said packed data to derive said coded data;

decoding said coded data to derive decoded data; and

connecting individual points within said decoded data by a straight line.

7. A method according to claim 6 wherein said step of decoding comprises the steps of:

identifying cusps in said decoded data, said cusps being at points of high curvature; and

deriving an interpolation point between each pair of points along said decoded data between said cusps.

8. A method according to claim 7 wherein said step of deriving comprises the step of using spline smoothing (eq. 3) to find said interpolation points.

9. A method according to claim 7 wherein a cusp is a point for which the exit segment subtends an obtuse angle to the entry segment.

10. A method according to claim 1 wherein said polygonal approximation is based on locating, on a segment of the digital representation defined between first and second points, an intermediate point maximally distant from a straight line between the first and second points, and wherein said line segments are less than a predetermined length.

11. A method according to claim 10 comprising detecting knot points by detecting local extrema in said digital representation.

12. A method according to claim 10 comprising detecting knot points by detecting local velocity minima in said digital representation.

13. A method according to claim 10, further comprising the steps of:

low pass filtering said digital representation prior to locating said knot points;

removing artifacts produced by said step of locating;

rescaling said resampled data to create rescaled data;

coding said rescaled data to create coded data; and

packing said coded data to create packed data.

14. A method according to claim 13 wherein said step of coding comprises steps of:

predicting a location of a next point on said digital representation; and

encoding a difference between said predicted location of said next point and an actual location of said next point.

15. A method of compressing the size of a digital representation of handwriting comprising the steps of:

detecting knot points in said digital representation, said knot points being at regions of high curvature of said handwriting; and

resampling said digital representation by polygonal approximation into a variable number of line segments between adjacent ones of said knot points to create resampled data;

wherein said step of resampling by polygonal approximation comprises substeps of;

defining a straight line from a first point along a portion of said digital representation to a second point along said portion of said digital representation;

locating a third point along a portion of said digital representation between said first point and said second point, said third point being a maximum distance from said straight line;

if said maximum distance is greater than a limit value, then replacing said straight line with a first straight line from said first point to said third point and a second straight line from said third point to said second point;

if said maximum distance is less than said limit value, then;

if said straight line is shorter than a maximum length, then replacing said portion of said digital representation between said first point and said second point with said straight line; and

if said straight line is loner than said maximum length, then replacing said straight line with a third straight line from said first point to a fourth point and a fourth straight line from said fourth point to said second point, said fourth point being located on said portion of said digital representation between said first point and said second point.

16. A method according to claim 15 wherein if said straight line has been replaced then the replacement straight lines are new straight lines which have each been defined between a respective first endpoint and second endpoint located on the digital representation, and said step of polygonal resampling comprises the further substeps, for each new straight line, of:

locating an intermediate point along a portion of the digital representation between the first endpoint and the second endpoint, said intermediate point being a new maximum distance from the new straight line; and

if said new maximum distance is more than said limit value, then replacing the new straight line with a first further straight line between the first endpoint and the intermediate point and a second further straight line between the intermediate point and the second endpoint;

if said new maximum distance is less than said limit value, then;

if said new straight line is shorter than said maximum length, then replacing said portion of said digital representation between the first endpoint and the second endpoint with said new straight line; and

if said new straight line is loner than said maximum length, then replacing said new straight line with a third further straight line from said first end point to a fourth endpoint and a fourth further straight line from said fourth endpoint to said second endpoint, said fourth endpoint being located on said portion of said digital representation between said first endpoint and said second endpoint;

wherein these substeps are repeated for each further straight line generated until all straight lines in the resampled representation are shorter than the maximum length and are not separated from any intermediate point in the section of the digital representation bounded by endpoints of the further straight line by more than said limit value.

17. A method according to claim 15 comprising detecting knot points by detecting local velocity minima in said digital representation.

18. A method of compressing the size of a digital representation of handwriting comprising the steps of:

forming a digital representation of the handwriting by digitizing the handwriting as sequences of coordinate pairs representing traces of strokes of the handwriting having negligible width;

detecting knot points in said digital representation, locations of said knot points being based upon static spatial parameters of said handwriting representation irrespective of handwriting velocity information;

defining each pair of adjacent knot points and points of said digital representation which are located therebetween as a digital representation segment; and

resampling each said digital representation segment by polygonal approximation into a variable number of line segments to create resampled data.

19. A method according to claim 18 wherein the step of resampling by polygonal approximation further comprises:

defining a first straight line for polygonal approximation between a first knot point and an adjacent second knot point;

if the first straight line is longer than a maximum length l, or if a point on a first digital representation segment between the first and second knot points is farther than a maximum distance d from the first straight line, then replacing said first straight line by second and third straight lines for polygonal approximation, said second straight line being between the first knot point and a third point located on said digital representation segment and said third straight line being between said third point and said second knot point.

20. A method according to claim 18 wherein said polygonal approximation is based on locating, on a segment of the digital representation defined between first and second points, an intermediate point maximally distant from a straight line between the first and second points.

21. The method of claim 18 comprising the further steps of:

filtering the digital representation before locating the knot points;

removing artifacts produced by said step of locating;

rescaling said resampled data to create rescaled data;

coding said rescaled data to create coded data; and

packing said coded data to create packed data.