基于简单线性迭代聚类算法和动态区域合并的岩屑图像分割

吴实;熊淑华;李杰;吴小强;何小海

【摘 要】岩屑图像分割要求精度高、速度快和鲁棒性强.针对这些要求,提出了基于SLIC(simple linear iterative clustering)和动态区域合并的分割算法.SLIC算法能产生形状规则、大小均匀、排列紧凑的超像素区域;但是SLIC分割后的图像过分割问题严重,为了降低过分割率,提出了基于NNR的动态区域合并算法,将超像素区域进行相似性合并.实验结果表明,将该算法用于岩屑颗粒图像分割,能够取得较好的效果.

【期刊名称】《科学技术与工程》 【年(卷),期】2016(016)035 【总页数】6页(P238-243)

【关键词】岩屑图像;图像分割;SLIC;动态区域合并 【作 者】吴实;熊淑华;李杰;吴小强;何小海

【作者单位】四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065 【正文语种】中 文 【中图分类】TP391.41

图像分割是按照一定的相似性准则将图像分成若干个特定的区域，并提取出感兴趣区域的技术和过程[1]。在石油行业的录井工程中，岩屑图像分割结果的好坏直接

影响目标提取和识别效果等后续的处理[2]；因此岩屑图像分割具有极其重要的研究意义。目前，国内外已经有的大量的分割算法，大致可分为基于边界检测、基于阈值、基于数学形态学和基于区域等分割算法[3]。

基于区域的分割方法是该领域的研究热点，SLIC[4]的超像素分割就是一种基于区域的分割算法。超像素具有边缘定位准确和计算复杂度低等优点，在计算机视觉领域越来越被广泛使用。针对超像素分割后存在的过分割问题，以及合并过程中的自适应性，本文提出一种基于SLIC和动态区域合并算法。该算法框图如图1所示。 超像素是由具有相似颜色、亮度和纹理等特征的相邻像素构成的图像块。因为超像素块包含图像的冗余信息，所以在很大程度上降低了后续处理的复杂度。目前主要的超像素分割算法有：J.Shi和J.Malik提出的归一化分割算法[5]，Moorer等提出的超像素网格算法[6]，Fukunaga和Hostetler提出的Mean shift算法[7]和由R.Achanta等提出SLIC算法[4]。由于SLIC方法计算速度快，形成的超像素区域具有高度的一致性，本文岩屑图像的初分割采用SLIC算法。

简单线性迭代聚类算法SLIC (simple linear iterative clustering)，是由R.Achanta[4]等人提出的一种原理简单、实现简便、在局部进行比较计算的快速聚类算法。该算法通过计算像素之间颜色相似度和空间位置临近度进行聚类得到超像素分割结果，这一过程是在一个五维空间[l,a,b,x,y]中实现的，其中[l,a,b]为CIELAB颜色空间的色彩向量，[x,y]为像素的空间坐标位置。SLIC算法采用一种新的、归一化的距离度量进行图像的聚类，这种归一化的距离同时考虑到了颜色相似度和像素位置信息。

假定一幅图像有N个像素，设期望产生K个尺寸近似相同的超像素块，则每个超像素块包含N/K个像素。每个超像素块的网格宽度就是，即聚类中心之间的距离。在SLIC算法中，第k个超像素的聚类中心可描述为： Ck=[lk,ak,bk,xk,yk]；k∈[1,K]

像素间颜色距离：

式(2)中，distlab表示像素之间颜色的差异，lk,ak,bk为聚类中心像素的各个颜色分量，li,ai,bi是在聚类中心2S×2S邻域范围内各像素的颜色分量。 像素空间距离：

式(3)中，distxy为空间位置的距离，xk,yk为聚类中心像素的横坐标和纵坐标，xi,yi是在聚类中心2S×2S邻域范围内各像素的横坐标和纵坐标。 归一化距离度量：

式(4)中，S为聚类中心间的距离，变量m为紧凑因子，用来衡量空间位置信息在计算颜色信息与空间信息的距离度量中所占的比重，控制超像素的紧密度，其值越大，表明越强调空间临近程度，从而聚类越紧凑。

Di为颜色距离与空间距离归一化后的和，表示两像素间的差异度，Di值越小，表明两个像素之间的差异度越小，相似度越高；差异度越大，相似度越低。

SLIC算法对岩屑图像进行超像素分割得到的图像过分割严重，为了降低过分割率，得到更准确的分割结果，需要对初分割的结果进行区域合并。现有的区域合并算法很多，其基本思想就是将具有同质性的区域合并在一起，同质性即为区域特征相似性。然而，大多数现有的区域合并算法在合并时需要人为输入合并的阈值。因此，提出了具有自适应性的基于NNG(nearest neighbor graph)的动态区域合并算法。 2.1 动态区域合并准则

合并判定是基于测量两区域边界像素之间的相似性。我们使用区域邻接图(RAG, region adjacency graph)[8]表示一幅图像，设G=(V,E)是一个无向图，vi∈V对应图中的节点集(超像素或区域)，E是相邻节点(区域)的边集，每条边(vi,vj)∈E的权重w(vi,vj)表示相邻节点的相似性，定义R∈V代表某个区域，其相邻区域集R1,R2∈V的最大相似权重[9]S(R1,R2)表示为:

假设一幅图像被分成图2(a)所示的不同超像素区域，则可以得到对应的RAG如图

2(b)所示。

合并判定包含相似性测量和区域同质性检验，其中，相似性决定候选区域是否合并，同质性检查一致属性。为了让同质区域进行合并，用谓词P来判决相邻区域是否为同质区域。可以定义区域合并谓词P： P(R1,R2)=

式(6)中，Ω1和Ω2分别是R1和R2的相邻区域集。判定区域R1和R2是否合并的准则为：R1和R2的相似性在各自的邻域集中拥有最大的值并且满足一致性准则。条件(a)要求区域满足在其邻域内，两个区域的相似度为每个区域的相似度的最大值，是否连接两相邻区域由条件(a)唯一确定，不满足条件(a)的区域一定不会合并。条件(b)作为合并停止条件，若没有条件(b)其区域将会合并成一整块区域。 为了合并过程具有自适应性，将评价区域一致性看作是序列试验过程。假设参数θ与随机参数x的分布有关，通过观察连续步骤中的随机变量来收集参数θ的信息。每个样本携带参数θ的统计信息，因此可以在观察的最后收集到θ的信息。在序列分析中，θ称为假设。在区域合并时，两个假设都包含有评价任务，即一对区域是“一致”或“不一致”，其分别对应H0:θ=θ0和H1:θ=θ1。判断一对区域是否属于同一组,可以从它的假设检验来寻找解决方案。

由Wald等[10]提出的序列概率比检验(sequential probability ratio test，SPRT)表明解决方案假设可以通过观察最小数量和满足预定义的两个错误概率界限。SPRT的一致性检验可以描述如下：随机变量x的分布在序列中随机游走，直到似然比δ不在区间(B,A)，其中实数A,B满足(B<0式中，Ia和Ib分别为区域a和区域b的抽样数据的颜色平均，Ia+b为两个区域抽样数据的颜色平均。SI为两区域间的协方差，λ1和λ2为标量参数。若每次测试相互，则似然比的和为：

式(10)中,N是δA时的第一个整数。

由此可知，当似然比δ越大，最终判决时支持H0；反之，δ越小，最终判决时支持H1。在SPRT理论中，Wald提出用一个实用的近似来进行测试，即A=lg(1-β)/α，B=lgβ(1-α)。其中，α和β为决策错误的概率: α=Pr{Rejecting H1when H1 is true} β=Pr{Accepting H1 when H0 is true}

α和β影响区域合并的质量，错误率越小，则区域合并质量越高。但是，错误率越小也会带来计算的负担。在本文的实验中，α和β都取为0.05。

由于SPRT测试的不确定性，可通过预设一个测试数量上限N0来实现一种截断的SPRT。在Wald的理论中，预期测试的数量为： E{n|θ0}=[A(1-β)+Bβ]/η0 E{n|θ1}=[Aα+B(1-α)]/η1

式中，η0=E{δ|θ0}； η1=E{δ|θ1}。 实验中设置N0为η0和η1中最大值。 2.2 基于NNR动态区域合并算法加速

合并算法过程取决于区域间的邻接关系，在每一个合并步骤中，需要计算邻域内的边与某个特定边的最大权重，这需要遍历整个图中所有边与相邻区域之间的关系。节点之间的边权重在每次图形迭代过程中需要更新与保存，由于边的位置是未知的，线性搜索节点和边需要O(‖E‖)时间。

根据对合并迭代过程的观察，边连接图中只有小部分边参与迭代过程，可以通过去掉冗余的边信息实现算法的加速。因此考虑在转换图时，通过对RAG图进行改进，

把那些不常用的边删除，降低算法的复杂度。算法的实现依赖于最近邻图NNG(nearest neighbor graph)的结构，该图结构定义如下：

对一个区域邻接图G=(V,E)，其NNG为有向图Gm=(Vm,Em)，其中Vm=V。如果定义一个对称相似函数S来测量边权重,有向边Em可以定义为: Em={(vi,vj)|w(vi,vj)=minS(vi,vj), (vi,vj)∈E}

图3为图2(b)转换为NNG图时一种可能的转换结果，每个相邻节点表示的边为节点之间的最大相似度，由此，NNG图所包含的边的数目为‖V‖，如果起始节点与终止节点具有一致性，则称其为环，如图3中节点4和节点5，具有环的节点则是将要合并的节点。

NNG图应用到区域合并过程，更新NNG图需要O(‖V‖)的搜索时间，如果有大量的节点，计算代价同样昂贵，在一次迭代合并过程中，循环节点被合并以后，其NNG相邻节点和图结构将被修改，新的循环节点仅能在合并节点的下一次邻域内构成，NNG图中环被合并修改后形成下一次环示意图如图4所示，合并节点1和节点2后，由于区域信息的改变，原本节点1和节点3为最近邻域节点，现在变化为节点3和节点4在各自邻域内具有最大相似度，同时，一个新的环在节点4和节点5之间形成。

在这种区域合并迭代方式下，新的环只能在下次迭代检测合并节点的邻域间形成，因此，在区域合并过程中，更新每一次NNG图边的计算量依赖于合并后NNG图邻域大小的分布，合并NNG周期的计算时间为O(γ(2)+1)，其中γ(2)是合并后邻域的大小，在大多数情况下，γ(2)远小于‖V‖，能够减少计算时间，加快算法速度。 2.3 基于NNR的动态区域合并的实现

由于SLIC产生的是过分割图像，对该图像的相似区域进行合并得到有意义的分割图像。为每个区域Ri分配两个标签和取决于区域合并开始之前，取决于区域合并停止时。由于SPRT过程中错误的决策，所以最后对应的并不是唯一的。测试结果

是否具有一致性取决于决策错误的概率α和β。一般来说，这些决策在同质区域下是精确的。在大部分的情况下，分割的结果取决于所给的图像和是否保证所有的结果满足合并谓词P。在合并的过程中，每个地区的标签是按顺序从最初的一个传递到最后一个，用序列表示为)。

为了得到最优的合并序列，即在每个区域的合并过程中获得最优的标签，则需要一个最小化的特定目标函数F。由合并谓词P可知，区域标签的转换对应着两个区域间的最小权重，因此一系列的标签转换可以定义为一组局部最小权重。所有的区域构成了整幅图像，F是转换成本在所有地区的总和，因此F可以定义为： 式(16)中，Fi为区域Ri最初分割的转换成本。为了得到最小化的F，可以采用了基于F的逐步最小化，通过使用动态规划(DP)技术[11]，将原问题分解成几个子问题。动态规划在计算机视觉领域被广泛用于求最优解问题。在动态区域合并中，区域Ri的最小化问题从标签开始，可以定义为：

式(17)中，)是到的转换成本，dk,k+1是标签为区域的最小的边权重，因此dk,k+1可以表示为：

动态区域合并算法的流程如图5所示。

首先对岩屑颗粒图像用SLIC算法进行超像素分割，然后采用基于NNR的动态区域合并算法对相邻的相似性区域进行合并，得到最后的结果图。

本文分割算法各阶段分割图如图6所示，图6(a)为待分割的岩屑图像，图6(b)为SLIC算法分割图像，图6(c)为动态区域合并后的最终图像，从图中可以看出，经过合并后的分割结果图与初分割图相比，过分割明显减少。

图7为不同算法分割对比图，其中图7(a)为文献[12]算法的结果图，图7(b)为文献[13]基于颜色相似度与长短边界信息的合并结果图，图7(c)为文献[14]基于边界集中区域颜色相似度与形状因子相结合的合并结果图，图7(d)为本文基于NNR的动态区域合并的合并结果图。从图中可知，文献[12]算法过分割严重。文献[13，

14]算法在合并时需要有用户输入合并的阈值，而本文的合并方法不需要，并且本文的合并方法对一些短的高对比度边界的合并效果很好，通过NNR算法加速后，速度提升了24.2%。

为得到客观的评价标准，可以定义如下的综合评价函数： E=α(1-PE)+β[u(1-PO)+v(1-PU)]

式(19)中，PE为误差概率，PO为过分割率，PU为欠分割率，α,β为误差概率加权系数，u,v为欠分割率加权系数，其中α+β=1,u+v=1。岩屑分割的目的是为后期的识别奠定基础，误差概率与欠分割率同等重要，故取α=0.5,β=0.5，而欠分割对后期岩屑识别影响非常大，岩屑的分割需要看重欠分割率的大小，故取u=0.2,v=0.8。实验中，选取10幅岩屑图像分别采用文献[12—14]和本文的算法进行分割评价，各项性能参数平均结果如表1所示。

从表中可以看出，本文算法对岩屑图像分割的过分割和欠分割都有一定的抑制作用，分割结果的综合评价得到一定的提高，改善了分割精度。

本文提出了一种基于SLIC和动态区域合并的岩屑颗粒图像分割方法。该方法采用SLIC算法对图像进行初分割，然后采用动态区域合并算法对初分割形成的过分割小区域进行相似性合并，降低其过分割率。为了提高计算效率，采用NNG的数据结构对算法进行加速，从而提高分割速度。实验结果表明，将该算法用于岩屑颗粒图像分割，具有较好的分割效果。

*通信作者简介：熊淑华(1969—)，女，副教授。研究方向：多媒体通信与信息系统。E-mail:******************。 【相关文献】

1 冈萨雷斯, 伍兹. 数字图像处理(第三版). 北京：电子工业出版社,2010

Rafael C. Gonzalez, Richard E. Woods. Digital Image Processing,Third Edition . Publishing

House of Electronics Industry,2010

2 范艳军. 岩屑图像分析系统设计与实现. 成都:四川大学, 2013

Fan Yanjun. Rock image analysis system design and implementation.Chengdu:Sichuan University,2013

3 杨丹丹. 矿岩颗粒图像分割方法研究综述. 盐城工学院学报(自然科学版), 2014;27(3):36—40,44 Yang Dandan, Research of ore particle image segmentation methods. Journal of Yancheng Institute of Technology (Natural Science Edition), 2014；27(3)：36—40,44 4 Achanta R, Shaji A, Smith K， et al. SLIC super-pixels compared to state-of-the-art super-pixel methods. Transactions on Pattern Analysis and Machine Intelligence, IEEE, 2012;34(11):2274—2282

5 Shi J, Malik J. Normalized cuts and image segmentation. Computer Society Conference on Computer Vision and Pattern Recognition, IEEE ,1977:731—737

6 Moore A P, Prince S J D, Warrell J,et al. Superpixel lattices. Conference on Computer Vision and Pattern Recognition, IEEE ,2008:1—8

7 Fukunaga K, Hostetler L. The estimation of the gradient of a density function, with applications in pattern recognition. Transactions on Information Theory, IEEE, 1975；21(1): 32—40

8 Trémeau A， Colantoni P. Regions adjacency graph applied to color image segmentation. IEEE Transactions on Image Processing，2009；(9)：735—744

9 Peng Bo, Zhang Lei, Zhang David. Automatic image segmentation by dynamic region merging. IEEE Transaction on Image Processing,2011;20(12):3592—3605

10 Wald A. Sequential analysis. Wiley Publications in Statistics. Third ed. Wiley,1947 11 Mishra A, Fieguth P, Clausi D. Accurate boundary Localization using Dynamic Programming on Snakes. Proceedings of the Canadian Conference on Computer and Robot Vision, 2008:261—268

12 Liu M Y, Tuzel O, Ramalingam S, et al. Entropy-rate clustering: cluster analysis via maximizing a submodular function subject to a matroid constraint. IEEE Trans. Pattern. Anal. Mach. buell, 2014;36(1): 99—112

13 何 艳. 岩屑图像分割算法研究. 成都:四川大学, 2013

He Yan. Research on rock image segmentation algorithm.Chengdu:Sichuan University,2013

14 王亚静. 岩屑图像多级超像素分割算法研究及实现.成都:四川大学,2015

Wang Yajing. The research and realization of multi-levelsuper-pixel cuttings image segmentation. Chengdu:Sichuan University,2015