Smoothing and fitting point sequences
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
39 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31)
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 si, 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
- 1, wherein the noise filter is a degree d λ
-
25. The method of claim 24 wherein the filtering is performed iteratively by performing d passes on the ordered sequence of points si to form a sequence of filtered points sij, 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 si, where i=0, . . . , n−
- 1, where finding corner points includes comparing a corner angle tolerance c with a curvature ci, −
1<
ci<
1, at each point si in the sequence, where corners are points si where ci<
c,and further where a chord-length li for each point si is defined as
- 1, where finding corner points includes comparing a corner angle tolerance c with a curvature ci, −
-
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 tz that is a closed sequence comprises;
calculating a frequency-space representation {circumflex over (t)}z of the segment of points tz;
calculating a frequency-space representation û
;
z of a smoothed segment uz by applying a low-pass transfer function g to {circumflex over (t)}z;
calculating the smoothed segment uz by taking an inverse discrete Fourier transform of û
;
z;
where {circumflex over (t)}z is defined as and where z is odd and where z is even and further where for each {circumflex over (t)}z, vz is a corresponding eigenvalue of an eigenvector associated with {circumflex over (t)}z, where vz is defined as and further where, for frequencies 0<
v<
2, with constants w and g0 chosen such that 1<
w<
m−
1 and 0<
g0<
1, the low-pass transfer function g is defined such thatif v<
vw
- 1, the smoothing for a segment of m points tz that is a closed sequence comprises;
-
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 tz that is an open sequence comprises;
subtracting a linear trend from the segment of points tz 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 uz;
where the linear trend is subtracted as follows and where {circumflex over (t)}′
z is defined asand further where for each {circumflex over (t)}′
z, vz is a corresponding eigenvalue of an eigenvector associated with {circumflex over (t)}′
z, where vz is defined as
vm−
1=0; and
further where, for frequencies 0<
v<
2, with constants w and g0 chosen such that 1<
w<
m−
1 and 0<
g0<
1, the low-pass transfer function g is defined such thatif v<
vw
- 1, the smoothing for a segment of m points tz that is an open sequence comprises;
-
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.
- , a chord-length θ
-
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, Φ
ωψ is a unique point such thatand where Ω
ωψ is a point on a line through Φ
ωψ and Φ
ωψ +1 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. - View Dependent Claims (33, 34, 35)
-
-
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. - View Dependent Claims (37, 38)
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.
-
Specification