基于形态学特征的颗粒图像分割和计数

王忠勇, 贾　萌, 侯中新, 陈在旭

(1.郑州大学 信息工程学院,河南 郑州 450001； 2.河南高远公路养护设备股份有限公司, 河南 新乡 453000)

基于形态学特征的颗粒图像分割和计数

王忠勇1, 贾萌1, 侯中新2, 陈在旭2

(1.郑州大学 信息工程学院,河南 郑州 450001； 2.河南高远公路养护设备股份有限公司, 河南 新乡 453000)

摘要：针对黏连严重、分辨率和清晰度较低的颗粒图像分割和计数问题，提出了一种基于分水岭和形态学特征的新方法.首先使用分水岭算法分割图像，得到过分割的结果，接着通过本文定义的区域形态学特征，再根据加权马氏距离和区域连接图(Region Adjacency Graph)进行区域合并.采用实际图像进行的实验表明，该算法效果良好，对原始图像的灰度、对比度和噪声变化具有不变性，在准确率-查全率(Precision-recall)曲线的表现上优于现有方法.

关键词：颗粒分割计数；分水岭算法；形态学特征；区域连接图

0引言

基于图像分割的物体计数有很多实际应用，例如谷物颗粒计数，微生物和细胞计数，基于截面图像的棒材计数等[1].大部分是依靠分水岭对计数目标进行分割.例如结合分水岭算法和欧拉数的计数方法[2]，基于距离变换[3]和分水岭算法分割二值化的黏连颗粒[4]是目前应用最广泛的方法.

实际工程中的成像条件往往十分复杂，在同步碎石封层的公路施工中，常常需要检测石子撒布覆盖率，目前仅能依靠人工计数样本方格内的石子数目，效率十分低下.笔者针对清晰度差，分辨率不足的图像，提出了一种鲁棒性较强的分割和计数方法.

由于分水岭算法能够响应非常微弱的边缘，形成的边缘连续且闭合，因此该算法针对成像质量差的图像有效.基于不同的实现思想，分水岭算法可分为模拟涨水法[5]、模拟降雨法[6]和模拟洪水消退法[7].分水岭分割算法也存在过分割问题，抑制过分割的方法一是预处理，采用滤波抑制原始图像中的伪极小值，同时保护边缘[8]；二是基于标记抑制过分割[9]，只有标记之间最强的分水线会被返回，三是后处理，即先得到过分割的结果，再进行区域合并[8].

本方法是一种后处理的技术.笔者充分发挥了分水岭算法将图像看作三维地形的思想，定义了若干形态学的特征来描述区域，并提出了根据特征合并区域的方法，以及停止规则.

1算法流程概述

本算法的流程如图1所示.首先对原始的颗粒图像进行高斯平滑预处理，这是为了减轻过分割的程度(而不是消除过分割)，以减小区域合并的运算量.

其次采用分水岭算法对其负图像进行分割.图像分割操作可以看作对像素分配标签，因此，称分水岭分割的结果为label图，它的尺寸与原始图像img相同，存储着对相应像素分配的标签(即区域标号).区域标号从1开始，每次发现新的局部极小值，就把标号加1，赋给该极小值像素，涨水过程中，对属于同一集水盆地的像素分配号码n，并称该区域为区域n.当涨水造成两个区域将要相连时,对此处的像素标签赋值0,以标志该像素是边缘.初始化形态学特征和区域连接图的工作可以在涨水过程中同步地完成，以减少运算量.

最后进行区域合并.以分割结果、形态学特征和区域连接图为输入数据，循环执行，每一次循环可完成一对相邻区域的合并，直至算法认定所有错误区域合并殆尽.

2形态学特征和区域连接性图

过分割会将图像分为大量细小的区域，如果一个区域里包括且仅包含一个颗粒，笔者定义其为正确分割的区域.如果一个区域不包括颗粒或仅仅是颗粒的一部分，笔者定义其为过分割的错误区域.图2为上述两种情形的例子，图2(a)表现了第一类不包括颗粒错误区域，图2(b)表现了第二类仅仅是颗粒的一部分.颗粒稀疏时倾向于发生第一类错误，颗粒密集时发生第二类.

本方法引入深度、面积和容量的几何概念，定义了6种形态学特征描述区域，并且在区域链接性图中使用区域之间分水岭的绝对高度衡量两区域的连接强度，以指导区域合并.

2.1区域形态学特征

如图3所示，该地形图的截面上有两个局部极小值，高度分别是hi和hj，因此初始的分割将在这里产生区域i和区域j. 点A和点B分别是区域i边缘上的最高点和最低点，记为hmin(i)和hmax(i)，区域j可类推.

定义1定义在涨水过程中，水面上升至hmin时的面积为盆地面积，单位为平方像素，记为Sbasin(如图3(a)中穿过B点的水平线所示)，

(1)

式中:δ和Sgn分别是狄拉克函数和符号函数.

定义2定义涨水至hmax时，水面面积为区域面积，记为Sregion(如图3(a)中穿过A点和C点的水平线所示)，

(2)

定义3定义涨水至hmin时，水池的深度为盆地深度，单位为像素，记为Hbasin(即水面面积为Sbasin时的深度)，

Hbasin(i)≜hmin(i)-hi.

(3)

定义4定义涨水至hmax时，水池的深度为区域深度，记为Hregion(即水面面积为Sregion时的深度)，

Hregion(i)≜hregion(i)-hi.

(4)

定义5定义涨水至hmin时，蓄水的体积为区盆地蓄水量，单位为立方像素，记为Vbasin(即Sbasin以下的体积)，

(5)

定义6定义涨水至hmax时，蓄水的体积为区域蓄水量，记为Vregion(Sregion以下的体积)，

(6)

2.2区域连接图

区域连接图[8,10]用于记录区域之间的连接关系和连接强度.它是一个无向图，记为G=(N,E).其中N={1,2，…，K},是节点的集合，代表区域，K是初始分割得到区域的数目，E∈RK×K是节点间连接的集合，代表区域间的边缘.

图4为一个区域连接图的例子，其中(a)模拟了一个包括6个子区域的分割;(b)用节点和连接的形式将它们表示出来;(c)是用于保存区域连接图的矩阵E，它的元素是布尔值，表示边缘，元素在矩阵中的位置表示所连接的节点.

除此之外，合并过程中还需要一个K×1的矩阵Validity，元素也是布尔值.在区域合并过程中，矩阵E的尺寸不会随着合并而动态改变，如果一个区域被合并而消失掉了，它会在Validity中被标记为无效，E中的对应行列也同样失效.

Strength是与E同尺寸的矩阵，其元素代表E中对应连接的连接强度.笔者采用分水岭的高度衡量2个区域之间的连接强度，分水岭的高度就是2个区域之间的边缘平均高度，

(7)

区域连接图节点的合并如图4(d)所示，所有与区域a和区域b有连接的区域，在合并后都将与新区域有连接.以Ai表示与区域i连接的区域集合

(8)

3合并算法

合并过程是循环执行的，每次循环使2个区域的合并，每次循环中需要完成：①搜索出一个错误区域i；②从与i相连的区域中选出连接强度最大的区域j；③执行i与j的合并；④更新区域特征和区域连接图；⑤检测停止规则.

3.1基于加权马氏距离搜索错误区域

如前所述，错误区域的面积、深度和蓄水量较小，因此首先统计所有区域形态学特征的均值向量M，然后找出距离均值最远(在负方向上)的一个样本，即为待合并的区域i.

显然，笔者定义的6种形态学特征不但量纲和数值变化范围不同，而且不同的形态学特征在描述区域时的重要性也不同.采用马氏距离可以消除量纲的影响，但不能反应重要性差别；加权欧氏距离没有考虑特征之间的相关性和量纲，因此，一种直观的想法是对马氏距离进行加权.

马氏距离的计数公式为

(9)

式中：Σ是样本协方差矩阵.而所谓的加权马氏距离[11]计算公式为

(10)

式(10)所示的加权马氏距离满足距离定义的三条基本公理，且对一切非奇异线性变换具有不变性(说明可以排除量纲影响),但是加权马氏距离不能严格地反映特征之间的相关性.

如果样本在xy平面上呈现二维高斯分布，欧氏距离的等距离曲线如图5(a)所示，欧氏空间中到某点等距离的点集是圆(高维时，为球面或超球面).加权欧氏距离的等距离曲线如图5(b)、(c)所示，它们是以均值为中心的椭圆簇.图5(d)中显示与样本数据的分布有关的马氏距离的等距离曲线.图5(e)、(f)是加权马氏距离的等距离曲线，这些曲线长轴的方向与样本分布有关，同时也受到加权的影响.

加权马氏距离是对马氏距离等距离曲线进行拉伸或压缩，可以看作是加权距离和马氏距离的结合.笔者采用线性搜索的方法优化权值.

3.2基于近邻函数确定合并入的区域

搜索得到要合并的区域i之后，需要从区域i的相邻区域中找到一个区域j，使区域i与区域j合并.确定区域j的依据是区域连接图的连接强度(式7)，采用近邻函数的方法.

间隔分水岭越低的区域连接强度越大，合并后的损失越小.对于相连的任意2个区域i和j，如果i是j的第I个近邻的区域，则定义区域i对区域j的近邻系数为I，记为d(i，j)=I.于是区域i和区域j之间的近邻函数值

Dij=d(i，j)+d(j，i)-2.

(11)

逐个检查与区域i相连的区域的近邻函数，找出最小值(最近邻)，然后使其与区域i合并.

3.3停止规则

如果算法的任务仅仅是对颗粒图像进行分割，停止规则可选取为：平均区域大小、区域数目、区域形状因子等等，其参数可以根据分割的目的进行设置.如果算法的任务是自动地统计颗粒的数目，则需要选择一种客观的衡量标准.

在颗粒图像中，局部的颗粒分布大致是均匀的，据此，笔者采用了区域面积方差的停止规则.方差可以度量数据和其均值的偏离程度，初始的过分割区域杂乱无章，大小不一，其方差较大，随着区域合并的进行，区域逐渐正确地与颗粒相一致，这时区域的面积差异应该最小.

由于合并过程中，区域面积的均值不断变化，为了使不同合并进程中的方差具有可比性，采取如下方式标准化数据，

(12)

4实验结果

图6是采用实际的同步碎石封层施工形成的石子图像实验的结果，可见本算法在实施区域合并中，能够在减少错误区域的同时避免将两颗相邻石子合并入同一区域，因而能对石子进行计数.

为了与一些现有方法[2，4]对比，人工标记出Groundtruth图像，用色点标示出了颗粒的位置.如果一个区域里包含色点，则该区域是一个正确分割，否则为错误分割，进而可以画出准确率(Precision)随返回区域数目(Recall)变化的曲线，如图7(a)所示.直接分水岭算法[2]仅通过预处理控制过分割，而基于距离变换方法[4]的准确性依赖于图像二值化的结果，在图像模糊、分辨率较低的数据上实验，它们的性能相对较差.

为了证明该分割方法对灰度、对比度和噪声变化的鲁棒性，以及计数方法的不变性，分别使原始图像经历Gamma变换、图像平滑、图像增强和加白噪声，再应用本算法，结果如表1所示.

对于不同的变换，表1第二列的参数意义不同：对图像平滑，是高斯模板的标准差；对Gamma变换，是γ值；对拉普拉斯模板图像增强，其为增强系数；对加白噪声，其为标准差.

进一步将表1中8个实验的准确率-查全率曲线绘制出来，如图7(b)所示，该结果说明本方法对图像降质具有很强的鲁棒性.

5结论

提出了采用分水岭算法辅以形态学特征和区域连接强度为指导的区域合并方法.该方法能够最大限度地发挥分水岭算法对微弱边缘的检测能力，基于形态学特征的区域合并算法则能够有效消除过分割.实验结果证明，在成像质量不高的场合，该算法较现有方法优越.

参考文献：

[1]徐蔚钦. 基于分水岭分割的粘连颗粒图像分析技术研究[D].长沙：中南大学信息科学与工程学院，2011.

[2]林小竹,王彦敏,杜天苍,等.基于分水岭变换的目标图像的分割与计数方法[J].计算机工程,2006,32(15): 181-183.

[3]BORGEFORS G. Distance transformations in digital images [J]. Computer Vision, Graphics, And Image Processing, 1986, 34(3):344-371.

[4]LIN H, TSAI M, CHEN C, et al. Cell segmentation and NC ratio analysis of third harmonic generation virtual biopsy images based on marker-controlled gradient watershed algorithm[C]//Seoul, Korea (South)：2012 IEEE International Symposium on Circuits and Systems (ISCAS). 2012: 101-104.

[5]VINCENT L, SOILLE P. Watersheds in digital spaces: an efficient algorithm based on immersion simulations [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(6): 583-598.

[6]SMET P D, PIRES R L, VLEESCHAUWER D, et al. Implementation and analysis of an optimized rain falling watershed algorithm[C]// Proceedings of SPIE. San Diego, USA: The International Society for Optical Engineering. 2000: 759-766.

[7]张立东, 毕笃彦.一种基于洪水消退模型的快速分水岭算法[J].模式识别与人工智能, 2006, 19(3): 349-360.

[8]HARIS H, EFSTRATIADIS S, MAGLAVERAS N, et al. Hybrid image segmentation using watersheds and fast region merging [J]. IEEE Transactions on Image Processing, 1998, 7(12): 1684-1699.

[9]XU Lu-lu, LU Hua-xiang. Automatic morphological measurement of the quantum dots based on marker-controlled watershed algorithm[J]. IEEE Transactions on Nanotechnology, 2013, 12(1): 51-56.

[10]BALLAED D, BROWN C, Computer vision[M]. Upper Saddle River, New Jersey，USA: Prentice Hall, 1982：247-158.

[11]赵琳，罗汉，刘京. 加权马氏距离判别分析方法及其权值确定[J].经济数学，2007，24(2): 185-188.

Segmentation and Counting of Granular Objects Based on Morphological Features

WANG Zhong-yong1, JIA Meng1, HOU Zhong-xin2, CHEN Zai-xu2

(1.School of Information Engineering，Zhengzhou University，Zhengzhou 450001，China； 2.Henan Gao-Yuan road maintenance equipment Corp., Xinxiang 453000, China)

Abstract:For the task of segmentation and counting of granular objects with low quality images, a new method which based on watershed and morphology is presented. First, an oversegmented result is gotten by conducting the watershed algorithm to the smoothed image. Then the region merge stage, which is directed by using the morphological features defined in this article, as well as weighted Mahalanobis distance and region adjacency graph (RAG), takes place. Experiments with real images demonstrate the validity of the method, that it is invariant under translation of gray scale, contrast and noise. And it performs better than any present method, in terms of precision-recall criterion.

Key words:segmentation and counting; watershed algorithm; morphological features; RAG

中图分类号：TP391

文献标志码：A

doi:10.3969/j.issn.1671-6833.2015.02.018

文章编号:1671-6833(2015)02-0080-05

作者简介：王忠勇(1965-)，男，河南郑州人，郑州大学教授，研究方向为无线通信技术，数字信号处理.

基金项目：国家自然科学基金资助项目(61172086)

收稿日期:2014-11-25；

修订日期：2015-01-03