Many concepts in one–dimensional signal processing are similar to concepts in multidimensional signal processing. However, many familiar one–dimensional procedures do not readily generalize to the multidimensional case and some important issues associated with multidimensional signals and systems do not appear in the one–dimensional special case.
Contents
- Motivation and applications
- Problem statement and basic concepts
- Direct convolution
- Discrete Fourier transform implementations of FIR filters
- Block convolution
- Minimax design of FIR filters
- Design using transformation
- Implementation of filters designed using transformations
- Trigonometric sum of squares optimization
- Iterative implementation for M D IIR filters
- Existing approaches for IIR filter design
- Shanks method
- Frequency domain designs for IIR
- Magnitude and magnitude squared design algorithm
- Magnitude design with stability constraint
- Design and implementation of M D zero phase IIR filters
- Implementation of Mixed Multidimensional Filters
- Using discrete Fourier transform DFT
- Using discrete cosine transform DCT
- Using discrete Hartley transform DHT
- Applications of MixeD Multidimensional Filters
- Review of 3 D Spatially Planar Signals
- Design of a 3 D MixeD cone filter using 2 D DHT
- References
Motivation and applications
Most of the signals we witness in real life exist in more than one dimension, be they image, video or sound among many others. A multidimensional (M-D) signal can be modeled as a function of
A multidimensional (M-D) signal can be modeled as a function of
Filtering is an application that is performed on signals whenever certain frequencies are to be removed so as to suppress interfering signals and reduce background noise. A mixed filter is a kind of filter that is different from the traditional Finite Impulse Response(FIR) and Infinite impulse response(IIR) filters and these three filters are explained here in detail. We can combine the M-D Discrete Fourier transform(DFT) method and the M-D linear difference equation(LDE) method to filter the M-D signals. This results in the so-called combined DFT/LDE filtering technique in which the Discrete Fourier Transform is performed in some of the dimensions prior to Linear Difference Equation filtering which is performed later in the remaining dimensions. Such kind of filtering of M-D signals is referred to as Mixed domain(MixeD) filtering and the filters that perform such kind of filtering are referred to as MixeD Multidimensional Filters.
Combining Discrete Transforms with Linear Difference Equations for implementing the Multidimensional filters proves to be computationally efficient and straightforward to design with low memory requirements for spatio-temporal applications such as video processing. Also the Linear Difference equations of the MixeD filters are of lower dimensionality as compared to normal multidimensional filters which results in simplification of the design and increase in the stability.
Multidimensional Digital filters are finding applications in many fields such as image processing, video processing, seismic tomography, magnetic data processing, Computed tomography (CT), RADAR, Sonar and many more. There is a difference between 1-D and M-D digital filter design problems. In the 1-D case, the filter design and filter implementation issues are distinct and decoupled. The 1-D filter can first be designed and then particular network structure can be determined through the appropriate manipulation of the transfer function. In the case of M-D filter design, the multidimensional polynomials cannot be factored in general. This means that an arbitrary transfer function can generally not be manipulated into a form required by a particular implementation. This makes the design and implementation of M-D filters more complex than the 1-D filters.
Problem statement and basic concepts
Multidimensional filters not unlike their one dimensional counterparts can be categorized as
In order to understand these concepts,it is necessary to understand what an impulse response means.An impulse response is basically the response of the system when the input to that system is a Unit impulse function.An impulse response in the spatial domain can be represented as
A Finite Impulse Response (FIR), or non-recursive filter has an impulse response with a finite number of non-zero samples. This makes their impulse response always absolutely summable and thus FIR filters are always stable.
The above difference equation can be represented in the Z-domain as follows
where
The transfer function
In the case of FIR filters the transfer function consists of only numerator terms as the denominator is unity due to the absence of feedback.
An Infinite Impulse Response (IIR), or recursive filter (due to feedback) has infinite-extent impulse response. Its input and output satisfy a multidimensional difference equation of finite order. IIR filters may or may not be stable and in many cases are less complex to realize when compared to FIR filters. The promise of IIR filters is a potential reduction in computation compared to FIR filters when performing comparable filtering operations. by, feeding back output samples, we can use a filter with fewer coefficients (hence less computations) to implement a desired operation. On the other hand, IIR filters pose some potentially significant implementation and stabilization problems not encountered with FIR filters. The design of an M-D recursive filter is quite different from the design of a 1-D filter which is due to the increased difficulty of assuring stability. For a
The transfer function in this case will have both numerator and denominator terms due to the presence of feedback.
Although multidimensional difference equations represent a generalization of 1-D difference equations, they are considerably more complex and quite different. A number of important issues associated with multidimensional difference equations, such as the direction of recursion and the ordering relation, are really not an issue in the 1-D case. Other issues such as stability, although present in the 1-D case, are far more difficult to understand for multidimensional systems
Multidimensional(M-D) filtering may also be achieved by carrying out the P-dimensional Discrete Fourier transform (DFT) over P of the dimensions where (P<M) and spatio-temporal (M - P) dimensional Linear Difference Equation (LDE) filtering over the remaining dimensions. This is referred to as the combined DFT/LDE method. Such an implementation is referred to as mixed filter implementation. Instead of using Discrete Fourier Transform(DFT), other transforms such as Discrete Cosine Transform(DCT) and Discrete Hartley Transform(DHT) can also be used, depending on the application. The Discrete Cosine Transform(DCT) is often preferred for the transform coding of images because of its superior energy-compaction property while Discrete Hartley Transform(DHT) is useful when a real-valued sequence is to be mapped onto a real-valued spectrum.
In general, the M-D Linear Difference Equation (LDE) filter method convolves a real M-D input sequence x(n(M)) with a M-D unit impulse sequence h(n(M))to obtain a desired M-D output sequence y(n(M)).
y(n(M)) = x(n(M))
where
If a sequence is zero for some i and for all
The MixeD filter method requires that the M-D input sequence be duration bounded in P of the M dimensions. The index (n(M)) is then ordered so that
The three step process can be summarized as follows,
Step 1. X(k(P),n(M-P)) = F(k(P))[
Step 2. Y(k(P),n(M-P)) = X(k(P),n(M-P))
Step 3.
The crucial step in the MixeD filter design is the 2nd step. This is because filtering takes place in this step. Since there is no filtering involved in Steps 1 and 3, there is no need to weigh the transform coefficients.
The block diagram which shows the MixeD filter method can be seen below.
Direct convolution
Output of any Linear Shift Invariant (LSI) filter can be determined from its input by means of the convolution sum. There are a finite number of non-zero samples and the limits of summation are finite for a FIR filter. The convolution sum serves as an algorithm that enables us to compute the successive output samples of the filter. As an example, let is assume that the filter has support over the region {(
If all input samples are available, the output samples can be computed in any order or can also be computed simultaneously. However, if only selected samples of the output are desired, only those samples need to be computed. The number of multiplications and additions for one desired output sample is (
For the 2D case, the computation of
Using the above equation to implement an FIR filter requires roughly one-half the number of multiplications of an implementation, although both implementations require the same number of additions and the same amount of storage. If the impulse response of an FIR filter possess other symmetries, they can be exploited in a similar fashion to reduce further the number of required multiplications.
Discrete Fourier transform implementations of FIR filters
The FIR filter can also be implemented by means of the Discrete Fourier transform (DFT). This can be particularly appealing for high-order filters because the various Fast Fourier transform algorithms permit the efficient evaluation of the DFT. The general form of DFT for multidimensional signals can be seen below, where
Let
On computing Fourier Transform of both sides of this expression, we get
There are many possible definitions of the M-D discrete Fourier transform, and that all of these correspond to sets of samples of the M-D Fourier transform; these DFT's can be used to perform convolutions as long their assumed region of support contains the support for
Therefore,
To compute (
For the 2D case, and assuming that
Block convolution
The arithmetic complexity of the DFT implementation of an FIR filter is effectively independent of the order of the filter, while the complexity of a direct convolution implementation is proportional to the filter order. So, the convolution implementation would be more efficient for the lower filter order. As, the filter order increases, the DFT implementation would eventually become more efficient.
The problem with the DFT implementation is that it requires a large storage. The block convolution method offers a compromise. With these approaches the convolutions are performed on sections or blocks of data using DFT methods. Limiting the size of these blocks limits the amount of storage required and using transform methods maintains the efficiency of the procedure.
The simplest block convolution method is called the overlap-add technique. We begin by partitioning 2-D array,
The regions of support for the different sections do not overlap, and collectively they cover the entire region of support of the array
Because the operation of discrete convolution distributes with respect to addition,
Figure (a) shows the section of the input array
The block output
The convolutions of the
The overlap-save method is an alternative block convolution technique. When the block size is considerably larger than the support of
The figure above shows the overlap-save method. The shaded region gives those samples of
For both the overlap-add and overlap-save procedures, the choice of block size affects the efficiency of the resulting implementation. It affects the amount of storage needed, and also affects the amount of computation.
Minimax design of FIR filters
The frequency response of a multi-dimensional filter is given by,
where
The frequency response of the ideal filter is given by
where
The error measure is given by subtracting the above two results i.e.
The maximum of this error measure is what needs to be minimized.There are different norms available for minimizing the error namely:
if p =2 we get the
When we say minimax design the
Design using transformation
Another method to design a multidimensional FIR filter is by the transformation from 1-D filters. This method was first developed by McClellan as other methods were time consuming and cumbersome. The first successful implementation was achieved by Mecklenbrauker and Mersereau and was later revised by McClellan and Chan. For a zero phase filter the one phase impulse response is given by
where
Let
where
The variable is
Thus
If we consider
The contours and the symmetry of
The values of
The conditions for choosing the mapping function are
Considering a two dimensional case to compute the size of
The main advantages of this method are
Implementation of filters designed using transformations
Methods such as Convolution or implementation using the DFT can be used for the implementation of FIR filters. However, for filters of moderate order another method can be used which justifies the design using transformation.Consider the equation for a 2-dimensional case,
where,
Using this we can form a digital network to realize the 2-D frequency response as shown in the figure below.Replacing x by
Since each of these signals can be generated from two lower order signals, a ladder network of N outputs can be formed such that frequency response between the input and nth output is
This realization is as shown in the figure below.
In the figure,the filters F define the transformation function and h(n) is the impulse response of the 1-D prototype filter .
Trigonometric sum-of-squares optimization
Here we discuss a method for multidimensional FIR filter design via sum-of-squares formulations of spectral mask constraints. The sum-of-squares optimization problem is expressed as a semidefinite program with low-rank structure, by sampling the constraints using discrete sine and cosine transforms. The resulting semidefinite program is then solved by a customized primal-dual interior-point method that exploits low-rank structure. This leads to substantial reduction in the computational complexity, compared to general-purpose semidefinite programming methods that exploit sparsity.
A variety of one-dimensional FIR filter design problems can be expressed as convex optimization problems over real trigonometric polynomials, subject to spectral mask constraints. These optimization problems can be formulated as semidefinite programs (SDPs) using classical sum-of-squares (SOS) characterizations of nonnegative polynomials, and solved efficiently via interior-point methods for semidefinite programming.
For the figure above, FIR filter in frequency domain with d=2; n1=n2=5 and has 61 sampling points. The extension of these techniques to multidimensional filter design poses several difficulties. First, SOS characterization of multivariate positive trigonometric polynomials may require factors of arbitrarily high degree. Second, difficulty stems from the large size of the semidefinite programming problems obtained from multivariate SOS programs. Most recent research on exploiting structure in semidefinite programming has focused on exploiting sparsity of the coefficient matrices. This technique is very useful for SDPs derived from SOS programs and are included in several general purpose semidefinite programming packages.
Let
The above summation is over all integer vectors
2-D FIR Filter Design as SOS Program:
We want to determine the filter coefficients
where the scalar
If the passband and stopband are defined, then we can replace each positive polynomial
Iterative implementation for M-D IIR filters
In some applications, where access to all values of signal is available (i.e. where entire signal is stored in memory and is available for processing), the concept of "feedback" can be realized. The iterative approach uses the previous output as feedback to generate successively better approximations to the desired output signal.
In general, the IIR frequency response can be expressed as
where
Now, let
where
In the signal domain, the equation becomes
After making an initial guess, and then substituting the guess in the above equation iteratively, a better approximation of
where
In the frequency domain, the above equation becomes
An IIR filter is BIBO stable if
If we assume that
Thus, it can be said that, the frequency response
To be practical, an iterative IIR filter should require fewer computations, counting all iterations to achieve an acceptable error, compared to an FIR filter with similar performance.
Existing approaches for IIR filter design
Similar to its 1-D special case, M-D IIR filters can have dramatically lower order than FIR filters with similar performance. This motivates the development of design techniques for M-D IIR filtering algorithms. This section presents brief overview of approaches for designing M-D IIR filters.
Shank's method
This technique is based on minimizing the error functionals in the space domain. The coefficient arrays
Let us denote the error signal as
And let
By multiplying both sides by
The total mean-squared error is obtained as
Let the input signal be
Substituting the result
Now, taking the double summation for the region "R" i.e. for
The coefficients
The major advantage of Shank's method is that IIR filter coefficients can be obtained by solving linear equations. The disadvantage is that the mean squared error between
Frequency-domain designs for IIR
Shank's method is a spatial-domain design method. It is also possible to design IIR filters in the frequency domain. Here our aim would be to minimize the error in the frequency domain and not the spatial domain.Due to Parseval's theorem we observe that the mean squared error will be identical to that in the spatial domain.Parseval's theorem states that
Also the different norms that are used for FIR filter design such as
is the required equation for the
The main advantages of design in the frequency domain are
The main disadvantage of this technique is that there is no guarantee for stability.
General minimization techniques as seen in the design of IIR filters in the spatial domain can be used in the frequency domain too.
One popular method for frequency domain design is the Magnitude and magnitude squared algorithms.
Magnitude and magnitude squared design algorithm
In this section, we examine the technique for designing 2-D IIR filters based on minimizing error functionals in the frequency domain. The mean-squared error is given as
The below function
where
The disadvantages of this method are,
Magnitude design with stability constraint
This design procedure includes a stability error
The minimum phase array can be determined by first computing the autocorrelation function of the denominator coefficient array
After computing
We form the cepstrum
The subscript "mp" denotes that this cepstrum corresponds to a minimum phase sequence
If the designed filter is stable, its denominator coefficient array
In practice,
Design and implementation of M-D zero-phase IIR filters
Often, especially in applications such as image processing, one may be required to design a filter with symmetric impulse response. Such filters will have a real-valued, or zero-phase, frequency response. Zero-phase IIR filter could be implemented in two ways, cascade or parallel.
In the cascade approach, a filter whose impulse response is
The cascade approach suffers from some computational problems due to transient effects. The output samples of the second filter in the cascade are computed by a recursion which runs in the opposite direction from that of the first filter. For an IIR filter, its output has infinite extent, and theoretically an infinite number of its output samples must be evaluated before filtering with the
In the parallel approach, the outputs of two non symmetric half-plane (OR four non-symmetric quarter-plane) IIR filters are added to form the final output signal. As in the cascade approach, the second filter is a space-reserved version of the first. The overall frequency response is given by,
This approach avoids the problems of the cascade approach for zero-phase implementation. But, this approach is best suited for the 2-D IIR filters designed in the space domain, where the desired filter response
For a symmetric zero-phase 2-D IIR filter, the denominator has a real positive frequency response.
For 2-D zero-phase IIR filter, since
We can write,
We can formulate the mean-squared error functional that could be minimized by various techniques. The result of the minimization would yield the zero-phase filter coefficients
Implementation of Mixed Multidimensional Filters
If the M-D transform transfer function, H(n(M)) = Y(n(M))/X(n(M)) for a particular class of inputs x(n(M)) and a particular transform is known, the design approximation problem becomes simple and we then have to find the (M-P) dimensional LDE's, one for each P-tuple that help in approximating all the complex (M-P) dimensional transform transfer functions, H(k(P),k(M-P)). But as the multidimensional approximation theory for dimensions greater than 2 is not well developed, the (M-P) dimensional approximation maybe a problem. The input and output sequences of each (M-P) dimensional LDE are complex and are given by X(k(P),k(M-P)) and Y(k(P),k(M-P)) respectively. The main design objective is to choose coefficients of the LDE in such a way that the complex (M-P) dimensional transform transfer function of the sequences X(k(P),k(M-P)) and Y(k(P),k(M-P)), are approximately in the ratio of H(k(P),k(M-P)) = H(n(M)). This can be very difficult unless certain transforms such as DFT, DCT and DHT are used. For the above-mentioned transforms, it is possible to find the (M-P) dimensional impulse response, h(k(P),n(M-P)) by approximating the Linear Difference Equations.
The following approaches can be used to implement Mixed Multidimensional filters:
Using discrete Fourier transform (DFT)
For a multidimensional array
F(k(P)) =
where
F(k(P)) =
where the division
To find the P-Dimensional inverse Discrete Fourier Transform, we can use the following:
F−1(k(P)) =
The Discrete Fourier Transform is useful for certain applications such as Data Compression, Spectral Analysis, Polynomial Multiplication, etc. The DFT is also used as a building block for techniques that take advantage of properties of signals frequency-domain representation, such as the overlap-save and overlap-add fast convolution algorithms. However the computational complexity increases if Discrete Fourier Transform is used as the Discrete Transform. The computational complexity of the DFT is way higher than the other Discrete Transforms and for P-D DFT, the computational complexity is given by O(
Using discrete cosine transform (DCT)
For a multidimensional array
F(k(P))
The P-Dimensional inverse Discrete Cosine Transform is given by:
F−1(k(P))
The DCT finds its use in data compression applications such as the JPEG image format. The DCT has high degree of spectral compaction at a qualitative level, which makes it very suitable for various compression applications. A signal's DCT representation tends to have more of its energy concentrated in a small number of coefficients when compared to other transforms like the DFT. Thus you can reduce your data storage requirement by only storing the DCT outputs that contain significant amounts of energy. The computational complexity of P-D DCT goes by O(
Using discrete Hartley transform (DHT)
For a multidimensional array
F(k(P))
It should also be noted that, if Discrete Hartley Transform is used, the computational complexity of complex numbers can be avoided. The overall computational complexity of P-D Discrete Hartley Transform is given by O(
The Discrete Hartley Transform is used in various applications in communications and signal processing areas. Some of these applications include multidimensional filtering, multidimensional spectral analysis, error control coding, adaptive digital filters, image processing etc.
Applications of MixeD Multidimensional Filters
Mixed 3-D filters can be used for enhancement of 3-D spatially planar signals. A 3-D MixeD Cone filter can be designed using 2-D DHT and is shown below.
Review of 3-D Spatially Planar Signals
An M-D signal, x(n(M)) is considered to be spatially-planar(SP) if it is constant on all surfaces, i.e.
Therefore, a 3-D spatially planar signal, x(n(3)) is constant on 3 surfaces and is given by
It may been shown that the 3-D DFT of a SP x(n(M)) yields 3-D DFT frequency domain coefficients, X(k(3)), which are zero everywhere except on the line L(k(3)) where (k(3))
A 3-D signal input sequence will be selectively enhanced by a 3-D passband enclosing this line. Thus we make use of a cone filter having a thin pyramidal shaped passband which is approximated using Mixed filter constructed using 2-D DHT.
Design of a 3-D MixeD cone filter using 2-D DHT
Firstly, we have to select the passband regions on {k1,k2}. The close examination of DFT and DHT, shows that the 3-D DHT of
Secondly, we have to find the characteristics of the LDE Input sequences
Now, using the shift property of 2-D DHT, we get,
v = 2(