—算法原理是很重要,如何运用的思考过程,也是值钱的嘛---
大约是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,把图库中的全部特征点降维之后,再结合一些其他的办法,磕磕绊绊的把项目做完了。问最终应用结果?勉强能符合设计要求