What is the DFT of a binomial filter?

Question

I hope this question is not too simple, I just started learning digital image processing. The 1D binomial filter of size 2 is defined by $B_2 = \frac{1}{4}\begin{bmatrix}1 & 2 & 1\end{bmatrix}$. The DFT should be $\frac{1}{2} + \frac{1}{2}\cos(\omega)$, but I have some trouble deriving this solution. I found it here.

My calculations:

$$X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N}nk} = \frac{1}{4} + \frac{2}{4}e^{-\frac{2\pi i}{3}1k} + \frac{1}{4}e^{-\frac{2\pi i}{3}2k}$$ Then I took the real part $Re(X_k)$, and found after simplifying $\cos^2(\frac{\pi k}{3})\cos(\frac{2\pi k}{3})$, which is incorrect. Only if I use two times the second element in $B_2$, I get the same result.

I'm also trying to understand the reason for applying the DFT in this case. My line of thought is: By taking the Laplace/z-transform of the impulse response, one obtains the system's transfer function. Because we are only interested in the steady-state response, we can ignore the imaginary part and calculate instead the fourier transform. Since the input $B_2$ is real, the real part of the DFT is enough. Is this correct?

Answer 1

[EDIT: note that the note you refer to compute the discrete-time Fourier transform, via a continuous argument in frequency. And not a DFT. You are apparently computing a 3-point DFT]

What I usually call the size-2 binomial filter is $\beta_1=\frac{1}{2}[1\;1]$, the 2-point moving average, whose Fourier representation is well-known, or easy to compute.

$$B_1(\omega) = \frac{1}{2} e^{-j\omega/2}(e^{-j\omega/2}+e^{j\omega/2}) = e^{-j\omega/2} \cos(\omega/2)$$

where $\cos(\omega/2)$ can be called "amplitude response".

I think that this index can lead to mistakes, and probably, this is what happened in formula (6) of the document. The formulation is misleading on both aspects: the formula for what they call$\hat{B}_2$ for the spectrum is real and corresponds to the amplitude spectrum.

One of their properties is to be obtained iteratively: $\beta_{n+1}=\beta_{n}\ast \beta_1$. Hence, $\beta_{2}=\beta_{1}\ast \beta_1$, and you can used the result that a convolution turns into a multiplication in the Fourier domain. Thus you can obtain the discrete time Fourier transform of $\beta_{2}$ as a self-product of the one for $\beta_{1}$ (cf. formula (7) on the document). Then:

$$B_2(\omega) = \left( e^{-j\omega/2} \cos(\omega/2)\right)^2 = e^{-j\omega} \cos^2(\omega/2) = e^{-j\omega}\frac{1}{2}(1+\cos \omega)$$

This is most probably the purpose of this exercice: Fourier can simplify computations.

Answer 2

I don't really understand the thing about cosines (as in: how is that helpful?) – a DFT is really just a mapping from a complex vector with $N$ elements to a complex vector with $N$ elements; and your calculation seems to be wrong, and I'm not sure where, but doing two of the three elements of the DFT manually might actually be enough to clear things up.

\begin{align} X_0 &= \sum\limits_{n=0}^{N-1} x_n e^{-i2\pi\frac nN\cdot 0}\\ &= \sum\limits_{n=0}^{N-1} x_n e^0\\ &= \frac 14 (1+2+1)\\ &=1\\[2em] X_1 &=\sum\limits_{n=0}^{N-1} x_n e^{-i2\pi\frac nN\cdot 1}\\ &=\sum\limits_{n=0}^{N-1} x_n e^{-i2\pi\frac n3}\\ &=\frac14 \left( 1 \cdot e^{-i2\pi\frac 03} + 2 e^{-i2\pi\frac 13} + 1 e^{-i2\pi\frac 23}\right)\\ &= \frac 14\left[1+ 2\cos\left(2\pi\frac13\right)+ i2\sin\left(2\pi\frac13\right) + \cos\left(2\pi\frac23\right)+ i\sin\left(2\pi\frac23\right)\right]\\ &\text{bit of basic trigonometry}\\ &=\frac14\left[ 1+ 2\cos\left(2\pi\frac13\right)+ i2\sin\left(2\pi\frac13\right) - \cos\left(2\pi\frac13\right) + i\sin\left(2\pi\frac13\right) \right]\\ &=\frac14\left[ 1+ 1\cos\left(2\pi\frac13\right)+ i3\sin\left(2\pi\frac13\right) \right]\\ &=\frac14\left[ 1-\frac12+ i3\frac{\sqrt3}2 \right]\\ &=\frac18+i\frac{3\sqrt3}8 \end{align}

Note how there's no taking of real parts or anything: the DFT of a sequence is complex in general, and you can't just drop the imaginary part. So, not quite sure why we're talking in control theory terms here, but no, you cannot just drop it. And: the discrete Fourier is not the same as the Laplace transform.

Answer 3

With the help of the two answers above, I think I finally understood what the paper was all about.

Let $Z_n = \sum_{i=1}^n X_i$ where $X_i \sim \text{Bernoulli}(p)$. The sum of $n$ Bernoulli random variables can be found by convolution in the time domain. Then $Z_n$ is a binomial variable.

In the document, the authors mistakenly wrote $B_2 = \frac{1}{4}\begin{bmatrix}1 & 2 & 1\end{bmatrix}$ which is $Z_2 = X_1 + X_2$. They wanted to write $Z_1 = X_1$ i.e. $B_1 = \frac{1}{2}\begin{bmatrix}1 & 1\end{bmatrix}$ (a Bernoulli variable).

The DFT of $B_1$ is

$$\sum_{n=0}^{2 - 1} x_n e^{-\frac{2\pi i}{2}kn} = \frac{1}{2} \cdot e^{-0} + \frac{1}{2} \cdot e^{-\frac{2\pi i}{2}k \cdot 1} = \frac{1}{2} + \frac{1}{2}\cos(\pi k) - \frac{1}{2}i\sin(\pi k)$$ for $k = \{0,1\}$. For $B_0$ and $B_1$ the output of the DFT is real (equation 6 in the paper). So I get the same result when I set $\omega = \pi k$.

Finally, the sum of $N$ Bernoulli variables in the frequency domain is $$B_N = \left(\frac{1}{2} + \frac{1}{2}e^{\frac{2\pi i k}{N+1}}\right)^N$$ (equation 7).

For example, let $N = 2$. Then

$$B_2 = \frac{1}{4} + \frac{1}{2}e^{\frac{2\pi i k}{3}} + \frac{1}{4}e^{\frac{4\pi i k}{3}}$$ for $k = \{0, 1, 2\}$. Then simplified $Re(B_2) = \cos(\frac{2\pi k}{3})\cos^2(\frac{\pi k}{3})$, which is what I also wrote in the question (but the imaginary part for $N > 1$ is necessary as somebody already wrote). And we can use this to build an algorithm which produces binomial coefficients or a binomial distribution https://stackoverflow.com/questions/11032781/fastest-way-to-generate-binomial-coefficients. A bit like the use of fft for polynomial multiplication.