2D adaptive filters

Last updated June 15, 2022

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.

Motivation

The topic of 2D adaptive filters is very important in electrical engineering and signal processing since these filters have the ability to take into account the nonstationary statistical properties of 2D signals. Adaptive filters find applications in areas such as Noise cancellation, Signal prediction, Equalization and Echo cancellation. Examples of applications of 2D adaptive filters include Image Denoising,^[1] Motion Tracking,^[2] OFDM channel estimation,^[3] magnetic recording equalization ^[4]

Example Application

2D Adaptive Filters can be used to identify systems. The system function of the unknown system is given by $P(z_{1},z_{2})$ , and $H(z_{1},z_{2})$ is the system function of the 2D adaptive filter when its output comes to steady. The error signal $e(n_{1},n_{2})$ between the unknown system output, $d(n_{1},n_{2})$ , and the adaptive filter output, $y(n_{1},n_{2})$ , is minimized if the unknown system and known 2D adaptive filter have the same input, and if the resulting outputs are similar. Then, it can be shown that $P(z_{1},z_{2})$ can be represented by $H(z_{1},z_{2})$ . $H(z_{1},z_{2})$ is known as the system identification model of the unknown system.

Problem Statement

General Block Diagram for a 2D Adaptive Filter. Adaptivefilter1.png — General Block Diagram for a 2D Adaptive Filter.

In digital signal processing, any linear shift invariant system can be represented by the convolution of the signal with the filter's impulse response, given by the expression:

$y(n_{1},n_{2})=\sum _{m_{1}}\sum _{m_{2}}w(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})$

If this system is to model a desired response $d(n_{1},n_{2})$ , the adaptive system can be obtained by continuously adjusting the weight values according to some cost function $F[e(n_{1},n_{2})]$ that evaluates the error between the two responses.

$e(n_{1},n_{2})=d(n_{1},n_{2})-y(n_{1},n_{2})$
$w_{j+1}(n_{1},n_{2})=w_{j}(n_{1},n_{2})+F[e(n_{1},n_{2})]$

Approaches

2D Least Mean Square FIR Adaptive Filters

Least mean square (LMS) Adaptive Filters^[5] use the most common error measure method, the mean square error. The 2D LMS Adaptive filters are derived from the 1D LMS adaptive filters main method which minimizes the output mean square value by adjusting coefficients of the filter. The filter has the primary 2D input signal d and the reference input signal x. The primary input signal d consists of the ideal signal and noise component. The filter is an N by N causal FIR filter with impulse response $w$ . Then we can get the filter output given by

$y(n_{1},n_{2})=\sum _{m_{1}=0}^{N-1}\sum _{m_{2}=0}^{N-1}w_{j}(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})$

where j is the iteration number for adaptive filters.

The error signal $e_{j}$ at the j-th iteration is defined as

$e_{j}=d(n_{1},n_{2})-\sum _{m_{1}=0}^{N-1}\sum _{m_{2}=0}^{N-1}w_{j}(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})$

The weight matrix at the next iteration is equal to the present weight matrix plus a change proportional to the negative gradient of the mean square error. For the two-dimensional LMS adaptive filter, the filter coefficients are updated as follows:

$w_{j+1}(n_{1},n_{2})=w_{j}(n_{1},n_{2})+2\mu e_{j}x(n_{1},n_{2})$

where $\mu$ is the scaler multiplier controlling which can control the rate of convergence and filter stability.

Advantages: The TDLMS adaptive filter can be implemented without any form of matrix operations or any averaging or differentiation. The algorithm convergence does not depend on the initial conditions and it will converge for any arbitrarily initial value, hence, it provides good performance in nonstationary images.

Disadvantages: The exact values of the expectations of the TDLMS adaptive filter will not converges to a fixed value, if we need to maintain its tracking ability. Therefore, the design choice of μ depends on the particular application and it involves a tradeoff between the convergence speed, tracking ability, and steady-state MSE.

2D Least Mean Square IIR Adaptive Filters

For a two-dimensional LMS IIR Adaptive filter, its basic idea is the same as 2D LMS FIR Adaptive Filters, except we are using an IIR filter, which can reduce the filter order requirements.^[6] The two-dimensional IIR filter`s difference equation can be written as

$y(n_{1},n_{2})=\sum _{m_{1}=0}^{M_{1}}\sum _{m_{2}=0}^{M_{2}}a(m_{1},m_{2})x(n_{1}-m_{1},n_{2}-m_{2})-{\sum _{m_{1}=0}^{L_{1}}\sum _{m_{2}=0}^{L_{2}}}_{(m_{1},m_{2})\neq (0,0)}b(m_{1},m_{2})y(n_{1}-m_{1},n_{2}-m_{2})$

where $y(n_{1},n_{2})$ and $x(n_{1},n_{2})$ are, respectively, the output and input of the adaptive filter. $b(m_{1},m_{2})$ and $a(m_{1},m_{2})$ are the masks of the filter`s input and output. The error signal is given by

$e(n_{1},n_{2})=d(n_{1},n_{2})-y(n_{1},n_{2})$

where $d(n_{1},n_{2})$ is the primary output signal.

The mean square error $E\{e^{2}(n_{1},n_{2})\}$ is minimized by updating the filter weights in a manner to converge to the optimum filter weight.

Advantages: IIR filters can satisfy the prescribed frequency response because it can reduce the filter`s order requirements.

Disadvantages: The performance surfaces of adaptive LMS IIR Adaptive filters are nonquadratic and may have local minima. Meanwhile, adaptive IIR filters may become unstable during the adaptation, thus some kind of stability monitoring is needed.

Recursive least square adaptive filters

2D Recursive Least Square Adaptive Filters^[7] can be developed by applying 1D recursive least squares filters along both horizontal and vertical directions. The RLS adaptive is an algorithm which finds the filter coefficients recursively to minimize the weighted least squares cost function. The RLS algorithm is different to the least mean squares algorithm which aim to reduce the mean square error, its input signal is considered deterministic. For this reason, the RLS algorithm has fast convergence characteristic.

Advantages: The RLS algorithm has fast convergence property. The accuracy of image denoising based on RLS algorithm is better than 2D LMS adaptive filters.

Disadvantages: The RLS algorithm needs a large amount of computations, especially in two-dimensional and multidimensional case.

Lexicographic Ordering

One convenient approach to implement 2D Adaptive Filters is to transform the 2D problem into a 1D problem by lexicographic ordering.^[5] This simplifies the implementation and makes it possible to benefit from the extensive literature that is available for 1D adaptive filters and utilize all of the existing 1D algorithms.

McClellan Transformations

McClellan transformations^[8] can be used to transform a 1D filter design into a 2D filter design by using a transformation function. This theory allows the design of 2D adaptive filters ^[9] out of existing 1D prototype filters. Compared to the direct approach, this system has the advantages of a lower computational complexity and a faster convergence rate. However, in order to work properly, it needs some a priori information about the system to correctly select the transformation function parameters, making the system pre-constrained.

Block Diagonal 2D Adaptive Filters

Block Diagonal 2D Adaptive Filters is an alternative approach ^[10] that scans the signal through blocks and applies weight adjustments for each block, instead of for each sample as in the traditional adaptive filters. The advantage of this kind of system is that it takes into account signal correlations along both dimensions. On the other hand, it assumes a higher local stationarity of the signal.

Related Research Articles

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.

An adaptive filter is a system with a linear filter that has a transfer function controlled by variable parameters and a means to adjust those parameters according to an optimization algorithm. Because of the complexity of the optimization algorithms, almost all adaptive filters are digital filters. Adaptive filters are required for some applications because some parameters of the desired processing operation are not known in advance or are changing. The closed loop adaptive filter uses feedback in the form of an error signal to refine its transfer function.

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 signal processing, specifically control theory, bounded-input, bounded-output (BIBO) stability is a form of stability for signals and systems that take inputs. If a system is BIBO stable, then the output will be bounded for every input to the system that is bounded.

In signal processing, the Wiener filter is a filter used to produce an estimate of a desired or target random process by linear time-invariant (LTI) filtering of an observed noisy process, assuming known stationary signal and noise spectra, and additive noise. The Wiener filter minimizes the mean square error between the estimated random process and the desired process.

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.

Least mean squares (LMS) algorithms are a class of adaptive filter used to mimic a desired filter by finding the filter coefficients that relate to producing the least mean square of the error signal. It is a stochastic gradient descent method in that the filter is only adapted based on the error at the current time. It was invented in 1960 by Stanford University professor Bernard Widrow and his first Ph.D. student, Ted Hoff.

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 cerebellar model arithmetic computer (CMAC) is a type of neural network based on a model of the mammalian cerebellum. It is also known as the cerebellar model articulation controller. It is a type of associative memory.

ADALINE is an early single-layer artificial neural network and the name of the physical device that implemented this network. The network uses memistors. It was developed by Professor Bernard Widrow and his doctorate student Ted Hoff at Stanford University in 1960. It is based on the McCulloch–Pitts neuron. It consists of a weight, a bias and a summation function.

Mean shift is a non-parametric feature-space mathematical analysis technique for locating the maxima of a density function, a so-called mode-seeking algorithm. Application domains include cluster analysis in computer vision and image processing.

The Least mean squares filter solution converges to the Wiener filter solution, assuming that the unknown system is LTI and the noise is stationary. Both filters can be used to identify the impulse response of an unknown system, knowing only the original input signal and the output of the unknown system. By relaxing the error criterion to reduce current sample error instead of minimizing the total error over all of n, the LMS algorithm can be derived from the Wiener filter.

In computer science, online machine learning is a method of machine learning in which data becomes available in a sequential order and is used to update the best predictor for future data at each step, as opposed to batch learning techniques which generate the best predictor by learning on the entire training data set at once. Online learning is a common technique used in areas of machine learning where it is computationally infeasible to train over the entire dataset, requiring the need of out-of-core algorithms. It is also used in situations where it is necessary for the algorithm to dynamically adapt to new patterns in the data, or when the data itself is generated as a function of time, e.g., stock price prediction. Online learning algorithms may be prone to catastrophic interference, a problem that can be addressed by incremental learning approaches.

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.

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.

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

Digital signal processing (DSP) is a ubiquitous methodology in scientific and engineering computations. In practice, DSP problems are often not only one dimensional. For instance, image data is a 2-D signal and radar is a 3-D signal. While the number of dimensions increases, the time and/or storage complexity of processing digital signals grow dramatically. Therefore, solving multidimensional DSP problems in real-time is extremely difficult.

Parallelmultidimensionaldigitalsignal processing (mD-DSP) is defined as the application of parallel programming and multiprocessing to digital signal processing techniques to process digital signals that have more than a single dimension. The use of mD-DSP is fundamental to many application areas such as digital image and video processing, medical imaging, geophysical signal analysis, sonar, radar, lidar, array processing, computer vision, computational photography, and augmented and virtual reality. However, as the number of dimensions of a signal increases the computational complexity to operate on the signal increases rapidly. This relationship between the number of dimensions and the amount of complexity, related to both time and space, as studied in the field of algorithm analysis, is analogues to the concept of the curse of dimensionality. This large complexity generally results in an extremely long execution run-time of a given mD-DSP application rendering its usage to become impractical for many applications; especially for real-time applications. This long run-time is the primary motivation of applying parallel algorithmic techniques to mD-DSP problems.

References

↑ Abadi, M. Shams Esfand, and S. Nikbakht. "Image denoising with two-dimensional adaptive filter algorithms." Iranian Journal of Electrical & Electronic Engineering 7.2 (2011).
↑ Trimeche, Mejdi. "Hierarchical Motion Estimation Using Recursive LMS Filters." (2007).
↑ Hou, Xiaolin, et al. "On two-dimensional adaptive channel estimation in OFDM systems." Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th. Vol. 1. IEEE, 2004.
↑ Kumar, P. Sarath, and Sumit Roy. "Two-dimensional equalization: Theory and applications to high density magnetic recording." Communications, IEEE Transactions on 42.234 (1994): 386-395.
1 2 Mohiy M.Hadhoud and David W.Thomas. "Two-Dimensional Adaptive LMS (TDLMS) Algorithm." IEEE Transactions on Circuits And Systems, Vol 35, No.5, May 1988.
↑ Alfredo C. Tan and Sheng-Tsal Chen, "Two-Dimensional Adaptive LMS IIR Filter." Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on Date 3–6 May 1993.
↑ Mitsuji Muneyasu, Eiji Uemoto and Takao Hinamoto. "A Novel 2-D Adaptive Filter Based On The 1-D RLS Algorithm." Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on 9-12 June 1997
↑ McClellan, James H. "The design of two-dimensional digital filters by transformations." Proc. 7th Annu. Princeton Conf. Information Sciences and Systems. 1973.
↑ Jenkins, W. K., and R. P. Faust. "A constrained two-dimensional adaptive digital filter with reduced computational complexity." Circuits and Systems, 1988., IEEE International Symposium on. IEEE, 1988.
↑ Azimi-Sadjadi, Mahmood R., and Hongye Pan. "Two-dimensional block diagonal LMS adaptive filtering Archived 2018-12-21 at the Wayback Machine ." Signal Processing, IEEE Transactions on 42.9 (1994): 2420-2429.

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.

[1] Abadi, M. Shams Esfand, and S. Nikbakht. "Image denoising with two-dimensional adaptive filter algorithms." Iranian Journal of Electrical & Electronic Engineering 7.2 (2011).

[2] Trimeche, Mejdi. "Hierarchical Motion Estimation Using Recursive LMS Filters." (2007).

[3] Hou, Xiaolin, et al. "On two-dimensional adaptive channel estimation in OFDM systems." Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th. Vol. 1. IEEE, 2004.

[4] Kumar, P. Sarath, and Sumit Roy. "Two-dimensional equalization: Theory and applications to high density magnetic recording." Communications, IEEE Transactions on 42.234 (1994): 386-395.

[Mohiy-5] 1 2 Mohiy M.Hadhoud and David W.Thomas. "Two-Dimensional Adaptive LMS (TDLMS) Algorithm." IEEE Transactions on Circuits And Systems, Vol 35, No.5, May 1988.

[6] Alfredo C. Tan and Sheng-Tsal Chen, "Two-Dimensional Adaptive LMS IIR Filter." Circuits and Systems, 1993., ISCAS '93, 1993 IEEE International Symposium on Date 3–6 May 1993.

[7] Mitsuji Muneyasu, Eiji Uemoto and Takao Hinamoto. "A Novel 2-D Adaptive Filter Based On The 1-D RLS Algorithm." Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on 9-12 June 1997

[8] McClellan, James H. "The design of two-dimensional digital filters by transformations." Proc. 7th Annu. Princeton Conf. Information Sciences and Systems. 1973.

[9] Jenkins, W. K., and R. P. Faust. "A constrained two-dimensional adaptive digital filter with reduced computational complexity." Circuits and Systems, 1988., IEEE International Symposium on. IEEE, 1988.

[10] Azimi-Sadjadi, Mahmood R., and Hongye Pan. "Two-dimensional block diagonal LMS adaptive filtering Archived 2018-12-21 at the Wayback Machine ." Signal Processing, IEEE Transactions on 42.9 (1994): 2420-2429.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]