改进的分水岭算法在粘连图像分割中的应用

张文飞 韩建海,2* 郭冰菁,2 李向攀,2 刘赛赛

1(河南科技大学机电工程学院 河南 洛阳 471003)2(河南省机器人与智能系统重点实验室 河南 洛阳 471003)3(郑州科技学院 河南 郑州 450000)

0 引 言

当前，我国的水果品质已经接近国际先进水平，然而水果市场的国际竞争力仍然很低，主要原因就在于我国的水果产后处理能力不足，其中像上线、清洗、烘干等处理比较容易解决，而水果分拣技术才是最核心的关键技术。但是我国目前水果检测和分拣技术仍比较落后，致使那些接近国际品质的水果没有被真正地分拣出来[1]。

目前，我国是世界上最大的原料药生产国和出口国，由于需求巨大，医药生产单纯靠人工劳动力无法满足，因此在很多医药生产线上出现了像机器人这样的自动化设备来代替人工完成一些生产工序，比如：医药生产、药品分拣、包装等，这些设备大都配有视觉装置，通过图像信息使自动化设备高效准确地完成作业任务。然而药品种类繁多，摆放杂乱无章，视觉机器人在分拣时容易出现漏捡、错捡的情况，造成的后果严重。所以不管是水果还是医药分拣，分拣的精度要求都是很高的，而分割又是分拣的核心一环，能否精确地将图像分割出来将直接影响后续分拣结果的好坏。

图像分割就是将图像中有意义或者感兴趣的目标区域提取出来，用于图像的后续处理[2]。但是由于设备或人为原因，以及图像在捕获、传输的过程中容易受到外界环境的影响，会使得到的图像质量降低，能否将目标物体从图像中准确分割出来将会直接影响后续图像处理的效果[3-4]。图像分割中比较难解决的问题就是图像的粘连性问题，在进行多种类水果和药盒无序分割时，若能解决水果和药盒之间的粘连性问题，将会很大程度上提高水果和药盒的分拣效率与检测精度。针对不同粘连程度的图像分割问题，研究者们提出了各种分割算法及其改进算法。基于形态学操作的图像分割算法具有简单、快速等特点，适用于简单图像的分割，但用于对粘连程度高的图像进行分割时，效果并不理想[5-6]。基于图论的图像分割算法会随着图像分辨率的提升而导致图的存储空间大、构图计算量大、计算速度慢等问题[7]。基于凹点匹配的图像分割算法分割效果依赖于能否正确匹配凹点，然而对于那些粘连程度比较高的图像，凹点是很难得到有效匹配的，也会导致分割不精确[8-9]。相对于其他图像分割算法，分水岭算法[10-11]对微弱边缘比较敏感，不容易丢失边缘信息，这也是解决粘连性问题的关键，但同时也会造成图像过分割的情况，影响分割精度。目前针对分水岭过度分割的问题，常见的解决方案有两种：一种是利用给分割图像制作一个掩膜标记来作为种子点引导分水岭分割；另一种是对分水岭分割后的图像利用一些区域合并准则合并相似区域。本文结合形态学运算和欧氏距离变换来改进传统的分水岭算法，用于分割粘连程度高的图像。实验结果表明，该算法在对于粘连程度高的多种类混合水果和药盒无序分割时具有很好的分割效果。

1 相关知识及算法流程

1.1 粘连图像的特征

1.1.1颜色特征

水果的种类多种多样，由于地域环境，生长时接收光照情况的不同，同一种水果也会出现很大的颜色差异，但主要还是以黄色、青色、红色为主。这些水果有些是纯色的，有些是混合颜色搭配的。药盒的种类更是多种多样，不同厂家有不同的设计风格，又加上药盒本身上面的颜色大都以混合颜色为主，所以对图像的分割造成了较大干扰。

1.1.2几何特征

水果的形状轮廓主要以圆形和椭圆形为主，药盒的形状轮廓主要以矩形为主，本文统一用图像轮廓外接圆来衡量其大小。实验主要分割外接圆大小在25 cm2以内的水果，长宽在16 cm×12 cm，也就是外接圆大小为314 cm2以内的药盒。水果原图和药盒原图如图1所示。

1.2 算法流程

本文提出了一种结合形态学运算和距离变换的改进分水岭分割方法。首先对图像进行前景提取[12-13]，得到目标图像，然后利用形态学运算去除噪声，接着制作掩膜标记，进行分水岭分割，这样可以在保证分割准确率的前提下大大提高粘连图像整体的分割效率。具体实现流程如下：

Step1输入粘连图像A，背景图像B，通过求取|A-B|≤阈值，提取前景图像P；

Step2输入图像P，用形态学运算去除多余的背景噪声，输出图像G；

Step3输入图像G，求取距离图像D，进行连通区域分析，得到标记图像M；

Step4结合形态学图像G，距离图像D，连通区域标记图像M，制作掩膜标记，进行分水岭分割。

2 算法原理及改进

2.1 递归双边滤波

2.1.1 递归双边滤波算法

对于粘连的水果或者药盒图像，由于图像中目标区域颜色和形状都很类似，若是用一般的滤波方法，比如高斯滤波、中值滤波，虽然能够得到一定的平滑图像，实现去除噪声的效果，但是对于粘连程度高的图像来说，在降噪的同时会使得部分边缘信息丢失。而递归双边滤波算法是一种高通滤波器，能够滤除掉图像中的低频信息，锐化像轮廓边缘这样的高频图像信息。相比传统双边滤波算法，递归双边滤波算法对值域滤波器核进行了约束，通过累积从像素坐标(i,j)到像素坐标(k,l)路径上相邻像素值的邻近性来实现[14]。

2.1.2 递归双边滤波算法的实现

从像素点(i,j)到像素点(k,l)有很多路径，本算法中采取的递归路径是先对像素点进行水平方向递归，在此基础上再对像素点进行垂直方向递归。递归双边滤波具体实现如下：

(1)

(2)

ω(i,j,k,l)=r(i,j,k,l)×d(i,j,k,l)

(3)

式(1)是递归双边滤波算法的值域核，表示从像素(i,j)到(k,l)相似像素值的递归；式(2)是递归双边滤波算法空域核，表示从像素(i,j)到(k,l)的空间域系数；式(3)是表示两个像素点的加权系数，取决于空域核和值域核的乘积。由于对值域核的递归约束，使得粘连图像中同一目标区域的像素彼此的依赖性更强，图像的粘连处边缘更加突出。

2.2 结合形态学运算的前景提取

形态学运算是图像处理中常用的一种数学工具。其基本思想是先构建一个结构元素，让其在图像中移动，与图像中的像素进行交、并集等集合运算[15-16]。本文用S(x)代表结构元素，(x,y)代表图像中的像素点，对于形态学中常用的腐蚀、膨胀、开运算、闭运算四种运算定义如下：

腐蚀：E=X⊙S={x,y|Sxy⊆X}

(4)

膨胀：E=X⊕S={x,y|Sxy∩A!=∅}

(5)

开运算：O=(X⊙E)⊕S

(6)

闭运算：C=(X⊕S)⊙S

(7)

为了后续图像精确分割，首先对粘连图像进行前景提取处理，本文采取的方式是先对前景信息进行粗提取，再进行精提取。具体实现方式如下：先采取一幅无前景图像的背景图像，然后将粘连图像与背景图像灰度化，进行相减，与设定的阈值比较，来达到图像前景信息的粗提取，这样就能去除大部分的背景图像信息，但是会有一些背景信息成为噪声点；接着再通过形态学运算，像处理传统噪声一样，来进行降噪处理，进行前景精提取，就能得到比较理想的前景信息。如图2、图3所示。

对于水果和药盒这两种粘连图像，通过实验测试，若是选取3×3的结构元素，则对图像腐蚀的程度会较低，达不到所需的去除背景噪声的效果；若是选取11×11或者更大的结构元素，会出现粘连图像边缘被腐蚀掉的情况。最终选取5×5的矩形内核结构元素，先对图像进行腐蚀操作，去除粘连图像中的一些离散噪声，收缩图像边界，再选取7×7的矩形内核结构元素对图像进行开运算，进一步平滑粘连物体边界的同时不明显改变其面积大小，就能将粘连图像的前景信息给提取出来。

2.3 距离变换

2.3.1距离变换的原理

在二维空间中，距离图像是对二值图像处理操作中常用的手段，其实质是将图像中每个非零像素与距其最近的零点像素的距离来作为距离图像相对应位置的像素[17-18]。距离图像可以使物体中心位置区域的像素更加突出，越靠近中心位置，像素灰度值越高，在距离图像中表现得越高亮；越靠近边界，像素值灰度值越低，图像表现得越晦暗。

2.3.2距离变换的实现

本实验采用欧氏距离变换，将一个大小为M×N的二值图像用一个二维数组AM×N=[aij]来表示，aij=1表示前景像素点，用aij=0表示背景像素点。假设背景像素集合表示为：B={(x,y)|aij=0}，前景像素集合表示为：F={(x,y)|aij=1}，则对集合A里面所有像素点(i,j)进行式(8)所示的距离变换；式(9)解释了欧氏距离计算方法。

dij=min{DE[(i,j),(x,y)],(x,y)∈B}

(8)

(9)

对水果和药盒图像做欧氏距离变换，得到距离图像，根据距离图像中像素距离背景像素越远图像越亮的特性，可以很容易确定粘连图像中超过某一阈值的高亮像素的大致位置。通过距离变换的水果和药盒图像如图4所示。

2.4 连通区域分析

连通区域指图像中位置相邻并且像素值相同的像素点组成的图像区域。本文采用的是基于种子填充法的连通区域分析，具体实现步骤如下：

1) 逐行扫描图像，直到当前像素点为前景像素，即P(x,y)=1。

(1) 将P(x,y)作为种子，并赋予其一个标签label，然后再将与该栈顶像素值相同的邻域像素都压入栈中；

(2) 弹出栈顶像素，赋予其相同的label，然后再将与该栈顶像素值相同的所有邻域像素都压入栈中；

(3) 重复步骤(2)，直到栈内元素为空，便找到了图像P中的一个连通区域，该区域内的像素值被标记为label；

2) 重复步骤1)，直到扫描结束，就可得到图像P的所有连通区域。

2.5 分水岭掩膜标记的制作

分水岭分割精度的高低取决于掩膜标记制作的好坏。本文掩膜标记的制作是结合形态学运算、距离图像和连通区域分析标记图像来共同制定的。具体实现为将形态学处理后的图像与距离图像二值化结果做差值运算，然后遍历差值后的图像像素，找出非零像素，并在连通区域标记图对应位置做上标记，即得到分水岭掩膜标记，如图5所示。

2.6 改进分水岭算法流程

改进后的分水岭算法实现过程大致为：先用递归双边滤波算法对彩色图像滤波，然后对图像进行灰度化、二值化、形态运算等操作，最后制作掩膜标记(mask)指导分水岭分割图像。改进后分水岭算法分割流程如图6所示。

3 实 验

本实验算法是在Ubuntu 16.04操作系统下，基于Clion IDE，采用C++语言进行编写和测试，实验数据来源于实验室利用kinect v2采集的混合水果数据和药盒数据。图7-图11列出了采用传统分水岭分割算法、图切割算法和结合距离变换的分水岭算法对水果和药盒图像的分割效果图。

从图8(a)、图9(a)、图10(a)、图11(a)可以看出，不管是水果数据还是药盒数据，传统分水岭算法分割的效果都不是很理想，过分割现象比较严重，主要原因是传统分水岭算法的分割过程是比较盲目的，易受噪声点的影响，产生过多的极小值点，在进行像素排序和模拟浸没的过程中，误把噪声点区域当成盆地，造成图像过度分割。从图8(b)、图9(b)、图10(b)、图11(b)可以看出，图切割算法的分割效果要比传统的分水岭算法要好得多，能够分割出粘连图像的大致轮廓，但存在的问题是很多目标轮廓之间是连通的，也会造成粘连分割定位不准确。从图8(c)、图9(c)、图10(c)、图11(c)可以看出，相比传统分水岭算法和图切割算法而言，结合距离变换的分水岭算法，对于种类比较多粘连程度比较大的目标物体分割精度提升很多。虽然此算法需要制作掩膜标记来引导分水岭分割目标物体，但是却在制作掩膜标记的时候，抛开了传统的将图像经过预处理再进行边缘检测的结果作为掩膜标记的思想，通过对图像做距离变换来突出目标物体的粘连部分，再对图像进行连通区域分析，根据形态学图像、距离变换图像，连通区域标记图像来制作分水岭的掩膜标记。这种掩膜标记制作方法在很大限度上缓解了分水岭掩膜标记制作不精确造成的过分割或欠分割的问题，对于水果和药盒的粘连图像分割具有很好的分割效果。

(a) 水果原图 (b) 药盒原图图1 粘连图像原图

(a) 前景粗提取 (b)前景精提取图2 水果图像前景提取

(a) 前景粗提取 (b) 前景精提取图3 药盒图像前景提取

(a) 水果距离图像 (b) 药盒距离图像图4 粘连图像的距离图像

(a) 水果图像掩膜标记 (b) 药盒图像掩膜标记图5 粘连图像的掩膜标记图像

图6 改进算法流程

(a) 水果原图 (b) 药盒原图图7 水果、药盒原图

(a) 传统分水岭 (b) 图切割算法 (c) 改进分水岭图8 水果分割算法比较

(a) 传统分水岭 (b) 图切割算法 (c) 改进分水岭图9 分割图像轮廓外接圆效果图

(a) 传统分水岭 (b) 图切割算法 (c) 改进分水岭图10 药盒分割算法比较

(a) 传统分水岭 (b) 图切割算法 (c) 改进分水岭图11 药盒分割效果图

为了进一步验证本文算法的优势，又分别使用500幅随意混合的水果图像和500幅随意混合的药盒图像来验证传统分水岭分割算法、图分割算法和改进的分水岭算法的分割正确率。分割正确率计算如下：

(10)

为了直观地比较三种分割算法在图像分割时间效率上的差别，以传统分水岭分割算法运算时间为标准进行对比，计算这三种算法的归一化运算时间：

(11)

三种分割算法实验结果正确率、归一化运算时间如表1、表2所示。

表1 三种分割算法分割水果结果比较

表2 三种分割算法分割药盒结果比较

由表1可以看出，传统分水岭算法分割水果图像时没有引导，分割比较盲目，每次分割都要进行像素排序，寻找种子点，再进行“模拟浸水”，比较费时，还容易受噪声点的影响，分割准确率也比较低，约10%左右。相比而言，图切割算法和改进后的分水岭算法分割时，效果要好很多，其中：图切割的分割时间约缩短至传统分水岭算法的三分之一，分割准确率达到了65.4%；本文改进后的分水岭分割算法的分割时间约为传统分水岭算法的五分之一，分割准确率达到了96.4%。

由表2可以看出，在对药盒图像进行分割时，传统分水岭算法由于分割时的局限性，分割时间比较高，分割准确率也是比较低的，约14.6%。而图切割算法对于药盒图像分割相比传统分水岭算法在分割时间与分割准确率上有了很大改善，时间缩短为传统分水岭的近三分之一，分割准确率也达到了74.8%。本研究中改进的分水岭分割算法相比前两种分割算法，在时间和分割准确率上都有很大提升，分割准确率更是达到了97.2%。

4 结 语

本文在传统分水岭算法的基础上，阐述了一种结合距离变换的标记分水岭算法，主要用于解决粘连程度比较大的目标物体的分割，在很大程度上改善了分水岭算法造成的过分割和欠分割问题，得到比较理想的分割效果。

本文改进后的分水岭算法，在水果和药盒图像的实验中，分割准确率达到97.2%，分割时间能稳定在90 ms左右。

由于水果种类和药盒种类比较多，后期还需要进一步改善算法，以便更适用于工业或医药等行业的应用。