摘要

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两边都大的点。

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

摘要

滤波作为计算机视觉中常见的一种操作，一般用于降噪、边缘提取等操作。滤波一般通过卷积操作完成，根据需要可以定制卷积核，实现均值/高斯/中值滤波。

卷积操作

卷积操作的示意图如下，给定卷积核g和图像f，卷积后的图像表示为

$$ (f*g)[m,n] = \sum_{k,l}f[m-k,n-l]g[k,l] $$

根据上述公式中的负号，卷积核实际使用时，是将核上下左右翻转后再作用在图像f上。当然这个操作在实际编程时已经被淡化，只不过卷积定义要求了负号(翻转)

卷积具有两个特性：

• Linearity，即$filter(f_1+f_2) = filter(f_1)+filter(f_2)$
• Shift invariance，即$filter(shift(f)) = shift(filter(f))$

以上两个性质说明任何具有平移不变性的线性操作都可以用卷积操作表示。除此之外，卷积操作还满足交换律、结合律、分配律、数乘等操作。

卷积操作会改变图像的大小(联想deep learning中卷积层的padding)，那么如何填充原始图像，保证结果图像和原图保持大小一致就是一个值得思考的问题。具体来说，可以通过填充0值、边缘复制、镜面反射等操作实现填充。

卷积核定制

图像平移

下图是最简单的卷积核，输出与原图保持一致。其中黑边是padding。

如果改变1的位置，那么会起到平移的作用，如下图。

图像模糊(blur)

如果采用全1卷积核，那么中心点的像素值会是一个范围内像素值的平均，从而达到模糊的效果。1/9是为了保证整个卷积核的权重和为1，控制亮度。

如果使用如下两个卷积核相减，最后会得到锐化后的图像。因为原图减去模糊后的图像，会使边缘更加清晰。第一个卷积核中心值为2是为了保证卷积核相减后权值仍为1。

一个更具体的锐化例子如下。

高斯模糊

如果使用传统模糊卷积核，会出现振铃现象，即模糊后的图像会出现线条。

为了抵御这种现象，提出了高斯卷积。事实上，高斯卷积几乎在所有需要平滑的地方都会出现。高斯核中的权值计算如下，权重是和中心点距离有关的函数，距离中心点越远，对应的权值越小。当然最后结果需要归一化，保证高斯核权重和为1。

高斯核有两个参数，高斯核大小与标准差$\sigma$。一般两者大小关系采用$3\sigma$原则。

高斯卷积首先可以滤掉图像的高频部分，相当于低通滤波器。

其次卷积本身是另一种高斯，这句话理解为：两个高斯核的作用可以用一个更大的高斯核作用等效替代，例如执行两次标准差为$\sigma$的高斯模糊操作后，等效于执行一次标准差为$\sqrt 2 \sigma$的高斯模糊。

最后为了加速运算，可以使用两次一维高斯模糊操作来代替一次二维高斯模糊。这样时间复杂度就从$O(n^2m^2)->O(n^2m)$

噪声

噪声分为椒盐噪声、脉冲噪声、高斯噪声三种。

高斯噪声可以使用高斯模糊来去除，标准差越大，去噪越明显，不过图像也越模糊。

中值滤波

而对于椒盐噪声，高斯模糊效果就不是很好。因为高斯说白了还是平滑，但是椒盐噪声有很多突兀的像素点。这个时候使用中值滤波效果可能会更好。具体来说，该点像素值等于核中像素值序列的中间值。

锐化的形式化表示

锐化的形式化表示如下图，最后得到的卷积核是拉普拉斯高斯。