next up previous
Next: About this document ... Up: fd Previous: Fourier Descriptor

FD used for shape matching

Given two 2D shapes represented by $\{u[m],\;\;m=0,\cdots,N-1\}$ and $\{v[m],\;\;m=0,\cdots,N-1\}$, respectively, we can determine how similar they are to each other, independent of their location, size, orientation and starting point.

First, the matching problem can be approached in spatial domain by minimizing a distance between the two shapes:

d(u,v)\stackrel{\triangle}{=}min_{\{v_0, S, \phi, m_0\}} \sum_{m=0}^{N-1}
\vert u[m]-Sv[m-m_0]e^{j\phi}-v_0 \vert^2

If $d(u,v)$ is small enough, $u$ and $v$ are similar.

Solving this problem requires a search for the minimum in a 5-dimensional space ($v_0$ has both real and imaginary parts), and is therefore very time consuming.

We next consider solving the problem in frequency domain by comparing $U[k]$ and $V[k]$, the FD's of the two shapes. The factor of location ($v_0$) can be easily eliminated by forcing the DC components $U(0)$ and $V(0)$ to zero, i.e., both shapes are centered at the origin. Now the FD's are

\begin{displaymath}U[k]=DFT[\;u[m]\;] \end{displaymath}


\begin{displaymath}V[k]=DFT[\;Sv[m-m_0]e^{j\phi} \;]
=SV[k]e^{j(\phi-2\pi m_0k/N)}=SV[k]e^{j(\phi-k\beta)}

where $\beta$ is a variable related to the starting point $m_0$:

\begin{displaymath}\beta\stackrel{\triangle}{=}-2\pi m_0/N \end{displaymath}

The distance between $U$ and $V$ is defined as

\begin{displaymath}D(U,V) \stackrel{\triangle}{=} min_{\{S,\phi,\beta\}} \sum_{k=1}^{N-1}
\vert U[k]-SV[k]e^{j(\phi+k\beta)} \vert^2

We don't have to search a 3-dimensional space to find $D(U,V)$. Consider an objective function which is to be minimized:

$\displaystyle J(S,\phi,\beta)$ $\textstyle \stackrel{\triangle}{=}$ $\displaystyle \sum_{k=1}^{N-1}\vert U[k]-SV[k]e^{j(\phi+k\beta)} \vert^2$  
  $\textstyle =$ $\displaystyle \sum_{k=1}^{N-1}[U[k]-SV[k]e^{j(\phi+k\beta)}] [U^*[k]-SV^*[k]e^{-j(\phi+k\beta)}]$  
  $\textstyle =$ $\displaystyle \sum_{k=1}^{N-1}U[k]U^*[k]+S^2\sum_{k=1}^{N-1}V[k]V^*[k]-
  $\textstyle =$ $\displaystyle \sum_{k=1}^{N-1}\vert U[k]\vert^2+S^2\sum_{k=1}^{N-1}\vert V[k]\vert^2-

where $ w[k]e^{j\alpha_k}\stackrel{\triangle}{=}U^*[k]V[k] $ and $w[k]$ is assumed to be real. Also note that if $z=x+jy$ is a complex number, then

\begin{displaymath}z+z^*=(x+jy)+(x+jy)^*=x+jy+x-jy=2x=2Re[z] \end{displaymath}

To find $S$, $\phi$, and $\beta$ that minimize $J(S,\phi,\beta)$, let

\frac{\partial J}{\partial S}=2S\sum_{k=0}^{N-1}\vert V[k]\vert^2
-2\sum_k w[k]\cos(\phi+k\beta+\alpha_k)=0
\end{displaymath} (1)

\frac{\partial J}{\partial \phi}=2S\sum_{k=0}^{N-1} w[k]\sin(\phi+k\beta+\alpha_k)=0
\end{displaymath} (2)

\frac{\partial J}{\partial \beta}=2S\sum_{k=0}^{N-1}\;w[k]k\sin(\phi+k\beta+\alpha_k)=0
\end{displaymath} (3)

Solving Eq. (1) for $S$, we get

S(\phi,\beta)=\frac{\sum_kw[k]\cos(\phi+k\beta+\alpha_k)}{\sum_k \vert V[k]\vert^2 }
\end{displaymath} (4)

From Eq. (2), we get

    $\displaystyle \sum_{k=0}^{N-1} w[k][sin\phi\; \cos(k\beta+\alpha_k)+
\cos\phi\; \sin(k\beta+\alpha_k)]$  
  $\textstyle =$ $\displaystyle \sin\phi \sum_{k=0}^{N-1} w[k] \cos(k\beta+\alpha_k)+
\cos\phi \sum_{k=0}^{N-1} w[k] \sin(k\beta+\alpha_k)=0$  

which yields
\tan \phi = -\frac {\sum_k w[k] \sin(k\beta+\alpha_k)}
{\sum_k w[k] \cos(k\beta+\alpha_k)}
\end{displaymath} (5)

Similarly, from Eq. (3), we can also get

\tan \phi = -\frac {\sum_k w[k]k \sin(k\beta+\alpha_k)}
{\sum_k w[k]k \cos(k\beta+\alpha_k)}
\end{displaymath} (6)

\frac{\sum_k w[k] \sin(k\beta+\alpha_k)}{\sum_k w[k] \cos(k...
...k]k \sin(k\beta+\alpha_k)}{\sum_k w[k]k \cos(k\beta+\alpha_k)}
\end{displaymath} (7)

Solving this equation we get $\beta$, and then from either Eq. (5) or Eq. (6) we $\phi$. We can then find $s$ from Eq. (4). Then $D(U,V)$ is obtained.

next up previous
Next: About this document ... Up: fd Previous: Fourier Descriptor
Ruye Wang 2013-11-18