图像检索中为什么仍用BOW和LSH

图像检索中为什么仍用BOW和LSH

LSH方法本身已经在很多文章中有过介绍,大家可以参考这里和这里.其主要思想就是在特征空间中对所有点进行多次随机投影（相当于对特征空间的随机划分）,越相近的点,随机投影后的值就越有可能相同.通常投影后的值是个binary code（0或者1）,那么点xi经过N次随机投影后就可以得到一个N维的二值向量qi,qi就是xi经过LSH编码后的值.
问题是LSH是一种随机投影,上篇博客中也提到这样随机其实没有充分利用到样本的实际分布信息,因此N需要取一个十分大的数才能取得好的效果.因此,[2]中作者理所当然地就想到对LSH的投影函数进行学习（用BoostSSC和RBM来做学习）,效果可以见图3.经过学习的LSH就可以通过更少的投影函数取得更好的区分性.这就和BOW的作用有点像了（都是通过学习对原始的特征空间进行划分）,只不过BOW对特征空间的划分是非线性的,而LSH则是线性的.

二、LSH VS BOW：检索的时候对什么特征做编码?
（ 以下对LSH的介绍将不区分是否利用BoostSSC和RBM来做学习）.LSH一般是对图像的全局特征做LSH.比如图像的GIST,HOG,HSV等全局的特征.可以说,LSH是将一个特征编码成另外一个特征.这有一点降维的味道.经过N次随机投影后,特征被降维为一个长度为N的二值特征了.
BOW一般是对图像的局部特征做编码,比如SIFT,MSER等.BOW是将一组特征（局部特征）编码成一个特征（全局特征）,带有一种aggregation的性质.这是它与LSH最大的不同之处.

lsh方法本身已经在很多文章中有过介绍，大家可以参考这里和这里。其主要思想就是在特征空间中对所有点进行多次随机投影（相当于对特征空间的随机划分），越相近的点，随机投影后的值就越有可能相同。通常投影后的值是个binary code（0或者1），那么点xi经过n次随机投影后就可以得到一个n维的二值向量qi，qi就是xi经过lsh编码后的值。 问题是lsh是一种随机投影（见图1），上篇博客中也提到这样随机其实没有充分利用到样本的实际分布信息，因此n需要取一个十分大的数才能取得好的效果。因此，[2]中作者理所当然地就想到对lsh的投影函数进行学习（用boostssc和rbm来做学习），效果可以见图3。经过学习的lsh就可以通过更少的投影函数取得更好的区分性。这就和bow的作用有点像了（都是通过学习对原始的特征空间进行划分），只不过bow对特征空间的划分是非线性的（见图2），而lsh则是线性的。 图1 图2 图3 二、lsh vs bow：检索的时候对什么特征做编码？ （ 以下对lsh的介绍将不区分是否利用boostssc和rbm来做学习）。lsh一般是对图像的全局特征做lsh。比如图像的gist，hog，hsv等全局的特征。可以说，lsh是将一个特征编码成另外一个特征。这有一点降维的味道。经过n次随机投影后，特征被降维为一个长度为n的二值特征了。 bow一般是对图像的局部特征做编码，比如sift，mser等。bow是将一组特征（局部特征）编码成一个特征（全局特征），带有一种aggregation的性质。这是它与lsh最大的不同之处。