李敏敏

（江蘇科技大學(xué) 江蘇 鎮(zhèn)江 212003）

目前基于細節(jié)點的指紋匹配算法，識別效果很大程度上取決于細節(jié)點的數(shù)量和準(zhǔn)確性，同時受指紋圖像質(zhì)量和大小等因素的影響較大，并且忽略了指紋豐富的脊線信息，極大地限制了指紋識別準(zhǔn)確性和魯棒性的提高。指紋豐富的脊線信息主要是指脊線的一些屬性，常見的有：脊線的長度、方向、頻率、脊線間的相對關(guān)系、脊線的曲率以及脊線上最大曲率點與脊線兩端點的距離比等。脊線的上述屬性幾乎不受指紋圖像平移、旋轉(zhuǎn)、縮放以及非線性變形的影響，具有一定的幾何不變性。因此，利用脊線屬性構(gòu)建指紋匹配模式可以提高指紋匹配的準(zhǔn)確性和魯棒性。

指紋脊線屬性的獲取首先需要獲得相應(yīng)的脊線數(shù)據(jù)，包括脊線的端點、脊線上每個像素點的坐標(biāo)以及這些像素點的排列順序，為此，就要進行脊線的追蹤。脊線追蹤就是從脊線的一端出發(fā)，沿著脊線的方向前進，記錄下脊線上每個像素點的坐標(biāo)，按其既定方向排列，最終到達脊線的另一端[1]。因為脊線具有豐富的指紋信息，所以已有很多學(xué)者對脊線追蹤進行了研究。

文獻[2-4]提出利用窗口判斷像素點的8鄰域紋線點數(shù)，利用指紋脊線端點、連續(xù)點和叉點的8鄰域點分布情況進行脊線像素點的判斷，從而對指紋脊線進行追蹤并記錄追蹤到的脊線數(shù)據(jù)。文獻[5]脊線追蹤時確定追蹤起始點后，在定位下一追蹤點時，采用適當(dāng)?shù)母櫜介L，以保證該點位于前一跟蹤點紋線方向的一定角度范圍內(nèi)，跟蹤過程中及時調(diào)整每一跟蹤點的角度，使得紋線跟蹤更為精確。文獻[6]將模式區(qū)分塊分別計算每塊的灰度方差并從大到小排序得到模式區(qū)圖像塊序列，依次尋找每塊的灰度值最小點作為跟蹤起始點，并采用文獻[7-8]中的紋線追蹤算法進行跟蹤并記錄。文獻[9]利用指紋脊線方向的連續(xù)性和相鄰脊線間的相關(guān)性，將要追蹤的脊線作為目標(biāo)采用計算機視覺中的目標(biāo)追蹤技術(shù)和反饋技術(shù)進行脊線追蹤，追蹤過程中通過反饋脊線的方向信息不斷對其方向進行矯正，確保脊線追蹤的準(zhǔn)確性。

由以上脊線追蹤算法可以看出，脊線追蹤的關(guān)鍵問題是如何根據(jù)已追蹤并記錄的紋線點去確定下一個紋線點。然而追蹤過程中對像素點方向性的判斷算法比較復(fù)雜，對于上面提到的較簡單的窗口的跟蹤方法雖然簡單，但由于脊線追蹤的每一個步驟都要利用窗口來獲得當(dāng)前點和上一個被跟蹤的點，并且按照已定義的規(guī)則依次搜索當(dāng)前點的8鄰域像素，從而判斷脊線上的下一個跟蹤點，因此，算法的運行速度比較慢。

我們在文獻[10]中提出以指紋端點和叉點為起點，沿著脊線的方向逐點進行跟蹤，從而遍歷指紋細化圖中所有脊線。由于文獻[10]中的脊線追蹤算法存在一定的不完善性，導(dǎo)致脊線追蹤的結(jié)果存在不完全現(xiàn)象，因此本文在文獻[10]的基礎(chǔ)上對算法進行了改進，實驗結(jié)果表明，改進后的算法對指紋細化圖具有非常理想的脊線追蹤效果。

1 算法改進

文獻[10]中脊線追蹤的算法思想：首先以提取到的細節(jié)端點為起始跟蹤點，記錄該端點位置；從該細節(jié)點開始，以其為前驅(qū)點，其鄰點為當(dāng)前點，通過一個獲取下一像素點的函數(shù)尋找脊線上下一像素點；判斷該像素點類型，如果為連續(xù)點，則更改前驅(qū)點和當(dāng)前點，即以該像素點為當(dāng)前點，原當(dāng)前點為前驅(qū)點，再通過獲取下一像素點的函數(shù)繼續(xù)搜索脊線上下一像素點，直至遇到這條脊線的另一個細節(jié)端點或叉點，則該細節(jié)點所在脊線的追蹤結(jié)束；對細節(jié)點記錄中所有端點，重復(fù)進行上面的步驟，如此反復(fù)下去，直至完成對指紋細化圖中所有端點所在脊線的追蹤；然后再以叉點為起點進行剩余脊線的追蹤，追蹤方法同上，此處需注意叉點連接3條脊線。這樣便完成了所有以端點和叉點為起點的脊線的追蹤。

文獻[10]中獲取下一個像素點的函數(shù)思想是：對當(dāng)前點的8鄰域進行判斷，如果其8鄰域內(nèi)除前驅(qū)點外只有一個黑點，則說明當(dāng)前點的下一個像素點存在，并返回下一個像素點；若沒有黑點或多于1個則認為沒找到下一像素點，并返回錯誤。該脊線追蹤算法對實例指紋圖像的脊線追蹤效果如圖1（b）所示。

圖1 指紋細化圖及脊線追蹤圖Fig.1 The fingerprint thinned image and ridge tracing image

由圖1（b）可以看出，叉點連接的脊線追蹤不完整；通過對多枚指紋圖像脊線追蹤結(jié)果觀察發(fā)現(xiàn)，文獻[10]中算法對以叉點為起點進行的脊線追蹤其結(jié)果存在不完整現(xiàn)象，不能獲得完整的脊線數(shù)據(jù)。通過對以上現(xiàn)象分析發(fā)現(xiàn)：由叉點開始脊線追蹤或脊線追蹤到叉點鄰近鄰域時有時會出現(xiàn)圖2所示的情況，圖2（a）中1號像素點的8鄰域內(nèi)除前驅(qū)點叉點外有兩個黑點，2號像素點8鄰域內(nèi)除前驅(qū)點也有兩個黑點；圖2（b）中2號像素點的8鄰域內(nèi)除前驅(qū)點外有2個黑點，此時文獻[10]中獲取下一像素點的函數(shù)就不會返回正確的像素點坐標(biāo)，從而該脊線沒有被追蹤到。因此，文中對文獻[10]中獲取下一像素點函數(shù)思想進行了改進。

圖2 叉點連接脊線追蹤問題Fig.2 The tracking problem of bifurcation connection ridge line

文中改進后的算法思想是：首先判斷前驅(qū)點的類型，如果是端點則直接判斷當(dāng)前點的8鄰域，除前驅(qū)點外，若有1個黑點則直接返回該像素點，若有2個黑點則返回與當(dāng)前點在水平或垂直方向緊挨的點，若有多個黑點則返回錯誤；如果前驅(qū)點是叉點，判斷當(dāng)前點的8鄰域時，若黑點同時是該叉點的8鄰域點則不計，除此以外判斷規(guī)則同上。算法改進后獲取下一個像素點的流程圖如圖3所示。

圖3 尋找脊線上待追蹤的下一點流程圖Fig.3 The flow chart of looking for the next point to track on the ridge

2 實驗結(jié)果

根據(jù)改進后的脊線追蹤算法進行細化指紋圖像的脊線追蹤，其結(jié)果如圖1（c）所示，從圖上可以看出改進后的脊線追蹤算法追蹤到了原脊線追蹤算法沒有追蹤完全的叉點連接脊線。通過對多枚指紋細化圖脊線追蹤的效果分析可知，改進后的脊線追蹤算法對指紋所有端點及叉點連接的脊線都能完全追蹤。

另外，由圖1可以看出，該指紋圖像只有左下角兩條脊線沒有追蹤到。經(jīng)分析可知，因為該兩條脊線位于指紋圖像的邊緣部分，其端點沒有被提取到，所以該兩條脊線沒有被追蹤到，該細化指紋圖的特征點提取情況如圖4所示。通過對大量指紋細化圖的脊線追蹤結(jié)果分析可得，本文改進的脊線追蹤算法對于提取到特征點的脊線來說都能夠追蹤到，也就是說，本文脊線追蹤算法具有很好的效果。

圖4 指紋細化圖特征點提取情況Fig.4 Feature points extraction conditions on fingerprint thinned image

3 結(jié) 論

文中對以指紋端點和叉點為起點進行脊線追蹤的算法進行了改進，通過對多枚指紋細化圖脊線追蹤的效果分析可知，改進后的脊線追蹤算法對提取到端點或叉點的脊線都能完全追蹤，說明改進后的脊線追蹤算法對指紋細化圖具有非常理想的脊線追蹤效果。本文脊線追蹤算法的提出為更好地獲得指紋信息提供了有效的手段，為提高指紋匹配的精確性和魯棒性奠定了堅實的基礎(chǔ)。由于本文脊線追蹤算法的實現(xiàn)是在指紋細化和特征點提取的情況下進行的，因此脊線追蹤的效果受指紋細化和特征點提取的影響。

[1]張云光.指紋后處理算法研究[D].沈陽：沈陽工業(yè)大學(xué)，2006.

[2]劉文星，王肇圻，母國光.紋線跟蹤及其在細化指紋后處理中的應(yīng)用[J].光電子激光，2002，13（2）：184－187.LIU Wen-xing，WANG Zhao-qi，MU Guo-guang.Ridge tracing and application in post-processing of thinned fingerprints[J].Optoelectronic Laser，2002，13（2）：184－187.

[3]RAN Chong-Jie，XIE Mei.A new figerprint matching method based on ridge tracing [C]//Proceedings of the 2007 International Conference on Wavelet Analysis and Pattern Recognition，2007：1108－1113.

[4]王水魚，劉武，王卓然.基于脊線跟蹤的指紋核心點檢測[J].計算機系統(tǒng)應(yīng)用，2011，20（6）：140－143.WANG Shui-yu，LIU Wu，WANG Zhuo-ran.Core point detection of fingerprint based on tracing ridges[J].Computer Systems&Applications，2011，20（6）：140－143.

[5]楊小冬，寧新寶，譚臺哲.基于紋線跟蹤的指紋細節(jié)提取算法[J].計算機應(yīng)用，2004，24（3）：75－78.YANG Xiao-dong，NING Xin-bao，TAN Tai-zhe.Fingerprint minutiae extraction by following its ridge[J].Computer Application，2004，24（3）：75－78.

[6]楊小冬，寧新寶，詹小四，等.基于紋線跟蹤的指紋分類方法[J].計算機工程，2005，31（7）：170－173.YANG Xiao-dong，NING Xin-bao，ZHAN Xiao-si，et al.Fingerprint classification method based on ridge-following[J].Computer Engineering，2005，31（7）：170－173.

[7]Maio D，Maltoni D.Direct gray-scale minutiae detection in fingerprints[J].IEEE Transactions on Pattern Analysis and Machine Intelligencf，1997，19（1）：27－40.

[8]JIANG Xu-dong，YA Wei-Yun，Ser W.Detecting the fingerprint minutiae by adaptive tracing the gray-level ridge[J].Pattern Recognition，2001（34）：999－1013.

[9]MA Rui，QI Ya-xuan，ZHANG Chang-shui，et al.A novel approach to fingerprint ridge line extraction[C]//Proceedings of International Symposium on Communications and Information Technology，2005：2－5.

[10]彭玲，李敏敏.一種基于細節(jié)點的脊線追蹤算法[J].科學(xué)技術(shù)與工程，2012，12（6）：1428－1430.PENG Ling，LI Min-min.A fingerprint ridge tracing algorithm based on minutiae[J].Science Technology and Engineering，2012，12（6）：1428－1430.