Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #922 > unrolled thread

Algorithms for comparing waveforms

Back to article view | Back to comp.programming

Contents

  Algorithms for comparing waveforms ri_wells@yahoo.com - 2011-10-14 16:32 -0700
    Re: Algorithms for comparing waveforms Thad Smith <ThadSmith@acm.org> - 2011-10-15 18:40 -0700
    Re: Algorithms for comparing waveforms ri_wells@yahoo.com - 2011-10-17 11:29 -0700
      Re: Algorithms for comparing waveforms Jerry Avins <jya@ieee.org> - 2011-10-17 17:12 -0400
      Re: Algorithms for comparing waveforms glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2011-10-17 23:10 +0000
        Re: Algorithms for comparing waveforms robert bristow-johnson <rbj@audioimagination.com> - 2011-10-17 17:06 -0700
      Re: Algorithms for comparing waveforms Geoff <geoff@invalid.invalid> - 2011-10-17 18:41 -0700
        Re: Algorithms for comparing waveforms Jerry Avins <jya@ieee.org> - 2011-10-17 23:12 -0400
        Re: Algorithms for comparing waveforms kym@kymhorsell.com - 2011-10-18 03:20 +0000
      Re: Algorithms for comparing waveforms fatalist <simfidude@gmail.com> - 2011-10-18 06:20 -0700

#922 — Algorithms for comparing waveforms

Can someone suggest pointers to good algorithms that can be used for
comparing the raw data corresponding to two waveforms to see if they
are similar {e.g. EKG waveforms of two healthy and normal human
beings}?  I am looking for open source code or pseudo code, rather
than terse mathematical equations, since the latter may not lend
themselves to easy and efficient implementation.

TIA,
Richard

[toc] | [next] | [standalone]

#926

On 10/14/2011 4:32 PM, ri_wells@yahoo.com wrote:
> Can someone suggest pointers to good algorithms that can be used for
> comparing the raw data corresponding to two waveforms to see if they
> are similar {e.g. EKG waveforms of two healthy and normal human
> beings}?  I am looking for open source code or pseudo code, rather
> than terse mathematical equations, since the latter may not lend
> themselves to easy and efficient implementation.

I think the key is to define "similar" in a rigorous way that can be implemented 
as an algorithm.  The signal period and amplitude may be the most prominent 
features of, say, an electrocardiogram, but may not be the important aspect for 
a particular purpose.

-- 
Thad

[toc] | [prev] | [next] | [standalone]

#932

On Oct 16, 12:32 pm, Jerry Avins <j...@ieee.org> wrote:
> On 10/16/2011 12:27 PM, ri_we...@yahoo.com wrote:
>
> > Cross posting to comp.dsp
>
> > On Oct 14, 6:32 pm, ri_we...@yahoo.com wrote:
> >> Can someone suggest pointers to good algorithms that can be used for
> >> comparing the raw data corresponding to two waveforms to see if they
> >> are similar {e.g. EKG waveforms of two healthy and normal human
> >> beings}?  I am looking for open source code or pseudo code, rather
> >> than terse mathematical equations, since the latter may not lend
> >> themselves to easy and efficient implementation.
>
> Can you define "similar" algorithmically?
>
> Jerry
> --

Jerry,

Kindly don't clobber me.  I will attempt to define "similar" in layman
terms rather than algorithmically:)

Two waveforms may be deemed similar if at least some of the following
are true:
- A human, who is shown the trace of the two waveforms, will conclude
that the waveforms are similar
- They have a constant phase difference, although amplitudes may not
be the same
- To a large extent they have the same harmonics, although not
necessarily the same amplitude for the various harmonics
- The harmonics of one waveform are a multiple of the harmonics of the
other waveform
- They have similar structures for peaks and troughs, although
amplitudes may not be the same


With this understanding, can someone provide pointers to algorithms
and/or opensource implementations?


TIA,
Richard

[toc] | [prev] | [next] | [standalone]

#934

On 10/17/2011 2:29 PM, ri_wells@yahoo.com wrote:
> On Oct 16, 12:32 pm, Jerry Avins<j...@ieee.org>  wrote:
>> On 10/16/2011 12:27 PM, ri_we...@yahoo.com wrote:
>>
>>> Cross posting to comp.dsp
>>
>>> On Oct 14, 6:32 pm, ri_we...@yahoo.com wrote:
>>>> Can someone suggest pointers to good algorithms that can be used for
>>>> comparing the raw data corresponding to two waveforms to see if they
>>>> are similar {e.g. EKG waveforms of two healthy and normal human
>>>> beings}?  I am looking for open source code or pseudo code, rather
>>>> than terse mathematical equations, since the latter may not lend
>>>> themselves to easy and efficient implementation.
>>
>> Can you define "similar" algorithmically?
>>
>> Jerry
>> --
>
> Jerry,
>
> Kindly don't clobber me.  I will attempt to define "similar" in layman
> terms rather than algorithmically:)

I'm not sneering, and I'm not out to clobber you. Fred Marshal gave you 
a lot to think about, much of which you ignored. If I knew a solution to 
your problem, I would have told you when I first wrote.

> Two waveforms may be deemed similar if at least some of the following
> are true:
> - A human, who is shown the trace of the two waveforms, will conclude
> that the waveforms are similar

Although it is every programmer's dream, there is not yet a DWIM opcode. 
I was led to ask for an algorithmic definition by that unfortunate lack. 
(DWIN == Do What I Mean)

> - They have a constant phase difference, although amplitudes may not
> be the same

Phase has meaning only when comparing waveforms of the same frequency. 
When the frequency is nearly the same, we borrow from optics and talk 
about coherence length -- long is good.

> - To a large extent they have the same harmonics, although not
> necessarily the same amplitude for the various harmonics

Harmonic structure depends on frequency also.

> - The harmonics of one waveform are a multiple of the harmonics of the
> other waveform

That is usually a sign that the fundamentals differ by the same 
multiple. Also, two waveforms with identical harmonic amplitudes can 
look very different if the phases differ.

> - They have similar structures for peaks and troughs, although
> amplitudes may not be the same

What about spacing? For example, does the relative spacing between the P 
wave and the QRS complex, and between the QRS complex and the T wave 
remain much the same over a range of heart rates?

> With this understanding, can someone provide pointers to algorithms
> and/or opensource implementations?

I'm sure that if such software exists, it either adjusts the time base 
to some standard, or uses analysis methods that are independent of time. 
You really ought to get in touch pith pattern-recognition people. I'm 
sure they can answer some questions I don't know to ask.

Jerry
-- 
Engineering is the art of making what you want from things you can get.

[toc] | [prev] | [next] | [standalone]

#936

In comp.dsp ri_wells@yahoo.com wrote:

(snip)
> Kindly don't clobber me.  I will attempt to define "similar" in layman
> terms rather than algorithmically:)

> Two waveforms may be deemed similar if at least some of the following
> are true:

> - A human, who is shown the trace of the two waveforms, will conclude
> that the waveforms are similar

> - They have a constant phase difference, although amplitudes may not
> be the same

When I was reading this, and forgot the context, I was thinking
of audio signals.  One could ask about audio waveforms that sound
similar, even if they are very different.  One is that in many 
cases the ear doesn't notice phase.  If you phase shift one (or more)
components of a sound, the waveform will look very different, but
the sound will be similar.  One way is to look at the magnitude
of the Fourier transform, which removes phase from consideration.

Anyway, you might at least look into what speech recognition
people are doing.

> - To a large extent they have the same harmonics, although not
> necessarily the same amplitude for the various harmonics

This one comes up often in music.  Though it tends to change
the sound, people can give a musical note to a sound with large
changes in harmonics.

> - The harmonics of one waveform are a multiple of the harmonics 
>     of the other waveform

Well, that naturally happens for harmonics, so you have to
be careful what you ask for.

One is that I think you can resample to a standard frequency.
First do the autocorrelation to find the fundamental, then resample
based on that.  Then you can fft, compute the magnitude to remove
phase, and look for harmonics.  Past that, it gets hard.

> - They have similar structures for peaks and troughs, although
> amplitudes may not be the same

The problem is that there are many things that a trained person
will see, and ignore others, but it isn't easy to teach a computer
to do those.  


> With this understanding, can someone provide pointers to algorithms
> and/or opensource implementations?

You might look at what image processing people are doing.  

One that I was looking at some time ago is medical imaging.
Say you have two pictures of some cells, one diseased, and one normal.
How can a computer, given another image, tell which one it is 
more like?  Many of the points you make above are also applicable.
You want to ignore overall intensity, color, scale, etc.   Then
narrow in on just what it is that identifies the disease.

EKG should be simpler, but the exact features that indicate
disease need to be separated from normal variations.

-- glen

[toc] | [prev] | [next] | [standalone]

#937

On Oct 17, 7:10 pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> In comp.dsp ri_we...@yahoo.com wrote:
>
> (snip)
>
> > Kindly don't clobber me.  

Jerry never clobbers anyone.  we leave that role to Vladie.

...

> > - They have similar structures for peaks and troughs, although
> > amplitudes may not be the same
>
> The problem is that there are many things that a trained person
> will see, and ignore others, but it isn't easy to teach a computer
> to do those.  

maybe if pitch detection (or estimating the period or fundamental
frequency) is done on both waveforms, and then using that period
information, the waveforms are resampled to have equal periods of some
specified integer (we call "N"), and then some circular cross-
correlation is done (normalized by the product of the r.m.s. of the
two waveforms) and if there is some lag where that normalized cross-
correlation gets close to 1, we might say that the two waveforms are
quite similar.  their Fourier series coefficients (which come from the
DFT of those N samples) would have nearly equal magnitude, and if
visual appearance is important, the complex angle of the Fourier
coefficients would be proportional to the frequency of each component.

it's a lot of rigemerole to go through if this waveshape matching
ain't what the OP wants.

> > With this understanding, can someone provide pointers to algorithms
> > and/or opensource implementations?

sorry.  but like the others, i dunno what all you're looking for,

r b-j

[toc] | [prev] | [next] | [standalone]

#938

On Mon, 17 Oct 2011 11:29:49 -0700 (PDT), ri_wells@yahoo.com wrote:

>On Oct 16, 12:32 pm, Jerry Avins <j...@ieee.org> wrote:
>> On 10/16/2011 12:27 PM, ri_we...@yahoo.com wrote:
>>
>> > Cross posting to comp.dsp
>>
>> > On Oct 14, 6:32 pm, ri_we...@yahoo.com wrote:
>> >> Can someone suggest pointers to good algorithms that can be used for
>> >> comparing the raw data corresponding to two waveforms to see if they
>> >> are similar {e.g. EKG waveforms of two healthy and normal human
>> >> beings}?  I am looking for open source code or pseudo code, rather
>> >> than terse mathematical equations, since the latter may not lend
>> >> themselves to easy and efficient implementation.
>>
>> Can you define "similar" algorithmically?
>>
>> Jerry
>> --
>
>Jerry,
>
>Kindly don't clobber me.  I will attempt to define "similar" in layman
>terms rather than algorithmically:)
>
>Two waveforms may be deemed similar if at least some of the following
>are true:
>- A human, who is shown the trace of the two waveforms, will conclude
>that the waveforms are similar
>- They have a constant phase difference, although amplitudes may not
>be the same
>- To a large extent they have the same harmonics, although not
>necessarily the same amplitude for the various harmonics
>- The harmonics of one waveform are a multiple of the harmonics of the
>other waveform
>- They have similar structures for peaks and troughs, although
>amplitudes may not be the same
>
>
>With this understanding, can someone provide pointers to algorithms
>and/or opensource implementations?
>

I don't know much about open source packages that might be available
but the algorithm you seek is the Fast Fourier Transform (FFT). Given
an arbitrary waveform, the FFT can break it down into it's harmonic
components. Once you have the harmonic coefficients you can compare
them between waveform A and B to see if they have the same "shape".
You would probably have to empirically determine how close the
coefficients of the terms have to be to call them "similar".

If you have digital samples of two waveforms with phase angle t
between them and unequal amplitudes they can be compared by applying
successive approximations of amplitude and phase to one of them until
it correlates as close as possible to the other. Mathematically:

f(A) = waveform sample A
f(B) = waveform sample B
K    = gain factor
t    = time shift (phase angle)

Then the waveforms are "similar" when

(K*f(A)-t) - f(B) is "approximately" zero. Where you set a maximum
value for a "zero" sum.

A good first guess at K would be the ratio between the maximum values
of the largest positive samples of the two waveforms. 

[toc] | [prev] | [next] | [standalone]

#939

On 10/17/2011 9:41 PM, Geoff wrote:
> On Mon, 17 Oct 2011 11:29:49 -0700 (PDT), ri_wells@yahoo.com wrote:
>
>> On Oct 16, 12:32 pm, Jerry Avins<j...@ieee.org>  wrote:
>>> On 10/16/2011 12:27 PM, ri_we...@yahoo.com wrote:
>>>
>>>> Cross posting to comp.dsp
>>>
>>>> On Oct 14, 6:32 pm, ri_we...@yahoo.com wrote:
>>>>> Can someone suggest pointers to good algorithms that can be used for
>>>>> comparing the raw data corresponding to two waveforms to see if they
>>>>> are similar {e.g. EKG waveforms of two healthy and normal human
>>>>> beings}?  I am looking for open source code or pseudo code, rather
>>>>> than terse mathematical equations, since the latter may not lend
>>>>> themselves to easy and efficient implementation.
>>>
>>> Can you define "similar" algorithmically?
>>>
>>> Jerry
>>> --
>>
>> Jerry,
>>
>> Kindly don't clobber me.  I will attempt to define "similar" in layman
>> terms rather than algorithmically:)
>>
>> Two waveforms may be deemed similar if at least some of the following
>> are true:
>> - A human, who is shown the trace of the two waveforms, will conclude
>> that the waveforms are similar
>> - They have a constant phase difference, although amplitudes may not
>> be the same
>> - To a large extent they have the same harmonics, although not
>> necessarily the same amplitude for the various harmonics
>> - The harmonics of one waveform are a multiple of the harmonics of the
>> other waveform
>> - They have similar structures for peaks and troughs, although
>> amplitudes may not be the same
>>
>>
>> With this understanding, can someone provide pointers to algorithms
>> and/or opensource implementations?
>>
>
> I don't know much about open source packages that might be available
> but the algorithm you seek is the Fast Fourier Transform (FFT).

Nonsense!

>                                                              Given
> an arbitrary waveform, the FFT can break it down into it's harmonic
> components. Once you have the harmonic coefficients you can compare
> them between waveform A and B to see if they have the same "shape".
> You would probably have to empirically determine how close the
> coefficients of the terms have to be to call them "similar".
>
> If you have digital samples of two waveforms with phase angle t
> between them and unequal amplitudes they can be compared by applying
> successive approximations of amplitude and phase to one of them until
> it correlates as close as possible to the other. Mathematically:
>
> f(A) = waveform sample A
> f(B) = waveform sample B
> K    = gain factor
> t    = time shift (phase angle)

And what if the two waveforms have very different frequencies? Phase is 
then meaningless.

> Then the waveforms are "similar" when
>
> (K*f(A)-t) - f(B) is "approximately" zero. Where you set a maximum
> value for a "zero" sum.
>
> A good first guess at K would be the ratio between the maximum values
> of the largest positive samples of the two waveforms.

[groan; head in hands]

Jerry
-- 
Engineering is the art of making what you want from things you can get.

[toc] | [prev] | [next] | [standalone]

#940

In comp.theory Geoff <geoff@invalid.invalid> wrote:
..
> I don't know much about open source packages that might be available
> but the algorithm you seek is the Fast Fourier Transform (FFT). Given
> an arbitrary waveform, the FFT can break it down into it's harmonic
> components. Once you have the harmonic coefficients you can compare
> them between waveform A and B to see if they have the same "shape".
> You would probably have to empirically determine how close the
> coefficients of the terms have to be to call them "similar".
...

EKG contain various chaotic phenomena that -- as they say -- confound
many simple methods.

So comparing FFT's is probably not a robost method for things like EKG. 
If the pulse rate varies a little -- but presents essentially the 
same "feature set" -- a Fourier transform will appear "distant" but 
should be "close".  (DFT will probably be than the continuous case).

OTOH if 2 transforms appear "close" (e.g. some kind of simple distance
metric or overlap integral) the underlying functions can be quite different
and the charts should be seen as such.

Not knowing exactly how the thing is mechanised the most robust method
I can visualise is to copy the way the experts compare charts.

They extract "features" that are known to be statistically robust and
see whether 2 charts have the majority of those features. I.e. some kind
of Bayesian methodology. (No doubt one of these features will be the 
"heart rate" and other frequencies related to "valve flutter" -- esp
of some of the valve leaves are stiff -- but these may not be as important 
as other transitory effects that probably won't register in the frequency domain).

Such a Baysean system can be tuned (as I'm now learning the hard way)
by maximizing some kind of "skill" metric -- i.e. discount decisions
that can largely be due to chance alone.

-- 
[Call me kook:]
>A scientist cites a data point that is consistent with a trend and
>says "This data is consistent with the trend; no surprise".
>A kook cites a data point inconsistent with the trend and says "Surprise!
>The trend is Wrong Wrong Wrong!".
Sorry but 1917 invalidates the trend.
-- BONZO@27-32-240-172 [daily nymshifter], 7 Feb 2011 13:29 +1100

[toc] | [prev] | [next] | [standalone]

#941

On Oct 17, 2:29 pm, ri_we...@yahoo.com wrote:
> On Oct 16, 12:32 pm, Jerry Avins <j...@ieee.org> wrote:
>
>
>
>
>
> > On 10/16/2011 12:27 PM, ri_we...@yahoo.com wrote:
>
> > > Cross posting to comp.dsp
>
> > > On Oct 14, 6:32 pm, ri_we...@yahoo.com wrote:
> > >> Can someone suggest pointers to good algorithms that can be used for
> > >> comparing the raw data corresponding to two waveforms to see if they
> > >> are similar {e.g. EKG waveforms of two healthy and normal human
> > >> beings}?  I am looking for open source code or pseudo code, rather
> > >> than terse mathematical equations, since the latter may not lend
> > >> themselves to easy and efficient implementation.
>
> > Can you define "similar" algorithmically?
>
> > Jerry
> > --
>
> Jerry,
>
> Kindly don't clobber me.  I will attempt to define "similar" in layman
> terms rather than algorithmically:)
>
> Two waveforms may be deemed similar if at least some of the following
> are true:
> - A human, who is shown the trace of the two waveforms, will conclude
> that the waveforms are similar
> - They have a constant phase difference, although amplitudes may not
> be the same
> - To a large extent they have the same harmonics, although not
> necessarily the same amplitude for the various harmonics
> - The harmonics of one waveform are a multiple of the harmonics of the
> other waveform
> - They have similar structures for peaks and troughs, although
> amplitudes may not be the same
>
> With this understanding, can someone provide pointers to algorithms
> and/or opensource implementations?
>
> TIA,
> Richard- Hide quoted text -
>
> - Show quoted text -

>>With this understanding, can someone provide pointers to algorithms
>>and/or opensource implementations?

You mean no math and "free" as in beer ?

Keep looking, dude... and don't forget to let us know about your
findings...

Here is one random reference to get you started:

http://www.math.dartmouth.edu/archive/m53f07/public_html/proj/MehtaMiller.pdf

But first you'd better get a book on chaos theory and nonlinear time-
series analysis and study it for couple years...

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web