基于三維凸包的指紋匹配識別方案研究

馬遠征

摘 要：文章在基本指紋加密的基礎上，加上三維凸包思想，在理論上將指紋加密三維進行立體化匹配。在加鎖時進行指紋三維凸包的構造，解鎖時進行指紋三維凸包的匹配。簡單介紹了三維指紋的提取辦法，及三維凸包的構造，通過引進三維凸包匹配思想，為指紋加密識別提供新的思路。

關鍵詞：網絡安全；三維凸包；指紋加密

1 指紋加密發展

人類和指紋識別的淵源要從公元前7000年開始，當時的古敘利亞人和古中國人就開始把指紋印在陶器上，方便辨識和認取。直到十九世紀末，很多國家開始將指紋加密用于偵破案件，這也是現代指紋加密技術的雛形。再后來，伴隨著計算機的出現，指紋加密技術又開始通過計算機進行運用，效率和準確度都有了前所未有的提升。指紋加密技術雖然已經有很長的歷史，擁有了完善的技術，但還是存在著改善的空間和可能

1.1 目前指紋加密技術存在的問題

目前的2D指紋加密系統，大約有5%的人無法有效地錄入指紋，或者注冊困難，就是我們通常所說的“指紋丟失族”，這部分人因為個人原因沒法進行指紋加密識別，還有很多時候，因為指壓力度不均，直接導致了識別處的誤差，因為手指表面變形或者污痕等人為因素，而出現不必要的誤差，這顯然是亟需解決的問題。

因此3D指紋技術應運而生，傳統的2D指紋技術主要是利用光的反射成像原理進行加密和識別，受到很多外界因素的干擾和局限，其中包括潮濕度，干凈程度，指紋過淺等問題，3D指紋技術很好地規避了這些問題，目前的3D技術主要采用的是晶體傳感的原理，通過采集3D指紋的指定特征點位進行匹配判斷。但是經過常規3D的劃分、強化、二值化、精密化、類型抽象后最終提取指紋的關鍵特征點，然后將特征點與樣本進行特征匹配，這個過程比較復雜和繁瑣，目前無法保證很高的準確率，因此文章提出了將三維凸包匹配結合進3D指紋的匹配，可以對今后的改進方向有一定的提示幫助作用。

1.2 指紋特征提取的方法

圖1是指紋的特征。對指紋模板進行圖形的預處理，將指紋中的特征性細節點通過一定的方式提取完畢之后，進行分類和匹配，提取的關鍵特征點主要有：模式區、核心點、三角點、終結點、分叉點、分歧點、孤立點、環點、短紋。

圖1 指紋的特征

1.3 目前三維指紋提取的方法

這種方法的原理是利用正弦光柵投影[1]，用規范公式化為：

s（a，b）=k+tcos（2πah0） （1）

這是基本的將光柵投影到立體指紋上之后，受到立體指紋的全方位變換（k為底色光柵覆蓋，t為投影光柵匹配性，a，b為向量基準，h0為載頻），光柵投影造成的局部性變化，被轉換為平面的紋理變換，用公式為：

s（a，b）=k+tcos[2πah0+k1（a，b）] （2）

其中k1（a，b）為立體指紋表面凹凸位移差造成的光柵變換，將變換之后的指紋用傅里葉變換成[2]：S（hx，hy）=Q（hx，hy）+P（hx-h0，hy）+P*（hx+h0，hy） （3）

Q（hx，hy）是震蕩為0時的情況，P（hx-h0，hy）是凹凸情況轉換為的基帶，P*（hx+h0，hy）為匹配的情況。該方法可以達到指紋很好的過濾，使得結果更加準確[3]。

最后經過對基帶進行統一處理得到需要的指紋基帶特征，也就是完成了指紋的三維提取工作。

2 三維凸包介紹

如圖2所示，所謂的三維凸包，就是能將空間中所有點包含在內的體積最小的凸多面體，它也是以空間中現有的所有點作為頂點的凸多面體，也是包含該點集的最小凸集。

圖2 三維凸包的構造

典型的算法有：Incremental 算法，Randomized incremental算法。

Incremental 算法：該方法比較簡易，辦法是一開始根據四個不在同一平面的點建立簡單的初始化三維凸包，逐步加入后續的點，判斷后續的點用計算立方體體積的方法來判定是否在現有的三維凸包內，以此類推，直到所有的點都進入三維凸包為止[4]。

Randomized incremental算法：與Incremental 算法的區別在于，該方法是進行逐步的添加面，每添加一個點，找出新產生的面，如果從點上能看到該面，則刪除該面，反之，作為新的面添加入凸包。

此處附判斷點集是否與凸包匹配的代碼。

圖3 部分匹配代碼

3 三維凸包在指紋加密中的理論性運用

文章的方法實質上是三維指紋凸包模型（指紋庫中已有的模型）與點集（從待檢測指紋中提取）的匹配問題[5]。

第一步先將已有的指紋模板，運用光投影特征提取技術，進行三維凸包的取樣，構造一個點集較大的凸包模型，放入指紋庫中，可以在抽象出來的三維指紋上取出1000個以上的點進行凸包的構建。

第二步將現有的需要檢測的指紋進行三維取樣，取出至少100個點集進行三維凸包與點集的匹配，以此判斷是否是一個指紋源的點集[6]。

第三步將已有的三維指紋樣本進行三維凸包的構建，保留存在凸包上的頂點作為“保留點集”[7]。此做法確保剔除了局部凹面上的頂點，使得得到的點集都存在于平滑凸面上。對待測三維指紋進行三維凸包的構建，作為“待測凸包”。將“保留點集”與“待測凸包”進行匹配，假如匹配的結果是“保留點集”全部都在“待測凸包”上或者“待測凸包”外，則在數據量充分大的情況下可以確保待測指紋與指紋庫中的匹配關系成立。

以上的指紋三維凸包化方法，都是基于“三維凸包與三維凸面的關系”：假如三維凸包上的點均在三維凸面上，則可以確定三維凸面上的任何點不會出現在三維凸包外部（在三維凸包上面或者內部）[4]。

過程如圖6所示。

4 結束語

給出一種指紋加密運用三維凸包方法的理論分析：這是一種目前尚未被應用和測試的匹配方法，假如匹配的點集數目達到一定程度，匹配的結果會較為可信。三維凸包構建算法有成熟的方法高效地完成，取點過程目前也有成型的隨機取點算法進行實現，匹配過程利用的是三維凸包與三維凸面的關系進行判斷，利用構建三維凸包中判斷點是否在凸包內的原理實現，通過更多的實驗優化該方法，以及確定該方法的可行性，高效性和準確性是進一步需要完成的重點工作。

參考文獻

[1]呂岑，朱歡敏.基于結構光投影的三維指紋特征提取方法[J].科學技術與工程，2014，14（1）：39-40.

[2]雍漢華，曹益平.基于光柵調制的歸一化頻譜三維別[J].激光技術，2008，32（2）：218-221.

[3]魏永超，鄭濤.基于局部指紋曲面片的點云三維物體識別[J].計算機應用，2010，46（3）：30-32.

[4]李志，李儒瓊.一種改進的快速三維凸包生成算法及實現[J].計算機工程與科學，2011，26（1）：33-35.

[5]宋偉，王阿川.基于糾錯碼的指紋加密算法研究[J].中國安全科學學報，2009，29（5）：19-20.

[6]Masafumi Takeda1，Kazuya Nakano，Hiroyuki Suzuki，Masahiro Yamaguchi.Encrypted Sensing Based on Digital Holography for Fingerprint Images[J].Optics and Photonics Journal，2015：6-14.

[7]Yijun Yang，Jianping Yu，Peng Zhang，Shulan Wang.A Fingerprint Encryption Scheme Based on Irreversible Function and Secure Authentication[J].Computational and Mathematical Methods in Medicine，2015：10-13.