基于图像插值和椭圆拟合的联指图分割算法*

刘 惠,张佳兵,张 彪

（大连理工大学 电子信息与电气工程学院,辽宁 大连 116024）

随着图像处理和模式识别技术的不断完善，指纹识别系统大量应用于人们的生产和生活中。目前，单指指纹识别技术已经相对较成熟，但是，指纹识别对比过程中的匹配指数原理，在单个指纹识别过程中会不可避免地出现一些误录率和错拒率，对生活和生产造成影响，甚至损失。在无需增加采集设备成本和识别算法复杂度的前提下，多指融合识别技术可提高单指指纹识别算法的性能[1]。此外在现场采集到的指纹也常以多指指纹的形式出现，因此，在单指指纹识别的基础上进行多指指纹识别,以提高身份验证的准确率，成为指纹识别的新兴研究方向。多指指纹识别首先将单个指纹从包含多指纹的联指图上分割出来，然后将每个指纹逐一识别，因此联指图分割的结果直接影响多指指纹识别的效果，是多指指纹识别的关键。

国外相关文献及专利报道了“指纹分割”论文[2]，该论文提出的算法对于噪声小的图像处理效果较好，但缺乏降噪等预处理过程，且无法分割存在指纹连接情况下的特殊联指图。“指纹分割的系统和方法”LO P Z等人的发明专利[3]中所提出的算法速度较快，实时性好。但在指纹边缘处处理效果不佳，且无法去除掌纹区域。国内处理联指图的方法有基于频域分析的联指图前后背景分离算法[4],该算法是建立在频域的基础上，降噪效果较好，但计算量较大。

本文提出了一种基于图像插值和椭圆拟合的联指图分割系统,该系统包括图像滤波、指纹中心及指纹偏转角度确定、非连指联指图旋转、连指旋转及插值分隔、逻辑指纹判断及指纹提取6个部分。实验证明该算法不但可以成功地分割低对比度联指图、噪声联指图、“光环”联指图、联指图旋转、部分残缺联指图，且可成功解决存在指纹连接情况下的特殊联指图分割。

1 算法的实现

1.1 图像滤波

由于联指图图像灰度不均匀且存在噪声，本算法设计了自适应滤波[5]对图像进行初步滤波。

(1)计算图像的阈值，并检测阈值是否符合要求，以决定是否有必要进行滤波操作。添加一个的下限L和一个U的上限u。当图像阈值大于U时，则认为图像质量比较高，能进行有效的后续处理。

(2)非线性滤波加强。将噪声进行严格过滤，而相对放宽图像失真的问题，采用了阈值乘以1.5的方式来加大阈值，并在后续步骤中，用原图进行了一定的补救措施。处理方式为：

其中,CGV表示当前处理点的灰度值；Threshold表示加强阈值。

(3)高斯滤波。由于图像中可能存在椒盐噪声，此时上述非线性滤波加强无法进行有效地滤波，所以添加一个图像平滑的高斯滤波，既不会对图像造成太大的失真，又可有效地去除椒盐噪声。

(4)源图补偿。经过上述步骤之后，图像有了一定的失真，于是采用将源图像叠加到处理图像上的办法进行修正补救。

接着进行阈值的再计算，并判断阈值是否符合要求，若不符合，则重复上述步骤，进行图像的再次滤波加强操作。若符合，则进入下一步操作。

1.2 指纹中心及指纹偏转角度确定

为确定各区域中心和各区域偏转角度，并以此判断是否有连指情况,设计了MS(Mean Shift)自适应算法初始半径的自动确定程序。

(1)对图像进行垂直投影，计算得到的垂直投影图是图像垂直线上的点数统计图。采用双向逼近法，计算出初始半径。

(2)利用计算出的初始半径，采用 MS算法，找出各指纹区域的中心点。

(3)当结束MS算法，有时会遇到连指情况，如图1所示。

图1 连指图

图中白色小圈表示指纹连接处，这时如直接调用MS算法将对图像处理的结果产生较大误差。于是采用独特的方法对MS算法得到的结果点进行分析判断：

(1)检查两个结果点是否足够靠近，即：

其中,Factor为人为指定参数,设定为 1.2；Radius为进行MS算法时的窗口半径。

(2)当两个结果点相距较近时，再判断两点连线与垂直轴线的夹角是否大于阈值angle。

同时满足以上两个条件时，即认为指纹出现了连接的情况。这时，将指纹连接的两个点进行标定，并跳出当前模块。计算新的MS半径,将椭圆长半轴的最大值Max_L与进行MS过程的窗口半径进行比较判别,如满足式(4)，则把用于MS算法窗口半径Radius用Max_L进行更新,继续半径的搜索，直到找到合适的半径。否则进入下一模块。

1.3 非连指联指图旋转

首先进行椭圆偏转角度的计算,将计算得到的角度纯化，计算得到所有手指的平均角度α，判断该角度是否大于设定的阈值。当计算角度大于阈值时,则根据计算得到的角度α进行MSR的旋转。

1.4 连指旋转及插值分隔

首先进行椭圆偏转角度的计算,并纯化计算得到的角度，计算得到所有手指的平均角度α。假定在角度的初始计算过程中获取的候选角度有 α0,α1,α2,α3,…,αn。

(1)计算其均值

(2)候选角度的纯化

其中，i∈{0,1,2,3,…，n},Threshold0为设定的阈值，然后进行候选角度个数n的更新。

(3)循环过程(2)直到角度纯化完毕。

(4)计算出被纯化的角度的均值，作为手指的偏转角度。对图像进行“旋转插值”操作，如图2所示。

设点(X0，Y0)为初始点，点(X1，Y1)为旋转后的点，初始点与X轴正向形成的角度为α0，矩阵运算的表达式为：

然而由于在实际图像处理中，Y轴反向，所以上述矩阵表达式将变化为：

接着进行插值操作：

(1)从以上的步骤可以找到MS结果中满足连接准则的标记点，取两点的平均值X坐标，作为初始模糊收索点，然后利用垂直半投影算法，计算出准确的指纹连接点。假设从上述步骤中得到了如下的MS结果点：

根据MSR点坐标的Y坐标进行从小到大的排序，得到新的 MSR0,MSR1,MSR2,MSR3,…,MSRn。经过排序后的MSR数组中第一个坐标点必然是指纹的中心点，可根据联指图的逻辑关系找出所有指纹，当找到了Y坐标最小的指纹中心点时便停止搜索，以最后找到的MSR的Y坐标加上指纹半径为垂直投影下限，进行图像的切割，将图像分为上下两部分，并对位于上方的图像进行垂直投影,可有效地去除图像中可能存在的掌纹干扰。

根据得到的垂直半投影图像统计图以及图像指纹连接的初始模糊搜索点，指纹的真实连接点必然存在于此点的附近。接着采用计算领域均值的方法确定连接处。

(2)在指纹连接处，插入灰度为“0”的黑色像素带，这样两个相连的指纹就被人为地分隔了,这时再进行MS自适应算法使两个指纹相互吸引且不受旁边指纹的影响。于是直接调用MS功能模块，对图像进行指纹半径和所有指纹及类指纹中心的确定操作。由于进行图像旋转插值操作后，指纹图像已经被旋正了，故可直接调用逻辑指纹的判断。

1.5 逻辑指纹判断

在经过旋转之后，对应的类指纹中心为图像中标“十”字的点。由于一个手指指纹的中心明显高于其他指节的中心，所以如果对一个手指的图像进行操作，即做一个三角形包含这个手指的每一个中心点，就可以只取出最高的个中心点，而去除图形中的其他中心点，如此循环操作，将可以去除包含掌纹点在内的所有干扰点。

食指和小拇指的中心点高度相差比较很明显，故通过比较食指和小拇指的中心点来判断左右手。

1.6 指纹提取

对去除干扰点之后的4个指纹中心F1、F2、F3、F4 以 Radius为初始半径进行椭圆拟合操作。找出每个中心点对应的椭圆长轴w、短轴L以及指纹的偏转角度α。椭圆规则化操作过程为。

其中，w为椭圆的宽，L为椭圆的长

(1)计算其均值

(2)候选比率的纯化其中，i∈{0,1,2,3,…，n},Threshold1为设定的阈值，然后进行候选角度个数n的更新。

(3)循环过程(2)直到角度纯化完毕。

(4)计算出被纯化比率的均值，记为avrate。

(5)对于剔除的点，更新短半轴 W=avrate×L。

对每个椭圆的W和L在一定范围内搜索,当某个像素的周围一定范围内平均灰度值大于阈值时,则停止移动，记录此点为 a1、a2、b1、b2。 计算矩形的 4 个顶点 c1、c2、c3、c4作出矩形，即为指纹区域。

2 实验结果与分析

2.1 实验环境

本文提出的算法实现环境为Windows操作系统，Visual C++6.0环境。

2.2 与现有算法比较

根据上面提出的方法,对从不同途径获取的具有不同图像质量的联指图可能出现的主要指纹图像进行了大量计算机仿真实验,并就“连指”联指图与参考文献的指纹分割算法做了比较，如图3所示。从图中可以看出，本文提供的算法可以成功地分割低对比度联指图、噪声联指图、“光环”联指图及部分残缺联指图分割，并且能分割现有算法不能处理的存在指纹连接情况下的联指图。

2.3 时间复杂度

本文的算法处理速度为5 s/幅，比较已有算法，本文算法在速度上具有实用价值。

本文提出一种基于图像插值和椭圆拟合的联指图分割算法。该算法充分利用了指纹图像中指纹区域和非指纹区域的灰度差异的特点，对图像进行滤波、插值分隔及椭圆拟合等操作，实现了多指指纹的自动分割。经过实验表明，该算法建立在图像时域基础上，计算量小，成功地完成低对比度联指图、噪声联指图、“光环”联指图、联指图旋转及部分残缺联指图分割，并且能成功地分割存在指纹连接情况下的联指图。

[1]宋占伟，王雪思.多指指纹自动分割算法[J].吉林大学学 报(信 息 科 学),2009,27(5)：500-505.

[2]HODL R,RAM S,BISCHOF H,et al.Slap fingerprint segmentation[C].In Computer Vision Winter Workshop,2009.

[3]Method and system for slapprint segmentation[P].US.Int.CI.G06K 9/00.2008/0298648.2008-11-04.

[4]李焱淼，张永良，黄亚平，等.基于频域分析的联指图前后背景分离算法[J].上海交通大学学报，2010，44(8)：1089-1093.

[5]GONZALEZ R C,WOODS R E,EDDINS S L.数字图像处理(第 2版)[M].阮秋琦,等译.北京：电子工业出版社，2005.