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

We use cookies on our website. Some of them are essential for the operation of the site, while others help us to improve this site and the user experience (tracking cookies). You can decide for yourself whether you want to allow cookies or not. Please note that if you reject them, you may not be able to use all the functionalities of the site.