Abstract: In this study, a novel video codec called L Shaped Morpho Codec (LSMC) based on Lifting Wavelet Transform (LWT) is proposed. Each frame in the video sequence is first decomposed into different sub-bands using LWT at maximum decomposition level. The proposed LSMC keeps track of significant pixels of sub-band in the scan order of left to right and top to bottom. If the pixel is found significant, then the morphological dilation is applied immediately to find the significant pixels using L shaped structuring element. This will improve the rate-distortion performance for lossy compression. Experimental results show that the proposed LSMC outperforms standard codec’s such as SPIHT and SPECK for lossy and lossless compression. For lossy compression, LSMC performs well at higher bit rates than the lower bitrates. The average bits per pixel (bpp) required for lossless compression by LSMC is less by 0.13 bpp over SPECK.
INTRODUCTION
The recent advances in medical imaging techniques such as Computed Tomography (CT) and Magnetic Resonance Image (MRI) produce large amount of medical images/videos. To reduce the storage space required by these images/videos an efficient compression technique is required. Fuzzy scheme along with H.264 for medical video compression is explained by Rajarathnam (2008). Motion complexity is used to estimate a frame’s target bit so that the bit allocation is in accordance with the complexity of frame’s motion contents and perceptual mode decision is employed to allocate the macro block’s bits perceptually.
Scalable video coding is a latest video compression standard which is explained by Nazir and Raja (2011). This standard is tested on two different types of videos namely Brain Computerized Tomography (CT) scan and Echocardiography. Spatial prediction, temporal prediction and context modeling is used as a new compression methods by Kumar and Sivaramaraju (2005) for compressing the video sequences. This proposed method gives as a good compression ratio and excellent image quality. For compressing a medical video an Adaptive Particle Swarm Optimization (APSO) is developed by Deshmane and Talbar (2010). The quality of the medical videos is enhanced up to 1 db using APSO in terms of Peak Signal to Noise Ratio. In comparison with exhaustive search algorithms, 90% of computational time is saved by APSO.
A two step method is presented by Liu et al. (2003) to compress medical monitoring video more efficiently. Initially, motions in the video sequence are detected and the detected regions are segmented into rectangle image regions. As a result this two-step method improves the compression ratio by retaining the essential video quality.
An approach based on region of interest for the compression of coronary angiogram is proposed by Uma Vetri Selvi and Nadarajan (2012). Wavelet based contourlet transform coder is used based on the set partitioned embedded block coder.
The JPEG-LS is a standard compression technique which uses intracoding technique to compress a single image. A new compression standard is proposed by Miaou et al. (2009) which combines the compression procedure of JPEG-LS with interframe correlation of image sequences.
A new compression algorithm is constructed by Khan and Wahid (2011) for video capsule endoscopy. First, the test images are sub sampled and then use a simple encoder, differential pulse code modulation. Finally, a lossless compression method Golomb-Rice is used to compress the endoscopy sequences.
Discrete wavelet transform (DWT) based compression for high quality neurophysiology is proposed by Xu et al. (2005). A video compression based on intraframe coding called Motion-JPEG 2000 is proposed by Fossel et al. (2003). The main advantages of this standard is higher bit depth of the components and the lossless mode.
Adaptive symbol prediction technique based micro angiogram video compression is presented by Vishnu et al. (2012). This technique utilizes the energy compaction property of integer wavelet transform. The main drawback of JPEG and MPEG technique is it creates block artifacts.
To eliminate this, a novel technique based on DWT for video compression of angiographic images is presented by Ho et al. (1996). In this study, a novel morpho codec for medical video compression based on lifting wavelet transform is proposed.
LIFTING WAVELET TRANSFORM
The proposed system for medical video compression is built based on LWT. The lifting scheme is a system for both designing wavelets and performing the discrete wavelet transform. Actually it is worthwhile to combine these steps and design the wavelet filters while performing the wavelet transform. The wavelet co-efficient are real numbers in Discrete Wavelet Transform (DWT) is the main drawback of DWT. The Lifting Scheme (LS) presented by Swelden’s (Julien et al., 2001; Pan et al., 2007) allows an efficient implementation of the DWT. Another property is that the ideal reconstruction is ensured by the structure of the LS itself. This allows latest transformations to be used. One such transformation is the Integer Wavelet Transform (IWT) (Bryt and Elad, 2008). The Lifting Scheme (LS) has been introduced for efficient computation of the DWT. Its main advantage with respect to the classical filter bank structure lies in its better computational efficiency and in the fact that it enables a new method for filter design. Each filter output is rounded to the nearest integer is a basic modification of linear transforms. IWT can be used to have a unified lossy and lossless codec.
It exploits the redundancy between the High Pass (HP) and Low Pass (LP) filters important for Perfect Reconstruction (PR). It reduces the number of arithmetic operations up to a part of two compared to the Filter-Bank (FB) implementation. Its structure guarantees that the method is reversible, regardless of the filters used. FB and LS implementations of the DWT are mathematically the same. It is possible to transform any PR-FB into the LS structure. Figure 1 shows the filters Hi (z) with an even index I are called prediction steps, the ones with an odd index are called update steps.
| Fig. 1: | Basic lifting based wavelet decomposition |
| Fig. 2: | IWT based on the lifting scheme |
Figure 2 shows that each lifting step is followed by a rounding to the nearest integer operation. The basic plan behind the LS is the following. The input data splits into two signals corresponding to evenly and oddly indexed samples. Then one signal is convolved with a lifting filter and added to the other one. This action is called a lifting step. The role of the two signals is then reversed and further lifting steps can be applied. The aim of the scheme is that after K lifting steps, one signal corresponds to the high pass and the other one to the low pass coefficients. Generally, lifting steps using the low pass signal are called prediction steps and steps using the high pass signal are the update steps, as show in Fig. 1. The reconstruction algorithm is simply the application of the same structure, but in the reverse order. The reconstruction filter is exactly equivalent to its decomposition counterpart, except for its sign in Eq. 1, i.e.:
| (1) |
With loss of simplification, it will be assumed that the lifting structure starts with a guess step and is composed of an even number of steps. It is adequate to set H1(z) or Hk(z) to be equal to zero to take into account all other cases. This is necessary because wavelet coefficients have real values, and thus cannot be well encoded without loss. The fact that PR is insured by the LS construction permits another approach (Bryt and Elad, 2008). It is possible to replace the linear filters of the different steps by any nonlinear operation and still preserve the PR properties. This last point allows the computation of the IWT. By introducing a rounding operation on the output of each filter, as shown in Fig. 2, it is possible to guarantee that all DWT coefficients have integer values for integer inputs.
The nonlinearity introduced by the rounding operations after each filter has been replaced by additive random noise [with power spectral density function φkd(z) and Hkr(z), respectively for the decomposition and the reconstruction noise]. The quantization due to the density is symbolized by H(z). When the IWT coefficients transmitted without loss, the nonlinearity (rounding) introduced at the encoder will be remunerated by one introduced at the decoder. If the compression is increased, the scheme becomes lossy. This is done by further quantizing the IWT coefficients. In this case the relationship between the nonlinearity of the encoder and one of the decoder becomes unknown. The prediction of the differences observed between the two transforms (Zukoski et al., 2006; Sajda et al., 2003) becomes of primary importance for embedded coding schemes which compress data in lossy and lossless manners.
PROPOSED SYSTEM
In this study, a novel LSMC for medical video compression based on LWT is proposed. The LWT is chosen due to their high energy compaction property that puts most energy of the given input into a small number of coefficients. Before applying the proposed search algorithm, each frame in the given video sequence is decomposed by using LWT. The maximum level of decomposition is used in order to utilize the high energy compaction of LWT.
Let us consider an image I which is decomposed by using LWT. The transformed image exhibit a hierarchical pyramidal structure defined by the levels of decomposition, with the topmost level being the root (Pearlman et al., 2004). The finest and coarsest pixels lie at the bottom and top (root) level of pyramid respectively. As in SPIHT (Said and Pearlman, 1996), the criteria for a set T of pixels is significant with respect to n in Eq. 2 if:
| (2) |
where, is wavelet transformed coefficients located at pixel position (i, j). Otherwise it is insignificant. Thus the significance of a set T can be written as in Eq. 3:
| (3) |
The encoding procedure of LSMC starts by dividing each frame into rectangular regions. The construction of rectangle regions follows the view of SPECK that uses two sets namely S set and I set. These two sets are encoded by LSMC that follows the methodology in SPECK and SPIHT. For the significance test, S set is used in LSMC as same as SPECK whereas spatial orientation tree is used in SPIHT. The main difference between SPECK and LSMC is the encoding of set S. In SPECK, the set S is encoded when the pixel level is reached (Pearlman et al., 2004). The proposed LSMC extends the encoding procedure of SPECK by using L shaped structuring element as shown in Fig. 3.
| Fig. 3: | L shaped structuring element |
After the pixel level is reached in set S, the significant pixels are scanned by dilation operation based on the L shaped structuring element. During the dilation, the neighbors of the significant pixels in the set S are scanned and tested for significance.
The final approximation image of the LWT transformed image forms the first S set and also the root of the pyramid. The whole transformed image except the first S set forms the initial I set. Firstly, the S set is tested for their significance in the sorting pass against the threshold n = nmax. The set S is called significant if it contains at least one wavelet coefficient with greater than or equal to 2nmax. If any pixel is found, then the significant list is updated with the position of that coefficient. Immediately, dilation is applied to find other significant pixel using L shaped element which will increase the speed of the process as well as reduce the size of the bit stream by the searching pattern. After the encoding of S set, I set is tested for their significance against the same threshold. The octave band partitioning is applied to the set I, if it is significant. This partition generates three S sets and one reduced I set. The S sets are encoded by the aforesaid procedure and octave band partition is applied again to the reduced I set. This procedure is repeated until the set I is empty and the sorting pass of the particular threshold is over.
The final encoding step of a particular threshold is the refinement pass. In this step, the pixels encoded during the previous sorting pass are refined. This whole process is repeated by decrement the threshold by 1. The algorithm of the proposed LSMC is as follows:
| Algorithm: | |
EXPERIMENTAL RESULTS
The performance of the proposed codec for medical video compression is evaluated by using 3 brain CT and MRI video sequences. At first, all the frames in the video sequence are extracted and the proposed algorithm is applied to each frame separately. To analyze the algorithm effectively, the codec is applied to achieve lossy as well as lossless compression of video sequence. The output of the codec has 0’s and 1’s and stored in an array. The reconstruction is possible by applying the reverse process to the encoded stream. The performance measures used in the proposed LSMC in comparison with SPIHT and SPECK are PSNR at various bitrates and lossless bitrates. The distortion is measured by the Peak Signal to Noise Ratio (PSNR), defined as:
where, MSE is the mean-squared-error between the original and reconstructed frames in the video sequence. Table 1 and 2 shows the PSNR value obtained by the proposed codec in comparison with SPIHT and SPECK at various bit rates for fame size of 256x256 and 512x512 respectively. Also the lossless bit rate obtained by the proposed codec is tabulated. The PSNR values shown in tables are the average PSNR value of all the sequences in the video sequences.
From the tables, it is observed that the proposed codec produces better PSNR and lossless bitrates than other codec’s like SPECK and SPIHT. At lower bitrates the performance of the proposed codec is fairly same as SPIHT and SPECK due to the high energy compaction of LWT. The number of bits available to encode the frame at lower bitrates is very less. Hence most of the bits are used to encode the approximation coefficients in the low frequency sub-bands.
| Table 1: | PSNR values obtained by the proposed LSMC in comparison with SPIHT and SPECK at various bit rates for frame size of 256x256 |
| Table 2: | PSNR values obtained by the proposed LSMC in comparison with SPIHT and SPECK at various bit rates for frame size of 512x512 |
Also the significant coefficients are clustered in the low frequency sub-band for a particular threshold the encoding part of LSMC is same as SPIHT and SPECK, because all the coefficients are significant during dilation.
As the bit-rate increases, the detailed coefficients also consider for the encoding process. In the high frequency sub-bands, most of the significant coefficients are scattered for a particular threshold. The proposed LSMC requires only one pixel to encode the coefficients in the structuring element during dilation if all are insignificant whereas SPECK requires three bits. Hence, the PSNR of the proposed LSMC increases as bitrates increases. For lossless compression, the proposed LSMC gives the best performance, showing the lowest rate on all video sequences. The average bits per pixel required for lossless compression by LSMC is less by 0.13 bpp over SPECK.
CONCLUSION
A novel L shaped morpho codec based on LWT for medical video compression is proposed. In order to utilize the high energy compaction property of LWT, each frame in the video sequence is initially decomposed by LWT at maximum decomposition level. The encoding procedure of LSMC closely follows the methodology in SPECK and SPIHT. The main difference of LSMC with SPECK and SPIHT is in the sorting pass. The proposed LSMC extends the encoding procedure by morphological dilation using L shaped structuring element. The results show better PSNR value over the other existing methods like SPIHT and SPECK at higher bit rates for lossy compression. The lossy compression achieved by LSMC is less by 0.13 bits per pixel over SPECK.