一种粘连颗粒图像中心点的识别方法①

叶 明, 吴迪飞

(南京航空航天大学 机电学院,南京 210016)

一种粘连颗粒图像中心点的识别方法①

叶 明, 吴迪飞

(南京航空航天大学 机电学院,南京 210016)

针对粘连颗粒检测中的中心点提取问题,提出了一种基于改进广义Hough变换的检测算法.该算法首先计算已知图形的覆盖圆环,然后将圆环模板遍历待测图像前景轮廓点进行覆盖区域累加,最后得到累加图的极大值.该算法产生的圆环具有旋转不变性,能够大大缩减检测时间.同时实验表明,这种圆环模板累加的算法能够得到更加准确的定位中心点,并且部分消除了伪中心.

粘连颗粒;广义Hough变换;前景标记

随着科技的发展,数字图像处理已经在医疗,农业生产自动检测,工业生产自动检测等领域得到广泛应用.在实际应用中常常遇到需要对粘连的颗粒进行分离操作的情况,如粘连细胞图像的自动分割,农作物图像的自动分离,粘连纤维图像的自动分割等.

粘连颗粒的分离通常采用的是凹点匹配算法[1-3]和分水岭算法[4-6].凹点匹配算法的主要研究问题为:(1)凹点和凹区域的求取;(2)凹点的匹配规则.然而求得的凹点和凹区域可能会受到轮廓噪音的影响,在凹点匹配规则中常常使用的凹区域向量[1,2],轮廓切线[3]等同样会受到轮廓噪音的影响.这使得凹点匹配算法受到很大的限制.因此较复杂的粘连颗粒分割通常采用的是分水岭算法.然而传统分水岭算法又会产生非常严重的过分割问题,因此有学者提出了区域标注器(也叫前景标记)来解决这个问题[6].该算法的优势在于采用前景标记对单个颗粒进行标记,然后再做分水岭变换,所以可以有效地消除原有分水岭算法结果中的过分割现象.但是其准确性主要依赖于标记提取的准确性.现在采用的前景标记提取算法主要是形态学重构算法[4]和极限腐蚀算法[5].然而这两种算法对于粘连颗粒的形状缺陷(如颗粒内部出现孔洞的情况)的鲁棒性均不理想.虽然一些文献[7,8]中对这两种算法提出修改方案,但依然无法很好地解决单个颗粒内部存在孔洞的问题.

针对前景标记提取不准确的问题,本文尝试使用广义Hough变换来予以解决.广义Hough变换(Generalized Hough transform,GHT)是根据已知图形去寻找在待求图像中和已知图形相似的图形的常用算法[9].其主要思想是通过已知图形构造一种变换,称为GHT坐标变换.遍历待求图像前景轮廓点作GHT坐标变换,得到的坐标即是需要在累加空间进行累加的点的坐标.最后累加空间的极值点为目标的可能位置.其变换公式为:

GHT的优点有:(1)可以检测任意复杂的形状;(2)对于有一定遮挡和一定形变的图形具有较好的鲁棒性.因此,GHT对于单个颗粒内部的孔洞等形状缺陷的干扰应该具有比较好的抗干扰能力.但GHT算法的时间和空间复杂度都较高,并且若轮廓噪音比较大时,采用轮廓梯度方向作为索值并不准确.因此需要对其进行一定的改进.

有许多对GHT进行改进的文献,包括对于精度的改进和对于速度的改进.对于精度的改进主要有使用其他索值代替梯度方向的方法[9-12]以及对大量样本进行训练来优化R表的方法[13,14].对于速度的改进主要有减少待检测点的数量的方法[15],使用旋转不变量作为索值使GHT算法获得旋转不变性的方法[16,17]和采用GPU并行处理的方法[18].文献[16]中使用相邻轮廓点梯度向量的夹角作为索值,使GHT具有旋转不变性,累加空间从四维变成三维,从而大大缩减了运行时间.但由于使用了轮廓点的梯度方向,因此容易受到轮廓噪音的干扰.

针对GHT及其改进算法存在的问题,本文对GHT做了一些改进.包括:(1)采用累加模板对每个轮廓点进行覆盖累加,回避了轮廓梯度的计算,从而减弱了轮廓噪音的影响;(2)累加模板为圆环,从而使其具有旋转不变性,减少了运行时间.

由于GHT算法只能搜索相似的图形,加上本文算法的一些限制,因此研究的粘连颗粒对象具有如下特点:(1)颗粒之间具有相似性,并且可能存在旋转变换;(2)轮廓的内切圆和外接圆的比值较小,形状与圆接近;(3)颗粒之间相互粘连,有一定的遮挡和形变;(4)粘连颗粒大小基本一致,缩放比例可以近似忽略.此类颗粒中比较典型的颗粒是各种类圆形的化学纤维,本文以化学纤维为例对问题进行说明如图1所示.

图1 化学纤维横截面

1 改进的广义Hough变换

1.1 覆盖圆环

对于单个颗粒图形的轮廓,可以使用一个圆环将其完全覆盖,如图2所示.其中圆环的中心为轮廓的质心,并且要求圆环的面积最小.

图2 颗粒轮廓及其覆盖圆环

将这个覆盖圆环沿着图2轮廓进行覆盖区域累加.则圆环中心经过每个轮廓点时,圆环均覆盖到了轮廓的质心,所以质心将成为累加图的区域极大值点.并且由于该圆环的面积最小,因此造成的错误累加也最少.基于以上两点考虑,可以采用最小覆盖圆环模板累加的方式来求粘连颗粒的质心.

这样做的好处是即使轮廓上的点发生了扰动,只要扰动在一定范围内,潜在的质心点仍然会被覆盖到.从而在一定程度上减弱了轮廓噪音的干扰.同时,因为只需进行N2×M次加法运算(N为圆环的直径,M为待检测图像前景轮廓点的个数)而无需计算梯度和变换后的坐标,所以该算法运算速度很快.

当然,这种方法也存在一些可能的问题.包括比例系数s,异形度λ等带来的影响.这些影响因素会在算法的实现和讨论中有所讨论.异形度λ的定义公式[19]为:

其中rmax和rmin分别是圆环的大小圆半径.λ值越小,颗粒的轮廓越接近于圆.

1.2 算法描述

算法分为两步:(1)圆环累加模板的制作;(2)进行模板累加并求极值点.算法流程图如图3所示.

图3 算法流程图

1.2.1 模板的制作

模板的制作是一个由已知图形得到最小覆盖圆环的过程.其具体步骤如下:

① 求模板图像的轮廓图;

② 求模板图像轮廓的质心(xr,yr),将质心作为参考点;

③ 求轮廓上每个点到参考点的距离,记录在dist中,其中dist为1×N的行向量,N为轮廓点的个数.令distmax=max(dist);

④ 确定模板Rtable的大小为边长等于(2*distmax+1)的正方形矩阵.对于每个dist(n),遍历Rtable中每个点(xk,yk),判断是否满足:

图4 累加圆环模板

本文中的模板图形选取采用人工选取的方式.主要是因为颗粒轮廓彼此之间具有相似性,由颗粒轮廓得到的distmax和distmin差距较小.模板图形会对结果产生些许影响,体现在中心点的位置不是完全重合上.

1.2.2 中心点的识别

中心点的识别过程是由求得的覆盖圆环模板和待检测图像找出粘连颗粒质心的过程.本文以图1作为样例进行说明,为了证明本文算法的有效性,对图1的二值图做了一些修改,具体为增加了凹陷,空洞和断裂等缺陷如图5(b)所示.

图5 样例的二值图

中心点识别的具体步骤如下:

① 计算待检测图像的前景轮廓.

② 置Acc为和待识别图像相同大小的零矩阵,作为累加空间.遍历待识别图像的每个轮廓点,将其与Rtable的中心点对齐.设Rtable覆盖的区域为Si,则Acc(Si)=Acc(Si)+1,其中下标i是轮廓点的编号.最终得到累加图Acc,如图6所示.

图6 样例的累加图Acc

③ 对Acc进行归一化处理,Acc=Acc max(Acc).

④ 令Acc2为和Acc大小相同的零矩阵.对Acc作阈值处理,令阈值为threshold.Acc中大于等于threshold的点在Acc2中置1,小于的点置0,如图7所示.threshold通常取0.4～0.9.

图7 阈值化后得到的待选点集

⑤ 遍历Acc2中的前景点(像素值为1的点),判断在Acc中,以这个点为中心,半径为R的圆形区域内,其是否为这个区域的最大值.若是,则将其坐标记录在(cx,cy)中,结果如图8所示.其中R是设定的阈值.R通常取0.6～0.8个distmax.

图8 待选点集中的区域极大值点,R取0.8*distmax

2 算法的实现和讨论

为了进一步说明算法的可行性,本文采用两组形状为“三角形”和“五角形”的粘连颗粒图像,应用文中算法与基于形态学重构的标记提取算法、经典的GHT算法进行仿真对比实验.本文所使用的实验平台为:PC机,主频2.2 GMHZ,内存3 G,Matlab9开发环境.由于三角形源图存在非均匀光照现象,因此使用了文献[4]中的方法进行二值化.五角形源图的二值化算法采用otsu算法,运用canny算子来获取两张图像的边缘图.

由表1可知,GHT算法在搜索与已知图形之间没有角度变换的图形所用时间比本文方法更长.因此,本文的方法在时间复杂度上小于GHT算法.由图9(e)和图10(e)可以看出GHT算法得到了一些伪中心点.产生伪中心点的主要原因分为两类:(1)附近其他轮廓的干扰以及轮廓形变的影响使中心点发生偏移;(2)旋转过程造成了前景区域外部出现了区域极值点.第一种伪中心点不易消除.第二种伪中心点的累加值较小,若增大threshold的值就能够在一定程度上消除这些伪中心点.但由于部分轮廓的缺失,导致前景中有一些中心点的累加值也比较小,如果增大threshold就会出现中心点的遗漏.因此GHT算法并不能很好地解决该类问题.本文的算法减弱了梯度方向的影响,加强了算法对于轮廓形变的鲁棒性,因此可以有效减少GHT算法中的第一类伪中心点的数量,同时仅在两个相邻颗粒的部分轮廓构成了已知图形的一部分轮廓时才会在前景区域外围形成区域极值点.

表1 本文方法和GHT算法运行时间对比(单位:秒)

由图9(d)和图10(d)可知,使用形态学重构计算纤维中心点的算法,若纤维上出现比较明显的孔洞和凹陷时,会将一个纤维误检为多个.该算法中使用到了距离变换来生成距离图.距离图中一个前景点的像素值是该点到所有轮廓点的最小距离,因此距离图的生成对于孔洞和凹陷比较敏感.若能够修正距离图,减少孔洞和凹陷,则可以在很大程度上消除误检的情况.本文的做法是在中心点识别准确的情况下,使用半径为r的圆来覆盖中心点区域,被覆盖的区域全部置1.

图9 三角形粘连颗粒源图和中心点识别图

图10 五角形粘连颗粒源图和中心点识别图

以图5(b)为例进行说明,图11中的r取值为distmin.对比图11(a)和(c)可以看出修正后的标记结果得到了非常大的改善.这种距离图修正的方法是建立在中心点的识别准确的基础上的.若识别的中心点因为形状误差发生偏移,则需要将r的取值减小.r取值减小后的修正效果将有所下降.

相比于GHT算法和其他相关算法,本文的方法可能会存在一些缺陷.如比例系数和异形度等对于算法的影响.对于不同尺度颗粒相互粘连的情况,使用缩放后的圆环来进行累加.当使用较小的圆环累加时,可能在较大颗粒内部形成多个区域极值点.当小颗粒的轮廓存在遮挡,使得其中心累加值较小时就无法使用阈值来过滤大颗粒内部形成的伪中心点从而出现错误的识别.如图12(b)所示,若下方两个小三角形的轮廓被部分遮挡,则其中心累加值将减小.当异形度较大时,颗粒将变成条状.这类颗粒的最小覆盖圆环的小圆半径很小,覆盖圆环与圆接近,使得累加图中出现大量冗余的累加,导致识别失败,如图12(d)所示.

图11 二值图修正的分水岭分割

图12 比例系数和异形度的影响

3 结语

本文提出了一种针对一类粘连颗粒的中心点识别算法.首先根据已知图形计算圆环覆盖模板,然后将圆环模板沿待检测图像轮廓进行覆盖累加.得到的累加图的极值点即各个纤维的中心.该算法计算出的覆盖圆环具有旋转不变性,大大降低了算法的时间复杂度,并且具有较高的准确性,是一种可靠的检测类圆形粘连颗粒中心的算法.得到的中心点对于距离变换图的修正可以起到指导作用,从而使得分水岭算法分割的准确度得到提高.

1 Farhan M,Yli-Harja O,Niemistö A.A novel method for splitting clumps of convex objects incorporating image intensity and using rectangular window-based concavity point-pair search.Pattern Recognition,2013,46(3):741–751.[doi:10.1016/j.patcog.2012.09.008]

2 Kumar S,Ong SH,Ranganath S,et al.A rule-based approach for robust clump splitting.Pattern Recognition,2006,39(6):1088–1098.[doi:10.1016/j.patcog.2005.11.014]

3 韦冬冬,赵豫红.基于凹点匹配的重叠图像分割算法.计算机与应用化学,2010,27(1):99–102.

4 倪志强,叶明.基于分水岭变换的粘连颗粒图像分割方法.计算机系统应用,2014,23(6):93–97.

5 戴丹.基于改进分水岭算法的粘连颗粒图像分割.计算机技术与发展,2013,(3):19–22.

6 Meyer F,Beucher S.Morphological segmentation.Journal of Visual Communication and Image Representation,1990,1(1):21–46.[doi:10.1016/1047-3203(90)90014-M]

7 刘相滨,邹北骥,孙家广.菌群细胞图像分离算法研究.电子学报,2005,33(6):1056–1059.

8 李希,王天江,周鹏.一种改进的粘连颗粒图像分割算法.湖南大学学报(自然科学版),2012,39(12):84–88.[doi:10.3969/j.issn.1674-2974.2012.12.015]

9 李智磊,翟宏琛,王明伟.一种可识别破碎图形的特殊广义Hough变换方法.物理学报,2007,56(6):3234–3239.[doi:10.7498/aps.56.3234]

10 胡正平,杨苏.基于关键特征点决策的广义Hough变换目标定位快速算法.信号处理,2009,25(11):1748–1753.[doi:10.3969/j.issn.1003-0530.2009.11.016]

11 刘宏申,程健.广义Hough变换算法的分析改进.中国科学技术大学学报,2009,39(11):1202–1206.

12 Kontschieder P,Riemenschneider H,Donoser M,et al.Discriminative learning of contour fragments for object detection.Proc.of the British Machine Vision Conference.Dundee,UK.2011.

13 Gall J,Lempitsky V.Class-specific Hough forests for object detection.2013 IEEE Conference on Computer Vision and Pattern Recognition.Miami,FL,USA.2009.1022–1029.

14 Opelt A,Pinz A,Zisserman A.A boundary-fragment-model for object detection.Computer Vision-ECCV 2006,9th European Conference on Computer Vision.Graz,Austria.2006.575–588.

15 Xu L,Oja E,Kultanen P.A new curve detection method:Randomized Hough transform (RHT).Pattern Recognition Letters,1990,11(5):331–338.[doi:10.1016/0167-8655(90)90042-Z]

16 Tsai DM.An improved generalized Hough transform for the recognition of overlapping objects.Image and Vision Computing,1997,15(12):877–888.[doi:10.1016/S0262-8856(97)00033-4]

17 杨华,尹周平,王瑜辉,等.基于局部不变几何特征的广义霍夫变换图像匹配方法:中国,CN103456005A.[2013-12-18].

18 侯怡婷.基于CUDA的Hough变换并行实现[硕士学位论文].大连:大连理工大学,2013.

19 尹平平.喷丝板微孔中熔体流动及异形纤维成形过程的研究[硕士学位论文].上海:东华大学,2006.

Detection Method for the Center of Touching Particle Image

YE Ming,WU Di-Fei
(College of Mechanical Engineering,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Aiming at the problem of detecting the centers of touching particles images,a detecting method based on the improved Generalized Hough transform is proposed in this paper.The method firstly figures out the ring that overlaps the known particle’s outline,then the overlapping area of the ring template is accumulated along the foreground contour of the image to be detected.Finally,the region maximum value of the accumulated matrix will be the centers of the particles.The ring template has rotation invariance so that the detection time will be shortened greatly.Meanwhile,the result shows that the method in this paper has fine detection effect.

touching particles;the Generalized Hough transform;foreground makers

叶明,吴迪飞.一种粘连颗粒图像中心点的识别方法.计算机系统应用,2017,26(9):181–187.http://www.c-s-a.org.cn/1003-3254/6048.html

① 基金项后:南京航空航天大学基本科研业务费专项科研资助项后(NS2014051)

2016-12-29;采用时间:2017-03-16