图像分割
图像分割是将⼀幅图像分割成有意义区域的过程。区域可以是图像的前景与背景或 图像中⼀些单独的对象。这些区域可以利⽤⼀些诸如颜⾊、边界或近邻相似性等特
征进⾏构建。
9.1 图割（Graph Cut）
Graph cuts是⼀种⼗分有⽤和流⾏的能量优化算法，在计算机视觉领域普遍应⽤于前背景分割（Image segmentation）、⽴体视觉（stereo vision）、抠图（Image matting）等。
此类⽅法把图像分割问题与图的最⼩割（min cut）问题相关联。⾸先⽤⼀个⽆向图G=<V，E>表⽰要分割的图像，V和E分别是顶点（vertex）和边（edge）的集合。此处的Graph和普通的Graph稍有不同。普通的图由顶点和边构成，如果边的有⽅向的，这样的图被则称为有向图，否则为⽆向图，且边是有权值的，不同的边可以有不同的权值，分别代表不同的物理意义。⽽Graph Cuts图是在普通图的基础上多了2个顶点，这2个顶点分别⽤符号”S”和”T”表⽰，统称为终端顶点。其它所有的顶点都必须和这2个顶点相连形成边集合中的⼀部分。所以Graph Cuts中有两种顶点，也有两种边。 第⼀种顶点和边是：第⼀种普通顶点对应于图像中的每个像素。每两个邻域顶点（对应于图像中每两个邻域像素）的连接就是⼀条边。这种边也叫n-links。 第⼆种顶点和边是：除图像像素外，还有另外两个终端顶点，叫S（source：源点，取源头之意）和T（sink：汇点，取汇聚之意）。每个普通顶点和这2个终端顶点之间都有连接，组成第⼆种边。这种边也叫t-links。
上图就是⼀个图像对应的s-t图，每个像素对应图中的⼀个相应顶点，另外还有s和t两个顶点。上图有两种边，实线的边表⽰每两个邻域普通顶点连接的边n-links，虚线的边表⽰每个普通顶点与s和t连接的边t-links。在前后景分割中，s⼀般表⽰前景⽬标，t⼀般表⽰背景。
图中每条边都有⼀个⾮负的权值we，也可以理解为cost（代价或者费⽤）。⼀个cut（割）就是图中边集合E的⼀个⼦集C，那这个割的cost（表⽰为|C|）就是边⼦集C的所有边的权值的总和。
Graph Cuts中的Cuts是指这样⼀个边的集合，很显然这些边集合包括了上⾯2种边，该集合中所有边的断开会导致残留”S”和”T”图的分开，所以就称为“割”。如果⼀个割，它的边的所有权值之和最⼩，那么这个就称为最⼩割，也就是图割的结果。⽽福特-富克森定理表明，⽹路的最⼤流max flow与最⼩割min cut相等。所以由Boykov和Kolmogorov发明的max-flow/min-cut算法就可以⽤来获得s-t图的最⼩割。这个最⼩割把图的顶点划分为两个不相交的⼦集S和T，其中s ∈S，t∈ T和S∪T=V 。这两个⼦集就对应于图像的前景像素集和背景像素集，那就相当于完成了图像分割。
图像分割可以看成pixel labeling（像素标记）问题，⽬标（s-node）的label设为1，背景（t-node）的label设为0，这个过程可以通过最⼩化图割来最⼩化能量函数得到。那很明显，发⽣在⽬标和背景的边界处的cut就是我们想要的（相当于把图像中背景和⽬标连接的地⽅割开，那就相当于把其分割了）。同时，这时候能量也应该是最⼩的。假设整幅图像的标签label（每个像素的label）为L= {l1,l2, lp }，其中li 为0（背景）或者1（⽬标）。那假设图像的分割为L时，图像的能量可以表⽰为：
E(L)=aR(L)+B(L)
其中，R(L)为区域项（regional term），B(L)为边界项（boundary term），⽽a就是区域项和边界项
之间的重要因⼦，决定它们对能量的影响⼤⼩。如果a为0，那么就只考虑边界因素，不考虑区域因素。E(L)表⽰的是权值，即损失函数，也叫能量函数，图割的⽬标就是优化能量函数使其值达到最⼩。
区域项：
其中Rp(lp)表⽰为像素p分配标签lp的惩罚，Rp(lp)能量项的权值可以通过⽐较像素p的灰度和给定的⽬标和前景的灰度直⽅图来获得，换句话说就是像素p属于标签lp的概率，我希望像素p分配为其概率最⼤的标签lp，这时候我们希望能量最⼩，所以⼀般取概率的负对数值，故t-link的权值如下：
Rp(1) = - ln Pr(Ip|’obj’)； Rp(0) = -ln Pr(Ip|’bkg’)
由上⾯两个公式可以看到，当像素p的灰度值属于⽬标的概率Pr(Ip|’obj’)⼤于背景Pr(Ip|’bkg’)，那么Rp(1)就⼩于Rp(0)，也就是说当像素p更有可能属于⽬标时，将p归类为⽬标就会使能量R(L)⼩。那么，如果全部的像素都被正确划分为⽬标或者背景，那么这时候能量就是最⼩的。
边界项：
其中，p和q为邻域像素，边界平滑项主要体现分割L的边界属性，B<p,q>可以解析为像素p和q之间不连续的惩罚，⼀般来说如果p和q越相似（例如它们的灰度），那么B<p,q>越⼤，如果他们⾮常不同，那么B<p,q>就接近于0。换句话说，如果两邻域像素差别很⼩，那么它属于同⼀个⽬标或者同⼀背景的可能性就很⼤，如果他们的差别很⼤，那说明这两个像素很有可能处于⽬标和背景的边缘部分，则被分割开的可能性⽐较⼤，所以当两邻域像素差别越⼤，B<p,q>越⼩，即能量越⼩。
总结：⽬标是将⼀幅图像分为⽬标和背景两个不相交的部分，运⽤图分割技术来实现。⾸先，图由顶点和边来组成，边有权值。那需要构建⼀个图，这个图有两类顶点，两类边和两类权值。普通顶点由图像每个像素组成，然后每两个邻域像素之间存在⼀条边，它的权值由上⾯说的“边界平滑能量项”来决定。还有两个终端顶点s（⽬标）和t（背景），每个普通顶点和s都存在连接，也就是边，边的权值由“区域能量项”Rp(1)来决定，每个普通顶点和t连接的边的权值由“区域能量项”Rp(0)来决定。这样所有边的权值就可以确定了，也就是图就确定了。这时候，就可以通过min cut算法来到最⼩的割，这个min cut就是权值和最⼩的边的集合，这些边的断开恰好可以使⽬标和背景被分割开，也就是min cut对应于能量的最⼩化。⽽min cut和图的max flow是等效的，故可以通过max flow算法来到s-t图的min cut。
在图割例⼦中将采⽤ python-graph ⼯具包，该⼯具包包含了许多⾮常有⽤的图算法，你可以在 le/p/python-graph/ 下载该⼯具包并查看⽂档。随后的例⼦⾥，我们要⽤到 maxi
mum_flow() 函数，该函数⽤ Edmonds-Karp 算法（/wiki/Edmonds-Karp_algorithm）计算最⼤流 / 最⼩割。采⽤⼀个完全⽤ Python 写成⼯具包的好处是安装容易且兼容性良好；不⾜是速度较慢。不过，对于⼩尺⼨图像，该⼯具包的性能⾜以满⾜我们的需求，对于较⼤的图像，需要⼀个更快的实现。
给出⼀个⽤ python-graph ⼯具包计算⼀幅较⼩的图 1 的最⼤流 / 最⼩割的简单例⼦：
from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import maximum_flow
gr = 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 是与汇点相连的节点。
9.1.1 从图像创建图像
给定⼀个邻域结构，我们可以利⽤图像像素作为节点定义⼀个图。这⾥我们将集中讨论最简单的像素四邻域和两个图像区域（前景和背景）情况。⼀个四邻域（4-neighborhood）指⼀个像素与其正上⽅、正下⽅、左边、右边的像素直接相连。
Graph cut的3x3图像分割⽰意图：我们取两个种⼦点（就是⼈为的指定分别属于⽬标和背景的两个像素点），然后我们建⽴⼀个图，图中边的粗细表⽰对应权值的⼤⼩，然后到权值和最⼩的边的组合，也就是（c）中的cut，即完成了图像分割的功能。
除了像素节点外，我们还需要两个特定的节点——“源”点和“汇”点，来分别代表图像的前景和背景。我们将利⽤⼀个简单的模型将所有像素与源点、汇点连接起来。
假定我们已经在前景和背景像素（从同⼀图像或从其他的图像）上训练出了⼀个贝叶斯分类器，我们就可以为前景和背景计算概率 pF(Ii) 和pB(Ii)。这⾥，Ii 是像素 i 的颜⾊向量。
现在我们可以为边的权重建⽴如下模型：
利⽤该模型，可以将每个像素和前景及背景（源点和汇点）连接起来，权重等于上⾯归⼀化后的概率。wij 描述了近邻间像素的相似性，相似像素权重趋近于 κ，不相似的趋近于 0。参数 σ 表征了随着不相似性的增加，指数次幂衰减到 0 的快慢。创建⼀个名为 的⽂件，将下⾯从⼀幅图像创建图的函数写⼊该⽂件中：
from pygraph.classes.digraph import digraph
from pygraph.algorithms.minmax import maximum_flow
import bayes
def 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_lables,prob = bc.classify(vim)
prob_fg = prob[0]
prob_bg = prob[1]
# ⽤m*n+2 个节点创建图
gr = digraph()
gr.add_nodes(range(m*n+2))
source = m*n # 倒数第⼆个是源点
sink = m*n+1 # 最后⼀个节点是汇点
# 归⼀化
for i in range(vim.shape[0]):
vim[i] = vim[i] / (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 ⽤于设置透明度。将下⾯函数增加到 中：
def show_labeling(im,labels):
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 = imsize
source = 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] = label
shape((m,n))
举例会读取⼀幅图像，从图像的两个矩形区域估算出类概率，然后创建⼀个图：
from scipy.misc import imresize
import graphcutstewart
im = array(Image.open('empire.jpg'))
电报码im = imresize(im,0.07,interp='bilinear')
size = im.shape[:2]
# 添加两个矩形训练区域
labels = zeros(size)
labels[3:18,3:18] = -1
labels[-18:-3,-18:-3] = 1
# 创建图
g = graphcut.build_bayes_graph(im,labels,kappa=1)
# 对图进⾏分割
res = graphcut.cut_graph(g,size)
双眼台风figure()
graphcut.show_labeling(im,labels)
figure()
imshow(res)
gray()
素娥篇
axis('off')
show()
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议