System and method for estimating a shift between two signals where one signal is known in advance

• US 6,665,335 B1
• Filed: 04/20/2000
• Issued: 12/16/2003
• Est. Priority Date: 11/08/1999
• Status: Expired due to Term

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Wenzel, Lothar, Rajagopal, Ram
• Primary Examiner(s): VO, DON NGUYEN
• Application Number:
  US09/553,200
• Time in Patent Office: 1,335 Days
• Field of Search: 375/224, 375/371, 375/226, 702/189, 382/225
• US Class Current: 375/224
• CPC Class Codes: G01S 7/292 Extracting wanted echo-signals
• CPC Class Codes: G06F 2218/12 Classification; Matching

Abstract

A system and method for estimating the shift between two signals. The shift estimation system method comprises: (a) receiving a first signal, where the first signal may be represented as a vector g having N components; (b) projecting the vector g to a space with dimension K less than N to obtain a projection vector X having K components; (c) computing measures of distance between the projection vector X and each vector in a set of stored vectors; (d) determining a stored vector p in the set of stored vectors with a minimum distance to the projection vector X. The stored vectors are generated from a template signal f, also represented as a vector with N components, by projecting shifted versions of the template signal f to the space of dimension K. The shifted versions of the template signal f may be referred to as shifted template vectors, or simply, shift vectors. The shift estimation method may provide a shift value corresponding to the shifted template vector which generates the stored vector p as an estimate for the shift between the received signal and the template signal f. The shift value defines the amount by which the template signal f must be shifted to obtain the shifted template vector.

Claims

1. A method for estimating a shift between two signals, the method comprising:

(a) receiving a first signal g, wherein the first signal g comprises a sequence of values which are representable as a vector g having N components;

(b) projecting the vector g to a space with dimension K less than N to obtain a projection vector X having K components;

(c) computing measures of distance between the projection vector X and a set of stored vectors, wherein each of the stored vectors is associated with a corresponding vector in a collection of shift vectors, wherein each of the shift vectors is a shifted version of a second signal f;

(d) determining a first stored vector in the set of stored vectors with a minimum distance to the projection vector X based on the measures of distance;

(e) providing a first shift value corresponding to the first stored vector, wherein the first shift value is an estimate of a shift between the first signal g and the second signal f.

2. The method of claim 1, wherein said shift represents a time-delay between the first signal g and the second signal f.

3. The method of claim 1 further comprising generating the set of stored vectors, wherein said generating comprises projecting the collection of shift vectors to the space with dimension K less than N.

4. The method of claim 3, wherein said first stored vector is generated by projection of a first shift vector in said collection of shift vectors, wherein the first shift value defines an amount by which the second signal f is shifted to obtain the first shift vector.

5. The method of claim 3 wherein said projecting the collection of shift vectors to the space comprises multiplying each shift vector in said collection by a matrix C.

6. The method of claim 5, wherein said projecting the vector g to a space to obtain a projection vector X comprises multiplying the vector g by the matrix C.

7. The method of claim 5 further comprising computing the matrix C prior to said projecting the vector g to the space with dimension K less than N, wherein said computing the matrix C includes performing an iterative search to determine a first matrix which maximizes an objective function.

8. The method of claim 7, wherein a simulated annealing algorithm is used to perform said iterative search.

9. The method of claim 7, wherein each iteration of the iterative search comprises evaluating the objective function on a current iterate matrix Y, wherein said evaluating comprises:

multiplying the set of shift vectors by the current iterate matrix Y to generate a set of image vectors;

computing a minimal distance between the image vectors in the set of image vectors;

computing a noise object size associated with the current iterate matrix Y;

computing a ratio comprising the minimal distance and the noise object size.

10. The method of claim 9, wherein said computing a noise object size comprises computing the sum of the squares of the elements of the current iterate matrix Y.

11. The method of claim 5 further comprising computing the matrix C prior to said projecting the vector g to the space with dimension K less than N, wherein said computing the matrix C comprises:

computing a Fourier transform of the second signal f;

identifying a collection of K/2 distinct integers in the range from 1 to N−

1 which maximize a sum of magnitudes of the Fourier transform evaluated on the collection of K/2 distinct integers subject to a spanning condition;

for each integer m of the K/2 distinct integers, assigning the cosine and sine waveforms with frequency m to a pair of columns of matrix C.

12. The method of claim 11, wherein the spanning condition is that the greatest common divisor of N and the collection of K/2 distinct integers is one.

13. The method of claim 11, wherein the spanning condition is that at least one of the K/2 distinct integer is relatively prime to N.

14. The method of claim 1, wherein each of the shift vectors are circularly-shifted versions of second signal f.

15. The method of claim 1, wherein said computing measures of distance between the projection vector X and the set of stored vectors comprises computing an L¹ distances between the projection vector X and each vector in the set of stored vectors.

16. The method of claim 1, wherein said computing measures of distance between the projection vector X and the set of stored vectors comprises computing dot products between the projection vector X and each vector in the set of stored vectors.

17. The method of claim 1, wherein (a), (b), (c), (d) and (e) are implemented by a processor executing under the control of a software shift estimation routine.

18. The method of claim 1, wherein (a), (b), (c), (d) and (e) are implemented by a Field Programmable Gate Array (FPGA).

19. The method of claim 1, wherein the first signal g comprises first pixel data extracted from a first image, and the second signal f comprises second pixel data extracted from a second image, wherein said first shift value indicates an estimated orientation of the first image with respect to the second image.

20. The method of claim 1, wherein (a), (b), (c), (d) and (e) are performed repeatedly for a series of signals including the first signal g.

21. The method of claim 1, wherein said determining a first stored vector in the set of stored vectors with a minimum distance to the projection vector X comprises:

computing dot products between the projection vector X and each of the stored vectors; and

selecting the stored vector in the set of stored vectors which maximizes the dot projects as the first stored vector.

22. The method of claim 1, wherein the first signal g comprises samples of received radar reflection, wherein the second signal f comprises samples of a transmitted radar pulse, wherein said first shift value indicates an estimated time of propagation between transmission of the transmitted radar pulse and reception of the radar reflection, wherein the first shift value is used to compute a distance to an object which generates the radar reflection.

23. The method of claim 1 further comprising providing an output to a user in response to the first shift value.

24. A computer-implemented method for estimating a shift between two signals, the method comprising:

(a) receiving a first signal g, wherein the first signal g comprises a sequence of values which are representable as a vector g having N components;

(b) projecting the vector g to a space with dimension K less than N to obtain a projection vector X having K components;

(c) computing measures of distance between the projection vector X and a set of stored vectors, wherein each of the stored vectors is associated with a corresponding vector in a collection of shift vectors, wherein each of the shift vectors is a shifted version of a second signal f;

(d) determining a first stored vector in the set of stored vectors with a minimum distance to the projection vector X based on the measures of distance;

(e) providing a first shift value corresponding to the first stored vector, wherein the first shift value is an estimate of a shift between the first signal g and the second signal f.

25. A signal analyzer system comprising:

a memory configured to store a shift estimation routine

a processor coupled to the memory and configured to execute the shift estimation routine, wherein, in response to the shift estimation routine executing on said processor, said processor is configured to;

(a) receive a first signal g, wherein the first signal g comprises a sequence of values which are representable as a vector g having N components;

(b) project the vector g to a space with dimension K less than N to obtain a projection vector X having K components;

(c) compute measures of distance between the projection vector X and a set of stored vectors, wherein each of the stored vectors is associated with a corresponding vector in a collection of shift vectors, wherein each of the shift vectors is a shifted version of a second signal f;

(d) determine a first stored vector in the set of stored vectors with a minimum distance to the projection vector X based on the measures of distance;

(e) provide a first shift value corresponding to the first stored vector, wherein the first shift value is an estimate of a shift between the first signal g and the second signal f.

26. The signal analyzer of claim 25, wherein, in response to the shift estimation routine executing on said processor, said processor is further configured to generate the set of stored vectors by multiplying each shift vector in said collection by a matrix C.

27. The signal analyzer of claim 25, wherein said processor projects the vector g to the space by multiplying the vector g with the matrix C.

28. The signal analyzer of claim 25, wherein, in response to the shift estimation routine executing on said processor, said processor is further configured to compute the matrix C prior to said projecting the vector g to the space with dimension K less than N, wherein said computing the matrix C includes performing an iterative search to determine a first matrix which maximizes an objective function.

29. The signal analyzer of claim 25, wherein, in response to the shift estimation routine executing on said processor, said processor is further configured to compute the matrix C prior to said projecting the vector g to the space with dimension K less than N, wherein said computing the matrix C includes:

computing a Fourier transform of the second signal f;

identifying a collection of K/2 distinct integers in the range from 1 to N−

1 which maximize a sum of magnitudes of the Fourier transform evaluated on the collection of K/2 distinct integers subject to a spanning condition;

for each integer m of the K/2 distinct integers, assigning the cosine and sine waveforms with frequency m to a pair of columns of matrix C.

30. A memory medium comprising program instructions for estimating a shift between two signals, wherein the program instructions are executable to implement:

(a) receiving a first signal g, wherein the first signal g comprises a sequence of values which are representable as a vector g having N components;

(b) projecting the vector g to a space with dimension K less than N to obtain a projection vector X having K components;

(c) computing measures of distance between the projection vector X and a set of stored vectors, wherein each of the stored vectors is associated with a corresponding vector in a collection of shift vectors, wherein each of the shift vectors is a shifted version of a second signal f;

(d) determining a first stored vector in the set of stored vectors with a minimum distance to the projection vector X based on the measures of distance;

(e) providing a first shift value corresponding to the first stored vector, wherein the first shift value is an estimate of a shift between the first signal g and the second signal f.

31. The memory medium of claim 30, wherein said shift represents a time-delay between the first signal g and the second signal f.

32. The memory medium of claim 30, wherein the program instructions are further executable to implement:

generating the set of stored vectors, wherein said generating comprises projecting the collection of shift vectors to the space with dimension K less than N.

33. The memory medium of claim 32, wherein said first stored vector is generated by projection of a first shift vector in said collection of shift vectors, wherein the first shift value defines an amount by which the second signal f is shifted to obtain the first shift vector.

34. The memory medium of claim 32, wherein said projecting the collection of shift vectors to the space comprises multiplying each shift vector in said collection by a matrix C.

35. The memory medium of claim 34, wherein said projecting the vector g to a space to obtain a projection vector X comprises multiplying the vector g by the matrix C.

36. The memory medium of claim 34, wherein the program instructions are further executable to implement:

computing the matrix C prior to said projecting the vector g to the space with dimension K less than N, wherein said computing the matrix C includes performing an iterative search to determine a first matrix which maximizes an objective function.

37. The memory medium of claim 36, wherein a simulated annealing algorithm is used to perform said iterative search.

38. The memory medium of claim 36, wherein each iteration of the iterative search comprises evaluating the objective function on a current iterate matrix Y, wherein said evaluating comprises:

multiplying the set of shift vectors by the current iterate matrix Y to generate a set of image vectors;

computing a minimal distance between the image vectors in the set of image vectors;

computing a noise object size associated with the current iterate matrix Y;

computing a ratio comprising the minimal distance and the noise object size.

39. The memory medium of claim 38, wherein said computing a noise object size comprises computing the sum of the squares of the elements of the current iterate matrix Y.

40. The memory medium of claim 34, wherein the program instructions are further executable to implement:

computing the matrix C prior to said projecting the vector g to the space with dimension K less than N, wherein said computing the matrix C comprises;

computing a Fourier transform of the second signal f;

identifying a collection of K/2 distinct integers in the range from 1 to N−

1 which maximize a sum of magnitudes of the Fourier transform evaluated on the collection of K/2 distinct integers subject to a spanning condition;

for each integer m of the K/2 distinct integers, assigning the cosine and sine waveforms with frequency m to a pair of columns of matrix C.

41. The memory medium of claim 40, wherein the spanning condition is that the greatest common divisor of N and the collection of K/2 distinct integers is one.

42. The memory medium of claim 40, wherein the spanning condition is that at least one of the K/2 distinct integer is relatively prime to N.

43. The memory medium of claim 30 , wherein each of the shift vectors are circularly-shifted versions of second signal f.

44. The memory medium of claim 30, wherein said computing measures of distance between the projection vector X and the set of stored vectors comprises computing an L¹ distances between the projection vector X and each vector in the set of stored vectors.

45. The memory medium of claim 30, wherein said computing measures of distance between the projection vector X and the set of stored vectors comprises computing dot products between the projection vector X and each vector in the set of stored vectors.

46. The memory medium of claim 30, wherein the first signal g comprises first pixel data extracted from a first image, and the second signal f comprises second pixel data extracted from a second image, wherein said first shift value indicates an estimated orientation of the first image with respect to the second image.

47. The memory medium of claim 30, wherein (a), (b), (c), (d) and (e) are performed repeatedly for a series of signals including the first signal g.

48. The memory medium of claim 30, wherein said determining a first stored vector in the set of stored vectors with a minimum distance to the projection vector X comprises:

computing dot products between the projection vector X and each of the stored vectors; and

selecting the stored vector in the set of stored vectors which maximizes the dot projects as the first stored vector.

49. The memory medium of claim 30, wherein the first signal g comprises samples of received radar reflection, wherein the second signal f comprises samples of a transmitted radar pulse, wherein said first shift value indicates an estimated time of propagation between transmission of the transmitted radar pulse and reception of the radar reflection, wherein the first shift value is used to compute a distance to an object which generates the radar reflection.

50. The memory medium of claim 30, wherein the program instructions are further executable to implement:

providing an output to a user in response to the first shift value.

51. A memory medium comprising program instructions for estimating a shift between two signals, wherein the program instructions are executable to implement:

(a) receiving a signal g, wherein the signal g corresponds to a shifted version of a signal f, wherein the signal g comprises a sequence of values having N components;

(b) creating a representation of the signal g in a space with dimension K less than N, wherein said creating produces a signal X having K components;

(c) computing measures of distance between the signal X and a set of stored signals, wherein each of the stored signals comprises a representation of a shifted version of the signal f in the space with dimension K

(d) determining a first stored signal in the set of stored signals with a minimum distance to the signal X, wherein the first stored signal corresponds to a first shift value;

(e) providing the first shift value, wherein the first shift value is an estimate of a shift between the first signal g and the second signal f.

52. The memory medium of claim 51,

wherein the signal g comprises a shifted version of the signal f.

53. The memory medium of claim 51,

wherein the signal g comprises a shifted noise-perturbed version of the signal f.

54. The memory medium of claim 51,

wherein each of the stored signals is a representation of a shifted noise perturbed version of the signal f in a space with dimension K.