快速归一化互相关

简介

[1] [2] [3] [4] [5] [6]

本文主要介绍J. P. Lewis的快速归一化互相关技术[2]。

计算两个信号之间的相关性是特征检测的经典方法，也是其它高级技术的基础[7]。相关性可以通过空域的卷积计算，也可通过快速傅立叶变换高效计算。虽然归一化互相关（NCC，normalized cross correlation）更利于特征匹配，但并没有高效的频域计算方法，因此，通常在空域计算。由于空域卷积复杂，[8]提出了几个非精确但快速的空域匹配方法。

事实上，通过事先计算图像积分，非归一化互相关可以被高效地归一化。

模版匹配

采用互相关的模版匹配可从欧氏距离平方推导。以$(u,v)$为参考点，

\begin{equation} d^2_{f,t}(u,v)=\sum_{x,y}[f(x,y)-t(x-u,y-v)]^2， \end{equation}

$f$是图像，$t$表示特征，上式展开为

\begin{equation*} d^2_{f,t}(u,v)=\sum_{x,y}[f^2(x,y)-2f(x,y)t(x-u,y-v)+t^2(x-u,y-v)^2]， \end{equation*}

$\sum t^2(x-u,y-v)^2$是常数，若$\sum f^2(x,y)$也近似为常数，那么只会余下互相关项

\begin{equation} c(u,v) = \sum_{x,y}f(x,y)t(x-u,y-v) \label{eq:cross-correlation-term} \end{equation}

度量图像和特征的相似性。采用\eqref{eq:cross-correlation-term}进行模版匹配有几个缺点：

• 图像能量$\sum f^2(x,y)$随位置而变化，可能导致匹配失败，比如特征与图像块非常匹配的相关性可能小于与亮斑的相关性¹；
• $c(u,v)$取值范围依赖于特征的大小；
• 不具有亮度不变性，比如光照导致的图像亮度变化。

相关系数（correlation coefficient）通过归一化图像和特征向量为单位长度，客服了这些问题，这就是余弦形式的归一化互相关性

\begin{equation} \gamma(u,v)={\sum_{x,y}[f(x,y)-\bar f_{u,v}][t(x-u,y-v)-\bar t]\over\left\{\sum_{x,y}[f(x,y)-\bar f_{u,v}]^2\sum_{x,y}[t(x-u,y-v)-\bar t]^2\right\}^{0.5}}， \end{equation}

$\bar t$和$\bar f_{u,v}$分别表示特征和图像区域的均值。

特征追踪

由于NCC并不具备尺度、旋转和透视变换不变性，并非理想的特征追踪方法。但是对某些应用，NCC是一种合理的选择。

参考资料

1. [1]J. P. Lewis, “Fast template matching,” in Vision interface, 1995, vol. 95, no. 120123, pp. 15–19.
2. [2]J. P. Lewis, “Fast normalized cross-correlation,” in Vision interface, 1995, vol. 10, no. 1, pp. 120–123.
3. [3]K. Briechle and U. D. Hanebeck, “Template matching using fast normalized cross correlation,” in Aerospace/Defense Sensing, Simulation, and Controls, 2001, pp. 95–102.
4. [4]D.-M. Tsai and C.-T. Lin, “Fast normalized cross correlation for defect detection,” Pattern Recognition Letters, vol. 24, no. 15, pp. 2625–2631, 2003.
5. [5]F. Zhao, Q. Huang, and W. Gao, “Image matching by normalized cross-correlation,” in Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, 2006, vol. 2, pp. II–II.
6. [6]G. G. Scandaroli, M. Meilland, and R. Richa, “Improving ncc-based direct visual tracking,” in Computer Vision–ECCV 2012, Springer, 2012, pp. 442–455.
7. [7]T. Poggio and R. Brunelli, “Face Recognition: Features Versus Templates,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 15, no. 10, pp. 1042–1052, 1993.
8. [8]D. I. Barnea and H. F. Silverman, “A Class of Algorithms for Fast Digital Image Registration,” Computers IEEE Transactions on, vol. c-21, no. 2, pp. 179–186, 1972.