Two-dimensional filter

Last updated July 19, 2022

Two dimensional filters have seen substantial development effort due to their importance and high applicability across several domains. In the 2-D case the situation is quite different from the 1-D case, because the multi-dimensional polynomials cannot in general be factored. This means that an arbitrary transfer function cannot generally be manipulated into a form required by a particular implementation. The input-output relationship of a 2-D IIR filter obeys a constant-coefficient linear partial difference equation from which the value of an output sample can be computed using the input samples and previously computed output samples. Because the values of the output samples are fed back, the 2-D filter, like its 1-D counterpart, can be unstable.

Motivation and applications

Due to the rapid development of information science and computing technology, the theory of digital filters design and application has achieved leap-forward development. We encounter a variety of signals in real-life, such as broadcasting signals, television signals, radar signals, mobile phone signals, navigation signals, radio astronomy signal, biomedical signals, control signals, weather signal, seismic signal, mechanical vibration signal, remote sensing and telemetry signals, etc. Most of these signals are analog signals and just a small portion of them are digital signals. The analog signals are continuous function of the independent variables, which can be one-dimensional, two-dimensional or multidimensional. In most cases, the variable of one-dimensional analog signals are time. After the time sampling and discretization of magnitude, such analog signal will become a one-dimensional digital signal. The resulting digital signal can be represented by a discrete sequence. For example, one common signal is voice signal. An example of a two-dimensional signal is an image. A filter is a system that can transform a signal into another signal. Examples of such transformation include smoothing the signal for noise removal, removing frequency components from a signal and amplifying frequency components for signal enhancement. The design and implementation of filter is an important branch in signal analysis and processing technology. Filters also play a main role in signal acquisition, transmission, processing and exchange.

Problem statement & basic concepts

Digital filters

Digital signal filtering is implementing a digital filter. A digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. The input and output signals are all digital signals. This is in contrast to the other major type of electronic filter, the analog filter, which is an electronic circuit operating on a continuous-time analog signal. Actually the basic concept of digital filters and analog filters are the same. The only difference is the types of signals and the methods to filtering. Digital filters can be implemented numerically in software and have the advantages of high processing accuracy, steady system, little volume and light weight. There is no impedance matching in digital filters and digital filters can accomplish some special filtering functions that can’t be accomplished by analog filters. Analog signals can also be processed through digital filters by using Analog to Digital converters.

Two-dimensional digital filters

Two-dimensional filters are used to process two-dimensional digital signals. There is an important difference between the design of 1-D and 2-D digital filter problems. In 1-D case, the design and the implementation of filters can be more easily considered separately. The filter can first be designed and then, through the appropriate manipulations of the transfer function, the coefficients required by a particular network structure can be determined. While in the 2-D case, the design and implementation are more closely related. Since multidimensional polynomials can’t be factored in general. This means that an arbitrary multi-dimensional transfer function can generally not be manipulated into a form required by a particular implementation. If our implementation can realize only factorable transfer functions, our design algorithm must be tailored to design only filters of this class. This has the effect of complicating the design problem and also limiting the number of practical implementations. Digital filters can be categorized into two main types, namely finite impulse response (FIR) and infinite impulse response (IIR). 2-D FIR digital filter is achieved by a non-recursive algorithm structure while 2-D IIR digital filter is achieved by a recursive feedback algorithm structure.^[1]

Existing approaches

Direct form implementations of 2-D IIR filters

An IIR filter may be implemented in direct form by rearranging its difference equation to express one output sample in terms of the input samples and previously computed output samples.^[2] For a first-quadrant filter, the input signal $x\left(n_{1},n_{2}\right)$ and the output signal $y\left(n_{1},n_{2}\right)$ are related by

$y\left(n_{1},n_{2}\right)=\sum _{l_{1}=0}^{L_{1}-1}\sum _{l_{2}=0}^{L_{2}-1}a(l_{1},l_{2})x(n_{1}-l_{1},n_{2}-l_{2})-\sum _{k_{1}=0}^{K_{1}-1}\sum _{k_{2}=0}^{K_{2}-1}b(k_{1},k_{2})y(n_{1}-k_{1},n_{2}-k_{2})$

Since the response of the filter to an impulse $\delta (n_{1},n_{2})$ is by definition the impulse response $h\left(n_{1},n_{2}\right)$ , we can derive the relationship

$h\left(n_{1},n_{2}\right)=a(l_{1},l_{2})-\sum _{k_{1}=0}^{K_{1}-1}\sum _{k_{2}=0}^{K_{2}-1}b(k_{1},k_{2})h(n_{1}-k_{1},n_{2}-k_{2})$

By taking the 2-D z-transform of both sides, we can solve for the system function $H\left(z_{1},z_{2}\right)$ , which is given by

$H_{z}(z_{1},z_{2})={\frac {\sum _{l_{1}=0}^{L_{1}-1}\sum _{l_{2}=0}^{L_{2}-1}a(l_{1},l_{2})z_{1}^{-l_{1}}z_{2}^{-l_{2}}}{\sum _{k_{1}=0}^{K_{1}-1}\sum _{k_{2}=0}^{K_{2}-1}b(k_{1},k_{2})z_{1}^{-k_{1}}z_{2}^{-k_{2}}}}={\frac {A_{z}(z_{1},z_{2})}{B_{z}(z_{1},z_{2})}}$

This ratio may be viewed as resulting from the cascade of two filters, an FIR filter with a system function equal to $A(z_{1},z_{2})$ and an IIR filter with a system function equal to $1/B(z_{1},z_{2})$ , as shown in the figure below.^[3]

Representation for the filter with the system function
H
(
z
1
,
z
2
)
{\displaystyle H(z_{1},z_{2})}
. Adapted from [3]. Figu1.jpg — Representation for the filter with the system function $H(z_{1},z_{2})$ . Adapted from [3].

Parallel implementations of 2-D IIR filters

Another method to build up complicated 2-D IIR filters is by the parallel interconnection of subfilters. In this case, the overall transfer function becomes

$H_{z}^{p}(z_{1},z_{2})=\sum _{i=1}^{N}H_{z}^{(i)}(z_{1},z_{2})$

Using equation

$H_{z}^{(i)}(z_{1},z_{2})={\frac {A_{z}^{(i)}(z_{1},z_{2})}{B_{z}^{(i)}(z_{1},z_{2})}}$

and putting the sum in transfer function over a common denominator, we get the expanded form

$H_{z}^{p}(z_{1},z_{2})={\frac {A_{z}^{p}(z_{1},z_{2})}{B_{z}^{p}(z_{1},z_{2})}}={\frac {\sum _{j=1}^{N}\prod _{i\neq j}A_{z}^{(j)}(z_{1},z_{2})B_{z}^{(i)}(z_{1},z_{2})}{\prod _{i=1}^{N}B_{z}^{(i)}(z_{1},z_{2})}}$

The parallel form cannot be used to implement an arbitrary 2-D rational system function.^[4] Nevertheless, we can synthesize interesting 2-D IIR filters which can be implemented by a parallel architecture. For example, the parallel form may be advantageous when designing a filter with multiple passband. The parallel implementation can also be useful for implementing a 2-D IIR filter whose impulse response is not confined to a single quadrant, such as a symmetric filter.

Parallel interconnection of N simple 2-D IIR filters to form a new 2-D IIR filter. Adapted from [3]. Tp1.jpg — Parallel interconnection of N simple 2-D IIR filters to form a new 2-D IIR filter. Adapted from [3].

Design of 2-D IIR filters with genetic algorithm

Many design techniques for 2-D IIR digital filters have been reported in the literature.^[1]^[2]^[3]^[4] In 2013, genetic algorithm had been successfully used to digital filter design for about a decade.^{[ citation needed ]} Here we present a method for designing 2-D IIR Filters called GA-Based design method.

Initialization

The figure below shows the proposed GA-Based design flow. Filter coefficients are encoded in their CSD number representation. In the population initialization, chromosomes are generated randomly. Each coefficient has the pre-specified wordlength and maximum number of non-zero digits, which can be set to any desired values.^[5]

GA-based Design Flow chart. Adapted from [5]. Tppt.jpg — GA-based Design Flow chart. Adapted from [5].

Genetic operators

Roulette Wheel Selection is used as the reproduction operator. After each crossover operation, the coefficient where the crossover point lies in will be checked upon CSD format. Mutation operation is the simple single bit flip. After mutation, each coefficient in the offspring is checked upon CSD format.

Fitness evaluation and replacement strategy

The fitness evaluation is a two-step process. The first step is to check the stability of each second order section using the stability triangle. Chromosomes failing the check are assigned fitness value 0. Elitist strategy is applied for old generation replacement. After reproduction the best chromosome and the worst chromosome in the offspring are found out. The designed filter has non-separable numerator and separable denominator transfer function.^[6] The number restoration technique is used to ensure that the filter coefficients are represented in the pre-specified CSD format.

Related Research Articles

The bilinear transform is used in digital signal processing and discrete-time control theory to transform continuous-time system representations to discrete-time and vice versa.

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

Linear filters process time-varying input signals to produce output signals, subject to the constraint of linearity. In most cases these linear filters are also time invariant in which case they can be analyzed exactly using LTI system theory revealing their transfer functions in the frequency domain and their impulse responses in the time domain. Real-time implementations of such linear signal processing filters in the time domain are inevitably causal, an additional constraint on their transfer functions. An analog electronic circuit consisting only of linear components will necessarily fall in this category, as will comparable mechanical systems or digital signal processing systems containing only linear elements. Since linear time-invariant filters can be completely characterized by their response to sinusoids of different frequencies, they are sometimes known as frequency filters.

In signal processing, a digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. This is in contrast to the other major type of electronic filter, the analog filter, which is typically an electronic circuit operating on continuous-time analog signals.

A wavelet is a wave-like oscillation with an amplitude that begins at zero, increases or decreases, and then returns to zero one or more times. Wavelets are termed a "brief oscillation". A taxonomy of wavelets has been established, based on the number and direction of its pulses. Wavelets are imbued with specific properties that make them useful for signal processing.

Filter design is the process of designing a signal processing filter that satisfies a set of requirements, some of which may be conflicting. The purpose is to find a realization of the filter that meets each of the requirements to a sufficient degree to make it useful.

In digital signal processing, a quadrature mirror filter is a filter whose magnitude response is the mirror image around $of that of another filter. Together these filters, first introduced by Croisier et al., are known as the Quadrature Mirror Filter pair.$

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely.

Infinite impulse response (IIR) is a property applying to many linear time-invariant systems that are distinguished by having an impulse response $which does not become exactly zero past a certain point, but continues indefinitely. This is in contrast to a finite impulse response (FIR) system in which the impulse response does become exactly zero at times for some finite, thus being of finite duration. Common examples of linear time-invariant systems are most electronic and digital filters. Systems with this property are known as IIR systems or IIR filters .$

In digital signal processing, downsampling, compression, and decimation are terms associated with the process of resampling in a multi-rate digital signal processing system. Both downsampling and decimation can be synonymous with compression, or they can describe an entire process of bandwidth reduction (filtering) and sample-rate reduction. When the process is performed on a sequence of samples of a signal or a continuous function, it produces an approximation of the sequence that would have been obtained by sampling the signal at a lower rate.

In signal processing, a filter bank is an array of bandpass filters that separates the input signal into multiple components, each one carrying a single frequency sub-band of the original signal. One application of a filter bank is a graphic equalizer, which can attenuate the components differently and recombine them into a modified version of the original signal. The process of decomposition performed by the filter bank is called analysis ; the output of analysis is referred to as a subband signal with as many subbands as there are filters in the filter bank. The reconstruction process is called synthesis, meaning reconstitution of a complete signal resulting from the filtering process.

Recursive least squares (RLS) is an adaptive filter algorithm that recursively finds the coefficients that minimize a weighted linear least squares cost function relating to the input signals. This approach is in contrast to other algorithms such as the least mean squares (LMS) that aim to reduce the mean square error. In the derivation of the RLS, the input signals are considered deterministic, while for the LMS and similar algorithm they are considered stochastic. Compared to most of its competitors, the RLS exhibits extremely fast convergence. However, this benefit comes at the cost of high computational complexity.

The Goertzel algorithm is a technique in digital signal processing (DSP) for efficient evaluation of the individual terms of the discrete Fourier transform (DFT). It is useful in certain practical applications, such as recognition of dual-tone multi-frequency signaling (DTMF) tones produced by the push buttons of the keypad of a traditional analog telephone. The algorithm was first described by Gerald Goertzel in 1958.

The lifting scheme is a technique for both designing wavelets and performing the discrete wavelet transform (DWT). In an implementation, it is often worthwhile to merge these steps and design the wavelet filters while performing the wavelet transform. This is then called the second-generation wavelet transform. The technique was introduced by Wim Sweldens.

In signal processing, a digital biquad filter is a second order recursive linear filter, containing two poles and two zeros. "Biquad" is an abbreviation of "biquadratic", which refers to the fact that in the Z domain, its transfer function is the ratio of two quadratic functions:

In signal processing, a filter is a device or process that removes some unwanted components or features from a signal. Filtering is a class of signal processing, the defining feature of filters being the complete or partial suppression of some aspect of the signal. Most often, this means removing some frequencies or frequency bands. However, filters do not exclusively act in the frequency domain; especially in the field of image processing many other targets for filtering exist. Correlations can be removed for certain frequency components and not for others without having to act in the frequency domain. Filters are widely used in electronics and telecommunication, in radio, television, audio recording, radar, control systems, music synthesis, image processing, and computer graphics.

Sonar systems are generally used underwater for range finding and detection. Active sonar emits an acoustic signal, or pulse of sound, into the water. The sound bounces off the target object and returns an “echo” to the sonar transducer. Unlike active sonar, passive sonar does not emit its own signal, which is an advantage for military vessels. But passive sonar cannot measure the range of an object unless it is used in conjunction with other passive listening devices. Multiple passive sonar devices must be used for triangulation of a sound source. No matter whether active sonar or passive sonar, the information included in the reflected signal can not be used without technical signal processing. To extract the useful information from the mixed signal, some steps are taken to transfer the raw acoustic data.

A two-dimensional (2D) adaptive filter is very much like a one-dimensional adaptive filter in that it is a linear system whose parameters are adaptively updated throughout the process, according to some optimization approach. The main difference between 1D and 2D adaptive filters is that the former usually take as inputs signals with respect to time, what implies in causality constraints, while the latter handles signals with 2 dimensions, like x-y coordinates in the space domain, which are usually non-causal. Moreover, just like 1D filters, most 2D adaptive filters are digital filters, because of the complex and iterative nature of the algorithms.

This article provides a short survey of the concepts, principles and applications of Multirate Filter Banks and Multidimensional Directional Filter Banks.

In signal processing, multidimensional discrete convolution refers to the mathematical operation between two functions f and g on an n-dimensional lattice that produces a third function, also of n-dimensions. Multidimensional discrete convolution is the discrete analog of the multidimensional convolution of functions on Euclidean space. It is also a special case of convolution on groups when the group is the group of n-tuples of integers.

References

1 2 T. S. Huang, “Stability of two-dimensional recursive filters,” IEEE Transactions on Audio and Electroacoustics, vol. 20, no. 2, pp. 158–163, 1972.
1 2 J. S. Lim, Two-Dimensional Signal and Image Processing, Prentice-Hall International, 1990.
1 2 Dan E. Dudgeon, Russell M. Mersereau, “Multidimensional Digital Signal Processing”, Prentice-Hall Signal Processing Series, ISBN 0136049591, 1983.
1 2 M. Ahmadi, “Design of 2-Dimensional recursive digital filters”, Control and Dynamics System, vol. 78, pp. 131-181, 1996.
↑ Li Liang, Majid Ahmadi, Maher Sid-Ahmed, “Design of 2-D IIR FIlters with Canonical signed-digit coefficients using genetic algorithm”, Department of Electrical & Computer Engineering, University of Windsor, Canada.
↑ A. Mazinani, M. Ahmadi, M. Shridhar and R. S. Lashkari, “A novel approach to the design of 2-D recursive digital filters”, Journal of the Franklin Institute, Pergamon Press Ltd, vol. 329, no. 1, pp. 127-133, 1992.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 T. S. Huang, “Stability of two-dimensional recursive filters,” IEEE Transactions on Audio and Electroacoustics, vol. 20, no. 2, pp. 158–163, 1972.

[:1-2] 1 2 J. S. Lim, Two-Dimensional Signal and Image Processing, Prentice-Hall International, 1990.

[:2-3] 1 2 Dan E. Dudgeon, Russell M. Mersereau, “Multidimensional Digital Signal Processing”, Prentice-Hall Signal Processing Series, ISBN 0136049591, 1983.

[:3-4] 1 2 M. Ahmadi, “Design of 2-Dimensional recursive digital filters”, Control and Dynamics System, vol. 78, pp. 131-181, 1996.

[5] Li Liang, Majid Ahmadi, Maher Sid-Ahmed, “Design of 2-D IIR FIlters with Canonical signed-digit coefficients using genetic algorithm”, Department of Electrical & Computer Engineering, University of Windsor, Canada.

[6] A. Mazinani, M. Ahmadi, M. Shridhar and R. S. Lashkari, “A novel approach to the design of 2-D recursive digital filters”, Journal of the Franklin Institute, Pergamon Press Ltd, vol. 329, no. 1, pp. 127-133, 1992.

[1]

[2]

[3]

[4]

[5]

[6]