Fan_Xuan
夜的那种黑丶
2017-12-08 03:22
采纳率: 57.1%
浏览 2.3k
已采纳

OpenCV SIFT特征转换为LSH(局部敏感哈希)

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • ttbb2016789
    ttbb2016789 2017-12-08 06:34
    已采纳

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

    大约是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,把图库中的全部特征点降维之后,再结合一些其他的办法,磕磕绊绊的把项目做完了。问最终应用结果?勉强能符合设计要求

    点赞 评论
  • oQiaDao
    oQiaDao 2017-12-08 06:02

    不打算也过多,我需要把它进行二值化,百度一波后感觉LSH可能是一个比较好的方法。但是本人在这方面纯属小白,求一份OpenCV SIFT特征转换为LSH(局部敏感哈希)的代码,最好是java

    点赞 评论

相关推荐