Granted Patent B1

US 8,014,630 · App. 11/799,946 · Granted Sep 6, 2011

Abstract

Claims (84)

1. A computerized method for encoding source data, the method comprising:

defining a source polygon using parametric representation associated with the source data;

identifying one or more portions of the source polygon, wherein each portion of the source polygon comprises a plurality of sample points;

passing a filter throughout a sequence of samples representing the source polygon to obtain a filtered polygon;

performing, by a processor, piecewise re-parameterization of each portion of the source polygon using a corresponding portion of the filtered polygon to obtain an updated sequence of samples representing the source polygon; and

iteratively repeating, by the processor, the passing of the filter and the piecewise re-parameterization until a convergence condition is satisfied, to provide encoded data.

2. The method of claim 1 wherein the source data is available in vector-graphic form or convertible into vector-graphic form.

3. The method of claim 1 wherein the encoded data comprises a last updated sequence of samples representing the source polygon, the source polygon and a last filtered polygon, or the last filtered polygon.

4. The method of claim 1 further comprising:

defining a sampling rate for each of the identified one or more portions of the source polygon; and

re-sampling each of the identified one or more portions of the source polygons based on a corresponding sampling rate.

5. The method of claim 4 wherein the filter is passed throughout an entire sequence of samples representing a re-sampled source polygon without considering a division into portions.

6. The method of claim 1 wherein the source polygon consists of a single portion.

7. The method of claim 1 wherein performing the piecewise re-parameterization of each portion of the source polygon comprises:

for each sample in a re-parameterized portion, computing a distance along the filtered polygon from a corresponding sample of the filtered polygon to an initial point, the initial point being a beginning of the filtered polygon or a beginning of the re-parameterized portion;

storing, for each portion, resulting distances in a corresponding part of a re-parameterization table;

normalizing, for each portion, the stored distances using a corresponding length-normalizing factor; and

relocating samples along the source polygon in the portion being re-parameterized using normalized distances from a corresponding part of the re-parameterization table.

8. The method of claim 7 further comprising:

keeping boundary samples of the re-parameterized portion unchanged while relocating the samples along the source polygon in the re-parameterized portion.

9. The method of claim 1 further comprising:

reconstructing the source data from the encoded data.

10. The method of claim 9 wherein reconstructing the source data comprises:

forming an initial interpolation polygon using a sequence of samples within the encoded data as knots;

up-sampling the interpolation polygon by inserting a set of extra samples in each interval between every two consecutive knots of the interpolation polygon, a number of extra samples being the same in each interval;

passing a filter throughout a sequence of samples representing the up-sampled interpolation polygon;

performing a piecewise update of each interval of the interpolation polygon using a corresponding portion of the filtered polygon as a reference interval; and

repeating the passing of the filter and the piecewise update of each interval until a reconstruction condition is satisfied, wherein a last updated interpolation polygon represents reconstructed source data.

11. The method of claim 10 wherein performing the piecewise update of each interval of the interpolation polygon comprises:

transforming a corresponding reference interval to fit between knots of an interpolation interval representing a current interval of the interpolation polygon.

12. The method of claim 11 wherein performing the piecewise update of each interval of the interpolation polygon further comprises:

if a stability condition for the interpolation interval is not violated, replacing the interpolation interval with the transformed reference interval; and

if the stability condition is violated, keeping the interpolation interval unchanged.

13. The method of claim 12 wherein the stability condition requires that an angle of rotation and a scaling factor for the reference interval be within corresponding thresholds when the reference interval is transformed to fit between the knots of the interpolation interval.

14. The method of claim 10 further comprising;

adjusting filtering parameters based on a specific application while repeating the passing of the filter.

15. The method of claim 1 further comprising:

adjusting filtering parameters during iterations based on a specific application.

16. The method of claim 1 wherein the parametric representation associated with the source data comprises spatial and non-spatial parts of the source data, the non-spatial parts being used as additional spatial coordinates weighted with adjustable proportionality coefficients.

17. A non-transitory computer-readable medium having executable instructions to cause a computer system to perform a method for encoding source data, the method comprising:

defining a source polygon using parametric representation associated with the source data;

identifying one or more portions of the source polygon, wherein each portion of the source polygon comprises a plurality of sample points;

passing a filter throughout a sequence of samples representing the source polygon to obtain a filtered polygon;

performing piecewise re-parameterization of each portion of the source polygon using a corresponding portion of the filtered polygon to obtain an updated sequence of samples representing the source polygon; and

iteratively repeating the passing of the filter and the piecewise re-parameterization until a convergence condition is satisfied, to provide encoded data.

18. The computer-readable medium of claim 17 wherein the method further comprises:

defining a sampling rate for each of the portions; and

re-sampling each of the portions based on a corresponding sampling rate.

19. The computer-readable medium of claim 17 wherein performing the piecewise re-parameterization of each portion of the source polygon comprises:

for each sample in a re-parameterized portion, computing a distance along the filtered polygon from a corresponding sample of the filtered polygon to an initial point, the initial point being a beginning of the filtered polygon or a beginning of the re-parameterized portion;

storing, for each portion, resulting distances in a corresponding part of a re-parameterization table;

normalizing, for each portion, the stored distances using a corresponding length-normalizing factor; and

relocating samples along the source polygon in the portion being re-parameterized using normalized distances from a corresponding part of the re-parameterization table.

20. The computer-readable medium of claim 17 wherein the method further comprises reconstructing the source data from the encoded data by:

forming an initial interpolation polygon using a sequence of samples within the encoded data as knots;

up-sampling the interpolation polygon by inserting a set of extra samples in each interval between every two consecutive knots of the interpolation polygon, a number of extra samples being the same in each interval;

passing a filter throughout a sequence of samples representing the up-sampled interpolation polygon;

performing a piecewise update of each interval of the interpolation polygon using a corresponding portion of the filtered polygon as a reference interval; and

repeating the passing of the filter and the piecewise update of each interval until a reconstruction condition is satisfied, wherein a last updated interpolation polygon represents reconstructed source data.

21. The computer-readable medium of claim 20 wherein performing the piecewise update of each interval of the interpolation polygon comprises:

transforming a corresponding reference interval to fit between knots of an interpolation interval representing a current interval of the interpolation polygon;

if a stability condition for the interpolation interval is not violated, replacing the interpolation interval with the transformed reference interval; and

if the stability condition is violated, keeping the interpolation interval unchanged.

22. A system for encoding source data, comprising:

a memory; and

an encoder to define a source polygon based on a parametric representation associated with the source data, to identify one or more portions in the source polygon, wherein each portion in the source polygon comprises a plurality of sample points, to pass a filter throughout the source polygon, to perform piecewise re-parameterization of each segment of the source polygon to obtain an updated parametric representation of the source polygon, and to iteratively repeat the passing of the filter and the piecewise re-parameterization until a convergence condition is satisfied, to provide encoded data, wherein the encoder is to perform the piecewise re-parameterization of each portion of the source polygon by

for each sample in a re-parameterized portion, computing a distance along the filtered polygon from a corresponding sample of the filtered polygon to an initial point, the initial point being a beginning of the filtered polygon or a beginning of the re-parameterized portion,

storing, for each portion, resulting distances in a corresponding part of a re-parameterization table,

normalizing, for each portion, the stored distances using a corresponding length-normalizing factor, and

relocating samples along the source polygon in the portion being re-parameterized using normalized distances from a corresponding part of the re-parameterization table.

23. The system of claim 22 wherein the encoder is further to define a sampling rate for each of the portions, and to re-sample each of the portions based on a corresponding sampling rate.

24. A system for encoding source data, comprising:

a memory;

an encoder to define a source polygon based on a parametric representation associated with the source data, to identify one or more portions in the source polygon, wherein each portion in the source polygon comprises a plurality of sample points, to pass a filter throughout the source polygon, to perform piecewise re-parameterization of each segment of the source polygon to obtain an updated parametric representation of the source polygon, and to iteratively repeat the passing of the filter and the piecewise re-parameterization until a convergence condition is satisfied, to provide encoded data; and

a decoder to reconstruct the source data from the encoded data including

forming an initial interpolation polygon using a sequence of samples within the encoded data as knots;

up-sampling the interpolation polygon by inserting a set of extra samples in each interval between every two consecutive knots of the interpolation polygon, a number of extra samples being the same in each interval;

passing a filter throughout a sequence of samples representing the up-sampled interpolation polygon;

performing a piecewise update of each interval of the interpolation polygon using a corresponding portion of the filtered polygon as a reference interval; and

repeating the passing of the filter and the piecewise update of each interval until a reconstruction condition is satisfied, wherein a last updated interpolation polygon represents reconstructed source data.

25. The system of claim 24 wherein the decoder is to perform the piecewise update of each interval of the interpolation polygon by:

transforming a corresponding reference interval to fit between knots of an interpolation interval representing a current interval of the interpolation polygon;

if a stability condition for the interpolation interval is not violated, replacing the interpolation interval with the transformed reference interval; and

if the stability condition is violated, keeping the interpolation interval unchanged.

Assignments (10)