一种用于图像匹配的快速有效的二分哈希搜索算法  

A Fast and Effective Dichotomy-Based Hash(DBH) Search Algorithm for Image Matching

作　　者：何周灿[1] 王庆[1] 

机构地区：[1]西北工业大学计算机学院,陕西西安710072

出　　处：《西北工业大学学报》2010年第4期609-615,共7页Journal of Northwestern Polytechnical University

基　　金：国家自然科学基金(60873085);国家"863"项目(2007AA01Z314;2009AA01Z332);"新世纪优秀人才"计划(NCET-06-0882)资助

摘　　要：文章针对高维图像特征的匹配问题,提出一种新的二分哈希搜索算法(Dichotomy BasedHash,DBH)。对具有大尺度旋转、缩放、视点和噪声变化的图像进行匹配,结果表明DBH可以较大提高最近邻搜索精度和查全率-查错率性能,从而获得较好的图像粗匹配结果。该算法搜索性能优于BBF(Best Bin First)算法,同时也比高维Hash搜索算法LSH(Local Sensitive Hash)更快更精确。Aim.The introduction of the full paper reviews past research and then proposes a new DBH search algorithm.Section 1 explains the DBH search algorithm with the help of Fig.1;its core consists of：（1） we calculate the distribution of the high-dimensional data set to each dimension;（2） we randomly choose the specified dimensions as the key dimensions;（3） we choose different hash functions to hash the high-dimensional features so that the similarity features of the images to be matched can be hashed into the same bucket,using high probability;（4） we present the procedural steps of the DBH search algorithm that hashes and queries for several times.Section 2 did experiments on image matching with the standard data set from Ref.13 and compared the image matching performance of our DBH search algorithm with that of BBF（best bin first） search algorithm and LSH（local sensitive hash） search algorithm.The experimental results,presented in Figs.2 and 4 and Tables 3 and 4,show preliminarily that our DBH search algorithm performs better in both accuracy and speed,and has higher recall vs（1-precision） ratios in different transformations of image pairs with rotation,scale,noise and weak affine change than the famous BBF search algorithm and the classical LSH search algorithm.

关 键 词：图像处理 数据结构 算法 图像匹配 最优分区优先搜索 局部敏感散列 二分哈希 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]