摘 要： 指紋識(shí)別在數(shù)據(jù)加密方面有廣泛的應(yīng)用，在此基于數(shù)值方法，借助Matlab軟件，利用最小二乘擬合、多項(xiàng)式曲線擬合、單項(xiàng)式基本插值、拉格朗日基本插值、牛頓基本插值、分段多項(xiàng)式插值和樣條插值等不同曲線擬合方法對(duì)指紋曲線分別進(jìn)行擬合，并對(duì)擬合效果和算法進(jìn)行比較，優(yōu)選最佳方法。針對(duì)劣性情況的指紋曲線，將廣義延拓逼近法應(yīng)用于指紋曲線擬合中，進(jìn)一步完善指紋曲線擬合，實(shí)現(xiàn)了各種擬合方法的總結(jié)和比較以及擴(kuò)展。

關(guān)鍵詞： Matlab 數(shù)值方法； 指紋； 曲線擬合； 插值

中圖分類號(hào)： TN911?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

指紋識(shí)別作為近年來比較流行的識(shí)別方法，在數(shù)據(jù)加密、交通、門禁、司法等各個(gè)領(lǐng)域得到了越來越廣泛的應(yīng)用。在進(jìn)行指紋曲線擬合時(shí)，可能會(huì)遇到指紋曲線類型多，擬合難度大，擬合效果不好的情況[1]。當(dāng)前市面上的指紋識(shí)別，在斷裂指紋的拼接這一方面，基本上是采用Gabor算子濾波的方式，雖然使用Gabor算子濾波效果不錯(cuò)，但是這種濾波要牽涉到一系列的卷積運(yùn)算，通常是對(duì)整個(gè)指紋圖像濾波，程序開銷比較大，濾波時(shí)間也較長(zhǎng)。然而，另一方面，如果用數(shù)值方法進(jìn)行斷裂曲線的拼接，它只是提取那些斷裂的指紋曲線，用數(shù)值方法進(jìn)行擬合，其他沒有斷裂的曲線，則保持原樣。這樣做的好處是，由于指紋中斷裂的曲線一般不多，所以擬合比較快捷，程序開銷較小。指紋斷裂曲線的拼接屬于指紋圖像預(yù)處理環(huán)節(jié)，當(dāng)把斷裂指紋拼接上，之后的指紋識(shí)別就方便了。

曲線擬合是用連續(xù)曲線近似地刻畫或比擬平面上離散點(diǎn)組所表示的坐標(biāo)之間的函數(shù)關(guān)系的一種數(shù)據(jù)處理方法，其應(yīng)用性非常強(qiáng)。本文基于數(shù)值方法，借助Matlab軟件，利用最小二乘擬合、多項(xiàng)式曲線擬合、單項(xiàng)式基本插值、拉格朗日基本插值、牛頓基本插值、分段多項(xiàng)式插值和樣條插值等不同曲線擬合方法對(duì)指紋曲線分別進(jìn)行擬合，并對(duì)擬合效果和算法進(jìn)行比較。在此基礎(chǔ)上，針對(duì)劣性情況的指紋曲線，將廣義延拓逼近法應(yīng)用于指紋曲線擬合中，進(jìn)一步完善指紋曲線擬合，實(shí)現(xiàn)了各種擬合方法的總結(jié)和比較以及擴(kuò)展。

1 指紋數(shù)據(jù)的最小二乘擬合[2]

1.1 正規(guī)方程解指紋曲線的最小二乘擬合問題[3]

圖1表明，殘差為0.992 0時(shí)擬合質(zhì)量良好，圖2顯示的是一種劣性情況，擬合質(zhì)量比較差。

1.2 用QR分解法求最小二乘擬合

除了正規(guī)方程，最小二乘問題也可以由QR分解來解決。通過一些實(shí)現(xiàn)最小二乘法的Matlab內(nèi)置命令，使用QR分解法來解超定方程組。正規(guī)方程法和QR分解法在解決最小二乘問題的差別不大，主要不同點(diǎn)在于計(jì)算所花費(fèi)的浮點(diǎn)操作次數(shù)和數(shù)值的穩(wěn)定性[4]。

圖1 最小二乘擬合良性情況

圖2 最小二乘擬合劣性情況

由圖3，圖4可知，對(duì)于良性問題，解正規(guī)方程和用QR分解法結(jié)果幾乎一樣，但對(duì)于劣性情況，QR分解法在使得殘差最小這方面要優(yōu)于解正規(guī)方程法[5]。

圖3 QR分解擬合良性情況

2 指紋曲線的多項(xiàng)式擬合

由圖5，圖6可知，對(duì)于指紋曲線的劣性情況，二次多項(xiàng)式和三次多項(xiàng)式的擬合效果均不好，高次多項(xiàng)式擬合效果比低次擬合效果稍好，但并不等于次數(shù)越高效果越好。而簡(jiǎn)單的多項(xiàng)式擬合可以反映出曲線的大致彎曲程度，但對(duì)于劣性情況擬合的效果并不好。

圖4 QR分解擬合劣性情況

圖5 多項(xiàng)式擬合良性情況

圖6 多項(xiàng)式擬合劣性情況

3 基本插值公式

3.1 用單項(xiàng)式基本插值公式進(jìn)行插值擬合[6]

圖7結(jié)果可見，警告信息指出了程序運(yùn)行結(jié)果A=1×1016，A是病態(tài)的，RCOND = 3.170 723×1032是估計(jì)條件數(shù)的倒數(shù)，它的值很小，說明矩陣的條件數(shù)非常大。如圖7所示，此時(shí)的插值函數(shù)出現(xiàn)嚴(yán)重的問題[7]。插值函數(shù)的曲線不是預(yù)料中的平滑曲線，而是不規(guī)則曲線。矩陣A的條件數(shù)非常大，因?yàn)槠渲械脑刂档拇笮〔町惡艽?，它們中的最小元素?，最大的元素是1×1016×4.045 4。在求解過程中的消去階段，很小的舍入誤差會(huì)導(dǎo)致很大的不確定性。在后面的代入過程中，會(huì)有更多的舍入誤差，并對(duì)Ci的真值產(chǎn)生擾動(dòng)，引起圖中所示的振蕩。舍入誤差的問題是使用單項(xiàng)式基本插值公式進(jìn)行多項(xiàng)式插值時(shí)固有的，這時(shí)因?yàn)閂andermonde矩陣通常是病態(tài)的。由于多項(xiàng)式求解中的舍入誤差，插值函數(shù)對(duì)輸入數(shù)據(jù)的逼近會(huì)變得不精確。

圖7 單項(xiàng)式插值擬合

3.2 用拉格朗日基本插值公式對(duì)指紋離散坐標(biāo)進(jìn)行

插值擬合

如圖8所示，沒有類似于圖7的警告信息，插值函數(shù)中也不會(huì)出現(xiàn)類似于圖7的亂真振蕩，這是因?yàn)槔窭嗜斩囗?xiàng)式不需要線性方程組的解，也就不會(huì)有破壞Vandermonde方程組解的精度的病態(tài)性和舍入誤差問題。

圖8 拉格朗日插值擬合

3.3 離散點(diǎn)的牛頓插值公式對(duì)指紋離散坐標(biāo)進(jìn)行

插值擬合

如圖9所示，牛頓形式插值采用均差形式比較方便，n階插值多項(xiàng)式可通過向n-1階牛頓多項(xiàng)式添加一個(gè)更高次項(xiàng)獲得。它計(jì)算比較高效，并且隨著多項(xiàng)式階數(shù)的增加，它仍然能夠保持比較可行的操作次數(shù)。牛頓形式插值的結(jié)果取決于支點(diǎn)的選取和插值多項(xiàng)式的階數(shù)。

3.4 分段多項(xiàng)式插值對(duì)指紋離散坐標(biāo)進(jìn)行插值擬合

如圖10所示，斜率不連續(xù)性表現(xiàn)得比較明顯。在進(jìn)行分段線性插值的實(shí)現(xiàn)中，比較重要的是在構(gòu)造插值式時(shí)選用合適的支點(diǎn)對(duì)。在一個(gè)對(duì)任意數(shù)據(jù)集進(jìn)行分段線性插值的Matlab函數(shù)中，支點(diǎn)的查找和插值函數(shù)計(jì)算都可以用Matlab程序自動(dòng)完成。

3.5 折半搜索法進(jìn)行分段線性插值對(duì)指紋離散坐標(biāo)進(jìn)行插值擬合

如圖11，圖12所示，此算法顯示出一個(gè)弊端就是在節(jié)點(diǎn)處雖然是連續(xù)的，但曲線并不光滑。節(jié)點(diǎn)處導(dǎo)數(shù)的連續(xù)性沒有受到約束，所以還有待于進(jìn)一步改進(jìn)。

圖9 牛頓插值擬合

圖10 分段式插值擬合

圖11 折半搜索法分段線性插值（一）

圖12 折半搜索法分段線性插值（二）

3.6 三階樣條插值

三階倦條插值結(jié)果如圖13所示，離散指紋數(shù)據(jù)對(duì)整個(gè)固定端點(diǎn)斜率進(jìn)行三階樣條插值，插值的效果并不好。在中間空白區(qū)域，插值后得到的曲線受力斷裂部分最近的兩個(gè)端點(diǎn)的影響較大。這兩個(gè)端點(diǎn)的斜率的大小會(huì)影響到斷裂部分插值的效果。但整個(gè)數(shù)據(jù)對(duì)集的邊界端點(diǎn)的斜率大小，對(duì)于斷裂部分插值的效果影響不大。當(dāng)整個(gè)數(shù)據(jù)對(duì)集的邊界端點(diǎn)為不同值時(shí)，整個(gè)曲線的變化并不明顯，需要進(jìn)一步改進(jìn)。

圖13 三個(gè)階樣條插值擬合

4 廣義延拓逼近法Matlab實(shí)現(xiàn)

首先將指紋曲線兩個(gè)端點(diǎn)處的片段擬合起來，因?yàn)槎它c(diǎn)處的片段不方便進(jìn)行單元域的延拓。程序中采用了Matlab內(nèi)置的interp1來實(shí)現(xiàn)，用三階樣條同樣可以實(shí)現(xiàn)，效果差別不大。除兩端點(diǎn)外的其他片段都采用廣義延拓逼近法實(shí)現(xiàn)。將每個(gè)片段的擬合函數(shù)的系數(shù)矩陣求出來，即可求得每個(gè)片段的逼近函數(shù)，再拼接起來，即可構(gòu)造相應(yīng)的指紋曲線[8]。由圖14和圖15可見，擬合的結(jié)果比較理想。可以通過延拓域的節(jié)點(diǎn)來約束當(dāng)前段的擬合，可操作性較好，效率較高[9]。

5 對(duì)比分析和結(jié)論

最小二乘擬合能很好的跟蹤離散數(shù)據(jù)點(diǎn)趨勢(shì)。求單項(xiàng)式基本插值公式的系數(shù)需要解Vandermonde矩陣，而矩陣可能是病態(tài)的，這樣會(huì)導(dǎo)致單項(xiàng)式系數(shù)不確定。另外單項(xiàng)式中的各項(xiàng)可能在大小上有很大差異，會(huì)導(dǎo)致多項(xiàng)式計(jì)算中的舍入誤差。這些數(shù)值上的復(fù)雜性可在構(gòu)造Vandermonde方程組之前通過對(duì)數(shù)據(jù)x進(jìn)行轉(zhuǎn)換和縮放來改進(jìn)。拉格朗日基本插值公式插值在理論分析中很有用，由拉格朗日基本插值公式形成的多項(xiàng)式插值式的舍入誤差比較小，但是計(jì)算比較繁瑣。牛頓多項(xiàng)式基本插值法不但舍入誤差比較小，而且計(jì)算公式也很高效.換句話說，對(duì)數(shù)值計(jì)算來講，使用牛頓基本插值公式進(jìn)行插值比使用單項(xiàng)式或拉格朗日基本插值公式更好。牛頓插值多項(xiàng)式的系數(shù)是輸入數(shù)據(jù)集的均差，均差在推導(dǎo)三階樣條時(shí)很有用。需要注意的是，對(duì)均勻分布的支點(diǎn)數(shù)據(jù)進(jìn)行任意階的多項(xiàng)式插值時(shí)，必須防止由多項(xiàng)式擺動(dòng)帶來的誤差。多項(xiàng)式擺動(dòng)會(huì)影響任何基本插值公式上定義的多項(xiàng)式。分段多項(xiàng)式插值使用相對(duì)低階的多項(xiàng)式，它們定義在輸入數(shù)據(jù)的子集上。對(duì)一維數(shù)據(jù)來說，插值式是由很多插值式在某些點(diǎn)上連接而成，所以需要選擇好合適的局部插值式。若采用三階樣條插值，插值式的總體平滑比較好，樣條插值式的精確度要受端點(diǎn)條件的影響很大，但通過本文的實(shí)驗(yàn)，三階樣條在指紋曲線的擬合方面，效果并不好[5]。

圖14 廣義延拓逼近法（一）

圖15 廣義延拓逼近法（二）

對(duì)于劣性情況，本文將廣義延拓逼近算法引進(jìn)到指紋曲線的擬合。所謂廣義延拓逼近算法是通過在延拓域上進(jìn)行擬合逼近，在邊界上進(jìn)行插值約束處理，將插值法和擬合法有機(jī)地結(jié)合，從而形成了廣義延拓算法自己的特點(diǎn)。廣義延拓外推模型基本上繼承了最小二乘擬合的長(zhǎng)處，可以充分地運(yùn)用較多的實(shí)驗(yàn)數(shù)據(jù)點(diǎn)，同時(shí)可以把最新的數(shù)據(jù)點(diǎn)鎖住，充分發(fā)揮最新數(shù)據(jù)的作用與影響，也就是用最新的數(shù)據(jù)進(jìn)行插值約束處理。通過本文的實(shí)驗(yàn)，廣義延拓逼近算法在指紋曲線擬合方面的效果比較好。

6 結(jié) 語

本文利用Matlab工具，通過數(shù)值方法，對(duì)指紋曲線使用多種方法分別進(jìn)行擬合，選擇將廣義延拓逼近法應(yīng)用其中，進(jìn)一步完善了指紋曲線擬合，實(shí)現(xiàn)了各種擬合方法的總結(jié)和比較以及擴(kuò)展。通過數(shù)值方法對(duì)指紋曲線進(jìn)行擬合，擬合效果較好，但其缺點(diǎn)在于需要對(duì)指紋曲線一根一根擬合，所需工作時(shí)間可能要較長(zhǎng)。但是，這也是它的優(yōu)點(diǎn)所在，正是由于它是一根一根的擬合，對(duì)于沒有斷裂的曲線，則保持原樣，不需要所有曲線（包含未斷裂的）都進(jìn)行擬合，減少了工作量。本文所提到的這些擬合插值方法，不僅可使用在指紋曲線的擬合中，在其他需要曲線擬合的研究領(lǐng)域也有廣泛的應(yīng)用。

參考文獻(xiàn)

[1] 李昊，傅曦.指紋模式識(shí)別系統(tǒng)算法及實(shí)現(xiàn)[M].北京：人民郵電出版社，2008.

[2] 解同信.最小二乘法求作擬合直線[J].北京工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2006（3）：5?7.

[3]呂喜明，李明遠(yuǎn).最小二乘曲線擬合的Matlab實(shí)現(xiàn)[J].內(nèi)蒙古民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2009（2）：125?127.

[4] 劉霞，王運(yùn)鋒.基于最小二乘法的自動(dòng)分段多項(xiàng)式曲線擬合方法研究[J].科學(xué)技術(shù)與工程，2014（3）：55?58.

[5] 李慶揚(yáng)，王能超，易大義.數(shù)值分析[M].北京：清華大學(xué)出版社，2001.

[6] 陳玉潔.多元多項(xiàng)式插值[D].長(zhǎng)沙：國(guó)防科學(xué)技術(shù)大學(xué)，2003.

[7] 韓艷麗，李鳳萍.插值與曲線擬合[J].中國(guó)西部科技，2009（11）：91?92.

[8] 施滸立，顏毅華，徐國(guó)華.工程科學(xué)中的廣義延拓逼近法[M].北京：科學(xué)出版社，2005.

[9] 王銀龍.基于廣義延拓逼近的暫態(tài)穩(wěn)定分析[J].機(jī)電工程，2007，24（10）：51?53.