我正在处理一个有趣的问题。
我有使用 John Daugman's algorithm 的生物识别系统将人类虹膜转换为二进制代码(用于我们大学的一些研究)。
虹膜编码是“扁平”的(不是存储为圆形，而是转化为矩形):
column 1 | column 2 | column 3 | ...
10011001 ...
10110111
01100010
...
其中列代表 30 位。问题是虹膜的每次扫描都有自己的噪声掩码(眼睑、反射...)并且匹配不是 100%，但最多在 96-98% 左右。
到目前为止，我们正在使用这样的算法(汉明距离匹配):
mask = mask1 & mask2;
result = (code1 ^ code2) & mask;
// ration of 1 bits allowed by mask
double difference = (double)one_bits(result)/one_bits(mask);
问题是我们现在正在构建真正的虹膜数据库(大约 1200-1300 个受试者，每个 3-5 个虹膜样本，你必须轮流计数，所以你需要为每个样本进行大约 10 次测试)。我们需要将当前样本与整个数据库进行比较(在 80*30 位上进行 65 000 次比较)，结果很慢。
问题:是否有反射(reflect)数据结构的哈希函数(并且当很少的位改变时只改变一点点)或者是“容错”的？我们需要在整个数据库中构建快速搜索算法(因此我们正在寻找可能的索引方法)。
更新:我想它应该通过某种“最近邻”查找来实现，或者使用某种聚类(其中相似的虹膜将被分组，并且在第一轮中只有一些代表会被检查)。
最佳答案
"A nilsimsa code is something like a hash, but unlike hashes, a small change in the message results in a small change in the nilsimsa code. Such a function is called a locality-sensitive hash."
关于数据库索引和查找与 "closest neighbour"不完全匹配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12825011/