Revision as of 01:15, 22 November 2012 by galazzo (Talk | contribs)

Face Recognition using 2D Fast Fourier Transform

From Nokia Developer Wiki
Jump to: navigation, search

This article explains how to implement a simple face recognition system based on analysis throught their Fourier spectrum. Recognition is done by finding the closest match between feature vectors containing the Fourier coefficients at selected frequencies. The introduced method well compares to other competing approaches.
Despite the argument is certainly complex, the approach used and the tools already implemented make the process easy to implement by all users. The call is therefore not to be frightened by appearances.

WP Metro Icon Multimedia.png
WP Metro Icon WP8.png
Article Metadata
Tested with
Devices(s): Nokia Lumia
Platform(s): Windows Phone
Windows Phone 8
Keywords: Face Recognition, Image Processing
Created: galazzo (12 Nov 2012)
Last edited: galazzo (22 Nov 2012)


The face is one of several features witch can be used to uniquely identify a person. It's the charateristic that we most commonly use to recognize others. Not two human faces are identical which makes them well suited for use in identification.
Besides being a challenging problem in itself the importance of face recognition systems lies in their potential applications such as access control, passport, etc...
The obviuous advantage of a face recognition system compared to competing methods is its low level of intrusion. It only requires looking into camera.
Automated face recognition systems generally evolved along two main routes, either the analysis of grey level information ( often called template based ) or the extraction of mainly geometrical features such as shape, profile or hair colour.
The work presented here comprises a novel template based approach that considering it's simple algorithm compares very wel to other more complex methods that are used commonly such Hidden Markov Models or back propagation Neural Network.

According to humans are thought to view faces primarly in a holistic manner and experiments suggest that holistic approaches are superior to geometrical recognition systems.
The tecnique presented is based on the Fourier spectrum of facial images, thus it relies on a global transformation , every pixel in the image contributes to each value in the spectrum.
The Fourier spectrum is a plot of the energy against spacial frequencies , where spatial frequencies rerlate to the spatial relations of intensities in the image . In our case this translate to distances between areas of particular brightness such as the overall area of the head or the distance of the eyes.
Higer frequencies describe finer details and contrary to what you might think we found them less useful for identification, just as humans can recognise a face from a brief look without focusing on small details.
The recognition of faces is done by finding the closet match ( the difference or distance ) between the newly presented face and all those faces known to the system. The distances are calculated between the feature vectors with entries that are the Fourier transform values at specially chosen frequencies. As few as 30 frequencies yield excellent results.

Fast Fourier Transform

The Fourier Transform is an important image processing tool which is used to decompose an image into its sine and cosine components. The output of the transformation represents the image in the Fourier or frequency domain, while the input image is the spatial domain equivalent. In the Fourier domain image, each point represents a particular frequency contained in the spatial domain image.

The Fourier Transform is used in a wide range of applications, such as image analysis, image filtering, image reconstruction and image compression, text orientation finding that will be covered ( hopefully ) in further articles.

The Fast Fourier Transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. The discrete Fourier transform (DFT) transforms one function into another, which is called the frequency domain representation of the original function. The DFT requires an input function that is discrete. Such inputs are often created by sampling a continuous function, such as a person's voice. The discrete input function must also have a limited (finite) duration, such as one period of a periodic sequence or a windowed segment of a longer sequence.

The DFT is the sampled Fourier Transform and therefore does not contain all frequencies forming an image, but only a set of samples which is large enough to fully describe the spatial domain image. The number of frequencies corresponds to the number of pixels in the spatial domain image, i.e. the image in the spatial and Fourier domain are of the same size.

For a square image of size N×N, the two-dimensional DFT is given by:


where f(a,b) is the image in the spatial domain and the exponential term is the basis function corresponding to each point F(k,l) in the Fourier space. The equation can be interpreted as: the value of each point F(k,l) is obtained by multiplying the spatial image with the corresponding base function and summing the result.
The Fourier Transform produces a complex number valued output image which can be displayed with two images, either with the real and imaginary part or with magnitude and phase. In image processing, often only the magnitude of the Fourier Transform is displayed, as it contains most of the information of the geometric structure of the spatial domain image. However, if we want to re-transform the Fourier image into the correct spatial domain after some processing in the frequency domain, we must make sure to preserve both magnitude and phase of the Fourier image.

The Fourier domain image has a much greater range than the image in the spatial domain. Hence, to be sufficiently accurate, its values are usually calculated and stored in float values.
The Fourier Transform is used if we want to access the geometric characteristics of a spatial domain image. Because the image in the Fourier domain is decomposed into its sinusoidal components, it is easy to examine or process certain frequencies of the image, thus influencing the geometric structure in the spatial domain.

In most implementations the Fourier image is shifted in such a way that the DC-value (i.e. the image mean) F(0,0) is displayed in the center of the image. The further away from the center an image point is, the higher is its corresponding frequency.

For a slighly deeper view, see Sound pattern matching using Fast Fourier Transform in Windows Phone.

498 page views in the last 30 days.