TEMPLATE PATTERN MATCHING

The model image is slid across the target image till a dissimilarity or similarity function is minimized/maximized

SIMILARITY AND DISSIMILARITY FUNCTIONS

SUM OF SQUARE DIFFERENCES

Sum of square differences can be deployed as dissimilarity function

$$SSD(i,j)=\sum _{m=0}^{M-1}\sum _{m=0}^{M-1}(I(i+m,j+n)-T(m,n){)}^2$$

SUM OF ABSOLUTE DIFFERENCES

$$SAD(i,j)=\sum _{m=0}^{M-1}\sum _{m=0}^{M-1}|I(i+m,j+n)-T(m,n){|}^2$$

NORMALIZED CROSS CORRELATION

This measure is invariant to intensity light changes

$$NCC(i,j)=\frac{{\sum }_{m=0}^{M-1}{\sum }_{m=0}^{M-1}I(i+m,j+n)\ast T(m,n)}{\sqrt{{\sum }_{m=0}^{M-1}{\sum }_{m=0}^{M-1}I(i+m,j+n{)}^2}\ast \sqrt{{\sum }_{m=0}^{M-1}{\sum }_{m=0}^{M-1}T(m,n{)}^2}}\Rightarrow$$ $$NCC(i,j)=\frac{\stackrel{\sim }{I}(i,j)\ast T}{\Vert \stackrel{\sim }{I}(i,j)\Vert \ast \Vert T\Vert }\Rightarrow$$ $$NCC(i,j)=\frac{\Vert \stackrel{\sim }{I}(i,j)\Vert \ast \Vert T\Vert cos(\theta )}{\Vert \stackrel{\sim }{I}(i,j)\Vert \ast \Vert T\Vert }=$$ $$cos(\theta )$$

The NCC represents the cosine between the vectors $\Vert \stackrel{\sim }{I}(i,j)\Vert$ and $\Vert T\Vert$ (max when the vectors are aligned)

ZERO MEAN NORMALIZED CROSS CORRELATION

This is a variant of the NCC that takes in to account the mean value of the intensity

$$NCC(i,j)=\frac{{\sum }_{m=0}^{M-1}{\sum }_{m=0}^{M-1}(I(i+m,j+n)-\mu (\stackrel{\sim }{I}))\ast (T(m,n)-\mu (T))}{\sqrt{{\sum }_{m=0}^{M-1}{\sum }_{m=0}^{M-1}(I(i+m,j+n)-\mu (\stackrel{\sim }{I}){)}^2}\ast \sqrt{{\sum }_{m=0}^{M-1}{\sum }_{m=0}^{M-1}(I(m,n)-\mu (T){)}^2}}$$

SAD vs SDD vs NCC vs ZNCC

ZNCC and NCC are more robust to intensity changes

PERFORMANCE

Template matching computation is too much slow for an industrial environment, in order to speed up computation an image pyramid is deployed

In order for this approximation to work levels need to be chosen empirically

PREVIOUS NEXT