Related Work - Hierarchical Neural Networks for Image Interpretation - page 40

space
Fig. 3.4. Coverage of the space-frequency plane by the coefficients of the representations used
in the fast Fourier transformation. The transformation maps a space-localized representation
step by step into a frequency-localized representation. The size of the representation is not
changed, since the number of cells and the area of a cell stays constant.

256 × 128 × 1 × 1 128 × 64 × 2 × 2 64 × 32 × 4 × 4 32 × 16 × 8 × 8 16 × 8 × 16 × 16
Fig. 3.5. Two-dimensional fast Fourier transformation. The absolute values of the first five
hierarchy levels for two example images are shown on a logarithmic scale. White corresponds
to zero.

FFT N ( k,f )

= FFT N/ 2 ( k,f e ) + T N ( k ) FFT N/ 2 ( k,f o );

= FFT N/ 2 ( k,f e ) − T N ( k ) FFT N/ 2 ( k,f o );

FFT N ( k + N/ 2 ,f )

T N ( k ) = e −i 2 πk/N . k = 0 ,...,N/ 2 − 1;

These smaller DFTs can be decomposed recursively, until the number of pixels de-
creases to two, where the DFT is trivial. To compute an FFT coefficient, only two
coefficients of the lower level need to be accessed. Information flows in a butterfly
graph from all pixels in the signal to the FFT coefficients.
Figure 3.4 illustrates the coverage of the space-frequency plane by the coeffi-
cients of the representations used in the FFT. The transformation maps a represen-
tation localized in space into a representation localized in the frequency domain in
log( N ) steps. All intermediate representations describe the complete signal that can
be reconstructed perfectly from each level. Thus, operations that are local in space
can be applied in the space representation, while operations local in frequency can
be applied in the frequency domain.
The FFT can be generalized to two-dimensional signals (images) by applying it
to each dimension separately. Figure 3.5 shows the first five steps of the 2D-FFT, ap-
plied to two 256 × 128 images which contain handwritten digit blocks. One can see
how the energy that is concentrated at the lines in the space-localized representation
is distributed by the transformation as the representation becomes more localized
in the frequency domain. The produced intermediate representations are useful for
operations that are local in space as well as in frequency. For instance, one can use
the fact that the magnitudes of the FFT coefficients become increasingly invariant
to translations in space.