一種改進(jìn)的基于細(xì)節(jié)點(diǎn)的脊線追蹤算法

李敏敏

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

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

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

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

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

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

1 算法改進(jìn)

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

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

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

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

圖2 叉點(diǎn)連接脊線追蹤問(wèn)題Fig.2 The tracking problem of bifurcation connection ridge line

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

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

2 實(shí)驗(yàn)結(jié)果

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

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

圖4 指紋細(xì)化圖特征點(diǎn)提取情況Fig.4 Feature points extraction conditions on fingerprint thinned image

3 結(jié) 論

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

[1]張?jiān)乒?指紋后處理算法研究[D].沈陽(yáng)：沈陽(yáng)工業(yè)大學(xué)，2006.

[2]劉文星，王肇圻，母國(guó)光.紋線跟蹤及其在細(xì)化指紋后處理中的應(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]王水魚(yú)，劉武，王卓然.基于脊線跟蹤的指紋核心點(diǎn)檢測(cè)[J].計(jì)算機(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]楊小冬，寧新寶，譚臺(tái)哲.基于紋線跟蹤的指紋細(xì)節(jié)提取算法[J].計(jì)算機(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]楊小冬，寧新寶，詹小四，等.基于紋線跟蹤的指紋分類(lèi)方法[J].計(jì)算機(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]彭玲，李敏敏.一種基于細(xì)節(jié)點(diǎn)的脊線追蹤算法[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.