基于图的图像分割-工程源码

基于图的图像分割算法的作者提供了工程源码:Graph Based Image Segmentation

工程结构

工程结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.
├── convolve.h
├── COPYING
├── disjoint-set.h - 并查集实现
├── filter.h - 高斯滤波实现
├── image.h - 图像数据类实现
├── imconv.h
├── imutil.h
├── Makefile
├── misc.h
├── pnmfile.h - PPM文件解析
├── README
├── segment.cpp - main函数,解析命令行参数,调用图像加载,图像分割以及图像保存函数
├── segment-graph.h - Kruskal算法实现
└── segment-image.h - 图像分割功能实现入口:调用高斯滤波算法,创建边集,调用Kruskal算法,合并小分量以及图像赋值

关键元素解析

PPM

作者假定输入图像为PPM格式,具体参考PPM文件解析

文件中得到的图像数据是一个一维行向量

image

图像数据类,保存图像长宽和字节数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <class T>
class image {
public:
/* create an image */
image(const int width, const int height, const bool init = true);

/* delete an image */
~image();

/* init an image */
void init(const T &val);

/* copy an image */
image<T> *copy() const;

/* get the width of an image. */
int width() const { return w; }

/* get the height of an image. */
int height() const { return h; }

/* image data. */
T *data;

/* row pointers. */
T **access;

private:
int w, h;
};

rgb

结构体rgb保存单个彩色像素

1
typedef struct { uchar r, g, b; } rgb;

edge

结构体edge保存边坐标和边权重

1
2
3
4
typedef struct {
float w;
int a, b;
} edge;

构建边集时,创建一维edge类型数组edges,大小为width * height * 4,保存当前顶点与右上、右中、右下和中下顶点所连的边

uni_elt

结构体uni_elt保存每个分量的秩(用于合并优化)、父指针以及分量大小

universe

universe实现并查集数据结构,初始化对象时输入分量个数,每个分量保存为eni_elt,同时保存最终分量数目。利用路径压缩和按秩合并进行优化

并查集具体概念参考:[数据结构][图算法]并查集

关键函数解析

  • main:入口程序,解析命令行参数(sigma/k/min_size/input_path/output_path),完成图像分割
    • loadPPM:加载PPM文件,返回image<rgb>对象
    • segment_image:首先将彩色图像分离,分别进行高斯滤波,然后创建边集edges,再调用segment_graph函数进行分量合并,对返回的并查集对象u再次进行分量合并,去除小分量影响,最后通过随机颜色对图像赋值
      • smooth:高斯过滤
      • segment_graphKruskal算法实现,完成图像合并

示例

sigma=0.5, k=500, min_size=50