Algorithms for comparing waveforms

[ri_w...@yahoo.com]

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

[Thad Smith]

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

[ri_w...@yahoo.com]

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

> 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

[Jerry Avins]

On 10/17/2011 2:29 PM, ri_w...@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.

[Geoff]

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.

[Jerry Avins]

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]

[k...@kymhorsell.com]

In comp.theory Geoff <ge...@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

[fatalist]

> 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...