刘璐

（沈阳航空航天大学计算机学院，沈阳 110000）

基于余弦相似度的Graph Cuts序列图像分割算法

刘璐

（沈阳航空航天大学计算机学院，沈阳 110000）

传统Graph Cuts算法容易出现漏分割、误分割现象，分割效果有待提高，且需要人工交互分割效率不高。针对传统算法的不足，提出基于余弦相似度的Graph Cuts序列分割图像算法。使用最大余弦相似度构造能量函数的区域项，计算超像素与种子聚类区域的最大余弦相似度。使用余弦相似度和颜色相似度来构造边界项，计算邻域超像素的颜色和相对距离特征相似度。将该算法与传统Graph Cuts算法进行分割结果比较精确率和召回率等均有提高，漏报率降和虚报率明显降低。算法应用于序列图像分割，减少人工交互，提高分割效率。

Graph Cuts算法；图像分割；余弦相似度；序列图像

0 引言

图像分割这一技术自从发展以来，有很多系统的、科学的分割方法。20世纪90年代首次成功应用图论理论在图像分割的研究中，引起了学者们对于图论理论及其应用的热烈关注，目前在图像分割、纹理合成、图像恢复、图像去噪、三维重构、运动目标检测和立体匹配等图像处理技术中都有广泛应用。

1 基于图论的分割算法研究现状

Boykov等人[1]首次在图像分割领域应用 Graph Cuts算法，构造出S/T图，并用区域项和边界项计算S/ T图的边的权值，最后通过最小化能量函数得到最小割，即得到分割结果。该算法优点是对噪声不敏感，不容易出现过分割。不足之处是当前后背景颜色相近时，趋于较短分割，而且由于需要人工交互，所以对于多幅图像分割处理起来效率不高，不能实现实时性。从Graph Cuts算法的出现就引起了研究人员对图论分割的关注，对以后的图论算法产生重要影响。

Rother等人[2]提出的基于高斯混合模型的Grab Cut算法，就是在Graph Cuts算法进行的改进，它通过不断迭代的方式提高了参数估计的准确性，并且简化了交互改善了用户体验。但是当选取的种子在区域外时，分割效果较差。2004年，Li Y等人[3]提出了Lazy snap⁃ping方法，利用Graph Cuts算法对图像分割得到粗分割，然后通过边界上的多边形顶点进行调整编辑得到细分割，缺点是对于大规模图像处理速度较慢，需要大量人工交互。文献[4]描述了GCBAC算法，它结合了主动轮廓算法与Graph Cuts算法，分割效果要比单独应用Graph Cuts算法好，但是该方法需要大量的训练模板，算法复杂度高，而且过于依赖初始轮廓。Rother等人[5]提出的co-segmentation方法，将Grab Cut算法和SVM算法相结合，该方法在每一层迭代经过SVM算法学习特征后得到超像素，将超像素的相似特征作为Grab Cut算法的分割约束进行图像分割，好处是只需要较少的交互，实现了无监督学习，但是算法复杂度高，时间消耗大。

本文对Graph Cuts算法进行研究并提出使用余弦相似度构造能量函数的区域项和边界项，分别描述原始Graph Cuts算法和本文算法的基本原理，通过实验对比验证本文算法分割结果更准确，误分割和漏分割的现象明显减少，并且应用于多幅序列图像分割，减少交互和算法时间。

2 Graph Cuts算法

Graph Cuts算法核心思想是，用户通过人机交互对图像中的目标和背景标记不同的标号，作为分割图像的硬约束条件，然后建立相应的S/T图，根据边的权值构造合适的能量函数，利用最大流/最小割算法来计算最优化的全局代价函数，即求解S/T图的最小割，从而实现图像分割。

首先把图像映射为S/T图，除了有普通顶点还包含两个终端顶点，分别为S源点和T汇点。S/T图中有两种边，一种边是n-links，由相邻像素连接组成，另一种边是t-links，由普通像素分别S源点和T汇点连接组成的边。其中邻域像素可以采用四邻域或八邻域方法。能量函数包含了两个约束项，区域项R（A）与边界项B（A），充分利用图像的区域属性和边界属性的信息，可以得到准确性更高的分割结果。边的权值由能量函数的区域项和边界项计算，能量函数通常有如下形式：

区域项R（A）用来评价给所有像素分配标号的情况，其定义如公式（2）所示。其中，Rp（Ap）表示为单个像素点p分配标号Ap的能量消耗。

边界项B（A）反应的是图像的光滑性约束，表示不同标号的相邻像素点之间的代价，其定义如公式（3）所示。其中，B（p,q）可以看作为像素p和像素q之间不连续的惩罚项，δ（Ap,Aq）表示当相邻像素p和q的标号相同时为1，相邻像素的标号不同时为0。

在给所有边赋权值后，构建出一个完整的S/T图，然后通过最大流/最小割算法计算能量函数E（A）的最小值，得到最小割，割集将把S/T图分割成两个子图S图和T图，即把图像分割成目标和背景。

3 本文算法描述

3.1 预处理步骤

（1）读入序列图像文件，并保存序列图像的编号；

（2）利用双线性插值对图像重采样，调整图像到统一大小，便于整理和分割序列图像；

（3）对图像进行高斯滤波平滑、亮度变换操作，使图像的对比度增强，使待分割的目标更加突出；

（4）最后以序列编号来命名保存图像，为序列图像分割做准备。

3.2 余弦相似度

Graph cuts是一种把图像分割问题看成像素标记问题的基于图论算法。能量函数的区域项用于反映像素点分配标签的特征相似度，边界项用于反映相邻像素间的特征相似度。像素的颜色特征和相邻像素间的距离特征相结合，共同对能量函数的特征相似度产生影响。

传统的Graph Cuts算法在建立边界项B（A）时，用基于欧氏距离的惩罚项B（p,q）来表示相邻像素的相似性的差异。欧氏距离（Euclidean distance）是距离度量，用于衡量向量在空间上存在的绝对距离，没有考虑维度方向上的相似性。

余弦相似度（Cosine similarity）[6]衡量的是向量的相对距离，体现的是一个空间三维的概念。余弦相似度是一种相似度度量（Similarity measure），更注重维度之间的差异。本文采用余弦相似度构造能量函数的区域项和边界项，从相对距离上衡量像素间的特征相似度。余弦相似度的值在[0,1]之间，也使得算法简单高效。||•||表示向量的二范数，则两个向量p和q的余弦相似度C定义为：

向量a与向量集B的最大余弦相似度（Max Co⁃sine similarity），其含义是取向量a与向量集B的每一个向量Bi的余弦相似度的最大值。最大余弦相似度MCS定义为：

3.3 基于余弦相似度的能量函数

利用分水岭方法对图像进行预分割，得到的图像由许多个小区域组成。小区域内像素相邻且特征相似，又称为超像素。这些小区域大多保留了图像分割的有效信息，且一般不会破坏图像中物体的边界信息。利用基于超像素的计算，在不损坏图像特征信息的同时，达到降低算法的复杂度的目的。其中，Sp表示分水岭后超像素的平均像素值。Lp∈{“obj”,”bkg”}表示超像素p被分为的标签是目标或背景。

用户对目标和背景交互后，使用FCM聚类算法，对目标和背景种子点集分别聚类，得到目标和背景种子点集的聚类区域的平均颜色。目标种子点集经过聚类后得到n个区域，每个聚类区域的平均像素值记作{Oi}，i=1，…，n。背景种子点集经过聚类后得到m个区域，每个聚类区域的平均像素值记作{Bj}，j=1，…，m。

本文使用最大余弦相似度MCS来构造区域项Rp，用来反映像素点分配标签的特征相似度。当为像素点分配的标签差异性越小，区域项的值越小。区域项Rp定义为：

其中，MCS（Sp,Oi）表示超像素与目标种子点聚类区域的最大余弦相似度，MCS（Sp,Bj）表示超像素与背景种子点聚类区域的最大余弦相似度，计算公式如下：

为像素分配为“obj”0标签时，Rp（“obj”）表示该像素与背景种子区域的最大余弦相似度占全部种子区域的最大余弦相似度的值，反映的是被分配为目标的像素与背景种子区域的相似程度，即被分配为目标的像素的惩罚项。为像素分配为“bkg”标签时，Rp（“bkg”）表示该像素与目标种子区域的最大余弦相似度占全部种子区域的最大余弦相似度的值，反映的是被分配为背景的像素与目标种子区域的相似程度，即被分配为背景的像素的惩罚项。

由公式表明，若当前像素属于“obj”的概率更大时，Rp（“obj”）的值会更小；同理像素属于“bkg”的概率更大时，Rp（“bkg”）的值会更小。

使用余弦相似度C、颜色相似度W来构造边界项Bpq，用来反映相邻像素间的特征相似度。当相邻像素间的特征差异性越大，边界项的值越小。边界项Bpq的计算公式为：

其中，颜色相似度W用于衡量两个像素的颜色特征的相似性。Sp和Sq表示邻域超像素的平均像素值，二者差值的平方表示两个邻域超像素的颜色差异性。尺度因子σ用噪声估计确定。再利用负对数exp（-x）使得邻域超像素的颜色差异性越大，W（Sp,Sq）的值越小。颜色相似度W定义如下：

余弦相似度C用来衡量邻域超像素的相对距离的相似程度，其定义如（12）所示。相邻超像素的距离和方向特征的差异性越大，余弦相似度C越小。当邻域超像素不属于相同的区域（目标或背景）时，余弦相似度C最小。

边界项Bpq综合考虑了相邻像素的颜色和相对距离特征，利用这些特征相似度，衡量相邻像素间不连续性，体现了图像的边界信息。越靠近图像的边界部分（即相邻像素越不连续），邻域超像素的颜色和相对距离特征差异性越大，由公式可知颜色相似度W和余弦相似度C就越小，边界项Bpq也就越小。

能量函数由区域项和边界项组成，当像素都被正确分配标签时，区域项的值最小，当边界都被正确分割时，边界项的值最小。能够实现图像被正确分割时，能量函数的值最小。

然后将图像映射成S/T图：图像分水岭预分割后的超像素映射为S/T图的普通节点的集合P，目标种子点集和背景种子点集被FCM聚类分割后的小区域映射为S/T图的S源点集和T汇点集。利用区域项和边界项计算S/T图中对应边的权值，普通邻域超像素的边的权值使用边界项Bpq计算，超像素与目标或背景种子区域的边的权值使用区域项Rp计算。

使用最大流/最小割算法中的其中一种算法：双向快速增广路径算法，该算法利用两棵搜索树从源点S到汇点T同时查找一条增广路径，算法速度快。利用双向快速增广路径算法计算能量函数最小值，得到最

D（Lp,Lq）表示邻域超像素的标签若相同则计算边界项，若不同边界项就直接为0。用于判断邻域超像素是否属于不同的区域。其定义如下：小割，从而实现图像分割。

3.4 序列图像分割算法

序列图像的基本特点是后一张图像与前一张图像相似，但是有差别。基于此特点，序列图像分割的核心思想是当前的图像分割后的模板作为下一张图像的种子点集。只有第一张图像需要单独分割，其余的序列图像可以实现自动分割。算法流程是：

（1）对第一张图像分割，使用本文提出的改进Graph Cuts算法得到分割后的模板，对模板腐蚀、膨胀操作得到第二张图像的种子点集；

（2）对当前图像分割，使用基于改进Graph Cuts算法，种子点是上一张图像分割得到并经过形态学方法处理的模板；

（3）重复步骤（2）直到分割好全部序列图像。

4 实验结果及分析

本文的实验数据的来源是LIDC-IDRI，一个公开的肺部影像数据库，像素间距为0.6641，图像间的序列间距为0.625。首先对多幅肺部序列图像进行预处理，使得待分割的目标更突出，为之后的多幅序列图像分割做准备。经过对238张图像的预处理实验，平均单张图像预处理需要约0.09秒。图1（a）表示使用鼠标对预处理后的图像人工标记，用蓝色的线标记背景种子点，红色的线标记目标种子点。图1（b）（c）为两种算法的实验结果可以看出本文算法的分割结果较好，对边界的分割更准确，减少误分割和漏分割的情况。

图1

由基于区域的测度可以计算一系列的评价指标，用于评价分割结果的准确性等。评价指标有真正类率（TPR），计算的是正样本被正确分割的概率，又称召回率、查全率。假正类率（FPR），计算的是负样本被错误分割为正样本的概率，又称虚报率。真负类率（TNR），计算的是负样本被正确分割的概率，也称特异性。假负类率（FNR），计算的是正样本被错误分割为负样本的概率，又称漏报率。准确率（ACC），就是正负样本分别被正确分割的概率。精确率（P），计算的是预测为正样本占实际为正样本的比例，又称查准率。F1是精确率和召回率加权调和平均，当F1较高时则能说明分割算法的准确度比较高。

为了验证实验的有效性，本文的实验数据有四组序列图像，分别对四组实验数据经过原始Graph cuts算法和基于余弦相似度的Graph cuts算法分割后，计算每组每张图像经过两种算法的评价指标，然后得到平均评价指标结果并计算本文算法相对于原始算法的环比增长率，如表1所示。

由表中的四组实验数据可知本文提出的基于改进Graph cuts算法的分割算法与基于原始Graph cuts算法的分割算法相比，在真正类率、真负类率、准确率、F1值均有所提高，在假正类率（即虚报率）和假负类率（即漏报率）均明显降低。由实验验证可得本文算法比原始Graph cuts算法的分割效果好，分割结果准确性提高，漏分割、误分割情况明显下降。

本文记录下两种算法分割的时间，基于本文算法的单幅图像分割的平均时间约为4.8782秒，而基于原始Graph Cuts算法的单幅图像分割的平均时间约4.4536秒，前者比后者多0.4246秒。

本文记录下人工标记所需时间，单幅图像标记的平均时间约29.4877秒。除了第一张图像需要标记，本文算法可以为每张序列图像省下约29秒，节省了大量的时间和人力，并提高了序列图像分割的效率。

5 结语

通过实验表明基于余弦相似度的Graph Cuts序列图像分割算法分割效果较好，误分割和漏分割的现象明显减少；可以实现序列图像分割，在保持良好分割效果的同时，提高序列图像分割算法的效率。

基于余弦相似度的Graph Cuts序列图像分割算法，对第一张图像的种子点选取依赖性较强，对于不同的序列图像种子点的选取需要作出调整。对于不同类型的图像需要调整式（1）中λ参数和式（11）中σ参数的值。后续的研究工作可以针对以上两点改进。

[1]Boykov Y,Jolly MP.Interactive Graph Cuts For Optimal Boundary&Region Segmentation of Objects in N-D Images[C].IEEE International Conference on Computer Vision，2001：105-112.

[2]Rother C,Kolmogorov V,Blake A.“Grabcut”-Interactive Foreground Extraction Using Iterated Graph Cuts[J].ACM SIGGRAPH,2004, 23（3）:309-314.

[3]Y Li,J Sun,CKTang,HY Shum.Lazy Snapping[J].ACM SIGGRAPH,2004,23（3）:303-308.

[4]Xu N,Bansal R,Ahuja N.Object Segmentation Using Graph Cuts Based Active Contours[C].Computer Vision and Image Understanding，2007，107（3）：210-224.

[5]Rother C,Minka T P,Blake A,et al.Cosegmentation of Image Pairs by Histogram Matching-Incorporating a Global Constraint into MRFs[C].IEEE Computer Society Conference on Computer Vision&Pattern Recognition，2006，1：933-1000.

[6]HV Nguyen,Li Bai.Cosine Similarity Metric Learning for Face Verification[C].Asian Conference on Computer Vision，2010，6493:709-720.

Graph Cuts Sequence Image Segmentation Algorithm Based on Cosine Similarity

LIU Lu

（School of Computer Science,Shenyang Aerospace University，Shenyang 110000）

Traditional Graph Cuts segmentation algorithm may bring leakage segmentation and error segmentation.The segmentation effect of the algo⁃rithm needs to be improved,and the algorithm needs human interaction with low segmentation efficiency.In order to improve the shortcom⁃ings of traditional algorithms,proposes the Graph Cuts algorithm of sequence image segmentation based on cosine similarity.Constructs the region term of the energy function by using the maximum cosine similarity,and calculates the maximum cosine similarity between the su⁃per-pixel and the seed clustering region.Constructs the boundary term of the energy function by using the cosine similarity and color simi⁃larity,and calculates the color and the relative distance feature similarity of neighborhood super-pixel.This algorithm is compared with the traditional Graph Cuts algorithm,the accuracy and recall rate are improved,the false positive rate and the false negative rate is reduced ob⁃viously.Applies this algorithm to sequence image segmentation,which reduces the manual interaction and improves the segmentation effi⁃ciency.

刘璐（1992-），女，辽宁抚顺人，硕士，研究方向为医学影像处理

2017-02-22

2017-05-20

1007-1423（2017）15-0020-05

10.3969/j.issn.1007-1423.2017.15.005

Graph Cuts Algorithm;Image Segmentation;Cosine Similarity;Sequence Image