CN109902700A - 一种基于哈希算法的大规模影像匹配方法 - Google Patents

Abstract

本发明公开了一种基于哈希算法的大规模影像匹配方法，所述方法包括：步骤1)提取原图像和目标图像的所有特征点；步骤2)在每个特征点处提取特征描述子，并为特征点分配方向值，生成特征向量；步骤3)利用哈希算法将所有的特征向量映射到哈希表，每个特征向量对应一个哈希特征码，利用映射函数将哈希特征码分别分配至若干个桶组中；步骤4)从原图像中选取一个特征点的特征向量为原特征，利用哈希表中的特征向量对原图像和目标图像进行匹配，获取匹配的同名点。本发明方法能够实现大规模影像的快速精确匹配，有效提高大规模影像的匹配效率，同时又可以保证大区域影像匹配的几何精度。

Description

一种基于哈希算法的大规模影像匹配方法

技术领域

本发明涉及影像匹配领域，尤其涉及一种基于哈希算法影像匹配方法。

背景技术

影像匹配是在变换的空间中寻找一种或多种变换关系，使来自不同时间、不同传感器或不同视角的同一场景的两幅或多幅影像在空间位置上保持一致。实质就是在两幅或者多幅影像之间寻找同名点。

计算机视觉领域著名且被广泛应用的SIFT算法通过为图像建立尺度空间及为特征点建立方向向量，从而检测出一种对尺度、旋转变化等都具备不变性的特征点。此算法能够很好地获得特征点的位置及邻域信息，使每个特征点都具有高度的唯一性。但是由于航空影像分辨率一般比较高、重叠率较大、影像数量较多等因素，以及直接利用特征描述子进行距离度量、穷举法的匹配策略，导致SIFT算法在遍历搜索每张影像匹配点的运算量巨大，速度大大降低，无法满足航空无人机摄影的现势性要求。在保证影像匹配精确性、可靠性的前提下，如何优化匹配策略改善和提高大规模影像匹配的效率是其重要的研究内容。

发明内容

本发明要解决的技术问题在于克服现有技术的不足，提供基于哈希算法的无人机航空大规模影像匹配方法，该方法针对无人机航空大规模影像，基于SIFT特征提取的基础上，采用哈希算法辅助的搜索策略代替穷举匹配方法，进而提高匹配同名点的效率。

为解决上述技术问题，本发明公开了一种基于哈希算法的大规模影像匹配方法，所述方法包括：

步骤1)提取原图像和目标图像的所有特征点；

步骤2)在每个特征点处提取特征描述子，并为特征点分配方向值，生成特征向量；

步骤3)利用哈希算法将所有的特征向量映射到哈希表，每个特征向量对应一个哈希特征码，利用映射函数将哈希特征码分别分配至若干个桶组中；

步骤4)从原图像中选取一个特征点的特征向量为原特征向量，利用哈希表中的特征向量对原图像和目标图像进行匹配，获取匹配的同名点。

作为上述方法的一种改进，所述步骤1)具体为：

采用sift算法为原图像和目标图像建立尺度空间及为特征点建立方向向量，从而检测出一种对尺度、旋转变化都具备不变性的特征点。

作为上述方法的一种改进，所述步骤2)具体为：

以特征点为中心取16*16的邻域作为采样窗口，将采样窗口的采样点与特征点的相对方向通过高斯加权后归入包含8个方向的梯度直方图，最后获得128维特征向量；将每个特征描述子归一化至0-120区间。

作为上述方法的一种改进，所述步骤3)的哈希算法为：MD2、MD4、MD5或SHA-1。

作为上述方法的一种改进，所述步骤3)包括：

步骤3-1)采用正态分布随机数生成器生成所有特征向量的哈希特征码；

步骤3-2)利用映射函数将哈希特征码分别映射至6个桶组，每个桶组含2¹⁰只桶；

步骤3-3)分别计算每个特征向量在6只桶组里的桶ID号。

作为上述方法的一种改进，所述步骤4)具体包括：

步骤4-1)采用桶ID号作为初次匹配相似性度量，将原图像的原特征向量Hash₀所在的桶组里检索具有相同桶ID号的目标图像的特征向量，检索到的特征向量为初始匹配特征向量Hash_i，1≤i≤M,M为初始匹配特征向量的个数；

步骤4-2)对初始匹配特征向量采用海明距离做第二次相似性度量，获得10个备选匹配特征向量；

对初始匹配特征向量Hash_i和原特征向量Hash₀进行异或运算，计算出两个特征哈希码的海明距离dH_i，从中选出10个海明距离最小的特征向量作为备选匹配特征向量：

步骤4-3)采用欧式距离对10个备选匹配特征向量做第三次相似性度量，获得2个最近备选匹配特征向量；

计算10个备选匹配特征向量与原特征向量的欧式距离，选择距离最近的两个备选匹配特征向量为最近匹配特征向量；

原图像中特征向量表示为R＝(r₁,r₂,…,r₁₂₈)

目标图像中特征向量表示为S＝(s₁,s₂,…,s₁₂₈)

以上两个特征之间的欧式距离表示为：

步骤4-4)计算两个最近匹配特征向量与原特征向量的欧式距离的比值，如果比值小于阈值T，则取欧式距离最小的点为该特征点的匹配点，否则，判断该特征点没有匹配点。

采用上述技术方案后，本发明与现有技术相比具有以下有益效果：

本发明方法将影像特征点的特征向量通过映射函数以哈希值表示，然后利用这些哈希值计算匹配距离，达到快速获得精确匹配点子集的目的，从而实现大规模影像的快速匹配。该方法有效提高大规模影像的匹配效率，同时又可以保证大区域影像匹配的几何精度。

附图说明

图1是本发明基于哈希算法的大规模影像匹配方法的流程框图；

图2是本发明基于哈希算法的大规模影像匹配方法的哈希映射示意图。

具体实施方式

下面结合附图和具体实施例，对本发明作进一步说明，以助于理解本发明的内容。

如图1所示，一种基于哈希算法的大规模影像匹配方法，所述方法包括：

步骤1)提取原图像和目标图像的所有特征点；

利用sift算法为原图像和目标图像建立尺度空间及为特征点建立方向向量，从而检测出一种对尺度、旋转变化等都具备不变性的特征点。此算法能够很好地获得特征点的位置及邻域信息，使每个特征点都具有高度的唯一性。目标图像可以有多个。

步骤2)在每个特征点处提取特征描述子，并为特征点分配方向值，生成特征向量；

以特征点为中心取16*16的邻域作为采样窗口，将采样窗口的采样点与特征点的相对方向通过高斯加权后归入包含8个方向的梯度直方图，最后获得4*4*8的128维特征向量。将每个特征描述子归一化至0-120区间，便于后期海明距离的计算。

步骤3)利用哈希算法将所有的特征向量映射到哈希表，每个特征向量对应一个哈希特征码；利用映射函数将哈希特征码至6个桶组，每个桶组含2¹⁰只桶；

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。好的哈希算法具有均匀分散性。典型的哈希算法包括MD2、MD4、MD5和SHA-1。在本实施例中，采用正态分布随机数生成器生成特征向量的哈希码，即采用的映射函数为正态分布函数。

在每只桶组里均会计算出对应的ID，进而每个桶里的特征具备了桶组ID的属性，作为特征点初次相似度量的参数；分别计算每个特征向量在6只桶组里的桶ID号，进而不同桶组里相同的桶ID具有相似的特性，所以桶ID号可以作为特征点初次匹配的相似度量参数。

步骤4)从原图像中选取一个特征点的特征向量为原特征向量，利用哈希表中的特征向量对原图像和目标图像进行匹配，获取匹配的同名点；具体包括：

步骤4-1)采用桶ID号作为初次匹配相似性度量，将原图像的原特征向量Hash₀所在的桶组里检索目标图像的特征向量，检索到的特征向量为初始匹配特征向量Hash_i，1≤i≤M,M为初始匹配特征向量的个数；

步骤4-2)对初始匹配特征向量采用海明距离做第二次相似性度量，获得10个备选匹配特征向量；

对初始匹配特征向量Hash_i和原特征向量Hash₀进行异或运算，计算出两个特征哈希码的海明距离dH_i，从中选出10个海明距离最好(即海明距离最小)的特征向量作为备选匹配特征向量：

海明距离：两个哈希码对应二进制(01串)取值不同的数量称为这两个哈希码的海明距离。举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。计算方法中异或结果中含有几个1，则海明距离等于这个数值。

步骤4-3)采用欧式距离对10个备选匹配特征向量做第三次相似性度量，获得2个最优备选匹配特征向量；

计算10个备选匹配特征向量与原特征向量的欧式距离，选择距离最近的两个最近匹配特征向量；

原图像中特征向量表示为R＝(r₁,r₂,…,r₁₂₈)

目标图像中特征向量表示为S＝(s₁,s₂,…,s₁₂₈)

以上两个特征之间的欧式距离表示为：

步骤4-4)计算两个最近匹配特征向量与原特征向量的欧式距离的比值，如果比值小于阈值T，则取欧式距离最小的点为该特征点的匹配点，否则，判断该特征点没有匹配点。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同替换，都不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求范围当中。

Claims (6)

1.一种基于哈希算法的大规模影像匹配方法，所述方法包括：

步骤1)提取原图像和目标图像的所有特征点；

步骤2)在每个特征点处提取特征描述子，并为特征点分配方向值，生成特征向量；

步骤3)利用哈希算法将所有的特征向量映射到哈希表，每个特征向量对应一个哈希特征码，利用映射函数将哈希特征码分别分配至若干个桶组中；

步骤4)从原图像中选取一个特征点的特征向量为原特征向量，利用哈希表中的特征向量对原图像和目标图像进行匹配，获取匹配的同名点。

2.根据权利要求1所述的基于哈希算法的大规模影像匹配方法，其特征在于，所述步骤1)具体为：

采用sift算法为原图像和目标图像建立尺度空间及为特征点建立方向向量，从而检测出一种对尺度、旋转变化都具备不变性的特征点。

3.根据权利要求2所述的基于哈希算法的大规模影像匹配方法，其特征在于，所述步骤2)具体为：

以特征点为中心取16*16的邻域作为采样窗口，将采样窗口的采样点与特征点的相对方向通过高斯加权后归入包含8个方向的梯度直方图，最后获得128维特征向量；将每个特征描述子归一化至0-120区间。

4.根据权利要求1所述的基于哈希算法的大规模影像匹配方法，其特征在于，所述步骤3)的哈希算法为：MD2、MD4、MD5或SHA-1。

5.根据权利要求3所述的基于哈希算法的大规模影像匹配方法，其特征在于，所述步骤3)包括：

步骤3-1)采用正态分布随机数生成器生成所有特征向量的哈希特征码；

步骤3-2)利用映射函数将哈希特征码分别映射至6个桶组，每个桶组含2¹⁰只桶；

步骤3-3)分别计算每个特征向量在6只桶组里的桶ID号。

6.根据权利要求4所述的基于哈希算法的大规模影像匹配方法，其特征在于，所述步骤4)具体包括：

步骤4-1)采用桶ID号作为初次匹配相似性度量，将原图像的原特征向量Hash₀所在的桶组里检索具有相同桶ID号的目标图像的特征向量，检索到的特征向量为初始匹配特征向量Hash_i，1≤i≤M,M为初始匹配特征向量的个数；

步骤4-2)对初始匹配特征向量采用海明距离做第二次相似性度量，获得10个备选匹配特征向量；

对初始匹配特征向量Hash_i和原特征向量Hash₀进行异或运算，计算出两个特征哈希码的海明距离dH_i，从中选出10个海明距离最小的特征向量作为备选匹配特征向量：

步骤4-3)采用欧式距离对10个备选匹配特征向量做第三次相似性度量，获得2个最近备选匹配特征向量；

计算10个备选匹配特征向量与原特征向量的欧式距离，选择距离最近的两个备选匹配特征向量为最近匹配特征向量；

原图像中特征向量表示为R＝(r₁,r₂,…,r₁₂₈)

目标图像中特征向量表示为S＝(s₁,s₂,…,s₁₂₈)

以上两个特征之间的欧式距离表示为：

步骤4-4)计算两个最近匹配特征向量与原特征向量的欧式距离的比值，如果比值小于阈值T，则取欧式距离最小的点为该特征点的匹配点，否则，判断该特征点没有匹配点。