Multirate filter bank and multidimensional directional filter banks

Multirate systems

Linear time-invariant systems typically operate at a single sampling rate, which means that we have the same sampling rate at input and output. In other words, in an LTI system, the sampling rate would not change in the system.

Systems that use different sampling rates at different stages are called multirate systems. The multirate system can have different sampling rates based on desire. Also multirate systems can provide different sampling rates without destroy the signal components. In Figure 1, you can see a block diagram of a two channel multirate system.

Multirate Filter Bank

Multirate filter bank divides a signal into a number of subbands, which can be analysed at different rates corresponding to the bandwidth of the frequency bands.
One important fact in multirate filtering is that the signal should be filtered before decimation, otherwise aliasing and frequency folding would occur.

Multirate Filter Designs

Multirate filter design makes use of properties of decimation and interpolation (or expansion) in the design implementation of the filter. Decimation or downsampling by a factor of M essentially means keeping every M t h sample of a given sequence.

Decimation, Interpolation, and Modulation

Generally speaking, using decimation is very common in multirate filter designs. In the second step, after using decimation, interpolation will be used to restore the sampling rate. The advantage of using decimators and interpolator is that they can reduce the computations when resulting in a lower sampling rate.

Decimation by a factor of M can be mathematically defined as: x ( n ) ↓ M = x ( M . n ) or equivalently, X ( z ) ↓ M = 1 M ∑ m = 0 M − 1 X ( z 1 M ) .

Expansion or upsampling by a factor of M means that we insert M-1 zeros between each sample of a given signal or a sequence. The expansion by a factor of M can be mathematically explained as: x ( n ) ↑ M = { x ( n M ) 0 n M o t h e r w i s e
or equivalently, X ( z ) ↑ M = X ( z M ) .

Modulation is needed for different kinds of filter designs. For instance, in many communication applications we need to modulate the signal to baseband. After using lowpass filtering for the baseband signal, we use modulation and change the baseband signal to the center frequency of the bandpass filter. Here we provide two examples of designing multirate narrow lowpass and narrow bandpass filters.

Narrow lowpass filter

We can define a narrow lowpass filter as a lowpass filter with a narrow passband. In order to create a multirate narrow lowpass FIR filter, we need to replace the time invariant FIR filter with a lowpass antialiasing filter and use a decimator along with an interpolator and lowpass anti-imaging filter. In this the resulting way multirate system would be a time varying linear phase filter via the decimator and interpolator. This process explained in block diagram form where Figure 2 (a) is replaced by Figure 2(b).

The lowpass filter consists of two polyphase filters, one for the decimator and one for the interpolator.

Multirate Filter Bank

Filter banks has different usage in many areas, such as signal and image compression, and processing. The main usage of using filter banks is that in this way we can divide the signal or system to several separate frequency domains.

A filter bank divides the input signal x ( n ) into a set of signals x 1 ( n ) , x 2 ( n ) , x 3 ( n ) , . . . . In this way each of the generated signals corresponds to a different region in the spectrum of x ( n ) . In this process it can be possible for the regions overlap (or not, based on application). Figure 4 shows an example of a three-band filter bank. The generated signals x 1 ( n ) , x 2 ( n ) , x 3 ( n ) , . . . can be generated via a collection of set of bandpass filters with bandwidths B W 1 , B W 2 , B W 3 , . . . and center frequencies f c 1 , f c 2 , f c 3 , . . . (respectively).

A multirate filter bank use a single input signal and then produces multiple outputs of the signal by filtering and subsampling. In order to split the input signal into two or more signals (see Figure 5) an analysis-synthesis system can be used . In figure 5, only 4 sub-signals are used.

The signal would split with the help of four filters H k ( z ) for k =0,1,2,3 into 4 bands of the same bandwidths (In the analysis bank) and then each sub-signal is decimated by a factor of 4. In each band by dividing the signal in each band, we would have different signal characteristics.

In synthesis section the filter will reconstruct the original signal: First, upsampling the 4 sub-signals at the output of the processing unit by a factor of 4 and then filtere by 4 synthesis filters F k ( z ) for k = 0,1,2,3. Finally, the outputs of these four filters are added.

Multidimensional Filter Banks

Multidimensional Filtering, downsampling, and upsampling are the main parts of multidimensional multirate systems and filter banks.

A complete filter bank consists of the analysis and synthesis sides. The analysis filter bank divides an input signal to different subbands with different frequency spectra. The synthesis part reassembles the different subband signals and generates a reconstructed signal. Two of the basic building blocks are the decimator and expander.As illustrated in Figure 6, the input gets divided into four directional sub bands that each of them covers one of the wedge-shaped frequency regions. In 1D systems, M-fold decimators keep only those samples that are multiples of M and discard the rest. while in multi-dimensional systems the decimators are D X D nonsingular integer matrix. it considers only those samples that are on the lattice generated by the decimator. Commonly used decimator is the quincunx decimator whose lattice is generated from the Quincunx matrix which is defined by [ 1 1 − 1 1 ] . A quincunx lattice that is generated by this matrix is shown in figure.

It is important to analyze filter banks from a frequency domain perspective in terms of subband decomposition and reconstruction. However, equally important is a Hilbert space interpretation of filter banks, which plays a key role in geometrical signal representations. For a generic K-channel filter bank, with analysis filters { h k [ n ] } k = 1 K , synthesis filters { g k [ n ] } k = 1 K , and sampling matrices { M k [ n ] } k = 1 K . In the analysis side, we can define vectors in l 2 ( Z d ) as
φ k , m [ n ] = d e f h k ∗ [ M k m − n ] , each index by two parameters: 1 ≤ k ≤ K and m ∈ Z 2 .
Similarly, for the synthesis filters g k [ n ] we can define ψ k , m [ n ] = d e f h k ∗ [ M k m − n ] .

Considering the definition of analysis/synthesis sides we can verify that c k [ m ] =< x [ n ] , φ k , m [ n ] >
and for reconstruction part x ^ [ n ] = ∑ 1 ≤ k ≤ K , m ∈ Z 2 c k [ m ] ψ k , m [ n ] .
In other words, the analysis filter bank calculate the inner product of the input signal and the vector from analysis set. Moreover, the reconstructed signal in the combination of the vectors from the synthesis set, and the combination coefficients of the computed inner products, meaning that x ^ [ n ] = ∑ 1 ≤ k ≤ K , m ∈ Z 2 < x [ n ] , φ k , m [ n ] > ψ k , m [ n ]

If there is no loss in the decomposition and the subsequent reconstruction, the filter bank is called perfect reconstruction. (in that case we would have x [ n ] = x [ n ] ^ .

Multidimensional Filter Banks Design

1-D filter banks have been well developed until today. However, many signals, such as image, video, 3D sound, radar, sonar, are multidimensional, and require the design of multidimensional filter banks.

With the fast development of communication technology, signal processing systems need more room to store data during the processing, transmission and reception. In order to reduce the data to be processed, save storage and lower the complexity, multirate sampling techniques were introduced to achieve these goals. Filter banks can be used in various areas, such as image coding, voice coding, radar and so on.

Many 1D filter issues were well studied and researchers proposed many 1D filter bank design approaches. But there are still many multidimensional filter bank design problems that need to be solved.^[6] Some methods may not well reconstruct the signal; some methods are complex and hard to implement.

Design of Separable Filter Bank

The simplest approach to design a multi-dimensional filter banks is to cascade 1D filter banks in the form of a tree structure where the decimation matrix is diagonal and data is processed in each dimension separately. Such systems are referred to as separable systems.

Design of Non-separable Multidimensional FilterBanks

Below are several approaches on the design of multidimensional filter banks.

2-Channel Multidimensional perfect reconstruction (PR) filter banks

In real life, we always want to reconstruct the divided signal back to the original one, which makes PR filter banks very important. Let H(z) be the transfer function of a filter. The size of the filter is defined as the order of corresponding polynomial in every dimension. The symmetry or anti-symmetry of a polynomial determines the linear phase property of the corresponding filter and is related to its size. Like the 1D case, the aliasing term A(z) and transfer function T(z) for a 2 channel filter bank are:

A(z)=1/2(H₀(-z) F₀ (z)+H₁ (-z) F₁ (z)); T(z)=1/2(H₀ (z) F₀ (z)+H₁ (z) F₁ (z)), where H₀ and H₁ are decomposition filters, and F₀ and F₁ are reconstruction filters.

The input signal can be perfectly reconstructed if the alias term is cancelled and T(z) equal to a monomial. So the necessary condition is that T'(z) is generally symmetric and of an odd-by-odd size. Linear phase PR filters are very useful for image processing. This 2-Channel filter bank is relatively easy to implement. But 2 channels sometimes are not enough for use. 2-channel filter banks can be cascaded to generate multi-channel filter banks.

To understand the working of 2-Channel Multidimensional filter banks we must first understand the design process of a simple 2D two-channel filter banks. In particular the diamond filter banks are of special interest in some image coding applications. The decimation matrix M for the diamond filter bank is usually the quincunx matrix which is briefly discussed in the above sections. For a two-channel system, there are only four filters, two analysis filters and two synthesis filters. So in some designs, two or three filters are chosen so that there is no aliasing and the remaining filters are then optimized to achieve approximate reconstruction. Design of 2D filters are more complex than 1D filters. So we usually use appropriate mapping techniques to achieve perfect reconstruction.. A polyphase mapping method is proposed to design an IIR analysis filter. For filter banks with FIR filter types, several 1D to 2D trasformations have been considered. For example, the McClellan transformation is used to achieve the FIR filter banks.

There has also been some interest in quadrant filters as shown. The decimation matrix for a quadrant filter bank is given by D = [ 2 0 0 1 ]

The fan filters are shifted versions of the diamond filters and hence the diamond filter banks are designed and can be shifted by ( π 0 ) in the frequency domain to obtain a fan filter. Filter banks in which the filters have parallelogram support are also of some importance. Several parallelogram supports for analysis and synthesis filters are also shown.These filters can be derived from the diamond filters by using uni-modular transformation.

Tree-structured filter banks

For any given subband analysis filter bank, we can split it into further subbands as shown in figure 8. By repeating this operation we can actually build a tree structured analysis bank. Example of a 1D tree structured filter bank is the one that results in an octave stacking of the passbands. In the 2D case, tree structures based on simple two-channel modules can offer sophisticated band-splitting schemes, especially if we combine the various configurations shown above.The directional filter bank which will be discussed below is one such example.

Multidimensional Directional Filter Banks

M-dimensional directional filter banks (MDFB) are a family of filter banks that can achieve the directional decomposition of arbitrary M-dimensional signals with a simple and efficient tree-structured construction. They have many distinctive properties like: directional decomposition, efficient tree construction, angular resolution and perfect reconstruction. In the general M-dimensional case, the ideal frequency supports of the MDFB are hypercube-based hyperpyramids. The first level of decomposition for MDFB is achieved by an N-channel undecimated filter bank, whose component filters are M-D "hourglass"-shaped filter aligned with the w₁,...,w_M respectively axes. After that, the input signal is further decomposed by a series of 2-D iteratively resampled checkerboard filter banks IRC_li^(Li)(i=2,3,...,M), where IRC_li^(Li)operates on 2-D slices of the input signal represented by the dimension pair (n₁,n_i) and superscript (Li) means the levels of decomposition for the ith level filter bank. Note that, starting from the second level, we attach an IRC filter bank to each output channel from the previous level, and hence the entire filter has a total of 2^{(L₁+...+L_N)} output channels.

Oversampled filter banks are multirate filter banks where the number of output samples at the analysis stage is larger than the number of input samples. It is proposed for robust applications. One particular class of oversampled filter banks is nonsubsampled filter banks without downsampling or upsampling. The perfect reconstruction condition for an oversampled filter bank can be stated as a matrix inverse problem in the polyphase domain.

For IIR oversampled filter banks, perfect reconstruction have been studied in Wolovich and Kailath. in the context of control theory. While for FIR oversampled filter banks we have to use a different strategy for 1-D and M-D, FIR filter are more popular since they are easier to implement. For 1-D oversampled FIR filter banks, the Euclidean algorithm plays a key role in the matrix inverse problem. However, the Euclidean algorithm fails for multidimensional (MD) filters. For MD filter, we can convert the FIR representation into a polynomial representation. and then use Algebraic geometry and Gröbner bases to get the framework and the reconstruction conditions for the multidimensional oversampled filter banks.

Multidimensional Filter Banks Using Grobner Bases

The general multidimensional filter bank (Figure 7) can be represented by a pair of analysis and synthesis polyphase matrices H ( z ) and G ( z ) of size N × M and M × N , where N is the number of channels and M = d e f | M | is the absolute value of the determinant of the sampling matrix. Also H ( z ) and G ( z ) are the z-transform of the polyphase components of the analysis and synthesis filters. Therefore, they are multivariate Laurent polynomials, which have the general form:
F ( z ) = ∑ k ∈ Z d f [ k ] z k = ∑ k ∈ Z d f [ k 1 , . . . , k d ] z 1 k 1 . . . z d k d . Laurent polynomial matrix equation need to be solve to design perfect reconstruction filter banks: G ( z ) H ( z ) = I | M | .
In the multidimentonal case with multivariate polynomials we need to use the theory and algorithms of Grobner bases(developed by Buchberger)

"Grobner bases" can be used to characterizing perfect reconstruction multidimensional filter banks, but it first need to extend from polynomial matrices to Laurent polynomial matrices.

The Grobner basis computation can be considered equivalently as Gaussian elimination for solving the polynomial matrix equation G ( z ) H ( z ) = I | M | . If we have set of polynomial vectors M o d u l e { h 1 ( z ) , . . . , h N ( z ) } = d e f { c 1 ( z ) h 1 ( z ) + . . . + c N ( z ) h N ( z ) } where : c 1 ( z ) , . . . , c N ( z ) are polynomials.
The Module is analogous to the span of a set of vectors in linear algebra. The theory of Grobner bases implies that the Module has a unique reduced Grobner basis for a given order of power products in polynomials.

If we define the Grobner basis as { b 1 ( z ) , . . . , b N ( z ) } , it can be obtained from { h 1 ( z ) , . . . , h N ( z ) } by a finite sequence of reduction (division) steps.

Using reverse engineering, we can compute the basis vectors b i ( z ) in terms of the original vectors h j ( z ) through a K × N transformation matrix W i j ( z ) as
b i ( z ) = ∑ j = 1 N W i j ( z ) h j ( z ) , i = 1 , . . . , K

Mapping-Based Multidimensional Filter Banks

Designing filters with good frequency responses is challenging via Grobner bases approach.
Mapping based design in popularly used to design nonseparable multidimensional filter banks with good frequency responses.
The mapping approaches have certain restrictions on the kind of filters; However, It brings many important advantages, such as efficient implementation via lifting/ladder structures. Here we provide an example of two-channel filter banks in 2D with sampling matrix D 1 = [ 2 0 0 1 ] We would have several possible choices of ideal frequency responses of the channel filter H 0 ( ξ ) and G 0 ( ξ ) . (Note that the other two filters H 1 ( ξ ) and G 1 ( ξ ) are supported on complementary regions.)
All the frequency regions in Figure can be critically sampled by the rectangular lattice spanned by D 1 .

So imagine the filter bank achieves perfect reconstruction with FIR filters. Then from the polyphase domain characterization it follows that the filters H1(z) and G1(z) are completely specified by H0(z) and G0(z), respectively. Therefore, we need to design H0(x) and G0(z) which have desired frequency responses and satisfy the polyphase-domain conditions. H 0 ( z 1 , z 2 ) G 0 ( z 1 , z 2 ) + H 0 ( − z 1 , z 2 ) G 0 ( − z 1 , z 2 ) = 2 There are different mapping technique that can be used to get above result.

Filter Banks Design in the Frequency Domain

If we do not want perfect reconstruction filter banks using FIR filters, the design problem can be simplified by working in frequency domain instead of using FIR filters.
Note that the frequency domain method is not limited to the design of nonsubsampled filter banks (read ).

Directional Filter Banks

Bamberger and Smith proposed a 2D directional filter bank (DFB).

The DFB is efficiently implemented via an l-level tree-structured decomposition that leads to 2 l subbands with wedge-shaped frequency partition (see Figure ).

The original construction of the DFB involves modulating the input signal and using diamond-shaped filters. Moreover, in order to obtain the desired frequency partition, a complicated tree expanding rule has to be followed. As a result, the frequency regions for the resulting subbands do not follow a simple ordering as shown in Figure 9 based on the channel indices.

The first advantage of DFB is that not only it is not a redundant transform but also it offers perfect reconstruction. Another advantage of DFB is its directional-selectivity and efficient structure. This advantage makes DFB an appropriate approach for many signal and image processing usage.

Directional Filter Banks can be developed to higher dimensions. It can be used in 3-D to achieve frequency sectioning. These kinds of filters can be used in selective filtering purposes to record and save signals information and features. Some other advantages of NDFB can be addressed as follow: Directional decomposition, Construction, Angular resolution, Perfect reconstruction, and Small redundancy.

Multidimensional Directional Filter Banks

N-dimensional directional filter banks (NDFB) can be used in capturing signals features and information. There are a number of studies regarding capturing signals information in 2-D(e.g., steerable pyramid, the directional filter bank, 2-D directional wavelets, curvelets, complex wavelets, contourlets, and bandelets).

Conclusion and Application

Filter banks play an important role in different aspects of signal processing these days. They have different usage in many areas, such as signal and image compression, and processing. The main usage of filter banks is that in this way we can divide the signal or system to several separate frequency components. Depending on our purpose we can choose different methods to design the filters. In this page we provide information regarding filter banks, multidimensional filter banks and different methods to design multidimensional filters. Also we talked about MDFB, which is built upon an efficient tree-structured construction, which leads to a low redundancy ratio and refinable angular resolution. By combining the MDFB with a new multiscale pyramid, we can constructed the surfacelet transform, which has potentials in efficiently capturing and representing surface-like singularities in multidimensional signals. MDFB and surfacelet transform have applications in various areas that involve the processing of multidimensional volumetric data, including video processing, seismic image processing, and medical image analysis. Some other advantages of MDFB include: Directional decomposition, Construction, Angular resolution, Perfect reconstruction, and Small redundancy.