一种基于随机采样哈希表示的图像匹配方法

摘要

本发明公开了一种基于随机采样哈希表示的图像匹配方法，包括以下步骤：将n幅图像组成原始数据集，提取所有图像的视觉特征生成特征空间；从原始数据集中随机选择m幅图像，同时在特征空间中随机抽取p个视觉特征子集，得到一个样本子集；学习得到样本子集的t个主特征向量，作为哈希投影函数；用来生成t位二值哈希编码；重复上述步骤k次，得到k段t位二值哈希编码，并级联得到k×t位的二值哈希编码，作为匹配特征；得到待匹配图像和原始数据集中每一幅图像的二值哈希编码；基于得到的二值哈希编码进行相似度度量，得到待匹配图像的匹配结果。本发明有助于加快基于哈希编码的近似近邻查找方法的精度，适用于图像检索、图像匹配及其它机器学习算法中。

说明书

技术领域

本发明涉及信息检索领域，尤其是一种基于随机采样哈希表示的图像 匹配方法。

背景技术

近年来，随着数据的大规模增长，我们已经进入大数据时代。大数据 给传统的机器学习和模式识别方法都提出了巨大的挑战。图像匹配是很多 模式识别问题和应用中的关键技术之一，即通过查询图像与数据库中的图 像进行两两比对，找出最相似的图像。传统的线性图像匹配方法，如：穷 举查找(exhaustive search)方法，在大规模数据的情况下是非常慢的，在 很多对速度要求比较高的应用中是不切实际的。比如，在图像检索应用中， 用户对于查询时间是有一定要求的，穷举查找所需要的时间往往是不可接 受的。

为了解决这个问题，近似近邻查找(Approximate Nearest Neighbor)方法 受到了广泛的关注，其中，最经典的是基于树的模型，在这种模型下，数 据被非常有效地存储，从而取得非常快的搜索速度。代表性的基于树的模 型有KdTree、BallTree等。然而，所有基于树的方法都面临一个问题，即 在高维情况下其搜索效率大大下降，有时候甚至不如简单的线性查找。在 这种背景下，基于二值表示的近似近邻查找方法被提出来。这类方法将原 始数据转化为二值编码，然后在汉明空间中进行近邻查找，在满足一定的 假设情况下，汉明空间中的最近邻被认为是原始空间中的近似近邻，这类 方法也被称为哈希方法。

现有的哈希方法中，大多数模型都基于矩阵的特征值分解。通常特征 向量会被作为哈希函数用来生成数据的二值编码。对于这些基于特征值分 解的方法，每个特征向量所包含的信息量是不相同的。一般来说，大多数 的信息包含在对应特征值大的特征向量(主成分)中，其它的特征向量往 往包含很多的噪声。然而对于所有的这些哈希方法，每个特征向量最后被 量化为相同位数的哈希码。这样，随着越来越多的特征向量被用来作为哈 希函数，被引入的噪声也会越来越多。在实践中，这种做法被证明会导致 一个问题，即随着位数的增加编码的效果反而越差。这种现象与理想效果 有很大的出入，因为直观上说，随着编码位数的增加，所含的信息量应该 越来越大，效果也应该越来越好。

发明内容

本发明旨在利用一种新的哈希表示方法来进行图像的匹配，从而克服 传统的基于特征值分解的哈希方法所存在的问题，实现高效准确的二值表 示。

为了达到此目的，本发明在传统基于特征值分解的图像匹配方法的基 础上，提出了一种基于随机采样哈希表示的图像匹配方法，大大提高了近 似近邻搜索的精度。

本发明提出的一种基于随机采样二值表示的图像匹配方法包括以下 步骤：

步骤1，将n幅图像组成原始数据集，并提取所有图像的视觉特征对 相应的图像进行表示，所述视觉特征组成特征空间，所述原始数据集的规 模为n，所述特征空间的特征总维数为d；

步骤2，从所述原始数据集中随机选择m幅图像作为训练样本组成样 本空间，其中，m远小于n；

步骤3，在所述特征空间中随机抽取p个视觉特征作为样本最后的表达， 得到一个由m个维数为p的视觉特征组成的样本子集X∈R^m×p；

步骤4，学习得到所述样本子集的t个主特征向量，并将其作为哈希投 影函数；

步骤5，基于这t个哈希投影函数，生成一段t位二值哈希编码；

步骤6，重复所述步骤2-步骤5k次，得到k段t位二值哈希编码，将 这k段t位二值哈希编码级联起来得到一段k×t位的二值哈希编码，作为匹 配特征；

步骤7，基于所述匹配特征，利用投影法得到待匹配图像和所述原始 数据集中的每一幅图像对应的二值哈希编码；

步骤8，利用所述待匹配图像的二值哈希编码与所述原始数据集中每 一幅图像对应的二值哈希编码进行相似度度量，相似度最高的图像即为所 述待匹配图像的匹配结果。

其中，所述视觉特征包括以下特征中的至少一个：颜色直方图、SIFT 特征、GIST特征。

其中，所述步骤4中，使用主成分分析法来学习主特征向量。

其中，使用主成分分析法来学习主特征向量包括以下步骤：

步骤41，计算所述样本子集X的协方差矩阵C；

步骤42，对于矩阵C进行特征值分解，选择对应特征值最大的t个特征 向量作为哈希投影函数。

其中，所述步骤4还包括对于得到的t个主特征向量进行随机旋转的 步骤。

其中，所述步骤7进一步包括以下步骤：

步骤71，对于待匹配图像和所述原始数据集中的每一幅图像，根据所 述步骤3，提取得到每幅图像的p个视觉特征；

步骤72，将所述步骤71得到的p个视觉特征投影到所述匹配特征上， 得到与每幅图像相应的、长度为k×t的二值哈希编码。

其中，所述步骤8中，利用二值哈希编码之间的距离进行相似度度量

通过上述技术方案，本发明在准确度、理论保证和时间复杂度方面具 有以下三点优势：

1)在生成哈希函数的过程中，重复步骤1和步骤2k次，但是由于每 次只选用信息量最高的主特征向量(含有较少的噪声)作为哈希函数，并 且每次得到的哈希函数是由不同的训练样本子集学习到的，所以最后得到 的k×t个哈希函数更加有效；

2)本发明具有良好的理论保证，在本发明方法中，可以证明随着位数 的增加，二值编码的效果会更好。也就是说，相比于其它基于特征值分解 的方法，本发明可以理论上保证随着编码长度的增加，搜索的准确率会变 高。

3)在本发明所有的步骤中，主要的计算量是对一个m×p规模的矩阵 进行PCA降维，其时间复杂度为O(mp²+p³)，远远低于对一个n×d规模 的矩阵进行PCA降维所需要的时间复杂度。虽然整个步骤1和步骤2需 要重复k次，但是由于本发明方法中这些步骤完全是独立的，所以很适合 于并行计算。总体来说，本发明中的二值编码方法很适合于大规模数据。

4)本发明方法不仅可以应用于图像匹配领域，还可应用于图像检索 及其它机器学习算法等众多领域。

附图说明

图1是本发明基于随机采样哈希表示的图像匹配方法的流程图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实 施例，并参照附图，对本发明进一步详细说明。

图1是本发明基于随机采样二值表示的图像匹配方法的流程图，如图 1所示，所述方法包括以下步骤：

步骤1，将n幅图像组成原始数据集，并提取所有图像的视觉特征对 相应的图像进行表示，所述视觉特征组成特征空间，所述原始数据集的规 模为n，所述特征空间的特征总维数为d；

其中，所述视觉特征可以为：颜色直方图、SIFT特征、GIST特征。

步骤2，从所述原始数据集中随机选择m幅图像作为训练样本组成样 本空间，其中，m远小于n；

步骤3，在所述特征空间中随机抽取p个视觉特征作为样本最后的表达， 这样，就可以得到一个由m，个维数为p的视觉特征组成的样本子集 X∈R^m×p。；

在本发明一实施例中，可以仅对样本空间进行随机采样，也可以仅对 特征空间进行随机采样，当然也可以像上文所描述的同时对样本空间和特 征空间进行随机采样。

上述随机采样的做法可以在一定程度上规避一些噪声样本。

步骤4，学习得到所述样本子集的t个主特征向量，并将其作为哈希投 影函数；

在本发明一实施例中，使用主成分分析法(PCA)来学习主特征向量。 具体地，使用主成分分析法(PCA)来学习主特征向量包括以下步骤：

步骤41，计算所述样本子集X的协方差矩阵C。；

步骤42，对于矩阵C进行特征值分解，选择对应特征值最大的t个特征 向量作为哈希投影函数。

该步骤中，为了使每个特征向量所包含的信息量尽可能的大，通常只 能选取少量的特征向量，这是因为排在后面的特征向量的信息量比较小而 且包含更多的噪声，也就是说，t是一个比较小的值。

在有些情况下，即使是前t个特征向量之间所包含的信息量也是不均 匀的，即第一个特征向量比第t个特征向量所包含的信息量要大很多。这 并不有利于二值编码的学习。为了解决这个问题，本发明提出对于得到的 t个主特征向量进行一次随机旋转，这样有利于得到信息量更加均匀化的 特征向量。

步骤5，基于这t个哈希投影函数，生成一段短的(t位)二值哈希编 码；

其中，根据哈希投影函数生成二值编码的方法是现有技术中常用的方 法，在此不作赘述。

步骤6，重复所述步骤2-步骤5k次，得到k段t位二值哈希编码，将 这k段t位二值哈希编码级联起来得到一段长的、k×t位的二值哈希编码， 即一个高效的二值表示，作为匹配特征；

在实际应用中，当t比较小时，如此短的二值编码往往是不够的。为 了使搜索结果更加准确，需要更长的哈希编码。然而，正如上文所述，直 接通过获取更多特征向量作为哈希投影函数的方法是不可行的。为了解决 这个问题，本发明提出上述通过连接数段短的编码来获得长的编码的方法。 次，这样就可以得到段位的哈希码。由于本发明在步骤2中的采样过程是 完全随机的，这样，得到的k段二值哈希编码是完全不同的，而且都包含 其独特的信息。

步骤7，基于所述匹配特征，利用投影法得到待匹配图像和所述原始 数据集中的每一幅图像对应的二值哈希编码；

所述步骤7进一步包括以下步骤：

步骤71，对于待匹配图像和所述原始数据集中的每一幅图像，根据所 述步骤3，提取得到每幅图像的p个视觉特征；

步骤72，将所述步骤71得到的p个视觉特征投影到所述匹配特征上， 得到与每幅图像相应的、长度为k×t的二值哈希编码

其中，所述投影可采用内积和阈值化处理的方式进行，当然也可采用 现有技术中的其他投影方法，在此不作赘述。

步骤8，利用所述待匹配图像的二值哈希编码与所述原始数据集中每 一幅图像对应的二值哈希编码进行相似度度量，相似度最高的图像即为所 述待匹配图像的匹配结果。

该步骤中，可通过二值哈希编码之间距离计算图像之间的相似度，与 所述待匹配图像的二值哈希编码距离最短的二值哈希编码对应的图像即 为所述待匹配图像的匹配结果。

本发明的上述技术方案采用了样本空间和特征空间的随机抽样、提取 主特征向量以及采用二值表示等技术手段，比基于传统哈希编码方法、 kd-tree的匹配精度有大幅度提高。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行 了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施例而 已，并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修 改、等同替换、改进等，均应包含在本发明的保护范围之内。