Method and apparatus for representing image data using polynomial approximation method and iterative transformation-reparametrization technique

• US 5,473,742 A
• Filed: 02/22/1994
• Issued: 12/05/1995
• Est. Priority Date: 02/22/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: ParaGraph International (Graphics Properties Holdings, Inc.)
• Inventors: Ryleev, Mikhail A., Polyakov, Vladislav G.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/200,046
• Time in Patent Office: 651 Days
• Field of Search: 395/133-139, 395/142, 395/155, 395/161, 395/140, 395/141, 395/150, 395/151, 382/13, 382/56
• US Class Current: 345/442
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: Y10S 345/947 Font character edge processing

Abstract

A piecewise parametric polynomial curve-fitting method using an iterative transformation-reparametrization technique is used to compress information describing lines, such as those formed by handwritten lines, for storage in a compressed form in a computer. The curve-fitting method is applied iteratively with adaptive segmenting of curve segments to optimize piecewise approximations of complex curves. Each piecewise segment is iteratively lengthened, parameterized with an updatable parametrization table, and approximated using a cosine-type transform. To minimize approximation errors, both the accuracy and the trend of the approximation errors are monitored. In order to match end-point positions of the piecewise approximation segments, the cosine coefficients representing each piecewise segment are modified in view of the edge conditions so the segments properly abut one another upon reconstruction.

Claims

1. A computer system for representing image data using polynomial approximation and iterative transformation-reparametrization, said computer system having a memory means and output means, said computer system comprising:

a digitizer for inputting and converting a curve into a binary format;

first memory location in said memory means for storing a first set of data points representing said curve including a first curve end in said binary format;

processor means coupled to said memory means and comprising means for;

1) transforming parametric representations of segments of said source curve to obtain truncated cosine coefficient representations of said line segments,

2) inverse transforming said truncated cosine coefficient representations to obtain parametric representations of approximations of said line segments,

3) computing parametrizations of said approximations of said line segments from said parametrizations of said approximations,

4) normalizing said parametrizations of said approximations to said line segments to obtain normalized parametrizations of said line segments,

5) reparametrizing said line segments in accordance with said normalized parametrizations to obtain successor parametric representations of said line segments,

6) approximating a selected segment of said source curve by a) obtaining an initial parametrization of said selected segment as an initial input for said transforming means, b) repeatedly applying said inverse transforming means, parametrization computing means, normalizing means, reparametrization means, and transforming means until an output of said inverse transforming means meets a predetermined goodness-of-fit criterion when compared to said selected segmentor a convergence criterion, and c) storing the last output of said transforming means in said second memory means as a compressed representation of said selected segment,

5) compressing said source curve by applying said approximating means to obtain a compressed representation of a designated segment of said source curve and then iteratively extending said designated segment along said source curve to obtain extended segments and applying said approximating means to said extended segments until said approximating means converges without meeting said goodness-of-fit criterion; and

second memory location in said memory means for storing a second set of data points, said second data points set designating a compressed representation of a final extended designated segment generated by said means for compressing.

2. The computer system of claim 1 wherein said processor means further comprises:

means for designating a first segment of said source curve beginning at said first curve end and applying said compressing means to said first segment to obtain a compressed representation of an extension of said first segment; and

means for designating a second segment beginning at an end of said extension of said first segment and applying said compressing means to said second segment to obtain a compressed representation of an extension of said second segment.

3. The computer system of claim 2 wherein said processor means further comprises:

edge condition processing means for modifying said cosine coefficient representations to satisfy at least two edge conditions defining a boundary between said extension of said first segment and said second segment.

4. The computer system of claim 2 wherein said processor means further comprises Huffman encoding means for further compressing said compressed representations of said extensions of said first and second segments along with beginning and end coordinates of said extensions of said first and second segments.

5. The computer system of claim 1 wherein said processor means further comprises:

means for designating successive segments of said source curve and applying said compressing means to said successive segments until said compressing means extends a designated segment to an end of said source curve opposite said first end, wherein said first segment begins at said first curve end and other successive segments abut the extensions of previous designated segments as generated by said compressing means.

6. In a computer system having a processor means and a memory coupled to said processor means, a method for representing a curve, said method comprising the steps of:

i) storing in a first memory means a sampled data point curve representation;

thereafter

ii) approximating with said processor means said curve utilizing said curve representation by;

a) demarcating with said processor means a current segment;

b) lengthening with said processor means said current segment by appending an adjacent fragment of said curve representation to said current segment, thereby lengthening said current segment;

c) parameterizing with said processor means said lengthened current segment employing a first parametrization table;

d) deriving with said processor means a set of cosine coefficients via a forward cosine-type transform on said lengthened current segment;

e) truncating with said processor means said set of cosine coefficients, thereby obtaining a set of truncated cosine coefficients;

f) modifying with said processor means said set of truncated cosine coefficients to satisfy at least two specific edge conditions, thereby obtaining a set of truncated and modified cosine coefficients;

g) obtaining with said processor means a parametric representation of an approximation of said lengthened current segment via an inverse cosine-type transform on said set of truncated and modified cosine coefficients;

h) computing with said processor means a first approximation error and storing said first approximation error in a memory array;

i) if a trend of approximation errors tends toward a first predetermined goodness-of-fit threshold;

i1) recomputing with said processor means said first parametrization table utilizing said approximation of said lengthened current segment;

i2) if said first approximation error is worse than a second predetermined goodness-of-fit threshold, repeating with said processor means the method starting at step c;

i3) if said first approximation error is not worse than said second predetermined goodness-of-fit threshold, forming a first set of segment descriptors representing said current segment and storing in a second memory means said first set of segment descriptors and repeating with said processor means the method starting at step b, taking said lengthened current segment as a new said current segment; and

j) if said trend of approximation errors does not tend toward said first predetermined goodness-of-fit threshold, designating with said processor means the ending point of said current segment the starting point of a new said current segment, and repeating with said processor means the method starting at step b.

7. The method of claim 6 wherein said sampled data point curve representation is time-sampled.

8. The method of claim 6 wherein said two specific edge conditions are the coordinates of a curve end.

9. The method of claim 6 wherein said first predetermined goodness-of-fit threshold and said second predetermined goodness-of-fit threshold are the same.

10. The method of claim 6 wherein said step of forming said set of segment descriptors comprises the steps of:

forming a set of coordinates for the ending point of said current segment; and

obtaining with said processor means a truncated and abridged set of cosine coefficients by discarding the four coefficients of the lowest degrees from said set of truncated and modified cosine coefficients.

11. The method of claim 6 wherein said step of forming said set of segment descriptors comprises the steps of:

forming with said processor means a set of values representing the difference in the coordinates of the ending point and the starting point of said current segment; and

obtaining with said processor means a truncated and abridged set of cosine coefficients by removing the four coefficients of the lowest degrees from said set of truncated and modified cosine coefficients.

12. In a computer system having a memory means, processor means, and output means, a method for compressing a source curve comprising the steps of:

a) digitizing said source curve to obtain a binary representation of said source curve;

b) designating a first segment of said source curve;

c) parameterizing said first segment to obtain an initial parametric representation of said first segment;

d) transforming said initial parametric representation to obtain a cosine coefficient representation;

e) truncating said cosine coefficient representation to obtain a truncated cosine coefficient representation;

f) inverse transforming said truncated cosine coefficient representation to obtain a parametric representation of an approximated segment;

g) computing a parametrization of said approximated segment from said parametric representation of said approximated segment;

h) normalizing said parametrization of said approximated segment to obtain a successor parametrization of said first segment;

i) reparameterizing said first segment in accordance with said successor parametrization to obtain a successor parametric representation of said first segment;

j) transforming said successor parametric representation to obtain a new cosine coefficient representation;

k) comparing said approximated segment to said first segment to determine if a predetermined goodness-of-fit criterion or convergence criterion has been met;

l) repeating said e), f), g), h), i), j) and k) steps until one of said predetermined criteria has been met;

m) storing a final truncated cosine coefficient representation generated in said j) step as a compressed representation of said first segment; and

n) entropy encoding said compressed representation to obtain a further compressed representation of said first segment.

13. The method of claim 12 wherein said n) step comprises Huffman encoding.

14. The computer system of claim 13 wherein said processor means coupled to said memory means further comprises:

means for forming a current segment having as a first segment end said first curve end;

iterating means for lengthening said current segment to obtain a lengthened current segment, for parameterizing said lengthened current segment with a parametrization table to obtain a parameterized lengthened current segment, for performing a forward cosine-type transform on said parameterized lengthened current segment to derive a third set of cosine coefficients, for truncating said third cosine coefficients set according to a predetermined degree of approximation to form a truncated set, for modifying said truncated set to satisfy at least two edge conditions defining said lengthened current segment to obtain a modified set, for performing an inverse cosine-type transform on said modified set to form an approximation of said lengthened current segment, for deriving a parametrization of said approximation, for normalizing said parametrization of said approximation to said lengthened current segment to obtain a normalized parametrization, for applying said normalized parametrization to said lengthened current segment to obtain a successor parameterized lengthened current segment, for computing an approximation error between said approximation and said lengthened current segment; and

means responsive to said iterating means for designating as a next-to-last-lengthened current segment said piecewise segment if a trend of approximation errors does not tend toward a predetermined goodness-of-fit threshold.

15. The computer system of claim 14 wherein said processor means coupled to said memory means further comprises means for recomputing said parametrization table if said trend of approximation errors tends toward said predetermined goodness-of-fit threshold.

16. The computer system of claim 13 wherein said means for optimizing comprises:

means for truncating said first set of coefficients to obtain said second sets of coefficients.

17. The computer system of claim 13 wherein said means for optimizing comprises:

means for applying boundaries between abutting segments of said curve as boundary conditions to modify said first set of coefficients.

18. The computer system of claim 13 wherein said processor means further comprises means for:

obtaining said first sets of cosine coefficients by approximating initial portions of said successive abutting segments.

19. A computer system for representing image data using polynomial approximation and iterative transformation-reparametrization, said computer system having a memory means and output means, said computer system comprising:

a digitizer for inputting and converting a curve into a binary format;

first memory location in said memory means for storing a first set of data points representing said curve including a first curve end in said binary format;

processor means, coupled to said memory means, comprising means for representing successive abutting segments of said curve as first sets of cosine coefficients and means for optimizing said first sets of cosine coefficients to obtain second sets of cosine coefficients; and

second memory location in said memory means for storing said second sets of cosine coefficients.

20. In a computer system having a processor and a memory means coupled to said processor means, a method for representing a curve comprising the steps of:

digitizing a curve into a binary format with a digitizer means and storing at a first portion of said memory means a first set of data points representative of a first curve end;

demarcating a piecewise segment of said curve with said processor means and storing said segment at a second portion of said memory means;

deriving a first set of cosine coefficients approximately representing said piecewise segment with said processor means and storing said first cosine coefficients set at a third portion of said memory means;

storing at a fourth portion of said memory means a second set of data points designating a piecewise segment ending point; and

optimizing with said processor means said first cosine set and storing said optimized second cosine set at a sixth portion of said memory means.

21. The method of claim 20 wherein said step of optimizing said second cosine set comprises the step of truncating said second cosine set with said processor means and storing said truncated second cosine set at a seventh portion of said memory means.

22. The method of claim 21 wherein said step of optimizing said second cosine set further comprises the step of modifying said truncated version of said second cosine set to satisfy at least two edge conditions defining said curve portion with said processor means and storing said modified version at an eighth portion of said memory means.

23. In a computer system having a processor and a memory means coupled to said processor means, a method for representing a curve comprising the steps of:

digitizing a curve into a binary format with a digitizer means and storing at a first portion of said memory means a first set of data points representative of a first curve end;

forming a current segment having as a first segment end said first curve end with said processor means and storing said current segment at a second portion of said memory means;

iteratively lengthening said current segment with said processor means to obtain a lengthened current segment and storing said lengthened current segment at a third portion of said memory means, parameterizing said lengthened current segment according to a parametrization table with said processor means and storing said parameterized current segment at a fourth portion of said memory means, performing a forward cosine-type transform on said parameterized current segment to derive a first set of cosine coefficients with said processor means and storing said first cosine set at a fifth portion of said memory means, truncating said first cosine set to form a truncated set according to a predetermined degree of approximation with said processor means and storing said truncated first cosine set at a sixth portion of said memory means, modifying said truncated set to satisfy at least two edge conditions defining said lengthened current segment to obtain a modified set with said processor means and storing said modified set at a seventh portion of said memory means, performing an inverse cosine-type transform on said modified set to form an approximation of said lengthened current segment with said processor means and storing said approximation at an eighth portion of said memory means, deriving a parametrization of said approximation and storing said parametrization of said approximation at a ninth portion of said memory means, normalizing said parametrization of said approximation to obtain a normalized parametrization and storing said normalized parametrization at a tenth portion of said memory means, applying said normalized parametrization to said lengthened current segment to obtain a successor parametrized current segment and storing said successor parametrized current segment at said fourth location of said memory means, computing an approximation error between said approximation and said lengthened current segment with said processor means and storing said approximation error at a eleventh portion of said memory means;

designating a next-to-last-lengthened current segment of said piecewise segment if a trend of approximation errors does not tend toward a predetermined goodness-of-fit threshold with said processor means and storing said designated next-to-last-lengthened current segment at a twelfth portion of said memory means as a current piecewise segment;

deriving a second set of cosine coefficients approximately representing said piecewise segment with said processor means and storing said second cosine coefficients set at an thirteenth portion of said memory means; and

storing at a fourteenth portion of said memory means a second set of data points designating a piecewise segment ending point.

24. The method of claim 23 wherein said step of demarcating said piecewise segment further comprises:

recomputing said parametrization table if said trend of approximation errors tends toward said predetermined goodness-of-fit threshold with said processor means and storing said recomputed table at an eighteen portion of said memory means.