最快的指纹匹配方法？
我正在尝试检查大量指纹（100,000 个指纹）中是否存在/匹配指纹。依次搜索匹配项将花费更多时间。有没有更好的方法来搜索匹配？是否可以将指纹组织成二叉树结构，从而减少比较次数？如果是的话我们该怎么做？如果答案是从 Java 的角度来看的话，将会很有帮助。
编辑：
我的所有指纹都是 .gif 图像。如何将指纹图像转换为数据？
谢谢。
I am trying to check whether a fingerprint exists/matches in a huge collection of fingerprints (100,000 fingerprints). It will take more time to search for matches sequentially. is there any better way to search for match? is it possible to organize the fingerprints in a binary tree structure so that the number of comparisons can be reduced? if yes how can we do it? it would be helpful if the answers are in Java perspective.
edit:
I have all the fingerprints as .gif images. how can i convert the finger print images into data?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
1) 您需要使用小波压缩算法按照小波压缩参数的顺序对指纹进行编码:
0, -1, 2.4, 5.6.7.7, 32.-1.5, 等
2) 您需要定义匹配函数，它会找到一些相似之处，有两个选项：
-几何方法（将象限与象限进行比较，所有字段通过某种空间算法间隔在连续块中）
优点：
硬件加速（SSE）像素匹配算法，使用仿射变换将所有指纹归一化为标准基础，fe 到正方形 512x512 px
缺点：
指纹质量灵敏度高（如果搜索到的指纹的一部分完全省略）
- 拓扑方法（直线、弧线、断点的连通性、相互定位）
优点：
对角度灵敏度低指纹的位置、质量，可以使用原始图像的比例和方向；
缺点：
分析速度慢，高度依赖于分类函数的质量，
3）您需要定义某种遗传算法来训练一组已知指纹的评估函数
您的知识系统将能够通过以下方式找到指纹：给定的样本，系统不知道，但经过训练可以找到一些特定的差异/匹配，提高了成功搜索的概率，喜欢搜索时错误匹配的概率。
1) You need to use Wavelet compression algorithm to encode the fingerprint in sequence of wavelet compression parameters:
0, -1, 2.4, 5.6.7.7, 32.-1.5, e.t.c.
2) You need to define match function, which will find some similarities, there are two options:
-the geometry approach (compare qudrants to qudrants, all field are spaced in continuous blocks by some space algorithm)
Pros:
hardware accelerated (SSE) pixel matching algorithm, normalization all fingerprints to a standart basis using affine transformation, f.e. to square 512x512 px
Cons:
Hight sensitivity in fingerprint quality (if a part of searched fingerprint is omittet totally)
-the topology approach (the connectivity of lines, arcs, the breakpoints, mutual positioning each other)
Pros:
Low sensibility to angle, position, and quality of fingerprint, can use the original image scale and direction;
Cons:
Low speed of analysis, highly dependent upon quality of an classification function,
3) You need to define some sort of a genetic algorithm to train the evaluate function on a known set of fingerprints
You knowledge system will be able to find fingerprints by the given sample, not known by the system, but trained to find some particular differences/matches, raises the probability of a successful search, lovering the probability of false matches upon the search.
这不是我的专业领域（我是一名网络开发人员），但我认为你应该研究一下神经网络。我下载了一些演示代码并做了一些字符识别实验。看到我设置的神经网络如何识别我在屏幕上绘制的字符，真是令人惊奇。但在它做到这一点之前，它首先必须学习（反向传播学习）。
这是提供大纲的幻灯片：
http://www.slideshare.net/alessandrobaffa/fingerprints-recognition-using -neural-networks
最后一张幻灯片包含更多参考资料。
祝你好运！
/托马斯·卡恩
This is not my field of expertise (I'm a web developer), but I think you should look into neural networks. I downloaded some demo code once and did some experimenting with character recognition. It was amazing to see how the neural network that I had setup could recognize characters that I drew on the screen. But before it could do this, it first had to learn (backpropagation learning).
Here's a slideshow that provides an outline:
http://www.slideshare.net/alessandrobaffa/fingerprints-recognition-using-neural-networks
The last slide contains further references.
Good luck!
/Thomas Kahn
您不能只是进行某种图像比较 - 有一些特定的方法可以分析和存储已经建立的指纹信息，例如，考虑到提取/扫描的指纹的质量和存储的指纹数据的质量。
我在 Google 上搜索了
指纹编码标准，并得到了几个有趣的结果，其中生物识别百科全书提到了“各种指纹编码标准的质量”，以及 文章讨论 FBI 图像编码标准（除其他外）You can't just do some kind of image comparison - there are specific ways to analyze and store fingerprint information already established which, for example, take into account the quality of the lifted/scanned fingerprint and that of the stored fingerprint data.
I googled for
fingerprint encoding standardand came up with several interesting results, including the Encyclopedia of Biometrics which mentions "quality in various fingerprint encoding standards", and an article talking about the FBI image coding standard (among other things)我知道这个问题是 4 年前提出的，但是有很多人正在观看它，对于观众来说，我认为我的回答可能会有所帮助。
有几个问题提出：-
1）有没有办法在大规模数据库中尽可能快地搜索指纹匹配？
答：是的 - 在匹配指纹之前，您缺少一个重要的步骤。这个过程就是指纹分类，分为排它分类和连续分类。独占分类更容易实现，因为您可以识别指纹的模式（称为类别），并将其仅与数据库中属于同一类别的指纹进行比较。这是为了加快指纹匹配速度而采取的措施。
下面由 Peter kovesi 创建的链接提供了用于匹配的方向场和细节提取的代码：-
http://www.csse.uwa.edu.au/~ pk/research/matlabfns/#fingerprints
奇异点检测和方向场有助于识别类别。它可以在链接上找到。
2）如何将指纹图像转换为数据？
Ans：好的，图像是什么格式并不重要，我使用 tiff。您需要知道指纹是由脊和谷组成的。山脊由较暗的线表示。您需要应用一种称为脊线分割的方法来丢弃背景并仅提取脊线。这被存储在掩码中。
3）“现有的图像和扫描的图像不会完全相似。这是我的问题”
Ans：是否受到噪声、旋转、平移等影响。减少噪声，使用增强技术。对于旋转，请使用参考点并对齐指纹。
我知道这是一个简短的概述，但我希望它能为您指明正确的方向。祝你好运！
I know that this question was asked 4 years ago, however many individuals are viewing it and for the viewers I think my response might be helpful.
There are a few questions posed:-
1)Is there any way to search for a fingerprint matching as fast as possible for large scale databases?
Ans: Yes - Before for a matching a fingerprint, there is an important step you are missing. This process is fingerprint classification, which is broken down into exclusive classification and continuous classification. Exclusive classification is easier to implement, since you identify a pattern of the fingerprint, known as a class and compare it to only the fingerprints in the database that are of the same class. This is what done to speed up fingerprint matching.
The link created by Peter kovesi below provides code for orientation field and minutia extraction for matching:-
http://www.csse.uwa.edu.au/~pk/research/matlabfns/#fingerprints
Singular point detection and orientation fields aids in identifying classes. It can be found on the link.
2)How can one convert the finger print images into data?
Ans: Ok, it doesn't matter what format the image is, I use tiff. You need to know that fingerprints are made up of ridges and valleys. Ridges are represented by the darker line. You need to apply something called ridge segmentation to discard the background and extract only the ridges. This is stored in a mask.
3) "the existing image and the image that is scanned wont be exactly similar. that's my problem"
Ans: Is it affected by noise, rotation, translation etc. Reducing noise, use enhancement techniques. For rotation, use reference points and align fingerprints.
I know this is a brief overview, however I hope that it points your'll in the right direction. Good luck!
我无法评论完全 DIY 的最佳方法，但我确实在该领域拥有很多现场专业知识。所有大型（昂贵！）商业产品都有 2 个或更多算法来对更大的数据集进行指纹匹配。有些使用指纹类（循环、螺纹等）来进行一些预过滤，但一般来说指纹索引不太好，您必须以智能方式对其进行暴力破解。这就是多种算法发挥作用的地方。
有几类算法可以进行非常快速的指纹比较（脊形状），但很容易出错，因此它们本身不够准确，无法在合理大小的数据库上进行合理的识别。因此，这些算法通常作为第一阶段部署。如果算法有任何疑问，则会进入下一阶段。这可以是某种“中级”算法，例如光谱细节或“缓慢而准确”的算法，例如实际比较所有细节的算法。最终效果是，第二阶段通常会纠正第一阶段的大部分错误接受。唯一不可挽回的损失是第一（和第二）阶段的错误拒绝。根据应用程序领域的不同，这个值可以忽略不计或相当高。这是准确性和性能之间的权衡。在我们自己的测试环境中，我们在单个（强大的）桌面上以这种方式看到每秒超过 100,000,000 个指纹的比较速度，在大约 1 毫秒内解决了原始问题。然而，它是一个复杂、昂贵且非常专业的软件。
I can't comment on the fully-DIY best approach, but I do have a lot of field expertise in this area. All large (expensive!) commercial products have 2 or more algorithms to do fingerprint matching on larger datasets. There are some that use fingerprint classes (loop, whorl etc) to do some pre-filtering, but in general fingerprints do not index very well, you'll have to brute force it in an intelligent way. That is where the multiple algorithms come into play.
There are a few classes of algorithms that can do very fast fingerprint compares (ridge shape) but are highly susceptible to errors so are not by themselves accurate enough to do a sane identification on reasonably sized databases. So those algorithms are typically deployed as first stage. If the algorithm is in any doubt, it passes to the next stage. This could be some 'mid-class' algorithm, e.g. spectral minutiae or a 'slow&accurate' algorith, e.g. something that actually compares all minutiae. The net effect is that the secondary stages typically correct for most of the false-accepts of the first stage. The only unrecoverable loss is the false rejects in the first (and second) stage. Depending on the application domain, this can be negligible or pretty high. It's a trade-off between accuracy and performance. In our own test environment we have seen speeds over 100.000.000 fingerprints compares per second in this way on a single (beefy) desktop, solving the original problem in ~1ms. It is however a complex, expensive and very specialist piece of software.
指纹匹配，如果您想要准确性，最好使用几乎所有自动指纹匹配算法都使用的经过验证的方法来完成。
提取细节点并将其位置和其他数据存储在模板中，然后使用两个模板内细节数据的相对位置的统计分析来计算两个模板匹配程度的分数。
使用这种技术通常需要考虑诸如每次印记将手指放置在指纹扫描仪上时手指的旋转和面积的差异等因素。
生物识别算法并不完美，其性能是通过其错误接受率 (FAR) 和错误拒绝率 (FRR) 来衡量的。这两项措施彼此成反比，这意味着当您提高安全性（降低 FAR）时，FRR 也会增加。
Fingerprint matching, if you want accuracy is best done using the tried and true methods that just about all automated fingerprint matching algorithm use.
The extract minutia points and store their location and other data in a template and then use statistical analysis of relative positioning of the minutia data within two templates to calculate a score of how closely the two templates match.
Using this technique often requires taking into consideration things like differences in the rotation and area of the finger as they were placed on the fingerprint scanner for each impression.
Biometric algorithms are not perfect and there performance is measured by their False Accept Rate (FAR) and their False Reject Rate (FRR). These two measures are inversely related to each other, meaning that as you increase security (decrease FAR) you increase the FRR.