基于三维凸包的指纹匹配识别方案研究

马远征

摘 要：文章在基本指紋加密的基础上，加上三维凸包思想，在理论上将指纹加密三维进行立体化匹配。在加锁时进行指纹三维凸包的构造，解锁时进行指纹三维凸包的匹配。简单介绍了三维指纹的提取办法，及三维凸包的构造，通过引进三维凸包匹配思想，为指纹加密识别提供新的思路。

关键词：网络安全；三维凸包；指纹加密

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.