2D 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 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]

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 ${\displaystyle x\left(n_{1},n_{2}\right)}$ and the output signal ${\displaystyle y\left(n_{1},n_{2}\right)}$ are related by

${\displaystyle 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 ${\displaystyle \delta (n_{1},n_{2})}$ is by definition the impulse response ${\displaystyle h\left(n_{1},n_{2}\right)}$, we can derive the relationship

${\displaystyle 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 ${\displaystyle H\left(z_{1},z_{2}\right)}$, which is given by

${\displaystyle 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${\displaystyle A(z_{1},z_{2})}$ and an IIR filter with a system function equal to ${\displaystyle 1/B(z_{1},z_{2})}$, as shown in the figure below.[3]

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

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

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

Using equation

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

${\displaystyle 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 _{ij}A_{z}^{(j)}(z_{1},z_{2})B_{z}^{(j)}(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].

Many design techniques for 2-D IIR digital filters have been reported in the literature([1]-[4]). During the past decade, genetic algorithm has been successfully used to digital filter design. Here we present a method for designing 2-D IIR Filters called GA-Based design method.

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].

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.

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.