Performance analysis of ROI compression algorithms of medical images.

Jayanthi, V.S. ; Ashwin, S. ; Shanmugam, A. 等

Introduction

Medical imaging is often perceived to designate the set of techniques that produce images of the internal aspect of the body for the diagnosis of diseases and surgical planning, These imaging models include computerized tomography (CT), magnetic resonance imaging (MRI), ultrasonic (US) imaging, X-radiographs, etc. MRI or CT imaging is often used when treating brain tumors, ankle, and foot. From these highresolution images, detailed anatomical information can be derived to examine human brain development and discover abnormalities. These imaging techniques produce large amounts of data. The medical images have large storage requirements when high resolution is demanded. Most of the medical images consist of areas of negligible contribution to the information finally perceived (e.g. background) and the regions, which are of extreme interest (Region of Interest) to the medical expert from the diagnosis point of view. Hence, compression is necessary for storage and efficient transmission for telemedicine applications. Compressing the image as a whole can result a very high compression rate but with considerable loss of overall quality. On the other hand, in medicine, it may be sufficient to maintain high image quality only in the region of interest (ROI), i.e., in diagnostically important regions [3] [4] [7]. Hence an approach that combines high compression rates with good quality in the ROI is needed. Region-of-interest (ROI) image compression allows for important parts of an image to be compressed with better quality than the rest of the image (background).

Image compression algorithms using Vector Quantization (VQ) [1] have been receiving considerable attention. Vector quantization is a lossy compression technique which is a multidimensional extension of scalar quantization. VQ partitions the input image to be encoded into two dimensional vectors, each of which is compared by an encoder with every code vector in a previously defined codebook. The index of the code vector which best matches the input block according to some distortion metric is sent to the decoder, which uses the index to look up reconstruction vector in its copy of the codebook. The reconstruction vectors are tiled to form a lossy compressed version of the input image. Contour lets have emerged as a new mathematical tool for image processing and provide compact and decorrelated image representations. The contour let transform developed by Do and Vetterli[8], is based on an efficient twodimensional (2-D) multiscale and directional filter bank that can deal effectively with images having smooth contours. Contour lets not only possess the main features of wavelets (namely, multiscale and time-frequency localization), but also offer a high degree of directionality and anisotropy. The main difference between contour lets and other multiscale directional systems is that the contour let transform allows for different and flexible number of directions at each scale, while achieving nearly critical sampling. The SPECK image coding introduced by Asad Islam and William A. Pearlman [9] utilizing scalar quantization on hierarchical structures of wavelet transformed images has been a very effective and computationally simple technique. It uses a recursive set-partitioning procedure to sort subsets of wavelet coefficients by maximum magnitude with respect to thresholds that are integer powers of two. It exploits two fundamental characteristics of an image transform, the well defined hierarchical structure, and energy clustering in frequency and in space. The SPECK coding algorithm is a fully embedded block-based coder which employs progressive transmission by coding bit planes in decreasing order. SPECK uses list structures to keep track of blocks to be tested. The use of lists in SPECK requires efficient memory management scheme, since the list nodes are added, removed or moved often. A variant of SPECK image compression called Listless SPECK for wavelet transformed images was reported by R.R.Lakkundi et al. [10]. Listless SPECK (LSK) uses the block splitting rules of SPECK and does an explicit breadth first search, without using lists. State information is kept in a fixed size array that corresponds to the array of coefficient values, with two bits per coefficient to enable fast scanning of the bit planes.

In this paper, our key focus is to compare the performance of the Region-of- Interest (ROI) compression algorithms of medical images. This paper is organized as follows: The next section briefly explains the Vector Quantization. Section 3 gives the brief overview of the contour let transforms. Section 4 outlines the CNLSPECK algorithm. In section 5 the proposed methods for Region-of-Interest (ROI) compression of Medical images are presented. Section 6 reports the experimental results. Finally Section 7 gives the conclusion.

Vector Quantization

Among lossy signal compression approaches VQ has been proved to be a simple image compression approach [2].Vector Quantizer (VQ) [2] [5] [6] Q of dimension k and size S can be defined as a mapping from data vectors in k-dimensional Euclidean space, into a finite subset of C of [R.sup.k]. Thus

Q : [R.sup.k] [right arrow] C (1)

where C = {[C.sub.1], [C.sub.2],...., [C.sub.S]} is the code book of vector quantizer. S is called size of codebook Each Ci is called a code vector. For each Ci, i. I = {1, 2,..., S} is called the index of the code vector and I is the index set. A data vector x [member of] [R.sup.k] is encoded by finding the index j of the code vector [C.sub.j] [member of] C such that [parallel] x - [C.sub.j] [parallel] [less than or equal to] [parallel] x- [C.sub.i] [parallel] [for all] i [not equal to] j and i, j [member of] I. The decoder uses the received index to retrieve the code word from the codebook and generates the reconstruction vector [C.sub.j] corresponding to x. The distortion measure used is mean square error (MSE) given by d(x, [C.sub.j]) = [parallel] x- [C.sub.j] [parallel]. If a VQ minimizes the average distortion, it is called the optimal VQ of size S.A simplified pictorial representation of Vector Quantization is shown in Fig.1.

[FIGURE 1 OMITTED]

A common approach for the generation of the codebook is the use of popular Generalized Lloyd algorithm (GLA) [1] proposed by Linde Buzo and Gray also known as k-means Algorithm. GLA is an iterative gradient descent algorithm that tries to minimize an average squared error distortion measure. It starts with an initial solution, which can be chosen arbitrarily. The existing solution is then improved iteratively using the optimality criteria in turn until a minimum is reached. The algorithm is relatively easy to implement.

The Contourlet transform

Wavelets are well adapted to point singularities (discontinuities), however they have a problem with orientation selectivity, and therefore, they do not represent twodimensional singularities (e.g. smooth curves) effectively. This paper introduces and presents an evaluation of the contourlet transform for image compression. The contourlet transform, as introduced by Minh Do and Martin Vetterli [1] is a new image decomposition scheme, developed to sparsely represent natural images. It provides sparse representation at both spatial and directional resolutions. The contourlet transform consists of two decomposition stages. The Laplacian pyramid is employed in the first stage, while directional filter banks (DFB) are used in the angular decomposition stage. The Laplacian pyramid transforms the image into one coarse version plus a set of LP bandpass images. The second stage applies appropriately 2-D quincunx filtering and critical subsampling to decompose each LP bandpass image into a number of wedge shaped subbands(Fig.2), and thus capturing directional information. Finally, the image is represented as a set of directional subbands at multiple scales.

[FIGURE 2 OMITTED]

The contourlet transform is perfect reconstruction and almost critically sampled with a small redundancy factor of up 4/3 due to the Laplacian pyramid. The contourlet transform is also called as Pyramidal directional filter banks (PDFB). When compared to the discrete wavelet transform, the contourlet transform with its extra feature of directionality yields some improvements and new potentials in image processing applications. Indeed, various experiments clearly show that smooth edges are efficiently represented by few local coefficients in the right directional subbands, leading to better representation of fine contours. [1]. With such a rich set of basis functions, Contourlets can represent a smooth contour with fewer coefficients compared with wavelets, as illustrated in Figure 3.It shows that how wavelets having square supports that can only capture point discontinuities, whereas contourlets having elongated supports that can capture linear segments of contours, and thus can effectively represent a smooth contour with fewer coefficients.

[FIGURE 3 OMITTED]

Fig. 4(a) shows a block diagram of a two-level contourlet decomposition, and Fig. 4(b) shows the subband images of test image pepper. Figure 4(a) Figure 4(b)

[FIGURE 4 OMITTED]

The CNLSPECK algorithm

Consider an image X which has been transformed using the contourlet transformation. The transformed image is said to exhibit a hierarchical pyramidal structure defined by the levels of decomposition, with the topmost level being the root. The finest pixels lie at the bottom level of the pyramid while the coarsest pixels lie at the top level. The image X is represented by an indexed set of transformed coefficients {[C.sub.i,j]} located at pixel position (i, j) in the transformed image.

The CNLSPECK algorithm makes use of rectangular regions of image. These regions or sets, henceforth referred to as sets of type S, can be of varying dimensions. The dimension of a set S depends on the dimension of the original image and the sub band level of the pyramidal structure at which the set lies.

The size of a set is defined to be the cardinality C of the set that is the number of pixels in the set.

size(S) = C(S) = [absolute value of S] 2)

The sets of various sizes will be formed, during the course of the algorithm, depending on the characteristics of pixels in the original set and a set of size 1 consists of just one pixel. The other types of sets used in the CNLSPECK algorithm are referred to as sets of type I. These sets are obtained by chopping off a small square region from the top left portion of a larger square region. A typical set I is illustrated in Fig. 5.

[FIGURE 5 OMITTED]

In CNLSPECK, the State information is kept in a fixed size array that corresponds to the array of coefficient values, with two bits per coefficient to enable fast scanning of the bit planes. CNLSPECK uses special markers which are updated, when block splitting forms new significant blocks. With these sparse marking schemes, large sections of the image are skipped at once, as breadth first scan moves through the blocks in lower level.In CNLSPECK, efficient skipping of blocks of insignificant coefficients is accomplished using a recursive zigzag image indexing scheme.

Linear Indexing

The proposed algorithm adopts the linear indexing to represent the index of a coefficient, which uses a single number instead of two.. Let R=C=[2.sup.N] be the number of rows and columns of the square image, and let r and c be zero-based row and column indices. Represent the row index in binary as, r = [[r.sub.Lr-1]...[r.sub.1],[r.sub.0]], where each of the [r.sub.n] is a bit, and for the column index as c=[[C.sub.Lr-1]...[c.sub.1],[c.sub.0]]. For an index (r,c), the linear index is defined by i = [[r.sub.Lr-1],[C.sub.Lr-1], ..., [r.sub.1],[c.sub.1], [r.sub.0],[c.sub.0]]. The bits of r and c are simply interleaved. The linear index I ranges from 0 to I-1, where I=RC. The bits of r and c are simply interleaved. The linear index I ranges from 0 to I-1, where I=RC. Fig. 6 shows an example of this indexing method. Every pre-final block of size 2 x 2 used in linear indexing for CNLSPECK, has four consecutive indices, before a pixel level is reached. Another important property of the linear indexing is that it efficiently supports the operations on coefficient positions, needed for block-based algorithms with one operation instead of two. Also, the linear index naturally facilitates a breadth first search

[FIGURE 6 OMITTED]

State Table Markers

CNLSPECK uses same block partitioning rules, as used by SPECK. Markers are placed at all initial pixels for all the sub-bands and the minimum number of bits to indicate the insignificant sub-band blocks in the initial passes in the proposed algorithm. The following markers are placed in the 2 bit per coefficient state table mark, to keep track of the set partitions. Each element of mark, if signifying a block, indicates something about the corresponding element in the val image array. Each marker and its meaning are listed below.

MIP: The pixel is significant or untested for this bit-plane.

MNP: The pixel is newly significant, so it will not be refined for this bit-plane.

MSP: The pixel is significant and will be refined in this bit plane.

MS2: The block of size 2 x 2, i.e., 4 elements to be skipped.

MS2 markers are used successively to skip 4 x 4 block, 8 x 8 block ... and so on. The amount of computational time required to calculate the number of MS2 markers in this algorithm is negligible. This can also be avoided by using additional pointers, such as MS4, MS8 ... etc.

A set T of pixels is said to be significant with respect to n if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

Otherwise it is insignificant.

The significance of a set T can be written as a function of n and the set T,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

Main Algorithm

The Pseudo code for the main encoder algorithm shown in Fig.7 is performed for each bit-plane, b, starting with B and decremented to 0, or until a bit budget is met. The significance level for each bit-plane is [s=2.sup.b]. Significance checks are always done with bitwise AND operation. The decoder follows the same overall procedure as the encoder with some low-level changes.

Initialization

Apply the contourlet transform to the given image.

Map the whole two-dimensional transform matrix into one-dimensional array (linear indexing) using mapping (n) and initialize the markers.

For the transformed linear indexed image S, find the maximum number of bits to be used (n) as,

n = [log.sub.2](max {|S(i)|}) [for all] i.

Figure 7 : The Pseudo code for CNLSPECK algorithm

Sorting Pass

For all pixels S(i)
Process S(i)

Refinement Pass

For each pixel, except those included in the last sorting
  pass, output the nth MSB of
   |[S.sub.(i)]|

Quantization Step

decrement n by 1, and go to step 2

Process S(i)
If the marker value is zero
{
if S(i) is a significant pixel, output 2 bits
First bit = '1' and
Second bit ='0' if it is positive.
Second bit ='1' else.
if S(i) is a insignificant pixel, output ='0'
}
else
Performance Analysis of ROI compression algorithms 81
{
check for block significant;
if significant
output='1' and
apply partition(i);
else
output = '0', skip the block and move to next block
}
partition(i)
{
divide the significant block into 4blocks
move to the inner block in the morton's scanning order.
}
mapping(n )
{
elements are arranged in the Morton Scan order matrix from 1 to n.
}

Proposed Region-of-Interest (ROI) compression algorithms of Medical images

Medical images are used to analyze different parts of human body. Generally, different regions of a medical image may have very different diagnostic importance, since eventual pathologies may happen only on several regions of the image corresponding to well defined organs or parts of organ. For example, on an MRI and CT scan image the expert is mainly interested in the states of the tissues. These tissues occupy finally a very restricted part of the image, therefore the rest; a large image zone may be compressed with a low bit rate since a poorer reconstruction quality is tolerable.

Region of Interest Vector Quantization (ROIVQ) image compression

The first method adopts a hybrid model of near lossless compression in the region of interest, with lossy compression in other regions. This method deeply exploits the advantages of Vector Quantization (VQ).Hence, this approach is known as Region of Interest Vector Quantization (ROIVQ) image compression.By changing the code vector dimension and increasing the codebook size, better performance of the Vector Quantization [2] [5] [6] can be obtained than using any other block coding technique. In the proposed ROI VQ approach, a separate generic codebook is designed for every region. The codebook size and the code vector (code word) dimension are chosen based on the medical importance of the given region. For diagnostically important region, a large codebook containing small code words is generated and for less important regions (background), codebook consisting of less code vectors of large dimension is designed. ROI-VQ coding and decoding in the proposed method is illustrated in Fig.8. Further, Huffman coding of indices generated by the encoder is used to achieve better compression ratio.

[FIGURE 8 OMITTED]

Region of Interest Compression using CNLSPECK (ROI-CNLSPECK)

The second proposed method is an image compression algorithm using an embedded, block-based, Contour let Transformed Image coding using No List SPECK (CNLSPECK) of low complexity. The information in all the bit planes will be encoded for diagnostically important regions and the information in LSB planes are excluded from encoding for less important regions.

Region of Interest Compression using hybrid CNLSPECK and VQ (ROI-CNLSPECKVQ)

The third proposed method is a novel hybrid image compression algorithm using an embedded, block-based, Contour let Transformed Image coding using No List SPECK (CNLSPECK) for diagnostically important regions and VQ with code book containing less code vectors(256 code vectors of dimension 64 (8x8)) for less important regions

Experimental Results

The proposed algorithms have been implemented in Matlab 7.0 and run on Pentium IV computer. The Generalized Lloyd Algorithm (GLA) has been used to design codebooks of every region, i.e., region of interest and region of less importance for VQ. GLA needs a training set of images (a set of images that are the representatives of the images to be compressed) for designing the generic codebook. In the proposed approach (ROIVQ), four images are used for designing codebooks of region of interest and region of less importance. The generic codebook can be used to encode any image (i.e., images other than those used to construct the code book). ROIVQ uses a code book consisting of 256 code vectors of dimension 64 (8x8) for region of less importance and a code book containing 256 code vectors of dimension 4 (2x2) for Region Of Interest. To achieve more compression lossless Huffman encoding is applied to the indices generated by the encoder. Codeword assignment for the indices is based on frequency distribution of code vectors in the encoded training image.

To show the efficiency of the proposed algorithms, the objective quality of encoded images are measured using PSNR (Peak value Signal-to-Noise Ratio), which is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

Where, [x.sub.ij] is the value of [ij.sup.th] pixel in the input image and [x.sub.ij]'is the value of [ij.sup.th] pixel in the reconstructed image.

Our proposed algorithms are tested on three test images The performance comparison of the algorithms in terms of PSNR and Compression rate on test images is given in Table I and Table II respectively.

The effectiveness of the proposed algorithms in preserving quality in the diagnostically important region i.e. ROI in reconstructed images have been demonstrated visually in Figs 9-11.

[FIGURE 9 OMITTED]

[FIGURE 10 OMITTED]

[FIGURE 11 OMITTED]

The original image in Fig 9(a) shows the image of brain showing an extensive Intracranial hemorrhage involving Left side of cerebrum (frontal lobe). There is an intense oedema surrounding the Lesion The original image in Fig. 10(a) shows a post contrast MR scan through the cerebellopontine angle demonstrates a tumor with intense enhancement that extends into the widened internal Auditory canal displacing the pons probably vestibular shcwannoma

Conclusion

Three Region of Interest compression algorithms of medical images have been presented. Based on prior knowledge and applying the ROI aspect, our approaches compress diagnostically important regions with a very good reconstruction quality. Moreover, a rather high overall compression rate is obtained due to the strong compression in less important regions.

The use of generic codebook in ROIVQ not only enables us to construct the codebook only once, but the knowledge of distribution of indices for the training images can also be exploited as a priory knowledge of distribution of training images. This is used for devising entropy coding (Huffman coding) scheme for index values. Since separate VQ codebooks are designed to compress different regions, every codebook is well adapted to the given region.

Simulation results provided by compressing various MRI and CT images of the brain validated the interests of the proposed approach. Results showed that the quality of reconstructed images in the region of interest is improved i.e., PSNR is increased up to 10dB using ROIVQ and PSNR is improved by 19 dB using ROI-CNLSPECK and ROI-CNLSPECKVQ approaches and also overall better compression is achieved. Even though higher compression ratios are obtained by using these techniques, the results are satisfactory from the diagnosis point of view.Among the proposed ROI compression algorithms, ROIVQ provides the higher compression rates, but PSNR of reconstructed images is comparatively very low. On the other hand, ROI-CNLSPECK produces better quality of the reconstructed images in the ROI region with overall lower compression rate. ROI-CNLSPECKVQ paves the middle path by achieving good reconstruction quality in ROI at good compression rate.

References

[1] Y. Linde, A. Buzo and R.M. Gray. "An Algorithm for Vector Quantizer Design" IEEE Trans.Commun., COM-28:84-95 Jan.1980

[2] N.M. Nasrabadi and R.A. King, "Image coding using vector quantization: a review", IEEE Trans. Com., Vol. 36, pp.957-971, Aug. 1988.

[3] L. Shen and R.M. Rangayyan, "A segmentation based lossless image coding method for high resolution medical image compression," IEEE Trans. Med. Imaging, vol. 16, pp. 301-307, Feb. 1997.

[4] S. Biswas, "Segmentation based compression for gray level images," Pattern Recognit., vol. 36, pp. 1501-1517, 2003.

[5] K. Sayood, Introduction to Data Compression, 2nd ed. San Mateo, CA: Morgan-Kaufmann, 2000.

[6] David Solomon, Data Compression, second edition Springer -Verlag, Newyork, 2001

[7] A.Cuhadar and S. Tasdoken, Multiple, Arbitrary shape ROI Coding with Zerotree Based Wavelet Coders, IEEE ICASSP, III: 257-260, 6-10 April 2003

[8] M. Do and M. Vetterli "The Contourlet transform: an efficient directional multiresolution image representation," IEEE Transactions on Image Processing, Vol. 14, Issue: 12 pp. 2091- 2106 Dec. 2005.

[9] A.Islam and W.A. Pearlman, "An embedded and efficient low-complexity hierarchical image coder," Visual Communications and Image Processing '99, Proceedings of SPIE, Jan. 1999. vol. 3653, pp. 294-305

[10] R.R. Lakkundi, M.V. Latte, D.K. Deshpande, "Reduced Memory Listless SPECK Image Compression" Proceedings of "International Conference on Intelligent Signal Processing and Robotics", Feb.2004

V.S. Jayanthi (1), S. Ashwin (1) and A. Shanmugam (2)

(1) Dept. of ECE, Sri Ramakrishna Engineering College, Coimbatore-641022

(2) The Principal, Bannari Amman Institute of Technology, Sathyamanagalam-638401

Table 1 : Performance Comparison in Terms of PSNR in dBs

Image    ROIVQ                       ROI-CNLSPECK
         PSNR(ROI)   PSNR(Overall)   PSNR(ROI)   PSNR(Overall)
Test
         30.143      20.557          31.438      22.077
Image1
Test
         30.479      20.694          30.752      21.133
Image2
Test
         29.149      26.347          46.739      27.771

Image    ROI-CNLSPECK-VQ
         PSNR(ROI)   PSNR(Overall)
Test
         31.438      20.565
Image1
Test
         30.752      20.696
Image2
Test
         46.739      26.489
Image3

Table 2 : Performance Comparison in terms of Compression rate (bpp)

Image          ROIVQ   ROI-CNLSPECK   ROI-CNLSPECK-VQ

Test Images1   0.308     3.875            0.921
Test Images2   0.336     3.776            0.885
Test Images3   0.319     3.487            0.848

Figure 6 : Linear Indexing with R=C=8 and two sub band levels
with bands delimited with thick lines

1    2    5    6    17   18   21   22
3    4    7    8    19   20   23   24
9    10   13   14   25   26   29   30
11   12   15   16   27   28   31   32
33   34   37   38   49   50   53   54
35   36   39   40   51   52   55   56
41   42   45   46   57   58   61   62
43   44   47   48   59   60   63   64