Segmentation and Grouping in Humans
Gestalt Psychology: 先从整体上认知、分割出一个物体，然后认识这个物体的各个细节
Proximity Principle: 靠近的物体会被分为一组
Similarity Principle: 相似的物体会被分为一组
Common Fate: 变化趋势相同的物体被分为一组
Common Region/ Connectivity: 被包围的/互相连接的物体被分为一组
Continuity Principle: 在一条连续曲线上的物体被分为一组
Symmetry Principle: 平行、对称的物体被分为一组
Illusory Contours: 人会产生视错觉、主观想象出的边界
人类的图像分割是非常主观的。为了简化人类的图像分割，我们引入以下的两种“approach”：
Top-down Segmentation: 来自同一物体的像素被归为一类
Bottom-up Segmentation: 相似的像素被归为一类
Segmentation as Clustering
图像可以转化到一个feature space，在这个域当中再进行分组，也就是clustering
像素的特征包括：亮度、颜色、位置。此外还可以增加深度、运动、质地、材料等等特征。用vector表示特征：[R,G,B,X,Y,D…]。因此图像→像素的vector→特征的vector
衡量像素的相似性
假设两个点i, j,其特征分别为。定义距离：
距离越小，像素越接近。
K-Means Segmentation
指定最终分组的个数K。
- 随机生成K个“means”作为每个cluster的均值。
- 将每个点分到距离最近的“means”上，分成K个cluster
- 重新计算每个cluster的均值，得到新的“means”
- 重复2、3，直到算法收敛
一些改进第1步的方法：
- 随机生成means，如果两个means距离过近，则重新生成
- 等间隔均匀地生成means
- 先取一个子集，进行K-Means Clustering，再将其结果作为初始化，对全集进行运算
优缺点：
- 简单，快速
- 需要提前选定number of clusters k
- 对初始化结果敏感
- 对outliers敏感
Mean-Shift Segmentation
特征的分布→密度→将密度转化为“海拔”
每一个“山峰”表示一个cluster。每一个山峰的peak(mode)表示cluster的“center”。每一个像素从“最陡”的方向爬山，爬到山峰后即被分到对应的cluster中。
该算法的实现：
- 选择一个像素点，记录其位置（mean）。
- 以其为中心取一个窗口，计算窗内的其他像素的平均位置，得到Centroid(mean)。
- 该像素移动到这个Centroid。
- 重复2，3，直到算法收敛，到达的点即为一个mode。
所有到达同一个mode的像素被归为一类
优缺点：
- 简单，但计算量大
- 可以任意分组，不需要提前指定
- 不需要初始化
- 对outliers鲁棒
- 分组结果取决于窗口大小W
Graph-Based Segmentation
每一个像素为一个顶点。两两像素之间存在边。则一副图像可以用顶点和边来描述。每一条边的两端两个顶点的相似程度决定了该边的权值。
Pixel Dissimilarity:
Pixel Affinity:
Graph Cut
cut是将一个图中的顶点分为不相重合的两个子集的“切割线”
cut-set是被cut切断的边的集合（两端两个顶点属于不同的子集的边的集合）
cost of cut是cut-set中的边的权值之和：
Graph cut算法设计
相似度高的顶点被分割到一个子集中，相似度低的顶点被分隔到两个子集中。通过寻找cost of cut的最小值，可以将图像分割成若干个子图。
该算法存在的问题是，容易出现小的、孤立的分割，因为边数越小，总的cost of cut明显更小。
解决方法是将cut normalize，这样就不受cut-set中边的数量的影响了。
首先需要衡量分割后子集和全集之间的联系：
Normalized Cut(NCut):
此部分参考教程：
