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

$$U[k]=DFT[\;u[m]\;]$$

and

$$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\stackrel{\triangle}{=}-2\pi m_0/N$$

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

$$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:

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

$$= \sum_{k=1}^{N-1}[U[k]-SV[k]e^{j(\phi+k\beta)}] [U^*[k]-SV^*[k]e^{-j(\phi+k\beta)}]$$

$$= \sum_{k=1}^{N-1}U[k]U^*[k]+S^2\sum_{k=1}^{N-1}V[k]V^*[k]- 2S\sum_{k=1}^{N-1}Re[U^*[k]V[k]e^{j(\phi+k\beta)}]$$

$$= \sum_{k=1}^{N-1}\vert U[k]\vert^2+S^2\sum_{k=1}^{N-1}\vert V[k]\vert^2- 2S\sum_{k=1}^{N-1}w[k]cos(\phi+k\beta+\alpha_k)$$

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

$$z+z^*=(x+jy)+(x+jy)^*=x+jy+x-jy=2x=2Re[z]$$

To 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$$ (1)

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

$$\frac{\partial J}{\partial \beta}=2S\sum_{k=0}^{N-1}\; w[k]k sin(\phi+k\beta+\alpha_k)=0$$ (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 }$$ (4)

From Eq. (2), we get

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

which yields

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

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)}$$ (7)

Solving Eqs. (5) and (6) simultaneously, we can obtain $\beta$ and $\phi$, given which, we can solve Eq. (4) for $S$. Then $D(U,V)$ is obtained.