Algorithms for comparing waveforms

[r***@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]

Post by r***@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.

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.

[r***@yahoo.com]

Cross posting to comp.dsp

Post by r***@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.

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]

Post by r***@yahoo.com

Cross posting to comp.dsp

Post by r***@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.

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.

Post by r***@yahoo.com
Two waveforms may be deemed similar if at least some of the following
- 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)

Post by r***@yahoo.com
- 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.

Post by r***@yahoo.com
- 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.

Post by r***@yahoo.com
- 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.

Post by r***@yahoo.com
- 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?

Post by r***@yahoo.com
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

[Geoff]

Post by r***@yahoo.com

Cross posting to comp.dsp

Post by r***@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.

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

[Jerry Avins]

Post by Geoff

Post by r***@yahoo.com

Cross posting to comp.dsp

Post by r***@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.

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

Post by Geoff
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
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.

Post by Geoff
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

[k***@kymhorsell.com]

In comp.theory Geoff <***@invalid.invalid> wrote:
..

Post by 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".

...

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.

[fatalist]

Post by r***@yahoo.com

Cross posting to comp.dsp

Post by r***@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.

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