Jump to content
  • Advertisement
Sign in to follow this  
Cornstalks

How to check if two periodic functions/signals match?

This topic is 2549 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've run into a bit of a problem and I'm trying to find the best way to find a solution. Say I've got two signals/functions (which are discontinuous, as they're regular samples from another function/signal). They'll both be normalized. What's the best way to check if the two signals/functions match? My main problem is that they may not be in the same phase as each other, but I want to still consider them as matching (i.e. consider the sin and cos waves, I'd consider them matching, though they're out of phase with each other). One option is to take the convolution of the two and find the max of the convolution, and if the convolution is above a certain threshold then I'd consider them as "matching." But I'd be repeating this process for many signals/functions (each signal/function represents an individual object), trying to match signals, and taking a convolution for each one seems rather expensive.

Should I maybe take the FFT of both of them and compare the FFT? I don't know how good of results that would produce. I haven't done a lot of signal processing/analysis.

Share this post


Link to post
Share on other sites
Advertisement
FFT sounds like a good approach. Keep in mind that shifting the phase corresponds to multiplying all Fourier coefficients by the same complex number of absolute value 1 (i.e. rotating all the coefficients in the complex plane), so you need to correct for that.

Share this post


Link to post
Share on other sites
Conceptually you could do the convolution thing, but you can implement that by computing the FFT of both signals and taking the product point by point. I would have to think a little bit about the details, but I am pretty sure this is workable.

Share this post


Link to post
Share on other sites
If you have two signals X(f) and Y(f) which are the Fourier transforms of the signals, then the quotient X(f)/Y(f) will have a constant magnitude and a linear phase if the two signals are equal. The phase shift corresponds to the delay between the two signals, and the constant amplitude is the scale difference between them. Noise will of course ensure that the magnitude won't be exactly constant, nor exactly linear phase, so you have to decide when the two signals are considered to be equivalent although they don't compare as exactly equal.

edit: I messed up some info in this post and it has been edited a few times. I think it should be correct now, in case someone read it between my edits.

Share this post


Link to post
Share on other sites

If you have two signals X(f) and Y(f) which are the Fourier transforms of the signals, then the quotient X(f)/Y(f) will have a constant magnitude and a linear phase if the two signals are equal. The phase shift corresponds to the delay between the two signals, and the constant amplitude is the scale difference between them. Noise will of course ensure that the magnitude won't be exactly constant, nor exactly linear phase, so you have to decide when the two signals are considered to be equivalent although they don't compare as exactly equal.


That sounds like what I'm looking for. Would I just do a point-wise X(f)/Y(f) for each element in X and Y (i.e. x[sub]i[/sub](f)/y[sub]i[/sub](f) for all i), and just compare the results to see if they're (mostly) constant? I'm not sure how to check if the phase is linear once I do X(f)/Y(f)...

@alvaro: I think I'm following you... are you suggesting I use the convolution theorem to find the convolution? That's probably how I'd do it if I went the convolution route, but it sounds like Brother Bob's way might be nice because I don't have to find the inverse FFT.

@Prefect: that's interesting to learn!

Share this post


Link to post
Share on other sites
Prefect and Brother Bob are pointing out essentially the same idea, which is simpler and more direct than what you or I were thinking.

Instead of dividing point by point (because I don't like potentially dividing by zero), you can try to compute what number you would have to multiply one of them to get the other, using the canonical Hermitian inner product, as follows. Let X and Y be the complex vectors that describe the FFT of your two signals. If Y = k * X, then <Y,X> = k * <X,X>. So compute the complex number k = <Y,X>/<X,X> which is trivial to compute and will tell you how much you have to magnify and shift one signal to match the other. Let's define Z:=Y-k*X. If the match is good, <Z,Z> will be small.

I think the procedure above should work well.

Share this post


Link to post
Share on other sites

[quote name='Brother Bob' timestamp='1324499874' post='4896296']
If you have two signals X(f) and Y(f) which are the Fourier transforms of the signals, then the quotient X(f)/Y(f) will have a constant magnitude and a linear phase if the two signals are equal. The phase shift corresponds to the delay between the two signals, and the constant amplitude is the scale difference between them. Noise will of course ensure that the magnitude won't be exactly constant, nor exactly linear phase, so you have to decide when the two signals are considered to be equivalent although they don't compare as exactly equal.


That sounds like what I'm looking for. Would I just do a point-wise X(f)/Y(f) for each element in X and Y (i.e. x[sub]i[/sub](f)/y[sub]i[/sub](f) for all i), and just compare the results to see if they're (mostly) constant?
[/quote]
I don't know what your i is supposed to represent. When you have a signal x(n) in time n, you get a signal X(f) in frequency f when you take the Fourier transform. There are no other subscripts or indices, unless there is some information about the signal you're leaving out in your description. But what I mean with division is the element-wise division of each frequency f.


I'm not sure how to check if the phase is linear once I do X(f)/Y(f)...

I did leave out some implicit information that is kind of given for signal processing guys like myself, sorry. Linear phase simply means that the phase is a linear function of the frequency; that is, phase=constant*frequency. Thus, if you take the phase of the quotient X(f)/Y(f) and divide by the frequency f, you get a constant value if the phase is linear.

Also something you have to be aware of with the phase is that phase wraps around the unit circle, and so multiples of 2*pi appear as the same instantaneous phase. You need to do something called phase unwrapping, which unwraps the phase and removes this 2*pi-ambiguity. You can search for phase unwrapping if you want to know more about it. It effectively means that, starting from f=0 and walking up in frequency, you add 2*pi once the phase has made one turn around the unit circle, and then 4*pi after the second turn, and so on.

Share this post


Link to post
Share on other sites

Prefect and Brother Bob are pointing out essentially the same idea, which is simpler and more direct than what you or I were thinking.

Instead of dividing point by point (because I don't like potentially dividing by zero), you can try to compute what number you would have to multiply one of them to get the other, using the canonical Hermitian inner product, as follows. Let X and Y be the complex vectors that describe the FFT of your two signals. If Y = k * X, then <Y,X> = k * <X,X>. So compute the complex number k = <Y,X>/<X,X> which is trivial to compute and will tell you how much you have to magnify and shift one signal to match the other. Let's define Z:=Y-k*X. If the match is good, <Z,Z> will be small.

I think the procedure above should work well.

Your solution may be easier than mine. You just have to complex conjugate the second operand of the inner product though.

Share this post


Link to post
Share on other sites

Your solution may be easier than mine. You just have to complex conjugate the second operand of the inner product though.


True. However, I am following the notation in the link I posted (which is also what I would normally use), which defines <a,b> as sum(a_i * conj(b_i)).

Share this post


Link to post
Share on other sites

[quote name='Brother Bob' timestamp='1324504577' post='4896321']
Your solution may be easier than mine. You just have to complex conjugate the second operand of the inner product though.


True. However, I am following the notation in the link I posted (which is also what I would normally use), which defines <a,b> as sum(a_i * conj(b_i)).
[/quote]
Yeah, sorry, I missed that detail. In hindsight, it is sort of obvious to me from the name of the link alone that you had a complex conjugate there already.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!