一种基于最小哈希的二值特征匹配方法

特征匹配是图像识别中一个基本研究问题。常用的匹配方式一般是基于贪婪算法的线性扫描方式，但只适用于低维数据。当数据维数超过一定程度时，这些匹配方法的时间效率将会急剧下降，甚至不强于强力线性扫描方法。本文提出一种基于最小哈希的二值特征匹配方法。通过最小哈希函数映射变换操作，将原始特征集合分成多个子集合，并将一个在超大集合下内查找相邻元素的问题转化为在一个很小的集合内查找相邻元素的问题,计算量有所下降。使用Jaccard距离度量的最小哈希函数能最大限度地保证原始数据中相似的向量对在哈希变换后依然相似。实验表明这种匹配方法应用在二值特征上时，可以获得比KD-Tree更好的匹配效果。

A Binary Feature Matching Method Based on Minimum Hashing

Feature matching is one of basic problems in image recognition. Common matching methods are the linear scanning methods based on greedy algorithm, and they are applied to low dimensional data. When data dimension exceeds a certain degree, the time efficiency of matching will decrease sharply, even not stronger than the strong linear scanning method. This paper proposes a binary feature matching method based on minimum hashing. By the mapping transformation in minimum hashing function, the original feature set will be divided into several subsets. It can be transformed into a problem of searching the adjacent elements within a tiny set instead of a huge set, which decreases the computational cost. Using Jaccard distance, minimum hashing function can maximally ensure the similarity of similar vectors in original data after hash transformation. Experiments show that this method can obtain better matching performance than KD-Tree when it is applied to binary feature.