1

我正在处理一个有趣的问题。

我有使用约翰道格曼算法将人类虹膜转换为二进制代码的生物识别系统(用于我们大学的一些研究)。

虹膜代码是“扁平的”(它不是存储为圆形,而是转换为矩形):

column 1 | column 2 | column 3 | ...

10011001 ...
10110111
01100010
...

其中 column 代表 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 次比较),结果证明这很慢。

问题:是否有任何散列函数反映数据结构(并且在少数位更改时仅更改一点)或“容错”?我们需要在整个数据库中构建快速搜索算法(因此我们正在寻找可能的方法来索引它)。

更新:我想它应该通过某种“最近邻”查找来实现,或者使用某种聚类(类似的虹膜将被分组,并且在第一轮中只检查一些代表)。

4

1 回答 1

5

检查 Locality Sensitive Hashing ( LSH ),这样的实现

“nilsimsa 代码类似于哈希,但与哈希不同,消息中的微小变化会导致 nilsimsa 代码发生微小变化。这样的函数称为局部敏感哈希。”

如何理解局部敏感哈希?

于 2012-10-31T17:53:03.937 回答