目录

图像分割(Segmentation)——K-Means, 最小割, 归一化图割

图像分割是将图片将相似的部分分割成相同的块

https://img-blog.csdnimg.cn/20200731140124510.png

Gestalt理论

解释物体分割的底层原理 将同一个东西群组在一起,集合中的元素可以具有由关系产生的属性

https://img-blog.csdnimg.cn/20200731141124328.png

Gestalt中常见的一些分组的情况

https://img-blog.csdnimg.cn/20200731142105698.png

现实生活中的分组现象

https://img-blog.csdnimg.cn/20200731142812410.png
将这种思想转化为算法

K-Means聚类

主要思想:相似的像素应该属于同一类

https://img-blog.csdnimg.cn/2020073114304895.png
像素表达:每个像素可以使用一个多维向量来表示,如(R, G, B)的三维向量,(R, G, B, x, y)的五维向量

K-Means算法: “物以类聚、人以群分”:

  1. 首先输入k的值,即我们希望将数据集经过聚类得到k个分组。

  2. 从数据集中随机选择k个数据点作为初始大哥(质心,Centroid)

  3. 对集合中每一个小弟,计算与每一个大哥的距离(距离的含义后面会讲),离哪个大哥距离近,就跟定哪个大哥。

  4. 这时每一个大哥手下都聚集了一票小弟,这时候召开人民代表大会,每一群选出新的大哥(其实是通>过算法选出新的质心)。

  5. 如果新大哥和老大哥之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大,趋于>稳定,或者说收敛),可以认为我们进行的聚类已经达到期望的结果,算法终止。

  6. 如果新大哥和老大哥距离变化很大,需要迭代3~5步骤。

https://img-blog.csdnimg.cn/20200731145629120.png

基于灰度值或颜色的K-means聚类本质上是对图像属性的矢量量化

https://img-blog.csdnimg.cn/20200731143822837.png

  • 语义分割:将不同位置上同样的物品分成同一类(如上图三)使用(R, G, B)的三维向量描述像素
  • 实列分割:将不同位置上同样的物品分成不同类,此时就需要考虑像素位置对分割的影响,使用(R, G, B, x, y)的五维向量描述像素

https://img-blog.csdnimg.cn/20200731150331930.png

Mean shift 聚类

K-Means算法可以很简单的进行分割,但是初始值对结果的影响非常大,Mean Shift 算法处理时将像素密度的峰值作为初始值,在特征空间中寻找密度的模态或局部最大值

https://img-blog.csdnimg.cn/20200731152036698.png

所有轨迹通向相同模态的区域

https://img-blog.csdnimg.cn/20200731151831291.png

Mean Shift

  1. 定义特征值:(color, gradients, texture, etc)
  2. 在单个特征点上初始化窗口
  3. 对每个窗口执行Mean Shift直到收敛
  4. 合并接近相同“峰值”或模式的窗口

分割实例

https://img-blog.csdnimg.cn/20200731153417647.png
优势

  • 算法计算量不大,在目标区域已知的情况下完全可以做到实时跟踪;
  • 采用核函数直方图模型,对边缘遮挡、目标旋转、变形和背景运动不敏感。

缺点:

  • 缺乏必要的模板更新;
  • 跟踪过程中由于窗口宽度大小保持不变,当目标尺度有所变化时,跟踪就会失败;
  • 当目标速度较快时,跟踪效果不好;
  • 直方图特征在目标颜色特征描述方面略显匮乏,缺少空间信息。

Image as Graphs

  • 节点代表像素
  • 每对节点之间代表边缘(或每对“足够接近”的像素)
  • 每条边都根据两个节点的亲和力或相似性进行加权

https://img-blog.csdnimg.cn/2020073115523359.png

  • 找一条边将,将像素之间的联系切断
  • 将切断的边的权重相加,使和最小(相似的像素应该在相同的部分,不同的像素应该在不同的部分)

定义权值 $$ exp(-\frac{1}{2\sigma^2}dist(X_i,X_j)^2) $$

  1. 假设用特征向量x表示每个像素,并定义一个适合于该特征表示的距离函数: $dist(X_i,X_j)^2$

  2. 然后利用广义高斯核将两个特征向量之间的距离转化为相似性

  3. 小的$\sigma$:仅群聚邻近点;大的$\sigma$:群聚距离远的点

    https://img-blog.csdnimg.cn/20200731160907845.png

最小割:将权值小的边去掉

https://img-blog.csdnimg.cn/20200731164000819.png

最小割中趋向于将点单独的割出来,就会导致分割出很多“小块”

https://img-blog.csdnimg.cn/20200731164409976.png

归一化图割

$$ \frac{W(A,B)}{W(A,V)}+\frac{W(A,B)}{W(B,V)} $$

  • $W(A,B)$:表示集合$A, B$中所有边的权重的和
  • $W(A,V),W(B,V)$:分别表示分割后集合$A, B$内边的个数,当总的边数一定,其中一个$W$很大时,另一个就会很小,导致整个算式所计算的权重就会很大
  • 定义一个邻接关系矩阵$W$,$(i,j)$表示第i个像素与第j个像素之间的权重,是一个对称的矩阵

  • 定义矩阵$D$,是一个对角的矩阵$D_{ii} = \Sigma_jW(i, j)$

https://img-blog.csdnimg.cn/2020073117251281.png

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

  • 归一化图割权重计算:其中,y是指示向量,如果第i个特征点属于A,那么它在第i个位置的值应该为1,反之则为0;利用拉格朗日算法求权重第二小(最小的是0)的特征值对应的特征向量y:$(D-W)y=\lambda y$ 所求出的y不是[0,…,1,0,0…]而是存在小数的向量,需要设置一个门限,将大于门限的设置为1,小于门限的设置为0

  • 使用特征向量y的项对图进行二分割

  • 改变门限,迭代将图像分成多个区块,也可以使用K-Means将得到的特征向量分类,达到分割多块的效果

分割效果:

https://img-blog.csdnimg.cn/20200731175641209.png

https://img-blog.csdnimg.cn/20200731175536315.png

学习资源:北京邮电大学计算机视觉——鲁鹏