朱立军,苑玮琦
一种改进蚁群算法的睫毛提取
朱立军1,2,苑玮琦1
( 1. 沈阳工业大学 信息科学与工程学院,沈阳 110870;2. 沈阳化工大学 计算机科学与技术学院,沈阳 110142 )
睫毛检测是虹膜识别预处理阶段的一个重要环节,本文提出一种基于改进蚁群算法的睫毛提取方法。该方法首先通过引入睫毛区域内、外方向因子使得人工蚂蚁能快速聚集到睫毛边缘,并且通过采取全局和局部两种策略来对信息素进行更新,然后使用OTSU算法根据所得图像的信息素浓度把图像分割成睫毛边缘和非睫毛边缘两部分。最后,对分割出的睫毛边缘进行整合、除噪,得到最终的睫毛。实验结果表明:该方法提取睫毛的效果较其他相关算法有明显的提高;并且当人工蚂蚁间距取约25 pixels的时候,算法既能保证睫毛检测的速度又能保证睫毛检测的效果。
蚁群算法;人工蚂蚁;睫毛检测;OTSU;虹膜识别
0 引 言
虹膜识别由于具有普遍性、唯一性、稳定性、非侵犯性等优点,所以被认为是目前最具潜力的生物特征识别方法之一。睫毛的主要作用是用来阻挡灰尘等异物进入眼睛,然而在提取虹膜特征时,睫毛有时可能不同程度地对虹膜形成遮挡,从而影响了真实虹膜特征的提取。因此,在虹膜识别的预处理阶段,准确地检测出睫毛遮挡区域是保证虹膜识别准确率非常重要的一个环节。
目前关于睫毛检测的主要方法包括:Kong Waikin等[1]把睫毛分成分散和聚集两类,对分散睫毛采用一维Gabor滤波器与图像做卷积,如果结果小于给定的阈值,则判断为睫毛;对于聚集睫毛的检测,则使用一个5´5的小矩形窗口,如果窗口的灰度差小于预设阈值,则该矩形窗口的中心就可判定为一个睫毛点;Huang Junzhou等[2]首先根据相位一致性提取噪声的边缘信息,然后结合边缘和区域的信息来定位眼睫毛区域;Suhad A等[3]首先对图像进行灰度变换来增强图像的对比度,然后采用Soble算子根据给定阈值来检测睫毛;Walid Aydi等[4]首先求出图像的对角梯度,然后通过预设阈值来提取睫毛;苑玮琦等[5]提出采用多种不同的方法,通过选取相应的阈值提取睫毛点,然后再把这些提取到的睫毛点组合起来形成最终的睫毛。来毅等人[6]使用灰度形态学的方法,将形态学运算后的图像二值化,即可检测出眼睫毛。
以上方法大多是采用人工预设阈值的方法来判定某个像素是否属于睫毛。这种方法的优势是简单、高效,而局限性是由于最优阈值往往难以得到,从而造成睫毛检测的结果不够令人满意。因此,为了进一步提高睫毛检测的效果,本文提出一种新的基于改进蚁群算法的睫毛提取方法,该方法不是通过人工预设阈值的方法来判定睫毛,而是先通过人工蚂蚁搜索睫毛边缘,在搜索的过程中不断增强睫毛边缘的信息,同时削弱非边缘信息,然后再通过OTSU算法[7]自动找到最优睫毛分割阈值。这样就能保证较好的睫毛分割效果。
1 改进蚁群算法提取睫毛的原理
蚁群算法是1991年意大利学者Dorigo M[8]等人从蚂蚁群体觅食行为的过程中得到启发, 提出的一种模拟蚂蚁行为的模拟进化算法,我们称为基本蚂蚁算法(AS)。由于该算法具有信息正反馈、分布计算和启发式搜索等特点,近些年来已经被成功地应用于路径优化[9],故障诊断[10]以及图像分割[11-16]。
对虹膜图像进行睫毛提取的过程可以理解为模拟蚂蚁行为的人工蚂蚁觅食过程。把图像看成二维矩阵,每个像素位置对应矩阵中的一个元素,每´像素区域里放一只人工蚂蚁。由于睫毛的特点是像素灰度值较低且边缘梯度较高,根据这一特点,人工蚂蚁的搜索目标就是灰度值小且梯度大的像素。为了提高睫毛提取的精度,在睫毛区域内部引入局部方向因子,该因子引导人工蚂蚁向离他较近的且信息素浓度较高的睫毛靠近;同时分别采取全局策略和局部策略来对信息素进行更新,使得睫毛边缘的信息素浓度进一步得到了增强。这样通过若干步迭代后,睫毛边缘的信息素浓度就会明显的高于非睫毛边缘区域的信息素浓度,然后再根据OTSU算法对所得到的图像进行分割就能很容易地分割出睫毛边缘。最后,对分割出的睫毛边缘进行整合、除噪,得到了最终的睫毛。算法流程图如图1所示,其中关键步骤如下。
图1 睫毛提取算法流程图
1.1 睫毛提取区域的确定
根据对大量虹膜图像观察发现:一般人的睫毛遮挡虹膜的范围为瞳孔中心以上区域,所以,我们选择睫毛提取(Eyelash Abstract, EA)区域为图像中以瞳孔的中心为底线的以上部分,如图2中粗黑线以上阴影部分所示。
图2 睫毛提取区域的确定
1.2 睫毛提取区域信息素初值的确定
另外,由于瞳孔边缘处的梯度较大且灰度较低,对人工蚂蚁路径选择会形成干扰,所以对瞳孔及其边缘附近区域的信息素初值置0。
1.3 转移概率的定义
人工蚂蚁每次从当前位置,在八邻域范围内按照转移概率选择下一步要到达的位置。在这里,对转移概率定义如下:
,分别表示EA区域的高度和宽度。表示位置和之间的距离。当人工蚂蚁走进睫毛区域内部时,参数使得人工蚂蚁在搜索睫毛边缘时,即考虑信息素浓度较高的边缘方向,同时也考虑了信息素浓度较低却距离较近的边缘方向,从而保证了睫毛提取的精度。
1.4 信息素更新策略
每只人工蚂蚁走完规定的步数后,各位置处的信息素根据式(7)进行调整:
为了进一步提高目标的信息素浓度,还采用信息素局部更新策略,引入参数
当第只人工蚂蚁遍历之后,位置处的信息素增量依据和的大小成比例的进行相应的调整,这样信息素越高的地方信息素增长越快,信息素越低的地方信息素增长越慢,从而有利于进一步提高睫毛提取效果。
1.5 睫毛边缘的分割
当所有蚂蚁按照方向转移策略和信息素更新策略遍历图像的过程中,睫毛边缘的信息素浓度会越来越大,当所有蚂蚁遍历完后,睫毛边缘的信息素浓度总体上就会明显比非睫毛边缘信息素浓度高。然后采用OTSU算法得到图像二值化的最优分割阈值,高于阈值的部分为睫毛边缘,像素灰度值设为255;低于阈值的部分分为非睫毛区域,像素灰度值设为0。
1.6 睫毛的整合
由于蚁群算法搜索的目标是梯度大且灰度小的像素,并且睫毛本身存在一定的宽度,因此采用如上方法提取到的是中间存在空隙的睫毛。为了得到完整的睫毛,需要对空隙进行填充。根据大量实验观察发现中间的缝隙宽度大约小于3 pixels。为了去掉中间的空隙,提取出完整的睫毛,分别求出目标二值睫毛图像的左、右边缘的图像,由于睫毛灰度的特点是中间低两边高,所以,左边缘的判别方法是:该位置是边缘(二值图像灰度值255)并且原始灰度图像中该位置右边像素灰度值一定比当前位置的低;同理右边缘的判别方法是该位置是边缘(二值图像灰度值255)并且原始灰度图像中该位置左边像素灰度值一定比当前位置的低。然后采用如下式显示最终的睫毛。
1.7 采用序列滑动窗口消除噪声
采取如上算法提取出的睫毛会存在一些噪声,为了进一步提高睫毛提取效果,需要进行除噪。根据观察发现睫毛一般是连续的,而这些噪声是一些孤立的斑点。采用序列滑动窗口来消除噪声。窗口序列的边长为3~pixel,窗口厚度为1 pixel,首先,采用3´3的窗口逐像素滑过图像,在滑动过程中,如果周围8个像素位置均没有灰度值为255的像素,而中间像素为255的像素,则确定该像素为噪声,把它的值改为0。然后,依次使用边长为4~的窗口采用同样的办法消除被窗口包围的噪声。
注意窗口选择不能太大,如果过大不但增加程序运行时间,而且有时会把睫毛误当做噪声消除,从而影响了睫毛提取的精度;如果选择过小,则有些噪声不能去除。经验表明,取5较为理想。
2 实验结果与分析
实验分别采用中科院自动化所的CASIA-IrisV1虹膜图库和本研究室自己采集的虹膜图库进行验证。其中CASIA-IrisV1库虹膜图像分辨力为320´280,本研究室自采集虹膜图像分辨力为800´600。实验所用机器的主频是2.71 GHz,内存为2 G,操作系统为Windows XP,编程所用工具为Visual C++2010。由于文献[1]和文献[4]都是针对没有进行规范化处理的虹膜图像。所以选择这两个算法与本文的算法进行对比。另外,文献[1]和文献[4]提取睫毛时都会产生噪声,为了对算法进行客观的比较,这两种算法对噪声的过滤也是采用和本文一样(1.7小节)的方法。本文算法主要参数的典型设置:图像梯度阈值=45;转移概率各因子的权重分别为=4,=2,;信息素更新,;蚂蚁属性设置=3 000,=25。
2.1 睫毛的提取效果比较
从图3可以看出:图3(b)、图3(c)算法提取的睫毛存在很多中断的现象,这主要是由于同一根睫毛不同部位的灰度值往往是不同的,而判定阈值却是恒定造成的。相比之下,图3(d)本算法提取的睫毛连续性比图3(b)、图3(c)算法有了明显的提高。同时,从图中还可以看出:对于睫毛较密的区域(如睫毛左上部分),相对其他算法,图3(d)算法提取的效果也较理想。图4是采用本研究室自采集虹膜图像进行睫毛检测的结果,由图4(d)可知,睫毛的提取效果要优于其他两种算法。
图3 不同算法对CASIA-IrisV1库虹膜图像睫毛检测效果的比较
需要指出的是,虽然本算法在提取睫毛的效果上优于其他算法,但仍然存在漏判和误判现象。其中漏判现象如图3(d)、4(d)中黑色箭头所示,从图中可以看出,箭头所指的睫毛并没有被完整地提取出来,其主要原因是由于这些睫毛末端的灰度值与背景较接近,且梯度值较小,所以人工蚂蚁较难识别,造成漏判;另外,当虹膜内部存在某些特征纹理(如裂缝、坑洞等),而这些特征纹理的边缘与睫毛较相似的时候,就会容易造成误判。如图4(d)中白色箭头所示。
图4 不同算法对本研究室自采集虹膜图像睫毛检测效果的比较
2.2 蚂蚁间距与运行时间和睫毛检测效果的关系
为了分析运行时间与人工蚂蚁间距的关系,分别在不同像素间距处放一只人工蚂蚁,得到算法的平均运行时间和人工蚂蚁间距的关系如图5所示。由图5可知,人工蚂蚁间距越大、算法运行时间越短;而人工蚂蚁间距越小,算法运行时间越长。当人工蚂蚁间距小于20 pixels的时候,程序的运行时间随着人工蚂蚁间距的增加下降较快;而当人工蚂蚁间距大于20 pixels的时候,程序运行时间下降较缓慢。
图5 蚂蚁间距与运行时间关系
另外,由实验可知,人工蚂蚁间距越大,睫毛提取的效果越差;间距越小,提取效果越好,以图3(a)为例,图6分别是采用本算法使用不同间隔数目人工蚂蚁提取睫毛所花费的运行时间及运行效果。可以看出,图6(a)和图6(b)效果差别并不明显,而图6(c)提取的睫毛则出现了明显的断裂。
图6 不同的间隔数和运行时间下的效果图
权衡如上两方面的因素并经过反复实验验证得出:当选取人工蚂蚁间隔数目取25 pixels时,既能保证较好的睫毛提取效果,又使得程序的运行时间较短。
3 结 论
本文提出了一种新的基于蚁群算法的睫毛提取算法,该算法不是通过人工预设阈值来判断睫毛,而是先通过人工蚂蚁的遍历来增强目标(睫毛边缘)的信息强度,然后使用OTSU算法自动获得最佳睫毛分割阈值。实验结果表明:与其他睫毛检测算法相比,该算法提取睫毛的效果有了明显的提高。并且通过实验验证,当人工蚂蚁间距取25 pixels的时候,既能保证睫毛检测的速度又能保证睫毛检测的效果。
由于本算法搜索的目标是灰度小、梯度大的像素。所以当睫毛的颜色与背景较接近,虹膜内部存在与睫毛特征相似的纹理边缘时,就可能造成漏判和误判。这是我们今后工作要进一步研究和解决的问题。
[1] WANIKIN K,DAVID Z. Detecting eyelash and reflection for accurate iris segmentation [J]. International Journal of Pattern Recognition and Artificial Intelligence(S0218-0014),2003,17(6):1025-1034.
[2] HUANG J Z,WANG Y H,TAN T N,. A new iris segmentation method for recognition [C]// Proceedings of the 17th International Conference on Pattern Recognition. Cambridge,UK,Aug 26,2004,8:554-557.
[3] ALI S A,LOAY D,GEROGE E. Iris Recognition System Based on Texture Features [J]. International Journal of Network Security(S1816-353X),2014,6:1-11.
[4] AYDI W,KAMOUN L,MASMOUDI N. A Fast and Accurate Eyelids and Eyelashes Detection Approach for Iris Segmentation [J]. Journal of Multimedia Processing and Technologies(S0976-4127),2012,3(4):166-173.
[5] 苑玮琦,徐露,林忠华. 一种新的虹膜图像预处理方法 [J]. 光电子·激光,2009,20(2):234-239.
YUAN Weiqi,XU Lu,LING Zhonghua. A novel method of iris image preprocessing [J]. Journal of Optoelectronics. Laster,2009,20(2):234-239.
[6] 来毅,路陈红,卢朝阳. 用于虹膜识别的眼睑及眼睫毛遮挡检测 [J]. 计算机辅助设计与图形学报,2007,19(3):346-350.
LAI Yi,LU Chenhong,LU Zhaoyang. Eyelid and eyelash occlusions detection for iris recognition [J]. Journal of Computer-Aided Design & Computer Graphics,2007,19(3):346-350.
[7] 贾永红. 数字图像处理 [M]. 武汉:武汉大学出版社,2009:146-149.
JIA Yonghong. Digital Image Processing [M]. Wuhan:Wuhan University Press,2009:146-149.
[8] COLORNI A,DORIGO M,MANIEZZO V,. Distributed optimization by ant colonies [C]// Proceedings of ECAL91 (European Conference on Artificial Life),Paris,France,1991:134-142.
[9] 许川佩,蔡震,胡聪. 基于蚁群算法的数字微流控生物芯片在线测试路径优化 [J]. 仪器仪表学报,2014,35(6):1417-1424.
XU Chuanpei,CAI Zhen,HU Chong. On-line test path optimization for digital microfluidic biochips based on ant colony algorithm [J]. Chinese Journal of Scientific Instrument,2014,35(6):1417-1424.
[10] 王家林,吴正国,杨宣访. 基于蚁群神经网络的线性直流电源故障诊断 [J]. 仪器仪表学报,2009,30(3):515-520.
WANG Jialin,WU Zhengguo,YANG Xuanfang. Fault diagnosis of linear DC electric source based on ant colony algorithm and neural network [J]. Chinese Journal of Scientific Instrument,2009,30(3):515-520.
[11] SUSMITA G,MEGHA K,ANINDYA H,. Use of aggregation pheromone density for image segmentation [J]. Pattern Recognition Letters(S0167-8655),2009,30(3):939-949.
[12] RAL P,DUTTA M. Image edge detection using modified ant colony optimization algorithm based on weighted heuristics [J]. International Journal of Computer Application(S0975-8887),2013,68(5):5-9.
[13] PANIGRAHY M P,AHMED S. Image edge detection based on ACO technique [J]. International Journal of Computer Science and Telecommunications(S2047-3338),2013,4(1):42-46.
[14] ZHANG Jian,ZHOU Jiliu,HE Kun,. Image edge detection using quantum ant colony optimization [J]. International Journal of Digital Content Technology and its Application(JDCTA)(S1975-9339),2012,6(11):187-195.
[15] TYAGI Y,PUNTAMBEKAR T A,SEXENA P,. A hybrid approach to edge detection using ant colony optimization and fuzzy logic [J]. Internal Journal of Hybrid Information Technology(S1738-9968),2012,5(1):37-46.
[16] YE Z G,MOHAMADIAN H,YE Y M. Quantitative analysis of feature detection using adaptive canny edge detector and enhanced colony optimization [J]. International Journal of Modeling and Optimization(S2010-3679),2012,2(4):384-390.
An Eyelash Extraction Method Based on Improved Ant Colony Algorithm
ZHU Lijun1,2,YUAN Weiqi1
( 1. School of Information Science and Engineering, Shenyang University of Technology, Shenyang 110870, China; 2. School of Computer Science and Technology, Shenyang University of Chemical Technology, Shenyang 110142, China )
Eyelash detection is an important step during the period of iris recognition preprocessing. An eyelash extraction algorithm based on improved ant colony algorithm is proposed. Firstly, by introducing direction factor of inside the eyelash region and outside the eyelash region, the artificial ant can gather to the eyelash-edge quickly, increasing pheromone intensity of eyelash-edge and decreasing that of non-eyelash-edge. At the same time, global and local strategies are taken respectively to update pheromone. After that, the OTSU algorithm is used to segment eyelash edge according to the pheromone intensity of image. Finally, by integrating the eyelash-edge and deleting the noise, the eyelash can be obtained. Experimental results show that, compared with other concerned algorithms, the effect of the proposed method is better than that of others, and when the distance between artificial ants is about 25 pixels, the algorithm can not only ensure eyelash detection speed but guarantee the detection effect.
ant colony algorithm; artificial ant; eyelash detection; OTSU; iris recognition
1003-501X(2016)06-0044-07
TP391. 41
A
10.3969/j.issn.1003-501X.2016.06.008
朱立军(1972-),男(汉族),辽宁沈阳人。讲师,硕士,主要研究方向为生物特征识别。E-mail: zhulijun@yeah.net。
2015-09-02;
2015-12-01
国家自然科学基金(61271365)