美文网首页
CV03_05:基于图的图像分割

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/
官网实现代码与论文入口截图

代码使用

  1. 使用make编译代码
代码编译
  • 提示:
    • 代码中有一个警告,不是错误,是编码者使用delete释放了私用new[]分配的内存。
  1. 命令的使用方式

    • 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
  2. 再MacOS中保存为PPM图像

PPM图像格式保存
  • 注意:
    • 使用Mac的工具保存的ppm图像是p1,p2,p3格式,segment工具不支持读取。所以我们使用Python程序生成ppm图像。
两个版本的ppm格式比较
  1. 使用Python把jpeg的图像转换为ppm
import cv2

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

# cv2.imshow("ppm", img)

# cv2.waitKey()

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

  1. 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)组成,表示为G=(V, E)
    1. 顶点v∈V;
      • 在图像处理中即为单个的像素点就是顶点;
    2. 连接一对顶点的边(v_i, v_j)具有权重w(v_i, v_j):
      -图像中的意义为像素之间的不相似度(dissimilarity)
  • 图像的像素与不相似度构成的图是无向图:
    • 没有方向的图称为无向图。
  • 树:图中的子图满足下面条件就是可以构成树

    • 子图中任何两个点都相连,并且没有回路。
    • 比如下面粗线相连的顶点构成的子图就是一个树。如果i与h相连,就是回路,就不再是树。
  • 示意图

无向图
  1. 最小生成树(MST,minimum spanning tree)
  • 前提(这个数学已经证明):连通的图都存在一个最小生成树。

  • 最小生成树:

    • 在一给定的无向图G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即),而w(u, v) 代表此边的权重;
    • 若存在 TE 的子集(即)且为无循环图,使得 w(T) 最小,则此TG的最小生成树。
      • 其中:w(T) = \sum \limits _{(u,v) \in T} w(u,v)

附录

Prim最小树生成算法

  1. 输入:

    • 一个加权连通图,其中顶点集合为V,边集合为E
  2. 初始化:

    • V_{new} = \{x\},其中x为集合V中的任一点(起始点),E_{new}= \{ \},为空;
  3. 重复下列操作,直到V_{new}= V

    1. 在集合E中选取权值最小的边<u, v>,其中u为集合V_{new}中的元素,而v不在V_{new}集合当中,并且v \in V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);
    2. v加入集合V_{new}中,将<u, v>边加入集合E_{new}中;
  4. 输出:

    • 使用集合V_{new}E_{new}来描述所得到的最小生成树。

Kruskal最小生成树算法

  1. W_N=(V,\{E\}) 是一个含有 n个顶点的连通网;

  2. 先构造一个只含 n 个顶点,而边集为空的子图:
    若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有n棵树的一个森林。

  3. 从网的边集 E 中选取一条权值最小的边:

    • 若该条边的两个顶点分属不同的树,则将其加入子图,也就是说,将这两个顶点分别所在的两棵树合成一棵树;
    • 反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。
  4. 依次类推,直至森林中只有一棵树,也即子图中含有n-1条边为止。


  1. 内部差:

    • 一个连通区域(Component)内部的差(internal difference)IntD:就是一个最小生成树中最小权重的边。
    • 可以先假定图G已经简化成了最小生成树 MST,一个分割区域C包含若干个顶点 ,顶点之间通过最小生成树的边连接。这个内部差就是指分割区域C中包含的最大边的权值。
      • IntD(C) = \max \limits _{e \in MST(C, E)} w(e)
  2. 区域差(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

  3. 区域分割的标准或者条件(Predicate):

    • 判断两个分割区域之间是否有明显的边界,主要是判断两个分割部分之间的差别Dif相对于MInt的大小,这里引入了一个阈值函数\tau 来控制两者之间的差值。
      • 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的定义如下:
      • MInt(C_1, C_2) = \min(Int(C1) + \tau_{C_1}, Int(C_2) + \tau_{C_2} )
  • 上面\tau_{C_1}\tau_{C_2}是两个阈值,阈值的作用主要是为了更好的控制分割区域边界的定义。
    • 比较直观的理解,小分割区域的边界定义要强于大分割区域,否则可以将小分割区域继续合并形成大区域。在这里给出的阈值函数与区域的大小有关。
      • \tau_{C} = \dfrac{k}{|C|}
      • |C|指区域顶点个数,k是一个参数,可以根据不同的需求(主要根据图像的尺寸)进行调节。

分割算法

  • 这个算法在原始的论文中有描述(E文)。
  1. 对于图G的所有边,按照权值进行排序(升序)

  2. S[0]是一个原始分割,相当于每个顶点当做是一个分割区域

  3. q = 1,2,...,m 重复3的操作(m为边的条数,也就是每次处理一条边)

  4. 根据上次S[q-1]的构建,选择一条边o[q](v_i,v_j)

    • 如果v_iv_j在分割的互不相交的区域中,比较这条边的权值与这两个分割区域之间的最小分割内部差MInt
      • 如果o[q](v_i,v_j) < MInt,那么合并这两个区域,其他区域不变;
    • 如果否,什么都不做。
  5. 最后得到的就是所求的分割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.基于边缘的分割 边缘图像阈值化 边缘松弛法 .边界跟踪 . 作为图搜索的边缘跟踪 .作为动态规划的边...

  • 图像分割中常用的评价标准

    在三维图像分割以及二维图像分割中,可能使用到的评价方法略有不同,但是总体上来说都可以分为基于面积或者基于轮廓的两种...

网友评论

      本文标题:CV03_05:基于图的图像分割

      本文链接:https://www.haomeiwen.com/subject/pdnfyhtx.html