3
$\begingroup$

On page 11 of Fundamentals of Image Processing by Ian T. Young, Jan J. Gerbrands, Lucas J. van Vliet (pdf) the results of the Fourier transform are shown (Figs 4a and 4b) and it appears to me (please correct me if I am wrong), that the transform may exhibit redundant data in four quadrants. If this is so, would it not be possible (especially for highly symmetrical images) to take just the top left quadrant, flip it left and then take the top half of this result and flip it downwards. Would this not preserve much of the information when a reverse FFT is performed? If so, it would allow as 4x reduction of transmitted information before a compression algorithm such as JPEG algorithm was applied.

$\endgroup$
4
$\begingroup$

For real images, there is indeed a formal redundancy, termed Hermitian or conjugate-symmetric as detailed by @Fat32. This symmetry however is "modulated" by the complex expression of the Fourier coefficients. So the FFT requires half the number of coefficients, but twice the amounts, due to the real/imaginary or modulus/phase couples. All in all, the redundancy vanishes.

More precisely, an FFT on a $2n$ length signal provides you with $n+1$ non redundant coefficients: the first (DC) and the last (Nyquist) are always real, the $n-1$ often complex. So you have $n-1$ complex coefficients, plus one pair of reals, altogether $n$ "pairs" of coefficients.

In general, with linear transformations, you cannot expect a bijective, one-to-one mapping with less transformed coefficients than samples in the signal/image, unless, as detailed by @Fat32, you reduce the data space, but then again, the transformed space would naturally have the same dimension as that of the data.

$\endgroup$
2
$\begingroup$

Your observation is basically right.

Given a 2D discrete-space real sequence $x[n_1,n_2]$, its 2D discrete-space Fourier transform $X(e^{j{\omega}_1},e^{j{\omega}_2})$ is a complex valued function which is conjugate-symmetric; i.e., $$X(e^{j{\omega}_1},e^{j{\omega}_2}) = X(e^{-j{\omega}_1},e^{-j{\omega}_2})^*$$

This creates redundancies. Specifically the first quadrant is mapped to the third quadrant (with phase reversal) and second quadrant is mapped into the fourth quadrant (with phase reversal)

If the input image is futher conditioned like being an even sequence or so, then the resulting Fourier transform will exhibit further symmetries and therefore redundancies.

For image compression application, DSFT (or DFT) is not used, however. Instead a more efficient and less redundant transform the discrete-cosine transform (DCT) is utilized.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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