SHAPE BASED MATCHING

Shape based matching is a technique that involves matching a specific set of corner points and their gradients to find the model image in the target

First, a set of control points, $P_k$, is extracted from the model image by an Edge Detection operation and the gradient direction at each $P_k$ is recorded.

Then at each position the gradients of the $P_k$ are compared to the ${\stackrel{\sim }{P}}_k$ ones computed from the image in order to compute a similarity function

$$S(i,j)=\frac{1}{n}\sum _{k=1}^n{u}_k(P_k)\ast {\stackrel{\sim }{u}}_k({\stackrel{\sim }{P}}_k)$$

with:

$$u(P_k)=\frac{1}{\Vert G_k(P_k)\Vert }\ast \left[\begin{array}{c}{I}_x(P_k)\\ I_y(P_k)\end{array}\right]$$ $$\stackrel{\sim }{u}({\stackrel{\sim }{P}}_k)=\frac{1}{\Vert {\stackrel{\sim }{G}}_k({\stackrel{\sim }{P}}_k)\Vert }\ast \left[\begin{array}{c}{I}_x({\stackrel{\sim }{P}}_k)\\ I_y({\stackrel{\sim }{P}}_k)\end{array}\right]$$ $$,k=\mathrm{1...}n$$

The upper function is limited in the interval $[-1,1]$ and it peaks when all model points are perfectly aligned with the target computed points, in this case a threshold can be set as the minimum number of model points to detect in the target image

IMPROVEMENTS

ROBUSTNESS

in some application is required to be invariant to global inversion of contrast polarity so a simple improvement of the similarity function can be deployed

$$S(i,j)=\frac{1}{n}|\sum _{k=1}^n{u}_k(P_k)\ast {\stackrel{\sim }{u}}_k({\stackrel{\sim }{P}}_k)|$$

PERFORMANCES

The computation of the similarity function can be improved once a threshold $S_{min}$ is chosen given the partial similarity function $S_p$ as:

$$S_p(i,j)=\frac{1}{n}\sum _{k=1}^p{u}_k(P_k)\ast {\stackrel{\sim }{u}}_k({\stackrel{\sim }{P}}_k)$$

so the following relation can be established:

$$S(i,j)<\frac{1}{n}(S_p(i,j)+(n-p))$$

and given the fact that the value of the similarity function need to be lower than the $S_{min}$ threshold

$$S(i,j)<S_{min}$$

it can be said that

$$S_p(i,j)<n\ast S_{min}+(p-n)$$

When the condition is verified the computation of the similarity function can be stopped

PROPERTIES

• Intensity invariant as the similarity function is based on gradient direction only
• No need of computing the edges on the target image which is a risky procedure
• robustness to occlusion which can be tuned by the $S_{min}$ parameter

PREVIOUS NEXT