2D adaptive filters

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

Block Diagram for Two-Dimensional System Identification.

2D Adaptive Filters can be used to identify systems. The system function of the unknown system is given by ${\displaystyle P(z_{1},z_{2})}$, and ${\displaystyle H(z_{1},z_{2})}$ is the system function of the 2D adaptive filter when its output comes to steady. The error signal ${\displaystyle e(n_{1},n_{2})}$ between the unknown system output,${\displaystyle d(n_{1},n_{2})}$, and the adaptive filter output,${\displaystyle 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 ${\displaystyle P(z_{1},z_{2})}$ can be represented by ${\displaystyle H(z_{1},z_{2})}$. ${\displaystyle 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.

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:

${\displaystyle 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 ${\displaystyle d(n_{1},n_{2})}$, the adaptive system can be obtained by continuously adjusting the weight values according to some cost function ${\displaystyle F[e(n_{1},n_{2})]}$ that evaluates the error between the two responses.

${\displaystyle e(n_{1},n_{2})=d(n_{1},n_{2})-y(n_{1},n_{2})}$
${\displaystyle 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 ${\displaystyle w}$. Then we can get the filter output given by

${\displaystyle 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 ${\displaystyle e_{j}}$ at the j-th iteration is defined as

${\displaystyle 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:

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

where ${\displaystyle \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

${\displaystyle 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 ${\displaystyle y(n_{1},n_{2})}$ and ${\displaystyle x(n_{1},n_{2})}$ are, respectively, the output and input of the adaptive filter. ${\displaystyle b(m_{1},m_{2})}$ and ${\displaystyle a(m_{1},m_{2})}$ are the masks of the filter`s input and output. The error signal is given by

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

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

The mean square error ${\displaystyle 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.

References

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.
5. 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." Signal Processing, IEEE Transactions on 42.9 (1994): 2420-2429.