ABSTRACT

Detection and segmentation of rocks plays an important role in many applications such as geological analysis and mining processes, and it is the foundation of the analysis and recognition. Rocks are usually segmented using a variety of features such as texture, shading, shape and edges. In this paper, an improved algorithm based on entropy rate superpixel and region merging is provided. The entropy rate superpixel segmentation algorithm proposes an objective function, which favors formation of compact and homogeneous clusters. Considering the shape of Rocks, the mirror sym- metry coefficient is integrated into the objective function. If rock images were then segmented by superpixel algorithms with this objective function, the results would adhere more accurately to rock boundaries. Furthermore, we propose an improved maximal similar region merging algorithm based on the sum and difference histograms for function reducing the over-segmentation. The experiment results show that applying this algorithm to rock images performs very well.

Keywords:Rock Image, Image Segmentation, Entropy Rate Superpixel, Region Merging

基于改进熵率超像素和区域合并的 岩屑图像分割

李杰，吴小强^*，熊淑华，王亚静，何小海

四川大学电子信息学院，四川 成都

收稿日期：2015年12月26日；录用日期：2016年1月10日；发布日期：2016年1月13日

摘 要

岩屑颗粒的分割与提取在地质分析、矿物处理中起着关键的作用，是岩性识别和分析的基础。针对岩屑颗粒图像纹理、阴影、形状、边缘特征复杂的特点，本文提出一种改进熵率超像素分割和区域合并后续处理方法。熵率超像素算法提出具有紧凑性、区域一致性约束的目标函数，考虑岩屑颗粒的形状，对此目标函数加入基于镜面对称系数的几何对称性约束条件，用此目标函数对岩屑颗粒聚类超像素分割，使岩屑颗粒图像分割边缘定位更加准确。针对超像素过分割严重的特征，提出基于和差直方图的最大相似度合并算法，降低岩屑图像过分割率。实验结果表明，此算法用于岩屑的分割，比其他算法取得较好的分割结果。

关键词 :岩屑图像，图像分割，熵率超像素，区域合并

1. 引言

在计算机视觉应用中，超像素具有减少算法复杂度的优点，常应用于图像处理的许多领域，如目标识别 [1] 、图像分割 [2] [3] 和3D重建 [4] [5] 。目前国内外已有大量的超像素分割算法，大致可以分为基于图论的分割算法和基于梯度下降的超像素两类 [6] ，代表性算法分别为Felzenswalb等人 [7] 提出的FH算法和Vincent等人 [8] 提出的分水岭(Water Sheds)算法，把这些算法应用在岩屑颗粒图像的分割上，尽管都有各自的优势特点，但很难同时保证在分割准确率和时间效率两个衡量图像分割优劣核心指标。王亚静等人 [9] 采用熵率超像素分割算法 [10] 对岩屑图像进行分割，取得了较好的分割效果。熵率超像素分割算法提出了包含两项的目标函数：1) 图上随机游走熵率，2) 平衡函数项，运用贪心算法迭代目标函数策略最大化目标函数。本文在分析熵率超像素算法图像分割基础上，对算法目标函数加入基于镜面对称系数的几何对称性约束条件,以改进熵率岩屑分割效果。该算法考虑岩屑颗粒形状信息，可得岩屑颗粒图像边缘附着性好、分割区域紧致、均匀的分割结果。最后，针对超像素分割过分割严重的问题，提出改进的最大相似度区域合并(MSRM)算法，以对岩屑颗粒分割图像后处理，改善最终分割结果。本文算法的主要框架如下图1。

2. 改进熵率超像素分割

2.1. 熵率超像素分割

1) 熵率：熵率超像素分割结合数学基础、图论、随机游走模型和信息熵的理论，假设原图为加权的

图1. 算法框架

无向图，原图像的像素为图的节点，相邻像素为图的边，像素相似度为边权重：，令为图随机游走过程，采用文献 [12] 随机游走模型，定义转移概率：

(1)

其中表示节点相邻边权重之和。

定义静态分布如下：

(2)

其中为归一化常量。

对于图的划分，目标是使图相邻边聚集为子图这样所得图其中，为划分子图数，也就是区域数目，为了获得区域一致性与紧致性的聚类区域，结合图理论，随机游走转移概率映射变换定义如下：

(3)

图随机游走熵率值函数：

(4)

2) 平衡项函数：为使聚类的簇具有相似大小，为选择边集，为图聚类数目，为聚类分布，图划分后边集，由此分布为：

(5)

则平衡项：

(6)

熵促使形成的簇具有类似的尺寸，使聚类的数目尽可能少。

3) 目标函数：结合熵率与平衡项的目标函数：

(7)

其中，为用户输入的系数，为聚类数，按如下公式计算：增加一条边后熵率值增加与平衡项函数值增加的比率：

(8)

2.2. 改进的熵率算法——融合几何对称性约束的熵率超像素分割

对于岩屑颗粒图像的研究发现，无论是什么样的岩屑颗粒，它们具有一定的对称性，熵率超像素分割算法利用像素的亮度信息以及空间位置距离关系分割图像，没有考虑像素之间的对称性特点。文献 [11] 中提出了一种表示和度量一对像素之间镜面对称性的关系方法—镜面对称系数，用于对具有对称性图像的轮廓提取，本节通过对镜面对称系数的介绍，引入镜面对称系数到熵率超像素岩屑颗粒分割目标函数里，从而对目标函数提出了一种基于镜面对称系数的几何对称性约束条件，增加了岩屑图像分割的准确性。

镜面对称系数 [11] 定义：

设I是灰度图像，p是图像I中的一个像素，是圆中的一个单位圆，以p为中心在R为半径的范围搜索对比度最大的像素点记为q，本文取R = 3，其中，的一个单位切向量，其方向垂直于像素p与像素q的连线。这里，对于和与其相关的角度，定义 v的反射矩阵为：

(9)

设p和q是空间内有明显差异的两个点，它们通过单位的切向量，和联系在一起。如果满足条件(10)则是镜面对称。

(10)

为了简单描述，称p和q是镜面对称的，而不称它们的切向量是镜面对称。这里，用镜面对称系数对两个不同像素点p和q之间的镜面对称性进行定量的表示，定义式如下(11)。

(11)

两个不同像素点p和q之间的镜面对称性表示为式(12)。

(12)

其中，值越大说明两个像素p和q越对称。

定义几何对称性约束函数为：

(13)

其中，图A为选择的边集，表示图A中相邻像素i, j之间由镜面对称系数度量的对称性。

熵函数随着的增大，即值趋向于1.0是递增的，每次向随机游走模型中加入一条新的边，就会增加随机游走模型的不确定性，随机游走模型的不确定性越大，则熵率越大，所以，这个随机游走模型的几何对称性约束函数是一个单调递增的函数。另外，在向随机游走模型中加入边时，随着边的逐渐增加，新加入的边对模型的不确定性的影响力就会逐渐减弱，因此函数也是一个满足收益递减属性，即子模性。综上分析，图的随机游走模型的几何对称性约束函数是一个单调递增的满足子模性要求的函数 [10] 。

2.3. 改进熵率超像素岩屑分割算法

为了得到具有同质性、大小均匀、形状规则具有一定对称性的超像素，就必须使用熵率来实现颜色相似度度量的要求，使用平衡项来实现大小控制的要求，使用几何对称性约束来实现超像素形状规则具有对称性的要求，所以本文提出了一个新的目标函数，即由2.1节中介绍的熵率函数、平衡项函数与本节提出的基于镜面对称系数的几何对称性约束函数组成。通过最大化关于边集的目标函数式(14)来得到分割结果。

(14)

对于选择的边集A，使其满足，参数是平衡项的权重，是几何对称性约束项的权重，并且都是正实数，所以，由三个函数相加的组合成的新目标函数保持了单调性和子模性。通过最大化上述目标函数，采用贪心策略实现图像的分割。

这里，采用2.1小节中介绍的平衡项的权重系数自动调节类似的方法进行几何对称项系数的自动估计：

1) 遍历所有的边，按照式(14)介绍的目标函数的计算方法，计算出所有边的熵率增益和几何对称项增益，并且找出熵率的最大增益和几何对称的最大增益。

2) 计算几何对称项系数：。其中K为期望产生的聚类数目，即超像素数目，为用户自己输入的一个起始系数。本文使用，是依据如下公式自动计算出的一个值。

(15)

算法具体步骤如下：

步骤1：把图像像素视为结点进行图的构造，初始化结点和边，相邻结点之间边的权重由如下式(16)获得。

(16)

其中表示像素坐标，表示的距离，表示亮度绝对值，核带宽根据实验结果设为。

步骤2：按照2.2.1小节中介绍的方法计算相邻结点之间表征几何对称性的镜面对称系数：对组成结点的像素进行八邻域内搜索，标记出组成与相邻结点之间公共边界的一系列像素点，对这些边界处的像素点按照式(12)分别计算出镜面对称系数，用计算出的所有镜面对称系数的均值作为相邻结点间的对称性度量。

步骤3：根据式(14)计算所有边的目标函数增益，对目标函数增益建立一个最大堆，采用贪心算法进行图的划分，同时每加入一条边，需要对这个堆进行相关更新，直到目标数目等于预先设定的目标数目，得到分割结果。

3. 基于和差直方图的最大相似度(MSRM)合并

经过实验结果得知，尽管改进熵率超像素算法对岩屑颗粒图像分割取得了很好的效果，但仍然存在过分割的区域，本文引用最大相似度优化合并算法对岩屑图像分割结果后处理，进一步提高分割准确度。最大相似度融合算法(MRSM) [13] 使用超像素作为处理单位，具有不需要阈值，自适应选择合并区域的特点，因此，相比于传统合并算法具有很大的鲁棒性优势，但原始MSRM算法计算维度多，计算量大，为此，本文采用符合岩屑颗粒特征描述的差直方图的绝对值提取目标区域相似度，改进MSRM算法的计算维度问题，这将极大的减少复杂度。

和差直方图描述图像灰度和与差的概率分布情况，反映了图像关于方向、相邻间隔、变化幅度的综合信息，具体描述如下：

考虑的灰度图像，灰度级图像的两个像素，，表示分析区域，对于相对偏移和差定义：

(17)

归一化的和差直方图定义：

(18)

其中表示的像素分布，表示的像素分布，代表区域像素总数量，在像素八邻域内，为了简单，我们取四个方向。

设区域QR为相邻区域，利用巴氏系数作为区域R与区域Q之间相似度的衡量标准，使用描述两区间的相似度，则有：

(19)

其中为区域差直方图，为彩色图像灰度量化值，越大时，说明两直方图的相似度越高，反之，两区域的直方图相似度就越低，表现在图像上的差异就比较大。

MSRM算法使用了一种自适应于图像内容的区域融合策略，设超像素区域Q与超像素区域R相邻，统计区域Q的所有邻接超像素区域，并将其邻接区域集合定义为，显然有，通过巴氏系数确定区域Q与其所有邻接区域的相似度，并记作：

(20)

若区域Q与区域R相似度满足式(21)

(21)

则合并两区域，图2显示两相邻区域合并前后效果示意图。

结合第2节与第3节所述，可得本文算法流程图如图3。

4. 实验结果与分析

文中首先对原始彩色岩屑颗粒图像进行高斯金字塔滤波预处理，然后对图像运用改进的熵率超像素分割图像，最后对过分割图像进行合并得到最终结果，软件程序均采用C++语言实现。

图4为本文算法与合并分水岭 [14] 、FH算法 [7] 、TurboPixels算法 [15] 对比，为达到实验结果准确性，所有的算法均采用所给论文最优参数。从图中可以看出:分水岭算法边缘定位准确，但存在非常多的过分割区域，尽管采用合并算法减少过分割，但仍然在某些区域不尽人意，FH在边缘处产生较多重复边缘，TurboPixel不仅过分割严重，且边缘定位不准，熵率超像素对岩屑图像的分割具有紧凑性与一致性的特点，由(e)、(f)可知：本文算法相对于原始熵率超像素边界定位更准，边缘依附性更好，增加了目标提取的精确度。

图5表示在分割过后对区域进行合并后结果，图(b)表示文献 [16] 基于颜色相似度与长短边界信息合

图2. 区域合并对比图

图3. 算法流程图

并方法的合并结果，图(c)为文献 [17] 基于颜色相似度与真假边缘分析方法的合并结果图，图(d)为本文基于差的绝对值直方图最大相似度合并结果，从图中可知，文献 [16] [17] 需要有用户输入阈值，而最大相似度合并不需要，且差直方图提取了岩屑颗粒纹理信息与颜色信息，比传统合并算法只基于颜色相似度更加精确，更能适合岩屑颗粒图像的合并。

图4. 改进熵率超像素与其他算法分割结果图对比

图5. 合并算法结果

5. 结束语

本文提出一种岩屑颗粒图像分割方法：基于岩屑图像对称系数的熵率超像素分割，该方法不仅使岩屑分割边缘附着性好，且考虑岩屑形状信息，使得分割结果更加准确。通过加入岩屑颜色、纹理区域特征的改进最大相似度合并算法，对分割结果进行进一步处理，提高分割准确性，且与原MSRM算法相比，加快了合并时间。

文章引用

李 杰,吴小强,熊淑华,王亚静,何小海. 基于改进熵率超像素和区域合并的岩屑图像分割
Rock Image Segmentation Based on Improved Entropyrate Superpixel and Region Merging[J]. 图像与信号处理, 2016, 05(01): 16-24. http://dx.doi.org/10.12677/JISP.2016.51003

参考文献 (References)