Python中基于图的图像分割
问题定义和基本思想（摘自本文）
令G =（V，E）是一个无向图，其中顶点vi∈V，待分割的元素集，并且边缘（vi，vj）∈E对应于成对的相邻顶点。每个边缘（vi，vj）∈E具有对应的权重w（（vi，vj）），这是相邻元素vi和vj之间相异性的非负度量。      
在图像分割的情况下，V中的元素是像素，边缘的权重是对该边缘连接的两个像素之间相异程度的某种度量（例如，强度，颜色，运动，位置或其他局部属性）。
特别是对于实施这里所描述的，边缘权重函数基于所述绝对强度差（在YIQ由边缘连接的像素之间的空间），  W（（六，VJ））= | I（PI） - I（PJ） | 。     
在基于图的方法中，分段S是将V划分为多个分量的过程
，以使每个分量（或区域）C∈S对应
于图中G0 =（V，E0）的连接分量，其中E0?E。
换句话说，任何分割都是由E中边缘的子集引起的。测量分割质量的方法有很多，但总的来说，我们希望组件中的元素相似，而不同组件中的元素不相似。
这意味着同一组件中两个顶点之间的边缘应具有较低的权重，而不同组件中两个顶点之间的边缘应具有较高的权重。
下图显示了算法中的步骤。该算法与用于计算无向图的MST的Kruskal算法非常相似。   
f17.png
阈值函数τ控制两个组件之间的差异必须大于其内部差异的程度，以便在它们之间有边界的证据。  
对于小组件，Int（C）不能很好地估计数据的局部特征。在极端情况下，当| C | = 1，Int（C）=0。因此，基于组件大小的阈值函数 τ（C）= k / | C |。需要使用， 其中| C | 表示C的大小，k是一些常数。   
也就是说，对于小零件，我们需要更强有力的边界证据。实际上，k设置观察范围，因为较大的k会导致对较大分量的偏好。
通常， 为了补偿数字化伪像，在计算边缘权重之前，先使用高斯滤波器稍微平滑图像。我们始终使用σ= 0.8的高斯，它不会对图像产生任何可见变化，但有助于消除伪影。  
以下python代码显示了如何创建图形。
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
import numpy as np
from scipy import signal
import matplotlib.image as mpimg
def gaussian_kernel(k
    # generate a (2k+1)x(2k+1) gaussian kernel with mean=0 and sigma = s
    probs = [exp(-z*z/(2*s*s))/sqrt(2*pi*s*s) for z in range(-k
return np.outer(probs
def create_graph(imfile
    # create the pixel graph with edge weights as dissimilarities
     rgb = mpimg.imread(imfile)[:
     gauss_kernel = gaussian_kernel(sz
     for i in range(3):
         rgb[:
     yuv = rgb2yiq(rgb)
     (w
     edges = {}
     for i in range(yuv.shape[0]):
         for j in range(yuv.shape[1]):
             #compute edge weight for nbd pixel nodes for the node i
             for i1 in range(i-1
                 for j1 in range(j-1
                     if i1 == i and j1 == j: continue
                     if i1 >= 0 and i1 = 0 and j1 < h:
                        wt = np.abs(yuv[i
                        n1
                        edges[n1
     return edges
一些结果
图像取自纸张本身或互联网。下图和动画显示了根据组件内部差异，通过迭代合并组件（通过选择最小权重边缘）进行分割的结果。
尽管作者在论文中将参数k的最佳值描述为300左右，但是由于在此实现中，像素RGB值被规范化（值在0 – 1之间），然后转换为YIQ值和YIQ强度用于计算权重（通常很小），在这种情况下效果最好的k值为0.001-0.01。
从下面的结果可以看出，参数k的值越高，最终分量的大小越大，结果中的分量数越少。
还显示了最小生成树的创建，图中显示的红色边缘 是算法选择的用于合并组件的边缘。
输入图像
            player.png
参数k的两个不同值的输出图像
player_k_0.001.gif
player_k_0.01.gif
out_ 0.001player.png
out_ 0.010player.png
经过几次迭代后创建的森林
mst1
输入图像
爬坡道
参数k的两个不同值的输出图像
hill_k_0.01
out_ 0.010hill.png
hill_k_0.001
out_ 0.001hill.png
经过几次迭代后创建的森林
mst3.png
输入图像
鹦鹉
输出分割图像
鹦鹉_k_0.001out_ 0.001parrot_Dark2.pngout_ 0.001parrot_hot.png
输入图像
道路2
分段输出图像
road2_k_0.01
out_ 0.001road2_Set1.png
输入图像
路
参数k的两个不同值的输出图像
road_k_0.001
out_ 0.001road.png
road_k_0.01out_ 0.010road.png
经过几次迭代后创建的森林
mst2.png
  输入图像（UMBC）
             umbc.png
分段输出图像
umbc_k_0.001out_ 0.001umbc.png
    我NPUT图片
nj.png
k = 0.001的分段输出图像
out_ 0.001nj.png
    我NPUT图片
手
k = 0.001的分段输出图像
ring_k_0.001
    我NPUT图片
鲜花2
k = 0.001的分段输出图像
out_ 0.001flowers2.png
    我NPUT图片（肝）
肝
分段输出图像
out_ 0.001liver.pngout_ 0.010liver.png
    我NPUT图片
建造
具有不同k值的分段输出图像
building_k_0.01
out_ 0.001building.png out_ 0.010building.png
    我NPUT图片
框号056
分割输出图像
out_ 0.001frame056.png
    我NPUT图片
维克
不同k的分段输出图像
题库