计算机视觉（本科） 北京邮电大学 鲁鹏

---

Segmentation分割

the goals of segmentation

• Group together similar-looking pixels for efficiency of furtherprocessing将相似的像素组合在一起，以提高进一步处理的效率
  • “Bottom-up” process
  • Unsupervised

超像素superpixels：

过分割：把一个完整的物体分割成很多的小块，分割过细。

欠分割：把很大一块分割在一起，本来不属于同一个物体分割在一起，分割过粗。

• Separate image into coherent “objects” 将图像分割成连贯的“物体”
  • “Bottom-up” or “top-down” process?
  • Supervised or unsupervised?

人的思路：自底向上和自顶向下、无监督和有监督结合。

Inspiration from psychology

The Gestalt school: Grouping is key to visual perception 格式塔学派:分组是视觉感知的关键

• Elements in a collection can have properties that result fromrelationships集合中的元素可以具有由关系产生的属性
  • “The whole is greater than the sum of its parts” 整体大于部分的总和。

涌现Emergence：如果一个系统的属性不是其任何基本元素的属性，那么它就是涌现的。涌现是涌现的属性和结构在更高层次组织或复杂性（「多者异也」）上的显现。个体的群集出现一个集体特征而每一个个体却没有。

• Gestalt factors格式塔因素：Gestalt（整体与其各部分的总和不同）

These factors make intuitive sense, but are very difficult to translate into algorithms 这些因素有直观的意义，但很难转化为算法

• Grouping phenomena in real life 现实生活中的分组现象：

Segmentation as clustering

把分割转换成聚类：认为相似的像素应该属于同一个物体。

语义分割：只能分割出所有辣椒

实例分割：区分出辣椒A和辣椒B是哪一个。

• K-means clustering based on intensity or color is essentially vectorquantization of the image attributes基于强度或颜色的K-means聚类本质上是图像属性的矢量量化
  • Clusters don’t have to be spatially coherent 集群不必在空间上是连贯的

包含位置信息：

K-Means for segmentation

• Pros

  • Very simple method
  • Converges to a local minimum of the error function 收敛到误差函数的局部极小值

• Cons

  • Memory-intensive 内存密集型
  • Need to pick K 需要选择K
  • Sensitive to initialization 对初始化敏感
  • Sensitive to outliers 对异常值敏感
  • Only finds “spherical”clusters 只发现“球形”星团

Mean shift clustering and segmentation均值偏移聚类和分割

• An advanced and versatile technique for clustering-based segmentation 基于聚类分割的高级通用技术

Mean shift algorithm ：

• The mean shift algorithm seeks modes or local maxima of density in the feature space 均值移位算法在特征空间中寻找模式或密度的局部最大值

Image and Feature space (L*u*v* color values) ：

在一个圆形区域内，计算出该区域内像素的重心，把圆心移到重心上（均值漂移）。通过均值漂移，圆心与重心重合即可。

迭代均值漂移：

最终圆心和重心重合：

**Mean shift clustering ： **

• Cluster: all data points in the attraction basin of a mode 聚类:一个模式的吸引盆地中的所有数据点。
• Attraction basin: the region for which all trajectories lead to the same mode 吸引盆地:所有轨迹都通向同一模式的区域。

Mean shift clustering/segmentation ：

• Find features (color, gradients, texture, etc) 寻找特征(颜色，渐变，纹理等)
• Initialize windows at individual feature points 在单个特征点初始化窗口
• Perform mean shift for each window until convergence 对每个窗口进行均值移位，直到收敛
• Merge windows that end up near the same “peak” or mode 合并接近相同“峰值”或模式的窗口

1.确定一次的搜索范围
2.随机初始化先锋队找山头
3每个像素寻找属于自己的山头

Mean shift segmentation results ：

Mean shift pros and cons ：

• Pros

  • Does not assume spherical clusters 不假设球状星团
  • Just a single parameter (window size) 只有一个参数(窗口大小)
  • Finds variable number of modes 找到可变数量的模式
  • Robust to outliers 对异常值稳健

• Cons

  • Output depends on window size 输出取决于窗口大小
  • Computationally expensive 计算成本高：需要大量的计算资源（如时间、内存等）来执行。
  • Does not scale well with dimension of feature space 不能很好地与特征空间的维度成比例

窗口太小会导致局部最优解，进而导致分割过细（过分割）。

Segmentation by graph partitioning

Images as graphs：

节点表示每个像素，每条边由两个节点的亲和度或相似性（affinity or similarity）加权。

Break Graph into Segments：

• Delete links that cross between segments 删除段之间交叉的链接。
• Easiest to break links that have low affinity 最容易断开具有低亲和力的链接
  • similar pixels should be in the same segments 相似的像素应该在相同的段中
  • dissimilar pixels should be in different segments 不同的像素应该在不同的段中

对给定的一张图，寻找一条线进行分割，使这条线上的权重之和最小（相似性最小的那些点被断开）。

---

Measuring affinity： 边的相似性的度量方式

Suppose we represent each pixel by a feature vector x, and define a distance function appropriate for this feature representation 假设我们用一个特征向量x来表示每个像素，并为这个特征表示定义一个距离函数。距离：$dist(x_i,x_j)$

Then we can convert the distance between two feature vectors into an affinity with the help of a generalized Gaussian kernel: 然后我们可以利用广义高斯核将两个特征向量之间的距离转化为亲和度：
e x p { − d i s t ( x i , x j ) 2 2 σ 2 } exp \{ {-\frac{dist(x_i,x_j)^2}{2 \sigma^2}} \} exp{−2σ2dist(xi​,xj​)2​}
归一化到0和1之间。

Scale affects affinity 规模影响亲和力：

$\sigma$ 比较小时，dist稍微大一点，相似性趋于0，也就是很近的点才被分类在一起。

$\sigma$ 比较大时，dist很大的两个点也可能被分类在一起。

下面三张图分别表示的是关于 $\sigma$ 越来越大 图像各点相似度的空间分布：每一小格代表一个像素点，相似度越高越亮

---

Graph cut：图分割

• Set of edges whose removal makes a graph disconnected 一组边的集合，它的移除使图断开
• Cost of a cut: sum of weights of cut edges 切割的代价:切割边的权值之和
• A graph cut gives us a segmentation 图分割给了我们一个图像分割。

What is a “good” graph cut and how do we find one? 什么是“好的”图切，我们如何找到一个?

Minimum cut：

最小割：在图论中，去掉其中所有边能使一张网络流图不再连通（即分成两个子图）的边集称为图的割（英语：cut (graph theory)）（英语：cut），一张图上最小的割称为最小割（英语：minimum cut或min-cut）。
与最小割相关的问题称最小割问题（英语：minimum cut problem或min-cut problem），其变体包括带边权、有向图、包含源点与汇点（简称有源汇），以及将原网络分为多于两个子图等问题。其中，带边权的最小割问题允许有负权边，可通过对所有边权取相反数简单地转化为最大流问题求解。

We can do segmentation by finding the minimum cut in a graph 我们可以通过在图中找到最小切割来进行分割

Efficient algorithms exist for doing this：

Drawback:minimum cut tends to cut off very small, isolated components 最小割倾向于切断非常小的，孤立的组件

Normalized cut：归一化割

This can be fixed by normalizing the cut by the weight of all the edges incident to the segment 这可以通过将所有关联到该段的边的权重归一化切割来解决

The normalized cut cost is:
$$\frac{w(A,B)}{w(A,V)}+\frac{w(A,B)}{w(B,V)}$$
其中：$w(A,B)$ 为A和B之间所有边的权值之和。

把一个集合V切割成两个集合A和B，要求切割掉的边的权重之和最小，但是这样很容易得到A为一个点，B为其余点的情况，所以才提出了这样的一个cost：避免孤立点的分割，避免把A切成一个像素B切成一个整体或者相反的情况。

当把A切成一个像素，$w(A,V)$ 会很小，$\frac{w(A,B)}{w(A,V)}$ 会很大。

• Let W be the adjacency matrix of the graph 设W为图的邻接矩阵。

• Let D be the diagonal matrix with diagonal entries D(i, i) = Σj W(i, j) 设D为对角矩阵，其对角项为 $D(i,i)={\sum }_{j}W(i,j)$ 。

• Then the normalized cut cost can be written as 则归一化切割代价可以写成：
  $$\frac{y^T(D-W)y}{y^{T}Dy}$$
  其中y为指示向量（indicator vector），如果第i个特征点属于A，则y在第i个位置的值为1，否则为负常数（negative constant）。

• Finding the exact minimum of the normalized cut cost is NP-complete, but if we relax y to take on arbitrary values, then we can minimize the relaxed cost by solving the generalized eigenvalue problem (D - W)y = λDy 找到归一化切割代价的确切最小值是NP-complete的，但如果我们将y松弛为任意值，那么我们可以通过求解广义特征值问题 $(D-W)y=\lambda Dy$ （对上面cost利用拉格朗日乘子法 $y^T(D-W)y-\lambda \times y^{T}Dy$ 求导得到）来最小化松弛代价。

• The solution y is given by the generalized eigenvector corresponding to the second smallest eigenvalue 解得的y由对应于第二小特征值的广义特征向量给出。

• Intutitively, the i-th entry of y can be viewed as a “soft” indication of the component membership of the i-th feature直观地说，y的第i项可以看作是第i个特征的分量隶属度的“软”指示? 得到的向量y可能不是整数，可以通过threshold调整为整数。

Normalized cut algorithm :

• 1.Represent the image as a weighted graph G = (V,E), compute the weight of each edge, and summarize the information in D and W 将图像表示为加权图G = (V,E)，计算每条边的权值，总结D和W中的信息
• 2.Solve (D - W)y = λDy for the eigenvector with the second smallest eigenvalue 求解$(D-W)y=\lambda Dy$，求特征值第二小的特征向量。
• 3.Use the entries of the eigenvector to bipartition the graph 使用特征向量的项对图进行二分

To find more than two clusters: 找到两个以上的簇:

• Recursively bipartition the graph
• Run k-means clustering on values ofseveral eigenvectors对几个特征向量的值运行k-means聚类

每个特征向量都是一种分法，聚类算法可以将距离较近的特征向量做为一类

Example result：

Normalized cuts: Pro and con

• Pros

  • Generic framework, can be used with many different features and affinity formulations通用框架，可用于许多不同的特性和亲和性公式。

• Cons

  • High storage requirement and time complexity 存储要求高，时间复杂度高
  • Bias towards partitioning into equal segments 倾向于划分为相等的段

Segments as primitives for recognition 分段的结果是识别的基元