基于小波變換的指紋全局方向場重建符闊

陳忠澤

摘 要：從大型指紋庫識別不完整或局部指紋仍然是今天的一大挑戰(zhàn)。在此文中，我們研究利用小波變換用于指紋方向場重建問題。特別的，我們提出了一種基于小波的多尺度方法從局部的指紋重建全局拓?fù)浔磉_(dá)。然后提出基于結(jié)合參數(shù)模型和非參數(shù)模型來描述重建問題，我們提供了一般表達(dá)式可用于所有有效的反變換模型的解決方案。這種方案允許我們分割保護(hù)存在的方向場同時預(yù)測丟失的未知部分的結(jié)構(gòu)。我們還開發(fā)了基于脊線拓?fù)涮卣鞯囊恍┫闰炐畔砉烙媮G失的方向結(jié)構(gòu)的算法。我們的統(tǒng)計實驗表明我們提出的基于模型的算法能有效的恢復(fù)指紋的方向場并應(yīng)用于指紋匹配，這樣重大的提高了局部指紋識別其他模塊性能。

關(guān)鍵詞：局部指紋；全局方向重建；小波模型

Wavelet transform for global fingerprint orientation field reconstruction

Kuo Fu Zhong Zhe Chen（College of Electrical Engineering，Nanhua University，Hengyang 421001，China）

Abstract：Identifying incomplete or partial fingerprints from a large fingerprint database remains a difficult challenge today. In this paper， we investigate the problem of inverse orientation model by exploiting wavelet translation. Specifically， we propose an wavelet based multiscale approach for reconstructing the global topology representation from a partial fingerprint. Then，we present an combine parametric model and non-parametric model for describing the reconstruction problem. we provide a general expression for all valid solutions to the inverse model. This allows us to preserve data fidelity in the existing segments while exploring missing structures in the unknown parts.We have further developed algorithms for estimating the missing orientation structures based on some a priori knowledge of ridge topology features. Our statistical experiments show that our proposed model-based approach can effectively reconstruct the orientation of fingerprint and used for pair-wised fingerprint matching， and thus significantly improve the other system module performance for partial fingerprint identification.

Key words：Partial fingerprint；global orientation reconstruction；wavelet model

在基于細(xì)節(jié)點指紋識別系統(tǒng)中，以前的認(rèn)識中基于細(xì)節(jié)點匹配的指紋存儲模板是安全且不屬于侵犯個人隱私權(quán)，而從2007年的發(fā)表的由細(xì)節(jié)模板重建原始指紋[2，3]的論文打破了這一認(rèn)識。指紋重建首先任務(wù)是由細(xì)節(jié)點模板重建方向場，把細(xì)節(jié)點模板類比于質(zhì)量很差的指紋，指紋重建可以借鑒用來得到更準(zhǔn)確更完整的方向場。另外低質(zhì)量指紋圖像的特征提取一直是自動指紋識別的一大難題，因為低質(zhì)量的指紋圖像難以計算其正確的紋路方向、紋路頻率，從而難以正確地提取奇異點、增強(qiáng)紋路和提取細(xì)節(jié)點。所以重建準(zhǔn)確的方向場才能很好的解決低質(zhì)量指紋處理問題。Jain和Feng[5]對局部指紋匹配進(jìn)行了詳細(xì)的介紹和改進(jìn)，文中強(qiáng)調(diào)增加特

征類型或數(shù)量，注重進(jìn)行指紋一對一的匹配。由于沒有分類檢索機(jī)制，如果用于大型指紋數(shù)據(jù)庫達(dá)不到實時識別認(rèn)證的效果。

現(xiàn)在大多數(shù)流行的指紋分類算法都需要一個值得信賴的方向圖，現(xiàn)有多種方法來估計指紋圖像的方向圖。文獻(xiàn)綜述[6]對大多數(shù)指紋方向場的方法進(jìn)行了介紹，大體分為局部估計和全局模型兩類。局部估計的方法包括梯度計算法[7]、基于濾波的方法、脊線投影法以及基于結(jié)構(gòu)張量等。由這些方法得到的指紋方向圖通常會有噪聲，得到的方向圖不夠連續(xù)，需要對方向圖進(jìn)行平滑處理。早期的全局方向場模型包括零極點模型、非線性相位模型、多項式模型以及多模型結(jié)合等，這些模型都依賴于準(zhǔn)確奇異點信息，但奇異點信息本就依賴于好的方向場。Wang和Hu[8]提出基于傅里葉級數(shù)模型來重建方向場，這種模型不但不需要奇異點信息，反而可以從模型中提取奇異點，而且模型系數(shù)被用來構(gòu)成特征向量用于指紋分類檢索。之后類似功能的模型相繼提出，Ram[9]使用勒讓德多項式模型，首先通過最小二乘法求得粗糙的模型參數(shù)，然后通過優(yōu)化的目標(biāo)函數(shù)得到精確參數(shù)。Liu[10]等使用基于復(fù)極矩（polar complex moments）基函數(shù)模型來重建方向場，且通過對齊參考點后的不變特征表達(dá)模型系數(shù)用于指紋檢索。這些模型不需要指紋先驗信息從而解決了低質(zhì)量指紋不能使用全局模型的缺點，但是Cappelli[11]指出這些全局模型在指紋質(zhì)量低到一定程度時預(yù)測全局方向場并不比梯度方法計算精確，甚至在奇異點附近存在更大誤差。所以許多對這些模型改進(jìn)或?qū)Ρ鹊恼撐囊蚕嗬^出現(xiàn)，文獻(xiàn)[12]通過對傅里葉級數(shù)模型在變換時加入質(zhì)量權(quán)值，這樣對質(zhì)量較差區(qū)域并不是完全舍去或是完全加入模型計算，對重建效果有一定的提高。文獻(xiàn)[13]通過殘余誤差項分析，較大誤差區(qū)域一般都位于奇異點，使誤差較大區(qū)域使用更高階的多項式來擬合，可以優(yōu)化全局模型對于奇異點附近方向誤差較大的問題。以上參數(shù)模型的方法大都離不開最小二乘法，用來找出一組模型系數(shù)使得模型擬合方向值后誤差的平方最小。Wang[15]擺脫復(fù)雜的最小二乘法，使用少量指紋區(qū)域通過膨脹平滑拓展的方法重建全局方向場，對奇異點區(qū)域偏差有較大的改善。文獻(xiàn)還使用了固定的外圍拱形模型代替背景區(qū)域方向場，并統(tǒng)計了圖像高質(zhì)量區(qū)域的大小對重建全局方向場可靠性的影響。值得注意的是文獻(xiàn)[14]提出非參數(shù)模型，其原理是變分方法，構(gòu)想出的指紋平坦區(qū)域類比于動能而奇異點區(qū)域類比于勢能處理方法，雖然在奇異點區(qū)域重建效果不理性，但是其重建的方向場平滑性好。

針對以上問題，本文提出了一種基于小波變換的指紋全局方向場重建方法。本文首先通過分析參數(shù)模型和非參數(shù)的優(yōu)缺點，隨后使用小波變換對初始方向場進(jìn)行重建得到全局的方向場，并提出了一種結(jié)合參數(shù)模型和非參數(shù)模型的改進(jìn)的重建方法。最后進(jìn)行試驗，結(jié)果表明本文算法對指紋方向場重建有較好的表現(xiàn)。

1 相關(guān)工作介紹與分析

1.1 基于多項式的指紋方向場模型

目前常用的指紋方向場計算方法是基于梯度的方法[7]?；谔荻鹊姆椒ň哂懈咝院鸵子趯崿F(xiàn)的特點，但是對噪聲比較敏感，對于低質(zhì)量指紋圖像基于梯度的方法得到的方向場并不理想。因此，常用基于梯度的方法來粗略估計指紋的方向場，然后采用基于濾波的平滑算法或者基于數(shù)學(xué)模型的計算方法進(jìn)一步消除噪聲影響?；跀?shù)學(xué)模型的計算方法由于其采用全局的方向場信息，對噪聲有較好的魯棒性。文獻(xiàn)[8，9，10]分別提出基于FOMFE、勒讓德多項式、復(fù)極矩的方向場計算模型，這些模型不需要指紋奇異點等先驗信息，算法運(yùn)行速度比較快，并且能夠有效去除噪聲的影響。這些方法本質(zhì)相同。首先采用梯度法計算指紋方向場θ（x，y），然后采用數(shù)學(xué)模型對指紋方向場進(jìn)行重建，有效去除噪聲的影響。由于方向角θ（x，y）的范圍在0～π并且是不連續(xù)的，為了避免方向角θ（x，y）不連續(xù)性的影響，引入一個新的二維向量：

由于f的連續(xù)性，才可以通過其它模型來進(jìn)行擬合，甚至是通過微分公式提取奇異點。對于任意f都可以寫成一系列基函數(shù)的線性組合與一個余項之和。多項式擬合的過程就是通過某種優(yōu)化算法得到一組系數(shù)，使得余項（誤差）最小，如下式所示：

式中，f為由梯度法得到的方向場轉(zhuǎn)換到sin和cos域的值，ε是噪聲或誤差，Ψ為以上提到的方向場模型。從上式求解系數(shù)β通?？紤]最小二乘法的問題：

然而，當(dāng)噪聲在f中的比例很大時，噪聲將被放大在解最小平方問題之后。為了抑制噪聲和保護(hù)圖像的特征，文獻(xiàn)[12]利用指紋質(zhì)量權(quán)值來解決這一問題，考慮權(quán)值l2范數(shù)：

式中 ；D為指紋質(zhì)量權(quán)值，運(yùn)算過程中通常將f轉(zhuǎn)換為1維向量，所以D只在對角線上有值，所以對求逆運(yùn)算無影響。解決問題（4）的方法考慮誤差向量ε與方向場模型的基向量正交：

假設(shè)平方矩陣ΨTΨ可逆，式（5）變?yōu)椋?/p>

指紋方向場零極點模型與混合模型的共同特點是都需要預(yù)先獲得指紋的奇異點信息，而多項式反變換模型能夠準(zhǔn)確的擬合出指紋的方向場分布，同時，該模型不需要預(yù)先獲得指紋的奇異點信息。然而，這么多存在的模型，都只是一種近似方法而不是真實的模型，因此指紋模式的自然變化在模型中沒有體現(xiàn)。所以當(dāng)有很大部分區(qū)域的為噪聲時，模型的恢復(fù)能力受到限制。

1.2 非參數(shù)模型

基于變分方法的指紋方向場總體模型考慮在時域進(jìn)行處理，主要考慮在時域的正則性，因此對正則項不同的定義可以得到不同的效果：

其中u為理想的方向場，右邊第一項為正則項，保證得到的方向場平滑；第二項為保真項，保證得到的數(shù)據(jù)盡可能接近原始方向場。在文獻(xiàn)[14]中p=2，把指紋的擴(kuò)散類似動力學(xué)變分原理中，正則項類似動能對應(yīng)指紋平滑區(qū)域，第二項類似勢能對應(yīng)指紋奇異點區(qū)域。采用梯度下降法，其歐拉格朗日方程：

上式為熱擴(kuò)散方程，擴(kuò)散各方向同性。然而指紋方向場具有不可壓縮流動流體的性質(zhì)，各向同性擴(kuò)散并不能很好的求解，因此在方向場降噪或修復(fù)的同時奇異點區(qū)域模糊。當(dāng)我們考慮各項異性擴(kuò)散時，令p=1；（7）式變?yōu)閺V泛使用的TV正則化模型：

在接下來的章節(jié)提出了綜合參數(shù)模型和非參數(shù)模型指紋方向場重建算法。

2 小波重建指紋方向場

2.1 小波變換

由于指紋模型系數(shù)多種應(yīng)用，如指紋檢索，分類。所以在指紋方向場模型中都希望求得的模型系數(shù)盡可能的少，而小波變換得到的系數(shù)和原始方向場的數(shù)量相同，因此在指紋方向場模型中很少用到。其實只要保證得到的小波系數(shù)盡可能的稀疏，小波本來就是很好的壓縮特性。而且相對于計算一系列基函數(shù)矩陣，小波變換計算更加方便簡單。同時擁有多尺度分析的能力對于奇異點的方向場計算更加精確。小波變換類似于其它指紋方向場模型的表達(dá)式：

由正交小波多尺度分析的尺度子空間Vj的標(biāo)準(zhǔn)正交基為{φj，k}，小波子空間Wj的標(biāo)準(zhǔn)正交基為{ψj，k}，多尺度分析的空間關(guān)系為Vj-1=Vj⊕Wj。根據(jù)雙尺度差分方程構(gòu)造定理：

前后兩個空間基之間的關(guān)系：

信號在前后兩個空間基上投影系數(shù)之間的關(guān)系：

當(dāng)考慮信號在Rn空間，這些線性算子有矩陣表達(dá)形式，簡單的表示小波分解為W。由于指紋奇異點區(qū)域方向場屬于高頻，平坦區(qū)域?qū)儆诘皖l。所以小波變換后指紋方向場不同區(qū)域會被分解到不同的層次。與其它模型相似之處在于使用盡可能少的系數(shù)來表示一個方向場，所以通過設(shè)閾值保留小波系數(shù)中的主要值，可以實現(xiàn)小波的方向場擬合。與其它模型的不同之處在于小波變換為時頻分析，即每個小波系數(shù)與時域有對應(yīng)關(guān)系，這也是方向場在不同的尺度對應(yīng)指紋的不同區(qū)域。

2.2 基于小波指紋方向場重建

指紋方向場O（x，y）是關(guān)于指紋塊（x，y）的函數(shù)，所以方向場恢復(fù)的目標(biāo)就是找到未知區(qū)域的方向從觀察到的初始方向場。指紋恢復(fù)是一個反變換問題，為了簡化符號，我們把方向場表示成向量在Rn空間，n等于總共的方向值。目標(biāo)是從觀察到的方向場f∈Rl找到未知的正確方向場u∈Rn：

式中 在方向場重建中為投影算子，與指紋質(zhì)量權(quán)值D有相同的性質(zhì)。為了不失一般性，我們考慮局部指紋段Ω為指定的二維指紋圖像前景區(qū)域，假設(shè)的指紋脊線流形具有連續(xù)性，我們希望延長流形趨勢從局部Λ的邊界平滑到未知區(qū)域（Ω＼Λ）。估計未知區(qū)域方向場必須包含信息從存在的片段Ω，這里提示了Λ結(jié)構(gòu)信息將被漸進(jìn)的傳播到未知區(qū)域（Ω＼Λ）。當(dāng)我們給定殘缺指紋的有效區(qū)域Λ來恢復(fù)f在區(qū)域（Ω＼Λ），Ω為完整指紋，定義投影算子：

考慮一種指紋模型時，希望使用更少的參數(shù)來表示整個方向場，即信號的主要成分集中在稀疏的點集上。因此在最小二乘法問題中考慮加入l1正則項：

當(dāng)小波基為haar小波時，小波變換與梯度算子類似，在文獻(xiàn)[1]對上式與非參數(shù)模型（9）正則化效果相關(guān)。為了結(jié)合參數(shù)模型和非參數(shù)模型，令Wu=v，基于分解的方法（17）可以變換到基于合成的方法。

上式被稱作基于合成的方法，WT為小波反變換，v為未知方向場的小波系數(shù)。它結(jié)合了基于參數(shù)模型和非參數(shù)模型的優(yōu)點，同時對小波不同尺度的系數(shù)進(jìn)行約束，使得方向場盡可能的平滑，甚至填充到指紋方向場未知區(qū)域。（18）式當(dāng)D=I時，為線性反變換問題的l1正則化問題，解決辦法為迭代收縮閾值算法，文獻(xiàn)[4]對這一算法進(jìn)行了詳細(xì)的證明與改進(jìn)。本文考慮其在指紋質(zhì)量權(quán)值D的情況下對指紋方向場重建的應(yīng)用。式（18）的解決方法為分別對fc和fs進(jìn)行正則化：

上式中 為軟閾值， ，λ在不同的小波分解層為不同的值本文定義為λj=2j*λ0。▽p（v）為

在上式計算過程中需對WTvc和WTvs進(jìn)行歸一化。

3 實驗結(jié)果比較分析

為了驗證和分析所提出的指紋方向場重建的準(zhǔn)確性，主要從基于小波的方向場模型和其他模型進(jìn)行對比。主要考慮文獻(xiàn)[15]和基于小波模型分別在指紋擬合和指紋方向場修復(fù)問題中的對比。首先通過對指紋預(yù)處理得到一個可靠地指紋質(zhì)量圖并分為5層，提取最高指紋質(zhì)量層的指紋區(qū)域并通過腐蝕操作來模擬殘缺指紋，這樣就可以使模擬的殘缺指紋對應(yīng)到原始全部指紋的任意位置。

當(dāng)有指紋很大部分區(qū)域的為噪聲時，模型的恢復(fù)能力受到限制，所以實驗主要對比在指紋方向場大區(qū)域重建的準(zhǔn)確性，如圖1所示。指紋圖像來自于FVC。圖1a中圖像質(zhì)量明顯較差，此圖由梯度法得不到完整的方向場；圖1b為指紋質(zhì)量分?jǐn)?shù)較高的部分；圖1c為對應(yīng)區(qū)域的局部方向場，區(qū)域由PΛ對應(yīng)；圖1d是文獻(xiàn)[15]提出的平滑拓展方法對局部方向場重建的結(jié)果，重建采用FOMFE模型；圖1e采用基于小波模型的本文方法。從圖1可以看出本文提出的方法對于低質(zhì)量指紋方向場重建更加平滑，符合指紋方向場類似流體的性質(zhì)，其中參數(shù)λ0=0.02～0.06；t=1，采用DB4小波。另外一個指紋重建的難點在于奇異點區(qū)域的重建，奇異點區(qū)域重建的效果體現(xiàn)出模型算法的適應(yīng)性。圖2為在指紋奇異點區(qū)域的重建效果對比圖。圖2a為完整的指紋圖形，隨機(jī)選自FVC2000，DB1_B，256x320像素。圖2b為去掉指紋的奇異點區(qū)域和一些相鄰區(qū)域?qū)?yīng)的指紋塊；圖2c為指紋局部方向場，模擬殘缺的指紋方向場；圖2d為文獻(xiàn)[15]的重建效果圖；圖2e為本文的重建效果圖。

4 結(jié)論

提出了一種基于小波的指紋方向場模型，一個重要的特點就是它能擬合方向場在不同的小波尺度，多尺度分析可解決指紋奇異點區(qū)域重建的難點。另外為了重建方向場，提出結(jié)合參數(shù)模型和非參數(shù)模型的特點，在基于模型的優(yōu)化算法中加入正則項，使得重建的方向場既有基于模型的擬合精度，又有非參數(shù)模型的平滑效果。我們描述的重建方法在指紋大區(qū)域噪聲的情形下，重建效果相對較好。我們的統(tǒng)計實驗結(jié)果表明提出的方法能有效的提高指紋方向場重建的效果，在奇異點區(qū)域的重建效果也有明顯提高。

[參考文獻(xiàn)]

[1]Cai J F，Dong B，Osher S，et al.Image restoration：Total variation，wavelet frames，and beyond[J].Journal of the American Mathematical Society，2012，25（4）：1033-1089.

[2]Ross A，Shah J，Jain A K.From template to image： Reconstructing fingerprints from minutiae points[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2007， 29（4）： 544-560.

[3]Cappelli R，Lumini A，Maio D，et al.Fingerprint image reconstruction from standard templates[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2007，29（9）： 1489-1503.

[4]A. Beck and M.Teboulle，A fast iterative shrinkage-thresholding algorithm for linear inverse problems，SIAM Journal on Imaging Sciences 2 （2009），no.1，183–202.

[5]Jain A K，F(xiàn)eng J.Latent fingerprint matching[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2011， 33（1）：88-100.

[6]Hou Z，Yau W Y，Wang Y.A review on fingerprint orientation estimation[J].Security and Communication Networks，2011，4（5）： 591-599.

[7]Hong L.，Wan Y.，Jain A.K.Fingerprint image enhancement： algorithm and Performance evaluation[J].IEEETransactions on Pattern Analysis and Machine Intelligence，1998，20（8）：777-789

[8]Wang Y，Hu J，Phillips D.A fingerprint orientation model based on 2d Fourier expansion （FOMFE） and its application to singular point detection and fingerprint indexing. IEEE Transactions on Pattern Analysis and Machine Intelligence 2007；29：573--585.

[9]Ram S，Bischof H，Birchbauer J.Curvature preserving fingerprint ridge orientation smoothing using legendre polynomials[C]//Computer Vision and Pattern Recognition Workshops，2008.CVPRW'08. IEEE Computer Society Conference on.IEEE，2008：1-8.

[10]Liu M，Yap P T.Invariant representation of orientation fields for fingerprint indexing[J].Pattern Recognition，2012， 45（7）：2532-2542.

[11]Cappelli R，Maltoni D，Turroni F.Benchmarking local orientation extraction in fingerprint recognition[C]//Pattern Recognition （ICPR），2010 20th International Conference on. IEEE， 2010：1144-1147.

[12]Tao X，Yang X，Cao K，et al.Estimation of fingerprint orientation field by weighted 2D fourier expansion model[C]//Pattern Recognition （ICPR），2010 20th International Conference on.IEEE，2010：1253-1256.

[13]Jirachaweng S，Hou Z，Li J，et al.Residual Analysis for Fingerprint Orientation Modeling[C]//Pattern Recognition （ICPR），2010 20th International Conference on.IEEE，2010：1196-1199.

[14]Hou Z，Lam H K，Yau W Y，et al.A variational formulation for fingerprint orientation modeling[J].Pattern Recognition， 2012，45（5）：1915-1926.

[15]Wang Y，Hu J.Global ridge orientation modeling for partial fingerprint identification[J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，2011，33（1）：72-87.