Detecting a shifted peak from two signals

I'm doing robotics and built a sonar system to detect walls using
pulse-compression - this seems to work fine so far. As I'm only interested
in the echoes from the front wall, I need to filter out unwanted side
echoes (e.g. from floor, ceiling).

My approach would be to send out a chirp, and get the echo profile then
let the robot move forward and send a second chirp to do a second profile -
then comparing these two profiles and those echoes which moved/shifted
might be the correct ones, those who stayed the same are considered clutter
(e.g. because the distance to the ceiling did not change).

My question is, if there is a common/statistical way to detect shifted
peaks from two signal readings? E.g. to detect those peaks, which are
moved, but still retain +/- the same amplitude?

I have uploaded an image to show an example:
http://homepage.mac.com/kussmaul/shiftedPeak.png

Michael Kussmaul wrote:

> I'm doing robotics and built a sonar system to detect walls using
> pulse-compression - this seems to work fine so far. As I'm only interested
> in the echoes from the front wall, I need to filter out unwanted side
> echoes (e.g. from floor, ceiling).
> 
> My approach would be to send out a chirp, and get the echo profile then
> let the robot move forward and send a second chirp to do a second profile -
> then comparing these two profiles and those echoes which moved/shifted
> might be the correct ones, those who stayed the same are considered clutter
> (e.g. because the distance to the ceiling did not change).
> 
> My question is, if there is a common/statistical way to detect shifted
> peaks from two signal readings? E.g. to detect those peaks, which are
> moved, but still retain +/- the same amplitude?
> 
> I have uploaded an image to show an example:
> http://homepage.mac.com/kussmaul/shiftedPeak.png

This problem looks a lot like the motion estimation in the video, or the 
pitch estimation in the audio.

To start with, subtract one picture from the other. The peaks which are 
the same will be cancelled.

Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On Tue, 04 Aug 2009 11:12:55 -0500, Vladimir Vassilevsky wrote:

> Michael Kussmaul wrote:
> 
>> I'm doing robotics and built a sonar system to detect walls using
>> pulse-compression - this seems to work fine so far. As I'm only
>> interested in the echoes from the front wall, I need to filter out
>> unwanted side echoes (e.g. from floor, ceiling).
>> 
>> My approach would be to send out a chirp, and get the echo profile then
>> let the robot move forward and send a second chirp to do a second
>> profile - then comparing these two profiles and those echoes which
>> moved/shifted might be the correct ones, those who stayed the same are
>> considered clutter (e.g. because the distance to the ceiling did not
>> change).
>> 
>> My question is, if there is a common/statistical way to detect shifted
>> peaks from two signal readings? E.g. to detect those peaks, which are
>> moved, but still retain +/- the same amplitude?
>> 
>> I have uploaded an image to show an example:
>> http://homepage.mac.com/kussmaul/shiftedPeak.png
> 
> This problem looks a lot like the motion estimation in the video, or the
> pitch estimation in the audio.
> 
> To start with, subtract one picture from the other. The peaks which are
> the same will be cancelled.
> 
That's not going to work well with peaks that change height, or that move 
just a little bit.  You can fix the former by doing some sort of peak 
detection, but for the latter you need to do some sort of nearby peak 
cancellation.

-- 
www.wescottdesign.com

>On Tue, 04 Aug 2009 11:12:55 -0500, Vladimir Vassilevsky wrote:
>
>> Michael Kussmaul wrote:
>> 
>><snip>
>> 
>> This problem looks a lot like the motion estimation in the video, or
the
>> pitch estimation in the audio.
>> 
>> To start with, subtract one picture from the other. The peaks which
are
>> the same will be cancelled.
>> 
>That's not going to work well with peaks that change height, or that move

>just a little bit.  You can fix the former by doing some sort of peak 
>detection, but for the latter you need to do some sort of nearby peak 
>cancellation.
>
>-- 
>www.wescottdesign.com
>

I already tried a few techniques (peak detection and then do a search
around the main peaks to see, if there is a shift) - but it's not so
trivial, because:
- I don't know the exact shift - I just know, there is a shift, but not
the exact amount.
- some faulty peaks are not present at all in the second profile or are
not in the first.
- if I have two nearby peaks, their shift might overlap, so I cancel out a
correct peak.

I will take a look at motion estimation as you suggested (I have some
background in computer vision) but I thought there you do more like a
feature detection - not sure if my peaks have unique characteristics so I
could detect them after a shift though.

On 5 Aug, 15:02, "Michael Kussmaul" <kussmaul.l...@nix.ch> wrote:

> I already tried a few techniques (peak detection and then do a search
> around the main peaks to see, if there is a shift) - but it's not so
> trivial, because:
> - I don't know the exact shift - I just know, there is a shift, but not
> the exact amount.
> - some faulty peaks are not present at all in the second profile or are
> not in the first.
> - if I have two nearby peaks, their shift might overlap, so I cancel out a
> correct peak.

You are attacking this in the wrong place.

First of all, find a matched filter for the emitted
pulse. Use this matched filter to crudely locate
the peaks. Then use some local neighbourhood method
around each peak to try an precisely locate it.
Depending on how well separated the peaks are,
and how good a representation for the pulse you
cand find, you could have a look a the phase of the
cross spectrum between the emitted pulse and the
reflection, for this step.

Once you have a set of possible reflector ranges,
you can start processing the range maps to exclude
random outliers and identify reflectors. Depending
on the characteristics of the reflectors, they
might show systematic variations in range and/or
backscattered energy. Use such characteristica
to characterize and filter range estimates.

But of course, the only peak you need to care
about is the first one, that represents the
nearest reflector.

Rune

>You are attacking this in the wrong place.
>
>First of all, find a matched filter for the emitted
>pulse. Use this matched filter to crudely locate
>the peaks. Then use some local neighbourhood method
>around each peak to try an precisely locate it.
>Depending on how well separated the peaks are,
>and how good a representation for the pulse you
>cand find, you could have a look a the phase of the
>cross spectrum between the emitted pulse and the
>reflection, for this step.
>
>Once you have a set of possible reflector ranges,
>you can start processing the range maps to exclude
>random outliers and identify reflectors. Depending
>on the characteristics of the reflectors, they
>might show systematic variations in range and/or
>backscattered energy. Use such characteristica
>to characterize and filter range estimates.
>
>But of course, the only peak you need to care
>about is the first one, that represents the
>nearest reflector.
>
>Rune
>

Thanks for your suggestions - I use a matched filter (the result of the
filter are the peaks, as shown in the picture of original post) and you
suggest to further refine the peaks by using a cross spectrum - as I'm
quite new to all this, I'm not so sure what would be the right way to do
so. 

E.g. my chirp is 1024 samples large (I'm using hearable sound - chirp is
exponential 15kHz -> 22kHz, 44.1kHz sample rate). I let go the chrip and
start sampling, assume at 500 samples along I receive the first echo, when
I got 4096 samples I stop recording. I then do my matched filtering (based
on a 4096 windows size) and detect a peak around 500 samples.

Now to cross-spectrum to refine peaks:
- Either I do it over the whole window (4096)
(FFT(referenceChirpWithAddedZerosToMakeIt4096Long) x
FFT*(4096ReceivedSamples))
and calculate the phase from it ( atan(imagPart/realPart) )
- Or I do it blockwise (to reduce leakage I could do a hanning or so
window) for each echo?
(FFT(referenceChirp1024) x FFT*(receivedSamplesfrom500Until1524)

I tried the first approach first - but could not directly see how I could
benefit from the phase information.

On 6 Aug, 12:58, "Michael Kussmaul" <kussmaul.l...@nix.ch> wrote:
> >You are attacking this in the wrong place.
>
> >First of all, find a matched filter for the emitted
> >pulse. Use this matched filter to crudely locate
> >the peaks. Then use some local neighbourhood method
> >around each peak to try an precisely locate it.
> >Depending on how well separated the peaks are,
> >and how good a representation for the pulse you
> >cand find, you could have a look a the phase of the
> >cross spectrum between the emitted pulse and the
> >reflection, for this step.
>
> >Once you have a set of possible reflector ranges,
> >you can start processing the range maps to exclude
> >random outliers and identify reflectors. Depending
> >on the characteristics of the reflectors, they
> >might show systematic variations in range and/or
> >backscattered energy. Use such characteristica
> >to characterize and filter range estimates.
>
> >But of course, the only peak you need to care
> >about is the first one, that represents the
> >nearest reflector.
>
> >Rune
>
> Thanks for your suggestions - I use a matched filter (the result of the
> filter are the peaks, as shown in the picture of original post) and you
> suggest to further refine the peaks by using a cross spectrum - as I'm
> quite new to all this, I'm not so sure what would be the right way to do
> so.
>
> E.g. my chirp is 1024 samples large (I'm using hearable sound - chirp is
> exponential 15kHz -> 22kHz, 44.1kHz sample rate). I let go the chrip and
> start sampling, assume at 500 samples along I receive the first echo, when
> I got 4096 samples I stop recording. I then do my matched filtering (based
> on a 4096 windows size) and detect a peak around 500 samples.
>
> Now to cross-spectrum to refine peaks:
> - Either I do it over the whole window (4096)
> (FFT(referenceChirpWithAddedZerosToMakeIt4096Long) x
> FFT*(4096ReceivedSamples))
> and calculate the phase from it ( atan(imagPart/realPart) )
> - Or I do it blockwise (to reduce leakage I could do a hanning or so
> window) for each echo?
> (FFT(referenceChirp1024) x FFT*(receivedSamplesfrom500Until1524)
>
> I tried the first approach first - but could not directly see how I could
> benefit from the phase information.

If the chirp is 1000 samples and you process over 4000
samples, there is llikely overlap between successive
reflections of the chirp. In that case the phase spectrum
idea will not work, as it requires that you have a segment
of data that contains only one reflection.

For details about the technique check out chapter 5 in

Bendat & Piersol: Random Data, 2000.

Rune

>If the chirp is 1000 samples and you process over 4000
>samples, there is llikely overlap between successive
>reflections of the chirp. In that case the phase spectrum
>idea will not work, as it requires that you have a segment
>of data that contains only one reflection.
>
>For details about the technique check out chapter 5 in
>
>Bendat & Piersol: Random Data, 2000.
>
>Rune
>

Ah, this makes sense - and yes, there is quite a lot of overlap. Looking
just at the time-domain the single reflections are not visible, only the
matched filter can distinguish them.