知识库 › 定位仓库学习 › 核心算法 › 前端 › Shi-Tomasi 角点检测
光流法需要若干稳定可解析的角点才能得到正确的光流结果，需要选取的特征点满足在x和y方向上均非奇异。用人话来讲就是，如果我选中了一个点，我需要无论我朝哪个方向摇动相机，这个特征点均存在变化，否则加入我选择了一条水平线上的一个点，我就会观测到：我横向移动相机，发现这个线上的其他特征点也在横向移动，我根本判断不出来相机是否移动。这个反映在数学上就是水平方向梯度奇异，导致这一系列特征点并不能满足同一运动方程，如果和其他正常运动的点一起参与运算，则会导致其他点的正确信息被污染，进而导致光流估计误差。所以说，存在“Good Features to Track”的点就应该是图片中的角点。
在这个需求下，Shi-Tomasi 算法就是在Harris角点检测算法上的优化，通过对窗口内结构张量的特征值判定，就能够高效判定需要追踪的角点。
OpenCV中使用的GFTT算法内部本质就是Harris和Shi-Tomasi算法，可以通过参数进行选择。
核心算法
首先，我们抓住目标点周围的一个窗口作为计算区间，定义在这个区间内如果产生变动将会带来的像素变化量函数
$$E(u, v) = \sum_{(x, y) \in W} w(x, y) \left[ I(x + u, y + v) - I(x, y) \right]^2$$
这个窗口一般取5*5或7*7，其中 $w(x,y)$是权重卷积核，用于调整所有像素对于最终变化量的贡献，一般采用高斯核。
对光流一阶泰勒展开
$$E(u, v) \approx \begin{bmatrix} u & v \end{bmatrix} M \begin{bmatrix} u \\ v \end{bmatrix}$$
其中
$$M = \sum_{(x, y) \in W} w(x, y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}$$
注意到这里直接采用了对x和对y的梯度，但是图像并不是连续的函数，并不存在严格意义上对于坐标的梯度。这里其实是使用了Sobel算子，通过对所有像素的遍历进行模拟求导。
经过上述变化， 我们提取出了一个二次型表达式用来近似像素变化量，只要比对若干个窗口内的这个二次型，我们就能判断这个窗口中心的像素是不是该作为特征点了。
这里涉及到二次型的一个理解：
这个就是一个二次型，在这个二次型中，像素变化被反映为窗口梯度协方差受到运动uv影响后得到的像素变化的加和。我们可以并不用计算这个式子，毕竟寻找角点的任务是在光流计算之前的行为，不同的运动对同一个角点造成的影响也应该是相同的，我们可以观察结构张量 $M$的特征来判断这个是不是一个可以追踪的角点。
这里也体现出二次型的作用，矩阵反映客观存在的特征，向量反映变化，二次型反映变化作用后的某种数值状态，其受到传入的矩阵和向量的数学含义的共同影响。
传统的Harris算法通过人为构造响应函数
$$R=det(M)-k⋅trace(M)^2$$
使用易于计算的行列式以及迹来展示矩阵对x方向和y方向的响应程度，其中k为人为设置的经验常数，一般取0.04∼0.06。
判断标准如下：
- R 很大且为正 → 角点
- R 为负 → 边缘
- |R| 很小 → 平坦区域
这个策略固然能够避免对特征值的计算，但是引入了难以确定的经验常数k，对于个别图像并不适用。所以Shi-Tomasi在这个基础上进行了修改。
他直接使用
$$R=min(\lambda_1,\lambda_2)$$
作为评判标准，由于对于M这个梯度协方差矩阵，两个特征值分别能够反映X方向和Y方向的控制强度，如果其中最小的那个都能够使R大于阈值，就说明这个矩阵在两个方向上都能反映出较大的控制能力。
这里引用原文的计算「Shi–Tomasi 角点」，事实上倾斜直线也能够通过两个特征值的最小值反映出来。
之前提到特征值的计算较为复杂，事实上，Shi-Tomasi看似重新引入了特征值计算，只有分别计算才面临较大的计算量，只用
$$min(\lambda_1,\lambda_2)=\frac{(a+c)-\sqrt{(a-c)^2+4b}}2$$
就能够得到判定参数 $R$。
之后就是老生常谈的部分，如果R大于阈值，我们就取该窗口中心像素为特征点就行。