1.  Field of the Invention
This invention relates to compression and automated analysis of electrocardiograms and other signals having recurring features with occasional significant deviations. 
2.  Description of the Prior Art
The correct medical diagnosis of heart problems often depends upon the analysis of ECG signals.  Where a heart problem is intermittent or irregular, it becomes necessary to record these ECG signals, sometimes while the patient is performing normal every-day activities.  Additionally, even for those patients with repeatable heart problems, there is a need to record and archive ECG signals for subsequent analysis and future comparison purposes, or to identify signal changes over time. 
Traditionally ECG records have been created on either long-scroll paper or on analog-technology tape recordings.  Whilst both these methods provide accurate imagery for subsequent analysis purposes, they are bulky to archive and are only suitable for short term recordings (a few minutes to 0.5 hours).  In more recent times, use has been made of digital technology to a) convert the analog ECG signal to digital samples at a suitably selected rate and resolution, and b) store the digital samples on a suitable storage media such as computer memory, computer disks or digital tape recordings.  Whilst this mechanism has increased storage time, storage media choices, and provides the possibility of computer enabled analysis of signals, there are still very real limitations in the length of recording time possible without severe limitations on sampling rates and signal resolution.  If sampling rate and signal resolution are lowered to reduce the size and number of digital samples to be recorded, thus increasing possible recording time, unacceptable degradation to the reconstituted signal occurs from a clinical analysis point of view.  Hence all commercially available ECG recording devices use some form of compression of the digital signal to increase the recording time possible on a given size of storage media. 
A large number of compression algorithms have been developed and a variety of them are in use in current commercial devices.  Compression algorithms are traditionally categorized into two classes, non-lossy and lossy.  Non-lossy algorithms have the property that the original digital signal prior to compression can be completely reconstituted.  These compression algorithms generally rely on removing duplicate or repeated information, in some form, from the original digital signal.  Such techniques as run-line encoding and difference recording in various forms, are at the heart of most non-lossy compression algorithms.  However, fundamentally such algorithms are limited in the amount of compression possible--there is only so much redundancy in a given signal that can be removed. 
Lossy compression has the potential to achieve much greater compression factors than lossless compression algorithms, permitting greater archiving capacities or reductions in data storage.  These lossy algorithms are therefore of great interest for ECG recording compression purposes. 
ECG traces are characterized by a high rate of regularity from signal to signal, and dramatic differences in the range of signal frequencies present in different portions of a trace.  For clinical purposes, certain portions of the ECG are of great significance. 
A heartbeat is naturally divided into three segments, which are known as the PQ, QRS, and ST blocks.  The R-peak of an ECG is an easily identified feature which occurs roughly in the center of the QRS-block.  The PQ-block occupies 2/5 of the time from the current beat's R-peak back to the previous beat's R-peak, less the portion which is devoted to the QRS-block.  Similarly, the ST-block occupies 3/5 of the time forward from the current beat's R-peak to the next beat's R-peak, less the portion which is devoted to the QRS-block.  The ECG sampling frequency is typically chosen to resolve the QRS-complex, which has a larger range of frequencies than the PQ- and ST-blocks; the latter blocks are therefore significantly oversampled.  Many of the features of clinical interest occur in the QRS-complex. 
Lossy compression algorithms that are not designed to preserve these significant portions of the ECG will usually achieve high compression ratios only at the expense of these higher-frequency, clinically significant features in the ECG signal.  For diagnostic applications in cardiology, the loss of this information is unacceptable.  Therefore, lossy algorithms have been, for the most part, of extremely limited use in these diagnostic applications. 
Another area in which significant gains in technology would be of great benefit is in the analysis portion of the clinical process.  When there is reason to believe that a heart event of clinical significance has occurred during a long ECG recording, a technician must review the entire length of the ECG to locate the event; this is typically done manually, without any form of automatic recognition.  That portion of the recording is then passed to a cardiologist for a more careful review, and for diagnosis.  When the recording is extremely lengthy, this reviewing process is extremely time-consuming and tiresome for the technician; for these reasons, it is an error-prone process.  Consequently, there is a need for an automated review process for ECG recordings; a highly sensitive automated review algorithm could be used to automatically identify potential significant events in a long ECG recording for further scrutiny by a technician, greatly reducing the time required to analyze the trace, and making the process less error-prone for the technician.  Due to the highly localized nature of ECG signal changes during significant events, this automatic identification of significant events is extremely difficult to do when the signal is analyzed in the time or frequency domain alone.  The theoretically optimal choice of transform domain for the representation of variations in signals is given by the Karhunen-Loeve Transform. 
The Karhunen-Loeve Transform (KLT) is an analysis tool which has long been recognized as a useful means of localizing signal irregularities in a sample of signals which are of uniform length.  It is particularly useful in analyzing signal samples where there is a great deal of similarity from signal to signal, when a great deal of the variance present in a signal sample can be captured in a few coefficients of the KLT.  The KLT is an orthonormal basis transformation which, when computed for a specific set of signal samples, has the following properties relative to the signal sample:
It is the optimal decorrelating transform for the signal sample; that is, each coordinate of the transformed signal sample, viewed as a random variable on the signal sample, is uncorrelated with every other coordinate.  PA0 If the basis elements of the KLT for a given signal sample are arranged in decreasing order of the variance captured in the corresponding coordinates, then the mean square error of representation for an element of the signal sample is minimized over all possible representations of length m when the first m basis elements are used to represent a signal.  PA0 It overcomes the problem of loss of clinically significant resolution in the signal which is reconstituted from the compressed signal.  PA0 It provides a natural means for automating the identification of clinically significant events, which can be accomplished entirely within the transform domain, i.e., before the signal is reconstituted using the inverse algorithm. 
The KLT is calculated by first computing the covariance matrix for the signal sample.  If the signals in the sample are of length K, then the covariance matrix is a K by K matrix whose (k,j) coordinate is the cross-covariance of the k coordinate and the j coordinate of a signal sample, viewed as a pair of random variables.  This matrix is symmetric; a well-known theorem states that it is therefore diagonalizable.  The basis transformation into a complete set of eigenvectors for the matrix constitutes the Karhunen-Loeve for the signal sample. 
The KLT is clearly dependent on the characteristics of the signal sample; the basis vectors for the KLT are of a form completely dependent on the sample, and therefore no fast algorithms for calculating the exact transform in all cases is known.  For the general sample of length K, the calculation of the KLT is an algorithm of complexity K.sup.3.  In cases where the sample length is high, and the characteristics of the sample are well understood, suboptimal decorrelating transforms (such as the Discrete Cosine Transform, in the case of many audio signals) are sometimes used in place of the KLT to keep computational complexity, and the cost of transformation, down. 
Typical error measures applied to signal compression, for example, signal-to-noise ratio, mean-squared error, and root-mean squared error, are based on average reconstruction error, and hence are insensitive to individual waveform departures from the typical waveform.  In medical signal analysis, which includes ECG analysis, such localized departures from typical signal behaviour are of clinical interest and are often evidence of pathology.  Using an error control technique based on average error leads to potentially large localized reconstruction errors, and hence the potential loss of clinically significant information.  A need remains in the art for a compression scheme capable of automatically detecting and correcting for localized departures from typical signal behaviour, in order to provide a high compression ratio and allow clinically acceptable reconstruction.