(转载)Harris角点检测原理

原文在这里，中间增加了一些额外的内容辅助理解。

角点检测(Corner Detection)也称为特征点检测，是图像处理和计算机视觉中用来获取图像局部特征点的一类方法，广泛应用于运动检测、图像匹配、视频跟踪、三维建模以及目标识别等领域中。

不同于HOG、LBP、Haar等基于区域(Region)的图像局部特征，Harris是基于角点的特征描述子，属于feature detector，主要用于图像特征点的匹配(match)，在SIFT算法中就有用到此类角点特征；而HOG、LBP、Haar等则是通过提取图像的局部纹理特征(feature extraction)，用于目标的检测和识别等领域。无论是HOG、Haar特征还是Harris角点都属于图像的局部特征，满足局部特征的一些特性。主要有以下几点：

可重复性(Repeatability)：同一个特征可以出现在不同的图像中，这些图像可以在不同的几何或光学环境下成像。也就是说，同一物体在不同的环境下成像(不同时间、不同角度、不同相机等)，能够检测到同样的特征。
独特性(Saliency)：特征在某一特定目标上表现为独特性，能够与场景中其他物体相区分，能够达到后续匹配或识别的目的。
局部性(Locality)；特征能够刻画图像的局部特性，而且对环境影响因子(光照、噪声等)鲁棒。
紧致性和有效性(Compactness and efficiency)；特征能够有效地表达图像信息，而且在实际应用中运算要尽可能地快。

相比于考虑局部邻域范围的局部特征，全局特征则是从整个图像中抽取特征，较多地运用在图像检索领域，例如图像的颜色直方图。
除了以上几点通用的特性外，对于一些图像匹配、检测识别等任务，可能还需进一步考虑图像的局部不变特征。例如尺度不变性(Scale invariance)和旋转不变性(Rotation invariance)，当图像中的物体或目标发生旋转或者尺度发生变换，依然可以有效地检测或识别。此外，也会考虑局部特征对光照、阴影的不变性。

Harris角点检测

特征点在图像中一般有具体的坐标，并具有某些数学特征，如局部最大或最小灰度、以及某些梯度特征等。角点可以简单的认为是两条边的交点，比较严格的定义则是在邻域内具有两个主方向的特征点，也就是说在两个方向上灰度变化剧烈。如下图所示，在各个方向上移动小窗口，如果在所有方向上移动，窗口内灰度都发生变化，则认为是角点；如果任何方向都不变化，则是均匀区域；如果灰度只在一个方向上变化，则可能是图像边缘。

对于给定图像I(x,y)I(x,y)（即图像强度）和固定尺寸的邻域窗口，计算窗口平移前后各个像素差值的平方和，也就是自相关函数：

E(u,v)=ΣxΣyw(x,y)[I(x+u,y+v)−I(x,y)]2E(u,v)=ΣxΣyw(x,y)[I(x+u,y+v)−I(x,y)]2

其中，窗口加权函数w(x,y)w(x,y)可取均值函数或者高斯函数，如下图所示：

根据泰勒展开，可得到窗口平移后图像的一阶近似（梯度乘以位移，注意IxIx表示x方向的梯度）：

I(x+u,y+v)≈I(x,y)+Ix(x,y)u+Iy(x,y)vI(x+u,y+v)≈I(x,y)+Ix(x,y)u+Iy(x,y)v

因此，E(u,v)E(u,v)可化为：

E(u,v)≈Σx,yw(x,y)[Ix(x,y)u+Iy(x,y)v]2=[u,v]M(x,y)[uv]E(u,v)≈Σx,yw(x,y)[Ix(x,y)u+Iy(x,y)v]2=[u,v]M(x,y)[uv]

M(x,y)=Σx,yw[I2xIxIyIxIyI2y]=[ACCB]M(x,y)=Σx,yw[Ix2IxIyIxIyIy2]=[ACCB]

因此，MM就是偏导数矩阵。
可以有多个角度来理解这个矩阵：
（1）几何角度：
E(u,v)E(u,v)可表示为一个二次项函数：

E(u,v)=Au2+2Cuv+Bv2E(u,v)=Au2+2Cuv+Bv2

A=Σx,ywI2x,B=Σx,ywI2y,C=Σx,ywIxIyA=Σx,ywIx2,B=Σx,ywIy2,C=Σx,ywIxIy

二次项函数本质上是一个椭圆函数，椭圆的曲率和尺寸可由M(x,y)M(x,y)的特征值λ1,λ2λ1,λ2决定，椭圆方向由M(x,y)M(x,y)的特征向量决定，椭圆方程和其图形分别如下所示：

（2）线性代数角度：
首先来点线性代数中特征值和特征向量的基本知识：
对于一个给定的方阵，它的特征向量经过这个方阵的线性变换后，得到的新向量与原来的特征向量保持在同一条直线上，但其长度或方向也许会改变，这个长度的缩放比例就是特征值。

注意：方阵代表了对向量的变换，而不是向量代表了对方阵的变换。对于方阵所产生的变换效果，就可以分解为特征向量和特征值的效果：特征向量代表了旋转，特征值代表了缩放。因此，对于任一向量，如果对其施加了方阵这一变换，就有可能使其旋转和缩放；特别地，对于特征向量这一向量，施加方阵后，就只会缩放，而不会旋转。
通过矩阵相似对角化分解，可以得到：

A=PBP−1A=PBP−1

其中，BB为对角阵，里面是特征值，决定了缩放；PP的列向量是单位化的特征向量，并且互相正交，决定了旋转。

一些参考文章：
矩阵特征值与特征向量和相似对角化
 如何理解矩阵特征值和特征向量？

有了上面的背景，先考虑角点的边界和坐标轴对齐的这种特殊情况，如下图所示，在平移窗口内，只有上侧和左侧边缘，上边缘IyIy很大而IxIx很小，左边缘IxIx很大而IyIy很小，所以矩阵MM可化简为（即没有旋转）：

M=[λ100λ2]M=[λ100λ2]

当角点边界和坐标轴没有对齐时，可对角点进行旋转变换，将其变换到与坐标轴对齐，这种旋转操作可用矩阵的相似对角化来表示，即：

M=XΣXT=X[λ100λ2]XTM=XΣXT=X[λ100λ2]XT

再回过头来重新看一下MM矩阵：

M(x,y)=Σx,yw[I2xIxIyIxIyI2y]=[ACCB]M(x,y)=Σx,yw[Ix2IxIyIxIyIy2]=[ACCB]

时刻注意，式中的IxIx是梯度，是导数，是灰度强度的差别。
对于矩阵MM，可以将其和协方差矩阵类比，协方差表示多维随机变量之间的相关性，协方差矩阵对角线的元素表示的是各个维度自身的方差，而非对角线上的元素表示的是各个维度之间的相关性，在PCA(主成分分析)中，将协方差矩阵对角化，使不同维度的相关性尽可能的小（相关性为0时就是非对角线元素为0），并取特征值较大的维度，来达到降维的目的。而这里的矩阵M中的对角线元素是灰度强度在某一方向上的梯度的平方，而非对角线上的元素则是灰度在两个不同方向上的梯度的乘积，所以可以将矩阵$M看成是一个二维随机分布的协方差矩阵，通过将其对角化，一方面可以得到两个正交的特征向量，另一方面也可以求取矩阵的两个特征值（与两个方向上的梯度直接相关），并根据这两个特征值来判断角点。

更多地关于PCA的补充知识：