Stephan Paukner¹

Foundations of Gabor Analysis for Image Processing²

Master’s Thesis
University of Vienna, Austria
November 2007

Keywords: mathematics, numerical harmonic analysis, time-frequency analysis, Gabor analysis, Gabor expansions, signal processing, image processing

Download the PDF (6.1 MB)
(Right click, “Save Link As...”)

Abstract

Signal processing plays an important role in modern society: Its applications span a comprehensive domain from automotive to entertainment industry, from medical diagnostic technology to communication services. Signals are electrical information that represents acoustical, optical or other data, like brain waves (EEG) or geophysical data, whose values exhibit a certain variability in location and time. These electrical data are to be edited, filtered, amplified, denoised, interpolated, transmitted or processed in some other way.

Fourier analysis quickly established as a standard method in signal analysis. Mathematically, signals are represented as discrete periodic functions that are composed of pure oscillations with different frequencies and amplitudes, and the Fourier transform unveils in what amount what frequencies are contained in a signal. But time information gets lost thereby, what led to the idea of a windowed or short-time Fourier transform (STFT), where only short time-intervals in the signal undergo a Fourier transform, cut out by a smooth window function that is subsequently shifted over the signal. However, the time-frequency information that the STFT provides is highly redundant, and a reduction is sought while preserving the complete time-frequency behavior of a signal.

Digital images can be handled just like digital sound signals, they’re representable as a sum of pure two-dimensional (2D) oscillations. Mathematically, there is no distinction at all, as the theory is developed in general function spaces. But it can be confusing in practise to talk about the time-frequency analysis of images, as the image signal does not evolve in one-dimensional time, but on a two-dimensional plane. Furthermore, the time-frequency plane becomes a four-dimensional position-frequency space, what makes it difficult to produce descriptive graphs of windowed 2D Fourier transforms of images. Nevertheless, mathematically the terms time and frequency are handled in arbitrary dimensions.

The problems that emerge in signal analysis nourish a standard task in mathematical analysis, namely that of describing arbitrary functions by the help of a set of simple functions that possess well-known and easy-to-handle analytical properties. Fourier analysis fulfills this by expanding a signal into a sum of elementary oscillations. The STFT equivalence is to use a sufficient set of time-frequency shifts of a single window function instead. The concern about when the emerging analysis and synthesis operations are reasonable is handled by the theory of frames, a generalization of the concept of bases. Gabor analysis unites these mathematical approaches: It yields conditions for a set of time-frequency shifted window functions to be a frame for the signal space and provides an understanding of signals by expanding them into a sum of those elementary shifted and modulated atoms.

This thesis wants to examine how the concepts of Gabor analysis apply to the case of digital images and what new problems emerge compared to one-dimensional signals. The following paragraphs summarize how this work is organized.

Chapter 1 is a summary of the foundations of time-frequency analysis. The Fourier transform and STFT are introduced in general function spaces that possess an inner product and are thus equipped with some kind of geometry. It makes sense to only consider functions of finite energy, making the space of square-integrable functions, L²(R^d), the candidate of choice.

Chapter 2 introduces the concept of frames in general (separable) Hilbert spaces. The special case of Gabor frames is again treated in L²(R^d). It is explained that Gabor expansions consider two window functions: The analyzing prototype and its reconstructing dual that is dependent on the chosen subgroup of the time-frequency plane. Whereas signal processing previously was of the time-continuous analog type, it has changed to a finite time-discrete model today due to the high availability of digital computers. The chapter ends with the necessary step to a time-discrete signal model.

Chapter 3 is dedicated to finite discrete Gabor frames for a finite discrete periodic signal model, eventually enabling computational implementations. A finite sequence of real or complex values can be represented as a vector, where the dimensionality of the emerging signal space should not be confused with the one-dimensionality of the vector shape. Things become related to terms of linear algebra, and the matrix representation of frames is introduced. Finally, dual Gabor windows on general sampling subgroups are shown that possess a significant non-zero imaginary part.

Chapter 4 takes the step from 1D signals to 2D images. It explains how images are represented in digital computers. The chapter provides an understanding of 2D elementary oscillations and the idea of 2D frequencies. The 2D Fourier transform unveils to what extent low frequencies contribute to the homogeneous areas in natural images and how higher frequencies are responsible for contours, edges and sharpness. Then the author provides a way of how to visualize the 4D position-frequency behavior of an image by presenting a collection of 2D images. The chapter ends with a treatment of 2D windows for the 2D STFT of images.

Chapter 5 finally comes to Gabor expansions of images. It turns out that the possible non-separability of 2D windows intervenes with the various depths of the non-separability of 4D sampling subgroups. The following sections reflect the order of increasing difficulty for computational implementations, going from twofold separability (of both 2D atom and 4D lattice) to true non-separability (of both atom and lattice). All cases are accompanied by numerical experiments with Gabor coefficient thresholding. Separable atoms allow for the consideration of tensor products of two 1D frames. The case of fully separable lattices allows for an efficient Gabor expansion by using the sampled 1D STFT. The involvation of non-separable subgroups leads to 2D duals with non-zero imaginary parts as well. Under certain conditions general 2D atoms on 4D grids can be mapped to a 1D case. Finally, an approach for obtaining quicker 2D Gabor expansions is provided by signal downsampling.

“Serious” image processing is not treated in this thesis, as implementations that involve Gabor systems had to be compared with approved existing methods. This work thus ends by providing references to literature that consider image processing methods by Gabor expansion, and lists some questions for further research.

The published numerical computations were performed on a PC using a single 1.6 GHz CPU and 1 GB RAM. The experiments were implemented in MATLAB 7 and Octave 2.9 on the Debian GNU/Linux operating system (‘lenny’, Kernel 2.6) and involved functions from the NuHAG MATLAB toolboxes. All figures were produced with MATLAB or The GIMP. The typesetting was done in LATEX.