CV03_05:基于图的图像分割

作者: 杨强AT南京 | 来源:发表于2020-03-18 08:36 被阅读0次

CV03_05:基于图的图像分割
图像分割方法
医学图像分割及应用
医学图像处理
LabVIEW彩色图像分割（基础篇—14）
graph cut算法
案例二图像分割
医疗图像分割方法综述
分割
图像分割中常用的评价标准

图像检测中使用了候选区域的生成算法，该算法使用了基于图的图像分割算法，这里专门整理备注下。

基于深度学习算法的对象侦测一般包含如下步骤：
1. 候选区域生成: 一张图像生成多个候选区域（推荐SS：Selective Search）
2. 特征提取：对每个候选区域，使用深度卷积网络提取特征（CNN）
3. 类别判断：使用分类器对抽取的特征分类，判别是否属于该类（SVM）
4. 位置精修：使用回归器精细修正候选框位置（Bounding box）

本主题专门解释候选区域的生成算法：
- 最简单的是采用滑窗（Sliding Window），因为枚举所有的候选区域，所以效率低下；
- 选择性搜索（Selective Search）
  - Selective Search 的前期工作就是利用Graph-Based Image Segmentation的分割算法。
关于Sliding Window算法的工作原理：
1. 对输入图像进行不同窗口大小的滑窗（方式：从左往右、从上到下）
2. 每次滑动时对当前窗口执行分类器(分类器是事先训练好的)，如果当前窗口得到较高的分类概率，则认为检测到了物体。
3. 对每个不同窗口大小的滑窗都进行检测后，会得到不同窗口检测到的物体标记，这些窗口大小会存在重复较高的部分
4. 最后采用非极大值抑制(Non-Maximum Suppression, NMS)的方法进行筛选
滑窗算法使用的示意图

使用滑窗方式侦测目标示意图

可以使用参数控制滑窗产生的数量：（可以参考OpenCV的级联分类器侦测函数的参数）
1. 使用滑窗增大因子，控制滑窗大小过于紧密而产生过多的滑窗。
2. 可以控制滑窗的滑动大小等。

Graph-Based Image Segmentation算法

算法的官方地址

url：http://cs.brown.edu/people/pfelzens/segment/

官网实现代码与论文入口截图

代码使用

使用make编译代码

代码编译

提示：
- 代码中有一个警告，不是错误，是编码者使用delete释放了私用new[]分配的内存。

命令的使用方式
- usage: ./segment sigma k min input(ppm) output(ppm)
- ppm（Portable Pixmap Format：像素映射图）是一种图像格式，由Jef Poskanzer 在1991年所创造的。
  - 该图像个有两个孪生格式：PBM（位图），PGM（灰度图）
  - ppm图像格式可以参考这篇文章：https://blog.csdn.net/kinghzkingkkk/article/details/70226214
再MacOS中保存为PPM图像

PPM图像格式保存

注意：
- 使用Mac的工具保存的ppm图像是p1,p2,p3格式，segment工具不支持读取。所以我们使用Python程序生成ppm图像。

两个版本的ppm格式比较

使用Python把jpeg的图像转换为ppm

import cv2

img = cv2.imread("gpu.jpeg")

# cv2.imshow("ppm", img)

# cv2.waitKey()

cv2.imwrite("seg.ppm", img)

segment工具使用

命令：

yangqiangdeMacBook-Pro:segment yangqiang$ ./segment 0.5 1000 100 seg_p6.ppm   out.ppm
loading input image.
processing
got 421 components
done! uff...thats hard work.

效果

基于图的图像分隔

基本思想

是由顶点集V（vertices）和边集E（edges）组成，表示为：
1. 顶点;
  - 在图像处理中即为单个的像素点就是顶点；
2. 连接一对顶点的边 $(v_i, v_j)$ 具有权重w(v_i, v_j)：
  -图像中的意义为像素之间的不相似度（dissimilarity）
图像的像素与不相似度构成的图是无向图：
- 没有方向的图称为无向图。

树：图中的子图满足下面条件就是可以构成树
- 子图中任何两个点都相连，并且没有回路。
- 比如下面粗线相连的顶点构成的子图就是一个树。如果i与h相连，就是回路，就不再是树。
示意图

无向图

最小生成树（MST,minimum spanning tree）

前提（这个数学已经证明）：连通的图都存在一个最小生成树。
最小生成树：
- 在一给定的无向图 $G = (V, E)$ 中， $(u, v)$ 代表连接顶点 $u$ 与顶点 $v$ 的边（即），而 $w(u, v)$ 代表此边的权重；
- 若存在为的子集（即）且为无循环图，使得最小，则此为的最小生成树。
  - 其中： $w(T) = \sum \limits _{(u,v) \in T} w(u,v)$

附录

Prim最小树生成算法

输入：
- 一个加权连通图，其中顶点集合为 $V$ ，边集合为 $E$ ；
初始化:
- $V_{new} = \{x\}$ ，其中 $x$ 为集合 $V$ 中的任一点（起始点）， $E_{new}= \{ \}$ ,为空；
重复下列操作，直到 $V_{new}= V$ ：
1. 在集合 $E$ 中选取权值最小的边 $<u, v>$ ，其中 $u$ 为集合 $V_{new}$ 中的元素，而 $v$ 不在 $V_{new}$ 集合当中，并且 $v \in V$ （如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
2. 将 $v$ 加入集合 $V_{new}$ 中，将 $<u, v>$ 边加入集合 $E_{new}$ 中；
输出：
- 使用集合 $V_{new}$ 和 $E_{new}$ 来描述所得到的最小生成树。

Kruskal最小生成树算法

设 $W_N=(V,\{E\})$ 是一个含有 $n$ 个顶点的连通网；
先构造一个只含 $n$ 个顶点，而边集为空的子图:
若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 $n$ 棵树的一个森林。
从网的边集 $E$ 中选取一条权值最小的边:
- 若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；
- 反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。
依次类推，直至森林中只有一棵树，也即子图中含有 $n-1$ 条边为止。

内部差：
- 一个连通区域（Component）内部的差（internal difference） $IntD$ ：就是一个最小生成树中最小权重的边。
- 可以先假定图已经简化成了最小生成树，一个分割区域包含若干个顶点，顶点之间通过最小生成树的边连接。这个内部差就是指分割区域中包含的最大边的权值。
  - $IntD(C) = \max \limits _{e \in MST(C, E)} w(e)$
区域差（Difference）：
- 是指两个分割区域 $C_1, C_2$ 之间顶点相互连接的最小边的权值。
  - $Dif(C_1, C_2) = \min \limits _{v_i \in C_1, v_j \in C_2} w(v_i, v_j)$
- 如果两个区域之间没有链接，则定义差为无穷大 $\infty$
区域分割的标准或者条件（Predicate）：
- 判断两个分割区域之间是否有明显的边界，主要是判断两个分割部分之间的差别相对于的大小，这里引入了一个阈值函数来控制两者之间的差值。
  - $D(C_1, C_2) = \begin{cases} true & if Dif(C_1, C_2) \gt Mint(C_1,C_2) \\ false & otherwise \end{cases}$
- 的定义如下：
  - $MInt(C_1, C_2) = \min(Int(C1) + \tau_{C_1}, Int(C_2) + \tau_{C_2} )$

上面与是两个阈值，阈值的作用主要是为了更好的控制分割区域边界的定义。
- 比较直观的理解，小分割区域的边界定义要强于大分割区域，否则可以将小分割区域继续合并形成大区域。在这里给出的阈值函数与区域的大小有关。
  - $\tau_{C} = \dfrac{k}{|C|}$
  - $|C|$ 指区域顶点个数，k是一个参数，可以根据不同的需求（主要根据图像的尺寸）进行调节。

分割算法

这个算法在原始的论文中有描述（E文）。

对于图G的所有边，按照权值进行排序（升序）
$S[0]$ 是一个原始分割，相当于每个顶点当做是一个分割区域
$q = 1,2,...,m$ 重复3的操作（ $m$ 为边的条数，也就是每次处理一条边）
根据上次 $S[q-1]$ 的构建,选择一条边 $o[q](v_i,v_j)$ ，
- 如果和在分割的互不相交的区域中，比较这条边的权值与这两个分割区域之间的最小分割内部差
  - 如果 $o[q](v_i,v_j) < MInt$ ，那么合并这两个区域，其他区域不变；
- 如果否，什么都不做。
最后得到的就是所求的分割 $S = S[m]$

提示：
- 在合并之前，可以对图像做一个高斯运算。
注意：
- 权重的计算方式很多种，可以采用距离，灰度差，或者如下(来自论文作者的源代码)：


static inline float diff(image<float> *r, image<float> *g, image<float> *b,
             int x1, int y1, int x2, int y2) {
  return sqrt(square(imRef(r, x1, y1)-imRef(r, x2, y2)) +
          square(imRef(g, x1, y1)-imRef(g, x2, y2)) +
          square(imRef(b, x1, y1)-imRef(b, x2, y2)));
}

实现代码参考

来自官方作者

#ifndef SEGMENT_IMAGE
#define SEGMENT_IMAGE

#include <cstdlib>
#include <image.h>
#include <misc.h>
#include <filter.h>
#include "segment-graph.h"

// random color
rgb random_rgb(){ 
  rgb c;
  double r;
  
  c.r = (uchar)random();
  c.g = (uchar)random();
  c.b = (uchar)random();

  return c;
}

// dissimilarity measure between pixels
static inline float diff(image<float> *r, image<float> *g, image<float> *b,
             int x1, int y1, int x2, int y2) {
  return sqrt(square(imRef(r, x1, y1)-imRef(r, x2, y2)) +
          square(imRef(g, x1, y1)-imRef(g, x2, y2)) +
          square(imRef(b, x1, y1)-imRef(b, x2, y2)));
}

/*
 * Segment an image
 *
 * Returns a color image representing the segmentation.
 *
 * im: image to segment.
 * sigma: to smooth the image.
 * c: constant for treshold function.
 * min_size: minimum component size (enforced by post-processing stage).
 * num_ccs: number of connected components in the segmentation.
 */
image<rgb> *segment_image(image<rgb> *im, float sigma, float c, int min_size,
              int *num_ccs) {
  int width = im->width();
  int height = im->height();

  image<float> *r = new image<float>(width, height);
  image<float> *g = new image<float>(width, height);
  image<float> *b = new image<float>(width, height);

  // smooth each color channel  
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      imRef(r, x, y) = imRef(im, x, y).r;
      imRef(g, x, y) = imRef(im, x, y).g;
      imRef(b, x, y) = imRef(im, x, y).b;
    }
  }
  image<float> *smooth_r = smooth(r, sigma);
  image<float> *smooth_g = smooth(g, sigma);
  image<float> *smooth_b = smooth(b, sigma);
  delete r;
  delete g;
  delete b;
 
  // build graph
  edge *edges = new edge[width*height*4];
  int num = 0;
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      if (x < width-1) {
    edges[num].a = y * width + x;
    edges[num].b = y * width + (x+1);
    edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x+1, y);
    num++;
      }

      if (y < height-1) {
    edges[num].a = y * width + x;
    edges[num].b = (y+1) * width + x;
    edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x, y+1);
    num++;
      }

      if ((x < width-1) && (y < height-1)) {
    edges[num].a = y * width + x;
    edges[num].b = (y+1) * width + (x+1);
    edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x+1, y+1);
    num++;
      }

      if ((x < width-1) && (y > 0)) {
    edges[num].a = y * width + x;
    edges[num].b = (y-1) * width + (x+1);
    edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x+1, y-1);
    num++;
      }
    }
  }
  delete smooth_r;
  delete smooth_g;
  delete smooth_b;

  // segment
  universe *u = segment_graph(width*height, num, edges, c);
  
  // post process small components
  for (int i = 0; i < num; i++) {
    int a = u->find(edges[i].a);
    int b = u->find(edges[i].b);
    if ((a != b) && ((u->size(a) < min_size) || (u->size(b) < min_size)))
      u->join(a, b);
  }
  delete [] edges;
  *num_ccs = u->num_sets();

  image<rgb> *output = new image<rgb>(width, height);

  // pick random colors for each component
  rgb *colors = new rgb[width*height];
  for (int i = 0; i < width*height; I++)
    colors[i] = random_rgb();
  
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      int comp = u->find(y * width + x);
      imRef(output, x, y) = colors[comp];
    }
  }  

  delete [] colors;  
  delete u;

  return output;
}

#endif

OpenCV中的实现调用

图像的图切割算法与选择性搜索在OpenCV有实现：
- opencv_contrib / ximgproc模块
- 也可以直接阅读源码

OpenCV的实现算法

GraphSegmentation类说明

cv::ximgproc::segmentation::GraphSegmentation Class核心三个参数：
1. k就是控制分割区域的边界；（控制子区域被包含区域合并）
2. sigma是高斯模糊使用的方差；
3. minSize最小大小。
返回的结果是：
- 与源图像一样的大小的矩阵，但是其中的元素是分割区域的id编号，编号从0开始，属于同一编号的就是同一个区域。

使用例子

%matplotlib inline
import cv2
import matplotlib.pyplot as plt

img = cv2.imread("gpu.jpeg")

gs = cv2.ximgproc.segmentation.createGraphSegmentation(sigma=1, k=300, min_size=100)
img_out = gs.processImage(img)

img_out.shape, img.shape

((1080, 1920), (1080, 1920, 3))

plt.imshow(img_out,cmap="gray")

<matplotlib.image.AxesImage at 0x11c043e80>

分割输出

img_out[1000:1080, 1800:1920]

array([[894, 894, 894, ..., 894, 894, 894],
       [894, 894, 894, ..., 894, 894, 894],
       [894, 894, 894, ..., 894, 894, 894],
       ...,
       [894, 894, 894, ..., 894, 894, 894],
       [894, 894, 894, ..., 894, 894, 894],
       [894, 894, 894, ..., 894, 894, 894]], dtype=int32)

附录

其他候选区域生成算法：
1. Objectness(需要权限)
  - 地址：http://groups.inf.ed.ac.uk/calvin/objectness/
2. Constrained Parametric Min-Cuts for Automatic Object Segmentation
  - 地址：http://www.maths.lth.se/sminchisescu/
3. Category Independent Object Proposals
  - 地址：http://vision.cs.uiuc.edu/proposals/
4. Selective Search
  - 地址：https://www.koen.me/research/selectivesearch/

CV03_05:基于图的图像分割
图像检测中使用了候选区域的生成算法，该算法使用了基于图的图像分割算法，这里专门整理备注下。基于深度学习算法的...
图像分割方法
主流医学图像分割方法：[1] 基于图论的分割方法中心思想：将图像映射为一张无向图（带权的无向图），图像中的像素点相...
医学图像分割及应用
截至目前，我们已经学习了很多关于图像分割的相关算法，就此，对图像的分割算法做以下总结：基于边界驱动的分割边缘检测...
医学图像处理
一、图像分割图像分割是前期的工作重点，主要使用了现成的软件来完成图像分割任务：3DMed（中国科学院自动化医学图...
LabVIEW彩色图像分割（基础篇—14）
基于目标颜色的彩色图像分割常包括色彩阈值处理（Color Threshold）和色彩分割（Color Segmen...
graph cut算法
注:本文内容主要参考图像分割之（二）Graph Cut（图割）和Graph Cuts 图分割学习 Graph cu...
案例二图像分割
基于连通域的图像分割案例可以用于物体计数和区域分割码上后期进行更改优化
医疗图像分割方法综述
图像分割的目的就是把目标从背景中提取出来, 分割过程主要基于图像的固有特征, 如灰度、纹理、对比度、亮度、彩色特征...
分割
1.阈值化2.基于边缘的分割边缘图像阈值化边缘松弛法 .边界跟踪 . 作为图搜索的边缘跟踪 .作为动态规划的边...
图像分割中常用的评价标准
在三维图像分割以及二维图像分割中，可能使用到的评价方法略有不同，但是总体上来说都可以分为基于面积或者基于轮廓的两种...