System and method for signal matching and characterization

• US 20020150298A1
• Filed: 01/12/2001
• Published: 10/17/2002
• Est. Priority Date: 01/12/2001
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Nair, Dinesh, Wenzel, Lothar, Rajagopal, Ram, Schmidt, Darren
• Granted Patent: US 6,963,667 B2
• Time in Patent Office: Days
• US Class Current: 382/209
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 2218/00 Aspects of pattern recognition specially adapted for signal processing
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A system and method for selecting a best match of a received input signal from a set of candidate signals, wherein two or more of the candidate signals are uncorrelated. In a preprocessing phase a unified signal transform (UST) is determined from the candidate signals. The UST converts each candidate signal to a generalized frequency domain. The UST is applied at a generalized frequency to each candidate signal to calculate corresponding generalized frequency component values (GFCVs) for each candidate signal. At runtime, the input signal of interest is received, and the UST is applied at the generalized frequency to the input signal of interest to calculate a corresponding GFCV. The best match is determined between the GFCV of the input signal of interest and the GFCVs of each of the set of candidate signals. Finally, information indicating the best match candidate signal from the set of candidate signals is output.

Claims

1. A computer-implemented method for determining a “

best match”

of an input signal of interest from a set of candidate signals, wherein two or more of the candidate signals are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate signals;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate signals to calculate a corresponding at least one generalized frequency component value for each of the set of candidate signals;

receiving the input signal of interest;

applying the unified signal transform for the at least one generalized frequency to the input signal of interest to calculate a corresponding at least one generalized frequency component value for the input signal of interest;

determining a best match between the at least one generalized frequency component value of the input signal of interest and the at least one generalized frequency component value of each of the set of candidate signals; and

outputting information indicating a best match candidate signal from the set of candidate signals.

2. The method of claim 1,

wherein said determining a best match between the at least one generalized frequency component value of the input signal of interest and the at least one generalized frequency component value of each of the set of candidate signals comprises:

subtracting each of the respective at least one generalized frequency component values of each candidate signal from the at least one generalized frequency component value of the input signal of interest; and

determining a smallest difference between each of the respective at least one generalized frequency component values of each candidate signal and the at least one generalized frequency component value of the input signal of interest;

wherein a candidate signal corresponding to the smallest difference is the best match candidate signal.

3. The method of claim 1,

wherein the unified signal transform includes a set of basis functions which describe an algebraic structure of the set of candidate signals.

4. The method of claim 1,

wherein the unified signal transform is operable to convert each of the set of candidate signals to a generalized frequency domain.

5. The method of claim 1,

wherein the unified signal transform is operable to convert each of the set of candidate signals into a representation of generalized basis functions, wherein the basis functions represent the algebraic structure of the set of candidate signals.

6. The method of claim 1,

wherein the unified signal transform is operable to decompose the signal into generalized basis functions, wherein the basis functions represent the algebraic structure of the set of candidate signals.

7. The method of claim 1,

wherein all of the candidate signals are uncorrelated with each other.

8. The method of claim 1,

wherein the input signal of interest and the candidate signals are one of 1-dimensional signals, 2-dimensional signals, or 3-dimensional signals.

9. The method of claim 1,

wherein the input signal of interest and the candidate signals are of a dimensionality greater than 3.

10. The method of claim 1,

wherein the input signal of interest and the candidate signals comprise one or more of image data, measurement data, acoustic data, seismic data, financial data, stock data, futures data, business data, scientific data, medical data, insurance data, musical data, biometric data, and telecommunications signals.

11. The method of claim 1,

wherein said determining a unified signal transform for the set of candidate signals comprises:

forming a matrix B from all of the values of the candidate signals, wherein each of the candidate signals comprises a corresponding column of the matrix B;

defining a matrix B′

, wherein the matrix B′

comprises a column-wise cyclic shifted matrix B;

defining a matrix A, wherein the matrix A comprises a cyclic shift matrix operator, wherein multiplying matrix A times matrix B performs a column-wise cyclic shift on matrix B, thereby generating matrix B′

, wherein AB=B′

, wherein A=B′

B<sup>−

1</sup>, wherein B<sup>−

1</sup> comprises an inverse matrix of matrix B, and wherein A^N=an N×

N identity matrix, I;

performing a Jordan decomposition on A=B′

B<sup>−

1</sup>, thereby generating a relation A=X_BΛ

X_B<sup>−

1</sup>, wherein X_B comprises a matrix of normalized columnar eigenvectors of matrix B, wherein Λ

comprises a diagonal matrix of eigenvalues of matrix B, and wherein X_B<sup>−

1</sup> comprises an inverse matrix of matrix X_B; and

calculating matrix X_B<sup>−

1</sup>, wherein the matrix X_B<sup>−

1</sup> comprises the unified signal transform.

12. The method of claim 11,

wherein the set of candidate signals comprises a number of candidate signals, wherein each of the candidate signals comprises a number of values, and wherein the number of values is equal to the number of candidate signals.

13. The method of claim 12, wherein the matrix B is regular.

14. The method of claim 1, further comprising:

receiving an initial set of N candidate signals before said determining a unified signal transform from the set of candidate signals, wherein at least one of said initial set of candidate signals comprises a set of M values, wherein M is greater or less than N;

15. The method of claim 14, wherein M is less than N, the method further comprising:

providing additional N−

M values for the at least one of said initial set of candidate signals, thereby generating said set of candidate signals, wherein each one of said set of candidate signals comprises N values.

16. The method of claim 15, wherein said providing additional N−

M values comprises interpolating two or more of the M values to generate the additional N−

M values.

17. The method of claim 15, wherein said providing additional N−

M values comprises extrapolating two or more of the M values to generate the additional N−

M values.

18. The method of claim 14, wherein M is less than N, the method further comprising:

fitting a curve to the M values for the at least one of said initial set of candidate signals;

sampling the curve to generate N values for the at least one of said initial set of candidate signals, thereby generating said set of candidate signals, wherein each one of said set of candidate signals comprises N values.

19. The method of claim 1, further comprising:

receiving an initial set of M candidate signals before said determining a unified signal transform from the set of candidate signals, wherein each of said initial set of candidate signals comprises a set of N values, and wherein M is less than N.

20. The method of claim 19, the method further comprising:

providing an additional N−

M candidate signals to said initial set of candidate signals, thereby generating said set of candidate signals, wherein said set of candidate signals comprises N candidate signals, and wherein each one of said set of candidate signals comprises N values.

21. The method of claim 19, wherein said providing additional N−

M candidate signals to said initial set of candidate signals comprises providing N−

M arbitrary candidate signals.

22. The method of claim 1, wherein said outputting information comprises displaying the information on a display screen.

23. The method of claim 1, wherein said outputting information comprises storing the best match candidate signal in a memory medium of a computer system.

24. The method of claim 1, further comprising:

processing the best match candidate signal to determine if the best match candidate is an acceptable match.

25. The method of claim 1, further comprising:

processing the best match candidate signal to determine characteristics of the received input signal of interest.

27. The memory medium of claim 26,

wherein the signal transform includes a set of basis functions which describe an algebraic structure of the set of candidate signals.

28. The memory medium of claim 26,

wherein the signal transform is operable to convert each of the set of candidate signals to a generalized frequency domain.

29. The memory medium of claim 26,

wherein the signal transform is operable to convert each of the set of candidate signals into a representation comprising generalized basis functions, wherein the basis functions represent the algebraic structure of the set of candidate signals.

30. The memory medium of claim 26,

wherein the signal transform is operable to decompose the signal into a form represented by generalized basis functions, wherein the basis functions represent the algebraic structure of the set of candidate signals.

31. The memory medium of claim 26,

wherein the signal transform is the unified signal transform.

32. The memory medium of claim 26,

wherein all of the candidate signals are uncorrelated with each other.

33. The memory medium of claim 26,

wherein the input signal of interest and the candidate signals are one of 1-dimensional signals, 2-dimensional signals, or 3-dimensional signals.

34. The memory medium of claim 26,

wherein the input signal of interest and the candidate signals are of a dimensionality greater than 3.

35. The memory medium of claim 26,

wherein the input signal of interest and the candidate signals comprise one or more of image data, measurement data, acoustic data, seismic data, financial data, stock data, futures data, business data, scientific data, medical data, insurance data, musical data, biometric data, and telecommunications signals.

36. The memory medium of claim 26, wherein said outputting information comprises displaying the information on a display screen.

37. The memory medium of claim 26, wherein said outputting information comprises storing the best match candidate signal in a memory medium of a computer system.

26. A memory medium comprising program instructions which are executable to determine a “

closest match”

between an input signal of interest and one of a set of candidate signals, wherein two or more of the candidate signals are uncorrelated, wherein the program instructions are executable to perform;

determining a signal transform for the set of candidate signals;

calculating one or more values of the signal transform applied to each of the set of candidate signals at at least one generalized frequency

receiving the input signal of interest;

calculating one or more values of the signal transform applied to the input signal of interest at the at least one generalized frequency;

determining a best match between the one or more values of the transformation of the input signal of interest and the one or more values of the transformation for each of the set of candidate signals; and

outputting information indicating a closest match candidate signal of the set of candidate signals.

38. A computer-implemented method for determining a “

best match”

of an input image of interest from a set of candidate images, wherein two or more of the candidate images are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate images;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate images to calculate a corresponding at least one generalized frequency component value for each of the set of candidate images;

receiving the input image of interest;

applying the unified signal transform for the at least one generalized frequency to the input image of interest to calculate a corresponding at least one generalized frequency component value for the input image of interest;

determining a best match between the at least one component value of the input image of interest and the at least one component value of each of the set of candidate images; and

outputting information indicating a best match candidate image from the set of candidate images.

39. A computer-implemented method for determining a “

best match”

of an input data set of interest from a set of candidate data sets, wherein two or more of the candidate data sets are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate data sets;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate data sets to calculate a corresponding at least one generalized frequency component value for each of the set of candidate data sets;

receiving the input data set of interest;

applying the unified signal transform for the at least one generalized frequency to the input data set of interest to calculate a corresponding at least one generalized frequency component value for the input data set of interest;

determining a best match between the at least one component value of the input data set of interest and the at least one component value of each of the set of candidate data sets; and

outputting information indicating a best match candidate data set from the set of candidate data sets.

40. A computer-implemented method for determining a “

best match”

of an input biometric signal of interest from a set of candidate biometric signals, wherein two or more of the candidate biometric signals are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate biometric signals;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate biometric signals to calculate a corresponding at least one generalized frequency component value for each of the set of candidate biometric signals;

receiving the input biometric signal of interest;

applying the unified signal transform for the at least one generalized frequency to the input biometric signal of interest to calculate a corresponding at least one generalized frequency component value for the input biometric signal of interest;

determining a best match between the at least one component value of the input biometric signal of interest and the at least one component value of each of the set of candidate biometric signals; and

outputting information indicating a best match candidate biometric signal from the set of candidate biometric signals.

41. A computer-implemented method for determining a “

best match”

of an input stock history waveform of interest from a set of candidate stock behavior waveforms, wherein two or more of the candidate stock behavior waveforms are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate stock behavior waveforms;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate stock behavior waveforms to calculate a corresponding at least one generalized frequency component value for each of the set of candidate stock behavior waveforms;

receiving the input stock history waveform of interest;

applying the unified signal transform for the at least one generalized frequency to the input stock history waveform of interest to calculate a corresponding at least one generalized frequency component value for the input stock history waveform of interest;

determining a best match between the at least one component value of the input stock history waveform of interest and the at least one component value of each of the set of candidate stock behavior waveforms; and

outputting information indicating a best match candidate stock history waveform from the set of candidate stock behavior waveforms.

42. A computer-implemented method for determining a “

best match”

of an input telecommunications signal of interest from a set of candidate telecommunications signals, wherein two or more of the candidate telecommunications signals are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate telecommunications signals;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate telecommunications signals to calculate a corresponding at least one generalized frequency component value for each of the set of candidate telecommunications signals;

receiving the input telecommunications signal of interest;

applying the unified signal transform for the at least one generalized frequency to the input telecommunications signal of interest to calculate a corresponding at least one generalized frequency component value for the input telecommunications signal of interest;

determining a best match between the at least one component value of the input telecommunications signal of interest and the at least one component value of each of the set of candidate telecommunications signals; and

outputting information indicating a best match candidate telecommunications signal from the set of candidate telecommunications signals.

43. A computer-implemented method for determining a “

best match”

of an input medical image of interest from a set of candidate medical images, wherein two or more of the candidate medical images are uncorrelated, the method comprising;

determining a unified signal transform from the set of candidate medical images;

applying the unified signal transform for at least one generalized frequency to each of the set of candidate medical images to calculate a corresponding at least one generalized frequency component value for each of the set of candidate medical images;

receiving the input medical image of interest;

applying the unified signal transform for the at least one generalized frequency to the input medical image of interest to calculate a corresponding at least one generalized frequency component value for the input medical image of interest;

determining a best match between the at least one component value of the input medical image of interest and the at least one component value of each of the set of candidate medical images; and

outputting information indicating a best match candidate medical image from the set of candidate medical images.

44. A computer-implemented method for determining a “

best match”

of an input signal of interest from a set of candidate signals, wherein two or more of the candidate signals are uncorrelated, the method comprising;

receiving the input signal of interest;

applying a unified signal transform for at least one generalized frequency to the input signal of interest to calculate a corresponding at least one generalized frequency component value for the input signal of interest, wherein the unified signal transform is determined from the set of candidate signals;

determining a best match between the at least one generalized frequency component value of the input signal of interest and at least one generalized frequency component value of each of the set of candidate signals; and

outputting information indicating a best match candidate signal from the set of candidate signals.