Notes on Efficient Graph-Based Image Segmentation
算法的目标
按照一种确定的标准, 将图片分割成细粒度的语义区域, 即Super pixel.
算法步骤
- 预处理. 将图片转换为undirected graph: \(G(V, E)\):
- 每一个像素都是一个顶点.
- 只有相邻像素间才存在边
- 边的权重为它连接的两个顶点间的像素距离
作者的代码使用了欧氏距离
- Steps:
- 将\(E\)按权重递增排序: \(\pi = (e_1, e_2, \dots, e_m)\)
- \(S^0 = V\), 即一开始每个顶点都一个单独的region.
- 重复4直到处理完所有的边得到\(S^1, S^2, \dots, S^{m - 1}, S^m\):
- \(S^q\)由\(S^{q - 1}\)得到:
- \(e_q = <v_i, v_j>\)
- 如果: (1) \(v_i, v_j\)不在\(S^{q - 1}\)的同一个连通区域内, 即:\(C_i^{q -1} \neq C_j^{q - 1}\), 且(2)\(e_q\)的权重比两个component内部的像素差异要小, 即:\(w(e_q) < MInt(C_i^{q -1}, C_j^{q - 1})\), 则将\(C_i^{q -1}, C_j^{q - 1}\)在\(S^{q-1}\)内合并.
- \(S^q = S^{q - 1}\)
- Return \(S^m\)
从之前的构图, 到后面的merge, 都是很常规的做法. 算法的关键在于\(MInt(C_i, C_i)\)函数上, 即如何决定是否合并两个相邻像素/相邻区域.注意, region/区域与component/连通分量在此处含义相同, 可交换使用
Pairwise Region Comparison
具体参考原文Section 3.1
在考虑是否要将两个region合并成一个region时, 需要考虑internal-region的像素差异程度与inter-region的像素差异.
region内部的差异定义为这个region的最小生成树的最大权重:
\[
Int(C) = \max_{e\in MST(C, E)}w(e)
\]
region间的差异定义为连接两个region的最小边的权重:
\[
Dif(C_1, C_2) = \min_{v_i \in C_1, v_j \in C2, <v_i, v_j> \in E} w(<v_i, v_j>)
\]
这个值在上面的算法中为\(w(e_q)\).
\[
MInt(C_1, C_2) = min(Int(C_1) + \tau(C_1), Int(C_2) + \tau(C_2))
\]
其中, \(\tau(C) = \frac {k}{|C|}\). \(k\)是一个指定的常数. \(|C|\)是region的面积(包含的像素个数).
\(Dif(C_1, C_2) < MInt(C_1, C_2)\)是合并\(C_1, C_2\)的前提条件. 之所以加入\(\tau(C)\), 是为了降低小region合并的门槛.
需要设定的参数
- \(\sigma\): 在分割图片之前需要对其进行高斯平滑操作, 使用期望为0, 方差为\(\sigma^2\)的高斯分布.
- \(k\): \(\tau = \frac {k}{|C|}\) 里的\(k\), \(k\)越大, 最后分割出的region也偏大
- \(min_area\): 在初次分割完之后, 会有很多小region, \(min_area\)用于判断小region, 然后将小region合并