基于改进FAST与分水岭算法的颗粒图像分割

， ，，，

(山东理工大学电气与电子工程学院，山东淄博255049)

在工业、农业、医学等领域中颗粒物质是普遍存在的，为了准确检测颗粒数量以及颗粒的粒径、粒形参数，需要利用图像处理技术对采集的颗粒图像进行处理，将目标区域从图像中提取出来，并将粘连的颗粒图像分割成单个区域，因此图像分割成为图像识别中至关重要的环节，但在实际图像处理过程中，由于颗粒本身形状不规则、大小参差不齐等原因，使得分割颗粒图像更加困难。

针对不同类型的粘连颗粒图像，学者们提出了各种分割方法及其改进方法。基于形态学操作的图像分割算法[1-2]具有方法简单、速度快等特点，但对粒径差距大、粘连程度高的颗粒分割效果不理想。基于凹点匹配的图像分割算法[3-4]，该算法的分割效果依赖于能否正确匹配凹点，但在实际应用中对于粘连情况比较复杂的颗粒图像，凹点就难以正确有效的匹配，导致未分割或错误分割。Vincent等[5]提出快速分水岭分割算法，可得到单像素封闭的分割图像，该算法对于微弱边缘有良好的响应，是图像分割中经典有效的一种算法，但由于颗粒图像本身局部不规则或其他原因，使得图像在分割过程中出现大量的伪极值点，容易造成严重的过分割。Qin等[6]提出基于扩展极大值变换的分水岭分割算法，通过不断迭代寻找最佳阈值，每次迭代重新进行分水岭算法，运算非常耗时。王鑫等[7]提出基于迭代腐蚀的分水岭分割算法，对于粘连程度高的颗粒容易造成欠分割情况。

计算机视觉中加速分割测试特征(features from accelerated segment test, FAST)算法[8]能够快速检测局部特征点，而基于h-maxima变换的分水岭算法(h-maxima分水岭算法)[9]可有效消除局部过分割现象。为了能够广泛的适用于各种粘连颗粒的准确快速分割，本文中通过改进FAST特征点检测算法，并结合h-maxima分水岭算法，实现一种与人眼分割效果类似的分割算法。根据不同颗粒特点和具体的分割要求，调整分割过程中阈值参数，可有效提高各种粘连颗粒分割的准确率及运算效率。

1 粘连颗粒分割算法

对于粘连图像的分割，需要对获取的颗粒图像进行图像预处理及边缘信息检测，为后续图像分割提供前提信息。预处理过程包括图像灰度化、图像二值化，并进行孔洞填充、开运算等形态学操作处理，最后获得颗粒二值图像。使用高斯拉普拉斯边缘检测算法[10]对二值图像进行边缘检测，获得单像素连续边缘图像及边缘点坐标信息。

1.1 H-maxima分水岭算法

分水岭图像分割原理是将一副灰度图像三维形象化，将地形学概念引入到图像分割中。分水岭分割算法可精准的定位图像边缘，形成封闭性强单像素的区域分割线。进行分水岭分割的灰度图像是由二值图像经距离变换得来的，距离变换是将二值图像中目标区域像素点到达最近背景点的距离表示为该像素点的灰度值，然后经过归一化处理，将二值图像重建成灰度值在[0,1]范围内均匀变化的灰度图像。为了满足精度要求，利用欧氏距离进行变换运算，但由于图像中颗粒边缘局部不规则，运算过程中容易出现一些伪极值点，即一个目标区域内有多个极值点，使得传统分水岭算法易造成过分割现象。

为了去除部分伪极值点，利用数学形态学操作中的h-maxima变换，可在一定程度上抑制过分割现象。设距离变换得到的灰度图像中极大值点灰度值为f，如果灰度图像中灰度值严格大于(f-h)的像素点可通过任一路径与极值点f相连，则划为一个连通区域，这样可以合并部分伪极值点。如式(1)所示，h-maxima变换抑制阈值小于h区域极大值点，以极大值点f为中心根据阈值h进行膨胀重构：

(1)

式中：X为距离变换后的灰度图像；RMAXh表示重建的极大值区域。

h-maxima分水岭算法阈值h一般取值范围在[0,1]，阈值h的取值只需保证分水岭脊线与二值图像获得的候选分割线每条都各对应2个边缘分割点即可。

1.2 改进FAST算法与边缘分割点检测

FAST算法原理是设定阈值t，比较半径为3像素圆上16个像素点的像素值与中心点p的像素值Ip，如图1所示。如果16个像素点中有N个连续点的像素值大于Ip+t或小于Ip+t，那么该中心点p为候选点。然后分别计算所有候选点与其周围16个像素点像素差值的绝对值总和，在以每个候选点为中心的邻域内进行比较，对检测出的候选点进行

图1 FAST算法检测模板Fig.1 Detection template of FAST algorithm

非极大值抑制。

FAST算法主要应用于整幅图像的局部特征点检测，为了准确提取粘连颗粒在粘连边缘处的边缘特征点信息，在FAST算法的基础上进行了改进。改进的FAST算法是根据高斯拉普拉斯边缘检测获得的边缘坐标信息遍历图像预处理后的二值图像边缘。将每个边缘点当作中心点pc，在二值图像边缘上统计以3像素为半径的圆上16个像素点pi(i=1,2,…,16)与中心点pc像素值相同，且可通过8邻接方式与中心点pc形成连通区域的像素点个数。边缘特征点检测过程需设定阈值T,如果符合要求的像素点个数不少于T，则认为中心点pc为所测边缘特征点pm，如式(2)所示。

(2)

通过利用h-maxima分水岭算法获得的分水岭脊线与边缘图像作与操作获得候选边缘分割点q，利用改进FAST特征点检测得到边缘特征点pm，以候选边缘分割点q为中心的5×5邻域内统计边缘特征点pm的个数，对候选边缘分割点q进行非极大值抑制。设定数量阈值M，如果边缘特征点pm的数量不少于M，则认为候选边缘分割点q为待边缘分割点，保留该点；否则，进行抑制。待边缘分割点集合形式如式(3)所示。

Sq=∪{q|Np≥M}，

(3)

式中：Sq代表待边缘分割点集合，Np为邻域内边缘特征点pm的个数。

利用待边缘分割点从分水岭脊线与二值图像进行与操作得到的候选分割线中提取待分割线，然后再利用边缘特征点识别每条待分割线对应的两边缘分割点是否存在不属于边缘特征点的伪边缘分割点，如果存在伪边缘分割点，则去除与伪边缘分割点相连的待分割线，最终得到正确的分割线进行图像分割。

通过上述过程进行颗粒图像边缘特征点检测及边缘分割点提取，如图2所示。

对图2a原始图像红框标识区域进行数字化表示，如图2b所示，1代表颗粒图像部分；0代表背景部分； 红色数字代表与边缘点像素值相同且可通过8邻接方式形成连通区域的像素点个数；黑色填充点表示候选边缘分割点q；红色方框表示对候选边缘分割点q进行非极大值抑制所使用的5×5邻域。当T取值12时会在图2b区域内可检测到5个边缘特征点，即大于等于12的像素点；同时设M阈值为3，那么候选边缘分割点q为待边缘分割点。通过同样的方式可确定图2a另一处边缘分割点同样属于待边缘分割点，同时这2个边缘分割点都属于边缘特征点，那么这2个点对应的待分割线就是最终要得到的分割线，进而实现粘连图像的正确分割。

a 原始图像

b图像的数字化表示图2 边缘分割点提取Fig.2 Edge segmentation points extraction

如图2b所示，在采用改进FAST算法提取边缘特征点的过程中，边缘分割点处边缘特征点像素值在[11,14]内，不同颗粒根据圆形度及黏连程度，边缘分割点处边缘特征点像素值会稍有变动，故阈值T在[10,13]内调节最为合理。阈值M的取值而很大程度上依赖于T的取值，阈值M一般在[3,5]取值，便可确定该点是否为待边缘分割点。

1.3 粘连颗粒分割算法流程与实现

粘连颗粒图像分割算法流程如图3所示。利用玉米颗粒进行图像分割处理，算法实现步骤如图4所示。

图3 粘连颗粒图像分割算法流程Fig.3 Process of image segmentation algorithm for touching particles

图4 粘连颗粒图像分割算法分割粘连玉米颗粒的实现过程Fig.4 Implementation of segmenting touching corn kernels by the touching particles image segmentation algorithm

由图4可知，1)对玉米原始图像4a进行图像预处理，得到图4b二值图像；2)采用h-maxima分水岭算法得到图4c分水岭脊线；3)通过分水岭脊线与二值图像作与运算得到图4d候选分割线，可以看出图4d中存在多条错误分割线；4)采用高斯拉普拉斯边缘检测得到图4e单像素连续边缘图像；5)通过分水岭脊线与边缘图像得到图4f，图中候选边缘分割点红框标识区域中存在错误边缘分割点；6)采用改进FAST特征值检测算法得到图4g边缘特征点；7)利用边缘特征点对候选边缘分割点进行非极大值抑制得到图4h待边缘分割点；8)利用待边缘分割点从候选分割线中提取待分割线得到图4i，图中待分割线红框标识区域仍有一处错误分割；9)判断待分割线对应2个边缘分割点是否都属于边缘特征点，识别伪边缘分割点得到图4j,利用图中伪边缘分割点去除与其相连的待分割线；10)最终得到图4k分割线；11)利用最终得到的分割线对图像进行分割得到图4l图像分割结果。

2 实验与对比分析

实验分别使用相机拍摄玉米颗粒图像、显微镜采集玻璃珠砂图像、动态图像颗粒分析仪采集自由落体盐颗粒图像。由于玉米颗粒费雷特直径[11]差距较大，玻璃珠砂粒径相差大，盐颗粒形状不规则，因此通过处理这3种具有代表性的颗粒图像，可以很好的比较各算法的优缺点。

分别采用传统分水岭算法、文献[6]基于扩展极大值变换的分水岭分割算法、文献[7]基于迭代腐蚀的分水岭分割算法、本文中提出的分割算法进行图像分割，并对分割结果进行比较。对玉米颗粒、玻璃珠砂颗粒和盐颗粒的分割结果如图5—7所示，其中各图中a为原始图像； b为传统分水岭算法分割结果；c为文献[6]基于扩展极大值变换的分水岭分割算法分割结果；d为文献[7]基于迭代腐蚀的分水岭分割算法分割结果；e为本文提出的分割算法分割结果。为了更好地对比分割结果，用不同颜色标识分割后的颗粒图像。

通过比较图5—7的分割结果图像可以看出，利用传统分水岭算法对图像进行分割，分割结果图像均产生大量过分割现象； 利用文献[6]算法对玻璃珠颗粒分割效果不错，玉米颗粒分割结果出现一处过分割错误，但对于边缘不规则的盐颗粒分割效果较差，易产生过分割现象； 而文献[7]算法对于玉米颗粒和盐颗粒分割效果较好，但对于颗粒粒径相差大、粘连程度高的颗粒图像易产生欠分割现象； 采用本文提出算法对3种粘连颗粒图像均实现了正确分割。为了进一步验证本文提出的算法对不同粘连颗粒分割更准确高效，利用传统分水岭算法、文献[6]算法、文献[7]算法、本文中改进算法对3种颗粒各50幅图像进行分割实验。

图5 玉米颗粒原始图像及分割结果图像Fig.5 Original images of corn kernels and images of segmentation results

图6 玻璃珠砂颗粒原始图像及分割结果图像Fig.6 Original images of glass beads and images of segmentation results

图7 盐颗粒原始图像及分割结果图像Fig.7 Original images of salt particles and images of segmentation results

以人眼手动分割结果作为标准，通过比较这4种算法的正确分割率、归一化运算时间来描述算法间的差别。正确分割率计算如式(4)所示。

(4)

为了直观地比较4种算法在图像分割时间效率上的差别，以传统分水岭算法运算时间为标准进行比较，如式(5)所示。

(5)

对3种颗粒分割实验结果正确分割率、归一化运算时间统计如表1所示。

表1 4种算法图像分割比较结果Tab.1 Comparison of four algorithms for image segmentation

由表1可以看出，文献[6]算法对于玉米和玻璃珠砂分割率相对于传统分水岭算法分别提高了52.16%和26.01%，对于盐颗粒分割效果虽然有很大改善，但分割正确率仍然偏低； 文献[7]算法在传统分水岭算法基础上提高了51.88%、17.90%、41.97%，而对于颗粒粒径差异大的玻璃珠砂分割正确率较低；本文中改进算法对于3种颗粒的分割效果最佳，正确分割率最高，在传统分水岭算法基础上分别提高了52.80%、27.37%、43.10%。从时间效率上比较，本文改进算法平均运算时间是文献[6]算法的1/3，是文献[7]算法的1/2。

经与其他3种算法相比较，本文提出的粘连颗粒图像分割算法对于以上3种不同颗粒分割结果均优于其他3种算法，在分割准确率以及分割时间效率上较文献[6]和文献[7]算法都有所提高。实验结果证明，本文中提出的改进算法适用范围更广，在提高运算效率的基础上同时也提高了正确分割率。

3 结论

1)本文中提出的一种基于改进FAST与h-maxima分水岭算法的粘连颗粒图像分割算法，极大地弥补了传统分水岭算法易导致过分割的缺点，最终实现各种粘连颗粒图像的高效分割。

2)改进算法适用范围最广，分割正确率均大于95%，在相对运算时间最短的情况下，图像分割结果的正确率最高。