Hybrid compression scheme using precoding block and fast stationary wavelet transformation

Abstract

In this paper a hybrid compression using precoding block and Fast Stationary Wavelet Transformation have been proposed for standard and compound images. The proposed method is the extension of transformation based compression process. It has two operations 1. precoding, 2. transformation. The first process is precoding in which the original image is divided into (n×n) non overlapping blocks then each block is combined with the precoding block, which have different level of gray values. When the original pixel value is nearer to the precoding block element, then the original pixel value is rounded near the precoding element data. Secondly the precoded image data has been transformed by FSWT (Fast Stationary Wavelet Transformation) and got the energy compaction.The proposed technique is dually reduce the size of the information by precoding block and transformation. So it is very much suitable for compressing all types of images.

1 Previous arts

A lot of previous methods have been implemented for image compression; a discrete cosine transform [11] express a sequence of data points in terms of a sum of cosine functions oscillating at different frequencies. But it can be done by using real numbers only.

Marpe et al. [3] propose wavelet based compression algorithm. In each iteration DWT decomposes its input into four spatial frequency sub bands. However, this method contains smaller code-block dimensions which gives reduced compression performance. It results in increased packet signaling overhead and increased disk thrashing.

Then the Vector quantization (VQ) works by Dividing a large set of points (vectors) into groups having same number of points closesr to them. The density matching property of vector quantization is powerful, especially for identifying the density of large and high-dimensioned data. Since data points are represented by the index of their closest centroid, then the Predictive coding estimates a pixel color value based on the pixel color values of its neighboring pixels. To enhance the accuracy of the estimation, the prediction scheme can help to minimize the upper bound of the residual errors from the prediction.

Shan Gai et al. [20] proposed Multiscale texture classification using reduced quaternion wavelet transform in which the texture classification will be performed using reduced quaterion. Shan Gai [19] proposed Image denoising using normal inverse Gaussian model in quaternion wavelet domain.

Shan Gai et al. [20] also proposed an Denoising Color Images by Reduced Quaternion Matrix Singular Value Decomposition, in which singular decomposition was performed because it will perfom matrix computations very well.

Guerrero et al. [21] proposed Support vector machines for crop/weeds identification in maize fields. Montalvo et al. [22] proposed an Automatic expert system for weeds/crops identification in images from maize fields. All these methods has its own merits and demerits.

Talukder & Harada (2007) have proposed a Discrete Wavelet Transform for Image Compression and A Model of Parallel Image Compression Scheme for Formal Verification. Averbuch et al. (1996) Proposed a compression scheme using wavelet and the decomposition has been done using pyramidal multiresolution scheme.

Daechul park Moon Ho Lee (1994) proposed a compression using a best wavelet packet bases exhibit a SFFT (short-time fast Fourier transform) subband decomposition at one source, a wavelet decomposition at another source, or any intermediate wavelet packet decomposition. Based on wavelet analysis adaptive method has been proposed by Hao (2001).

Antonini et al. (1992) proposed a method based on two steps. At first the original image was decomposed by the wavelet transform and then according to the Shannon’s rate distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. Jong-Han et al. (1998) proposed a region based wavelet transform to overcome a problem that wavelet transform is not applicable to the arbitrarily shaped in images. Donoho et al. (1998) review recent interactions between harmonic analysis and data compression. Jiaxian et al. (2007) proposed a data analysis algorithm which analysis the observed data. A 2-dimension data decomposition framework and makes modifications of contexts used by Embedded Block Coding with Optimized Truncation.

Huang et al. (1992) proposed a compression technique in which three fast search routines are used in encoding phase of vector Quantization. Shen En Qian (2004) proposed A fast vector quantization algorithm for data compression of hyperspectral imagery. Hao Xu et al. (2007) Proposed a new directional DCT-like transform, whose transform matrix is dependent on directional angle and interpolation used there.

Bo Li et al. (2011) proposed a 2-D Oriented Wavelet Transform which can perform integrative oriented transform in arbitrary direction and achieve a significant transform coding gain. Azam Karami et al. (2012) Proposed a algorithm based on Discrete Wavelet Transform and Tucker Decomposition (DWT-TD), exploits both the spectral and the spatial information in the images. The core idea behind this technique is to apply TD on the DWT coefficients of spectral bands of HSIs. The hybrid method used for optimize spatial prediction and the choice of subsequent transform in image compression. Image compression scheme with pruning proposal based on Discrete Wavelet transformation has been proposed by Mozammel & Amina (2012).

The two dimensional discrete wavelet transform has been applied by Kamrul & Koichi (2007) and the detail matrix from the information matrices have been estimated. The reconstructed image is synthesized using estimated detail matrices and information matrix provided by the wavelet transform Alarcon et al. (2013) proposed a compression method using DWT and thresholding.

The hybrid compression using precoding and FSWT (Fast Stationary Wavelet Transform) has been proposed. Here the initial compression has been done by precoding matrix then the precoded data has been compressed using FSWT (Fast Stationary Wavelet Transform). The compression ratio can be achieved depend upon the precoding matrix elements. So it is very much suitable to get good compressed data by adjusting the precoding matrix elements.

2 Proposed hybrid system

The proposed method is the extension of transformation based compression process. It has two operations 1. precoding, 2. transformation. In precoding the original image is divided into (n×n) non overlapping blocks then each block is combined with the precoding block, which have different level of gray values.The proposed algorithm has been illustrated in block diagram as shown in Fig. 1.

When the original pixel value is nearer to the precoding block element, the original pixel value is rounded near the precoding element data. Then the precoded image data has been transformed by FSWT (Fast Stationary Wavelet Transform), then the soft Thresholding will be parallel operated on the transformed coefficients and got the energycompaction.

In the decoding section the compressed data is regenerated using Inverse FSWT and get the original image. This proposed technique will dually reduce the size of the information by precoding block and transformation. So it is very much suitable for compressing all types of still images and achieve high PSNR value. The main compression had been done on the precoding process design.

Algorithm 1- for precoding

Step 1: Read the input image I(x,y)I And divide it in to NXN matrix

Step 2: construct the MXM precoding block mask which is equal to dividend input image

Step 3: initialize the precoding matrix element by zero

Step 4: update the left diagonal element of the precoding matrix based upon the weight vector value

Step 5: weight value of the precoding matrix element can be calculated by NXN of the original dividend matrix by the formulae

Step 6: update only the diagonal element of the matrix of the precoding block rest of the elements will be added with the original image matrix

Step 7: slide the window for whole image and get the compressed Image.

Algorithm 2- for transformation

Step 1: Get the precoded image P(x,y)

Step 2: Perform a single-level Fast StationaryWavelet Decomposition.

Step 3: Construct the level 1 approximation and details (A1, H1,V1 and D1) from the coefficients

Step 4: perform a decomposition at level 3 of the image (again using the haar wavelet),

Step 5: Reconstruct approximation at Level 3 and details from coefficients.

Step 6: Do the soft Thresholding for the coefficients.

Step 7: Regenerate the image by taking Inverse Stationary Wavelet Transform.

2.1 Precoding design

The precoding is nothing but a predefined block holding the different gray level values based upon the weight parameter and the precoding block gray values varies from 2 to 256.

Construction of precoding block: The precoding block is constructed based upon the weight parameter and if the weight parameter value is high means, the precoding block element value will be high and the precoding block element value will be changing based on the weight value for each pixel in the original image non overlapping block. The precoding block is defined in matrix form (2.1). $P = [\begin{matrix} P_{1, 1} & P_{1, 2} & \dots & P_{1, r} \\ P_{2, 1} & P_{2, 2} & \dots & P_{2, r} \\ P_{S, 1} & P_{S, 2} & \dots & P_{S, r} \end{matrix}]$ (2.1)

Weight parameter: The weight parameter value will be determined based upon the neighborhood pixel values of the original image. The non overlapping blocks weight value will be computed based upon the average value of upper diagonal and lower diagonal pixel value of the original block. The weight parameter for precoding block element is given by W_n = Average of Upper diagonal and lower diagonal value of the original image.

2.2 Transformation

To encode a 2Jx2J image, an analyzing wavelet ψ and a minimum decomposition level J-P are selected and used to compute DWT of the image. If the wavelet has the complementary scaling function φ, then fast wavelet transform can be used. The transform converts a large portion of the original image to horizontal, vertical, and diagonal coefficients with zero mean and Laplacian- like distribution. Many of these coefficients carries little visual information. It can be quantized and coded to reduce inter-coefficient and coding redundancy. Since the wavelet transform is both computationally efficient and inherently local (since basis functions have a limited duration). So, image subdivision into block is not needed, which eliminate the blocking artifact and it is the major difference compared to the transform coding.

We use a class of orthogonal wavelet bases generalizing the Daubechies functions this is well adapted to numerical calculations. In these bases (for a given accuracy) integral operators satisfying certain analytical estimates have a band-diagonal form, and can be applied to arbitrary functions in a fast manner. In particular, Dirichlet and Neumann boundary value problems for certain elliptic partial differential equations can be solved in N order calculations, where N is the number of nodes in the discretization of the boundary region.

Effectively, this paper provides two schemes for the numerical evaluation of integral operators. The first is a straight forward realization (standard form) of the matrix in the wavelet basis. This scheme is an order N log (N) procedure (even for such simple operators as multiplication by a function). Haar Wavelet:The haar function h_j,k with integer indices j and k are defined by $H_{j,} k (x) = {\begin{matrix} 2^{j / 2} & for 2^{j} (k - 1) < x < 2^{j} (k - 1 / 2) \\ - 2^{j / 2} & for 2^{j} (k - 1 / 2) < x < 2^{j} (k) \\ 0 & otherwise \end{matrix}$ (2.2)

Clearly the Haar function h_j,k (x) is supported in the dyadic interval J $h_{j, k} = [2^{j} (k - 1), 2^{j} k]$ (2.3)

To obtain a numerical method for calculating the haar coefficients,given N = 2ⁿ samples of a function for simplicity it is represented in scaled values as in Equation 2.4. $S_{k}^{0} = 2^{n / 2} \int_{2 k - 1}^{2} f (z) dz$ (2.4)

Off an intervel of length 2^k the haar coefficients interval length is obtained. Then the coefficients can be written as $d_{k}^{1} = \frac{1}{\sqrt{2}} (s_{2 k - 1}^{0} - s_{2 k}^{0})$ (2.5)

We also compute the average $S_{k}^{1} = \frac{1}{\sqrt{2}} (s_{2 k - 1}^{0} - s_{2 k}^{0})$ (2.6)

On the interval of length 2^-n+1 repeating this we get the haar coefficients $d_{k}^{j + 1} = \frac{1}{\sqrt{2}} (s_{2 k - 1}^{j} - s_{2 k}^{j})$ (2.7)

And the averages are, $S_{k}^{j + 1} = \frac{1}{\sqrt{2}} (s_{2 k - 1}^{j} - s_{2 k}^{j})$ (2.8)

2.3 FSWT

Replacing the haar basis S with vanishing moment S and assuming the coefficient $S_{k}^{o}, k = 1, \dots \dots \dots, N$ are given, then we can replace the expression with the formulae as in 2.9 and 2.10. $S_{k}^{j} = \sum_{n = 1}^{n = 2 M} h_{n} S_{n + 2 k - 2}^{j - 1}$ (2.9) $d_{k}^{j} = \frac{1}{\sqrt{2}} (d_{2 k - 1}^{0} - d_{2 k}^{0})$ (2.10)

Where $S_{k}^{j}$ and $d_{k}^{j}$ are periodic sequences with the period $2_{1}^{n - j}$ .

After the first, second or third level decomposition has been done, soft thresholding will be parallel operated on the transformed coefficients. Soft thresholding is a wavelet shrinkage in which the values are reduced.

3 Result and analysis

In this section we have almost verified 15 data sets with our proposed methods from that we could find out the MSE, and PSNR. Here two of the error metrics are used to compare the various image compression techniques are Mean Square Error (MSE) and the Peak Signal to Noise Ratio (PSNR). The MSE is the cumulative squared error between the compressed and the original image, whereas PSNR is a measure of the peak error. The mathematical formulae for the MSE and PSNR are given in Equations (2.11) and (2.12) respectively. $MSE = \frac{1}{MN} \sum_{y = 1}^{N} \sum_{x = 1}^{M} [I (x) - I (y)]^{2}$ (2.11) $PSNR = 20 * {log}_{10} \frac{255}{\sqrt{MSE}}$ (2.12) where I(x) is the original image, I(y) is the approximated version (which is actually the decompressed image) and M, N are the dimensions of the images. A lower value for MSE means lesser error, and as seen from the inverse relation between the MSE and PSNR, this translates to a high value of PSNR. Logically, a higher value of PSNR is good because it means that the ratio of Signal to Noise is higher.

Here, the ‘signal’ is the original image, and the ‘noise’ is the error in reconstruction. So, if you find a compression scheme having a lower MSE (and a high PSNR), you can recognize that it is a better one. The following output results showing the performance of the proposed compressed technique for different precoding matrix with thetransformation.

Comparison is performed using various techniques and tabulated in Table 1.

4 Discussion

The hybrid compression using precoding and FSWT (Fast Stationary Wavelet Transform) has been proposed. This method gives the optimal compression by combining the precoding block and Fast stationary wavelet transform for all kind of still images, it is the extension of transformation based compression process. The initial compression has been done by the precoding matrix then the precoded data has been compressed using FSWT (Fast Stationary Wavelet Transform). It dually reduces the size of the information by precoding block and transformation. So the optimal performance has been achieved compared to other methods. The compression ratio can be achieved depend upon the precoding matrix elements. So it is very much suitable to get good compressed data by adjusting the precoding matrix elements.

References

Jeng

J.-H.

and Tseng

C.-C.

, Study on huber fractal image compression, Image Processing, IEEE Transactions on18(5) (2009).

Jiang

, A low-cost content-adaptive and ratecontrollable near-lossless image codec in DPCM domain, Image Processing, IEEE Transactions on9(4) (2000).

Marpe

, Berlin

GmbH.

, Blattermann

, Ricke

and Maass

, A two-layered wavelet-based algorithm for efficient lossless and lossy image compression, IEEE Transactions on Circuits and Systems for Video Technology10(7).

Burstedde

and Kunoth

, Fast iterative solution of elliptic control problemsin wavelet discretization, Journal of Computational and Applied Mathematics (2003).

Leung

S.W.

, Zhu

Y.S.

, Wong

C.M.

and Wong

K.K.

, Time-Frequency and Time-Scale Analysis, Proceedings of the IEEE-SP International Symposium on, 1996.

Karami

, Yazdi

and Mercier

, Compression of hyperspectral images using discerete wavelet transform and tucker decomposition, IEEE Journal Of Selected Topics In Applied Earth Observations And Remote Sensing5(2) (2012).

Babu

K.A.

, Implementation of data compression using Huffman coding Methods and Models, in 11 Computer Science International Conference on(ICM2CS), 2010.

Zhang

and Liu

, A novel lossless compression for hyperspectral images by context-based adaptive classified arithmetic coding in wavelet domain,Xian, Geoscience and Remote Sensing Letters, IEEE4(3) (2007).

Tajallipour

, Saskatoon

S.K.

and Wahid

, Efficient implementation of adaptive LZW algorithm for medical image compression, 14th International Conference on Computer and Information Technology (ICCIT)2011.

10.

Xie

Y.-H.

, Tang

X.-A.

and Sun

M.-Y.

, Image Compression Based on Classification Row by Row and LZW Encoding, CISP ’08 Congress on Image and Signal Processing, 1, 2008.

11.

Oizumi

, Preprocessing method for DCT-based image-compression, Consumer Electronics, IEEE Transactions on Consumer Electronics52(3) (2006).

12.

Bhatnagar

, Jonathan Wu

Q.M.

and Raman

, A new fractional random wavelet transform for fingerprint security, IEEE Transactions On Systems, Man, And Cybernetics— Part A: Systems And Humans42(1) (2012).

13.

Porwik

and Lisowska

, The haar–wavelet transform in digital image processing: Its status and achievements, Machine Graphics Vision13(1/2) (2004), 79–98.

14.

Chang

C.-C.

, Tai

W.-L.

and Lin

C.-C.

, A reversible data hiding scheme based on side match vector quantization, IEEE Transactions on Circuits and Systems for Video Technology16(10) (2006).

15.

Prediction and estimation of some characteristics of time series, IEEE Transactions on Information Theory55(9) (2009).

16.

Lahme

and Miranda

, Karhunen-Loeve decomposition in the presence of symmetry, IEEE Transactions on Image Processing8(9) (1999).

17.

Karim

S.A.A.

, Karim

B.A.

, Kamarudin

M.H.

and Hasan

M.K.

, Wavelet Transform and Fast Fourier Transform for signal compression: A comparative study, (ICEDSA), 2011 International Conference on Electronic Devices, Systems and Applications.

18.

Gai

, Yang

and Zhang

, Multiscale texture classification using reduced quaternion wavelet transform?International Journal of Electronics and Communications67(3) (2013)233–241.

19.

Gai

and Limin

, Image denoising using normal inverse Gaussian model in quaternion wavelet domain, Multimedia Tools and Applications74(3) (2015)1107–1124.

20.

Gai

, Yang

, Wan

and Lei

, Denoising color images by reduced quaternion matrix singular value decomposition?Multidimensional Systems and Signal Processing26(1) (2013)307–320.

21.

Guerrero

J.M.

, Pajares

, Montalvo

, Romeo

and Guijarro

, Support vector machines for crop/weeds identification in maize fields, Expert Systems with Applications39(12) (2012)11149–11155.

22.

Montalvo

, Guerrero

J.M.

, Romeo

, Emmi

, Guijarro

and Pajares

, Automatic expert system for weeds/crops identification in images from maize fields, Expert Systems with Applications40(1) (2013)75–82.