Lsh( Locality Sensitive Hashing)

LSH(Locality-Sensitive Hashing) #

Date: 2015/7/25

LSH可看作是一种降维的方法，将图片映射到一组不长的hash码中，以hash码代码图片的像素特征，在上面做类似KNN的相似图片查询。

LSH的一个基础结构是满足下面两个条件的hash函数：

  • 如果d(x,y)≤d1, 则h(x)=h(y)的概率至少为p1;
  • 如果d(x,y)≥d2, 则h(x)=h(y)的概率至多为p2;
    LSH称上述的hash函数为(d1,d2,p1,p2) - sensitive

由上述基本结构，可以生成LSH family，简单的说，是可以通过一定的变化，使d1, d2, p1, p2做一些定向的改变。LSH family

  • Jaccard distance： (d1,d2,1−p1,1−p2) - sensitive

  • Hamming distance： (d1,d2,1−d1/d,1−d2/d) - sensitive

  • Cosine distance： (d1,d2,(180−d1)180,(180−d2)/180) - sensitive

  • normal Euclidean distance： (a/2,2a,1/2,1/3) - sensitive

  • AND操作

  • OR操作

LSH在查找中的应用 #

目前就理解到一种方法：将样本扔到桶里去，比如生成L位的hash，那么就有了2L个桶，将待查样本转化为hash后，直接去对应桶中遍历找出前K个相似的样本即可。桶中样本可再次使用hash或别的方式查找。
使用这种Hash方式查找最近邻，可降低查找样本数，分为了12L

Categories: 图像查找