基于LSH索引的快速图像检索

《基于LSH索引的快速图像检索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于!"#索引的快速图像检索唐俊华阎保平（中国科学院网络中心数据库室，北京%"""O"）P75-,.：+-*1Q)*4)-RCFM#-/#/*摘要高维空间中点数据的索引及检索是基于内容图像检索领域的关键问题，文中将@&A（.2/-.,+BC’*C,+,D’4-C4,*1）索引算法应用于基于内容图像检索系统中，与传统的索引方法相比，该算法具有复杂度比较低、支持非常高的维数、极低的EST代价等特点。实验结果证明，将该索引算法应用于基于内容图像检索系统中，其性能优于传统的索引方法#关键词基于内容图像检索索引结

2、构相似性检索@&A算法文章编号%""!7O==%7（!""!）!$7""!"7"!文献标识码0中图分类号UV=W%$%&’()%*+,+’-.+/%01%&+234!"#(42+5.4*6%4*78498%:%41%3;.4*（;-+-M-C’;’X-3+5’*+，Y25X)+’3Z’+I23GE*[235-+,2*Y’*+’3，U4’Y4,*’C’0/-F’5B2[&/,’*/’C，<’,Q,*1%"""O"）<=&’-%>’：E+,C-/3,+,/-.,CC)’[23,*F’,*1-*F3’+3,

3、’D-.2[4,14F,5’*C,2*-.X2,*+F-+-,*/2*+’*+7M-C’F,5-1’3’]+3,’D-.[,’.F#E*+4,CX-X’3，-*’IG,*F2[,*F’,*1C+3)/+)3’,C-F2X+’F,*+4’/2*+’*+7M-C’F,5-1’3’+3,’D-.CBC+’5，,*/25X-3,C2*I,+4+3-F,+,2*-.,*F’,*15’+42FC，+4’@&A/-*M),.FI,+4.2I/25X.’,+B，C)XX23+D’3B4,14F,5’*C,2*-.

4、,+B，-*F’D’*D’3B.2IEST/2C+，’+/#?+@A3-2&：Y2*+’*+7M-C’F,5-1’3’+3,’D-.，E*F’C+3)/+)3’，&,5,.-3,+B3’+3,’D-.，@&A-.123,+45%引言证明，在数据规模、维数增大时，该索引方法仍然具有很好的性在基于内容的图像检索系统中，需要在图像集中查找与某能。个给定图像“相似”的图像，这样的查找过程叫“相似性检索”。通常，是从图像中提取“特征”，然后在图像的“特征”上定义相!问题定义似性。大多数情况下，特征用多维空间的点

5、（或矢量）来描述，空为了方便说明，首先定义几个记号。用!表示图像集合，间的维数可能低至几维，也可能大至数千维。空间中特征矢量映射#：!!$将!中的每幅图像映射到%维特征矢量数据集$中的一个矢量（也就是&%中的一个点）上。假设采用的距离之间的接近程度反映了对象内容的相似程度，因此基于内容的测度为’：&%(&%!&)"K"L，其中&)表示正实数空间，则相似度检索就简化为空间中点的快速搜索问题。实现相似搜索的方法很多，但是存在一种最基本的方法，可以由’（·，·）衡量，’（·，·）越小，相似度越大。如果用&*（

6、+）表示查询结果集，其中+表示查询对象，传叫做“顺序扫描算法”（&’()’*+,-.&/-*0.123,+45，&&0）：顺序""检查对象集合中的每个对象是否符合相似性检索要求。&&0的统的“,7近邻查询（,7*’-3’C+*’,14M23,*1()’3B）”（,为给定的开销很大。多年来，人们已经开发出多种支持相似性检索的索一个正整数），可以定义如下：*引结构，例如67树8%9，:7;7树8!9，:7;7<7树8=9，&&7树8$9和&67树8>9当,N%时，&（+）NK+3+#$，$4#$：’（4，+

7、）%;（+，+）L，%-"./0.12"""等，这些方法都可以归类为空间划分的方法，在文献8?9中指出，*设&（,-%）-"./0.12（+"）为“（,-%）最近邻查询”的结果，则“,7近邻查随着维数的增加这一类的索引方法的检索性能会急剧恶化。例询”定义为：如，当维数增加时，67树的检索时间复杂度将很快的接近!（"）。**在很多情况下，做相似图像检索时，快速地检索出一个大&,-"./0.12（+"）N&（,-%）-"./0.12（+"）"K+3+#$5，$4#$：’（4，+"）%’*致符合要求的图像集合

8、，往往比花费很长的时间检索出与检索（+，+"）L，其中$6$-&（,-%）-"./0.12（+"）。要求完全相符合的图像集合更具有吸引力。这一点在数据规模在上一节中提出，快速地检索出一个大致符合要求的图像较大，并且对响应时间有较高要求的场合显得尤为重要。@&A集合，往往比花费很长的时间检索出与检索要求完全相符合的（@2/-.,+B&’*C,+,D’A-C4,*1）算法首先由E*FBG和H2+I-*,8J9提图像集合更具有吸引力。基于这个想法