有限元指纹图像配准*

姚丽莎，程家兴

安徽新华学院 信息系统软件研究所，合肥 230088

有限元指纹图像配准*

姚丽莎+，程家兴

安徽新华学院 信息系统软件研究所，合肥 230088

针对指纹图像中形变复杂多样的特点，对指纹图像配准算法进行研究，发现目前指纹配准算法存在复杂度高，精度低，速度慢，易受指纹形变等影响的缺陷，引入有限元分析理论，提出了有限元指纹图像配准算法。该算法将指纹图像配准中的复杂形变转换为有限个离散形变单元组成的弹性形变，以分叉点、转折点、指纹图像上两点的连线所穿越的脊线数量等特征作为特征指标，求出采样指纹与标准指纹的模糊贴近度，并创造性地以此为相似性测度，构造总体刚度方程，进而迭代求解最佳位移，完成指纹图像配准。实验表明，该算法位移量的误差最小，用时为8.894 s，其有效降低了算法复杂度，提高了精度，同时也有效避免了指纹复杂多样的形变等因素对指纹配准算法精度的影响。

指纹配准；有限元；模糊贴近度；指纹特征点

1 引言

在生物特征识别领域中，指纹识别技术[1]发展迅速。信息技术的飞速发展在为自动指纹识别的应用开辟广阔市场的同时，也对指纹识别技术提出了新的挑战。指纹匹配[2]的准确性与效率对指纹识别的优劣有直接影响，它是指纹识别的核心内容。

然而，在实际指纹采样的工作过程中存在着复杂的形变问题，如采样手指的角度偏差，指纹粗糙度发生较大变化，采样手指压力不同等都会造成指纹图像的形变。基于细节点模式的指纹匹配算法在匹配前需找到采样指纹与库指纹的形变变换的最优解，即指纹配准。为提高指纹识别的准确率，提高指纹匹配的准确性，就要提高指纹配准的准确性。国内外许多研究人员在指纹配准上提出了许多研究成果，如文献[3]的基于新的细节点柱形编码的指纹匹配算法，文献[4]的基于细节点全局置信度的指纹匹配算法等。还有一些研究在图像配准中应用力学上的有限元模型，Schnabel等人将有限元法应用于求解基于B样条精配准前的初始变换[5]；Xuan等人利用样条曲线为有限元模型控制局部形变[6]。但这些算法对配准精度有所限制，大多只能用于粗配准，不能解决指纹图像的复杂形变问题。

目前指纹配准算法存在复杂度高，精度低，速度慢，易受指纹形变等影响的缺陷，为解决指纹图像复杂形变问题，本文引入有限元分析理论，提出了一种新的基于有限元分析理论的指纹图像配准算法。首先将配准图像进行有限次离散化的划分，并将指纹图像配准中的复杂形变转换为有限个离散形变单元组成的弹性形变，以提高指纹配准算法的精度和速度。为解决现有基本有限元算法对刚体位移不敏感，精度具有局限性的缺陷，求解配准过程中有限元的能量函数时，创造性地以分叉点、转折点、指纹图像上两点的连线所穿越的脊线数量等特征作为特征指标，求出采样指纹与标准指纹的模糊贴近度。采用采样指纹与标准指纹的模糊贴近度测度为驱动，构造总体刚度方程，提高图像配准的精度。该算法可有效削弱因指纹平移、旋转、手指压力不均等因素造成的对指纹配准准确度的影响。

2 有限元配准

有限元理论是“先化整为零，再集零为整”。最终解看成是由有限个有限单元的近似解组成，然后根据有限个单元近似解推导求解总的最终解。这样复杂问题就转换为若干个简单问题，能适应各种复杂问题的求解。

指纹图像具有复杂形变问题[7]，配准过程可以归结为某个量的极值问题[8]。指纹图像的有限元配准就是将复杂的形变体转化为较为简单的离散的有限个形变单元，以此为基本单位，依据图像的能量函数，对整个图像的形变进行计算。

有限元法求解复杂问题的基本思路可概括为3个步骤，即对弹性体进行结构离散化、单元分析和整体分析，如图1所示。

对两幅待配准的指纹图像A、B在配准中进行单元划分，选取像素点的位移u为待定位移函数，在所有可能满足位移边界条件的位移中，搜索可以满足平衡条件的位移，使总势能E成为极小值，此位移即为平衡条件下近似解[9]。以位移u为例，该能量泛函可以用泰勒展开式表达：

Fig.1 Analytical procedure using finite element method图1 有限元法分析步骤

其中，ε为应变；σ为应力；∇为用于能量计算的梯度算子；2(I1-I2)∇I1u表示弹性形变；(I1-I2)2表示刚体的位移。高阶导数不一定满足一致连续性，因此通常只考虑弹性形变项而省略位移项，这样便将图像配准问题转化为求解位移解u的有限元问题。

3 模糊贴近度

指纹纹线的端点（末稍点）和分叉点被视为指纹的主要特征点[10-11]，如图2所示。指纹图像特征点的绝对位置可能会随着指纹图像的平移、旋转或局部形变发生很大变化，然而两个特征点的连线所穿越的脊线数目及特征点构成的多边形的边和角则不会发生较大改变，这是衡量指纹图像匹配程度的重要特征指标[12-13]。

Fig.2 Endpoint and cross point of fingerprint image图2 指纹图像的端点和叉点图

指纹中心点也是指纹图像的主要特征点，指纹线在此点处汇聚，形成收敛，如图3所示。以指纹中心点为参考点，可确定各特征点的位置，具体方法是：

Fig.3 Information map of fingerprint feature points图3 指纹特征点信息图

（1）若最内层隆起线是一条直线，则确定隆起线的上端点为中心点；

（2）若最内层隆起线的上凸部分出现分叉，则确定分叉为中心点；

（3）若隆起线存在多条，则确定最左边的隆起线的上端点为中心点。

在确定指纹中心点后，以与中心点距离大于D (0＜D≤10)且最近的4个点（M,N,P,Q）为其特征点，连接这4个点构成四边形MNPQ，如图4所示。

Fig.4 Apolygon consisting of fingerprint feature points图4 指纹特征点多边形

指纹特征点组成的四边形MNPQ中4个点间的距离可分别由式（2）～式（6）求得：

四边形MNPQ中的两个夹角a与b的值由式（7）、式（8）求得：

衡量指纹匹配程度的重要指标为两点连线所穿越的脊线数量。因为指纹图像上两点连线所穿越的脊线数量不会随着指纹图像发生平移、旋转、缩放等形变而发生变化。依据参考文献[14]所给出的方法计算MN和NP连线所穿越的脊线数量Imn和Inp。

设论域U={X1,X2,…,Xn}[15]有n个模糊子集 ω1, ω2,…,ωn，构成了标准指纹库。B为采样指纹，σ(ωi,B)表示B与ωi(i=1,2,…,n)的模糊贴近度。若σ(ωm,B)= max{σ(ω1,B),σ(ω2,B),…,σ(ωn,B)}，则B最贴近 ωm，B应归于ωm。用模糊贴近度σ(ω,B)作为指纹图像配准的测度函数，其应满足如下条件：

（1）σ(ω,ω)=1；

（2）σ(ω,B)=σ(B,ω)；

（3）σ(∅,U)=0,其中∅为空集；

（4）由ω⊂B⊂C可得σ(ω,C)≤σ(ω,B)∧σ(B,C)，其中C为模糊集[16]。

由此推导出模糊贴近度公式为：

本文利用特征点构成的多边形的边、角及两个点的连线所穿越的脊线数目为特征指标求两幅图像的模糊贴近度，以此为测度函数，进而不断迭代，从而求解最佳位移解。

4 有限元指纹图像配准算法

4.1 总体刚度方程构造

式（1）通过泰勒公式展开后，由于高阶导数不一定满足一致连续，通常省略位移项，而只考虑弹性形变项，但是省略刚体位移项，常会带来在配准过程中，对较大位移和旋转等刚性变换不够敏感的问题，进而影响指纹图像配准的准确性。为此本文将模糊贴近度用于有限元理论中对指纹图像进行配准。

总体刚度方程的构造是整个配准过程的关键。弹性形变后，内部各点发生位移。在有限元分析理论中，将整体离散化，用一个相对简单的函数来描述单元内每个点的位移，称为位移函数。因为多项式便于计算而且能逼近任何复杂函数，所以一般用系数多项式来表示二维平面问题的位移函数。如图5所示，以三角单元位移Δ为例，其3个节点编码依逆时针方向进行，依次为i、j、k。单元的每个节点在平面问题中具有两个自由度。

Fig.5 Three nodes of triangular element图5 三角单元3节点

经过推导，位移函数表达式为：

其中，Ni表示插值函数，反映单元的位移变化形态，故称形函数。

下标i、j、k轮换，表示三角形单元的3个节点，其中系数ai、bi、ci的取值用克莱姆法则求得：

S表示三角形的面积，其计算公式为：

Δ=Nue为位移函数矩阵，其中ue是单元节点位移列阵，如式（14）所示：

单元节点位移与单元体内应变及应力的关系可以根据广义胡克定律、弹性体几何方程式ε=LΔ（L为变换矩阵）、式（10）得到：

式（15）中，B是几何矩阵，其大小为B=LN；ε表示应变矩阵；ζ表示应力矩阵；D表示弹性矩阵。有如下关系：

式（16）中，E为杨氏模量（Young’s modulus），其大小表示固体材料抗形变的能量；v为泊松比；ζx、ζy、τxy为应力矩阵ζ的应力分量；εx、εy、γxy为应变矩阵ε的应变分量。

将上述单元体各分量组合：

对于二维有限元，等效能量梯度与每个等效节点力 f(fix,fiy)成正比，故有：

其中，U是总体位移阵列；K是总体刚度矩阵；R是全部外力的等效节点力阵列；α是正系数；∇m表示相似性测度的梯度。本文将模糊贴近度作为测度，即这里m为模糊贴近度，因此有：

其中，σ(A,B)为标准图像A与采样图像B单元体模糊贴近度。这里以单元体内局部中心点来确定特征点，以特征点构成的多边形的边、角及两个点的连线所穿越的脊线数目为特征指标求标准图像A与采样图像B的单元体模糊贴近度。

该算法以有限元模拟形变模型，既考虑了图像的物理形变，又融入了图像的模糊贴近度为度量。

各个单元体势能的总和为结构体总的势能，在离散化的情况下有：

4.2 算法步骤

本文利用有限元分析理论将指纹配准问题的复杂形变转换为有限个离散形变单元组成的弹性形变问题，使用模糊贴近度为相似性测度，构造总体刚度方程，进而不断迭代求解最佳位移。

在确立有限元材质并设置属性参数的基础上，首先，对采样指纹图像进行插值，依据当前测度函数求解位移的初始值；然后，以模糊贴近度为测度不断迭代求解新的位移解，当两次求得的位移解的差值小于某一特定极小值时迭代结束，此时的位移解即为最终值。图6所示为本文配准算法流程图。

5 实验结果与分析

实验分别采用文献[3]基于新的细节点柱形编码的指纹匹配算法、文献[4]基于细节点全局置信度的指纹匹配算法和本文算法进行比较。

Fig.6 Flow chart of registration algorithm in this paper图6 本文配准算法流程图

实验1选取标准指纹图像如图7（a）和采样指纹图像如图7（b）进行指纹图像配准，3种算法的配准结果分别如图7（c）、（d）、（e）所示。

在实验过程中记录不同迭代次数下位移量x、y以及旋转角度θ的变化情况，如图8（a）、（b）、（c）所示。这里位移量x、y以及旋转角度θ的标准值为100、100、58。实验用标准指纹图像与配准后的指纹图像的均方根R来作为评价参数，比较3种算法在不同迭代次数下的变化情况，如图8（d）所示。

式中，n表示图像大小；Tr(x)表示配准结果；Tq(x)表示标准图像。R越小表示两幅图像的差异越小。

实验1表明本文算法与文献[3]、[4]算法的比较结果：从图8（a）、（b）、（c）可以看出，在不同迭代次数下，本文算法对形变更为敏感，均更接近于实际位移量，配准效果更优；从图8（d）可以看出，误配率明显降低，在精度上有显著提升。

实验2选取标准指纹图像如图9（a）和采样质量较差存在复杂形变的指纹图像如图9（b）进行指纹图像配准，3种配准算法的配准结果分别如图9（c）、（d）、（e）所示。

在实验过程中记录不同迭代次数下位移量x、y以及旋转角度θ的变化情况，如图10（a）、（b）、（c）所示。这里位移量x、y以及旋转角度θ的标准值为10、10、14。3种算法的均方根在不同迭代次数下的变化情况如图10（d）所示。

实验2采用了质量较差存在复杂形变的采样图像，结果表明本文算法与文献[3]、[4]算法相比，亦取得良好的实验结果，有效避免了指纹复杂多样的形变等因素对指纹配准算法精度的影响。

实验3为了进一步验证算法的有效性，实验选取10对不同的指纹图像分别用3种算法进行图像配准。以Δxˉ、Δyˉ、Δθˉ、Tˉ即水平位移量、垂直位移量、旋转偏移量误差的平均值及算法平均执行时间为依据来比较以上3种配准算法，结果如表1所示。

Table 1 Parameter results of different registration algorithms表1 不同配准算法的参数结果

Fig.7 Registration results of experiment 1图7 实验1配准结果图

Fig.8 Parametric variation of experiment 1图8 实验1参数变化情况图

Fig.9 Registration results of experiment 2图9 实验2配准结果图

本文算法将指纹图像配准中的复杂形变转换为有限个离散形变单元组成的弹性形变，提高指纹配准算法的精度和速度。为解决现有基本有限元算法对刚体位移不敏感，精度具有局限性的缺陷，以分叉点、转折点、指纹图像上两点的连线所穿越的脊线数量等特征作为特征指标，求解配准过程中有限元的能量函数，并采用采样指纹与标准指纹的模糊贴近度测度为驱动，构造总体刚度方程，提高图像配准的精度。本文算法可有效削弱因指纹平移、旋转、手指压力不均等因素造成对指纹配准准确度的影响。从表1可以看出，从水平位移量、垂直位移量、旋转偏移量误差的平均值上可见本文算法优于其他两种算法。从算法平均执行时间可见，本文算法的效率优于其他两种算法。

Fig.10 Parametric variation of experiment 2图10 实验2参数变化情况图

6 结束语

本文采用有限元和模糊贴近度对指纹图像进行配准。有限元模型能够逼近指纹图像总的精确形变，在有限单元内创造性地采用模糊贴近度为能量函数，对刚体位移变化更敏感。实验表明，本文算法水平位移量、垂直位移量、旋转偏移量误差的平均值分别为3.084 721 mm、3.897 214 mm、2.651 432°，较其他两种算法误差最小；算法平均执行时间为8.894 s，用时最少。本文算法提高了精度，降低了复杂度，并且实验2表明本文算法有效避免了指纹图像复杂形变问题对配准精度的影响。

[1]Zhang Bo.Research on incomplete fingerprint recognition based on data mining and information[D].Beijing:Beijing University of Posts and Telecommunications,2012.

[2]Li Ke.The research of fingerprint recognition system based on sparse matrix[D].Wuhan:Wuhan University of Science and Technology,2012.

[3]Cappelli R,Ferrara M,Maltoni D.Minutia cylinder-code:a new representation and matching techinque for fingerprint recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(12):2128-2141.

[4]Fu Xiang,Feng Jufu.An fingerprint matching algorithm based on minutia global confidence[J].Pattern Recognition andArtificial Intelligence,2014,27(9):835-840.

[5]Schnabel J A,Tanner C,Castellano-Smiih A D,et al.Validation of non-rigid image registration using finite elementmethods application to breast MR images[J].IEEE Transaction on Medical Imaging,2003,22(2):238-247.

[6]Xuan Jianhua,Wang Yue,Freedman M T,et al.Nonrigid medical image registration by finite element deformable sheet-curve models[J].International Journal of Biomedical Imaging,2006,13(4):1-9.

[7]Zhang Jie.Researches on the key technologies in incomplete fingerprint recognition[D].Beijing:Beijing University of Posts and Telecommunications,2013.

[8]Zeng Chao,Li Na,Wang Wei,et al.Registration of medical images using group search optimizer combined with Powell’s method[J].Journal of Yunnan University:Natural Sciences Edition,2013,35(5):603-609.

[9]Krol A,Unlu M Z,Magri A,et al.Iterative finite element deformable model for non-rigid coregistration of multimodal breast images[C]//Proceedings of the 3rd IEEE Intemational Symposium on Biomedical Imaging:Nano to Macro,Arlington,Apr 6-9,2006.Piscataway,USA:IEEE,2006:852-855.

[10]Popuri K,Cobzas D,Jägersand M.Fast FEM-based non-rigid registration[C]//Proceedings of the 2010 Canadian Conference on Computer and Robot Vision,Ottawa,May 31-Jun 2,2010.Washington:IEEE Computer Society,2010:378-385.

[11]Zhang Yuanyuan.Researches on fingerprint identification related algorithms[D].Beijing:Beijing University of Posts and Telecommunications,2012.

[12]Chen Xiaoguang,Feng Jufu.A novel algorithm for distorted fingerprint matching using stable regions[J].Journal of Image and Graphics,2010,15(8):1220-1229.

[13]Chen Hongtao.A study of fingerprint recognition and encryption based on entropy analysis[D].Xi’an:Xidian University,2012.

[14]Chai Haiyan,Tian Dongping,Fan Jiulun,et al.Fingerprint minutia matching algorithm based on similar triangle theory [J].Communications Technology,2009,42(10):57-59.

[15]Yuan Dongfeng,Du Heng,Qin Xiaotie.Fingerprint matching algorithm based on local triangular feature point model[J]. Journal of Chongqing Normal University:Natural Science, 2013,30(2):69-73.

[16]Xie Jijian,Liu Chengping.Fuzzy mathematics method and its application[M].Wuhan:Huazhong University of Science and Technology Press,2008:61-122.

附中文参考文献：

[1]张博.基于数据挖掘和融合理论的残缺指纹识别应用研究用[D].北京:北京邮电大学,2012.

[2]李珂.基于稀疏矩阵的指纹识别系统研究[D].武汉:武汉科技大学,2012.

[4]付翔,封举富.一种基于细节点全局置信度的指纹匹配算法[J].模式识别与人工智能,2014,27(9):835-840.

[7]张洁.残缺指纹识别中若干关键技术的研究[D].北京:北京邮电大学,2013.

[8]曾超,李娜,王维,等.群搜索算法与Powell法结合的医学图像配准[J].云南大学学报:自然科学版,2013,35(5): 603-609.

[11]张圆圆.指纹识别技术相关算法的研究[D].北京:北京邮电大学,2012.

[12]陈小光,封举富.基于稳定区域的形变指纹匹配算法[J].中国图象图形学报,2010,15(8):1220-1229.

[13]陈宏涛.基于熵分析的指纹识别与加密算法应用研究[D].西安:西安电子科技大学,2012.

[14]柴海燕,田东平,范九伦,等.基于相似三角形原理的指纹匹配算法[J].通信技术,2009,42(10):57-59.

[15]袁东锋,杜恒,秦小铁.基于三角形局部特征点模型指纹匹配算法[J].重庆师范大学学报:自然科学版,2013,30 (2):69-73.

[16]谢季坚,刘承平.模糊数学方法及应用[M].武汉:华中科技大学出版社,2008:61-122.

YAO Lisha was born in 1986.She received the M.S.degree from Anhui University in 2011.Now she is a lecturer at Anhui Xinhua University.Her research interests include image processing,pattern recognition and artificial intelligence,etc.

姚丽莎（1986—），女，安徽合肥人，2011年于安徽大学获得硕士学位，现为安徽新华学院讲师，主要研究领域为图像处理，模式识别，人工智能等。主持两项安徽省高校自然科学重点研究项目。

CHENG Jiaxing was born in 1946.He received the Ph.D.degree from University of South Australia in 1997.Now he is a professor and Ph.D.supervisor at Anhui Xinhua University.His research interests include intelligent computing, pattern recognition and bio-informatics,etc.

程家兴（1946—），男，安徽合肥人，1997年于澳大利亚南澳大学获得博士学位，现为安徽新华学院教授、博士生导师，主要研究领域为智能计算，模式识别，生物信息学等。发表学术论文100余篇，主持2项国家自然科学基金项目，1项教育部优秀留学回国人员基金项目。

Fingerprint Registration Based on Finite Element*

YAO Lisha+,CHENG Jiaxing
Institute of Information Systems Software,Anhui Xinhua University,Hefei 230088,China
+Corresponding author:E-mail:jsjyaolisha@163.com

Fingerprint registration algorithm is studied for the complexity and variety of fingerprint deformation.Because the existing fingerprint registration algorithms have the defects of high complexity,low precision,slow speed and easy to be affected by fingerprint deformation,this paper introduces finite element analysis theory,and proposes a fingerprint registration algorithm based on finite element.In this algorithm,discrete finite element is used as basic unit to simulate the deformation of whole elastomer for complex deformation in fingerprint images.It takes the turning point,bifurcation point,the number of ridge lines between two points in fingerprint images and so on as the features. The fuzzy similarity is creatively proposed as metric for solving the overall stiffness equation to complete fingerprint registration.The experimental results show that the error of displacement of the proposed algorithm is the smallest and the time is 8.894 seconds,it lowers the complexity,and also improves the precision.At the same time,it can avoid the influence of the complexity and variety of fingerprint deformation on the accuracy of the fingerprint registration algorithm.

fingerprint registration;finite element;fuzzy similarity;fingerprint feature points

10.3778/j.issn.1673-9418.1602033

A

TP391.41

*The Natural Science Research Project of Anhui Colleges and Universities under Grant No.KJ2015A309(安徽省高校自然科学重点研究项目).

Received 2016-02,Accepted 2016-06.

CNKI网络优先出版:2016-06-02,http://www.cnki.net/kcms/detail/11.5602.TP.20160602.1144.004.html

YAO Lisha,CHENG Jiaxing.Fingerprint registration based on finite element.Journal of Frontiers of Computer Science and Technology,2017,11(4)：643-651.