指紋曲線數(shù)值擬合方法的對比和優(yōu)選

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

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

中圖分類號： 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 引 言

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

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

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

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

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

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

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

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

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

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

圖3 QR分解擬合良性情況

2 指紋曲線的多項式擬合

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

圖4 QR分解擬合劣性情況

圖5 多項式擬合良性情況

圖6 多項式擬合劣性情況

3 基本插值公式

3.1 用單項式基本插值公式進行插值擬合[6]

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

圖7 單項式插值擬合

3.2 用拉格朗日基本插值公式對指紋離散坐標進行

插值擬合

如圖8所示，沒有類似于圖7的警告信息，插值函數(shù)中也不會出現(xiàn)類似于圖7的亂真振蕩，這是因為拉格朗日多項式不需要線性方程組的解，也就不會有破壞Vandermonde方程組解的精度的病態(tài)性和舍入誤差問題。

圖8 拉格朗日插值擬合

3.3 離散點的牛頓插值公式對指紋離散坐標進行

插值擬合

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

3.4 分段多項式插值對指紋離散坐標進行插值擬合

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

3.5 折半搜索法進行分段線性插值對指紋離散坐標進行插值擬合

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

圖9 牛頓插值擬合

圖10 分段式插值擬合

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

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

3.6 三階樣條插值

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

圖13 三個階樣條插值擬合

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

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

5 對比分析和結論

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

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

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

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

6 結 語

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

參考文獻

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

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

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

[4] 劉霞，王運鋒.基于最小二乘法的自動分段多項式曲線擬合方法研究[J].科學技術與工程，2014（3）：55?58.

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

[6] 陳玉潔.多元多項式插值[D].長沙：國防科學技術大學，2003.

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

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

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