角检测

角检测（英语：Corner detection）或兴趣点检测（interest point detection），是计算机视觉系统中用来提取特征以及推测图像内容的一种方法。角检测的应用很广，经常用在运动检测、跟踪、马赛克（image mosaicing）、全景图缝合（panorama stiching）、三维建模以及物体识别中。

问题定义

两条边的交点形成一个角（点）。而图像的要点（也称为受关注点）是指图像中具有代表性以及稳健性（即指该点能够在有噪声干扰的情况下也能稳定的被定位，在大陆亦被称为：鲁棒性）的点。也就是说，要点可以是角（点），也可以不是，例如局部亮点或暗点，线段终点，或者曲线上的曲率最大值点。在实际应用中，很多所谓的（角）点检测算法其实是检测要点，而不仅仅是角（点）。所以，如果我们只想检测角的话，还需要对检测出的要点进一步分析。

例如也可以先经过边检测，之后在做一些后处理来检测角，像是Kirsch operator和Frei-Chen masking set两种方法。为了分辨区辨识时图像含有一部分目标图像的资讯是否正确，角检测通常不是一个非常确定且同时需要很多额外的确认才可以确定，角检测在图像上最简单的做法是利用相关性，但这样的作法需要耗费大量的运算资源以及得到的结果可能只是局部最大值，因此有另一个常见的作法是使用Harris和Stephens所提出的经由改善Moravec方法的结果。

Moravec 角检测演算法

这是最早使用来做角检测的做法，他首先定义所谓的“角”就是那些自我相似程度低的点。这个演算法检查所有图像中的像素，并考虑以该像素为中心点的一片范围，该范围与他周围覆盖最大的另一个范围的相似度做为参考，而相似度通常是将两个范围的对应点计算误差的平方和(SSD: Sum of Squared differences) ，越小代表相似度越高。

举例来说，如果一个像素是位于一片均匀强度的区块时，这时每个像素周围与其附近的像素的周围都是相当类似的，因此相似度也高，不会被认为是角。而在图形的边界处的像素，若是与边垂直方向处附近的像素，两者的周围图像相似度就会比较低，然而若是与边平行附近的像素，两者的周围图像相似度就会比较高(看到的都是一条在同样位置的边)，因此也不会被认为是角。只有在那些与附近像素的周围图像都很不相似的像素，才会被认为是“角”。

如果我们将这种与周围的相似程度量化(使用误差平方和)，并且找出整个图像的局部最大值(局部最不相似的点)，这些局部最大值就很有可能是我们想要侦测到的“角”。

Harris & Stephens / Plessey / Shi–Tomasi 角检测演算法

主条目：哈里斯边角侦测

Harris & Stephens改善了Moravec的方法，他们直接考虑每个像素沿著特定方向处的像素的SSD，而不是使用与周围像素范围的SSD。

不失一般性，我们假设现在是对一个灰阶的2维图像来做侦测。令这个图为 $I$ ，考虑 $(u,v)$ 位置的像素与周围的区块，并选取一个固定向量 $(x,y)$ 作为该像素的参考像素，因此固定的这个向量 $(x,y)$ 所算出的所有差平方和的总和记做为 $S(x,y)$ ，而对于每个 $(u,v)$ 做不同加权，就可以得到

$S(x,y)=\sum _{u}\sum _{v}w(u,v)\,\left(I(u+x,v+y)-I(u,v)\right)^{2}$

如果使用泰勒展开式将 $I(u+x,v+y)$ 展开，假设$I_{x}$ 和 $I_{y}$是 $I$ 的偏微分，可以得到

$I(u+x,v+y)\approx I(u,v)+I_{x}(u,v)x+I_{y}(u,v)y$

并将原式改写成

$S(x,y)\approx \sum _{u}\sum _{v}w(u,v)\,\left(I_{x}(u,v)x+I_{y}(u,v)y\right)^{2},$

或是使用矩阵来简化算式

$S(x,y)\approx {\begin{pmatrix}x&y\end{pmatrix}}A{\begin{pmatrix}x\\y\end{pmatrix}},$

其中矩阵 $A$ 为

$A=\sum _{u}\sum _{v}w(u,v){\begin{bmatrix}I_{x}^{2}&I_{x}I_{y}\\I_{x}I_{y}&I_{y}^{2}\end{bmatrix}}={\begin{bmatrix}\langle I_{x}^{2}\rangle &\langle I_{x}I_{y}\rangle \\\langle I_{x}I_{y}\rangle &\langle I_{y}^{2}\rangle \end{bmatrix}}$

式子中的矩阵是Harris矩阵，而括号代表对所有的 $(u,v)$ 取加权平均，

一个角(或者说是要点)可以被刻划成该点 $(u,v)$ 使得 $S(u,v)$ 在不同的方向 $(x,y)$ 之间有很大的变异数的点。 根据分析 $A$ 的特征值，以上的特性可以用下面的方式阐述：在角的点上，$A$应该要有两个"大"的特征值。

根据特征值的大小，我们会有以下的推论：

1. 如果 $\lambda _{1}\approx 0$ 和 $\lambda _{2}\approx 0$ 则这个像素 $(u,v)$ 只是一个普通的点。
2. 如果 $\lambda _{1}\approx 0$ 但 $\lambda _{2}$ 为一个大的正数，则这个像素 $(u,v)$ 位在边上面。
3. 如果 $\lambda _{1}$ 和 $\lambda _{2}$ 都是大的正数，则这个像素 $(u,v)$ 就是一个角点。

Harris 和 Stephens 注意到计算特征值在运算量上面相当大，计算中需要使用到取平方根的操作，因此给出了另一个近似值 $M_{c}$ ，其中 $\kappa$ 是需要调整的重要参数。

$M_{c}=\lambda _{1}\lambda _{2}-\kappa \,(\lambda _{1}+\lambda _{2})^{2}=\operatorname {det} (A)-\kappa \,\operatorname {trace} ^{2}(A)$

因此该演算法不需要真正的去做 $A$ 的特征分解，而只需要去估计 $A$ 的行列式和迹。 Shi–Tomasi 角检测在假设一般图像每个像素所给出的函数值通常是光滑(smooth)且稳定的(stable)，他直接去计算 $\min(\lambda _{1},\lambda _{2})$ ，有时又称该方法为 Kanade-Tomasi 角检测。

而 $\kappa$ 的值通常是由经验决定，而通常在 0.04–0.15 的范围里是可解的。 另一种方法可以避开选择 $\kappa$ 的困扰，这个方法是使用 Noble's 角测度 $M_{c}'$ ，而角测度是计算所有特征值 的调和平均数

$M_{c}'=2{\frac {\operatorname {det} (A)}{\operatorname {trace} (A)+\epsilon }},$

其中 $\epsilon$ 是一个小的正常数。

而角的位置的共变异数矩阵即为$A^{-1}$，可以写成

${\frac {1}{\langle I_{x}^{2}\rangle \langle I_{y}^{2}\rangle -\langle I_{x}I_{y}\rangle ^{2}}}{\begin{bmatrix}\langle I_{y}^{2}\rangle &-\langle I_{x}I_{y}\rangle \\-\langle I_{x}I_{y}\rangle &\langle I_{x}^{2}\rangle \end{bmatrix}}.$

Förstner 角检测

使用 Förstner 演算法的例子

在某些情况，会希望更精确地去计算角的位置，为了得到近似值，Förstner 演算法可以解出闭集上的角附近范围中的所有切线与最接近这些切线的点，该演算法依赖于在一个理想的角附近。

一个像素 $\mathbf {x'}$ 的切线 $T_{\mathbf {x'} }(\mathbf {x} )$ 可以由数学式给出

$T_{\mathbf {x'} }(\mathbf {x} )=\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )=0$

其中 $\nabla I(\mathbf {x'} )=[I_{\mathbf {x} },I_{\mathbf {y} }]^{\top }$ 是图像 $I$ 在 $\mathbf {x'}$ 点的梯度向量。 而最靠近长方形范围 $N$ 中所有切线的点 $\mathbf {x} _{0}$ 为

$\mathbf {x} _{0}={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}T_{\mathbf {x'} }(\mathbf {x} )^{2}d\mathbf {x'}$

$\mathbf {x} _{0}$ 到切线 $T_{\mathbf {x'} }$ 的距离依照梯度向量的大小来加权，因此若经过该点的切线有较大的梯度的话，在加权上就会占较高的比重。

尝试著解 $\mathbf {x} _{0}$ ：

${\begin{aligned}\mathbf {x} _{0}&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}(\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} ))^{2}d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\int _{\mathbf {x'} \in N}(\mathbf {x} -\mathbf {x'} )^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }(\mathbf {x} -\mathbf {x'} )d\mathbf {x'} \\&={\underset {\mathbf {x} \in \mathbb {R} ^{2\times 1}}{\operatorname {argmin} }}\,(\mathbf {x} ^{\top }A\mathbf {x} -2\mathbf {x} ^{\top }\mathbf {b} +c)\end{aligned}}$

$A\in \mathbb {R} ^{2\times 2},{\textbf {b}}\in \mathbb {R} ^{2\times 1},c\in \mathbb {R}$ 分别为

${\begin{aligned}A&=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }d\mathbf {x'} \\\mathbf {b} &=\int \nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\c&=\int \mathbf {x'} ^{\top }\nabla I(\mathbf {x'} )\nabla I(\mathbf {x'} )^{\top }\mathbf {x'} d\mathbf {x'} \\\end{aligned}}$

要找出最小值可以经由计算式子对 $x$ 的微分，并让微分后的式子等于0来解$x$

$2A\mathbf {x} -2\mathbf {b} =0\Rightarrow A\mathbf {x} =\mathbf {b}$

注意到如果要能够解上述等式， $A\in \mathbb {R} ^{2\times 2}$ 必须要是可逆的，或是说 $A\in \mathbb {R} ^{2\times 2}$ 必须要是满秩的，而解可以写成

$x_{0}=A^{-1}\mathbf {b}$

只有在范围 $N$ 之中有角时才存在。

此外 Lindeberg 给出一个方法去评估角的确定性，经由最小化误差

${\tilde {d}}_{min}={\frac {c-b^{T}A^{-1}b}{{\mbox{trace}}A}}$

而这对所有尺度都适用，因此这方法可以自动去适应图片中不同梯度大小所造成的影响与误差。

此外

• $c$ 可以被视为最小平方误差计算中的误差，因此当 $c$ 为0时，将没有误差存在。
• 这个演算法可以用来找出环状特征的中心，只需将上述演算法中的梯度向量改成法线向量即可。

多尺度 Harris 算子

Harris 算子中的微分矩阵 $A$ 会牵涉到要计算图像中的偏微分(Image derivatives) $I_{x},I_{y}$，而这可以用附近点的线性组合来做逼近，而计算线性组合时通常也会需要根据附近图像值的大小来做缩放，因此需要两个额外的缩放参数：(i)一个局部缩放参数主要用来让图像平滑一点 (ii)一个积分参数用来累积在微分操作中的非线性算子，作为图像的修正项。

若以 $I$ 代表原本图形中的亮度，$L$ 为一个将图像 $I$ 通过一个高斯滤波器让图像变模糊的结果。

$g(x,y,t)={\frac {1}{2{\pi }t}}e^{-(x^{2}+y^{2})/2t}$

而参数 $t$ 用来控制高斯滤波器的变异数

$L(x,y,t)\ =g(x,y,t)*I(x,y)$

令 $L_{x}=\partial _{x}L$ 和 $L_{y}=\partial _{y}L$ 为 $L$ 的偏导数，此外用一个高斯滤波器作为缩放大小，参数 $s$ 可供调整。 则multi-scale second-moment matrix 可以被定义为

$\mu (x,y;t,s)=\int _{\xi =-\infty }^{\infty }\int _{\eta =-\infty }^{\infty }{\begin{bmatrix}L_{x}^{2}(x-\xi ,y-\eta ;t)&L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)\\L_{x}(x-\xi ,y-\eta ;t)\,L_{y}(x-\xi ,y-\eta ;t)&L_{y}^{2}(x-\xi ,y-\eta ;t)\end{bmatrix}}g(\xi ,\eta ;s)\,d\xi \,d\eta .$

则我们也可以用前面类似的方法来计算 $\mu$ 的特征值，并且定义多尺度 Harris corner 测度为

$M_{c}(x,y;t,s)=\operatorname {det} (\mu (x,y;t,s))-\kappa \,\operatorname {trace} ^{2}(\mu (x,y;t,s))$

注意到局部尺度参数 t 和积分尺度参数 s ，这两个参数通常会有相对关系 $s=\gamma ^{2}t$，其中 $\gamma$ 为一个参数通常介于 $[1,2]$ 之间。 因此我们可以计算多尺度 Harris corner 测度 $M_{c}(x,y;t,\gamma ^{2}t)$ ，在给定的任何局部尺度 t 去做到多尺度角侦测。 一般实际应用上，多尺度角侦测通常会先做尺度选择的步骤，可以参考正规化尺度拉普拉斯算子 。

$\nabla _{norm}^{2}L(x,y;t)\ =t\nabla ^{2}L(x,y,t)=t(L_{xx}(x,y,t)+L_{yy}(x,y,t))$

常常在尺度选择的部分用到，并且用来同时调整尺度以适应该角点。

• 空间范围内多尺度角测度 $M_{c}(x,y;t,\gamma ^{2}t)$ 的最大值：

$({\hat {x}},{\hat {y}};t)=\operatorname {argmaxlocal} _{(x,y)}M_{c}(x,y;t,\gamma ^{2}t)$

• 将图像通过一个高斯滤波器 $\nabla _{norm}^{2}(x,y,t)$ (拉普拉斯算子)所得到的 $L$ 的局部最大值或最小值：

${\hat {t}}=\operatorname {argmaxminlocal} _{t}\nabla _{norm}^{2}L({\hat {x}},{\hat {y}};t)$

参考文献

来源

• C. Harris and M. Stephens. A combined edge and corner detector. Proceedings of the 4th Alvey Vision Conference: 147–151. 1988. 
• C. Harris. Geometry from visual motion. A. Blake and A. Yuille (编). Active Vision. MIT Press, Cambridge MA. 1992. 
• H. Moravec. Obstacle Avoindance and Navigation in the Real World by a Seeing Robot Rover. Tech Report CMU-RI-TR-3 Carnegie-Mellon University, Robotics Institute. 1980.