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$ is a variable related to the starting point $m_0$:

$$\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 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$$ (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\phi\; \sin(k\beta+\alpha_k)]$$

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