Fourier Descriptor

Let $x[m]$ and $y[m]$ be the coordinates of the mth pixel on the boundary of a given 2D shape, a complex number can be formed as $z[m]=x[m]+jy[m]$, and the Fourier Descriptor (FD) of this shape is defined as:

$$Z[k]=DFT[z[m]]=\frac{1}{N}\sum_{m=0}^{N-1}z[m]e^{-j2\pi mk/N}\;\;\;(k=0,\cdots,N-1)$$

where $N$ is the total number of pixels along the boundary.

FD can be used as a representation of 2D closed shapes independent of its location, scaling, rotation and starting point. For example, the first $L<N$ FD's $\{ Z[k],\;k=0,\cdots,L\}$ can be used to represent the 2D shape as they reconstruct approximately the shape without the details (corresponding to the high frequency components susceptible to noise). However, note that since the Fourier transform is a complex transform, the frequency spectrum has negative frequencies as well as positive frequencies, with the DC component in the middle. Therefore the inverse transform with $L<N$ components needs to contain both positive and negative terms:

$$\hat{z}[m]=\sum_{k=-L/2}^{L/2} Z[k]e^{j2\pi mk/N}\;\;\;(m=0,\cdots,N-1)$$

The following figures show the reconstruction of a Gumby figure based on different percentages of frequency components (descriptors) after the Fourier transform of the pixels on the boundary of the figure in the image. The percentages used are, from left to right, $0.1\%$, $1\%$, $2\%$, $5\%$, and $100\%$. It can be seen that the reconstructed figures using $5\%$ of the frequency components are very similar to the actual figure (using one hundred percent of the frequency components on the right).

Fourier discriptor has the following properties:

• Translation

  If the 2D shape is translated by a distance $z_0=x_0+jy_0$:
  

  $$z'[m]=z[m]+z_0\;\;\;(m=0,\cdots,N-1)$$
  
  
  its FD becomes
  
  $$Z'[k] = \frac{1}{N}\sum_{m=0}^{N-1}[z[m]+z_0]e^{-j2\pi mk/N}... ...1}{N}\sum_{m=0}^{N-1}z_0e^{-j2\pi mk/N} = Z[k]+z_0 \delta[k]$$
  
  
  i.e., the translation only affects the DC component $Z(0)$ of the FD.

• Scaling

  If the 2D shape is scaled (with respect to origin) by a factor $S$:
  

  $$z'[m]=S\;z[m]$$
  
  
  its FD is scaled by the same factor:
  
  $$Z'[k]=S\;Z[k]$$
  
  

• Rotation

  If the 2D shape is rotated about the origin by an angle $\phi$:
  

  $$z'[m]=z[m]\;e^{j\phi}$$
  
  
  its FD is multiplied by the same factor
  
  $$Z'[k]=Z[k]\;e^{j\phi}$$
  
  

• Starting Point

  If the starting point on the boundary is shifted from 0 to $m_0$:
  

  $$z'[m]=z(m-m_0)$$
  
  
  by time shifting theorem, its FD becomes
  
  $$Z'[k]=Z[k]e^{-j2\pi m_0k/N}$$