基于多智能体系统的自适应指纹图像分割算法

2011-01-25楚亚蕴詹小四

浙江外国语学院学报 2011年1期

汪媛,楚亚蕴,詹小四

(1.浙江外国语学院,浙江杭州310012;2.山东大学计算机科学与技术学院,山东济南250101;3.阜阳师范学院计算机与信息学院,安徽阜阳236041)

1 引言

近年来,传统的基于特定物品或知识的身份识别方法已经无法满足现代信息社会的实际应用需要,如何准确、可靠地对人的身份信息进行验证于是成为计算机应用领域需要解决的重要课题之一.其中,利用人类的生理特征或行为特征的生物特征识别技术成为了一种重要的身份认证技术,而自动指纹识别技术就是一种利用每个人都拥有的独一无二的指纹信息识别对象身份的生物特征识别技术.虽然指纹识别技术已相对成熟,指纹识别产品也已经被大家所普遍接受,但低质量、强噪声指纹图像处理仍然是自动指纹识别技术中具有挑战性的课题.在低质量指纹图像处理过程中,低质量指纹图像分割技术处在整个指纹识别技术体系的最前端,对后续的低质量指纹图像处理方法的性能有较大影响.对低质量指纹图像进行准确的分割处理可以降低背景或强噪声区域对后续处理方法的不良影响,提高指纹特征信息提取结果的可靠性和精度,从而提高自动指纹识别系统的识别精度[1-3].同时,准确的分割结果可以有效减少后续处理过程中的数据量,降低自动指纹识别系统的处理时间[1-3].一般而言,可以将指纹图像分割方法分为基于方向信息(或方向一致性)的指纹图像分割方法[2-4],基于灰度信息(或灰度统计均方差)的指纹图像分割方法[1,5-6]和融合方向、灰度特征等多类信息的多指标融合指纹图像分割方法[7-8].

在图像处理领域,指纹图像通常被看作是一类较为典型的纹理图像,具备较为规则、可靠的纹理特征.作为纹理图像而言,其重要表现为在局部区域中具有很强的方向性和纹理的规律性重现,指纹图像也不例外,在局部区域中的方向一致,规律性强.因此,Mehtre B.M.等人[2-4]提出了方向图指纹分割法,依据指纹图像的方向信息实现对指纹图像的分割处理.显然,这类方法有一个前提条件,即所求取的方向信息是可靠、准确的.否则,由于方向信息求取结果的错误,分割结果的有效性不可能得到保证.因此,对于低质量指纹图像而言,由于强噪声的干扰,方向信息求取结果的准确性必然下降,从而导致了分割算法的实际性能急剧下降,无法满足应用的实际需要.

另外,作为典型的纹理图像,有效指纹图像区域的灰度变化具有很强的规律性,在自动指纹识别技术中,通常认为指纹图像的灰度变化是符合正弦分布的.事实上,从微观上分析,指纹图像的局部区域可以被视为完全符合二维正弦分布规律,因此高质量的指纹图像区域的灰度方差较大.然而,在背景区域中,其各个像素的灰度变化较为平缓,不再是典型的纹理图像,而是平滑图像,因此背景区域的灰度方差较小,在数值上和指纹图像区域的灰度方差有较大的差距.正是依据这一特征,Lin H等人[1]首先提出了利用灰度方差实现对指纹图像进行分割处理;甘树坤等人[5-6]在此基础上做了进一步的研究,提出了利用灰度方差信息和灰度均衡结果的指纹图像分割方法.显然,当背景中有强噪声时,背景区域的灰度方差也将变大,甚至超出了正常指纹图像区域的灰度方差,从而直接导致了这类方法分割结果的不准确.因此,这类方法对低质量指纹图像的分割结果并不是非常准确,往往不能有效地将强噪声背景区域从前景指纹中分离出去.

因此,耿茵茵等人[7]在此基础上进行了更深入的研究,通过将灰度方差和方向图融合在一起,提出基于灰度方差和方向图的分级指纹图像分割方法;冯星奎等人[8]将多类分割指标融合在一起,提出了多指标合成的指纹图像分割方法.这些方法在一定程度上解决了单一指标指纹图像分割算法的缺点.但这些方法只是简单地采用多个分割指标,在空间上进行聚类或是采用阈值(很多时候是一些经验值)对特定的图像区域进行判别,并没有很好地利用邻域像素具有相似特性这一图像中普遍存在的特征,对低质量指纹图像的实际处理效果仍不是非常理想.

近年来,多智能体系统[9](Multi-Agent System,MAS)的理论日渐完备,在实践中也取得了显著成效,被广泛地应用于智能信息处理领域.在图像处理领域,Liu等人[10]利用反应式智能体设计了自动分割大脑CT图像的MAS系统,能够有效完成对大脑CT图像的自动分割,获得了比较理想的实验结果.刘俊义等人[11]提出利用分布式智能体检测灰度图像对称轴的MAS系统.陈小波等人[12]针对大脑图像中存在的背景、灰质、白质和脑髓液等4个区域的灰度均值、方差等特征的不同,实现了一种基于MAS的自适应图像分割方法,较好地完成了对大脑图像中这4个区域的分割处理.上述这些方法主要是针对大脑图像等医学图像的实际处理需要,这类图像的纹理性较弱,各个子域内的像素变化并不强烈.

本文在深入分析指纹图像的特征和多智能体系统的基础上,将多智能体系统引入到指纹图像分割处理过程中,实现了一种用于指纹图像分割处理的多智能体系统.在初始状态下,无差异的detector群体随机地、相对均匀地分布在指纹图像环境中,由于各自所处的环境不同,每个detector具有了各自不同的目标,而目标和感知的差异又导致了各个detector能力的不同.通过繁殖和移动,每个detector会不停地向周围指纹图像区域进行扩散,这就必然和其它detectors之间形成竞争.在竞争过程中,由于各个detector能力的不同,各个detector之间为扩张势力会进行合作和目标合并.在整个演化过程中,由monitor负责监控全局并协调各个detector之间为了共同的任务而协同工作,以实现对整个多智能体系统的有效管理.通过多智能体系统内部各个detector的不断扩散、合并,系统自身反复进行演化,并最终达到某种平衡状态,此时即有效地实现了对指纹图像的分割处理.

2 多智能体系统

多智能体系统本质上是一种开放式系统,它可以根据所处的环境因素自动地调整其内部结构[10-12].一般而言,多智能体系统(MAS)由检测智能体(detector)、管理智能体(monitor)和智能体之间的关系等三部分组成.

检测智能体(detector) 每个检测智能体的类型、目标和行为可以不同.它们存在于环境中,通过感知所在环境的局部信息完成自身的移动、繁殖、定居或消亡等决策过程.本质上,detector通过感知周边环境信息寻找与自身目标相同的图像区域并加以繁殖,从而实现对同类指纹图像区域的融合,将有效指纹图像区域从背景中分离出来,以完成对指纹图像的分割处理,是一种典型的反应式agent结构.

一般而言,detector主要有目标(goal)、感知(sense)和能力(ability)三种属性.目标是指detector所检测对象的特征信息,如指纹图像区域的灰度均值、方差、方向一致性等可以进行量化度量的特征信息,一般可定义第i个检测智能体的目标为goali=[Mi,Vi,Ci],其中Mi,Vi,Ci分别为detector所在图像区域的灰度均值、方差和方向一致性.感知是指在detector的感知半径内的邻域对象的属性,一般也用图像区域的灰度均值、方差等进行表示.能力反映了detector对当前环境的适应程度,随着其目标和局部感知环境的变化而变化,一般定义能力为:abilityi=exp(-|goali-sensei|),可见其符合正态分布。

管理智能体(monitor) 由于detector只能感觉所在局部区域的环境信息,具有很强的局部性,从而会导致多智能体系统的演化是不确定的,无法收敛到合适的解.因此,monitor用于对系统的整体状态进行全局的监控,根据高层知识对detector进行指导和约束,从更高层次监控detector的行为并给予协调,从而可以加速求解过程,约束求解方向,以使得MAS系统能够快速、有效地收敛到合适的解.另外,monitor还需要根据用户需求和一定准则(前后两次detector的目标和分布是否保持稳定)判定MAS系统是否达到稳定状态并输出最终的指纹图像分割结果.

智能体之间关系单个智能体的能力有限,必须和其它智能体共享信息和并协同工作,以完成更复杂的任务,因此,智能体之间形成了一定的依赖关系,这可以用MAS组织结构来表示,这种结构根据需要而产生和瓦解,是一种动态结构.

本文根据指纹图像分割的实际需要,设计了一种MAS结构,如图1所示.

3 基于MAS的自适应指纹图像分割算法

由图1可以看出,detector分布于指纹图像中,用于感知所在指纹图像区域的局部邻域特征信息,并与目标进行比较.当对象的属性和目标属性相一致时,detector将选择在相应的指纹图像区域进行定居,并在此基础上繁殖N个下一代detectors,然后继续沿一定方向进行搜索.Monitor负责对整个MAS系统的当前状态进行全局监控,协调并约束所有detector的行为,并对所有detector的目标进行目标的合并、修正和更新等任务.在整个系统中,detector所感知到的指纹图像区域的特征属性是每个detector进行移动、定居、繁殖和消亡的基础.本文在分块图像的基础上,综合考虑图像的灰度分布特征、方向一致性和梯度一致性等能够有效表示指纹局部特征的多个指标,将他们作为分块指纹图像的属性并作为detector所感知的对象属性.

图1 MAS结构

3.1 第(i,j)块指纹图像区域的灰度均值M(i,j)和灰度方差V(i,j)

对第(i,j)块指纹图像区域而言,对应的灰度均值和灰度方差分别定义为M(i,j)和V(i,j),具体计算过程如下:

其中,w为指纹图像的分块尺寸,一般取w等于8或16,(k,l)为图像块内偏移量,g(m,n)为指纹图像中像素(m,n)的灰度值.

3.2 第(i,j)块指纹图像区域的方向信息一致性属性Cor(i,j)

在指纹图像处理领域,方向信息一致性是指在局部指纹图像区域内方向信息的相似性度量,本文用点方向信息一致性进行表示.方向一致性属性可以有效表示图像局部区域的纹理一致性和噪声强度.对于背景区域或强噪声区域而言,其点方向一致性较差,而对于有效指纹区域,其点方向一致性则较好.其中第(i,j)块子图的方向信息一致性Cor(i,j)定义为

其中,Sum为第(i,j)块子图中所有像素点的数目,当分块尺寸为w时有Sum=w×w,Peak1和Peak2分别为第(i,j)块子图对应的点方向直方图的峰值和次峰值.本文中8方向点方向图计算方法采用聂桂军等人提出的连续分布方向图计算方法[13].

3.3 第(i,j)块指纹图像区域的梯度均值Gra(i,j)

梯度信息能够有效地表示指纹图像中局部区域的灰度变化量.对于有效指纹图像区域而言,由于指纹图像灰度变化的渐变性和规律性(可以看成符合正弦曲面),所在区域的梯度值较大.对于背景区域而言,由于缺乏规律性的变化,一般情况下灰度值近似一致,所在区域的梯度值较小.本文中第(i,j)块子图所对应的梯度均值定义为

其中,gra(m,n)表示像素点(m,n)的梯度变化,为了降低噪声等因素的干扰,采用了邻域统计均值来表示,如公式(5)所示:

这里,Gx(m,n),Gy(m,n)分别为像素点(m,n)在x,y方向上的偏导,表示了该点在x,y方向上的灰度变化量,一般可分别由x,y方向上的sobel算子求取.

通过上述分析可知,首先对指纹图像进行分块处理,在分块图像的基础上进行分割,其次分别求取各个指纹图像块的特征属性,作为智能体处理对象的属性,然后在对MAS系统进行初始化的基础上,通过各类智能体的演变对目标进行检测,直至整个系统趋向于稳定,最后输出最终的指纹图像分割结果.算法的基本实现过程如下所示:

(1)按照一定的分块尺寸对图像进行不重叠分块处理

按照指纹图像处理的实际需要对指纹图像进行不重叠分块,分块尺寸w一般可以选择为8或16,本文中取分块尺寸为8.

(2)分别求取各个指纹图像块的属性集{M(i,j),V(i,j),Cor(i,j),Gra(i,j)}

对任意一个指纹图像块(i,j),采用上述公式分别求取对应的属性值,构成该图像子块的属性集{M(i,j),V(i,j),Cor(i,j),Gra(i,j)},以此作为detector检测的对象属性.

(3)初始化MAS系统

按照指纹图像的实际大小,在指纹图像中随机分布一定数量的detector,任一位置不可以多于1个,detecor的初始目标设为其感知的局部环境,即goal＜-sense;同时,设置能力阈值T、移动步数阈值S和一次繁殖所生成的下一代detector数目N三个参数.

(4)detector进行反复演化,直到满足系统终止条件

在每一个循环周期内,分布在指纹图像中的各个detector将根据其自身能力和生命期进行主动演化.在演化过程中,主要有繁殖、死亡、定居和移动等4种基本动作.通过上述4种基本操作产生新一代的detectors,形成演化后的分布状态.在整个系统演化过程中,monitor将根据当前detector分布状态,按照对象属性、detector的活性等条件完成冲突的消解过程和目标的合并过程,并更新所有detector的目标作为当前分布下的detector目标,为后续的演化运算提供了有力的依据.在一个周期结束后,monitor会根据给定的结束条件检测系统是否已经处于稳定状态.如果满足所给定的结束条件,则执行下一步,否则,进入下一次循环周期,detector重新进行演化.

(5)输出分割结果

当monitor检测到系统已经满足结束条件时,MAS系统将根据detector的分布状态输出指纹图像分割结果,然后采用低通滤波器消除孤立块,从而完成最终的指纹图像分割过程.本文根据演化前和演化后detector的目标和分布状态的一致性作为系统的终止条件,当演化前和演化后detector的目标和分布状态不一致时,说明该系统仍需要进一步演化,以获得更优的指纹图像处理结果.否则,说明该系统已经处于稳定平衡状态,此时认为指纹图像分割过程,输出指纹图像分割结果.

5 实验分析及结论

为了分析算法的实际分割处理效果,文中选取了高质量指纹图像、对比度差的低质量指纹图像以及背景噪声很强的低质量指纹图像等3组典型指纹图像进行了自动分割处理,并和基于灰度方差的指纹图像分割算法以及基于点方向一致性的指纹图像分割算法进行了比较分析.具体实验结果如图2所示.

由图2可以看出,对于高质量图像(图2(a) Img1805号指纹)而言,3种算法的实际分割结果差距很小,都能够满足后续处理的需要;对于低对比度指纹图像(图2(e) Img1903号指纹)而言,方差法会存在严重的过分割现象,这是由于对比度低而导致的有效指纹区的方差其实也很小,简单地采用方差阈值不再能够适应图像分割的实现需要,方向图分割算法有效改善了这种过度分割现象,但仍然存在一定程度的过分割,而本文算法所得到的分割结果相比上述两种方法而言则有更大的改观,这是由于本方法是从局部对象的相似性角度进行考察,且指标是多样的,有效消解了过分割现象;对于含有较强背景噪声的指纹图像(如汗渍所形成的大面积噪声,图2(e) Img1903号指纹所示)而言,方差法由于不能有效地降低噪声对方差计算结果的影响,从而导致了对应子块的方差较大,算法不能有效去除背景区域,方向图法在此基础上有较好的改善,但仍然不够理想,而本文算法则能够对这类指纹图像进行更为有效的分割处理.

本文提出了一种基于MAS的自适应指纹图像分割方法,模仿了竞争和扩张过程,MAS演化的平衡即代表了指纹图像分割的完成,此时的系统状态即代表了最终的分割结果.对比实验结果说明,本文的算法对噪声具有较好的鲁棒性,能够对对比度差、背景噪声强等多类指纹图像进行更为准确、有效的分割处理.

[1]Lin H,Wan Y F,Jain A K.Fingerprint image enhancement:Algorithm and performance evaluation[J].IEEE PAM I,1998,20(8):777-789.

[2]Mehtre B M,MurtbyN N,Kapoor S.Segmentation of fingerprint images using the directional image[J].Pattern Recognition,1987,20(4):429-435.

[3]黄贤武,苏鹏程,柏培权.基于方向滤波分割的指纹自动识别系统算法[J].中国图像图形学报,2002,7(8):829-834.

[4]贾则,戴荣涛,张芬,等.基于连续分布方向图的指纹图像分割算法研究[J].微电子学与计算机,2007,24(12):141-143.

[5]甘树坤,吕雪飞,吕颖,等.指纹自动识别中图像分割方法研究[J].电子技术应用,2007,24(11):65-67.

[6]胡涛,林家骐.基于灰度均衡的指纹图像分割算法[J].计算机工程与应用,2007,43(24):205-207.

[7]耿茵茵,唐良瑞.指纹图像分级分割算法[J].北方工业大学学报,2000,12(3):21-26.

[8]冯星奎,颜祖泉,肖兴明,等.指纹图象合成分割法[J].计算机应用研究,2000,1(1):76-77.

[9]Wooldridge M,Jennings N R.Intelligent agents:theory and practice[J].The Knowledge Engineering Review,1995,10(2):115-152.

[10]Liu J,Tang Y Y.Adaptive image segmentation with distributed behavior-based agents[J].IEEE Transactions on PAM I,1999,21(6):544-551.

[11]刘俊义,王润生.利用分布式主动智能体检测灰度图像的对称轴[J].软件学报,2002,13(7):1238-1241.