Performance Analysis of Advanced Transforms in 2-D Signals

Performance Analysis of Advanced Transforms in 2-D Signals

Ms. K. Prasuna Asst. Prof, Department of ECE,

Vijaya Institue of Technology for Women, Vijayawada, AP

Abstract:-Data compression is an important tool in digital image processing to reduce the burden on the storage and transmission systems. Fast 1D-2D Framlet Transform algorithm for computing advance transforms are proposed. For a 2D framelet transformation, the algorithm is applied in x-direction first and then in y-direction. The propose method reduces heavily processing time for decomposition of video sequences keeping or overcoming the quality of reconstructed sequences In addition, it cuts heavily the memory demands.

In this paper, Discrete Hartley type transform (CCT) and Fast Fourier transforms (FFT) methods are used for both data compression and decompression process. Algorithms are developed and tested using the two methods on different images. A comparison with respect to mean square error with the original image is also presented. The main advantage of discrete Hartley type transform is, it is a real transform. Discrete cosine transform also has similar performance as that of discrete Hartley type transform. An algorithm for compression using FFT method and Framelet is also presented.

Keywords-Wavelet transform, Framelet, FFT,DCT

1. INTRODUCTION

   Though standard DWT is a powerful tool for analysis and processing of many real-world signals and images, it suffers from three major disadvantages, Shift- sensitivity, Poor directionality and Lack of phase information. Thesedisadvantages severely restrict its scope for certain signal

   Transform, and Sampling and Interpolation process using Fast Fourier Transform.

   In this paper Discrete Hartley type transform is used for data compression in two dimensions, which is directly applicable to digital image processing of RPV photographed images. The performance is compared with the existing Fast Fourier Transform. The Hartley transform (HT) was developed as a substitute to Fourier transform (FT) in applications where the data is in real domain. [6], [7]. The HT was also defined in two dimensions in which kernel is not separable . Another modified separable Hartley type transform, named the CAS-CAS transform (CCT) was also defined. CAS stands for Cosine plus Sine. CCT for two dimensional cosine plus sine transform. Algorithms are developed for data compression and decompression using the two transforms namely CCT and FFT in two dimensions. Comparison of compressed and decompressed image with the original image with respect to mean square error is carried out.

2. CCT METHOD

   Discrete Hartley type transform in two dimensions as separable transform is the CAS-CAS transform and is called as CCT. Hartley transform relations in 2-D in which the kernel is not separable are

   Hu,v x m, ncas mu nv

   Hu,v x m, ncas mu nv

   M 1 N 1

   M N

   and image processing applications [1].

   Other extensions of standard DWT such as Wavelet Packet Transform (WP) and Stationary Wavelet Transform (SWT) reduce only the first disadvantage of shift-

   m0 n0

   and reverse transform is

   (1)

   sensitivity but with the cost of very high redundancy and

   1 M 1 N 1

   mu nv

   involved computation. Recent research suggests the

   Xm,n H u, vcas2

   M x N M N

   (2)

   possibility of reducing two or more above-mentioned disadvantages using different forms of Wavelet Transforms [2-4] with only limited (and controllable) redundancy and moderate computational complexity. Data compression before transmission reduces the channel bandwidth requirement and memory space [1] to [7]. There are different transforms available for data compression. These are Karhumen Loeve Transform, Discrete Cosine

   u 0 v0

   M N

   M N

   cas2 mu nv is not a separable kernel. But for 2-

   D DFT the kernel is separable. Hence the row column decomposition method [14] of computing 2-D transform from 1-D fast Fourier transform algorithm can be used. In

   case of 2-D Hartley transform row column can not be applied directly. To take advantage of the fast 1-D HT algorithms, a separable Hartley like transform namely CAS-CAS transform that is CCT is shown.

   C (u, v)

   B(u, v)

   B(u, v N )

   2

   B(u M , v)

   2

   for u 0,1,……., M 1

   4

   4

   4

   for v 0,1,………, N 1

   for u 0,1,…….., M 1

   4

   for v N , …., N 1

   4 2

   for u M , .., M 1

   M 1 N 1 2 mu

   2 nv

   4 2

   T u,v

   m0 n0

   x m, ncas cas

   M N

   (3)

   B(u M , v N )

   2 2

   for v 0,1,………….., N

   4

   for u M , .., M 1

   4 2

   for v N , ……, N 1

   4 2

   1 M -1 N -1

   2 mu

   2 nv

   X m, n T u, vcas cas

   (u, v) is matrix of size (M/2, N/2), a compression ratio of 4

   M x N u0 v0

   M N

   (4)

   with respect to original size of the image matrix A of size (M, N) is achieved.

   Where

   cas =cos +sin and

   1

   D(u, v) C(u, v)

   0

   for u 0,1, …….., M 1

   4

   for v 0,1, …….., N 1

   4

   for u 0,1, …….., M 1

   2

   2

   H u, v T u, v T -u, v T u, -v- T -u, -v

   (5)

   C (u, v N )

   2

   4

   for v N , …., 3N 1

   4 4

   for u 0,1, ……., M 1

   4

   In this way 2-D Discrete Hartley transform can be computed. For the compression and decompression process only CCT is used instead of Hartley transform.

   for v 3N , ……, ( N 1)

   4

   0 for u M , …., 3M 1

   4 4

   A. Algorithm for Compression and De-Compression Using CCT

   1. The analog Image is scanned to get digital image with a size of pixels (256 x 256) as reference data matrix A. Instead of particular size of the digital image data, general size of the original image matrix A is considered as (M, N).

   2. CCT of this matrix A is Computed using equation (3) as Matrix B which is of same size as A. Important observation is that the CCT coefficient matrix is having larger amplitudes at the four corners and the value diminishes, negligibly small towards central region.

   3. Based on the above principle, the CCT coefficients matrix B is modified to reduce its size to (M/2, N/2), to achieve a compression factor of 4 by neglecting small amplitude coefficients. Construct a new matrix C (u, v) from B (u, v) which is reduced in size as follows

      for v 0,1, …………., ( N 1)

      C (u M , v) for u 3M , …., (M 1)

      2 4

      for v 0,1, …….., N 1

      4

      0 for u 3M , …, (M 1)

      4

      for v N , .., 3N 1

      4 4

      2

      2

      C (u M , v N ) for u 3M , …, (M 1)

      2 4

      for v 3N , …, ( N 1)

      4

   4. This reduced CCT coefficient matrix is to be transmitted instead of the original matrix, so that memory space is saved for storage and burden on the transmission channel is reduced by a factor of 4.

   5. At the receiver, after receiving the modified CCT matrix C (u, v), is appended with zeros at respective regions, to make it to reference image size as follows

   6. Each D (u, v) is multiplied by the square of the compression factor.

   7. Inverse CCT is Performed using equation (4) on the sequence D (u, v) of size (M, N) to obtain the replica of Perform the original image A.

3. FAST FOURIER TRANSFORM METHOD

   The Fourier transform relations in 2-D

   • j2 mu nv

     1. FRAMELETS

        Framelet are very similar to wavelets but have some important differences. In particular, whereas wavelets have

        M N

        M N

        are X (u, v) M 1 N 1

        m 0 n 0

        x(m, n) e

        (6)

        an associated scaling function F(t) and wavelet function y(t), framelets have one scaling function F(t) and two wavelet functions y1(t) and y2(t) .

        The scaling function F(t) and the wavelets y1(t)and y2(t)

        where m 0,1,…M 1,

        M 1 N 1

        n 0,1,…N 1

        • j2 mu nv

        M N

        are defined through these equations by the low-pass (scaling) filter h0(n) and the two high-pass(wavelet) filters p(n) and p(n).

        To compute a single level for 1-D signal the next steps

        x(m, n)

        u 0 v 0

        X (u, v)e

        (7)

        should be followed:

        1. Checking input dimensions: Input vector should be of length N, where N must be even and N> = length of

           where u 0,1,…M 1, v 0,1,…N 1

           A. Algorithm for Compression and Decompression Using FFT

           The procedure is similar to that of Hartley type transform for data compression and decompression using Fast Fourier

           transform. The algorithmic steps given above for Hartley

           analysis filters

        2. Construct a transformation matrix: using transformation matrices given in (10) and (11)

        3. Transformation of input vector, which can be done by apply matrix multiplication to the 3N/2xN constructed

        transformation matrix by the Nx1 input vector

        transform, are to be used for this also by replacing CCT with FFT. FFT magnitude coefficients are also concentrated at the corners as that of CCT.

        Y

        Where

        W 3N N .X N1

        2

4. ALGORITHM FOR COMPRESSION AND DECOMPRESSION USING DCT

The Discrete Cosine Transform relations in 2-D are

X Y 0 : N 1

L 2

X Y N : N 1

M 1 N 1

(2m 1)u (2n 1)v

H 1 2

X (u, v) uv

x(m, n) cos 2M cos 2N

m 0 n 0

X Y N : 3N 1

H 2

(8)

2

Where m = 0, 1. M-1; and n = 0, 1 N-1

2-D Framelet transform: The choice of the transform to be used depends on a number of factors, in particular,

u

u

v

v

1 Foru 0

M

2 Foru 1……M 1

M

1 Forv 0

M

2 Forv 1….N 1

M

computational complexity and coding gain.

1. Checking input dimensions: Input matrix should be of length NxN, where N must be even and N> = length of analysis filters

2. For an NxN matrix input 2-D signal, X, construct a 3N/2xN transformation matrix, W, using transformation matrices given in (10) and (11)

3. Apply Transformation by multiplying the transformation matrix by the input matrix by the transpose of the transformation matrix.

This multiplication of the three matrices result in the final

And 2-D inverse discrete cosine Transform is

discrete framelet transformed matrix.

M 1 N 1

x m, n uv X (u, v) cos

m0 n0

(2m 1)u

2M

cos

(2n 1)v

2N

(9)

Y W.X .W T

1. RESULTS AND CONCLUSIONS

Where u= 0, 1 M-1, and v= 0,… N-1

Equation (8) is forward transform and equation (9) is reverse transform.

Two methods are tried for different compression factors. The mean square error estimation of resultant images with respect to the original image data (figure 1) are presented in table 1.

TABLE. 1.

The framelet transform is extended to 2D by iterating the 1D over sampled filter bank on the rows and then on the columns of an image, as is usually done for separable 2D- framelet transform.At a given level in the iterated filter bank, this separable extension produces nine 2D subbands. These subbands are showed in Fig. 2. Since L is a lowpass filter (h0(n)) while both H1 and H2 are highpass filters (p(n) and p(n)), the H2H2, H2H1, H1H2, H1H1 subbands each have a frequency-domain support comparable to that of the HH subband in a DWT. A similar scheme creates the H1L, H2L (LH1, LH2) subband with the same frequency- domain support as the corresponding HL (LH) subband of the DWT, but with twice as many coefficients. Finally, note that there is only one subband LL with the same frequency- domain support as the LL subband in a DWT(Fig.3&4).

REFERENCES

1. W. H. Chen, C. H. Smith, and S. Fralick, A fast computational algorithm for the discrete cosine transform,IEEE Trans. Commun.

   Vol. com- 25, pp. 1004-1009,Sep. 1977

2. P.Yip and K. R. Rao. A fast computational algorithm for the discrete cosine transform, IEEE Trans. Commun., vol. com- 38, pp. 304-307, Feb.1980

3. K.R. Rao and R. Yip, Discrete cosine transform algorithm,

   Advantages and applications, Newyork, academic 1990

4. K. Rose, A. Heiman and I. Dintein, DCT/DST Alternate transform image coding, IEEE Trans. Com. Vol. com-38, pp. 94-101, Jan. 1990

5. T.P. ORourkr and R.L. Stevenson, Improved image decompression for reduced transform coding artifacts, IEEE

Fig.1 Image Subbands after a single-level decomposition, for (a): Scalar Wavelets and (b): Framelets

Fig2. .After Input column transform

Fig.3.Upper leftmost transform, LL subband

Reconstructed Image

50

50

100

150

200

250

300

350

400

450

Original Image

100 200 300 400 500

100

150

200

250

300

350

400

450

100 200 300 400 500

Fig 4. Original and reconstructed images MSE=65.025