基于Harris角点检测和聚类算法的掌纹图像ROI提取方法

陈典典, 程培培, 马军山

(上海理工大学 光电信息与计算机工程学院, 上海 200093)

引 言

随着社会信息化的深入发展,身份识别的重要性飞速上升。掌纹识别是一种有着广泛应用前景的生物识别方法,是对现有生物识别技术的有益补充[1]。图像预处理是掌纹识别过程的关键一环,算法提取出的掌纹感兴趣的区域(region of interest,ROI)的质量好坏直接影响到最终的识别效果[2]。因此寻找一种有效的掌纹ROI提取方法对于掌纹识别技术的研究十分重要。

目前已有的掌纹ROI提取方法主要有基于拟合椭圆的方法[3],基于最大内切圆的方法[4],基于曲率及小波变换的方法[5-6],基于形态学的方法[7]等,提取的掌纹ROI形状主要有正方形、圆形与椭圆形等。其中,圆形和椭圆形的ROI具有较好的鲁棒性,能够适应不同大小的手掌。但与正方形ROI相比,其形状特征不利于后续的特征提取与匹配工作,同时搜索最大内切圆或椭圆会耗费大量的时间,不利于掌纹识别的实际应用。因此正方形ROI的应用与研究更加广泛。

在正方形掌纹ROI的提取过程中,关键点的检测与定位至关重要。Harris算子是一种基于信号的点特征提取算子,具有计算简单、提取的角点特征均匀合理、算子稳定的特点[8]。因此部分研究者试图将Harris角点检测方法引入到掌纹图像ROI提取中来。目前已有的基于Harris角点检测算法进行掌纹ROI提取的方法[9]在应用中仍有很大的缺陷,具体表现在需要进行人为鼠标操作、结果误差较大等。本文根据掌纹图像的特点提出了一种基于Harris角点检测和聚类算法的掌纹图像ROI提取方法,并在香港理工大学与中科院自动化研究所的掌纹数据库中进行测试,结果表明,该方法易于实现,提取的结果准确性与稳定性较好,并对各个掌纹数据库具有普适性。

1 Harris角点检测算法和聚类算法

1.1 Harris角点检测算法

Harris角点检测原理是利用移动的窗口在图像中计算灰度变化值[10],其关键流程包括转化为灰度图像、计算差分图像、高斯平滑、计算局部极值和确认角点。

对于一幅二维图像I以及一个各向同性窗w,在某一像素点(x,y)上,将图像窗口平移[u,v]则产生灰度变化的平方和E(u,v)为

(1)

使用二维函数的一阶泰勒公式简化式(1)可以得到

(2)

式中:Ix是图像I在x方向上的梯度;Iy是图像I在y方向上的梯度。令矩阵

(3)

定义角点相应函数R为

R(M)=det(M)-K·trace2(M)

(4)

式中:det(M)为矩阵的行列式;trace(M)为矩阵的迹;K为可调参数,有关文献建议范围为0.04～0.15。Harris角点检测算法就是对角点响应函数R进行阈值处理,当R大于给定的阈值,即判定为角点。

本文使用Harris角点检测器对二值化掌纹图像进行角点提取,当角点检测器对图像进行操作时,图像明暗边缘的细小锯齿或尖峰会对角点检测造成误提取,对后续的关键点定位步骤造成不利的影响。增大窗口w的尺寸大小可以减小Harris矩阵方差,从而减少误检测的角点,但是会使角点形成簇。使用聚类算法寻找角点簇的中心点,可以得到关键点的坐标。

1.2 聚类算法

聚类分析就是用数学方法研究和处理给定对象的分类,其过程是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇,使得同一个类簇内的数据对象的相似性尽可能大,同时不在同一个簇中的数据对象的差异性也尽可能得大[11]。如图1所示,聚类算法将坐标系中所有的点分为了3类,计算出3个点作为聚类中心并作为每一类的代表。

目前有多种聚类方法[12],对于不同的应用情况,应当根据数据的类型以及聚类的目的进行选择。本文主要使用了K-means聚类算法,是一种十分经典的高效率聚类算法。K-means算法以k为参数,把n个对象分成k个簇,使簇内具有较高的相似度,而簇间的相似度较低。K-means算法的处理过程如下:首先,随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心;然后,对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;最后,重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。

图1 聚类算法的应用Fig.1 The application of clustering algorithm

2 掌纹ROI提取步骤

2.1 图像降噪

如图2所示,原始的图像的噪声会对后续的处理结果造成不利的影响。本文使用中值滤波器进行图像降噪,设h(i,j)代表滤波之后的图像,g(i,j)为滤波之前的图像,则滤波窗口为A的图像中值滤波可以表示为

h(i,j)=medA{g(i,j)}=med{g(i+r,j+s)}, (r,s)∈A

(5)

图3为滤波后的图像。

图2 掌纹原图像Fig.2 Palmprint source image

图3 中值滤波后的掌纹图像Fig.3 The palmprint image after median filtering

2.2 图像的二值化与边缘平滑

图像二值化是一个重要步骤,本文算法采用固定阈值T=50对图像进行二值化,此过程表示为

(6)

对二值图像进行闭运算可以平滑图像的边缘,减少角点的误提取,图4和图5分别表示了图像经过二值化与边缘平滑的结果。

2.3 角点检测

对经过前文处理获得的二值图片进行Harris角点检测。通过第1部分的分析可知,当使用较大的窗进行角点检测时能够在检测结果中极大地减少无关的角点。本文算法中取窗的大小为10,图6显示了检测结果。

2.4 关键点定位与坐标系建立

收集特定位置的角点簇并利用聚类算法分析,得到角点簇的中心。在得到的中心点中,取食指与中指之间角点簇的中心点O1(x1,y1)以及无名指与小拇指角点簇中心点O2(x2,y2)作为基准点,过这两个点做直线为新建立坐标系的y轴,以线段O1O2的中点为原点,做线段的中垂线为x轴建立坐标系。如图7所示。

图4 二值化掌纹图像Fig.4 Binary palmprint image

图5 闭运算处理后的图像Fig.5 The image after closed operation

图6 角点检测结果Fig.6 Results of corner test

图7 建立坐标系Fig.7 Establishment of coordinate system

2.5 根据新坐标系定位ROI

最后根据步骤4确定的坐标进行掌纹ROI的定位提取,具体做法是:先将掌纹图像以原点O为中心旋转θ角度,θ可表示为

(7)

当θ为正值时,将图像逆时针旋转,反之顺时针旋转。之后确定合适的距离D,可以取得掌纹ROI图像,图8反映了这一过程。图9为本算法取得的ROI图像。

图8 旋转之后的图片Fig.8 The image after rotate

图9 截取到的掌纹ROIFig.9 Palmprint ROI

3 实验分析

在本文ROI提取方法中,对检测出来的角点进行筛选是十分重要的一环。对于不同的掌纹数据库,因其图像采集方式、摆放标准的不同,则角点收集范围应当按照实际情况进行修改。本文算法分别针对香港理工大学掌纹数据库以及中科院自动化研究所掌纹数据库的不同特点制定了相应的角点收集与关键点筛选定位规则。 利用Python编程验证本文方法,进行提取掌纹ROI的实验。

3.1 处理香港理工大学掌纹数据库

3.1.1图像数据

香港理工大学掌纹数据库[13]中的图像均为256级的灰度图像,是利用特殊的带有定位装置的掌纹图像收集器进行收集的,故该掌纹数据库的自由度较低,进行预处理较为容易。图2显示了该数据库中的一张掌纹图像,图像的大小为284×384,格式为bmp格式。

图10 关键点定位过程Fig.10 The positioning process of key points

3.1.2关键点定位

对于掌纹数据库,根据图6显示的角点分布情况,可以制定如下的角点收集与筛选规则,图10反映了这一过程:

1) 首先通过逐列搜索的方式得到点K1,K2,K3,K4的大致坐标;

2) 根据K1,K4两点确定矩形ABCD为角点收集的范围,得到角点坐标集合P;

3) 对集合P进行簇为4的K-means均值聚类,得到各个簇的中心点O1、O2、P1、P2;

4)O1、O2、P1、P24个点中纵坐标最小的点O1与最大的点O2即为我们要寻找的关键点。

3.1.3掌纹图像处理结果

抽取300幅图像组成测试图像数据库,其中10幅图像来自同一只手,另外290幅图像为随机抽取。设置提取的ROI大小为128×128,图11与图12显示了本文算法的提取效果。经统计,本文算法成功处理299张,失败1张,成功率为99.7%。

图11 对同一只手掌图像的ROI提取结果Fig.11 The results of ROI extraction from same palmprint

图12 对不同手掌图像的ROI提取结果Fig.12 The results of ROI extraction from different palmprint

3.2 处理中科院自动化研究所掌纹数据库

3.2.1图像数据

中科院自动化研究所掌纹数据库(CASIA)中的图像亦均为256级的灰度图像,该库中的样本均是使用CCD简单采集得到,没有用于固定的圆柱。故该掌纹数据库的自由度较高,关键点难以定位,预处理难度较高,一般使用最大内切圆或拟合椭圆的方法提取ROI。图 13显示了CASIA中的几张典型手掌图像,图像的大小为480×640,格式为jpg格式。

3.2.2关键点定位

对于CASIA掌纹数据库,图14显示了角点分布情况,可以看出角点主要分布在指尖和两指之间。由于不同图像的角点簇的数量和位置不尽相同,因此确定角点收集与关键点筛选规则如下:

1) 收集图像中的所有检测到的角点坐标得到集合P;

2) 对集合P进行簇为n(n=3,4,5…)的K-means聚类,得到聚类中心;

3) 对所有得到的聚类中心点取整,判断是否全部都位于集合P中,如果不是,则取n=n+1,并重复步骤2,如果是,则进行下一步;

4) 得到角点簇的中心点A、B、C、D、E后,如图14所示,我们需要得到A、B、C三个指间点,可以利用A、B、C三点组成的三角形面积最小这一特性进行判断;

5) 得到A、B、C三点的坐标后,纵坐标最小的点A与最大的点C即为我们要寻找的关键点。

图13 CASIA掌纹数据库图像Fig.13 Images from CASIA palmprint database

图14 角点检测结果Fig.14 Results of corner test

3.2.3掌纹图像处理结果

抽取200幅图像组成测试图像数据库,其中5幅图像来自同一只手,另外195幅图像为随机抽取。设定ROI提取大小为200×200,图15与图16显示了本文算法的提取效果。经统计,本文算法成功处理198张,失败2张,成功率为99%。

图15 对同一只手掌的ROI提取结果Fig.15 The results of ROI extraction from the same palmprint

图16 对不同手掌的ROI提取结果Fig.16 The results of ROI extraction from different palmprints

3.3 错误提取分析

图17为错误提取的掌纹ROI图像。通过分析,造成错误提取的直接原因是由于部分掌纹图像由于存在较强的噪声干扰,本文的方法未能有效地去除,使Harris角点检测器提取到了较多且情况复杂的角点,从而未能正确提取到关键点,导致误提取的出现。进一步减少图像中噪声对提取结果的干扰,是本文方法的改进方向。

图17 错误提取的掌纹ROIFig.17 Wrong extraction of palmprint ROI

4 结 语

在掌纹识别技术的研究中,研究者往往需要花费大量的时间去研究提取掌纹图像的ROI。通过实验分析,本文提出的方法可以适应多种不同的掌纹数据库,提取的效果稳定准确。目前,有大量的库函数可以帮助研究者实现本文的各项算法,因此本文方法实现简单。综上所述,本文所提出的基于Harris角点检测及聚类算法的掌纹ROI提取方法对掌纹识别技术的研究发展很有意义。但同时本文算法无法对复杂背景下的掌纹图像进行有效的ROI提取,运行效率仍有大量的优化空间,需进一步优化完善。