OpenCV SIFT特征转换为LSH（局部敏感哈希）

Question

OPENCV SIFT提取出来的特征维度太高，特征点数目也过多，我需要把它进行二值化，百度一波后感觉LSH可能是一个比较好的方法。但是本人在这方面纯属小白，求一份OpenCV SIFT特征转换为LSH（局部敏感哈希）的代码，最好是java的，C++的话也是可以的，不胜感激！！！
邮箱：[e-mail]

Answer 1

—算法原理是很重要，如何运用的思考过程，也是值钱的嘛---

大约是2-3年前，手头有个项目是图形检索。就是输入一张图，找出一张最近似的图片。就是现在各种APP和搜索引擎上常见的拍照之后直接搜索信息和商品的功能。两者的原理是完全一样的。我的项目规模不大，设计要求是单服务器，图库大小是10万张，检索时间不能大于2秒时间。这个设计要求，最难的地方有两点，第一，更新图库的时候如何快速刷新现有图像特征数据库。第二，则是降低匹配时间。

一般来说，图像特征匹配算法常用的有SURF和SIFT，两种取的图像特征维度是不同的。SURF是64维，SIFT则是128维。从代码的角度，64维可以理解为有个变量是数组，数组的长度是64。128维就是数组长度是128.我在项目中采取的试SURF算法。图像特征点依据参数不同，一张图会在500-1000左右游走。按最低的500来计算，10万张图的总特征点数量是5000万个。

于是最终图像检索的问题就转换成：从5000万个64维的特征点中找到和用户输入的图所包含的大约500-1000个特征点，距离最近的一组特征点，并判断这组特征点归属图库中的那些图片，命中率又是多少？

因为求的是最近距离，所以每两个点之间都要计算距离。如果算法不做优化，那么查询一次，就需要在64维坐标系中最少计算250亿次两点间距离。时间要求在2秒之内，想想都可怕。而且SURF的特征值都是浮点数。

2维算距离的公式大家都学过，(x1-x2)的平方+(y1-y2)的平方，再开方，就能得出两点之间的距离值。64维，依次类推就行。大量的数据计算过程中，有大量的平方和开方，基本上就是性能黑洞。我项目本身也只能是单服务器，试图通过提升硬件来扩容计算量，是行不通的。

所以整体项目设计最终演化成一个问题：如何降低运算量。

一切性能优化的问题，最后也是“如何降低运算量”。在这个项目中，我查询了大量资料之后，采用了一些方法来降低单次运算量，比如分组，比如降维。

降维的方法，论文库中搜索下，很多，各种方案都有。因为项目本身的要求就是要快速计算。那么对降维方法的基本要求是，第一快速运算，第二，运算必需有唯一结果。

快速运算这个要求就略过不说了。LSH的运算速度已经足够快了。运算结果唯一性是非常重要的一条要求。结果唯一，就可以进行预先运算，运算结果可以永久保存，超多方便之处。而且从运算量的角度来说，判断是否相等，也比其他的运算符要快很多。

看了不少论文之后，最终选择的降维方法是LSH，就是局部敏感哈希算法。（对算法本身有兴趣的，请自行搜索资料）。LSH代码量很小，核心也就是几行代码，改写成任何一种语言都很方便。严格来说，我选中的是Locality-Sensitive Hashing Scheme Based on p-Stable Distributions。源代码参考是LSHBOX。

实际上LSH每次全新计算结果并不唯一，好在这个算法有一套随机数可以事先生成之后固定下来。这样可以让SURF特征点，无论什么时候输入，输出结果都是一样的。最终64维的浮点数全部降维到10维，转换为整数。计算量降低了好几个量级。降低到10维是反复测试之后的结果。降太低，会有大量的高维点映射到低维数据上，最终的运算量完全没降下来，就失去了降维的意义了。

最终通过LSH，把图库中的全部特征点降维之后，再结合一些其他的办法，磕磕绊绊的把项目做完了。问最终应用结果？勉强能符合设计要求