Cross-correlation by convolution (unexpected results)

Since an image is word ten thousand words, here's what sums up what i'm
trying to do http://www.geocities.com/michel0528/correlation.jpg

As you can see, I'm trying to correlate the first signal by the second
by correlation. The problem is, I didn't really expect the result you
can see on the picture, I expected more something looking like from not
too close like a delta function right in the middle.

So what's wrong, is it that my convolution function is broken, or is
there something I did wrong/something I didn't understand right about
cross-correlation by convolution?

Michel Rouzic wrote:
> Since an image is word ten thousand words, here's what sums up what i'm
> trying to do http://www.geocities.com/michel0528/correlation.jpg
>
> As you can see, I'm trying to correlate the first signal by the second
> by correlation. The problem is, I didn't really expect the result you
> can see on the picture, I expected more something looking like from not
> too close like a delta function right in the middle.
>
> So what's wrong, is it that my convolution function is broken, or is
> there something I did wrong/something I didn't understand right about
> cross-correlation by convolution?

First, these are images, right? The lines in the two first images did
resemble graphs of linear functions at first.

If these are images, use a simpler signal to check the implementation.
For instance, use two images that are all black, except for, say, a
25 x 25 block of white pixels. The corelation between those images
ought to form a pyramid in spatial domain. Once you get that result,
you try to distort one of the images and see if the resulting
distortion 
in correlation domain is as expected.

Rune

"Michel Rouzic" <Michel0528@yahoo.fr> wrote in message 
news:1138502806.658790.269740@g47g2000cwa.googlegroups.com...
> Since an image is word ten thousand words, here's what sums up what i'm
> trying to do http://www.geocities.com/michel0528/correlation.jpg
>
> As you can see, I'm trying to correlate the first signal by the second
> by correlation.
O.K. starting from the left :
1) is this a spectrogram of a complex chirp return so that across the page 
is increasing time, up the page is increasing frequency and the (log?) 
magnitude of the response is indicated by the colour of the pixels ?  Looks 
like it as I can see what looks like a second harmonic at the start of a 
linear fm chirp then a pair of sidebands appear later (one of which is 
aliased back in at the top right hand corner).

2)  You then want to convolve your return echo with a time reversed version 
of the original chirp? This looks like a clean spectrogram of your original 
chirp with the time axis reversed and I assume from your text that * is 
convolution and not element by element multiplication - is that right?

3) and you get something like the far right picture - is this a spectrogram 
too? I don't see why it would be if you are looking for an impulse 
response - perhaps you will describe a bit more what the axes mean?

Best of luck - Mike

Rune Allnor wrote:
> Michel Rouzic wrote:
> > Since an image is word ten thousand words, here's what sums up what i'm
> > trying to do http://www.geocities.com/michel0528/correlation.jpg
> >
> > As you can see, I'm trying to correlate the first signal by the second
> > by correlation. The problem is, I didn't really expect the result you
> > can see on the picture, I expected more something looking like from not
> > too close like a delta function right in the middle.
> >
> > So what's wrong, is it that my convolution function is broken, or is
> > there something I did wrong/something I didn't understand right about
> > cross-correlation by convolution?
>
> First, these are images, right? The lines in the two first images did
> resemble graphs of linear functions at first.
>
> If these are images, use a simpler signal to check the implementation.
> For instance, use two images that are all black, except for, say, a
> 25 x 25 block of white pixels. The corelation between those images
> ought to form a pyramid in spatial domain. Once you get that result,
> you try to distort one of the images and see if the resulting
> distortion
> in correlation domain is as expected.
>
> Rune

Oh sorry I forgot to tell, those are spectrographs of sounds. I thought
it would seem obvious. And anyways, I made sure my implementation of
convolution was working with windowed-sinc functions, that's pretty
much all.

Mike Yarwood wrote:
> "Michel Rouzic" <Michel0528@yahoo.fr> wrote in message
> news:1138502806.658790.269740@g47g2000cwa.googlegroups.com...
> > Since an image is word ten thousand words, here's what sums up what i'm
> > trying to do http://www.geocities.com/michel0528/correlation.jpg
> >
> > As you can see, I'm trying to correlate the first signal by the second
> > by correlation.
> O.K. starting from the left :
> 1) is this a spectrogram of a complex chirp return so that across the page
> is increasing time, up the page is increasing frequency and the (log?)
> magnitude of the response is indicated by the colour of the pixels ?  Looks
> like it as I can see what looks like a second harmonic at the start of a
> linear fm chirp then a pair of sidebands appear later (one of which is
> aliased back in at the top right hand corner).

Um.. This is the spectrogram of two chirps and their result. Nothing
complex, all real data. Spectrograms made with Adobe Audition aka
CoolEdit

> 2)  You then want to convolve your return echo with a time reversed version
> of the original chirp? This looks like a clean spectrogram of your original
> chirp with the time axis reversed and I assume from your text that * is
> convolution and not element by element multiplication - is that right?

Yup that's perfectly right.

> 3) and you get something like the far right picture - is this a spectrogram
> too? I don't see why it would be if you are looking for an impulse
> response - perhaps you will describe a bit more what the axes mean?

Yes this is the spectrogram of the result. What's not obvious is that
it's twice as long as the two first signals. The X axis means time, the
Y axis means frequency, the colors mean magnitude. What I expected as
an impulse response was a rather black/blueish background with a
yellowish vertical stripe right in the middle.

"Michel Rouzic" <Michel0528@yahoo.fr> wrote in message 
news:1138557715.831008.238690@g47g2000cwa.googlegroups.com...
>
> Mike Yarwood wrote:
>> "Michel Rouzic" <Michel0528@yahoo.fr> wrote in message
>> news:1138502806.658790.269740@g47g2000cwa.googlegroups.com...
>> > Since an image is word ten thousand words, here's what sums up what i'm
>> > trying to do http://www.geocities.com/michel0528/correlation.jpg
>> >
>> > As you can see, I'm trying to correlate the first signal by the second
>> > by correlation.
>> O.K. starting from the left :
>> 1) is this a spectrogram of a complex chirp return so that across the 
>> page
>> is increasing time, up the page is increasing frequency and the (log?)
>> magnitude of the response is indicated by the colour of the pixels ? 
>> Looks
>> like it as I can see what looks like a second harmonic at the start of a
>> linear fm chirp then a pair of sidebands appear later (one of which is
>> aliased back in at the top right hand corner).
>
> Um.. This is the spectrogram of two chirps and their result. Nothing
> complex, all real data. Spectrograms made with Adobe Audition aka
> CoolEdit
>
>> 2)  You then want to convolve your return echo with a time reversed 
>> version
>> of the original chirp? This looks like a clean spectrogram of your 
>> original
>> chirp with the time axis reversed and I assume from your text that * is
>> convolution and not element by element multiplication - is that right?
>
> Yup that's perfectly right.
>
O.k. then , apart from a few ripply bits you should be fine.

>> 3) and you get something like the far right picture - is this a 
>> spectrogram
>> too? I don't see why it would be if you are looking for an impulse
>> response - perhaps you will describe a bit more what the axes mean?
>
> Yes this is the spectrogram of the result. What's not obvious is that
> it's twice as long as the two first signals. The X axis means time, the
> Y axis means frequency, the colors mean magnitude. What I expected as
> an impulse response was a rather black/blueish background with a
> yellowish vertical stripe right in the middle.

Right. I'm puzzled too , X axis is time o.k. colors mean magnitude  o.k.- 
but you only have one value per unit time lag as the result of your 
convolution -  so what's frequency?

Best of luck - Mike

Michel Rouzic schrieb:
> Since an image is word ten thousand words, here's what sums up what i'm
> trying to do http://www.geocities.com/michel0528/correlation.jpg
> 
> As you can see, I'm trying to correlate the first signal by the second
> by correlation. The problem is, I didn't really expect the result you
> can see on the picture, I expected more something looking like from not
> too close like a delta function right in the middle.

Take a look at the result in the time domain, and you will see a delta 
function. It looks that way in a spectrogram, your convolution function 
is working correctly.

Mike Yarwood wrote:
> "Michel Rouzic" <Michel0528@yahoo.fr> wrote in message
> news:1138557715.831008.238690@g47g2000cwa.googlegroups.com...
> >
> > Mike Yarwood wrote:
> >> "Michel Rouzic" <Michel0528@yahoo.fr> wrote in message
> >> news:1138502806.658790.269740@g47g2000cwa.googlegroups.com...
> >> > Since an image is word ten thousand words, here's what sums up what i'm
> >> > trying to do http://www.geocities.com/michel0528/correlation.jpg
> >> >
> >> > As you can see, I'm trying to correlate the first signal by the second
> >> > by correlation.
> >> O.K. starting from the left :
> >> 1) is this a spectrogram of a complex chirp return so that across the
> >> page
> >> is increasing time, up the page is increasing frequency and the (log?)
> >> magnitude of the response is indicated by the colour of the pixels ?
> >> Looks
> >> like it as I can see what looks like a second harmonic at the start of a
> >> linear fm chirp then a pair of sidebands appear later (one of which is
> >> aliased back in at the top right hand corner).
> >
> > Um.. This is the spectrogram of two chirps and their result. Nothing
> > complex, all real data. Spectrograms made with Adobe Audition aka
> > CoolEdit
> >
> >> 2)  You then want to convolve your return echo with a time reversed
> >> version
> >> of the original chirp? This looks like a clean spectrogram of your
> >> original
> >> chirp with the time axis reversed and I assume from your text that * is
> >> convolution and not element by element multiplication - is that right?
> >
> > Yup that's perfectly right.
> >
> O.k. then , apart from a few ripply bits you should be fine.
>
> >> 3) and you get something like the far right picture - is this a
> >> spectrogram
> >> too? I don't see why it would be if you are looking for an impulse
> >> response - perhaps you will describe a bit more what the axes mean?
> >
> > Yes this is the spectrogram of the result. What's not obvious is that
> > it's twice as long as the two first signals. The X axis means time, the
> > Y axis means frequency, the colors mean magnitude. What I expected as
> > an impulse response was a rather black/blueish background with a
> > yellowish vertical stripe right in the middle.
>
> Right. I'm puzzled too , X axis is time o.k. colors mean magnitude  o.k.-
> but you only have one value per unit time lag as the result of your
> convolution -  so what's frequency?

I'm not sure I got what you meant... Frequency is axis Y. Just like for
any other spectrogram.

Andreas Schwarz wrote:
> Michel Rouzic schrieb:
> > Since an image is word ten thousand words, here's what sums up what i'm
> > trying to do http://www.geocities.com/michel0528/correlation.jpg
> >
> > As you can see, I'm trying to correlate the first signal by the second
> > by correlation. The problem is, I didn't really expect the result you
> > can see on the picture, I expected more something looking like from not
> > too close like a delta function right in the middle.
>
> Take a look at the result in the time domain, and you will see a delta
> function. It looks that way in a spectrogram, your convolution function
> is working correctly.

Oh yeah damn, i'm feeling dumb for not having noticed that. My result
is stored on floats and as you can see by the magnitude it was too big
for me to see that.

However, what do I do with my result? The "delta function" I got isn't
even really a delta function, but a 6400 bins chirp, surrounded by all
the noise you can see. Do I keep only the 6400 bins of interest? Do I
convolve that one little chirp with another to make it at last
straight? Why isn't it even straight in the first place?? Does it mean
that the recorded chirp lasted about 0.066% longer that the original
one for some reason?

Michel Rouzic schrieb:
> Andreas Schwarz wrote:
> 
>>Michel Rouzic schrieb:
>>
>>>Since an image is word ten thousand words, here's what sums up what i'm
>>>trying to do http://www.geocities.com/michel0528/correlation.jpg
>>>
>>>As you can see, I'm trying to correlate the first signal by the second
>>>by correlation. The problem is, I didn't really expect the result you
>>>can see on the picture, I expected more something looking like from not
>>>too close like a delta function right in the middle.
>>
>>Take a look at the result in the time domain, and you will see a delta
>>function. It looks that way in a spectrogram, your convolution function
>>is working correctly.
> 
> 
> Oh yeah damn, i'm feeling dumb for not having noticed that. My result
> is stored on floats and as you can see by the magnitude it was too big
> for me to see that.
> 
> However, what do I do with my result?

Depends on what you *want* to do.

 > The "delta function" I got isn't
> even really a delta function, but a 6400 bins chirp, surrounded by all
> the noise you can see.

As I wrote above, forget the spectrogram, it's making things much more 
complicated than they are. Take a look at your convolution result in the 
time domain. I'm sure you will see a pretty sharp peak at the center. 
Try to shift one of the input signals and look at the result again, you 
will see the peak shifted too, etc.

 > Do I keep only the 6400 bins of interest? Do I
> convolve that one little chirp with another to make it at last
> straight? Why isn't it even straight in the first place?? Does it mean
> that the recorded chirp lasted about 0.066% longer that the original
> one for some reason?

Sorry, I don't understand. Why don't you post a more detailed 
description of what you are trying to accomplish and what you have tried 
so far?

Andreas