Inverted Index Compression for Scalable Image Matching 倒排索引图像匹配

《Inverted Index Compression for Scalable Image Matching 倒排索引图像匹配》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、InvertedIndexCompressionforScalableImageMatchingDavidM.Chen1,SamS.Tsai1,VijayChandrasekhar1,GabrielTakacs1,RamakrishnaVedantham2,RadekGrzeszczuk2,BerndGirod11DepartmentofElectricalEngineering,StanfordUniversity,Stanford,CA943052NokiaResearchCenter,PaloAlto,CA94304AbstractToperformfastimagema

2、tchingagainstlargedatabases,aVocabularyTree(VT)usesaninvertedindexthatmapsfromeachtreenodetodatabaseimageswhichhavevisitedthatnode.Theinvertedindexcanrequiregigabytesofmemory,whichsignificantlyslowsdownthedatabaseserver.Inthispaper,wedesign,develop,andcomparetechniquesforinvertedindexcompress

3、ionforimage-basedretrieval.Weshowthatthesetechniquessignificantlyreducememoryusage,byasmuchas5×,withoutlossinrecognitionaccuracy.Ourworkincludesfastdecodingmethods,anofflinedatabasereorderingschemethatexploitsthesimilaritybetweenimagesforadditionalmemorysavings,andageneralizedcodingschemeforso

4、ft-binnedfeaturedescriptorhistograms.Wealsoshowthatreducedindexmemorypermitsmemory-intensiveimagematchingtechniquesthatboostrecognitionaccuracy.1.IntroductionInthepastfewyears,advancesinvisualsearchhaveledtothedevelopmentofnumerousimage-basedretrievalsystems[1][2][3][4].Mostoftheadvancesareb

5、asedonlocalimagefeaturessuchasSIFT[5],SURF[6],andCHoG[7]whichcanbematchedrobustlydespitephotometricandgeometricdistortions.Equallyimportantforlarge-scaleimagesearcharedatastructureswhichefficientlyindexlocalfeatures,andthemostnotableofthesearetheVocabularyTree(VT)[8]anditsrecentextensions[9][

6、10].Tofacilitatefastsearchthroughadatabasecontainingbillionsoffeatures,theVTsplitsthefeaturedescriptorspacebytree-structedvectorquantization(TSVQ),wheretheVQcentroidsarethetreenodes.Eachimage’ssetoffeaturedescriptorscanthenbecompactlysummarizedbyatreehistogram,whichcountshowofteneachtreenode

7、isvisited.Tospeedupimagesearch,theVTof[8]usesaninvertedindex.Foreachtreenode,theinvertedindexstoresalistofimageIDsindicatingwhichdatabaseimageshavevisitedthatnode,aswellasthevisitfrequencies.Fig.1showsaVT-basedretrievalsystemwithaninvertedindex.Dur