Efficient Graph-Based Image Segm

2019-11-19 本文已影响0人谢小帅

Paper：Efficient Graph-Based Image Segmentation, MIT, 2004
参考：基于图的图像分割（Graph-Based Image Segmentation）

1. 整体思路

充分利用了 图、树、最小生成树、森林 等传统数据结构

像素点之间的相似度，由 RGB 衡量，也可用其他颜色空间，本质上是对 R/G/B 三值后处理

那么全图像素形成1个无向图 $UG$ ，每个顶点可形成 8邻域或 4邻域相似度
使用最小生成树算法将无向图中的节点联系成森林，可理解森林中每棵树即为1个物体

2. 全局阈值 → 自适应阈值

聚类时：判断两个区域是否合并，最简单的方法只考虑连接二者的边的不相似度。

2.1 全局阈值分配并不合适

h 高频区，像素变化差异大
s 斜坡区，像素逐级变化，刚好在区域连接处的边满足阈值
p 平坦区，像素基本无变化，低频区

2.2 自适应阈值

类内差异 vs 类间差异

定义 $k$ 值，增加1个可变常数项 $r(C) = \frac{k}{|C|}$ ，解决合并起点 “零容忍” 问题。
既然 $|C|$ 表示区域像素数，那么归并起点 $|C| = 1$ ，则 $Diff(C_1,C_2) \leq k$
$Mint(C_i,C_j)$ ： $M$ 表示 min，二者较小值

下图展示了不同分割结果，有 3 个参数

$sigma$ 高斯核，先对原图高斯滤波
$k$ 控制了超像素的大小
$min$ 超像素最小阈值，当 $|C_i| < min$ ，选择与其差异最小的区域合并

设置不同 k 的分割结果

3. 算法步骤

计算每个像素点与其 8邻域 或 4邻域 的不相似度。

将边按照不相似度从小到大排列得到 $e_1, e_2, ..., e_N$
选择 $e_1$ ：最小生成树，两个区域只需要连接 1 条边，但是最小不相似度的边对应的两个区域不一定满足 4 中的条件 2，即 $e_1$ 对应的 2 个区域不一定能连接。
对当前选择的边进行合并判断。设其所连接的顶点为，如果满足合并条件：
- $v_i,v_j$ 属于两个不同区域 $Id(v_i) \neq Id(v_j)$
- $w_{ij} \leq Mint(C_i,C_j)$ 执行 5，否则执行 6
更新阈值及类标号
- 更新类标号： $Id(v_i), Id(v_j)$ 统一为 $Id(v_i)$
- 更新该类的不相似度阈值： $w_{ij} = w_{ij} + \frac{k}{|C_i| + |C_j|}$ （注意：由于不相似度小的边先合并，所以 $w_{ij}$ 即为合并后的最大边，即 $Int(C_i, C_j) = w_{ij}$ ）
如果 $n \leq N$ ，按顺序选择下一条边，转到 4

以上算法尚不能解决 孤立的同类区域，还需要做一些最近邻树的相似性度量

上一篇下一篇

猜你喜欢

热点阅读