摘要

特征提取是视觉中的一个重要任务，通过提取特征点，可以完成全景拼接等操作。harris角点就是一个比较好的特征。

特征选择

一个好的特征具有以下几种性质。

• 重复性，特征在不同摄影角度、不同地理位置得到的一系列照片中都应该出现。
• 特殊性，特征应该是特别的，容易辨认的。
• 计算友好，提取特征需要考虑计算效率。
• 局部性，特征应该占据图像的一小部分，对杂波和遮挡具有鲁棒性

特征点应用

特征点应用可以用在图像对齐、3D重建等等视觉任务。

角点

在角点周围的区域中，图像梯度具有两个或多个主导方向，并且它具有重复性、辨别度高。所以角点是一个比较好的特征。

识别角点可以使用一个方框，当方框框住角点时，往任意方向移动，方框内的内容都会发生改变。

我们可以使用$E(u,v)$来描述一个方框移动时，方框内容的变化程度。这里的I指图像强度，也是像素值大小。$x,y$指方框内的各个像素点的坐标.$w(x,y)$指不同像素点的权重，一般方框中心的权重较大。

这里的E(u,v)是相对于某个固定位置的方框定义的，其实可以表示成$E(X,Y,u,v)$，$X,Y$是方框中心点位置，因为之后要用到不同位置的E

$$ E(u,v) = \sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^2 $$

原始的$E$计算过于复杂，每次都需要取方框内和移动后方框内的像素值进行计算。所以这里使用二维二阶泰勒公式进行近似。这里在(0,0)处展开，也就是麦克劳林展开。

最后得到结果如下图。$E(u,v)$变成$M$矩阵的二次型，而$M$矩阵是二阶黑塞矩阵。这里假设I是二阶连续可导的，所以$I_xI_y=I_yI_x$。

这里x,y应该是指u,v，表示偏导的第一个参数和第二个参数。

现在回顾一下角点的性质，对于框住角点的方框。无论是u方向还是v方向，$E(u,v)$都具有较大值。

而$M$矩阵是实对称矩阵，具有n个正交的特征向量，因此可以相似对角化。R是正交矩阵，所以也可以理解成旋转矩阵，可以对坐标进行旋转映射。

先不考虑R的影响，当M是对角矩阵时，只有两个特征值都不为0时，$E(u,v)$才是$u,v$的函数，表示$E$在$u,v$方向都敏感。假如$\lambda_1=0$，那么$E$对于u不敏感，那么这个方框的中心点应该在一条线上。

这个时候考虑R，其实也只是对于移动量$[u,v]$进行坐标的旋转。不影响结果的判断。可视化来说，$M$分解得到的R其实就是负责旋转角点与坐标轴对齐。

harris角点总结

综上所述，判断一个像素点是否是角点。首先构建这个像素点的$E(u,v)$函数，再根据泰勒展开进行化简，得到M矩阵，根据M矩阵的特征值可以得到该像素点的$E(u,v)$随着$u,v$的变化趋势，从而判断该点是否是角点。

实际应用时，可以通过以下公式化简，不需要计算矩阵M的特征值。

harris角点的形式化流程如下。

• 首先通过高斯偏导模板获得每个像素的方向导数
• 计算每个像素的矩阵M
• 通过判别式计算R值，再根据阈值判断是否是角点
• 为了减小角点个数，使用NMS极大值抑制

完整检测过程如下图。

Invariance and covariance

Invariance：

• $feature(transform(image)) = features（image）$

Covariant：

• $features(transform(image))=transformorm(features(images))$

harris角点算法对于位置和旋转是Covariant，但是对于尺度放缩不是Covariant

摘要

Hough变换相比于其他的拟合方法，它可以检测多个图形(当然RANSAC采用TOPK也可以实现多图形检测)。具体来说，Hough变换是将图像空间的像素点向参数空间投影并投票，通过投票最大值得到最优参数。

直线拟合

二维空间的直线有两个参数$m,b$。那么Hough变换投影的参数空间也是二维。

对于图像中的一条线，对应参数空间中的一个点，该点的票数加一。

对于图像中的一个点，对应参数空间中的一条线，线上的票数加一。

那么对于图像中的多个点，如果这些点有较好的线性关系，那么参数空间投票时，会有一个点票数最高，而这个点则是拟合直线的参数。

上述参数空间有个问题，就是$m,b$的范围无法确定，如果直线垂直x轴，m会趋于无限大，参数空间也趋于无限大。因此需要换一种参数表示，这里使用极坐标表示直线。

更换坐标系后，投票策略转换为下图。对于图像上的每个点(这里说图像一般是指边缘图像，可以是canny算法得到的结果)，根据已知$x,y$，遍历$\theta$值，得到对应$\rho$,参数空间中的网格加一票。最后选择票数最高的作为拟合结果。

直线拟合效果如下，右侧为参数空间，亮度代表票数。

方形和圆形拟合结果如下。

噪声影响

如果往数据点中掺入随机高斯噪声，那么参数空间中的亮点会分散。单个参数网格对应的票数会减小。

关于处理噪声点，有以下几种方法：

• 选择适合的网格大小。如果网格太大的话，一个网格代表多条直线，拟合结果不准确；网格太小，每个网格的票数较少，如果无法达到阈值，则无法检测
• 使用软投票。给网格投票时，依据高斯分布给附近的网格也投票。
• 不适用无关的特征。通过canny算法预先处理图像边缘，可以得到图像每个边缘点的梯度大小和方向，该点的边缘线与梯度方向垂直，那么给参数空间投票时，只需要给固定的$\theta$方向投票即可！

随机点影响

对于随机的数据点，参数空间也可能出现票数较高的网格，造成错误拟合。

参数搜索优化

刚刚提到：使用canny算法预先处理图像边缘，可以得到图像每个边缘点的梯度大小和方向，该点的边缘线与梯度方向垂直，那么给参数空间投票时，只需要给固定的$\theta$方向投票即可。投票算法如下图。

这里的$\theta$正好和梯度的方向$\theta_2$一致，都与边缘线垂直。

拟合圆形

圆形有三个参数，$x,y,r$，所以参数空间是三维的。对于一个数据点，确定该点梯度方向后，圆心可能出现在两个地方，然后再枚举r，并在参数空间里的小方块里投票。这里r是有界的，最大不超过图像的大小。

如果不使用梯度方向进行优化，那么圆心可能出现在数据点为圆心的一个圆上，参数空间投票可视化也就是一个圆锥。计算量会很大。

这种方法对于尺度放缩和嘈杂环境是鲁棒的。

泛化使用Hough变换

Hough变换还可以用来识别物体中心点。给定每种元素的分布和图形中心点，可以画出每种元素的矢量图。

测试时将图中的每个元素都套用矢量图，根据投票最多的点可以确定图形中心点。

总结

RANSAC指Random sample consensus，随机采样一致性。算法流程如下：

• 随机选择数据点的一个子集
• 通过数据子集优化模型
• 在模型拟合结果附近的数据点将为该模型参数投票
• 重复以上操作，直到找到一个最优模型，有最多的数据点为他投票

迭代示意图如下。

拟合直线的流程如下图。其中s，d是超参数。拟合直线的流程如下图。其中s，d是超参数。在最后得到票数最高对应的直线时，一般会用该直线和周围的d个点再做一次最小二乘，使拟合更精确。

关于N的选择也是一个重要问题，需要兼顾准确率和效率。通过以下公式可以对给定准确率的情况下预估次数N。其中e是外点率，需要给定，s是每次循环的采样点个数，N是循环个数，p是准确率。

$$ (1-(1-e)^s)^N = 1-p $$

当然N也可以使用自适应的方法确定。算法流程如下图。N初始化为无穷大，当拟合到一个更好的曲线时，重新估计N的大小(N会越来越小)，作为循环的终止条件。内点率外点率可以通过设定一个阈值t来计算。

下图是RANSAC的总结。

补充：指纹配对

RANSAC也可以做指纹的配对，通过拟合两个指纹之间的仿射变换，最后通过投票最大值来判断两个指纹是否来自同一个人。

摘要

如果说边缘检测只是将给定图像的边缘提取出来，那么拟合就是对这些边缘进行数学建模，得到形式化的数学表示。接下来以最简单的拟合直线为例。

最小二乘法

损失函数是所有数据点拟合直线的预测值与真实值的差的平方和。

可以通过偏导或线代的向量投影得到最优参数，下图为偏导过程与结果。

全最小二乘

最小二乘有两个问题：首先是无法表示垂直x轴的直线，二是损失函数不能很好表示直线与数据点之间的距离。全最小二乘对此进行了改善，首先修改了直线的表示方式，其次损失函数从纵向距离改为了直线到数据点的垂直距离。

求解步骤是：首先通过E对d偏导，得到d的a,b参数表示；再找到$U^TU$矩阵的最小特征值，对应的特征向量就是参数a,b的值(最好情况就是找到特征值0的特征向量，但是矩阵特征值不一定有0，所以退而求其次求最小)

全最小二乘的物理意义如下图，就是使所有数据点在直线的垂直方向上的投影最小。

鲁棒估计

最小二乘容易受到极端数据点的影响。

通过变换损失函数，当数据点距离直线越远时，损失会稳定到一个常数，从而减轻极端数据点的影响。$\sigma$是超参数，可以调整拟合对于外点的敏感性，具体见下图。

鲁棒最小二乘因为距离不是线性操作，所以最优参数需要通过迭代得到。为了加速迭代，可以使用最小二乘用于初始化。

摘要

边缘检测是视觉中比较基础任务。通过边缘可以更容易的对图像中的事物进行认知，或者说边缘是图像语义的压缩表示。

检测方法

对于图像边缘，边缘两侧的像素值相差较大。那么可以通过导数来确定边缘位置。

导数定义如下，对于离散的像素点，$\delta x$可以简单表示为1个像素。

进一步可以使用卷积操作来实现横向/纵向边缘的提取，如下图所示。

关于边缘检测算子，有prewitt、sobel、roberts.prewitt比较经典，sobel算子其实是高斯模糊与边缘检测的叠加操作($[1 2 1]^T[-1 0 1]$)，roberts算子则检查斜向的边缘。

我们得到了横向、纵向的偏导，其实就可以确定某个像素点的实际梯度方向。这个梯度方向和边缘线保持垂直，所以也可以得到边缘线的方向，这在之后的拟合hough变换会用到。对梯度取模，可以使边缘现象更加明显。

高斯偏导模板

刚刚提到的sobel算子可以拆解成高斯模糊和边缘检测(偏导)的操作，高斯模糊可以去除一部分噪声，从而使边缘检测更准确。根据求导法则，可以先对高斯核求导，再使用求导后的高斯核进行卷积。求导后的高斯核叫做高斯偏导模板。

示意图如下，左右两图分别检测竖向边缘和横向边缘。

高斯偏导模板的核内数值和应该是0，这样可以保证恒定不变区域卷积后的值为0，即不存在边缘。

Canny边缘检测

直接取梯度的范数，会出现伪边、边缘线不闭合等情况。

使用canny算法提取边缘更加准确。

首先是极大值抑制，使边缘线更细。只保留像素值比梯度方向b两边都大的点。

第二个方法是双门限阈值法。先通过高门限提取部分边，再逐步降低门限值，补充高门限值提取出来的边缘图像。