Filter Bank Design and Sub-Band Coding
Arash Komaee, Afshin Sepehri
Department of Electrical and Computer
Engineering
Email: {akomaee, afshin}@eng.umd.edu
1. Introduction
In this project, we design a Quadrature Mirror Filter (QMF) Bank with application to sub-band image coding. Then we extend our result to four-band filter bank.
In section 2
we design a QMF filter bank with the choice of analysis filters 
. We then find 
, 
, 
, 
so that our system satisfies perfect reconstruction
constraint. We will see simulation result and advantages and disadvantages of
such a system through simulation.
In section 3
we want to be a linear-phase FIR filter. We design our filters so we
again meet perfect reconstruction constraint. We will see properties of such a
filter.
In section 4 we design a perfect reconstruction QMF bank with IIR analysis and synthesis filters. We simulate the system and see pros and cons of the design.
Now we test the results of previous sections and their applications on image sub-band coding. In section 5 we extend the concept of 1-D filter banks to 2-D. We apply our filters to some sample images and try to get as higher compression rate as possible by assigning less number of bits to bands with less energy level. We develop a performance evaluation measure so that we can compare different filter banks.
Section 6 extends previous experiment to four-band filter bank. We develop our 2-D filter banks so we can get better performance in sense of less number of bits per pixel along with preserving image quality to a reasonable extent.
2. Two Channel Perfect Reconstruction
Filter bank
A diagram for the analysis/synthesis system used for sub-band coding with two channels is shown in Figure 2.1
Figure 2.1 Two-channel filter bank
The relation between input 
and output 
in z domain is defined
as
(2.1)
This can be written as
(2.2)
which
is the distortion transfer function and
is the aliasing term.
To achieve perfect
reconstruction, 
must be pure delay and
must be canceled completely. That is the filters must satisfy
the following conditions:
(2.3)
(2.4)
Solving the above equations for 
and 
we obtain
(2.5)
(2.6)
This is the most general constraint that we have on our synthesis filters so that we can achieve perfect reconstruction. This will be used in later sections.
2.1 Quadrature Mirror Filter
Bank
If we constrain
and 
to be mirror image of
each other,
i.e. 
then we have
(2.7)
(2.8)
So, if we design filter we are able to design other
filters according to equations (2.7), (2.8), and . These filters can be FIR or IIR.
Also, we can put another
constrain and consider only designing with FIR filters. Consequently the two
following conditions must be satisfied by
(2.9)
(2.10)
where 
and 
are real constants and 
and
are integers. Solving the equations we result
(2.11)
(2.12)
Having the above equations satisfied, we need that be even and be odd integers
so we define them as
Also we define
Thus the general form for quadratic mirror two
channel FIR filters will be
(2.13)
(2.14)
Clearly the filters are from
order one so they cannot be good approximations for ideal low-pass and high
pass filters. The frequency response of the filters are shown in Figure 2.2 for
and 
.
Figure 2.2 Frequency response of and defined in
(2.13) and (2.14) for c0=c1=½
and n0=n1=0
2.2. Simulation
We can test perfect reconstruction property of the system through simulation.
Figure 2.3 Simulation result of the
perfect reconstruction filter bank shown in figure 2.2
A random input applied to
the system of figure 2.1 with filters 
and 
is shown in figure
2.2. The simulation result can be seen in figure 2.2. As depicted in figure,
the two plots of 
and 
are identical (except one step delay) which shows the system
is perfect reconstruction.
2.3. Discussion
Making assumption of in filter design has
advantages and disadvantages. As we can see in 2.7 and 2.8, synthesis filters and and analysis filter all can be designed
easily when is designed. So this makes designing process fast and easy.
Meanwhile we face some quality degradation using such a system.
If we use FIR filters, having system perfect reconstruction makes degree of freedom in designing the filters low (2.13 and 2.14) and such a system does not have good quality and we cannot achieve sharp cut-off. Thus frequency bands cannot be separated very well.
If we use IIR filters, we may
face stability problems on and . Hence, finding stable filters is so hard and such design is
not trivial. We will see more on section 4.
3. Linear-phase FIR filter Design
In this section we are about to
design and as a linear-phase FIR
filter. As shown in previous section, having the assumption we can design a perfect
reconstruction system, but such a system does not have acceptable response in
stop and pass bands, and as a result we do not get good quality and
performance. So, to achieve better performance we need to relax the condition so we can design and separately yet
preserving perfect reconstruction condition. As you will see in the following
subsection, designing such a filter is not easy but will give us a really
better performance than the order one filter we came to in previous section.
3.1. Designing a High Quality FIR Perfect Reconstruction
Filter Bank
If we relax the condition , it is possible to design and with sharp cut-off
band. The cost we must pay for such filters is the complexity in design and
implementation of high order filters. Here we will introduce a two-step
procedure to design a perfect reconstruction two-channel filter bank. In the first
step we obtain the impulse response of to satisfy the
requirements of cut-off frequency and transition band. In the second step we
will find both have acceptable frequency response and satisfy the condition
of perfect reconstruction
3.1.1. Designing H1(z)
We assume that is a linear FIR filter from an even order i.e.
(3.1)
where 
is any even integer. The
Z-transform of 
will be
(3.2)
We can show that the Fourier transform of can be written as
(3.3)
Let us define 
as
(3.4)
then we have
(3.5)
Also we define
(3.6)
(3.7)
where 
. Based on the above definitions we can write
(3.8)
According to figure 3.1 we denote by 
and 
, the stop and pass bands of.
Figure 3.1 Stop and pass bands in a
high pass filter
The total power of error (deviation of 
from ideal filter) in
stop and pass bands are
(3.9)
(3.10)
Considering (3.8), one can show that 
and 
can be written in the
following form
(3.11)
(3.12)
where 
and 
are defined as
(3.13)
(3.13)
Now we define the cost
function of our optimization problem as a linear combination of and
(3.14)
Defining 
as
(3.15)
We can write the cost function as
(3.16)
Our goal in this problem is
to obtain 
such that 
be minimized and also
the frequency response of the filter be equal to 1 at 
. The solution to this problem is
(3.17)
where 
is the eigenvector of 
corresponding to
smallest eigen-value.
Note that 
is a factor, which
specify the relative importance of the error in stop and pass bands. By proper
choice of the parameters ,, and we can obtain the best
performance of the filter .
3.1.2. Designing H0(z)
The design of is more difficult than
. In this case not only we must design for acceptable
frequency response, but we must meet the perfect reconstruction requirements.
Again we assume that is linear phase with
even order 
. Let
(3.18)
and assume that
(3.19)
We will see that 
is the number of free
parameters we can use for shaping the frequency response of . The remaining degrees of freedom (
) will be used to satisfy the perfect reconstruction
requirements. The poly-phase components of and can be written as
(3.20)
(3.21)
(3.22)
(3.23)
And the poly-phase matrix will be
(3.24)
We define 
as the determinant of 
and we know that is from order 
.
(3.25)
Let us define vectors 
and 
as
(3.26)
(3.27)
Also we define the 
matrix 
as follows
(3.28)
Note that the vector 
was already computed
so the matrix is completely known.
Based on definition of , , and we know
(3.29)
Because 
and are both linear phase
it is easy to show 
is also linear phase
i.e.
(3.30)
Thus the knowledge of is equivalent to
knowledge of
(3.31)
Defining the 
matrix 
as
(3.32)
we see
(3.33)
Note that the components of are symmetric with
respect to 
, also for perfect reconstruction just one component of is nonzero. Thus the
only way that the perfect reconstruction can hold is that
(3.34)
where 
is an arbitrary
constant. The above condition is equivalent to
(3.35)
where 
is a 
vector defined as
(3.36)
Thus the perfect reconstruction condition can be
cast in the form
(3.37)
Based on (3.33) and (3.35) we define the vector 
as
(3.38)
where
(3.39)
We also define the 
matrix 
as
(3.40)
Clearly
(3.41)
Plugging the above equation in 3.37 we can write the
perfect reconstruction condition in the following way
(3.42)
Defining 
as
(3.43)
we can write (3.42) as
(3.44)
Now we focus on using the remaining degrees of
freedom for shaping the frequency response of as a low-pass filter.
By
defined as
(3.45)
the frequency response of is written as
(3.46)
Consider the frequency response of a low pass filter
Figure 3.2 Stop and pass bands for a
low pass filter
Based on 
and 
shown in this figure,
we define the power of error is pass band an stop band as
(3.47)
(3.48)
Like the last section we can see
(3.49)
(3.50)
where
(3.51)
(3.52)
We define the matrix 
as a linear
combination of 
and 
that is
(3.53)
We recall that 
is a parameter to
trade-off between the error of pass band and the stop band.
The cost function we will use in this case is
(3.54)
and our goal is to minimize this cost function
subject to the constrain (3.44) that is
(3.55)
Using the method of Lagrange multipliers the solution
of this optimization problem will be
(3.56)
Also we determine such that
(3.57)
which results
(3.58)
Finally we obtain using (3.41)
(3.59)
Having and determined, we obtain and as follows
(3.60)
where 
is any positive
integer. With 
we obtain
(3.61)
(3.62)
and the distortion function will be
(3.63)
Based on MATLAB a m-file is
generated to perform all the computations. The source of this file is included
at the end of the report. Using this computer program for the following values
we obtained , , , and .
The resultant impulse responses are given at the end
of the report. Also the frequency response of the filters are illustrated in
figure 3.3
Figure 3.3 Frequency response of FIR
filters
3.2. Discussion
In the last subsection we presented a procedure to design
perfect reconstruction two-channel filter bank. This method can always be used
for designing the filter banks. Also as it can be seen in figure 3.3 the
frequency response of filters approximate the ideal case well, the frequency
response in pass band is almost flat and in stop band the filters have more
than 40 dB attenuation. The disadvantage of this method is that their order is relatively
high that is 
and 
.
4. IIR filter Design
In this section we discuss the possible application
of IIR filters in filter banks, assuming that the condition holds. The main
difficulty of this approach is that although stable and can be easily
designed, it is possible that and obtained by (2.7) and
(2.8) be unstable. One method to overcome the difficulty is to design containing one or more
parameters and then try to find the parameter(s) such that and be stable. In the
remaining of this section we will show the method for a second order IIR .
One method for designing a digital filter is to first design an analog counterpart, then using bilinear transform to obtain the discrete version of that analog filter. The bilinear transform defined by
(4.1)
has the advantage that it maps the inside of unit
circle to the left half of s-plan. This property guarantees that under the bilinear
transformation, a stable analog filter results a stable digital filter.
We use the Butterworth analog filters as the bases of our design. The transfer function for a second order Butterworth filter is
(4.2)
Appling the bilinear
transform to the above analog filter results
(4.3)
Let us define
(4.4)
(4.5)
We obtain from (2.7) and (2.8)
(4.6)
(4.7)
The stability of filters
depends on the location of roots of
(4.8)
At this point we try to find
a proper value forsuch that all roots of 
be located inside the
unit circle. Using a computer program we compute the roots of for different values
of . The resultant root locus is plotted in figure 4.1 Note that
the pole at 
cannot be counted as
an unstable pole, because by proper choice of 
we can cancel it.
Figure 4.1 Root locus of
Clearly for some values of (
), all roots of are inside the unit
circle and filters are stable . On the other hand for 
the filters have to
unstable poles.
For 
, the transfer functions of and are
(4.9)
(4.10)
The frequency response of and for is illustrated in
figure 4.2. Also to make sure that the whole system is perfect reconstruction,
the distortion function 
is shown in figure
4.3.
Figure 4.2 Frequency response of IIR
Filters
Figure 4.3 - Distortion function for
IIR filter bank
4.1. Discussion
In general with equal
degrees, IIR filters can better approximate an ideal filter than FIR filters.
But as it is illustrated by figure 4.2, the frequency response of and are not completely
satisfactory. The reason is the low degree of them. Based of the method we
discussed here, it is not easy to design a high order IIR filter. In other word
the method used here cannot be easily extended to higher order filters. Again
we recall that the main difficulty of using IIR filters in perfect
reconstruction filter banks is the stability of synthesis filters.
5. Two dimensional QMF and image coding
In this section we apply the filters designed in
previous sections to a practical experiment. We are to perform image coding by
taking advantage of sub-band coding so that we can compress images as much as
possible. The idea is that usually most of the energy of images is located in
lower band frequencies. So if we separate the frequency bands, we are able to
designate less number of bits to higher frequency portion of the image. So,
totally we receive less number of bits per pixel.
For applying designed 1-D
filters to 2-D case, we need an extension. As depicted in figure 5.1, we can
divide frequency bands in the two dimensions and perform coding of each band
separately (figure 5.1). We apply 1-D
filters once on rows and next on columns of image.
Figure 5.1 Sub-band Coding of a 2-D
Image
In the following three subsections, we apply three filter banks designed in sections 2, 3 and 4 and see their performances. These filters will be extended to 4-band filter banks in section 6. All simulations were done in Matlab.
5.1. FIR filter with H1(z) = H0(-z)
The filter designed in section 2 was applied to two sample benchmarks (lenna and baboon). Since system is perfect reconstruction, the output of the system is absolutely identical to the original file. (figures 5.1 and 5.3)
The main characteristic of image files is that most of the energy is centralized in lower frequency band. This can be seen from figures 5.2 and 5.4 where different frequency elements of the signal were separated. Also, the energy level of each band is reported in Table 5.1. These all show that we can easily reduce the number of designated bits to higher bands without losing considerable energy. In fact these degradations cannot be detected easily by humans eye. The interesting issue is that this degradation of coding is negligible as compared to quantization error, which is unavoidable.
Figure 5.1 Left: Original Image
(lenna.tiff) scale by 40% , Right: Output of filter designed in section 2
Figure 5.2 Sub-bands of Image shown
in figure 5.1 using filter banks designed in section 2
(all but first one are
gained by 10 to make them more visible)
Figure 5.3 Left: Original Image
(baboon.tiff) scale by 40% , Right: Output of filter designed in section 2
Figure 5.4 Sub-bands of Image shown
in figure 5.3 using filter banks designed in section 2
(all but first one are
gained by 10 to make them more visible)
|
Lenna |
Baboon |
||
|
99.5109% |
0.2941% |
98.0257% |
0.5109% |
|
0.1454% |
0.0496% |
1.1626% |
0.3008% |
Table 5.1 Energy percentage of
different sub-bands divided by filter designed in section 2
5.2. FIR filter with no constraint
In next experiment the filter designed in section three was applied to same images and similar results were received. It shows that since in these images, most of the energy (more than 98%) is in first quarter of frequency spectrum, even if a very simple FIR filter is applied, we can achieve very good performance and high compression result. (figures 5.5 to 5.8 and Table 5.2)
Figure 5.5 - Left: Original Image (lenna.tiff) scale by
40% , Right: Output of FIR filter designed in
section 3
Figure 5.6 Sub-bands of Image shown
in figure 5.5 using FIR filter banks designed in section 3
(all but first one are
gained by 10 to make them more visible)
Figure 5.7 Left: Original Image
(baboon.tiff) scale by 40% , Right: Output of FIR filter designed in section 3
Figure 5.8 Sub-bands of Image shown
in figure 5.7 using FIR filter banks designed in section 3
(all but first one are
gained by 10 to make them more visible)
|
Lenna |
Baboon |
||
|
99.4105 % |
0.1967 % |
98.0630 % |
0.4085 % |
|
0.0991 % |
0.0460 % |
1.1435 % |
0.2725 % |
Table 5.2 Energy percentage of
different sub-bands divided by filter designed in section 3
In figure 5.9 the relation between energy of error signal and number of bits per pixel was shown. As it can be seen, by using less than 1 bit per pixel we can almost get complete performance and error level is almost negligible. Output images stored using only 1.5 bits per pixel can be seen in figure 5.10 which is almost same as original images. Similar results can be achieved from IIR filter which we preferred not to repeat.
Figure 5.9 Energy percentage of the
error signal based on number of bits per pixel
Figure 5.10 Output images coded only
using in average 1.5 pixels per bit
6. The 4-Channel Filter Bank
Based on the design of a 2-channel perfect reconstruction
filter bank, we can design a 4-channel bank with perfect reconstruction
property. Here is the main idea behind this design. Assume that we have applied
the input signal to a 2-channel bank. Now we apply the output of each channel
to the input of another bank with exactly the same design. At this stage we
have four outputs with rate of 
. Let us denote by 
the transfer function
of the new analysis bank then
(6.1)
We can use the same method to determine the transfer functions of synthesis bank
(6.2)
Based on the design of section 3
and using (6.1) and (6.2) we can obtain a high quality, perfect reconstruction,
FIR 4-channel filter bank. The frequency response of the above filters with , , , and obtained in section 3
are illustrated in figure 6.1
Figure 6.1 Frequency response of
4-channel filter bank
Result of the simulation for different filter banks can be seen in the following sub-sections.
6.1. FIR filter with H1(z) = H0(-z)
As shown in figures 6.2 and 6.3 and table 6.1, most of the energy is still in the very lower part of frequency spectrum. So these images can be highly compressed by assigning different number of bits per pixel to each sub-band. The relation between energy level and number of pixels can be found in figure 6.4.
Figure 6.2 Sub-bands of Image using
filter banks designed in section 2
(all but first one are
gained by 10 to make them more visible)
Figure 6.3 Sub-bands of Image using
filter banks designed in section 2
(all but first one are
gained by 10 to make them more visible)
|
Lenna |
Baboon |
||||||
|
98.6316% |
0.2289% |
0.0532% |
0.0382% |
96.5001% |
0.7432% |
0.3234% |
0.4937% |
|
0.5516% |
0.0987% |
0.0223% |
0.0317% |
0.4753% |
0.3071% |
0.1371% |
0.2085% |
|
0.1179% |
0.0236% |
0.0087% |
0.0105% |
0.1194% |
0.0768% |
0.0489% |
0.0645% |
|
0.1112 % |
0.0414% |
0.0117% |
0.0188% |
0.1776% |
0.1371% |
0.0781% |
0.1093% |
Table 6.1 Energy percentage of
different sub-bands divided by filter designed in section 2
6.2. FIR filter with no constraint
The results of simulation can be seen in figures 6.4 and 6.5 and table 6.2. In figure 6.6 you can see images coded with only 1 bit per pixel.
Figure 6.4 Sub-bands of Image using
filter banks designed in section 3
(all but first one are
gained by 10 to make them more visible)
Figure 6.5 Sub-bands of Image using
filter banks designed in section 3
(all but first one are
gained by 10 to make them more visible)
|
Lenna |
Baboon |
||||||
|
98.4035% |
0.1701% |
0.0187% |
0.0438% |
96.3171% |
0.7574% |
0.2053% |
0.5564% |
|
0.4377% |
0.1224% |
0.0064% |
0.0313% |
0.4789% |
0.3047% |
0.1153% |
0.2497% |
|
0.0334% |
0.0100% |
0.0046% |
0.0089% |
0.0509% |
0.0315% |
0.0244% |
0.0468% |
|
0.1126 % |
0.0462% |
0.0084% |
0.0252% |
0.1860% |
0.1230% |
0.0632% |
0.1169% |
Table 6.2 Energy percentage of different
sub-bands divided by filter designed in section 3
Figure 6.6 Output images coded only
using in average 1.0 bit per pixel