Blog

Complex Fourier Descriptors

fd

Any contour of length \(N\) can be described as a sequence \((x(k),y(k))   k = (0...N)\).

We can write this as complex notation:

\[ s(k) = x(k) + j\cdot y(k) \]

Then transform the function \(s(k)\) in fourier domain to get the

complex fourier descriptors \(a\):

\[a(u) = \frac{1}{N} \sum_{k=0}^{N-1} s(k) \cdot e^{-\frac{2j\pi uk}{N}}\]

The inverse transform with \(M\) fourier descriptors leads to a closed curve contour:

\[\hat{s}(u) = \sum_{k=0}^{M-1} a(u) \cdot e^{\frac{2j\pi uk}{N}}\]

It is possible to distinguish different contours (e.g. Letters) w.r.t their fourier descriptors. Only a few descriptors are necessary so it is easy to compare them.

Here is a octave code to scan a contour and perform fourier descriptors:

function w = window(n,k)
  if (rem (n, 2) == 0)
    w = [zeros(n/2-k,1) ;ones(2*k,1);zeros(n/2-k,1)  ];
  else
    w = [zeros(n/2-k+1,1) ;ones(2*k,1);zeros(n/2-k,1)  ];
  endif
endfunction
function R=fd(A,N)
  
  [height, width] = size(A);
  
  
  % Search begining of object
  starty = 0;
  startx = 0;
  for i = 1:height
    for j = 1:width
      if (A(i,j)==0)
        startx = i;
        starty = j;
        break;
      endif
    endfor
  endfor
  
  % follow Contur
  x = startx;
  y = starty;
  j = sqrt(-1);
  F =[startx + j*starty];
  
  
  while 1
    if(A(x+1,y-1) == 0 && max(ismember(F,((x+1)+j*(y-1)))) == 0 )
      F=[F; ((x+1)+j*(y-1))];
      x = x+1;
      y = y-1;
      continue;
    elseif(A(x,y-1) == 0 &&  max(ismember(F,((x)+j*(y-1)))) == 0 )
      F=[F; ((x)+j*(y-1))];
      x = x;
      y = y-1;
      continue;
    elseif(A(x-1,y-1) == 0 &&  max(ismember(F,((x-1)+j*(y-1)))) == 0 )
      F=[F; ((x-1)+j*(y-1))];
      x = x-1;
      y = y-1;
      continue;
    elseif(A(x+1,y) == 0 && max(ismember(F,((x+1)+j*(y)))) == 0 )
      F=[F; ((x+1)+j*(y))];
      x = x+1;
      y = y;
      continue;
    elseif(A(x-1,y) == 0 && max(ismember(F,((x-1)+j*(y)))) == 0 )
      F=[F; ((x-1)+j*(y))];
      x = x-1;
      y = y;
      continue;
    elseif(A(x+1,y+1) == 0 && max(ismember(F,((x+1)+j*(y+1)))) == 0 )
      F=[F; ((x+1)+j*(y+1))];
      x = x+1;
      y = y+1;
      continue;
    elseif(A(x,y+1) == 0 && max(ismember(F,((x)+j*(y+1)))) == 0 )
      F=[F; ((x)+j*(y+1))];
      x = x;
      y = y+1;
      continue;
    elseif(A(x-1,y+1) == 0 && max(ismember(F,((x-1)+j*(y+1)))) == 0 )
      F=[F; ((x-1)+j*(y+1))];
      x = x-1;
      y = y+1;
      continue;
    else
      break;
    endif
    
  endwhile;
  
  R = ifft(ifftshift(  fftshift(fft(F)) .*  window(size(F),N) ));
  
endfunction