Review on Progressive Coding Technique for 2-D ECG Compression

Review on Progressive Coding Technique for 2-D ECG Compression

Dhanashri N. Kharche,

PG Student

Elect. & Telecom. Department Sinhgad College of Engineering, Vadgaon(BK)

Pune, India

Supriya O. Rajankar,

Ass. Professor & PG Coordinator

Digital System, Elect. & Telecom. Department Sinhgad College of Engineering, Vadgaon (BK)

Pune, India

Abstract Medical signals must be compressed before transmission due to storage limitations and bandwidth. Set Partitioning in Hierarchical Trees (SPIHT) coding technique has become a standard model for ECG signal compression. It is an efficient method for lossy and lossless coding of medical signals. With some modificationin the SPIHT algorithm M- SPIHT algorithm have been presented. In this paper, use Dual Tree Complex Wavelet Transform (DT-CWT) for coding and Compare encoding performance with SPIHT and MSPIHT. In this project, we study the commonly used algorithms for signal compression and compare its performance. We apply this compression algorithm on 2-D ECGusing MIT-BIH arrhythmia database.

Index TermsElectrocardiogram (ECG) compression, Discrete wavelet transform (DWT), Dual tree complex wavelet transform (DT-CWT), Set partitioning in hierarchical trees (SPIHT),Modified set partitioning in hierarchical trees (MSPIHT).

1. INTRODUCTION

   Multichannel ECG data provide cardiologists with essential information to diagnose heart disease. In an ambulatory monitoring system, the volume of ECG data is essentially large, as a long period of time is mandatory in order to gather enough information about the patient. As an example, with the sampling rate of 360 Hz, 11 bits/sample data resolution, a 24-hour record needs about 43 Mbytes per channel. Therefore, an effective data compression scheme for ECG signals is required in many practical applications including: (a) ECG data storing; (b) ambulatory recording systems; and (c) ECG data broadcast over telephone line or digital telecommunication network.For good analysis of disease, we required 12 to 24 hour of recording. The restrictions on storage capacity are such that medical signal compression techniques must be employed to reduce the storage requirements.If wecompress ECG data then for storage require less memory. For efficient storage and transmission of ECG signal overtelephone line, it is required to store or transmit data, withoutany loss of diagnostic characteristic, this is a challenge totransmit compressed ECG signal. The ECG waveform is havingcharacteristics that are important for diagnosis of the disease.

   In past, ECG Signal is compressed using 3 methods can be classified as: direct methods, parameter extraction methods and transform methods. ECG signal is compressed using

   AZTEC proposed by V. Kumar, S. Saxena, V. Giri, and Dilbag Singh [1] and SAPA proposed byV. Kumar, S. Saxena, and V. Giri [2] which is classified as direct method. It compresses ECG data directly. This method is less complex. Disadvantage of this methods are that in high fidelity area it cant achieve high compression ratio. VQ (vector Quantization) proposed by C. Sun, and S. Tai [3] and NN (neural network) proposed byS. Saxena, V. Kumar, and

   V. Giri[4] are the parts of parameter extraction methods. In this it extract particular characteristic or parameter. Compression ratio is high but selected models and their robustness is weak. Transform methods [5]-[7] are working in time and frequency domain. It convert signal in time- frequency representation and remove redundancies.

   ECG signal is non-stationary signal means having different frequency component at different time and location. In recent years,compression is also required along with encoding of signals and images in an efficient way of multimedia based application. Forstill signal compression, the JPEG standard has been established by ISO and IEC [8]. JPEG performance is degrades at low bit-rates mainly because of the underlying block-based DCT scheme. Wavelet transform is good method for compression of ECG signal because it is working in both frequency and time domain. The quality of compressed medical signal must reach an acceptable level to avoid misdiagnosis. In recent years, many wavelet transform based ECG data compression techniques with low reconstruction error and fine visual quality have been proposed. Most of these wavelet-based ECG Compression algorithms disregard the redundancy between adjacent heartbeats and then apply wavelet transform directly to the acquired one-dimensional (1-D) ECG data.

   The SPIHT algorithm represents advancement over the innovative wavelet-based image coding method, it employ a tree representation of the zero wavelet coefficients. Sheni Chuan Tai, Chia-Chun Sun and Wen-Chien Yan proposed a 2-D ECG compression based on Wavelet and Modified SPIHT using cut and align, preprocessing approach [9]. MSPIHT has better performance than the originalSPIHT algorithm.

   In ECG signal, there is some similarity between adjacent heartbeats; each beat has almost same frequency and time signal. Some ECG compression technique used for 1-D (one dimension) not utilizes such similarity between each beat of

   heart, due to this capacity requirement increases which results in increasing its cost. So, 2-D (two-dimensional) transform system is used to overcome this problem, which utilizes correlation between adjacent heartbeat, to improve the compression of ECG signal and also its quality performance. In this paper, preprocessed ECG signal and convert ECG signal into 2-D and then apply DT-CWT for coding, encode it by SPIHT and MSPIHT algorithm.

   A. ECG Signal Compression Process Flow

   The DT-CWT based ECG signal compression method using progressive SPIHT and MSPIHT encoding and decoding is shown in the Fig.1.

   ECG signal is preprocessed and convert it into 2-D. Q-shift DT-CWT is apply on ECG image for decomposition of signal. Apply SPIHT or MSPIHT algorithm for encode wavelet coefficient.

   SPIHT or MSPIHT algorithm is considered as state-of the- art algorithm for ECG signal compression.The principles of the SPIHT or MSPIHT algorithm are to partition wavelet coefficients in subband and transform coefficients by magnitude with sorting algorithm. Most significant bit is transmitted to decoder.

   According to ECG signal compression process flow, first ECG image is decomposed using DT-CWT followed by a SPIHT or MSPIHT coding process. The SPIHT or MSPIHT

   The SPIHT algorithm workson a wavelet-transformed image.This image must be equal in length and width of an integer power of 2. It encodes the wavelet coefficients. Then this encoding sends low order bits of coefficients after high- order bits. The SPIHT algorithm only needs anywhere from 1 to log2N steps of the wavelet transform. Energy is concentrated in coefficients that those coefficients tend to have a larger magnitude and there is a spatial self-similarity between the parent and child pixels that propose an encoding scheme which move from the parent to the child will reveal decreasing coefficient magnitudes. It is a very fast coding

   /decoding algorithm [11].

   The SPIHT algorithm used three lists for encoding as follows:

   • List of Insignificant Pixels (LIP) contains smaller magnitudes coefficients that have smaller than the threshold.

   • List of Insignificant Sets (LIS) contains sets of wavelet coefficients that have magnitudes smaller than the threshold which is denoted as insignificant. The sets exclude the coefficients corresponding to the tree and all sub tree roots. They have at least four elements.

   • List of Significant Pixes (LSP) is a list of pixels contains magnitudes larger than the threshold which is denoted as significant.

     In figure 2 the term significant pixel is denoted as the magnitude of a pixel exceeds or equals the present threshold and an insignificant pixel is denoted as a pixel whose magnitude is less than the present threshold. An insignificant set can be one of two types of sets. In this, set H contains all the pixels in the last level of the wavelet transform that was performed, including the coarse and detail coefficients. Figure 3 shows the wavelet tree structure of SPIHT algorithm.

     The following figure shows the corresponding tree representations:

     coding algorithm will be used to encode the wavelet coefficients. Output of SPIHT or MSPIHT coder is

     Initialize: Initialize:

     Initialize:

     If S	LIS D (m, n) or L (m, n)

     Ds of Roots

     compressed ECG image. Now reverse processing is carried out for decomposition part to obtain the reconstructed ECG image. The SPIHT or MSPHT decoder will be used to decode the encoded coefficients and with inverse DT-CWT used to get the reconstructed image.

     All Roots

     LIP

     (i, j)

     If S

     Empty

     LSP

     (l, k)

2. SET PARTITIONING IN HIERARCHICAL TREES (SPIHT)

   SPIHT algorithm, presented by Said and Pearlman, is a highly progressive version of the EZW algorithm [10] [11]. By using this algorithm, the highest PSNR values for given compression ratios for a variety of images can be achieved. It delivers a well comparison standard for all subsequent algorithms. SPIHT stands for Set Partitioning in Hierarchical Trees. Hierarchical trees denote to the quadtrees as defined in EZW. The term Set Partitioning mentions to the way these quad trees divide or partition and the wavelet transforms at a given threshold.

   IS S

   Set Partitioning Operation

   Single-Element Subsets

   Os stripped from Ds

   S Significant, IS Insignificant

   Fig-2: SPIHT Algorithm [12]

   Multiple-Element Subsets Remainder from Ds as Lsor

   Os (as Ds) stripped from Ls

   Fig-3:Wavelet Tree Structure of SPIHT Algorithm

   • (i, j): set of coordinates of all offspring of node (i, j)

   • D (i, j): set of coordinates of all descendants (all nodes that are below) of node (i, j)

   • H (i, j): set of all tree roots (nodes in the highest pyramid level)

   • L (i, j): D (i, j) O (i, j) (all descendants except the offspring of node.

     A general method for the code is as follows:

     Step 1: In this, Initialization of threshold and order list

     Output n, n can be selected by user or predefined for maximum efficiency, LSP is empty; add starting root coordinates means it assign coefficients of the entire root node in low-pass sub-band to LIP and LIS. The sorting of in the LIP and LIS is same with that of EZW zero tree structure. Step 2: Sorting Pass

     The aim is to encode the significant coefficient of current bit. Two main steps as follows:

     1. Check all the wavelet coefficients in LIP to determine whether they are important coefficients:

   • If it is yes, then output 1 and the sign bit, positive or negative sign bits of wavelet coefficients are represented by 1 and 0, and then remove the coefficient from LIP and add to the end of order list LSP.

   • If it is not, we do not need to remove it from the list of LIP and give a direct output of 0.

     1. According to the type of trees, check all the important trees in the LIS:

   • D-type tree: If the tree is important, we need to give output of 1, and then encode the coefficients on sub- node. If the coefficient of child node is important, we need to make output of 1 and sign bit, then move it into LSP. If the coefficient of child node is not important, the output shall be 0, and then move it in LIP. If the child node has offspring, put the tree to the

     end of LIS list and observe it as L-tree. If this tree is not significant, then we require making output of 0.

   • L-type tree: If the tree is important, then make output of 1 and move each child node to the end of LIS as a D- tree, then delete the parent tree from LIS. If this tree is not significant, then the output shall be 0. Algorithm provides that if there are coefficients which can make inspection on the SPIHT have to check the coefficients in LIP; if there is no coefficient for inspection in LIP, then remove the unprocessed coefficients from LIS and put in LIP; if in LIS there are coefficients which have not been treated, then SPIHT will end segmentation processing of this time.

   Step 3: Refinement Pass

   The aim is output but not the improving position of important factor in generated in the process of scanning. For each node (i, j) in LSP, if (i, j) is not just added during the scanning process, then absolute value |Ci, j| of the output of this node coefficient can be transmitted.

   Step 4: Update the threshold

   Decrement n by 1 i.e. deduces half of the threshold value and conduct the next level coding (back to step 2).

3. MODIFIED SPIHT ALGORITHM

For ECG compression, SPIHT technique is efficient. Some improvement in SPIHT algorithm this will be more efficient technique for compression of signal. After wavelet decomposition, all important informations are located in low-low band. In SPIHT technique, coefficient is divided into sub-bands and using 3 list of partitioning encodes the coefficients. Because of these lists require high memory for storage of data. Also, during encoding we add and delete data. This operation require more time for encoding. This is major drawback in SPIHT algorithm. To overcome this problem MSPIHT technique proposed. In this algorithm, sorting operation and refinement operation are combined. Two new concepts are presented for modification in SPIHT algorithm as number of error bits and absolute zerotree.

1. Number of Error Bits: In SPIHT algorithm, significant pixels are stored in LSP. Insignificant pixels and insignificant sets are stored in LIP and LIS simultaneously. List of significant pixel are send to decoder. In this the least significant bits will be omitted. These omitted parts of bits are called as truncating error.

   We define number of omitted bits which is number of errors bits (denoted as Be) before encoding process. Coefficients in sub-bands are founds as significant or insignificant its first bit are outputted. In this coefficients are not stored into LSP and LIP.

2. Absolute Zerotree: During wavelet decomposition, significant pixels are lies in low band. In this magnitude of coefficients are decreases rapidly. In subband there are some coefficients are so small that some tress will be zerotrees before expected compression ratio. In SPIHT, Coordinates of zerotree are stored in LIS and it will never be removed. In this LIS is rapidly expanded.

In MSPIHT, We have defined to indicate the number of truncating error bits. In all zerotree, the magnitude of its descendants is lower than truncating error bit then it will be never significant. This coordinates are need not to store in

LIS. Thus we dont need to scan repeatedly and because of that lower time required for scanning and increased the speed of algorithm.

This modification in SPIHT algorithm, it require less memory to store because of removing LIP and LSP. Its speed is also increased because it does not scan the coefficients repeatedly.

LIS are splits into 2 parts as the insignificant pixels in D(i,j) and the insignificant pixels in L(i,j). We referred it as Type 1 and Type 2. In this sorting and refinement pass are combined. It reduces the execution time. In wavelet coefficients, the largest value in MSB and its descendants are stored in Type

1. Last error bit is omitted and rest of th bits of pixel with its sign bit is transferred to decoder. In first pass, the magnitude of pixels and sign information is coded.

Each coefficient has four offspring. This coefficient and its adjacent coefficients with the same parent are grouped. It is coded together to remove redundancy. The same scheme is used for all coefficients. MSPIHT coded from higher level coefficients. For each coordinate (i,j), it codes the individual coefficient C(i,j) and the descendant set D(i,j). For all coordinates, it checks whether it is significant from previous coding pass.

After that, MSPIHT check significance of D(i,j) coefficients and if it is insignificance in previous coding pass then check its maximum value in D(i,j). If it is greater than threshold (2n) then transfer 1 and if it is less than threshold then transfer 0. If coefficient is greater than threshold then D(i,j) is partitioning into O(i,j) and L(i,j) and remaining entry is removed from LIS. It check all coefficients in O(i,j) and also send 1 for its positive sign and 0 for its negative sign. If zero (k,1)=1 then transfer 1 bit and if not, then consider this branch as zerotree and remove it. In subband, If L(i,j) is exist it will move in type 2. After that check its significance then it will move to LIS. If it is insignificant then remove it from LIS list. Check all coefficients and for next pass the value for threshold (2n) means n is less by one. The process is continued till all coefficients are coded.

4. CONCLUSIONS

In this paper, we studied ECG compression techniques. SPIHT algorithm is efficient for encoding of ECG signal. Storage of coefficients in three lists namely LIP, LIS and LSP, it required more memory. In LIS, checking of coefficients repeatedly, it requires more time for computation. Making some changes in SPIHT algorithm, it will be more efficient. Storage of coefficients required less memory and its computation speed will be high. MSPIHT will be good compression algorithm for ECG image. Using zerotree encoding algorithm it is more effective and it required less time. It will be better algorithm than other wavelet one. This algorithm is also used for other medical signal or image compression. It will also use for telemedicine applications.It will gives high PSNR value and compression ratio at low bit rate.

ACKNOWLEDGEMENT

We would like to thank Dr. M. B. Mali, Head of Department, Dept. of E&TC, SCOE, Pune and Dr. S. D. Lokhande (Principal), SCOE, Pune for providing necessary guidance and infrastructure for completion of work.

REFERENCES

1. V. Giri, and Dilbag Singh,V. Kumar, S. Saxena, Improved modified AZTEC technique for ECG data compression: Effect of length of parabolic filter on reconstructed signal, Computers and Electrical Engineering, vol. 31, no. 4-5, pp. 334-344, Jun.-Jul. 2005.

2. V. Kumar, V. Giri andS. Saxena, Direct data compression of ECG signal for telemedicine, International Journal Systems Science, vol.37, no. 1, pp. 45-63, Jan. 2006.

3. C. Sun, and S. Tai, Beat-based ECG compression using gain-shape vector quantization, IEEE Trans. Biomed. Eng., vol. 52, no. 11, pp. 1882-1888, Nov. 2005.

4. V. Kumar , S. Saxena and V. Giri, ECG data compression using EBP- NN, IEEE Technical Review, vol. 20, no.6, pp. 583-604, 2003.

5. L. Hadjileontiadis, R. Istepanianand S. Panas, ECG data compression using wavelets and higher order statistics methods, IEEE Trans. Biomed. Eng., vol. 5, no.2, pp. 108-115, Jun. 2001.

6. B. Rajoub, An efficient coding algorithm for the compression of ECG signals using the wavelets transform, IEEE Trans. Biomed. Eng., vol. 49, no.4, pp. 355-362, Apr. 2002.

7. M. Blanco-Velasco, F. Cruz-Rolda´n, J. Godino-Llorente, and K. Barner,ECG compression with retrieved quality guaranteed, Electronics Letters, vol. 40, no.23, pp. 1466-1467, Nov. 2004.

8. Ali Bilgin, Michael W. Marcellin and Maria I. Altbach, Compression of Electrocardiogram Signals using JPEG2000, IEEE Transactions on Consumer Electronics, Vol. 49, No. 4, NOVEMBER 2003.

9. Shen-Chuan Tai, Chia-Chun Sun*, and Wen-Chien Yan, A 2-D ECG Compression Method Based on Wavelet Transform and Modified SPIHT IEEE Trans. Biomed. Eng., vol. 52, no. 6, June 2005.

10. Li Hui Fang, Miao GuoFeng and XuHouJie, Images Compression Using Dual Tree Complex Wavelet Transform, IEEE International Conference of Information Science and Management Engineering, pp. 559-562, August 2010.

11. Jianxiong Wang and Fuxia Zhang, Study of the Image Compression Based on SPIHT Algorithm, IEEE International Conference on Intelligent Computing and Cognitive Informatics (ICICCI), pp. 130- 133, June 2010.

12. S.A. Wagh, S.O. Rajankar, D.G. Ganage and O.S. Rajankar, Performance Evaluation of DWT and DT-CWT with SPIHT Progressive Image Coding for Natural Image Compression, International Journal of Advanced Research in Electrical, Electronics and Instrumentation Vol. 1, Issue 4, October 2012.

BIOGRAPHIES

D. N. Kharche born in 1991, obtained BE degree from Dr. BabasahebAmbedkarMarathwada University, Aurangabad, India in 2012. Currently pursuing ME degree from Sinhgad College of Engineering, Pune, India. Her field of interest is signal and image compression.

S. O. Rajankar born in 1970, obtained BE degree from University of Pune, India and ME degree from Government College of Engineering, Pune, India. Joined the Department of Electronics & Telecommunication Engineering, Sinhgad College of Engineering, Pune, India as a lecturer in 1993 and is presentlyworking as Associate Professor and PG Coordinator, Digital System, Dept. of E&TC. Her current research interest includes signal-image processing, network & lines and electromagnetics.