Efficient re-sampling of discrete curves

• US 20030194144A1
• Filed: 10/03/2002
• Published: 10/16/2003
• Est. Priority Date: 04/10/2002
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: M. Crotty, Kevin, Nair, Dinesh, Wenzel, Lothar, Schmidt, Darren R., Rajagopal, Ram, Kumar, Satish V., Fisher, Matthew S.
• Granted Patent: US 7,120,301 B2
• Time in Patent Office: Days
• US Class Current: 382/242
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G06V 10/752 Contour matching

Abstract

System and method for re-sampling discrete curves, thereby efficiently characterizing point sets or curves in a space. The method may also provide improved means for mapping point sets or curves to new point sets or curves for curve matching. A weight vector or function is determined based on a plurality of discrete curves, e.g., from one or more template data sets or images. The weight function enhances differences between weighted discrete curves. A set of orthonormal polynomials is determined based on the computed weight function, where the set of orthonormal polynomials comprises a set of orthogonal eigenfunctions of a Sturm-Liouville differential equation. Values for a plurality of zeros for one of the set of orthonormal polynomials is determined that comprise resampling points for the plurality of discrete curves. Each of the plurality of discrete curves is resampled based on the determined values of the plurality of zeros.

Claims

1. A computer-implemented method for re-sampling discrete curves, the method comprising:

normalizing a plurality of discrete curves, wherein each discrete curve comprises a respective sequence of points;

computing a weight function based on the plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

determining a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of basis functions;

determining values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

re-sampling each of the plurality of discrete curves based on the determined values of the plurality of zeros.

2. The method of claim 1, further comprising:

prior to said normalizing, uniformly re-sampling each of the plurality of discrete curves, wherein, after said uniform re-sampling, each of the plurality of discrete curves has the same number of points.

3. The method of claim 1, wherein each respective sequence of points comprises a sequence of complex values.

4. The method of claim 1, wherein said normalizing comprises normalizing one or more of:

energy of the discrete curves; and

length of the discrete curves.

5. The method of claim 1, wherein said computing the weight function comprises:

computing a weight vector w, such that

<

c_n,c_m>

_w=δ

_nm

wherein c_n and c_m comprise any two discrete curves of the normalized discrete curves; and

wherein δ

_nm is the Kronecker delta.

6. The method of claim 1, wherein components of the weight function are non-negative.

7. The method of claim 1, wherein the weight function comprises a Sturm-Liouville weight function.

8. The method of claim 1, wherein the re-sampling points for the plurality of discrete curves comprise a set of optimal re-sampling points for the plurality of discrete curves.

9. The method of claim 1, wherein the re-sampling points for the plurality of discrete curves comprise a re-sampling scheme that enhances differences between the plurality of discrete curves.

10. The method of claim 1, wherein the plurality of discrete curves comprise one or more of:

image objects from one or more images; and

data objects from one or more data sets.

11. A carrier medium which stores program instructions for re-sampling discrete curves, wherein the program instructions are executable by a processor to perform:

normalizing a plurality of discrete curves, wherein each discrete curve comprises a respective sequence of points;

computing a weight function based on the plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

determining a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of basis functions;

determining values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

re-sampling each of the plurality of discrete curves based on the determined values of the plurality of zeros.

12. The carrier medium of claim 11, wherein the program instructions are further executable by a processor to perform:

prior to said normalizing, uniformly re-sampling each of the plurality of discrete curves, wherein, after said uniform re-sampling, each of the plurality of discrete curves has the same number of points.

13. The carrier medium of claim 11, wherein each respective sequence of points comprises a sequence of complex values.

14. The carrier medium of claim 11, wherein said normalizing comprises normalizing one or more of:

energy of the discrete curves; and

length of the discrete curves.

15. The carrier medium of claim 11, wherein said computing the weight function comprises:

computing a weight vector w, such that

<

c_n,c_m>

_w=δ

_nm

wherein c_n and c_m comprise any two discrete curves of the normalized discrete curves; and

wherein δ

_nm is the Kronecker delta.

16. The carrier medium of claim 11, wherein components of the weight function are non-negative.

17. The carrier medium of claim 11, wherein the weight function comprises a Sturm-Liouville weight function.

18. The carrier medium of claim 11, wherein the re-sampling points for the plurality of discrete curves comprise a set of optimal re-sampling points for the plurality of discrete curves.

19. The carrier medium of claim 11, wherein the re-sampling points for the plurality of discrete curves comprise a re-sampling scheme that enhances differences between the plurality of discrete curves.

20. The carrier medium of claim 11, wherein the plurality of discrete curves comprise one or more of:

image objects from one or more images; and

data objects from one or more data sets.

21. A system for re-sampling discrete curves, comprising:

a computer system, comprising;

a processor; and

a memory medium coupled to the processor; and

wherein the memory medium stores program instructions which are executable by the processor to;

normalize a plurality of discrete curves, wherein each discrete curve comprises a respective sequence of points;

compute a weight function based on the plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

determine a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of basis functions;

determine values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

re-sample each of the plurality of discrete curves based on the determined values of the plurality of zeros.

22. A system for re-sampling discrete curves, comprising:

means for normalizing a plurality of discrete curves, wherein each discrete curve comprises a respective sequence of points;

means for computing a weight function based on the plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

means for determining a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of basis functions;

means for determining values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

means for re-sampling each of the plurality of discrete curves based on the determined values of the plurality of zeros.

23. A computer-implemented method for re-sampling discrete curves, the method comprising:

receiving one or more images, wherein each image contains one or more image objects;

determining a plurality of discrete curves from the one or more images, wherein each of the discrete curves corresponds to one of the one or more image objects, and wherein each discrete curve comprises a respective sequence of points;

normalizing each of the plurality of discrete curves,

computing a weight function based on the plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

determining a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of basis functions;

determining values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

re-sampling each of the plurality of discrete curves based on the determined values of the plurality of zeros.

24. A computer-implemented method for re-sampling discrete curves, the method comprising:

receiving one or more data sets, wherein each data set contains one or more data objects;

determining a plurality of discrete curves from the one or more data sets, wherein each of the discrete curves corresponds to one of the one or more data objects, and wherein each discrete curve comprises a respective sequence of points;

normalizing each of the plurality of discrete curves,

computing a weight function based on the plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

determining a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of basis functions;

determining values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

re-sampling each of the plurality of discrete curves based on the determined values of the plurality of zeros.

25. A computer-implemented method for re-sampling discrete curves, the method comprising:

computing a weight function based on a plurality of discrete curves, wherein the weight function enhances differences between weighted discrete curves;

determining a set of orthonormal polynomials based on the computed weight function, wherein the set of orthonormal polynomials comprises a set of orthogonal eigenfunctions of a Sturm-Liouville differential equation;

determining values for a plurality of zeros for one of the set of orthonormal polynomials, wherein the values for the plurality of zeros comprise re-sampling points for the plurality of discrete curves; and

re-sampling each of the plurality of discrete curves based on the determined values of the plurality of zeros.