CV03_05:基于图的图像分割

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

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

基于深度学习算法的对象侦测一般包含如下步骤：
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:基于图的图像分割

Graph-Based Image Segmentation算法

算法的官方地址

代码使用

基本思想

附录

Prim最小树生成算法

Kruskal最小生成树算法

分割算法

实现代码参考

OpenCV中的实现调用

GraphSegmentation类说明

使用例子

附录

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读