图像分割是将一幅图像分割成有意义区域的过程。区域可以是图像的前景与背景或图像中一些单独的对象。这些区域可以利用一些诸如颜色、边界或近邻相似性等特征进行构建。本章中，我们将看到一些不同的分割技术。

1 图割（Graph Cut）

图论中的图（graph）是由若干节点（有时也称为顶点）和连接节点的边构成的集合。下图给出了一个示例。边可以是有向的或无向的，并且这些可能有与它们相关联的权重。

图割是将一个有向图分隔成两个互不相交的集合，可以用来解决很多计算机视觉方面的问题，诸如立体深度重建、图像拼接和图像分割等计算机视觉方面的不同问题。从图像像素和像素的近邻创建一个图并引入一个能量或代价函数，我们有可能利用图割方法将图像分割成两个或多个区域。图割的基本思想是，相似且彼此相近的像素应该划分到同一区域。

图割C（C是图中所有边的集合）的代价函数定义为所有割边的权重求和相加：$E_{cut}=\sum_{(i,j)\in C}w_{ij}$w_ij是图中节点i到节点j的边（i，j）的权重，并且是对割C所以的边进行求和。

图割图像分割的思想是用图来表示图像，并对图进行划分以使得代价E_cut最小。在用图表示图像时，增加两个额外的节点，即源点和汇点；并仅考虑那些将源点和汇点分开的割。

寻找最小割（minimum cut）等同于在源点和汇点间寻找最大流（maximum flow）。此外，很多高效的算法都可以解决这些最大流、最小割的问题。

这里给出一个用python-graph工具包计算一幅较小的图的最大流、最小割的简单例子（上面的图例）：

from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import maximum_flowgr = digraph()
gr.add_nodes([0,1,2,3])gr.add_edge((0,1), wt=4)
gr.add_edge((1,2), wt=3)
gr.add_edge((2,3), wt=5)
gr.add_edge((0,2), wt=3)
gr.add_edge((1,3), wt=4)
flows,cuts = maximum_flow(gr, 0, 3)
print ('flow is:' , flows)
print ('cut is:' , cuts)

首先创建有4个节点的有向图，4个节点的索引分别0…3，然后用add_edge()增添边并为每条边指定特定的权重。边的权重用来衡量边的最大流容量。以节点0为源点，3为汇点，计算最大流。上面两个python字典包含了流穿过每条边和每个节点的标记：0是包含源点的部分，1是与汇点相连的节点。你可以手工验证这个割确实是最小的。

1.1 从图像创建图

给定一个邻域结构，我们可以利用图像像素作为节点定义一个图。这里我们将集中讨论最简单的像素四邻域和两个图像区域（前景和背景）情况。一个四邻域（4-neighborhood）指一个像素与其正上方、正下方、左边、右边的像素直接相连。

除了像素节点外，我们还需要两个特定的节点——源点和汇点，来分别代表图像的前景和背景。我们将利用一个简单的模型将所有像素与源点、汇点连接起来。

下面给出创建这样一个图的步骤：
1.每个像素节点都有一个从源点的传入边；
2.每个像素节点都有一个到汇点的传出边；
3.每个像素节点都有一条传入边和传出边连接到它的近邻。

为确定边的权重，需要一个能够确定这些像素点之间，像素点与源点、汇点之间边的权重（表示那条边的最大流）的分割模型。与前面一样，像素i与像素j之间的边的权重记为w_ij，源点到像素i的权重记为w_si，像素i到汇点的权重记为w_it。

让我们先回顾一下上一章中在像素颜色值上用朴素贝叶斯分类器进行分类的知识。假定我们已经在前景和背景像素（从同一图像或从其他的图像）上训练出了一个贝叶斯分类器，我们就可以为前景和背景计算概率p_F（I_i）和p_B（I_i）。这里，I_i是像素i的颜色向量。

现在我们可以为边的权重建立如下模型：$w_{si}=\frac{p_F(I_i)}{p_F(I_i)+p_B(I_i)}$ $w_{it}=\frac{p_B(I_i)}{p_F(I_i)+p_B(I_i)}$$w_{ij}=\kappa e^{-|I_i-I_j|^2/\sigma}$利用该模型，可以将每个像素和前景及背景（源点和汇点）连接起来，权重等于上面归一化后的概率。w_ij描述了近邻间像素的相似性，相似像素权重趋近与k，不相似的趋近于0。参数σ表征了随着不相似性的增加，指数次幂衰减到0的快慢。

下面创建一个名为 graphcut.py 的文件，从一幅图像中创建图的函数：

from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import maximum_flow
import bayesdef build_bayes_graph(im,labels,sigma=1e2,kappa=2):"""从像素四邻域建立一个图，前景和背景（前景用1标记，背景用-1标记，其他的用0标记）由labels决定，并用朴素贝叶斯分类器建模"""m,n = im.shape[:2]#每行是一个像素的RGB向量vim = im.reshape((-1,3))#前景和背景(RGB)foreground = im[labels==1].reshape((-1,3))background = im[labels==-1].reshape((-1,3))train_data = [foreground,background]#训练朴素贝叶斯分类器bc = bayes.BayesClassifier()bc.train(train_data)#获取所有像素的概率bc_labels,prob = bc.classify(vim)prob_fg = prob[0]prob_bg = prob[1]#用m*n+2个节点创建图gr = digraph()gr.add_node(range(m*n+2))source = m*n #倒数第二个是源点sink = m*n+1 #最后一个节点是汇点#归一化for i in range(vim.shape[0]):vim[i] = vim[i]/linalg.norm(vim[i])#遍历所有的节点，并添加边for i in range(m*n):#从源点添加边gr.add_edge((source,i),wt=(prob_fg[i]/(prob_fg[i]+prob_bg[i])))#向汇点添加边gr.add_edge((i,sink),wt=(prob_bg[i]/(prob_fg[i]+prob_bg[i])))#向相邻节点添加边if i%n !=0 : #左边存在edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i-1])**2)/sigma)gr.add_edge((i,i-1),wt=edge_wt)if (i+1)%n !=0 : #右边存在edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i+1])**2)/sigma)gr.add_edge((i,i+1),wt=edge_wt)if i//n !=0 : #上边存在edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i-n])**2)/sigma)gr.add_edge((i,i-n),wt=edge_wt)if i//n !=m-1 : #下左边存在edge_wt = kappa*exp(-1.0*sum((vim[i]-vim[i+n])**2)/sigma)gr.add_edge((i,i+n),wt=edge_wt)return gr

在这个函数中，用1标记前景训练数据、用-1标记背景训练数据的一幅标记图像。基于这种标记，在RGB值上可以训练出一个朴素贝叶斯分类器，然后计算每一像素的分类概率，这些计算出的分类概率便是从源点出来和到汇点去的边的权重，由此可以创建一个节点为n*m+2的图。注意源点和汇点的索引，为了简化像素的索引，将最后的两个索引作为源点和汇点的索引。

为了在图像上可视化覆盖的标记区域，可以利用contourf()函数填充图像（这里指带标记图像）等高线间的区域，参数alpha用于设置透明度。图建立起来后便需要在最优位置对图进行分割，cut_graph() 函数可以计算最小割并将输出结果重新格式化为一个带像素标记的二值图像。 添加下面的内容到 graphcut.py 中：

def show_labeling(im, labels):"""显示图像的前景和背景区域。前景labels=1,背景labels=-1,其他labels=0"""imshow(im)contour(labels, [-0.5, 0.5])contourf(labels, [-1, -0.5], colors='b', alpha=0.25)contourf(labels, [0.5, 1], colors='r', alpha=0.25)axis('off')def cut_graph(gr, imsize):"""用最大流对图gr进行分割，并返回分割结果的二值标记"""m, n = imsizesource = m * n  # 倒数第二个节点是源点sink = m * n + 1  # 倒数第一个是汇点# 对图进行分割flows, cuts = maximum_flow(gr, source, sink)# 将图转为带有标记的图像res = zeros(m * n)for pos, label in cuts.items()[:-2]:  # 不要添加源点/汇点res[pos] = labelreturn res.reshape((m, n))

需要再次注意源点和汇点的索引，需要将图像的尺寸作为输入去计算这些索引，在返回分割结果之前要对输出结果进行reshape()操作。割以字典返回，需要将它复制到分割标记图像中，这通过返回列表（键，值）的.iten() 方法完成。

编写实验代码：读取一幅图像，从图像的两个矩形区域估算出类概率，然后创建一个图：

from scipy.misc import imresize
from PCV.tools import graphcut
from PIL import Image
from numpy import *
from pylab import *im = array(Image.open("empire.jpg"))
im = imresize(im, 0.07, interp='bilinear')
size = im.shape[:2]
# add two rectangular training regions
labels = zeros(size)
labels[3:18, 3:18] = -1
labels[-18:-3, -18:-3] = 1
# create graph
g = graphcut.build_bayes_graph(im, labels, kappa=2)  # k决定领进像素间的相对权重# cut the graph
res = graphcut.cut_graph(g, size)
figure()
graphcut.show_labeling(im, labels)
figure()
imshow(res)
gray()
axis('off')
show()

变量kappa（方程中的K）决定了近邻像素间边的相对权重。上图k值为1，改变K值分割的效果如下所示，分别是k=2和k=5的情况；随着K值增大，分割边界将变得更平滑，并且细节部分也逐步丢失。你可以选择根据自己应用的需要及想要获得的结果类型来选择合适的K值。

1.2 用户交互式分割

利用一些方法可以将图割分割与用户交互结合起来，形成用户交互式分割。例如，用户可以在一幅图像上为前景和背景提供一些标记。另一种方法就是利用边界框或“lasso”工具选择一个包含前景的区域。

下面给出一个完整的例子。实验会载入一幅图像及对应的标注信息，然后将其传递到我们的图割路径中：

from scipy.misc import imresize
from PCV.tools import graphcut
from PIL import Image
from numpy import *
from pylab import *def create_msr_labels(m, lasso=False):""" Create label matrix for training fromuser annotations. """labels = zeros(im.shape[:2])# backgroundlabels[m == 0] = -1labels[m == 64] = -1# foregroundif lasso:labels[m == 255] = 1else:labels[m == 128] = 1return labels# load image and annotation map
im = array(Image.open('empire.jpg'))
m = array(Image.open('empire.bmp'))
# resize
scale = 0.1
im = imresize(im, scale, interp='bilinear')
m = imresize(m, scale, interp='nearest')
# create training labels
labels = create_msr_labels(m, False)
# build graph using annotations
g = graphcut.build_bayes_graph(im, labels, kappa=2)# cut graph
res = graphcut.cut_graph(g, im.shape[:2])
# remove parts in background
res[m == 0] = 1
res[m == 64] = 1# plot the result
figure()
imshow(res)
gray()
xticks([])
yticks([])
savefig('labelplot.pdf')

从上面结果可知，前景和背景容易分开色彩反差较大的图像中，图像分割得比较好，但是在颜色复杂的图像中，分割效果并没有那么好。

2 利用聚类进行分割

上一节的图割问题通过在图像的图上利用最大流、最小割找到了一种离散解决方案。在本节，我们将看到另一种分割图像图的方法，即基于谱图理论的归一化分割算法，它将像素相似和空间近似结合起来对图像进行分割。

该方法来自定义一个分割损失函数，该损失函数不仅考虑了组的大小而且还用划分的大小对该损失函数进行“归一化”。该归一化后的分割公式将上一节方程中分割损失函数修改为：$E_{ncut}=\frac{E_{cut}}{\sum_{i\in A}w_{ix}}+\frac{E_{cut}}{\sum_{j\in B}w_{jx}}$A 和 B 表示两个割集，并在图中分别对A 和 B 中所有其他节点（函数进行“归一化”这里指图像像素）的权重求和相加，相加求和项称为 association。对于那些像素与其他像素具有相同连接数的图像，它是对划分大小的一种粗糙度量方式。

定义w为边的权重矩阵，矩阵中的元素w_ij为连接像素i和像素j边的权重。D为对w每行元素求和后构成的对角矩阵，即$D=diag(d_i),d_i=\sum_jw_{ij}$。归一化分割可以通过最小化下面的优化问题而求得：$min_y\frac{y^T(D-W)y}{y^TDy}$向量y包含的是离散标记，这些离散标记满足对于b为常熟$y_i\in \{1,-b\}$（即y只可以取这两个值）的约束，y^TD求和为0.由于这些约束条件，该问题不太容易求解。

通过松弛约束条件并让y yy取任意实数，该问题可以变为一个容易求解的特征分解问题。这样求解的缺点是你需要对输出设定阈值或进行聚类，使它重新成为一个离散分割。

松弛该问题后，该问题便成为求解拉普拉斯矩阵特征向量问题：$L=D^{-1/2}WD^{-1/2}$正如谱聚类情形一样，现在的难点是如何定义像素间边的权重w_ij。利用原始归一化割中的边的权重，通过下式给出连接像素i和像素j的边的权重：$w_{ij}=e^{-|I_i-I_j|^2/\sigma_g}e^{-|x_i-x_j|^2/\sigma_d}$式中第一部分度量像素I_i和I_j之间的像素相似性，I_i(I_j)定义为RGB向量或灰度值；第二部分度量图像中x_i和x_j的接近程度，x_i(x_j)定义了每个像素的坐标矢量，缩放因子σ _g和σ_d决定了相对尺度和每一部件趋近0的快慢。

# -*- coding: utf-8 -*-from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import maximum_flow
import bayes
import numpy
import scipydef ncut_graph_matrix(im,sigma_d=1e2,sigma_g=1e-2):"""创建用于归一化割的矩阵，其中sigma_d和sigma_g是像素距离和像素相似性的权重参数"""m,n = im.shape[:2]N = m*n#归一化，并创建RGB或灰度特征向量if len(im.shape)==3:for i in range(3):im[:,:,i] = im[:,:,i] / im[:,:,i].max()vim = im.reshape((-1,3))else:im = im / im.max()vim = im.flatten()#x,y坐标用于距离计算xx,yy = meshgrid(range(n),range(m))x,y = xx.flatten(),yy.flatten()#创建边线权重矩阵W = zeros((N,N),'f')for i in range(N):for j in range(i,N):d = (x[i]-x[j])**2+(y[i]-y[j])**2W[i,j] = W[j,i] = exp(-1.0*sum((vim[i]-vim[j])**2)/sigma_g)*exp(-d/sigma_d)return W

这个函数获取图像数组，并利用输入的彩色图像RGB值或灰度图像的灰度值创建一个特征向量。由于边的权重包含了距离部件，对于每个像素的特征向量，利用meshgrid()函数来获取x和y的值，然后该函数会在N个像素数上循环，并在N×N归一化割矩阵W中填充值。

可以顺序分割每个特征向量或获取一些特征向量对它们进行聚类来计算分割结果。这里选择第二种方法，它不需要修改任意分割数也能正常工作。将拉普拉斯矩阵进行特征分解后的前ndim个特征向量合并在一起构成矩阵W，并对这些像素进行聚类。下面函数实现了这种聚类过程：

def cluster(S,k,ndim):""" 从相似性矩阵进行谱聚类 """# 检查对称性if sum(abs(S-S.T)) > 1e-10:print 'not symmetric'# 创建拉普拉斯矩阵rowsum = sum(abs(S),axis=0)D = diag(1 / sqrt(rowsum + 1e-6))L = dot(D,dot(S,D))# 计算 L 的特征向量U,sigma,V = linalg.svd(L,full_matrices=False)# 从前 ndim 个特征向量创建特征向量# 堆叠特征向量作为矩阵的列features = array(V[:ndim]).T# k-meansfeatures = whiten(features)centroids,distortion = kmeans(features,k)code,distance = vq(features,centroids)return code,V

# -*- coding: utf-8 -*-
from numpy import *
from PIL import Image
from PCV.tools import graphcut
import ncut
from scipy.misc import imresize
from pylab import *im = array(Image.open("C-uniform01.ppm"))
m,n = im.shape[:2]#调整图像的尺寸大小为（wid,wid）
wid = 50
rim = imresize(im,(wid,wid),interp='bilinear')
rim = array(rim,'f')#创建归一化割矩阵
A = ncut.ncut_graph_matrix(rim,sigma_d=1,sigma_g=1e-2)#聚类
code,V = ncut.cluster(A,k=3,ndim=3)#变换到原来的图像大小
codeim = imresize(code.reshape(wid,wid),(m,n),interp='nearest')#绘制分割结果
figure()
subplot(121)
imshow(im)
title('分割前图像')
subplot(122)
imshow(codeim)
title('分割后图像')
gray()
show()

上面实验利用归一化分割算法分割图像，用到了静态手势“C”、“拳头”和小人图像，聚类数k均设置为3，都会显示三部分信息，把上面的图像都分成三部分。在上面的结果中，保持所有参数都一致，只修改了图像的内容，对图像进行阈值处理不会给出相同的结果，对RGB值或灰度值进行聚类也一样，其中原因是它们没有考虑像素的近邻。

3 变分法

诸如 ROF 降噪、K-means 和 SVM 的例子，这些都是优化问题。当优化的对象是函数时，该问题称为变分问题，解决这类问题的算法称为变分法。 我们看一个简单而有效的变分模型。

下面看一个简单而有效的变分模型。Chan-Vese 分割模型对于待分割图像区域假定一个分片常数图像模型。这里我们集中关注两个区域的情形，比如前景和背景，不过这个模型也可以拓展到多区域。

如果我们用一组曲线Γ将图像分离成两个区域Ω₁和Ω₂，分割是通过最小化 Chan-Vese 模型能量函数给出的：$E(\Gamma)=\lambda length(\Gamma)+\int_{\Omega_1}(I-c_1)^2dx+\int_{\Omega_2}(I-c_2)^2dx$该能量函数用来度量与内部平均灰度常数 c1 和外部平均灰度常数 c2 的偏差。这里这两个积分是对各自区域的积分，分离曲线 Γ 的长度用以选择更平滑的方案。

from PIL import Image
from PCV.tools import graphcut
from PCV.tools import rof
from scipy.misc import imresize
from pylab import *im = array(Image.open("boy_on_hill.jpg").convert('L'))
U,T = rof.denoise(im,im,tolerance=0.01)
t = 0.4  #阈值
title('Original Image')
imshow(im)
import scipy.misc
scipy.misc.imsave('result.pdf',U<t*U.max())

为确保得到足够的迭代次数，调低ROF迭代终止时的容忍阈值。利用ROF降噪最小化CV模型，得到如上面的分割结果。可以看出，图像灰度级越复杂，ROF迭代次数越多，降噪过程越久。