指紋特徵快速匹配方法、裝置及其應用的製作方法

2023-10-10 13:20:29

專利名稱：指紋特徵快速匹配方法、裝置及其應用的製作方法
技術領域：
本發明涉及一種利用指紋的全局特徵信息(即指紋圖像的中心點)和局部細節特徵信息(即指紋脊線的分叉點和端點)實現指紋特徵快速匹配的方法，也涉及用於實現該指紋特徵快速匹配方法的裝置，還涉及到一種使用該指紋特徵快速匹配裝置進行指紋特徵匹配的智慧卡(smartcard)，屬於模式識別及智慧卡技術領域。
背景技術：
智慧卡技術被公認為是企業和政府解決身份識別和安全問題的有效技術手段。
當前，智慧卡技術已經發展到了利用生物特徵進行身份識別的階段。在與公鑰結構和JavaTM技術結合之外，智慧卡技術再與生物特徵識別技術相結合，可以實現一種最強壯的身份驗證方式。因此，作為具有最高安全性的可攜式多功能身份識別和通信媒介，採用生物特徵識別技術的智慧卡被公認為是以在線和離線方式進行可靠的個人身份認證的最佳方案。這裡所說的生物特徵識別技術是指採集、分析人體的獨特特徵，如指紋、視網膜和聲音模式等，進行身份驗證的技術。
在生物特徵識別技術中，指紋識別技術發展最早，人們在二十世紀六十年代就開始使用計算機來處理指紋。經過不斷的發展，現在指紋識別已經是比較成熟的技術，有很多相關的技術成果問世。例如公開號為CN1735908的發明專利申請就公開了一種指紋匹配設備和方法、記錄介質和能夠使用少量數據快速執行指紋匹配處理的程序。CPU檢測指紋圖像的中心點C、分叉點P1到P8和終點Q1到Q10並且通過連接與中心點C最接近的分叉點P1和分叉點附近的兩個分叉點P2和P3產生三角形W1。三角形的面積S1和三邊的長度存儲在閃速存儲器中。此外，CPU計算分叉點P1和分叉點P1附近的終點Q1的位置、分叉點P2和分叉點P2附近的終點Q3的位置和分叉點P3和分叉點P3附近的終點Q3的位置，並且在閃速存儲器中存儲這些位置作為已登記模板。當執行匹配時，CPU判斷三角形的面積和邊長以及從匹配圖像獲得的終點的位置是否與已登記模板一致。
公開號為CN1716276的發明專利申請也公開了一種指紋識別算法及系統，其特徵是有關指紋特徵信息的輸入方法以及由上述輸入方法所輸入的所登錄指紋特徵信息，由上述輸入方法輸入的指紋特徵的相關信息以及指紋信息的記憶方法；從所輸入的兩種指紋特徵的相關信息來計算兩種指紋的類似程度；運用類似程度的計算方法來計算由指紋記憶方法所記憶的登錄指紋的位置所存在的差異的概略值稱為第一位置計算方法，在修正了由上述第一位置計算方法計算出的登錄指紋的位置和輸入指紋的位置的差異之後，運用上述類似程度計算方法來計算登錄指紋和輸入指紋的旋轉差異的概略值稱為第一旋轉計算方法，登錄指紋和輸入指紋的位置的差異，以及旋轉差異的概略值；運用上述第一位置以及其旋轉計算方法計算出的登錄指紋和輸入指紋位置的差異，以及旋轉差異的概略值，以及上述類似程度的計算方法，把上述指紋記憶方法所記憶的登錄指紋的位置和輸入指紋位置的差異進行比較，將其概略值確定在較小的範圍內，進行詳細地比較，稱為第二位置計算方法。運用上述第二位置計算方法來計算登錄指紋位置和輸入指紋位置的差異以及上述類似程度計算方法，運用指紋記憶方法所登錄的旋轉和輸入指紋旋轉的差異匹配其概略值，同上述第一旋轉計算方法進行比較，將其確定在較小的範圍之內，進行詳細的比較，稱為第二旋轉位置計算方法；運用第二位置計算方法，第二旋轉位置計算方法計算所登錄的指紋位置和輸入指紋的位置以及旋轉位置的差異進行修正，再運用上述類似程度的計算方法計算類似程度，依據其結果來判斷登錄的指紋和所輸入的指紋是否為同一人；將上述判斷結果進行輸出。
從技術角度分析，指紋識別是典型的模式識別問題，主要是由指紋的特徵提取和特徵匹配兩大部分組成的。目前，指紋識別比對算法大多數採用細節比對方法，主要分為兩大類有中心點比對算法和無中心點比對算法。無中心點比對算法是藉助細節的某些冗餘特徵輔助匹配，匹配過程中不需要中心點。它的優點是對採集的指紋圖像的定位要求不高，但比對效率低下，不適應對時間要求較高的場合，更不適合於在計算資源和計算能力均有限的智慧卡內進行。有中心點比對算法是藉助中心點輔助定位指紋圖像並進行匹配，它的優點是比對的速度非常快，但缺點是對中心點定位的精度要求比較高，如果中心點定位的精度不夠準確的話，常常導致比對失敗。
在智慧卡中使用指紋特徵識別技術，必須充分考慮到智慧卡本身的特點。與計算機相比，智慧卡內的存儲空間有限，因此指紋的特徵數據不可能太多；另外，智慧卡內處理器的運算能力往往有限，因此指紋特徵匹配算法必須簡單而高效，能夠快速判斷指紋是否匹配。但是，現有的指紋匹配算法往往忽視智慧卡的上述特點所帶來的限制，因此在計算機中使用效果良好的算法，在智慧卡中就不未必能得到令人滿意的效果。目前，就本申請人所知，專門針對智慧卡的特點進行優化的指紋匹配算法尚不多見。

發明內容
本發明的第一個目的是提供一種針對智慧卡運算和存儲能力有限的特點而專門進行優化的指紋特徵快速匹配方法。該方法利用指紋的全局特徵和細節特徵，可以快速、準確地進行指紋特徵匹配。
本發明的第二個目的是提供一種用於實現該指紋特徵快速匹配方法的裝置。
本發明的第三個目的是提供一種使用上述指紋特徵快速匹配裝置進行指紋特徵匹配的智慧卡。
為實現上述的發明目的，本發明採用下述的技術方案一種指紋特徵快速匹配方法，其特徵在於包含如下步驟(1)檢測指紋圖像的中心點；(2)如果找到中心點，則以指紋圖像的中心點為參考對應點進行細節特徵匹配；如果找不到中心點，則轉入步驟(9)；(3)匹配是否成功？(4)如果匹配成功則判斷為是同一指紋，如果不成功則以所述中心點為參考中心，在模板和輸入特徵點集合中尋找可以作為匹配參考對應點的細節特徵點對，並將它們記錄下來；(5)以記錄下的細節特徵點對作為參考對應點，對指紋的細節特徵進行匹配；(6)匹配是否成功？(7)如果匹配成功則判斷為是同一指紋，如果不成功則轉入步驟(9)；(9)將前述步驟中未使用的模板和輸入細節點對作為參考對應點，進行細節點匹配；(10)匹配是否成功？(11)如果匹配成功則判斷為是同一指紋，如果不成功則判斷為非同一指紋。
其中，所述步驟(1)中，所述中心點通過如下步驟W確定W1)將輸入指紋圖像分成大小為W×W的塊，其中，W為整數；W2)計算每個塊中每個像素的梯度Gx和Gy；W3)計算每一塊的局部主方向；W4)將方向場轉化到一個連續的向量場中，通過低通濾波器修正脊線方向；W5)計算指紋圖像的方向場；W6)計算某一點的Poincare索引，如果該點的Poincare索引值為1/2，則該點為中心點。
候選中心點為數個時，通過k-均值聚類算法得到最終的中心點位置。
在確定中心點所在區塊後，對該區塊進一步劃分為更小的區塊，並使用如步驟W所述方法重新計算中心點的位置。
所述細節特徵匹配分為兩步進行，首先是利用一對參考點在特徵點集合中的局部鄰域結構信息來進行局部結構信息粗匹配，在粗匹配通過之後，以該參考點作為對應點進行全局精確匹配。
所述細節特徵匹配計算在極坐標系下進行。
所述細節特徵匹配方法分為如下步驟1)以模板細節點和輸入細節點作為參考細節點，將輸入點集和模板點集中的鄰域細節點或全局細節點變換到極坐標系；2)將極坐標中的模板細節點和輸入細節點按極角遞增方向排序，並連接成串；3)用自適應限界盒方法匹配所述串，找出並記錄匹配分數，將匹配分數的大小作為是否進行全局精確或匹配成功與否的依據；4)找出各次匹配分數中的最大值，把它當作輸入細節點集與模板細節點集的匹配分數，如果匹配分數高於一個預先設定的閾值，則認為輸入圖像與模板圖像來自同一個指紋，否則認為它們來自不同指紋。
所述自適應限界盒的大小用radius_size和angle_size來表示，用如下式來計算極半徑為r的模板細節點的radius_size和angle_sizeradius_size=r_smallifr_sizer_smallr_sizeifr_smallr_sizer_larger_largeifr_sizer_large]]>r_size＝α1+β1rangle_size=a_smallifa_sizea_smalla_sizeifa_smalla_sizea_largea_largeifa_sizea_large]]>α_size＝α2-β2r其中α1，β1，α2，β2為預先設定的經驗參數，且均大於零，r是模板細節點的極半徑，r_small，r_large，a_small，a_large分別是radius_size和angle_size的上界和下界，它們是預先通過試驗設定的值。
所述匹配分數Ms通過下式獲得Ms=100nb_pair*nb_pairMc*Nc+*nb_pair-*match_error]]>其中nb_pair為匹配上的細節點對的數目，match_error為各匹配點對的累積匹配誤差，Mc，Nc分別是模板和輸入指紋圖像在公共區域的特徵點個數，α，β為預定的加權係數。
其中，所述α的值為2，β的值為3。
一種指紋特徵快速匹配裝置，其特徵在於包括中心點判斷單元，用於尋找和判斷指紋中的中心點；匹配對應點選擇單元，用於在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對，並將它們記錄到起來；匹配判斷單元，用於執行特徵點的匹配計算；極坐標轉換單元，用於將有關特徵點與中心點的空間位置轉換為極坐標；首先由中心點判斷單元尋找和判斷指紋中的中心點，若存在中心點，則以該中心點為對應點，由匹配判斷單元進行匹配計算，得出匹配結果；如果中心點未能找到，則由匹配對應點選擇單元和匹配判斷單元將其他未考慮的模板和輸入細節點對作為參考對應點對兩枚指紋進行細節點匹配，得出匹配結果；如果中心點進行匹配計算的結果是不匹配，則由匹配對應點選擇單元以所述兩個中心點為參考，在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對，以這些特徵點對作為匹配算法的參考對應點，由匹配判斷單元對模板和輸入細節點進行特徵點匹配，得出匹配結果。
所述匹配判斷單元進行匹配計算之前，由極坐標轉換單元將有關中心點和特徵點的空間位置轉換為極坐標。
一種智慧卡，具有微處理器、存儲器、通信電路，其特徵在於所述智慧卡中還具有上述的指紋特徵快速匹配裝置。
一種使用上述的智慧卡進行身份認證的方法，用戶通過讀卡器上的指紋採集設備輸入其指紋，指紋傳感器採集到指紋數據後，提交給特徵提取模塊，並把指紋特徵傳遞到所述智慧卡；所述智慧卡對輸入的指紋特徵與保存的指紋特徵進行匹配，若匹配成功，則完成身份認證，其特徵在於所述智慧卡採用上述的指紋特徵快速匹配方法進行指紋特徵匹配。
本發明所提供的指紋特徵快速匹配方法具有如下的優點(1)由於特徵比對過程在中心點信息的指導下進行，從而可以快速地確定兩枚指紋圖像之間的旋轉和平移變換關係，因此克服了無中心點匹配算法效率低下的缺點；(2)在利用指定參考點對對兩枚指紋的細節特徵進行比對時，採用了先進行局部鄰域粗匹配，再進行全局精確匹配的方法，大大加快了指紋比對的速度；(3)由於在匹配分數的計算上，考慮了細節特徵點匹配誤差對匹配結果的影響，從而得到可以更為精確匹配結果。
採用上述指紋特徵快速匹配方法的智慧卡可以進一步提高其安全可靠性和使用方便性，從而為生物特徵識別技術和智慧卡應用技術的融合提供了一種可行的途徑。


下面結合附圖和具體實施方式
對本發明作進一步的說明。
圖1是閉曲線的離散表示示意圖。
圖2顯示的是求奇異點方向的表格。
圖3是局部特徵向量示意圖。
圖4顯示了可變大小的限界盒的一個示例。
圖5是本發明所提供的指紋特徵快速匹配方法的基本流程圖。
圖6是一個典型的智慧卡的邏輯結構圖。
圖7介紹了內置指紋特徵快速匹配裝置的智慧卡進行指紋特徵匹配的典型過程。
具體實施例方式
為便於理解，下面首先集中介紹本發明所提供的指紋特徵快速匹配方法的具體實施方式
及實施裝置，再具體介紹該方法在智慧卡中的應用。
本指紋特徵快速匹配方法主要包括以下幾方面的技術內容指紋圖像中心點檢測，指紋圖像配準，基於局部結構信息的細節粗匹配，基於全局結構信息的細節精確匹配，基於奇異點信息的特徵匹配和匹配分數計算。下面對其逐一加以介紹。
1.指紋圖像中心點檢測中心點的計算是以方向場為基礎的，為了準確的得到指紋圖像的方向場，採用如下步驟1)將輸入指紋圖像分成大小為W×W的塊。其中，W為整數；2)計算每個塊中每個像素的梯度Gx和Gy；3)計算每一塊的局部主方向
(i,j)=12tan-1(u=i-W/2i+W/2v=j-W/2j+W/22Gx(u,v)Gy(u,v)u=i-W/2i+W/2v=j-W/2j+W/2(Gx2(u,v)-Gy2(u,v)))---(1)]]>其中Gx和Gy分別是x和y方向上的梯度，W是用來估計方向場的塊的寬度，θ(i，j)是點(i，j)所在塊的主方向。
4)由於噪聲、斷裂的脊線和谷線的存在，估計的脊線方向θ(i，j)可能不是總正確。在沒有奇異點的鄰域內，局部脊線方向是緩慢變化的，可以用一個低通濾波器來修改不正確的脊線方向。為了做這件事情，方向場需要轉化到一個連續的向量場中φx(i，j)＝cos(2φ(i，j)) (2)φy(i，j)＝sin(2φ(i，j)) (3)φx，φy是向量場的x，y分量，低通濾波可以如下表示x(i,j)=u=-w/2w/2v=-w/2wh(u,v)x(i-uw,j-vw)---(4)]]>y(i,j)=u=-w/2w/2v=-w/2wh(u,v)y(i-uw,j-vw)---(5)]]>其中h是一個二維低通濾波器，其積分為1，wφ×wφ是濾波器的大小。這個平滑操作是在塊上執行的。其預設大小為5×5。
5)計算在(i，j)處的局部方向場O(i,j)=12tan-1(y(i,j)x(i,j))---(6)]]>這樣我們就得到了指紋圖像的方向場。
6)奇異點的計算設O是指紋圖像的方向場，點(i，j)處的Poincare索引的如下計算
Poincare(i,j)=12k=0N(k)---(7)]]>(k)=(k),if|(k)|2+(k),if(k)-2-(k),otherwise---(8)]]>δ(k)＝O(ψx(i′)，ψy(i′))-O(ψx(i)，ψy(i))(9)i′＝(i+1)modNψ(10)其中ψx(i)和ψy(i)分別是以給定點為中心的具有Nψ個像素的封閉曲線上第i個點的x和y坐標．如果Poincare索引值為1/2，那麼該給定點(i，j)就被確定為中心點。
在本發明中，閉曲線是在一個5×5方格中取。如圖1所示，則在曲線D1D2...D12D1上其Poincare索引的值如下Poincare(i,j)=i=112|Di-D(i+1)mod12|---(11)]]>這樣得到相鄰的幾個候選中心點，用k-均值聚類算法可以得到最終的中心點位置。
在一些指紋圖像中，由於噪聲等因素的影響，可能存在偽中心點。為了消除偽中心點，還計算了同一點的裡面曲線d1d2...d8d1的Poincare值。只有當在3×3和5×5的Poincare值(1/2)相同的時候，這個候選中心點才作為真正的中心點。
對每一個中心點，確定其方向如下在5×5的方向場中，計算八個方向(即圖2中的0、1…7)上的方向相互之間的差值的和，最小的方向就為中心點的方向，如圖2所示。在計算過程中，可能會有兩個方向的和是一樣的，此時可以取這兩個方向的平均值作為中心點的方向。
指紋圖像的中心點為指紋細節特徵點的匹配提供了可供利用的信息，但這與中心點檢測的精確度有關。上面給出的中心點檢測方法，得到的只能是基於分塊的中心點位置，若要利用這些中心點位置作為兩枚指紋的對應點，精度顯然是不夠的．為了得到更為精確的中心點位置，還需要一個中心點位置的精確定位過程，即在上述位置的局部鄰域以更小的分塊尺寸重新計算中心點的位置。由於這種計算在很小的圖像範圍內進行，因此速度可以很快。
2.指紋圖像配準對於待匹配的模板指紋和輸入指紋，我們得到的只是從指紋圖像中檢測到的細節點和中心點的坐標位置，方向和類型信息。由於事先不知道這兩幅指紋間的對應關係，首先要找到合適的變換將它們對應起來，這個過程就是指紋的配準。我們使用一對特徵點(一個來自於模板指紋，一個來自於輸入指紋)作為參考點，利用它們之間的坐標平移和方向旋轉關係來構造相似變換，將輸入指紋特徵點變換到模板指紋特徵點的坐標空間中。由於指紋圖像的非線性形變往往呈放射狀，在某個區域內的形變比較大，然後非線性地向外擴張，因而，在極坐標中能更好地描述非線性形變。另外，在極坐標系中，我們不需要考慮輸入圖像與模板圖像的參考點之間的平移，因為輸入圖像與模板圖像間的平移是固定的，也就是說另外一對對應點之間的平移與參照點之間的平移是一樣的，這樣，將另外一對對應點的坐標相對於參照點轉換為極坐標時，平移就被抵消掉了，而且，在極坐標系中顯然比在直角坐標系中更便於處理兩幅圖像間的旋轉。綜合上述原因，本發明將在極坐標系中進行細節匹配。
即使輸入指紋與模板指紋來自同一個手指，它們之間還是會有像平移，旋轉，尺度變化這樣的形變。在對兩幅圖像進行匹配之前先要估計它們之間的形變參數，並以此對這兩幅圖像進行校準。由於兩幅指紋圖像通常是用同一個儀器採集的，可以假定它們間的尺度變化係數為1。另外，在極坐標中可以不考慮兩幅圖像間的平移。因而需要作出估計的僅有輸入圖像與模板圖像間的旋轉參數。
令P=((x1p,y1p,1p)T,......,(xMp,yMp,Mp)T)---(12)]]>表示模板指紋中的M個細節點，Q=((x1q,y1p,1q)T,......,(xNq,yNq,Nq)T)---(13)]]>
表示輸入指紋中的N個細節點。
為了把細節點轉換到極坐標系中去，我們要在模板細節點集和輸入細節點集中各選一個參照點作為相應的極坐標系中的原點，並算出其它細節點相對於參照點的極坐標。若兩枚指紋中都存在中心點，則先以中心點作為參考點對；若有一枚或兩枚指紋都沒有中心點，則無法知道模板細節點集與輸入細節點集的對應關係，此時將考慮所有可能的參考點對。
對模板點集中的每一點Pi(1≤i≤M)和輸入點集中的每一點Qj(1≤j≤N)，如果它們是相同類型的細節點，則計算它們之間的歐氏距離和Pi方向相對於Qj方向的旋轉角度rotate[i][j]。若這兩者滿足一定的閾值條件(如距離不超過80，角度差不超過45)，則將它們作為一對參考點進行接下來的粗匹配和精確匹配過程。否則，接著考察其它可能的參考點對。
要在極坐標系中將輸入圖像與模板圖像校準，只需將其它所有輸入細節點與模板細節點都分別相對於參照點Pi和Qj轉換到極坐標系中，然後在所有輸入細節點的極角上加一個角度rotate[i][j]。也就是說，將輸入細節點與模板細節點都分別相對於參照點Pi和Qj用下式轉換到極坐標系中rieii=(xi-xr)2+(yi-yr)2tan-1(yi-yrxi-xr)i-r---(14)]]>其中(xi，yi，θi)T是待轉換細節點的坐標，(xr，yr，θr)T是參考細節點的坐標，(ri，ei，θi)T是細節點在極坐標中的表示(ri表示極半徑，ei表示極角，θi表示細節點方向與參考細節點方向之間的夾角)。然後，我們對每一個輸入細節點的ei加一個角度rotate[i][j]。
3.基於局部結構信息的細節粗匹配對於給定的一對參考點，先利用它們在特徵點集合中的局部鄰域結構信息來判斷它們是否可以作為真正的對應點來進行全局精確匹配。只有通過了局部結構信息粗匹配的參考點對，才利用它們作為對應點進行真正的全局精確匹配，這樣就大大降低了細節點匹配的計算量，同時提高了匹配算法的精度和運算的效率。
對於某一特徵點Pk＝(xk，yk，k，)T，利用離它最近的另外m個特徵點(m一般取值為6～9)和它自己建立特徵向量，把這個特徵向量作為局部結構信息，這個局部特徵是旋轉平移不變的。圖3示意了m＝2的情形，其特徵向量描述如下Flk＝((dki，θki，ki)T，(dkj，θkj，kj)T)(15)dki=(xk-xi)2+(yk-yi)2]]> ki＝d(k，i) (16)其中 其中，dki是兩個特徵點之間的距離，θki是特徵點Pk、Pi連線方向與特徵點Pk方向之間的夾角，ki是兩個特徵點方向的夾角。以上計算過程實質上是以特徵點Pk為原點進行的極坐標變換。
對於任意兩個參考特徵點，計算出它們各自的局部特徵向量後，利用下述的點匹配算法確定鄰域細節點的匹配情況。如果鄰域匹配細節點數超過一定的閾值，則利用它們作為對應點進行全局精確匹配，否則，繼續考察其它的參考點對。
4.基於全局結構信息的細節點精確匹配在某一參考點對Pb(b＝b1，b2)通過了鄰域結構信息的粗匹配後，再利用這兩個特徵點作為進一步進行全局匹配的對應參考點，將圖像上除最近鄰點外的其它特徵點Pk相對於對應點Pb進行坐標變換 Fgk表示特徵點Pk相對於對應點Pb進行極坐標變換後得到的向量。所有的Fgk和已經計算得到的Pb的局部特徵向量一起構成全局特徵向量。利用下述的細節點匹配算法對全局特徵向量進行匹配從而得到全局匹配結果。
5.細節點的匹配在上述的局部結構信息粗匹配和全局信息的精確匹配過程中，都涉及到極坐標系中的細節點特徵向量的匹配問題。本發明中的細節點匹配算法如下1)以模板細節點Pi和輸入細節點Qj作為參考細節點，利用上面介紹的方法將輸入點集和模板點集中的鄰域細節點或全局細節點變換到極坐標系；2)將極坐標中的模板細節點和輸入細節點按極角遞增方向排序，並連接成串，表示如下 其中M，N分別為模板和輸入特徵向量中的細節點數目；3)用後面將要介紹的自適應限界盒方法匹配串Pis和Qjs，找出並記錄匹配分數，將匹配分數的大小作為是否進行全局精確或匹配成功與否的依據；4)找出各次匹配分數中的最大值，把它當作輸入細節點集與模板細節點集的匹配分數。如果匹配分數高於一個預先設定的閾值，則認為輸入圖像與模板圖像來自同一個指紋，否則認為它們來自不同指紋。
自適應限界盒及其大小如圖4所示，一個限界盒是放在模板細節點上的一個盒子。限界盒的大小用radius_size和angle_size來表示，它們的值將隨著細節點的極半徑大小而改變。用下式來計算極半徑為r的模板細節點的radius_size和angle_size。
radius_size=r_smallifr_sizer_smallr_sizeifr_smallr_sizer_larger_largeifr_sizer_large---(20)]]>r_size＝α1+β1r(21)angle_size=a_smallifa_sizea_smalla_sizeifa_smalla_sizea_largea_largeifa_sizea_large---(22)]]>α_size＝α2-β2r (23)其中α1，β1，α2，β2為預先設定的經驗參數，且均大於零。r是模板細節點的極半徑，r_small，r_large，a_small，a_large分別是radius_size和angle_size的上界和下界，它們的值也是預先通過試驗設定的。
使用自適應大小的限界盒而不是固定大小的限界盒是為了使算法對非線性形變更為魯棒。非線性形變一般在一個特定的區域內較大，然後非線性地向外擴張。當細節點的極徑較小時，小的形變就可以造成大的極角的改變，而極半徑的改變較小。所以在這種情況下限界盒的angle_size應該比較大而radius_size則應該較小。另一方面，當細節點的極半徑較大時，極角的較小改變就會造成細節點位置的較大變動，而極半徑的形變可以看成是該細節點與參考細節點間的所有區域的形變的累加。所以在這種情況下限界盒的angle_size應該比較小而radius_size則應該較大。
匹配Pis和Qjs的算法描述如下1)用(20)～(23)式決定每一個模板細節點的限界盒的大小。置nd_pair[i][j]＝0。(nd_pair[i][j]表示以模板細節點Pi和輸入細節點Qj作為參考細節點進行特徵匹配時匹配上的細節點對數)2)做如下循環While 1≤m≤M doWhile 1≤n≤N doif模板細節點m與輸入細節點n滿足conditionl，thennd_pair[i][j]＝nb_pair[i][j]+1；End ifIncrease n；End whileIncrease m；End while上述過程中，condition1定義為 其中r=rmp-rnq---(25)]]>=aif(a=(mp-nq+360)mod360)180a-180---(26)]]>
r_low[m]，r_high[m]，θ_low[m]，θ_high[m]分別為模板細節點m限界合極半徑和極角誤差的下限和上限。condition1是將模板細節點m和輸入細節點n看作匹配點對的條件。其含義是，輸入細節點n應該在模板細節點m的限界盒的內部，這兩個細節點的方向差異應小於ε(如ε＝30)。
6.匹配分數的計算在以兩個細節點(一個來自模板指紋，一個來自輸入指紋)為參考完成以上匹配過程後，假定匹配上的細節點對的數目為nb_pair，各匹配點對的累積匹配誤差為match_error。則匹配分數的計算如下Ms=100nb_pair*nb_pairMc*Nc+*nb_pair-match_error---(28)]]>其中Mc，Nc分別是模板和輸入指紋圖像在公共區域的特徵點個數，match_error為各匹配細節點對匹配誤差(包括公式(25)～(27)中的Δr，Δθ，Δ)的加權平均，α，β為預定的加權係數(其典型值分別為2.0和3.0)。將以上匹配分數與預先設定的匹配閾值進行比較，即可作出匹配與否的判斷。
7.基於中心點信息的特徵匹配經過指紋圖像中心點檢測後，指紋特徵信息包括兩部分一部分為局部細節特徵點信息，即為指紋脊線的分叉點和端點；另一部分為指紋的全局特徵信息，即為指紋的中心點。因此，有了指紋的中心點信息後，就可以提高匹配算法的運行效率。總結起來，本發明中的特徵點匹配算法如圖5所示，以如下步驟進行1)若模板指紋和輸入指紋中均有中心點，則以兩枚指紋的中心點為對應點進行特徵點匹配，其中的特徵點匹配算法如上述第5節所述；否則轉第四步；2)若以中心點為對應點進行特徵點匹配時返回匹配一致結果，則特徵匹配算法結束；否則，以上述兩個中心點為參考，在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對(將模板細節點限界合的尺寸放大，重新進行全局細節特徵點匹配即可)，並將它們記錄到集合Point Pair中；3)利用第二步中得到的各個特徵點點對作為匹配算法的參考對應點，對模板和輸入細節點進行特徵點匹配，遇到匹配一致結果則結束特徵匹配算法；4)將其他未使用過的模板和輸入細節點對作為參考對應點對兩枚指紋進行細節點匹配，遇到匹配一致結果則結束特徵匹配算法。
考慮到卡內指紋比對的響應時間，本發明所提供的方法在考慮了足夠多的參考對應點對並進行細節點匹配後，不管匹配成功與否都將返回。
上述的指紋特徵快速匹配方法主要是針對智慧卡內存儲和運算能力有限的具體環境而專門優化設計的。由於在匹配過程中充分利用中心點的指導作用，對兩枚指紋圖像進行快速配準，從而大大提高了算法的時間效率；同時，利用自適應限界合的細節點匹配方法有效克服了指紋圖像非線性形變對匹配算法精度的影響；對於給定的一對參考點，先進行局部鄰域結構信息的粗匹配，再進行全局細節信息的精確匹配，從而大大降低了細節點匹配過程的計算量，同時提高了匹配算法的精度和運算的效率。
用於實施本方法的軟體可以做成固件形式的指紋特徵快速匹配裝置，集成在智慧卡中。該指紋特徵快速匹配裝置包括中心點判斷單元，用於尋找和判斷指紋中的中心點；匹配對應點選擇單元，用於在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對，並將它們記錄到起來；匹配判斷單元，用於執行特徵點的匹配計算，極坐標轉換單元，用於將有關特徵點與中心點的空間位置轉換為極坐標。在進行指紋特徵快速匹配操作時，首先由中心點判斷單元尋找和判斷指紋中的中心點，若存在中心點，則以該中心點為對應點，由匹配判斷單元進行匹配計算，得出匹配結果；如果中心點未能找到，則由匹配對應點選擇單元和匹配判斷單元將其他未考慮的模板和輸入細節點對作為參考對應點對兩枚指紋進行細節點匹配，得出匹配結果。如果中心點進行匹配計算的結果是不匹配，則由匹配對應點選擇單元以上述兩個中心點為參考，在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對，以這些特徵點對作為匹配算法的參考對應點，由匹配判斷單元對模板和輸入細節點進行特徵點匹配，得出匹配結果。匹配判斷單元進行匹配計算之前，由極坐標轉換單元將有關中心點和特徵點的空間位置轉換為極坐標，匹配運算是基於極坐標數據進行的，這樣可以減少計算量，從而更快地獲得結果。
上述的指紋特徵快速匹配裝置主要用在智慧卡中。圖6介紹了一種典型的非接觸式智慧卡的內部邏輯結構。其中使用的微處理器晶片是MPU，具有邏輯控制、管理功能、加密解密功能等，存儲器包括ROM、RAM、EEPROM等。RFC是射頻收發電路，主要解決卡的讀寫通訊與供電，CAU是加密運算協處理器，SL是安全邏輯。當然，上述裝置用在接觸式智慧卡也是完全可以的。
不同類型的智慧卡的存儲器空間大小從512Byte至16KB不等，且有不同的分區選擇。對於實施本發明所述方法的智慧卡而言，由於需要存儲指紋特徵數據，智慧卡的容量一般應選擇1KB以上的。在本發明中，如果使用特徵點的坐標模型，僅考慮脊末梢與分叉點兩類特徵點，則一枚指紋的特徵數據加密後不超過256Byte，完全可以存儲在智慧卡的存儲區內。
對於應用本發明所述方法進行指紋特徵快速匹配的智慧卡而言，可以將上述的指紋特徵快速匹配裝置內置於智慧卡的微處理器中，也可以獨立設置。圖7介紹了內置指紋特徵快速匹配裝置的智慧卡進行指紋特徵匹配的典型過程。用戶使用帶有指紋識別的讀卡器，通過讀卡器上的指紋採集設備輸入其指紋，指紋傳感器採集到指紋數據後，提交給特徵提取模塊，提取本次指紋特徵，並把指紋特徵傳遞到智慧卡；智慧卡對輸入的指紋特徵與保存的指紋特徵進行匹配，若成功，則允許用戶進行後續的操作，如果匹配不成功，則提示用戶重新輸入指紋數據。一般連續多次不成功可以自動鎖死智慧卡。
上述方案仍然存在一個安全弱點在於，如果攻擊者通過具他途徑獲取了用戶的指紋信息，那麼只要他獲取到用戶的智慧卡後，可以把事先獲取到的指紋信息發送給智慧卡完成指紋匹配、認證過程。解決這個安全弱點的方法有兩種，一種方法是把指紋傳感器，讀卡器和智慧卡集成在一個設備，使得智慧卡只接受來自這個設備的指紋數據，這樣做成本較高。另一種方法是把讀卡器和指紋傳感器集成在一起，智慧卡和讀卡器在交換數據前進行相互認證，數據進行加密傳輸，這樣做的不足之處在於技術方案複雜。
以上所述，僅為本發明較佳的具體實施方式
，但本發明的保護範圍並不局限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到的變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應該以權利要求書的保護範圍為準。
權利要求
1.一種指紋特徵快速匹配方法，其特徵在於包含如下步驟(1)檢測指紋圖像的中心點；(2)如果找到中心點，則以指紋圖像的中心點為參考對應點進行細節特徵匹配；如果找不到中心點，則轉入步驟(9)；(3)匹配是否成功？(4)如果匹配成功則判斷為是同一指紋，如果不成功則以所述中心點為參考中心，在模板和輸入特徵點集合中尋找可以作為匹配參考對應點的細節特徵點對，並將它們記錄下來；(5)以記錄下的細節特徵點對作為參考對應點，對指紋的細節特徵進行匹配；(6)匹配是否成功？(7)如果匹配成功則判斷為是同一指紋，如果不成功則轉入步驟(9)；(9)將前述步驟中未使用的模板和輸入細節點對作為參考對應點，進行細節點匹配；(10)匹配是否成功？(11)如果匹配成功則判斷為是同一指紋，如果不成功則判斷為非同一指紋。
2.如權利要求1所述的指紋特徵快速匹配方法，其特徵在於所述步驟(1)中，所述中心點通過如下步驟確定1)將輸入指紋圖像分成大小為W×W的塊，其中，W為整數；2)計算每個塊中每個像素的梯度Gx和Gy；3)計算每一塊的局部主方向；4)將方向場轉化到一個連續的向量場中，通過低通濾波器修正脊線方向；5)計算指紋圖像的方向場；6)計算某一點的Poincare索引，如果該點的Poincare索引值為1/2，則該點為中心點。
3.如權利要求2所述的指紋特徵快速匹配方法，其特徵在於候選中心點為數個時，通過k-均值聚類算法得到最終的中心點位置。
4.如權利要求2所述的指紋特徵快速匹配方法，其特徵在於在確定中心點所在區塊後，對該區塊進一步劃分為更小的區塊，並使用如權利要求2所述方法重新計算中心點的位置。
5.如權利要求1所述的指紋特徵快速匹配方法，其特徵在於所述細節特徵匹配分為兩步進行，首先是利用一對參考點在特徵點集合中的局部鄰域結構信息來進行局部結構信息粗匹配，在粗匹配通過之後，以該參考點作為對應點進行全局精確匹配。
6.如權利要求1所述的指紋特徵快速匹配方法，其特徵在於所述細節特徵匹配計算在極坐標系下進行。
7.如權利要求5或6中任意一項所述的指紋特徵快速匹配方法，其特徵在於所述細節特徵匹配方法分為如下步驟1)以模板細節點和輸入細節點作為參考細節點，將輸入點集和模板點集中的鄰域細節點或全局細節點變換到極坐標系；2)將極坐標中的模板細節點和輸入細節點按極角遞增方向排序，並連接成串；3)用自適應限界盒方法匹配所述串，找出並記錄匹配分數，將匹配分數的大小作為是否進行全局精確或匹配成功與否的依據；4)找出各次匹配分數中的最大值，把它當作輸入細節點集與模板細節點集的匹配分數，如果匹配分數高於一個預先設定的閾值，則認為輸入圖像與模板圖像來自同一個指紋，否則認為它們來自不同指紋。
8.如權利要求7所述的指紋特徵快速匹配方法，其特徵在於所述自適應限界盒的大小用radius_size和angle_size來表示，用如下式來計算極半徑為r的模板細節點的radius_size和angle_sizeradius_size=r_smallifr_sizer_smallr_sizeifr_smallr_sizer_larger_largeifr_sizer_large]]>r_size＝α1+β1rangle_size=a_smallifa_sizea_smalla_sizeifa_smalla_sizea_largea_largeifa_sizea_large]]>a_size＝α2_β2r其中α1，β1，α2，β2為預先設定的經驗參數，且均大於零，r是模板細節點的極半徑，r_small，r_large，a_small，a_large分別是radius_size和angle_size的上界和下界，它們是預先通過試驗設定的值。
9.如權利要求7所述的指紋特徵快速匹配方法，其特徵在於所述匹配分數Ms通過下式獲得Ms=100nb_pair*nb_pairMc*Nc+*nb_pair-*match_error]]>其中nb_pair為匹配上的細節點對的數目，match_error為各匹配點對的累積匹配誤差，Mc，Nc分別是模板和輸入指紋圖像在公共區域的特徵點個數，α，β為預定的加權係數。
10.如權利要求9所述的指紋特徵快速匹配方法，其特徵在於所述α的值為2，β的值為3。
11.一種指紋特徵快速匹配裝置，其特徵在於包括中心點判斷單元，用於尋找和判斷指紋中的中心點；匹配對應點選擇單元，用於在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對，並將它們記錄到起來；匹配判斷單元，用於執行特徵點的匹配計算；極坐標轉換單元，用於將有關特徵點與中心點的空間位置轉換為極坐標；首先由中心點判斷單元尋找和判斷指紋中的中心點，若存在中心點，則以該中心點為對應點，由匹配判斷單元進行匹配計算，得出匹配結果；如果中心點未能找到，則由匹配對應點選擇單元和匹配判斷單元將其他未考慮的模板和輸入細節點對作為參考對應點對兩枚指紋進行細節點匹配，得出匹配結果；如果中心點進行匹配計算的結果是不匹配，則由匹配對應點選擇單元以所述兩個中心點為參考，在模板和輸入特徵點中尋找可能的可以作為匹配對應點的模板和輸入特徵點對，以這些特徵點對作為匹配算法的參考對應點，由匹配判斷單元對模板和輸入細節點進行特徵點匹配，得出匹配結果。
12.如權利要求11所述的指紋特徵快速匹配裝置，其特徵在於所述匹配判斷單元進行匹配計算之前，由極坐標轉換單元將有關中心點和特徵點的空間位置轉換為極坐標。
13.一種智慧卡，具有微處理器、存儲器、通信電路，其特徵在於所述智慧卡中還具有如權利要求11所述的指紋特徵快速匹配裝置。
14.一種使用如權利要求13所述的智慧卡進行身份認證的方法，用戶通過讀卡器上的指紋採集設備輸入其指紋，指紋傳感器採集到指紋數據後，提交給特徵提取模塊，並把指紋特徵傳遞到所述智慧卡；所述智慧卡對輸入的指紋特徵與保存的指紋特徵進行匹配，若匹配成功，則完成身份認證，其特徵在於所述智慧卡採用如權利要求1所述的指紋特徵快速匹配方法進行指紋特徵匹配。
全文摘要
本發明公開了一種智慧卡卡內指紋特徵快速匹配方法，也公開了用於實現該指紋特徵快速匹配方法的裝置，還公開了一種使用該指紋特徵快速匹配裝置進行指紋特徵匹配的智慧卡。本指紋特徵快速匹配方法充分利用指紋的全局特徵信息和局部細節特徵信息，可以更方便、準確、快速的判斷兩枚指紋是否匹配。本發明較傳統的指紋特徵匹配方法有較大的優勢，非常適合在智慧卡內運行。
文檔編號G06K9/00GK1831847SQ20061006587
公開日2006年9月13日 申請日期2006年3月28日 優先權日2006年3月28日
發明者汪雪林, 胡俊義, 石玉平 申請人:北京握奇數據系統有限公司