# 18.15.2 Algorithms (2D FFT Filters)

2D FFT filters are used to process 2D signals, including matrix and image. A two-dimensional fast Fourier transform (2D FFT) is performed first, and then a frequency-domain filter window is applied, and finally 2D IFFT is performed to convert the filtered result back to spatial domain.

Five types of filters and four types of windows are available in the 2D FFT Filters tool.

## Filter Types

Filter types include: Low Pass, High Pass, Band Pass, Band Block, and Threshold.

Note that High Pass, Band Pass, and Band Block filters can all be created using Low Pass.

Filter types in 2D FFT Filters are listed in the following table. To understand 2D filter types of Low Pass, High Pass, Band Pass, Band Block more easily. Note the Ideal Window is used for each filter type in the table.

For a 2D filter H(u,v), u=0, 1,.., M-1, v=0, 1,..., N-1. Normalize the frequency coordinates: m=(u-M/2)/M, n=(v-N/2)/N, where -0.5<m<0.5 -0.5<n<0.5 . r is defined as:
$r(u,v)=\sqrt{m^2+n^2}$ and $\ F_c$ is the cutoff frequency.

Low Pass Block the frequency components above the cutoff frequency, and allow only the lower frequency components to pass. $H_{LP}(u,v) = \begin{cases}1, \ r(u,v)< F_{c} \\0, \ otherwise \end{cases}$ Block frequency components that are below the cutoff frequency. $H_{HP}(u,v) = \begin{cases}1, \ r(u,v)> F_{c} \\0, \ otherwise \end{cases}$ Note that $H_{HP}(u,v)=1\ -H_{LP}(u,v)$. Allow frequencies within a specific range determined by the lower and upper cutoff frequencies to pass. $H_{BP}(u,v) = \begin{cases}1,\ F_{c1}\le r(u,v)\le F_{c2} \\0, \ otherwise \end{cases}$ Note that $H_{BP}(u,v)=\ H_{LP2}(u,v) -H_{LP1}(u,v)$. where $\ H_{LP1}(u,v)$ and $\ H_{LP2}(u,v)$ are low-pass filters with the lower and upper cutoff frequency Fc1 and Fc2 respectively. Remove the frequencies within the chosen range. $H_{BB}(u,v) = \begin{cases}0,\ F_{c1}\le r(u,v)\le F_{c2} \\1, \ otherwise \end{cases}$ Note that $H_{BB}(u,v)=\ 1-H_{BP}(u,v)$. Allow only frequency components whose amplitudes are between the lower threshold value and the upper threshold value to pass. $H_{AT}(u,v) = \begin{cases}1,\ TH_1 \cdot max(A(u,v))\le A(u,v)\le TH_2 \cdot max(A(u,v)) \\0, \ otherwise \end{cases}$ Where $A(u,v)=\ abs(H(u,v))$, $\ TH_1$ and $\ TH_2$ are lower and upper threshold values. Note that window will not be used for Threshold filter type.

## Window Types

Window types in 2D FFT Filters include Butterworth, Ideal, Gaussian, and Blackman.

High Pass, Band Pass, and Band Block filters can all be created from the Low Pass option for other window types in the same way as the Ideal window, which is listed in the table in Filter Types. Therefore only Low Pass filters for each window type are described below.

A common way to generate a 2D filter is to rotate the corresponding 1D filter window in the m - n normalized frequency domain, i.e., use $r=\sqrt{m^2 + n^2}$ to replace the variable in 1D Butterworth window function. We take the generation of 2D low-pass Butteworth filter as an example to describe the procedure.

### Butterworth

1D Butterworth window function is expressed as:

$H(u)=\frac{1}{1 + \left (\frac{m}{F_c} \right )^ {2p} }, u = 0, 1, ..., M-1$

Parameters are described as follows:

• m = (u - M/2) / M : the normalized frequency within range [-0.5, 0.5], +/- 0.5 corresponds to the half Nyquist frequency. Note that other normalization methods can also be found. We choose this one because the filter's peak must be aligned with the DC component of the FFT result.
• Fc: the cutoff frequency, which is within the range (0, 0.5], is a key parameter for a filter. For Butterworth, the cutoff frequency is the frequency at which H(u) decreases to half its maximum value. Thus using a larger Fc results in smoother filtering. In general, a smoother filter is better to reduce the negative ringing effect caused by FFT filtering.
• p: the filter order, which is an integer number. The smaller p is, the smoother the filter is.

For a 2D FFT filter, let m = ( u - M/2 ) / M, n = (v - N/2 ) / N. Both m and n are within the range [-0.5, 0.5]. Rotate the 1D Butterworth window in the m - n normalized frequency domain, and let $r=\sqrt{m^2+n^2}$, the 2D Butterworth low pass filter can be expressed as:

$H(u,v)=\frac{1}{1 + \left (\frac{r}{F_c} \right )^ {2p} }, \ u = 0, 1, ..., M-1, \ v = 0, 1, ..., N-1$

H(u,v) should only take values within a circular zone, the radius of which is determined by R = max(-m[0], m[M-1], -n[0], n[N-1]). And when r > R, the value of H(u,v) should be set to zero. And the cutoff frequency Fc is within range (0, R].

The cutoff frequency is normalized by 2R so that Fc's value range is always (0, 0.5].

The procedure to create a 2D FFT filter is as below.

A 2D Butterworth low pass filter for Fc=0.3, p=1 is shown as follows.

### Ideal

Ideal Filter is introduced in the table in Filter Types.

### Gaussian

2D Gaussian low pass filter can be expressed as:

$H(u,v)=exp(-\frac{r^2}{2 \cdot F_c ^ 2} )$

For the 2D Gaussian filter, the cutoff value used is the point at which H(u,v) decreases to 0.607 times its maximum value. Larger values of Fc correspond to a smoother filter.

A 2D Gaussian low pass filter for Fc=0.2 is shown.

### Blackman

2D Blackman low pass filter can be expressed as: $H(u,v)=\begin{cases}0.42 - 0.5 \cdot cos(2 \pi (r + 0.5) ) + 0.08 \cdot cos(4 \pi (r + 0.5) ),\ r(u,v) \le R\\0, \ r(u,v) > R \end{cases}$

Note that this window function is slightly different from the standard form commonly seen, which is high-pass. Here we want a low-pass filter, so we add 0.5 to r to turn the filter into low-pass.

2D FFT Filters in OriginPro provide a Truncate Window option to decide whether to cut off the Blackman window.

2D Blackman low pass filters without (first graph) and with (second graph) truncation are shown below.

## Cutoff Value

2D FFT Filters in OriginPro supports four ways to specify the Cutoff Value. They are Fraction, Fourier Pixel, Wavelength, and Hertz. Relations for these four ways are listed as follows.

Fourier Pixel Pixel in the matrix that stores the data. The value can be any positive number of type double. Fraction = Fourier Pixel / sqrt( (cols/2)^2+(rows/2)^2 ), where cols and rows are numbers of columns and rows of the filter, respectively. Wavelength = (cols-1) / Fourier Pixel Hertz = Fourier Pixel / cols