李青 张文杰 陈菁
摘 要： 指纹识别在数据加密方面有广泛的应用，在此基于数值方法，借助Matlab软件，利用最小二乘拟合、多项式曲线拟合、单项式基本插值、拉格朗日基本插值、牛顿基本插值、分段多项式插值和样条插值等不同曲线拟合方法对指纹曲线分别进行拟合，并对拟合效果和算法进行比较，优选最佳方法。针对劣性情况的指纹曲线，将广义延拓逼近法应用于指纹曲线拟合中，进一步完善指纹曲线拟合，实现了各种拟合方法的总结和比较以及扩展。
关键词： Matlab 数值方法； 指纹； 曲线拟合； 插值
中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2015）24?0027?04
Comparison and optimization of numerical fitting methods for fingerprint curves
LI Qing， ZHANG Wenjie， CHEN Jing
（School of Science， Beijing Forestry University， Beijing， 100083， China）
Abstract： Fingerprint identification， as a popular identification method， has been widely used in data encryption. The different curve fitting methods such as the least?squares fitting， polynomial curve fitting， monomial interpolation， Lagrange interpolation， Newton interpolation， polynomial interpolation in subsection， spline interpolation and so on are utilized in this paper to make the fingerprint curve fitting by means of Matlab software and on the basis of numerical methods. And then the fitting results and algorithm are compared to select an optimal method. The generalized extension approximation method is used in fingerprint curve fitting to deal with the bad fingerprint curves to further improve the fingerprint curve fitting. The summary， comparison and expansion of various fingerprint curve fitting methods were achieved.
Keywords： Matlab numerical method； fingerprint； curve fitting； interpolation
0 引 言
指纹识别作为近年来比较流行的识别方法，在数据加密、交通、门禁、司法等各个领域得到了越来越广泛的应用。在进行指纹曲线拟合时，可能会遇到指纹曲线类型多，拟合难度大，拟合效果不好的情况[1]。当前市面上的指纹识别，在断裂指纹的拼接这一方面，基本上是采用Gabor算子滤波的方式，虽然使用Gabor算子滤波效果不错，但是这种滤波要牵涉到一系列的卷积运算，通常是对整个指纹图像滤波，程序开销比较大，滤波时间也较长。然而，另一方面，如果用数值方法进行断裂曲线的拼接，它只是提取那些断裂的指纹曲线，用数值方法进行拟合，其他没有断裂的曲线，则保持原样。这样做的好处是，由于指纹中断裂的曲线一般不多，所以拟合比较快捷，程序开销较小。指纹断裂曲线的拼接属于指纹图像预处理环节，当把断裂指纹拼接上，之后的指纹识别就方便了。
曲线拟合是用连续曲线近似地刻画或比拟平面上离散点组所表示的坐标之间的函数关系的一种数据处理方法，其应用性非常强。本文基于数值方法，借助Matlab软件，利用最小二乘拟合、多项式曲线拟合、单项式基本插值、拉格朗日基本插值、牛顿基本插值、分段多项式插值和样条插值等不同曲线拟合方法对指纹曲线分别进行拟合，并对拟合效果和算法进行比较。在此基础上，针对劣性情况的指纹曲线，将广义延拓逼近法应用于指纹曲线拟合中，进一步完善指纹曲线拟合，实现了各种拟合方法的总结和比较以及扩展。
1 指纹数据的最小二乘拟合[2]
1.1 正规方程解指纹曲线的最小二乘拟合问题[3]
图1表明，残差为0.992 0时拟合质量良好，图2显示的是一种劣性情况，拟合质量比较差。
1.2 用QR分解法求最小二乘拟合
除了正规方程，最小二乘问题也可以由QR分解来解决。通过一些实现最小二乘法的Matlab内置命令，使用QR分解法来解超定方程组。正规方程法和QR分解法在解决最小二乘问题的差别不大，主要不同点在于计算所花费的浮点操作次数和数值的稳定性[4]。
图1 最小二乘拟合良性情况
图2 最小二乘拟合劣性情况
由图3，图4可知，对于良性问题，解正规方程和用QR分解法结果几乎一样，但对于劣性情况，QR分解法在使得残差最小这方面要优于解正规方程法[5]。
图3 QR分解拟合良性情况
2 指纹曲线的多项式拟合
由图5，图6可知，对于指纹曲线的劣性情况，二次多项式和三次多项式的拟合效果均不好，高次多项式拟合效果比低次拟合效果稍好，但并不等于次数越高效果越好。而简单的多项式拟合可以反映出曲线的大致弯曲程度，但对于劣性情况拟合的效果并不好。
图4 QR分解拟合劣性情况
图5 多项式拟合良性情况
图6 多项式拟合劣性情况
3 基本插值公式
3.1 用单项式基本插值公式进行插值拟合[6]
图7结果可见，警告信息指出了程序运行结果A=1×1016，A是病态的，RCOND = 3.170 723×1032是估计条件数的倒数，它的值很小，说明矩阵的条件数非常大。如图7所示，此时的插值函数出现严重的问题[7]。插值函数的曲线不是预料中的平滑曲线，而是不规则曲线。矩阵A的条件数非常大，因为其中的元素值的大小差异很大，它们中的最小元素是0，最大的元素是1×1016×4.045 4。在求解过程中的消去阶段，很小的舍入误差会导致很大的不确定性。在后面的代入过程中，会有更多的舍入误差，并对Ci的真值产生扰动，引起图中所示的振荡。舍入误差的问题是使用单项式基本插值公式进行多项式插值时固有的，这时因为Vandermonde矩阵通常是病态的。由于多项式求解中的舍入误差，插值函数对输入数据的逼近会变得不精确。
图7 单项式插值拟合
3.2 用拉格朗日基本插值公式对指纹离散坐标进行
插值拟合
如图8所示，没有类似于图7的警告信息，插值函数中也不会出现类似于图7的乱真振荡，这是因为拉格朗日多项式不需要线性方程组的解，也就不会有破坏Vandermonde方程组解的精度的病态性和舍入误差问题。
图8 拉格朗日插值拟合
3.3 离散点的牛顿插值公式对指纹离散坐标进行
插值拟合
如图9所示，牛顿形式插值采用均差形式比较方便，n阶插值多项式可通过向n-1阶牛顿多项式添加一个更高次项获得。它计算比较高效，并且随着多项式阶数的增加，它仍然能够保持比较可行的操作次数。牛顿形式插值的结果取决于支点的选取和插值多项式的阶数。
3.4 分段多项式插值对指纹离散坐标进行插值拟合
如图10所示，斜率不连续性表现得比较明显。在进行分段线性插值的实现中，比较重要的是在构造插值式时选用合适的支点对。在一个对任意数据集进行分段线性插值的Matlab函数中，支点的查找和插值函数计算都可以用Matlab程序自动完成。
3.5 折半搜索法进行分段线性插值对指纹离散坐标进行插值拟合
如图11，图12所示，此算法显示出一个弊端就是在节点处虽然是连续的，但曲线并不光滑。节点处导数的连续性没有受到约束，所以还有待于进一步改进。
图9 牛顿插值拟合
图10 分段式插值拟合
图11 折半搜索法分段线性插值（一）
图12 折半搜索法分段线性插值（二）
3.6 三阶样条插值
三阶倦条插值结果如图13所示，离散指纹数据对整个固定端点斜率进行三阶样条插值，插值的效果并不好。在中间空白区域，插值后得到的曲线受力断裂部分最近的两个端点的影响较大。这两个端点的斜率的大小会影响到断裂部分插值的效果。但整个数据对集的边界端点的斜率大小，对于断裂部分插值的效果影响不大。当整个数据对集的边界端点为不同值时，整个曲线的变化并不明显，需要进一步改进。
图13 三个阶样条插值拟合
4 广义延拓逼近法Matlab实现
首先将指纹曲线两个端点处的片段拟合起来，因为端点处的片段不方便进行单元域的延拓。程序中采用了Matlab内置的interp1来实现，用三阶样条同样可以实现，效果差别不大。除两端点外的其他片段都采用广义延拓逼近法实现。将每个片段的拟合函数的系数矩阵求出来，即可求得每个片段的逼近函数，再拼接起来，即可构造相应的指纹曲线[8]。由图14和图15可见，拟合的结果比较理想。可以通过延拓域的节点来约束当前段的拟合，可操作性较好，效率较高[9]。
5 对比分析和结论
最小二乘拟合能很好的跟踪离散数据点趋势。求单项式基本插值公式的系数需要解Vandermonde矩阵，而矩阵可能是病态的，这样会导致单项式系数不确定。另外单项式中的各项可能在大小上有很大差异，会导致多项式计算中的舍入误差。这些数值上的复杂性可在构造Vandermonde方程组之前通过对数据x进行转换和缩放来改进。拉格朗日基本插值公式插值在理论分析中很有用，由拉格朗日基本插值公式形成的多项式插值式的舍入误差比较小，但是计算比较繁琐。牛顿多项式基本插值法不但舍入误差比较小，而且计算公式也很高效.换句话说，对数值计算来讲，使用牛顿基本插值公式进行插值比使用单项式或拉格朗日基本插值公式更好。牛顿插值多项式的系数是输入数据集的均差，均差在推导三阶样条时很有用。需要注意的是，对均匀分布的支点数据进行任意阶的多项式插值时，必须防止由多项式摆动带来的误差。多项式摆动会影响任何基本插值公式上定义的多项式。分段多项式插值使用相对低阶的多项式，它们定义在输入数据的子集上。对一维数据来说，插值式是由很多插值式在某些点上连接而成，所以需要选择好合适的局部插值式。若采用三阶样条插值，插值式的总体平滑比较好，样条插值式的精确度要受端点条件的影响很大，但通过本文的实验，三阶样条在指纹曲线的拟合方面，效果并不好[5]。
图14 广义延拓逼近法（一）
图15 广义延拓逼近法（二）
对于劣性情况，本文将广义延拓逼近算法引进到指纹曲线的拟合。所谓广义延拓逼近算法是通过在延拓域上进行拟合逼近，在边界上进行插值约束处理，将插值法和拟合法有机地结合，从而形成了广义延拓算法自己的特点。广义延拓外推模型基本上继承了最小二乘拟合的长处，可以充分地运用较多的实验数据点，同时可以把最新的数据点锁住，充分发挥最新数据的作用与影响，也就是用最新的数据进行插值约束处理。通过本文的实验，广义延拓逼近算法在指纹曲线拟合方面的效果比较好。
6 结 语
本文利用Matlab工具，通过数值方法，对指纹曲线使用多种方法分别进行拟合，选择将广义延拓逼近法应用其中，进一步完善了指纹曲线拟合，实现了各种拟合方法的总结和比较以及扩展。通过数值方法对指纹曲线进行拟合，拟合效果较好，但其缺点在于需要对指纹曲线一根一根拟合，所需工作时间可能要较长。但是，这也是它的优点所在，正是由于它是一根一根的拟合，对于没有断裂的曲线，则保持原样，不需要所有曲线（包含未断裂的）都进行拟合，减少了工作量。本文所提到的这些拟合插值方法，不仅可使用在指纹曲线的拟合中，在其他需要曲线拟合的研究领域也有广泛的应用。
参考文献
[1] 李昊，傅曦.指纹模式识别系统算法及实现[M].北京：人民邮电出版社，2008.
[2] 解同信.最小二乘法求作拟合直线[J].北京工业职业技术学院学报，2006（3）：5?7.
[3]吕喜明，李明远.最小二乘曲线拟合的Matlab实现[J].内蒙古民族大学学报：自然科学版，2009（2）：125?127.
[4] 刘霞，王运锋.基于最小二乘法的自动分段多项式曲线拟合方法研究[J].科学技术与工程，2014（3）：55?58.
[5] 李庆扬，王能超，易大义.数值分析[M].北京：清华大学出版社，2001.
[6] 陈玉洁.多元多项式插值[D].长沙：国防科学技术大学，2003.
[7] 韩艳丽，李凤萍.插值与曲线拟合[J].中国西部科技，2009（11）：91?92.
[8] 施浒立，颜毅华，徐国华.工程科学中的广义延拓逼近法[M].北京：科学出版社，2005.
[9] 王银龙.基于广义延拓逼近的暂态稳定分析[J].机电工程，2007，24（10）：51?53.
