Piecewise-linear subband coding scheme for fast image decomposition

Abstract

Transform coding methods play a very important role in the development of diverse multimedia technologies. The discrete cosine and wavelet transforms are frequently used in the field of image processing and set up a basis for contemporary image compression standards (JPEG, MPEG). In this paper a novel two-channel piecewise-linear subband coding scheme (PL-SBC) is introduced. Its most important advantage are exceptionally fast and easy for implementation computational algorithms combined with good reconstruction quality. The proposed PL-SBC system is based on the dual filter bank consisting of a single filter at the decomposition stage and a single one at the reconstruction stage. For the presented PL-SBC scheme, the conditions of perfect reconstruction and the piecewise-linear approximation filter bank have been defined. The compression properties of a new subband coding scheme have been analysed for different categories of images and in comparison with well-known signal transforms, such as cosine, piecewise-linear, piecewise-constant and wavelet transforms. The research includes a comparison of the reconstruction error both in objective as well as subjective approach.

1 Introduction

Over the last few years portable devices have become an especially important platform for multimedia tools. Mobile devices have gained huge popularity due to their connectivity (wireless and packet transmission) and relatively high computing power (gigahertz speed, multicore processors). However, reduced energy resources restrict the range of their applications particularly in the fields of image analysis and computer vision. Among different techniques of image processing, transform coding methods come to the foreground. They are applied in image enhancement, compression, watermarking etc.[14], nevertheless they are characterized by high computational complexity – floating point representation and calculations, specialized addressing modes. Therefore, it seems of crucial importance to optimize image processing performance using simple and fast algorithms. The proposed piecewise-linear subband coding scheme (PL-SBC) is addressed to this area of applications. Its most important characteristic is dual filter bank i.e. the source signal decomposition is performed with a single filter and the reconstruction is obtained with only one filter as well. This results in very fast and easy to implement computational algorithms.

The main purpose of this paper is to present the structure and properties of the PL-SBC decomposition scheme and to investigate its compression capabilities for different categories of images: photographic, synthetic and compound. For some applications, the reconstruction results of the presented subband image coding method are comparable and even better than the results of compression by the DCT and wavelet transforms. In combination with efficient computational algorithms this method offers competitive alternative for other linear transforms.

The paper is organized as follows. Related works are discussed in Section 2. The proposed subband coding system, perfect reconstruction conditions, piecewise-linear approximation filters and fast algorithms for the decomposition and reconstruction stages are introduced in Section 3. The experiments and results are described in Section 4. The conclusions are presented in the final section.

2 Related works

The research on transform coding for images was initiated with works of Andrews and Pratt [2] at the end of the sixties of the 20th century. The next two decades are a period of the intensive study of transforms providing the optimum image energy accumulation in certain, little and closely limited area of the spectrum. Out of many transforms examined in this period, the discrete cosine transform (DCT) got the greatest significance. The decisive factors were very good compression properties and comparatively fast computational algorithms. As a result, the international image compression standards JPEG and MPEG based on the DCT transform were published [15–18].

Issuing new image compression standards based on the cosine transform didn’t reduce the intensity of the research into new image coding methods. In 1986 Woods and O’Neil [29] used the subband coding method to image compression for the first time. The subband coding consists in the decomposition (analysis) of the signal by the digital filtering. As a result we obtain subbands which are downsampled to preserve the same number of samples as in the source signal. The reconstruction (synthesis) of the signal proceeds in the reverse order. The subband signals are upsampled, filtered and added [28]. A typical two-band subband filtering system is presented in Fig. 1.

Fig. 1

Structure of two-band subband filtering system. H1 and G1 are low-pass filters and H2 and G2 are high-pass filters

Methods based on applying wavelet transforms [1,20,25,26] represent a very similar approach to the image decomposition. The concept of wavelets can be viewed as the synthesis of ideas which originated in engineering, physics and mathematics [5,13]. The past 20 years have proved wavelet to be a powerful mathematical tool with a great variety of possible applications. In fact, methods of using the wavelet transforms for image coding became the main research area in the field of the image processing and analysis.

Regardless of the great success of the JPEG standard it is not suitable for the compression of all the types of images e.g. it gives the poor compression quality of documents. Being aware of the existing standard disadvantages, JPEG group undertakes research into a new standard development responding to new fields of application, such as: electronic trade, online libraries etc. As a result, the ISO 15444–1/ITU-T.800 standard called JPEG2000 has been published [18]. It is based on wavelet transforms [3,22,24,27], the algorithm of embedded block coding with optimized truncation [23] and the arithmetic coding. The new standard resolves a lot of problems of the JPEG standard, but its high computational complexity limits the application area.

A different category of transformations are piecewise-linear transforms. They are distinguished by very fast computational algorithms and represent an interesting alternative to transforms based on the harmonic functions. Piecewise-linear basis functions are derived from stepwise-constant basis functions by integration over certain finite interval. The sets of PL functions form a basis for some function spaces because they are linearly independent. They are not orthogonal but the sets of expansion coefficients can be simply calculated. The first efforts of applying those functions were presented by Paul and Koch [21]. As a result of further research conducted by the prof. Dziech team, new transforms based on Walsh and Haar functions were proposed [6,10]. Their applications in the field of image compression were investigated and presented in many publications [4,7–9,11,12]. It shows that the Haar-based piecewise-linear transforms have extremely efficient algorithms and good compression properties, particularly for the synthetic and compound images. However, the reconstruction quality of photographic images is unsatisfactory due to specific distortions.

3 Piecewise-linear subband coding system (PL-SBC)

3.1 Proposed two-channel filter bank

A block diagram of the proposed subband coding system using one pair of filters is presented in Fig. 2. In the decomposition (analysis) stage, the input signal is divided into two subbands W (z) and U (z). In the upper branch the signal is processed by filter H (z), delayed and downsampled by a factor of 2. In the bottom branch the input signal is only downsampled by a factor of 2. Because of delay z ⁻¹, the input signal is separated into odd and even components. Downsampling causes the reduction of samples amount and preserves the same length of signals before and after the decomposition stage. The reconstruction stage is constructed in a different way. The bottom subband signal U (z) is upsampled by a factor of 2, processed by filter G (z) and combined with the signal which is formed by upsampling and shifting the subband signal W (z) by z ². In the final step this signal is delayed (z ⁻¹) and added to upsampled subband signal W (z).

Fig. 2

Structure of the proposed subband coding system

For the discrete input signal X(z), the decomposition equations are formulated as follows

$$ Y(z)= X(z)\cdot H(z)\cdot {z}^{-1} $$

(1)

$$ W(z)=\frac{1}{2}\cdot Y\left({z}^{1/2}\right)+\frac{1}{2}\cdot Y\left(-{z}^{1/2}\right) $$

(2)

$$ U(z)=\frac{1}{2}\cdot X\left({z}^{1/2}\right)+\frac{1}{2}\cdot X\left(-{z}^{1/2}\right) $$

(3)

Substituting (1) for (2) gives the subband signals

$$ W(z)=\frac{1}{2}\cdot X\left({z}^{1/2}\right)\cdot H\left({z}^{1/2}\right)\cdot {z}^{-1/2}+\frac{1}{2}\cdot X\left(-{z}^{1/2}\right)\cdot H\left(-{z}^{1/2}\right)\cdot \left(-{z}^{-1/2}\right) $$

(4)

$$ U(z)=\frac{1}{2}\cdot X\left({z}^{1/2}\right)+\frac{1}{2}\cdot X\left(-{z}^{1/2}\right) $$

(5)

These equations can be written in the matrix form

$$ \left[\begin{array}{c}\hfill W(z)\hfill \\ {}\hfill U(z)\hfill \end{array}\right]=\frac{1}{2}\left[\begin{array}{cc}\hfill H\left({z}^{1/2}\right)\cdot {z}^{-1/2}\hfill & \hfill H\left(-{z}^{1/2}\right)\cdot \left(-{z}^{-1/2}\right)\hfill \\ {}\hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill X\left({z}^{1/2}\right)\hfill \\ {}\hfill X\left(-{z}^{1/2}\right)\hfill \end{array}\right] $$

(6)

The reconstruction equations are formulated as follows

$$ V(z)= W\left({z}^2\right) $$

(7)

$$ Q(z)= U\left({z}^2\right) $$

(8)

$$ P(z)={z}^{-1}\cdot \left( V(z)\cdot {z}^2+ G(z)\cdot Q(z)\right) $$

(9)

$$ \widehat{X}(z)= P(z)+ Q(z) $$

(10)

Substituting (7),(8),(9) for (10) gives the output signal

$$ \widehat{X}(z)= z\cdot W\left({z}^2\right)+\left( G(z)\cdot {z}^{-1}+1\right)\cdot U\left({z}^2\right) $$

(11)

This relationship can be expressed in matrix form

$$ \widehat{X}(z)=\left[\begin{array}{cc}\hfill z\hfill & \hfill G(z)\cdot {z}^{-1}+1\hfill \end{array}\right]\cdot \left[\begin{array}{c}\hfill W\left({z}^2\right)\hfill \\ {}\hfill U\left({z}^2\right)\hfill \end{array}\right] $$

(12)

The fundamental requirement for subband coding scheme is to produce the output signal that is as close as possible or even exactly the same as the input signal. Substituting (6) for (12) gives the relationship between both signals

$$ \widehat{X}(z)=\left[\begin{array}{cc}\hfill z\hfill & \hfill G(z)\cdot {z}^{-1}+1\hfill \end{array}\right]\cdot \frac{1}{2}\left[\begin{array}{cc}\hfill H(z)\cdot {z}^{-1}\hfill & \hfill H\left(- z\right)\cdot \left(-{z}^{-1}\right)\hfill \\ {}\hfill 1\hfill & \hfill 1\hfill \end{array}\right]\left[\begin{array}{c}\hfill X(z)\hfill \\ {}\hfill X\left(- z\right)\hfill \end{array}\right] $$

(13)

This expands to

$$ \widehat{X}(z)=\frac{1}{2}\cdot \left( H(z)+ G(z)\cdot {z}^{-1}+1\right)\cdot X(z)+\frac{1}{2}\cdot \left( G(z)\cdot {z}^{-1}+1- H(z)\right)\cdot X\left(- z\right)={F}_0(z)\cdot X(z)+{F}_1(z)\cdot X\left(- z\right) $$

(14)

The F ₀ (z) defines the transfer function of the subband coding scheme and determines the quality of reconstruction. If some scaling and delay can be accepted, the filter bank performs perfect reconstruction when

$$ {F}_0(z)=\frac{1}{2}\cdot \left( H(z)+ G(z)\cdot {z}^{-1}+1\right)= c\cdot {z}^{-{n}_0} $$

(15)

where:

• c – scaling factor

• n ₀ – delay factor

The F ₁ (z) denotes alias components and if it equals zero, an alias-free filter bank will be obtained. In this case

$$ {F}_1(z)=\frac{1}{2}\cdot \left( G(z)\cdot {z}^{-1}+1- H\left(- z\right)\right)=0 $$

(16)

For the proposed subband coding system, the perfect signal reconstruction is achieved when the following conditions are met

$$ H(z)+ H\left(- z\right)= c\cdot {z}^{-{n}_0} $$

(17)

$$ G(z)= z\cdot \left[ H\left(- z\right)-1\right] $$

(18)

3.2 Subband piecewise-linear approximation

The properties of the proposed subband coding system are specified by the filter H(z) transfer function. It should be designed to provide both the perfect reconstruction of the input signal as well as good approximation characteristics. Assuming the value of the predicted sample is defined as the difference between the arithmetic mean of neighboring input samples, an output can be written as

$$ y(n)= x(n)-\frac{x\left( n-1\right)+ x\left( n+1\right)}{2} $$

(19)

In z-transform domain

$$ Y(z)= X(z)-\frac{X(z)\cdot {z}^{-1}+ X(z)\cdot z}{2} $$

(20)

$$ H(z)=\frac{Y(z)}{X(z)}=-\frac{1}{2}\cdot \frac{{\left( z-1\right)}^2}{z} $$

(21)

This filter satisfies condition (17)

$$ H(z)+ H\left(- z\right)=2 $$

(22)

Substituting (21) for (18) gives the reconstruction filter G(z)

$$ G(z)=\frac{1}{2}\cdot \left({z}^2+1\right) $$

(23)

In Fig. 3 the decomposition of the input signal onto subbands w(n) and u(n) is presented in the graphical form.

Fig. 3

Piecewise-linear decomposition by PL-SBC system

The input signal x(n) is presented with the bold line. The subband signal u(n) is formed by downsampling by a factor of 2. The subband signal w(n) is formed as the difference of an odd sample and the averaged value of the two neighboring even samples.

3.3 Matrix formulation

The proposed piecewise-linear coding subband system (PL-SBC) can be represented in the matrix form. The signal decomposition stage is described as follows

$$ \left[\begin{array}{c}\hfill \mathbf{u}\hfill \\ {}\hfill \mathbf{w}\hfill \end{array}\right]=\mathbf{D}\times \mathbf{x}=\left(\mathbf{H}\times {\mathbf{P}}_{-1}\times {\mathbf{K}}_{\mathbf{U}}+{\mathbf{K}}_{\mathbf{B}}\right)\times \mathbf{x} $$

(24)

where:

• x – input signal vector with elements x _i , i = 0,1,…,N, N – even number

• w, u – subband signal vectors with elements u _i and w _i , i = 0,1,…,N/2

• D – decomposition matrix of size N + 1 x N + 1

• H – filter H(z) transfer matrix of size N + 1 x N + 1

• P₋₁ – delay matrix of size N + 1 x N + 1

• K_U, K_B – downsampling by a factor of 2 matrix of size N + 1 x N + 1

The reconstruction stage is described as follows

$$ \widehat{\mathbf{x}}=\mathbf{R}\times \left[\begin{array}{c}\hfill \mathbf{u}\hfill \\ {}\hfill \mathbf{w}\hfill \end{array}\right]=\left({\mathbf{P}}_{-1}\times \left({\mathbf{P}}_2\times {\mathbf{K}}_{\mathbf{U}}^{\mathbf{T}}+\mathbf{G}\times {\mathbf{K}}_{\mathbf{B}}^{\mathbf{T}}\right)+{\mathbf{K}}_{\mathbf{B}}^{\mathbf{T}}\right)\times \left[\begin{array}{c}\hfill \mathbf{u}\hfill \\ {}\hfill \mathbf{w}\hfill \end{array}\right] $$

(25)

where:

• $\widehat{x}$ – input signal vector with elements x _i , i = 0,1,…,N, N – even number

• w, u – subband signal vectors with elements u _i and w _i , i = 0,1,…,N/2

• R – reconstruction matrix of size N + 1 x N + 1

• G – filter G(z) transfer matrix of size N + 1 x N + 1

• P₋₁ – delay matrix of size N + 1 x N + 1

• P₂ – shift matrix of size N + 1 x N + 1

• K_U, K_B – downsampling by a factor of 2 matrix of size N + 1 x N + 1

Below, the reconstruction matrix for piecewise-linear decomposition of N + 1 = 9 signal length is presented. The dotted line separates two subband channels. The upper part performs downsampling by a factor of 2 and the bottom part performs convolution with the transfer function H(z) and downsampling by a factor of 2.

$$ {D}_{PL}=\left[\begin{array}{ccccccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill & \hfill 1\hfill \\ {}\hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill \dots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill \end{array}\right] $$

(26)

$$ {R}_{PL}=\left[\begin{array}{ccccccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill {\scriptscriptstyle \frac{1}{2}}\hfill & \hfill 0\hfill & \hfill \cdots \hfill & \hfill 0\hfill & \hfill 1\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right] $$

(27)

3.4 Fast computational algorithms

The most important feature of the proposed piecewise-linear subband coding scheme (PL-SBC) are fast and easy for implementation computational algorithms. PL-SBC fast algorithms have been created on the basis of matrixes (26) and (27). In Fig. 4 the flowcharts of the piecewise linear decomposition and reconstruction algorithms for the signal length N + 1 = 9 are presented.

Fig. 4

PL-SBC decomposition (left) and reconstruction (right) algorithms, N = 8. The arrows at the reconstruction stage indicate multiplication by ½

The PL-SBC decomposition algorithm operates on the input signal of odd length N + 1 and splits its up into two subband signals N/2 and N/2 + 1 long. The signals of even length have to be padded with one sample. On the basis of the filter transfer function, it is possible to extend the input signal with sample which produce zero value coefficient.

Let

$$ y(n)= x(n)-\frac{x\left( n-1\right)+ x\left( n+1\right)}{2}=0 $$

(28)

Then

$$ x\left( n+1\right)=2\cdot x(n)- x\left( n-1\right) $$

(29)

A simplicity of implementation is an important advantage of the presented algorithm. The algorithm of the decomposition stage for the N-size input signal requires only N additions/subtractions and N binary shifts. No complicated addressing modes are required, because only a division into even and odd samples takes place. Only basic arithmetical operations are performed: adding and subtracting. Multiplication and division by 2 can be easily implemented with binary shifts. Calculations can be led both on floating point as well as fixed point numbers. For example, for the monochrome image with 256 grey levels, spectral coefficients are located in the scope from −255 to 255 with the accuracy of ½. For representing such a spectre 10-bit representation will be enough e.g. in the fixed-point format (9.1) where the integral part is represented with 9 bits and the fractional part with 1 bit.

The algorithm of PL-SBC reconstruction stage is also very simple for implementation. It requires N additions/subtractions and N/2 binary shifts and has 25 % lower complexity than the decomposition algorithm.

3.5 Multilevel PL-SBC scheme

A possibility to construct cascaded systems is an important advantage of the subband coding systems. If some SBC system has a perfect response, any intermediate subband signal may be decomposed by the application of the same SBC system and a two-level system will also have a perfect response. If cascading is applied to each of the subband signals, the system is called a uniform cascade system. Otherwise, it is named a non-uniform or pyramid cascade [19]. In practical applications, especially in the area of multimedia processing, multilevel subband coding systems are usually used. In this method, subband signals from one decomposition level are treated as the input to the next level. In Fig. 5 the two-level non-uniformly cascaded PL-SBC system is presented.

Fig. 5

Two-level pyramid PL-SBC system

Cascaded multilevel SBC systems can also be represented in the matrix form. The reconstruction matrix of 3-level pyramid PL-SBC system for signal N + 1 = 9 samples long is described as follows:

$$ {D}_{PL3}=\left[\begin{array}{ccccccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ {}\hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill \\ {}\hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill \\ {}\hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill & \hfill 0\hfill & \hfill 0\hfill \\ {}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -\frac{1}{2}\hfill & \hfill 1\hfill & \hfill -\frac{1}{2}\hfill \end{array}\right] $$

(30)

4 Piecewise-linear subband image coding

The subband decomposition for images is based on 1-D subband algorithms applied to the rows and columns of 2-D data array. The basic 2-D scheme can be used to obtain finer decompositions of the spectrum. In the uniform subband decomposition, the 2-D subband coding scheme is applied to each of 4 sub-images, obtaining 16 sub-images each with 1/16 of the input data. The decomposition can be further applied to each of the subbands.

Many diverse non-uniform decomposition schemes can be constructed. In the pyramid scheme [28], only a low-frequency sub-image is decomposed into 4 sub-images. The K-level pyramid subband decomposition produces 3 K + 1 subbands. In this scheme, the input image is decomposed on sub-images being sequential approximations of the input data. Another approach to subband decomposition is to apply multilevel 1-D subband algorithm to the rows and columns of the image. This method is utilized by Haar Piecewise-Linear Transforms (HPL,PHL) [11,12]. Logarithmically scaled spectrums of the 2-level PL-SBC uniform, the 2-level PL-SBC pyramid and log ₂ N-level PL-SBC (HPL like) systems are shown in Fig. 6.

Fig. 6

PL-SBC decomposition systems: a) 2-level uniform PL-SBC, b) 2-level pyramid PL-SBC, c) log ₂ N-level PL-SBC where NxN-image size

In order to evaluate compression capabilities of the piecewise-linear subband coding scheme, selected thresholds in the spectral domain are applied. Each sample whose magnitude is greater than the threshold level is selected and the rest are set to zero. An inverse 2-D transformation is then performed to obtain a reconstructed image.

Different classes of test images have been analyzed. Apart from well-known photographic images (Lena, Goldhill), computer generated imagery and compound images were used (Fig. 7). All the test images were taken from the University of Waterloo image repository (http://links.uwaterloo.ca/Repository.html).

Fig. 7

Computer generated and compound test images

In subband coding systems, the compression quality is closely related to the decomposition level. When the decomposition level exceeds 3, the coding gain is changed insignificantly. Therefore, in further investigations a three-level pyramid decomposition scheme will be used. Additionally, for the goal of threshold sampling 2-D PL-SBC spectrum subbands were scaled with the successive powers of √2 factor. This normalization procedure can be integrated with the quantization process being a common post-processing procedure in most image coding methods.

Plots of the Peak Signal-to-Noise Ratio (PSNR) versus a compression ratio defined as the percentage of zero coefficients for the selected test images are shown in Fig. 8. The presented subband coding scheme has very good decomposition properties especially for computer generated images. Images Slope and Text are perfectly reconstructed for 53.6 % and 73.1 % of rejected coefficients respectively.

Fig. 8

Threshold sampling: PSNR versus compression ratio for different test images

Photographic images (portraits, landscapes) are also well compressed. For the compression ratio up to 85 %, the reconstructed image quality measured by PSNR is higher than 30 dB. The detail analysis of reconstructed images shows only little distortions. As it is seen in Fig. 9, at the compression ratio CR = 90 % the reconstructed images are well visible and just around 92 % PSNR falls below 30 dB for Lena image.

Fig. 9

Reconstructed test images using threshold sampling with PL-SBC system at compression ratio 90 % (a) PSNR = 31.51 dB, (b) PSNR = 27.83 dB, (c) PSNR = 50.93 dB, (d) PSNR = 38.01 dB

The proposed subband coding scheme (PL-SBC) has been compared with different piecewise-linear and piecewise-constant transforms (Fig. 10). The decompressed image quality for the proposed scheme is much higher than for Walsh and PWL transforms, better than triangle wavelet and similar to Haar transform. For CR > 90 % Haar wavelet has better PSNR, but in the reconstructed images (Fig. 11) square distortions are visible. The PSNR performance of threshold sampling for different transforms and images for CR = 90 % is compared in Table 1.

Fig. 10

Threshold sampling: PSNR versus compression ratio for different stepwise-constant and piecewise-linear transforms for Lena image

Fig. 11

Reconstructed Lena image using threshold sampling with different transforms at compression ratio 90 % a PL-SBC, b Haar Wavelet, c Triangle Wavelet, d Walsh

Table 1 The PSNR performance of threshold sampling efficiency for CR = 90 %

In Fig. 12 the results of threshold compression of Lena and Montage image using the subband coding scheme, cosine and wavelet transforms are presented. The reconstructed image quality is comparable with the discrete cosine transform performed on 8x8 pixel blocks and CDF 9/7 [3] wavelet transform (Fig. 13). For compound images consisting of natural scenes, texts and graphics, the proposed coding scheme is very competitive in terms of quality with well-known transforms but much faster and easier for implementation.

Fig. 12

Threshold sampling: PSNR versus compression ratio for different transforms for Lena and Montage images

Fig. 13

Reconstructed Lena image using threshold sampling with different transforms at compression ratio 90 % a original image, b PL-SBC, c CDF 9/7 Wavelet, d DCT 8x8

5 Conclusions

In this paper a new method of image decomposition called piecewise-linear subband decomposition scheme (PL-SBC) has been presented and analysed. It can be treated as an alternative approach in reference to the transforms based on harmonic functions. This method makes significant improvement over existing piecewise linear transforms in all aspects. It has the best PSNR performance and subjective error properties of the piecewise-linear methods tested. The computational algorithms of PL-SBC system are even faster than Haar wavelet.

The PL-SBC decomposition produces spectrum similar to the wavelet transform, therefore many methods developed for the multiresolution analysis can be applied. The most powerful feature of the presented SBC system are very fast and easy for implementation computational algorithms that are much faster than that of the cosine and wavelet transforms. The compression properties of the above presented subband technique are comparable or - for synthetic images - even better than those of DCT and wavelet transforms, therefore the proposed method is especially suitable for processing of compound images e.g. scanned documents or computer presentations.