1
$\begingroup$

I'm studying image denoising by linear filtering with cross-correlation, in particular with a moving-average kernel (K x K kernel of all equal elements which sum is 1).

For clarity, I'd like to refer to 1D moving average filters (and the 2D extension is just done by using 2D Fourier transforms):

I read the dsp SE answer at this link that finds the magnitude of the frequency response of a moving average filter, but that post uses a discrete time Fourier transform, whereas I've seen in a book the use of the discrete Fourier transform: the only difference is that the discrete Fourier transform version is obtained by sampling the discrete-time Fourier transform $H(\omega)$ in the points $\omega_k = \frac{2\pi \cdot k}{N}$.

The book I'm reading also states that the discrete Fourier transform has "meaning" only when $k$ is such that $k \in [-\frac{N}{2}, \frac{N}{2}]$ (and of course $k$ is an integer).

I don't understand how to interpret the sequence given out by the DFT with respect to the frequency response of that filter and why the DFT has "meaning" only if $k \in [-\frac{N}{2}, \frac{N}{2}]$ and not $k \in [0, N-1]$. I also suppose that N is the size of the 1D moving average filter, but I'm not sure.

EDIT: moreover, how does the size of the moving average filter relate to the frequency response?

Thanks in advance.

$\endgroup$

1 Answer 1

1
$\begingroup$

OK. There's a lot of things going on in your question, and they aren't really pertinent to the title. Here goes:

... but that post uses a discrete time Fourier transform, whereas I've seen in a book the use of the discrete Fourier transform ...

OK. The book was taking a short cut. Hopefully it explained what it was doing and why. For an infinitely-large image, the discrete-time Fourier transform (DTFT) is exactly correct; for any image the discrete Fourier transform (DFT) will have undesired edge effects.

the only difference is that the discrete Fourier transform version is obtained by sampling the discrete-time Fourier transform $H(\omega)$ in the points $\omega_k = \frac{2 \pi k}{N}$.

This is incorrect. It is a not-bad approximation if some conditions are met: For a time-domain signal $x(n)$ that is only nonzero for some interval $n \in [n_{min}, n_{max}]$ and $n < N$, and which has a DTFT whose spectrum is very small for $\omega \notin [-\pi, \pi]$, then the approximation is good to the extent that the spectrum outside of $[-\pi, \pi]$ is small.

I don't understand ... why the DFT has "meaning" only if $k \in [-\frac{N}{2}, \frac{N}{2}]$ and not $k \in [0, N-1)$.

The DFT has meaning for any contiguous interval of $N$ points (and even sets of $N$ points that aren't contiguous, but meet certain conditions -- but that's getting really weird). But that meaning gets further and further away from easy physical truths the further you get from $k \in [-\frac{N}{2}, \frac{N}{2}]$

For any DFT, $H(k) = H(k \mod N)$. This drops out of the defining math. It is why the DFT only has "meaning" for some set of $N$ points -- that's just all there is. This is a reflection of the fact that the DFT is a lossless transform, and you start with $N$ points. Once you look at $N$ output points, there cannot be more information in additional points.

For any DFT of a real-valued (not complex) signal, $H(k) = H(-k)^*$, where $X^*$ is the complex conjugate of $X$. So for that case, while the DFT output has "meaning" outside the interval $k \in [-\frac{N}{2}, \frac{N}{2}]$, it's not a terribly useful meaning. In fact, because $H$ is complex, and it contains $N$ non-zero real or imaginary components in the interval $k \in [0, \frac{N}{2}]$, that's often the only part you look at if you're starting with real-valued data (and there's FFT routines that are designed to take real-valued data and be just a bit faster than their fully-complex counterparts because of the inherent symmetry).

moreover, how does the size of the moving average filter relate to the frequency response?

Generally speaking, if you have two filters of the same overall shape, the broader one has a narrower frequency response, and visa-versa. There's an exact relationship when you're talking about a continuous-time signal and taking it's Fourier transforms. Everything becomes hand-wavy when you get into discrete time, but the principle more or less applies.

So -- a wider moving average filter has a lower cutoff frequency, pretty much proportional to the number of points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.