Hybrid DCT-HAAR block

In this paper we have constructed a new hybrid transform. We have combined the DCT block and the Haar block into one block which we have called hybrid DCT-HAAR block. This new block combines the advantages of the DCT which works extremely well for highly correlated data and the advantages of the Haar transform which gives superior results for images exhibiting rapid gradient variations. The DCT is applied to the upper left corner of the block. The Haar is applied to the remaining parts of the block. We derived the equations of the matrix M needed to recover the hybrid block. Our method increased the PSNR obtained by the DCT transform and enhanced the edge recovery of the Haar transform.

Keywords: DCT; Haar; Wavelet; Hybrid; PSNR

Image compression is an efficient technique of reducing the size of data representing an image that is highly correlated. The purpose of image compression is to save memory and transmission time [[8]]. There are different methods in which image can be compressed. One of the most common compressed graphic image formats is the JPEG format which is based on the Discrete Cosine Transform (DCT) [[12]]. Another most commonly transform used in image compression is the Wavelet transform. One of the simplest wavelet is the Haar wavelet. It is based on doing average and difference operations on the image intensity values [[15]].

There are two kinds of compression [[17]]. Lossless compression involves the preservation of the image as if no detail is lost. Lossy compression, allows less than perfect reproduction of the original image. The advantage of lossy compression (our work) is that it can produce a much smaller compressed file than lossless compression. Note that JPEG applies DCT with a zigzag quantization that makes the compression visually lossless. JPEG 2000 uses the Wavelet Transform in their compression scheme. DCT is well suited for highly correlated data. It does a kind of de-correlation [[1]] for those data and has the property of energy compactness. Energy compactness means that DCT tries to concentrate energy or information in some elements of the block instead of spreading it in the whole block. This helps in increasing the compression since we are only interested in the elements that contain the maximum energy needed. Note that DCT concentrates this energy in the upper left corner of the block where the low frequencies reside [[16]].

On the other hand, the Haar transform [[13]] works well for high frequencies and achieves a high compression ratio while maintaining the quality of the image. It is very well performant for images that have rapid gradient variations.

Combining DCT and DWT was done in [[2], [14]] by applying the discrete cosine transform on the discrete wavelet transform coefficients. In [[9]] Hybrid matrices are generated using combination of various matrices like DCT, Hadamard and Kekre's Transform.

The JPEG (Joint Photographic Experts Group) algorithm was founded to compress images with minimal data loss and high compression ratios. The JPEG consists of 4 different phases. First, the image is divided into 8 × 8 blocks of pixels. Next, the DCT can be applied to each block of image to convert it to the frequency domain. Then each one is compressed by performing a quantization process to remove the unnecessary information. Then, the transform coefficients which are quantized are transmitted to the receiver. Therefore, the DCT plays an important role of compression in the JPEG standard that offers a lossy compression of images. The JPEG process is shown in Fig. 1.

Graph: Fig. 1The JPEG process

The discrete cosine transform (DCT) is a concept for converting a signal into elementary frequency components and is based on dividing images into parts of different frequencies. The DCT de-correlates the image data. The de-correlation is the removal of redundancy between adjacent pixels [[3]]. It is one of the useful properties of Discrete Cosine Transform. After applying the DCT, the autocorrelation becomes very small. The data becomes uncorrelated. We can remove the unnecessary coefficients (small values) and transform the coefficients orderly to encode them independently and uniquely without repeating the same information represented in correlated pixels twice or more.

Equation 1 shows an example of the equation of the Discrete Cosine Transform (DCT)

1 $$\begin{array}{c}{g}^{\prime }\left(x,u\right)=\lambda \left(u\right)\mathit{cos}\frac{\pi \left(2x+1\right)u}{2N}\\ \text{where}\lambda \left(u\right)=\left\{\begin{array}{cc}\sqrt{\frac{2}{N}}& u=0\\ \sqrt{\frac{1}{N}}& \mathit{\text{otherwise}}\end{array}\right)\end{array}$$

Graph

The Discrete Cosine Transform (DCT) basis is shown in Fig. 2.

Graph: Fig. 2The DCT Basis

Another very popular technique in image compression is the Discrete Wavelet Transform. The purpose of Wavelet transform is to change the data from time-space domain to time-frequency domain for a better compression. In addition, The Discrete Wavelet Transform can give high compression rate [[11]]. First, the image is passed into two filters: a high (H) and a low (L) pass filter. This process can be repeated in order to get the four sub-bands LL, HL, LH and HH. This is called the 2-D DWT [[11]]. Figure 3 shows a 3-level wavelet decomposition.

Graph: Fig. 3The 3 Level Decomposition of Wavelet

The Wavelet Transform produces a large number of zero or near zero coefficients. The compression is done by thresholding these values.

The Haar transform is a part of the wavelet family. It has its own basis and is the simplest wavelet basis. Equation 2 shows the Haar Transform basis formulas.

2 $$\begin{array}{c}\mathrm{\Psi }\left(\mathrm{x}\right)=\left\{\begin{array}{c}1,0.0\le x<0.5\\ -1,0.5\le x<1.0\\ 0,\mathit{\text{otherwise}}\end{array}\right)\\ \varnothing \mathit{pq}\left(x\right)=2^{\raisebox{1ex}{$p$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}\mathrm{\Psi }\left(2^{p}x-q+1\right)\end{array}$$

Graph

The Haar Transform Basis for 8 × 8 blocks is shown in Fig. 4.

Graph: Fig. 4The Haar Basis

It is regularly necessary to proceed with some measures to quantify the quality of reconstruction of lossy compression. The Peak Signal-to-Noise Ratio (PSNR) is one of these measures [[7], [10]]. It is given by the following equation:

3 $$\mathit{\text{PSNR}}=20{\mathit{log}}_{10}\left(\frac{255}{\sqrt{\frac{1}{n\ast m}{\sum }_{i=0}^{n-1}{\sum }_{j=0}^{m-1}{\left[f\left(i,j\right)-f^{\prime }\left(i,j\right)\right]}^2}}\right)$$

Graph

where.

• nxmis the size of the image,
• f(i,j)is the pixel of row i and column j of the original image, and;
• f'(i,j)is the pixel of row i and column j of the reconstructed image

In [[6]] they use suitable graph Fourier transforms (GFTs) to minimize the.

total signal representation cost of each pixel block. In [[5]] clusters of super-pixels are used as coding blocks. A graph transform is computed within each region. In [[4]] steerable DCT (SDCT) enables precise matching of directionality in each image block, achieving improved coding efficiency.

Let n be a positive integer. The one-dimensional DCT of order n is defined by an n x n matrix C whose entries are

$$C_{\mathit{ij}}=a_{i}cos\frac{\left(2j+1\right)\pi }{2n}$$

Graph

$$C=\sqrt{\frac{2}{n}}\left[\begin{array}{cccc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}& \Lambda & \frac{1}{\sqrt{2}}\\ cos\frac{\pi }{2n}& cos\frac{3\pi }{2n}& \Lambda & cos\frac{\left(2n-1\right)\pi }{2n}\\ \mathrm{M}& \mathrm{M}& \Lambda & \mathrm{M}\\ cos\frac{\left(n-1\right)\pi }{2n}& cos\frac{\left(n-1\right)3\pi }{2n}& \Lambda & cos\frac{\left(n-1\right)\left(2n-1\right)\pi }{2n}\end{array}\right]$$

Graph

The discrete cosine transform, C, has one basic characteristic: it is a real orthogonal matrix.

$$\begin{array}{c}{\mathrm{C}}^{\mathrm{T}}\mathrm{C}=1\\ {\mathrm{C}}^{-1}={\mathrm{C}}^{\mathrm{T}}\end{array}$$

Graph

The 2d- DCT is a separable transform:

We apply the one dimensional DCT first in the horizontal direction F = C*XT. Then we applied it in the vertical direction Y = C*FT.

The 2d-DCT is the matrix:

$$\mathrm{Y}=\mathrm{C}{\left({\mathrm{CX}}^{\mathrm{T}}\right)}^{\mathrm{T}}={\mathrm{CXC}}^{\mathrm{T}}$$

Graph

Since C is an orthogonal matrix we can solve for X using C−1 = CT

$$\mathrm{X}={\mathrm{C}}^{\mathrm{T}}\mathrm{YC}$$

Graph

The 8 × 8 DCT BASIS (C for n = 8):

Graph

And the DCT of an 8 × 8 image block X is: Y=CXCT.

For example the 8 × 8 image block X and its 8 × 8 DCT Y is shown below:

Graph

DCT can be used for image compression because the first few coefficients could capture most of the image. DCT discards some of the high frequency information (edges) and transmit the "important" coefficients (the coefficients that have most information about the image).

The most important values to our eyes will be placed in the upper left corner of the matrix (low frequency). The least important values will be mostly in the lower right corner (Fig. 5) of the matrix (high frequency).

Graph: Fig. 5The DCT Block

Applying this concept to our previous example, we get:

Graph

In general mxm sub-block in the upper left corner of the block is kept while the other entries are put to zero. An illustration is shown in Fig. 6.

Graph: Fig. 6DCT Quantization

The 8 × 8 HAAR transform matrix is

$$H=\frac{1}{\sqrt{8}}\left[\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 1& 1& 1& 1& -1& -1& -1& -1\\ \sqrt{2}& \sqrt{2}& -\sqrt{2}& -\sqrt{2}& 0& 0& 0& 0\\ 0& 0& 0& 0& \sqrt{2}& \sqrt{2}& -\sqrt{2}& -{\sqrt{2}}_1\\ 2& -2& 0& 0& 0& 0& 0& 0\\ 0& 0& 2& -2& 0& 0& 0& 0\\ 0& 0& 0& 0& 2& -2& 0& 0\\ 0& 0& 0& 0& 0& 0& 2& -2\end{array}\right]$$

Graph

The HAAR of an 8 × 8 block X is: Y=HAHT.

It is not difficult to see that that is H orthogonal. H−1 = HT.

The compressed image is obtained from: X = HTYH.

After applying the Haar transform, the values that are less than a threshold α are zeroed. The remaining values are kept. A small compression ratio leads to a small compression. However, the PSNR will be better. An illustration is shown in Fig. 7.

Graph: Fig. 7Haar Quantization

The energy packing properties of the DCT is better than the Haar transform.

Haar transform gives superior results for images exhibiting rapid gradient variations. Unlike the discrete cosine transform, the HAAR transform is not Fourier-based and therefore wavelets do a better job of handling discontinuities in data.

The basis for the Fourier transform (FT) are sinusoids. To reconstruct a spike like signal (or edges), you will need to superpose infinite number of sinusoids. The FT doesn't work efficiently with non-stationary signals. (Fig. 8).

Graph: Fig. 8The HAAR high frequencies

The HAAR efficiency in handling high frequencies is shown in the following image:

Our contribution is to combine these 2 transforms into one transform which has a new basis which is the combination of the DCT and the HAAR basis. Y = (C + H)X(C + H)T.

Taking advantage of the energy compactness property of DCT and the efficiency of the Haar transform, we suggest a process where a hybrid DCT-Haar block is used. The way this block is formed is illustrated in Fig. 9.

Graph: Fig. 9The DCT-Haar block

The process consists of the following steps:

• Dividing the image into 8 × 8 blocks
• Computing the DCT and Haar transforms for each block based on Eq. 4.
• ath display="block" xmlns="http://www.w3.org/1998/Math/MathML">O=BABT _ht_

Graph

where.

• Ais the 8 × 8 original block,
• Bis the combined 8 × 8 (DCT + Haar) basis (C + H).
• Ois the combined 8 × 8 (DCT + Haar) block.

Equation 4 is equivalent to an equation of the following form:

5 $$\left(\mathrm{O}\right)=\mathrm{M}\left(\tilde{A}\right)$$

Graph

where.

• (O)is the vectorized version of O,
• ( $\tilde{A}$ )is the vectorized version of $\tilde{A}$ ,
• Mis a 64 × 64 matrix to be determined.

We are interested in the matrix M because it will be the key for block recovery. Note that M is of size n2xn2for an nxn block.

In order to get the general formula of M for any nxn block, a general form of A and B are taken. The results appear in Figs. 10 and 11.

Graph: Fig. 10Matrix M for an 8 × 8 Block

Graph: Fig. 11Some Sub-Matrices of M for an 8 × 8 Block

Figure 11 shows some submatrices of the matrix M. the other sub matrices can be constructed in the same manner because there is a repeated pattern. A feasible code is presented in Fig. 12.

Graph: Fig. 12Algorithm for generating the M matrix

Figure 12 shows how to calculate the n2x n2 Matrix for a given nxn block. It calculates all the components of the M matrix (represented by m(i,j) in the algorithm) given in Fig. 9.

For example m(1,1) = b11xb11, m(1,2) = b11xb12,......

Figures 13, 14, and 15 show the M matrix for DCT, Haar and mixed transform for 4 × 4 blocks.

Graph: Fig. 13M Matrix for Haar Basis for 4 × 4 Blocks

Graph: Fig. 14M Matrix for DCT Basis for 4 × 4 Blocks

Graph: Fig. 15M Matrix for Mixed 4 × 4 Blocks

If M is invertible, then M−1 is used to get $\tilde{A}$ . There is nothing that guarantees the invertibility of M. Therefore, we can get $\tilde{A}$ by getting the pseudo inverse of M or simply the transpose of M and multiplying the answer by O as shown in Eq. 6.

6 $$\left(\tilde{A}\right)={\mathrm{M}}^{†}\left(\mathrm{O}\right)$$

Graph

Then $\widetilde{\left(A\right)}$ should be arranged correctly to get the 8 × 8 recovered block $\tilde{A}$ .

To validate our proposed methods, we used a set of 4 grayscale images: Barbara, Boat, Peppers and Lena that are represented respectively in Fig. 16. The size of each image is 512 × 512.

Graph: Fig. 16Images used

The efficiency of our method is tested in this section. It must be compared with the DCT and Haar transforms applied on 8 × 8 blocks using the same quantization method.

In order to compare our method with the DCT transform, different values for the parameter m are used and the PSNR value for each m is calculated. For the Haar blocks chosen in our method, α is set to 15. Plots of m versus PSNR values for different images are shown in Fig. 17.

Graph: Fig. 17DCT Parameter m vs PSNR for Different Images Using DCT and our Method

It is clear that our method gives a higher PSNR than DCT for the same value of m for those images especially when there is more compression. In fact a small value of m means that a bigger portion of the block is set to zero i.e. more compression is involved. More compression means a smaller PSNR value. The relation between m and the compression ratio for the Boat image is shown in Fig. 18.

Graph: Fig. 18Relation between m and Compression Ratio

In order to compare our method with the Haar transform, different values for the parameter α are used and the PSNR value for each α is calculated. For the DCT blocks chosen in our method, m is set to 4. Plots of α versus PSNR values for different images are shown in Fig. 19.

Graph: Fig. 19Haar Threshold α vs PSNR for Different Images Using Haar and our Method

It is clear that our method gives a higher PSNR than Haar for the same value of α for those images especially when there is more compression. In fact a large value of α means that a bigger portion of the block is set to zero i.e. more compression is involved. More compression means a smaller PSNR value. The relation between α and the compression ratio for the Boat image is shown in Fig. 20.

Graph: Fig. 20Relation Between α and Compression Ratio

The results show that our method outperforms the DCT and Haar transforms for those four images. In addition, for the Barbara image where there are a lot of high frequencies due to the big number of edges, it is clear that our method has a better recovery than DCT and Haar.

To investigate more, DCT and our method are applied for the 4 images for the same compression ratio as shown in Figs. 21, 22, 23, and 24.

Graph: Fig. 21Results for the Barbara Image

Graph: Fig. 22Results for the Lena Image

Graph: Fig. 23Results for the Pepper Image

Graph: Fig. 24Results for the Boat Image

The Figures show that our method gives a PSNR better than that of DCT for the same compression ratio. For the same compression ratio, the error of recovery for both the Haar transform and our method is shown in Fig. 25.

Graph: Fig. 25Error Images after Applying Haar and our Method

Figure 25 shows that the error of recovery via the Haar transform in all images is bigger than the error produced from our method. The error reflects the ability to recover the images' edges. Therefore, our method gives a better PSNR than DCT and better edge recovery than Haar. In order to see the performance of our method, the thresholds α of Haar and m of DCT are varied. This is accompanied by presenting the percentage of the sent DCT blocks for the Pepper image. Results are shown in Table 1.

Variation of α and m for Pepper Image

Table 1 shows that for any value of m, increasing α leads to more compression. However, for the same α increasing m leads to less compression. Compression ratio and PSNR are inversely proportional. In fact, increasing the compression leads to a sacrifice in the image quality. The percentage of the DCT blocks taken is affected by the values of α and m. Increasing α for a fixed m leads to take more DCT blocks because big values of α lead to a high compression and low PSNR for Haar blocks. This makes the sender choose more DCT blocks. For a fixed value of α, decreasing m leads to choosing more Haar blocks. This can be explained in the same manner as before.

Overall, examining the values of the table can help in choosing the best α and m to be applied in the algorithm. For α = 15 and m = 4, the compression ratio is acceptable and the PSNR value indicates a good quality of the image. Therefore, those values (for 8 × 8 blocks) are chosen to be applied in the compression algorithm of our method.

We compared our algorithm to DCT to one of the state art approach which is the steerable discrete cosine transform [[4]] using 8 × 8 blocks. Our approach gave higher PSNR for all the images as shown in Table 2.

Comparison of our approach with DCT and Steerable DCT using 8 × 8 block

This paper combined DCT and Haar transforms into one hybrid block. It exploited the advantages of both transforms while minimizing the weaknesses of each one. While DCT is applied to the upper left corner of the block the remaining parts of the block are transformed via Haar. We derived the equations of the matrix M needed to recover the hybrid block. Our method increased the PSNR obtained by the DCT transform and enhanced the edge recovery of the Haar transform.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.