Smoothing and fitting point sequences

• US 6,304,677 B1
• Filed: 04/07/1998
• Issued: 10/16/2001
• Est. Priority Date: 04/07/1998
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Schuster, Michael
• Primary Examiner(s): ROGERS, SCOTT A
• Application Number:
  US09/056,716
• Time in Patent Office: 1,288 Days
• Field of Search: 345/441, 345/442, 345/136, 178/18.01, 178/18.03, 178/19.01, 178/20.01, 382/269, 382/267, 382/264, 382/241, 382/209, 382/171, 382/168, 382/164, 382/242, 382/119, 382/187, 382/189, 382/173, 382/266, 382/260, 382/261, 382/199, 382/200
• US Class Current: 382/264
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 5/10 using non-spatial domain filtering
• CPC Class Codes: G06T 5/70 Denoising; Smoothing
• CPC Class Codes: G06V 30/1423 the instrument generating sequences of position coordinates corresponding to handwriting preprocessing or recognising digital ink G06V30/32

Abstract

A method and apparatus implementing a technique for entering a representation of a desired curve into a computer. In one aspect, the technique includes receiving an ordered sequence of points representing the desired curve as input. The points of the sequence of points are grouped into one or more contiguous segments of points. The points of each segment are smoothed to generate a segment of smoothed points for each segment. One or more mathematical curves are fitted to each segment of smoothed points. Together, the one or more mathematical curves from each segment of smoothed points form the representation of the desired curve.

Claims

1. A computer-implemented method for entering a representation of a desired curve into a computer, the method comprising:

receiving an input of an ordered sequence of points representing the desired curve;

grouping the points of the sequence of points into one or more contiguous segments of points;

smoothing the points of each segment only after all of said contiguous segments of points are defined by grouping to generate a segment of smoothed points for each segment of points; and

fitting one or more mathematical curves to each segment of smoothed points, the one or more mathematical curves from each segment of smoothed points together forming the representation of the desired curve.

2. The method of claim 1 further comprising applying a noise filter to the ordered sequence of points before grouping the points into segments, the noise filter having a high pass-band.

3. The method of claim 2 wherein the smoothing comprises applying a smoothing filter to the points of each segment and the noise filter has a pass-band greater than that of the smoothing filter.

4. The method of claim 1 wherein grouping points into segments comprises:

determining which points are break points, a break point being an end point of the ordered sequence of points or a corner point within the ordered sequence of points, a corner point being a point having a high estimated curvature; and

grouping points between adjacent break points into single segments, where a closed curve without corner points forms a single segment.

5. The method of claim 4 wherein determining whether a point is a corner point comprises calculating the estimated curvature for the point from a plurality the points in the ordered sequence of points within a certain distance of the point.

6. The method of claim 5 wherein calculating the estimated curvature for a point comprises:

finding one or more consecutive leading points in the ordered sequence, where each leading point precedes the point in the ordered sequence and is less than a certain distance from the point;

forming a leading chord for each leading point, each leading chord having a first end point at the point and a second end point at the corresponding leading point;

calculating a leading average angle by averaging angles formed by each leading chord relative to the point;

finding one or more consecutive following points in the ordered sequence, where each following point follows the point in the ordered sequence and is less than a certain distance from the point;

forming a following chord for each following point, each following chord having a first end point at the point and a second end point at the corresponding following point;

calculating a following average angle by averaging angles formed by each following chord relative to the point; and

comparing the leading average angle and the following average angle.

7. The method of claim 5, wherein the certain distance is a Euclidean distance.

8. The method of claim 5, wherein the certain distance is a chord-length distance.

9. The method of claim 4 wherein the technique for smoothing a segment differs depending on whether the segment is an open segment or a closed segment.

10. The method of claim 9 wherein:

the technique for smoothing an open segment comprises calculating a frequency-space representation of the segment by taking a discrete sine transform of the segment; and

the technique for smoothing a closed segment comprises calculating a frequency-space representation of the segment by taking a discrete Fourier transform of the segment.

11. The method of claim 1 wherein the smoothing for a segment that is a closed sequence comprises:

calculating a frequency-space representation of the segment;

smoothing the frequency-space representation; and

inverting the smoothed frequency-space representation.

12. The method of claim 11 wherein smoothing the frequency-space representation comprises applying a low-pass filter to the frequency-space representation.

13. The method of claim 11 wherein:

calculating the frequency-space representation comprises applying a discrete Fourier transform; and

inverting the smoothed frequency-space representation comprises applying an inverse discrete Fourier transform.

14. The method of claim 1 wherein the smoothing for a segment that is an open sequence comprises:

subtracting a linear trend from the segment;

calculating a frequency-space representation of the segment;

smoothing the frequency-space representation;

calculating a subtracted segment by inverting the smoothed frequency-space representation; and

adding the linear trend to the subtracted segment.

15. The method of claim 14 wherein smoothing the frequency-space representation comprises applying a low-pass filter to the frequency-space representation.

16. The method of claim 14 wherein:

calculating the frequency-space representation comprises applying a discrete sine transform; and

inverting the smoothed frequency-space representation comprises applying an inverse discrete sine transform.

17. The method of claim 1 wherein, for each segment of points that is an open sequence, the positions of the end points of the segment of smoothed points are the same as the end points of the segment of points corresponding to that segment of smoothed points.

18. The method of claim 1 wherein the smoothing for each segment is independent of fitting a mathematical curve to the segment.

19. The method of claim 1 wherein fitting a curve to a segment of smoothed points comprises:

calculating a trial curve for the smoothed segment;

calculating a fidelity criterion for the trial curve on the smoothed segment; and

dividing the smoothed segment into two or more smoothed sub-segments if the trial curve does not satisfy the fidelity criterion and recursively fitting a curve to each smoothed sub-segment.

20. The method of claim 19 wherein the trial curve has a predetermined mathematical form.

21. The method of claim 19 wherein the trial curve is a parametric curve.

22. The method of claim 19 wherein the trial curve is a Bezier curve.

23. The method of claim 1 wherein fitting a curve to a smoothed segment comprises:

calculating tangent vectors at end points of the smoothed segment;

calculating a trial Bezier segment with constrained end points and tangents to the smoothed segment using the tangent vectors;

calculating a fidelity criterion for the trial Bezier segment on the smoothed segment; and

dividing the smoothed segment into two smoothed sub-segments if the trial Bezier segment does not satisfy the fidelity criterion and recursively fitting a curve to each smoothed sub-segment.

24. The method of claim 1 further comprising applying a noise filter to the ordered sequence of n points s_i, where i=0, . . . , n−

1, wherein the noise filter is a degree d λ

−

μ

filter, where, for frequencies k, 0<

k<

2, 0<

λ

<

−

μ

, and d even, the λ

−

μ

filter has a transfer function given by

25. The method of claim 24 wherein the filtering is performed iteratively by performing d passes on the ordered sequence of points s_i to form a sequence of filtered points s_i^j, for j=1, . . . , d, as follows

26. The method of claim 1 wherein grouping the points comprises finding corner points in the ordered sequence of n points s_i, where i=0, . . . , n−

1, where finding corner points includes comparing a corner angle tolerance c with a curvature c_i, −

1<

c_i<

1, at each point s_i in the sequence, where corners are points s_i where c_i<

c,

and further where a chord-length l_i for each point s_i is defined as

27. The method of claim 1 wherein, for a smoothness tolerance S and z=0, . . . , m−

1, the smoothing for a segment of m points t_z that is a closed sequence comprises;

calculating a frequency-space representation {circumflex over (t)}_z of the segment of points t_z;

calculating a frequency-space representation û

;

_z of a smoothed segment u_z by applying a low-pass transfer function g to {circumflex over (t)}_z;

calculating the smoothed segment u_z by taking an inverse discrete Fourier transform of û

;

_z;

where {circumflex over (t)}_z is defined as ${\hat{t}}_0=\sqrt{\frac{1}{m}}<br><br>\underset{r=0}{\overset{m-1}{\sum <br><br>}}<br><br>t_r,$

and where z is odd ${\hat{t}}_z=\sqrt{\frac{1}{m}}<br><br>\underset{r=0}{\overset{m-1}{\sum <br><br>}}<br><br>t_r<br><br>\cos \left(\frac{2<br><br>\mathrm{\pi <br><br>}<br><br>\lceil <br><br>\frac{z}{2}\rceil <br><br><br><br>r}{m}\right),$

and where z is even ${\hat{t}}_z=\sqrt{\frac{1}{m}}<br><br>\underset{r=0}{\overset{m-1}{\sum <br><br>}}<br><br>t_r<br><br>\sin \left(\frac{2<br><br>\mathrm{\pi <br><br>}<br><br>\lceil <br><br>\frac{z}{2}\rceil <br><br><br><br>r}{m}\right);<br><br>$

and further where for each {circumflex over (t)}_z, v_z is a corresponding eigenvalue of an eigenvector associated with {circumflex over (t)}_z, where v_z is defined as $v_z=1-\cos \left(\frac{2<br><br>\mathrm{\pi <br><br>}<br><br>\lceil <br><br>\frac{z}{2}\rceil <br><br>}{m}\right);<br><br>$

and further where, for frequencies 0<

v<

2, with constants w and g₀ chosen such that 1<

w<

m−

1 and 0<

g₀<

1, the low-pass transfer function g is defined such that

if v<

v_w

28. The method of claim 1 wherein, for a smoothness tolerance S and z=0, . . . , m−

1, the smoothing for a segment of m points t_z that is an open sequence comprises;

subtracting a linear trend from the segment of points t_z to form a subtracted segment t′

_z;

calculating a frequency-space representation {circumflex over (t)}_z of the subtracted segment of points t′

_z;

calculating a frequency-space representation û

;

′

_z of a smoothed subtracted segment u′

_z by applying a low-pass transfer function g to {circumflex over (t)}′

_z;

calculating the smoothed subtracted segment u′

_z by taking an inverse discrete Fourier transform of û

;

′

_z;

adding the linear trend to the smoothed, subtracted segment u′

_z to form a smoothed segment u_z;

where the linear trend is subtracted as follows $t_z^{\mathrm{\prime <br><br>}}=t_z-\frac{m-1-z}{m-1}<br><br>t_0-\frac{z}{m-1}<br><br>t_{m-1};<br><br>$

and where {circumflex over (t)}′

_z is defined as ${\hat{t}}_z^{\mathrm{\prime <br><br>}}=\sqrt{\frac{2}{m-1}}<br><br>\underset{r=0}{\overset{m-1}{\sum <br><br>}}<br><br>t_r^{\mathrm{\prime <br><br>}}<br><br>\sin <br><br>\left(\frac{\mathrm{\pi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z<br><br>\text{\hspace{1em}<br><br>}<br><br>r}{m-1}\right);<br><br>$

and further where for each {circumflex over (t)}′

_z, v_z is a corresponding eigenvalue of an eigenvector associated with {circumflex over (t)}′

_z, where v_z is defined as $v_z=1-\cos <br><br>\left(\frac{\mathrm{\pi <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z}{m-1}\right)$ 

v<sub>m−

1</sub>=0

; and

further where, for frequencies 0<

v<

2, with constants w and g₀ chosen such that 1<

w<

m−

1 and 0<

g₀<

1, the low-pass transfer function g is defined such that

if v<

v_w

29. The method of claim 1 wherein during the smoothing each segment of points is up-sampled by linear interpolation to achieve a total number of points in the segment equal to an integer power of two.

30. The method of claim 1 wherein, for a fidelity tolerance ƒ

, a chord-length θ

, and Ψ

=0, . . . , γ

−

1, the curve fitting comprises for each smoothed segment of γ

points φ

_ψ

;

estimating tangent vectors at end points of the smoothed segment of points φ

_ψ

using a local quadratic interpolate over all points of the smoothed segment φ

_ψ

within θ

of the endpoints, where θ

is approximately equal to 2ƒ

;

fitting a Bezier segment b(t) with constrained endpoint positions and tangents to the smoothed segment of points φ

_ψ

using least squares with a normalized chord-length parameterization;

calculating a fidelity criterion for the Bezier segment b(t) on the smoothed segment of points φ

_ψ

; and

dividing the smoothed sequence of points φ

_ψ

into two or more smoothed sub-segments if the Bezier segment b(t) does not satisfy the fidelity criterion and recursively fitting a curve to each smoothed sub-segment.

31. The method of claim 30 wherein calculating the fidelity criterion comprises:

computing a polygonal approximation of the Bezier segment b(t) within a flatness ε

ƒ

, where 0<

ε

<

1, the polygonal approximation comprising α

points Φ

_ω

with chord-length Θ

_ω

, where ω

=0, . . . , α

−

1;

where for each point φ

_ψ

in the smoothed sequence, Φ

<sub>ω

ψ</sub>

is a unique point such that $\frac{{\mathrm{\Theta <br><br>}}_{{\mathrm{\omega <br><br>}}_{\mathrm{\psi <br><br>}}}}{{\mathrm{\Theta <br><br>}}_{\mathrm{\alpha <br><br>}-1}}\le <br><br>\frac{{\mathrm{\theta <br><br>}}_{\mathrm{\psi <br><br>}}}{{\mathrm{\theta <br><br>}}_{\mathrm{\gamma <br><br>}-1}}<<br><br>\frac{{\mathrm{\Theta <br><br>}}_{{\mathrm{\omega <br><br>}}_{\mathrm{\psi <br><br>}}+1}}{{\mathrm{\Theta <br><br>}}_{\mathrm{\alpha <br><br>}-1}},$

and where Ω

<sub>ω

ψ</sub>

is a point on a line through Φ

<sub>ω

ψ</sub>

and Φ

<sub>ω

ψ

+1</sub> nearest to the point φ

_ψ

in the smoothed segment;

such that b(t) satisfies the fidelity criterion if any one of the following conditions holds true;

32. A computer-implemented method for entering a representation of a desired curve into a computer, the method comprising:

receiving an input of an ordered sequence of points representing the desired curve;

grouping the points of the sequence of points into one or more contiguous segments of points;

smoothing the points of each segment to generate a segment of smoothed points for each segment of points; and

fitting one or more mathematical curves to each segment of smoothed points, the one or more mathematical curves from each segment of smoothed points together forming the representation of the desired curve;

wherein fitting a curve to a segment of smoothed points comprises;

calculating a trial curve for the smoothed segment;

calculation a fidelity criterion for the trial curve on the smoothed segment; and

dividing the smoothed segment into two or more smoothed sub-segments if the trial curve does not satisfy the fidelity criterion and recursively fitting a curve to each smoothed sub-segment; and

wherein calculating the fidelity criterion comprises;

generating a sequence of trial points by sampling the trial curve;

for each point in the smoothed segment,

(a) calculating a first normalized distance from the point to a first end of the smoothed segment;

(b) finding an exact trial point that is the first normalized distance from a first end of the trial curve if such a trial point exists, and calculating an exact fidelity distance from the point to the exact trial point, where the fidelity criterion is satisfied if the exact fidelity distance is less than or equal to a fidelity tolerance;

(c) if an exact trial point is not found,

(i) finding a leading trial point and a following trial point that are consecutive trial points a second normalized distance and third normalized distance, respectively, from the first end of the trial curve, where the second normalized distance is less than the first normalized distance and the third normalized distance is greater than the first normalized distance

(ii) calculating a leading fidelity distance from the point to the leading trial point, where the fidelity criterion is satisfied if the leading fidelity distance is less than or equal to the fidelity tolerance;

(iii) calculating a following fidelity distance from the point to the following trial point, where the fidelity criterion is satisfied if the following fidelity distance is less than or equal to the fidelity tolerance;

(iv) calculating a fidelity chord between the leading trial point and the following trial point;

(v) finding a fidelity chord point on the fidelity chord that is a point on the fidelity chord closest to the point in the smoothed segment; and

(vi) calculating a chord fidelity distance from the point to the fidelity chord point, where the fidelity criterion is satisfied if the chord fidelity distance is less than or equal to a fraction of the fidelity tolerance.

33. The method of claim 32 wherein the trial curve has a predetermined mathematical form.

34. The method of claim 32 wherein the trial curve is a parametric curve.

35. The method of claim 32 wherein the trial curve is a Bezier curve.

36. A computer program, residing on a computer-readable medium, comprising instructions for causing a computer to:

receive an input of an ordered sequence of points representing the desired curve;

group the points of the sequence of points into one or more contiguous segments of points;

smooth the points of each segment only after all of said contiguous segments of points are defined by grouping to generate a segment of smoothed points for each segment of points; and

fit one or more mathematical curves to each segment of smoothed points, the one or more mathematical curves from each segment of smoothed points together forming the representation of the desired curve.

37. The program of claim 36 wherein instructions to group points into segments comprise instructions for causing a computer to:

determine which points are break points, a break point being an end point of the ordered sequence of points or a corner point within the ordered sequence of points, a corner point being a point having a high estimated curvature; and

group points between adjacent break points into single segments, where a closed curve without corner points forms a single segment.

38. The program of claim 37 wherein instructions to determine whether a point is a corner point comprise instructions for causing a computer to calculate the estimated curvature for the point from all the points in the ordered sequence of points within a certain distance of the point.

39. A computer program product, tangibly stored on a computer-readable medium, for generating a representation of a curve, the method comprising instructions operable to cause a programmable processor to:

receive an input of an ordered sequence of points representing the desired curve;

group the points of the sequence of points into one or more contiguous segments of points;

smooth the points of each segment to generate a segment of smoothed points for each segment of points; and

fit one or more mathematical curves to each segment of smoothed points, the one or more mathematical curves from each segment of smoothed points together forming the representation of the desired curve;

wherein instructions to fit a curve to a segment of smoothed points comprise instructions to;

calculate a trial curve for the smoothed segment;

calculate a fidelity criterion for the trial curve on the smoothed segment; and

divide the smoothed segment into two or more smoothed sub-segments if the trial curve does not satisfy the fidelity criterion and recursively fit a curve to each smoothed sub-segment; and

wherein instructions to calculate the fidelity criterion comprise instructions to;

generate a sequence of trial points by sampling the trial curve;

for each point in the smoothed segment,

(a) calculate a first normalized distance from the point to a first end of the smoothed segment;

(b) find an exact trial point that is the first normalized distance from a first end of the trial curve if such a trial point exists, and calculate an exact fidelity distance from the point to the exact trial point, where the fidelity criterion is satisfied if the exact fidelity distance is less than or equal to a fidelity tolerance;

(c) if an exact trial point is not found,

(i) find a leading trial point and a following trial point that are consecutive trial points a second normalized distance and third normalized distance, respectively, from the first end of the trial curve, where the second normalized distance is less than the first normalized distance and the third normalized distance is greater than the first normalized distance

(ii) calculate a leading fidelity distance from the point to the leading trial point, where the fidelity criterion is satisfied if the leading fidelity distance is less than or equal to the fidelity tolerance;

(iii) calculate a following fidelity distance from the point to the following trial point, where the fidelity criterion is satisfied if the following fidelity distance is less than or equal to the fidelity tolerance;

(iv) calculate a fidelity chord between the leading trial point and the following trial point;

(v) find a fidelity chord point on the fidelity chord that is a point on the fidelity chord closest to the point in the smoothed segment; and

(vi) calculate a chord fidelity distance from the point to the fidelity chord point, where the fidelity criterion is satisfied if the chord fidelity distance is less than or equal to a fraction of the fidelity tolerance.