摘要

语义分割任务是将一张图像做像素级别的分割，将一些原始数据(例如平面图像）作为输入并将它们转换为具有突出显示的感兴趣区域的掩模。它的难度会比图像分类和物体识别更难。当然我们这里讨论的分割效果还是从像素的一些统计特征出发，并没有引入人的先验认知知识(其实也多少引入了一点，例如格式塔理论，不过基于这个理论的算法难以建模)，所以效果是比较差的。

格式塔理论

格式塔理论其实是一种心理学理论，它表明人类视觉是整体的：我们的视觉系统自动对视觉输入构建结构，并在神经系统层面上感知形状、图形和物体，而不是只看到互不相连的边、线和区域。最经典的问题就是比较线段长短。

格式塔理论给我们了一些设计语义分割的思路，它给出了一些像素点分类的指导思想。例如通过地理位置、相似性、平行、对称等关系去分类像素点，实现分割。

这里其实就是自底向上的分割思路。人类看到一张图像做分割，应该是根据已有的知识，自顶向下地去分离物品，比如从人的分离、再到人身上衣服、首饰的分离；而机器做分割，都是从像素出发做分割，单从像素点没办法理解分割操作，这就需要格式塔理论给出的一些人眼视觉的底层模式来指导自底向上的分割了。

实际上，格式塔理论给出的这些模式虽然符合人的视觉特性，但是用算法难以建模。所以只有一部分模式被用在算法中。

基于聚类的分割

分割最简单的一个方法就是聚类，通过将相似的像素点聚在一起，将其认为是一个分割块，最终聚类的分类结果就是分割结果。聚类采用的特征可以是简单的RGB值，也可以是带有位置信息的RGB值，当然也可以是灰度值。

以下是不加入位置信息的灰度图、RGB图的聚类结果。可以发现这种分割并不能分割不同实例，比如两个辣椒连同西兰花都被聚在了一起。

如果加入位置信息，不同实例由于空间位置不同，就有可能被区分，例如下图的两个黄瓜片。

聚类的方式有很多，常见的就是KMeans。具体算法及其优缺点可以参考之前的博客~

Mean shift聚类与分割

先看两张Mean shift做分割的两张结果，还是挺惊艳的。

总的来说，Mean shift有点像基于密度的算法(例如DBSCAN这种)，它是计算给定圆框的重心位置，不断让圆框的圆心逼近重心的方向，从而找到密度最大的那个点。在这个过程中，圆框框住的那些数据点，都可以理解是同一个类。给两张图感受一下就懂了。

算法思想是比较简单的，就是找到一张图像的多个密度中心，每个密度中心认为是一个类。当然为了提高效率，算法还做了一些trick，比如label扩散等等。

Mean Shift有以下优缺点

优点：

• 不用假定数据簇的形状(因为基于密度)
• 只需要一个简单参数，即圆窗的大小
• 可以找到不同的模式(因为只依赖数据点密度)
• 对于外点鲁棒

缺点：

• 效果取决于圆窗大小
• 计算量比较大
• 无法对付高维特征(之前在KMeans也提到过，就是高维灾难，数据点在高维空间是稀疏的，通过密度不好迭代)

图论分割

图论分割的思想是：把图像认为是一个图G(V;E)，首先计算相邻像素点之间的距离Dis，再通过Dis为图中的每条边建模相似度Similarity，然后找到一个最小cost的切割，将整张图切成两份，完成二分类的切割，重复多次就完成语义的分割。

具体例子如下，边的权值代表相似度。

找到一个最小分割，就把最不相似的两份数据点分离开。

当然如果只找最小cost的切割，容易出现孤立点的情况。

所以引入图论中的正则化切割，将cost重新建模为

$$ cost = \frac {w(A,B)}{w(A,V)} + \frac {w(A,B)}{w(B,V)} $$

最终计算最小切割的流程如下：

• 计算W矩阵，即邻接矩阵，代表任意两点之间的相似度
• 计算D矩阵，D矩阵为对角矩阵，对角内容为W矩阵对应行的和
• 最小正则化损失表示为下式，其中y是01向量，代表图中数据点的分类情况

$$ normalized-cost=\frac {y^T(D-W)y}{y^TDy} $$

• 接下来求上式最小值，可以转换成求解以下方程$(D-W)y=\lambda Dy$,进一步转换成$D^{-1}(D-W)y=\lambda y$，即求$D^{-1}(D-W)$矩阵的倒数第二小特征值(因为矩阵有最小特征值0)，对应的特征向量y就是结果。

纹理特征聚类进行分割

我们也可以使用之前提到的纹理特征提取图像信息，再通过聚类将相似的像素点聚在一起，达到分割的目的。

不过纹理特征聚类这种方法在边缘表现不好，会将一个物体的边缘部分也作为一个实体。

摘要

通过纹理特征，我们可以确定物体表面的方向和形状。同时通过纹理特征，我们可以做语义分割、分类、纹理生成等任务。

纹理特征的获取

纹理就是从重复的局部模式组成，局部模式可以通过不同滤波器进行寻找，然后再通过梯度的直方图对局部模式进行表达。梯度直方图的生成做法是给定一个滑动窗口，每次统计窗口中各个像素的梯度方向信息，从而得到这个窗口的梯度直方图信息，然后将窗口移到下一个区域(HOG特征不同窗口之间有重叠，梯度方向信息则是通过不同的核得到)。例如上面四种动物的梯度方向直方图如下图所示，不同直方图之间存在较为明显的差异。

具体来说，我们可以使用之前用过的两个偏导核(其实就是边缘检测)对一张照片进行卷积，得到两个响应图。

使用红色窗口比对两个图片同一位置中的边缘点个数，列成表格。这个表格也就刻画了一个窗口的两维特征，这两维特征是通过两个偏导核得到的。进一步，我们可以把窗口的二维特征画到二维平面，大概能看到四个类。基本对应平坦区域、竖边、横边、拐点几种纹理。

事实上，我们可以采用多个模板去提取纹理信息，如下图所示，有检测边、条纹、斑点的模板。

不同模板提取出来的信息不同，那么对于图像中的一个像素点，我们可以得到他的多维表示。(38个核就对应一个38维向量)

通过多个模板的响应，我们也可以做简单的分类操作。如下图所示，通过响应值较大的模板去推断图片的纹理信息。

摘要

本节主要介绍尺度不变特征以及其经典代表——SIFT，网上关于如何计算SIFT特征的博客有很多，但是大多数博客都没有解释为什么这样找到的特征就是"尺度不变"的、为什么尺度和$\sigma$相关联等问题。因此这篇博客会对这些问题进行一些个人的补充，不一定对，欢迎留言~

尺度不变特征

在这里，我想把尺度理解成某个物体的大小。那么尺度不变特征就可以解释为：那些随着物体尺度变化而不会发生改变的特征。

具体来说，可以假设两张都有一个黑色实心圆的图片，图片大小保持一致，而图中的圆半径不一致。圆的尺度不同，那么尺度不变特征就可以理解成这两张图中共有的一些特征，这些特征不会随圆的改变而变化/消失。当然这里的圆也可以是复杂的建筑，如下图所示。

之前提到的harris角点就明显不是一个尺度不变特征，当角点的大小放大到一定程度，只能检测到边，而检测不到角点，这说明角点特征不是尺度不变的。

回到刚刚圆的例子，我们希望能有一个特征，可以描述不同半径的圆。如果找到了，那么我们就可以允许识别任务中摄像头可以有一定的远近变化，这是非常有意义的，因为生活中的大部分识别任务不能100%保证摄像头与物体始终保持固定的距离。这就是尺度不变特征的意义。

拉普拉斯模板与圆形检测

之前介绍过高斯偏导模板，高斯一阶导模板可以检测边缘(边缘点的响应结果为极值)，二阶导同样可以做到(边缘点的响应是0)，我们称高斯二阶导模板为拉普拉斯模板。

拉普拉斯模板有个特点：对于特定宽度的信号，存在某个$\sigma$的拉普拉斯模板，两者卷积结果响应具有最大值，如下图所示。换句话说，对于某个宽度的信号，都可以找到一个$\sigma_0$对应的拉普拉斯模板，使两者在信号中间那个点的响应$f_0$最大，并且其他$\sigma$的拉普拉斯响应都小于$f_0$。

那么这个响应什么时候最大呢？可以证明：当信号宽度和拉普拉斯模板的0平面宽度一致时，响应可以取到最大值。带入拉普拉斯模板零平面方程可以得到$\sigma=r/\sqrt2$。

至此，我们发现拉普拉斯模板可以检测圆形物体，具体方法是：对于同一张图像，我们使用不同的拉普拉斯模板去卷积($\sigma不断增大$),得到一系列卷积响应图。对于每个像素点，我们取出这些相应图中对应位置的响应，组成一个响应值序列。如果该序列存在极值，即满足响应从小到大再到小的趋势。那么我们可以认为在这个像素点可能是一个圆的圆心，圆的半径就是响应极值对应的拉普拉斯模板的$\sigma$乘以$\sqrt2$。

尺度与sigma

以上说明还没有涉及尺度不变的问题，现在我们回到最开始提到的两张图像，两张图象都有一个圆，圆的半径不同。对于其中一张图像，我们通过上述方法可以检测出圆形的位置和大小。对于另外一张呢？同样可以！两者的区别只在于，我们通过一系列拉普拉斯模板去寻找响应值极值时，两张图片极值出现的像素点可能不同(圆心不同)以及极值对应的拉普拉斯模板$\sigma$不同(半径不同)。

但是这背后蕴藏了一个信息：对于圆这个物体，我们通过拉普拉斯响应可以在不同图像中都识别到它。并且这个圆大小并不影响我们的检测，无非是寻找到的$\sigma$不同而已。

那么这种拉普拉斯极值响应，是不是就是一种尺度不变的特征呢？答案我认为是对的，事实上这就是SIFT特征的理论基础。

还有一个小问题：我们刚刚发现拉普拉斯响应极值对应的$\sigma$和最终检测出来的圆形半径有关，圆形半径越大，$\sigma$越大，对应的拉普拉斯响应图越模糊。所以我们可以将圆形大小、$\sigma$、卷积结果的模糊程度联系起来。并且也多少能够解释网上的这种说法：不同$\sigma$的高斯模板卷积出来的图片对应不同的尺度空间，尺度原本应该描述大小上的关系(至少我的第一反应是)，实际上却和图片的模糊程度相关。

SIFT特征

关于SIFT特征的求法，网上的资料已经非常丰富了。这里大概提一下重要的几个点。

改进一

第一个改进是使用DOG近似LOG，这是利用高斯模板之间的差分来近似拉普拉斯模板。可以证明的是

$$ normed \space LOG = \sigma \frac{ \partial G }{ \partial \sigma } $$

$$ G(x,y,k\sigma) - G(x,y,\sigma) \approx (k-1)\sigma^2 \nabla ^2G $$

那么我们就可以通过DOG(Difference of Gaussians)去近似LOG，可以节约计算量~

改进二

其次是不同$\sigma$的高斯响应，我们使用不同$\sigma$的高斯模板对于原图进行多次卷积操作。事实上，随着sigma不断增大，卷积核也越来越大，计算效率会不断降低。所以为了节约效率，SIFT有了第二个改进，通过上一次卷积的结果计算下一次卷积，这里用到了卷积的可加性，如下所示。

$$ \sigma_{op} = \sqrt{\sigma_{next}^2-\sigma_{curr}^2} $$

我们要得到一个$\sigma_{next}$的结果，只需要在$\sigma_{curr}$的基础上做一次$\sigma_{op}$的卷积就可以了。

改进三

第三个改进是使用多尺度的响应图，不同octave之间的图像大小相差一倍(使用上一个octave的倒数第三张图片缩放一倍后作为本octave的第一张图片，并且第一张图片不再做高斯模糊处理，为什么是倒数第三章可以参考其他博客，大概就是这种$\sigma$分布可以保证倒数第三张的$\sigma$刚好是$k\sigma$)。这里同样是考虑运算效率，小图上的卷积更快，并且降采样可以视为$sigma减半$，意味着不同octave之间可以使用相同的卷积模板，这也是opencv实现中的一个trick。

改进四

由于原始SIFT只能检测出圆形的特征区域，无法克服拍摄视角等问题。所以可以使用放射变换对圆进行微调。

具体用到了之前harris角点提到的M矩阵，通过改变圆某个方向的半径，使M矩阵的两个特征值尽可能保持一致。具体方法就是，首先通过R矩阵确定圆形拍扁(拉长)的方向，在特征值较小的方向，将检测出来的圆进行压缩，直到椭圆区域内的M矩阵两个特征值一致。

改进五

对于提取出来的区域，我们可能会遇到视角旋转等问题。所以这里需要对提取出来的区域做一次归一化旋转。具体来说，就是统计区域内的各个像素点的梯度方向，画出统计直方图，根据直方图的主方向进行旋转，达成归一化的效果。因为只涉及梯度，所以这种方法对于光照、环境都是鲁棒的。

SIFT描述符

SIFT描述符的生成网上有很多资料，大致就是把SIFT区域分成4x4的子区域，每个子区域统计8个方向的梯度方向直方图，通过这八个实数来描述这个子区域，因此最终一个区域可以得到大小为128维的SIFT向量。这就是SIFT描述符了~

总结

总的来说，SIFT特征理解起来还是比较抽象的，特别是尺度不变部分的描述。SIFT描述符也不止用在SIFT算法中，只要是对某个区域进行特征抽象都可以使用SIFT描述符的思想。

摘要

特征提取是视觉中的一个重要任务，通过提取特征点，可以完成全景拼接等操作。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变换还可以用来识别物体中心点。给定每种元素的分布和图形中心点，可以画出每种元素的矢量图。

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

总结