Compressing ECG Signals using Matching Pursuit

The present project represents an exploration effort to achieve good compression of ECG signals by utilizing a transform to redundant dictionary of basis functions.

Abstract
The present project represents an exploration effort to achieve good compression of ECG signals by utilizing a transform to redundant dictionary of basis functions. The chosen basis characterizes as having a good energy distribution in both time and frequency domains.

Motivation
Why to compress ECG signals?
A 24-hour long ECG signal having 10 bits per sample requires about 1.3 GB memory to save.
An ordinar hospital may have many thousands ECGs per year. From here ine can easily conclude that compressing is necessary.

ECG basics
Most ECG signals have a common pattern with a highly important area called P-QRS-T. It looks like:

1

In our experiment we were interested to ensure a high quality compressing of the above area. The remaining flat pieces of ECG are not very important so we could save some bandwidth on them. This optimization led to comparatively good compress ratio but the algorithm we developed for extracting P-QRS-T area was simple and might not work correctly with all ECG signals.

Implementation
The project was implemented in Matlab that made our work convenient but disabled us to conduct some time profiling to speed up computations.

The compress algorithm has several stages:
1) Compilation of a dictionary of basis sampled functions
2) Separating the long input signal to shorter frames to enable transform
3) Iterative transform executing using the following formula: 2
the stop condition is a desired precision
4) The resulting set of coefficients(scalar products) is enhanced by a back projection algorithm
5) Storing the computed coefficients and dictionary indexes

The decompress algorithm is simple:
1) restore frames using 3
2) assembly frames into contiguous signal

Some remarks and implementation details should be mentioned.

A) As a basis we chose a subset of Gabor functions given by:
4
where g(t) is a normalized Gaussian function. To obtain a set of sampled Gabor functions one should use discrete values of s – scale, u – translation, xi – modulation.
As already pointed such a subset of Gabor functions gives a good energy distribution in both time and frequency.

B) Let the sampled basis vector is of n dimentions, then the dictionary may be represented as a matrix having O( n*n*log(n) ) elements. This means longer basis vectors lead to fast performance fall( because the algorithm scans the dictionary exhaustively at each iteration ). On the other hand with larger dictionary better compress ratio may be achieved.

There are some results obtained after the program execution

5

The above graph refers to these parameters:
Basis vector length: 64,
Approximate compression ratio 3.34, percent mean square difference(PRD): 0.98%, elapsed time(sec): 11.76.

Much better result in compress ratio achieved with a dictionary containing 128-long basis vectors:
6
Approximate compression ratio: 6.17, percent mean square difference (PRD): 0.99%, elapsed time (sec): 35.48

Conclusion
Our goal was to investigate an applicability of matching pursuit algorithm to ECG signals compressing.
Although we got a good compression ratio, the algorithm turned out to be rather time and memory consuming.
Thus we have a rich area to search for various of optimization techniques that may lead to better performance.

Acknowledgments
We would like to thank our supervisors Johanan Erez and Elad Yomtov and the VISL laboratory for their support and guidance and to the Ollendorff Research Center Fund which supported this project.