本发明涉及图像处理领域， 尤其涉及一种基于级联二值编码的图像匹配 方法。 背景技术

图像匹配是计算机视觉、 图像处理等领域的关键技术， 在三维重建、 图 像拼接、 目标识别等方面具有广泛的应用。 特别是在大范围场景的三维重建 问题中， 由于大规模图像之间的匹配需要耗费大量时间 ， 导致三维重建的速 度非常慢。 因此， 快速、 准确的图像匹配是亟待解决的问题。

图像匹配技术大致可以分为三类： 点匹配， 线匹配和区域匹配。 由于其 对光照变化、 仿射变换和视角变化的鲁棒性， 点匹配的重视程度较高， 许多 有效的算法被提出。 然而， 点匹配通常是非常耗时的， 一对图像匹配的计算 时间复杂性为 ⁰ (^ ² )， 其中 ^N 为平均每幅图像的特征点个数。 在暴力匹配情况 下， 特征点匹配问题可以被看作是一个最近邻查找 问题。 作为替代方案， 提 出了近似最邻近查找， 其中比较著名的是基于树的模型， 在这种模型下， 数 据被非常有效地存储， 从而取得非常快的搜索速度。 但是所有基于树的方法 在高维情况其搜索效率大大下降， 有时候甚至不如简单的线性查找。 发明内容

本发明的目的是针对现有技术的不足， 提供一种基于级联二值编码的图 像匹配方法， 可以实现高效和准确的图像匹配。

为实现上述目的，本发明提供了一种基于级联 二值编码的图像匹配方法， 所述方法包括： 步骤 Sl， 利用基于多个哈希表的哈希查找方法对图像中 的候选特征点进 行粗 选， 得到候选特征点的候选子集；

步骤 S2， 将所述候选特征点的候选子集映射到高维汉明 空间； 步骤 S3， 建立汉明距离-数据地址的哈希表； 查询所述汉明距离-数据地 址的哈希表， 从而得到最佳匹配特征点。

进一步的， 所述步骤 S1具体为： 步骤 Sl l， 通过短的哈希码做粗哈希查 询， 图像中的所有特征点通过局部位置敏感哈希方 法映射成 m位的哈希函数 的哈希码。

进一步的， 所述步骤 S11具体为： 对于第一图像 I 中的第一特征点 p， 用 m位哈希码建立一个哈希查找表， 第二图像 J中所有和第一特征点 p落到 同一个哈希桶中的特征点被返回；

其中 ， 通过局部位置敏感哈希生成 L 个不同 的哈希函数 gr(?) 二 i 、.K- ( ： ^k . " US)) ' ' ¹ 二 H ， 对 4 工于母个入哈入希函7数， 建、 入 ϋ一个 哈希表， 将第一图像 I 中的第一特征点 p 投入到哈希桶 (Ρ)中， 其中， = 1,2 „. JL。

进一步的， 所述步骤 S2具体为： 通过 n位哈希函数（n>m )将这些候选 特征点映射到高维汉明空间中， 然后在所述高维汉明空间中进行汉明距离的 计算并排序。

进一步的， 所述步骤 S3具体为：

计算查询点与候选特征点之间的第一汉明距离 ；

以所述第一汉明距离为键， 以候选特征点的内存地址为值建哈希表； 遍历所述汉明距离 -数据地址的哈希表的数据库， 并建立汉明距离 -数据 地址哈希表；

从键值最小的桶开始查找， 直到找满预设个候选特征点为止， 找到的预 设个候选特征点是与查询点汉明距离最小的预 设个候选特征点。 本发明图像匹配方法， 其匹配釆用了一个三层的哈希结构， 通过逐层筛 选的过程实现快速准确的特征点匹配， 处理速度快， 效果好， 可实现高效和 准确的图像匹配。 附图说明

图 1为本发明一种基于级联二值编码的图像匹配� �法的流程图。 具体实施方式

下面通过附图和实施例， 对本发明的技术方案做进一步的详细描述。 本发明图像匹配方法提出了一种由粗到细的级 联二值编码方法， 综合了 哈希方法的查询和排序两种查找策略， 大大提升了图像特征点匹配的速度， 匹配釆用了一个三层的哈希结构， 通过逐层筛选的过程实现快速准确的特征 点匹配。

图 1为本发明一种基于级联二值编码的图像匹配� �法的流程图， 如图所 示， 本发明具体包括如下步骤：

步骤 101， 利用基于多个哈希表的哈希查找方法对图像中 的候选特征点 进行粗 选， 得到候选特征点的候选子集；

本步骤是基于多哈希表的候选特征点查询。

具体的，通过短的哈希码做一次最粗略的哈希 查询，即哈希查找（ Hashing Lookup ) ₀ 其中， 图像中的所有特征点通过局部位置敏感哈希方 法映射成 m位 的哈希码。 对于图像 I 中的特征点 p， 为了找到它在图像 J中的匹配点， 需 要用这些 m位哈希码建立一个哈希查找表。 图像 J中所有和点 p落到同一个 哈希桶中的特征点将被返回。

哈希查找具有常数的时间复杂度， 在本发明中， 釆用一种基于多个哈希 表的哈希查找方法。 具体的， 通过局部位置敏感哈希（LSH )生成 L个不同的 哈希函数 g: ) = ¾ _{2 £} ½), J = ... _t L, 对应于每个哈希函数， 可以建立一个哈希表。 对于图像 I中的特征点 p， 将其投入到哈希桶^ (p)中， 其中， = H L。

因为越长的哈希码判别力越强， 从而使得相似点落到同一个桶中的概 率 和相异点落到同一个桶的概率 ₂ 的差距变大。 当 m增大时， ？^将减少， 即要使 L充分大从而保证真正的近邻至少有一次和查� �点落在同一个桶 中。 具体的， 这个概率为 1 - (i -

需要为不同的应用选择不同的参数 m和 L。例如在三维重建中的图像匹 配， 分别选择参数 m=8或 10， L=6。

步骤 102， 将候选特征点的候选子集映射到高维汉明空间 ；

在步骤 101的粗搜索之后， 可以在步骤 102中对步骤 101得到的候选 子集进行精确搜索， 例如计算每一个候选特征点与查询点之间的欧 氏距 离。 但是， 因为候选子集的规模仍然很大， 直接计算欧式距离需要很大的 计算量， 本发明釆用通过更长的 n位哈希函数（n>m ) 将这些候选特征点 映射到高维汉明空间中， 然后就可以在这个空间中进行汉明距离的计算 并 排序。

步骤 103， 建立汉明距离-数据地址的哈希表； 查询汉明距离-数据地址 的哈希表， 从而得到最佳匹配特征点。

为了进行最精确的查找， 需要找到汉明空间中的前 K个近邻， 并且在 其中找到欧氏距离最近的前两名来判断是否匹 配。

通常来说， 为了找到前 κ个近邻， 需要遍历数据库 K次， 当数据库非 常大时， 这个过程也是很耗时的。 在本发明中， 提出一种基于哈希的前 κ 名的查找方法， 仅需要遍历数据库一次就可以定位前 κ名。

具体的， 在遍历数据库的过程中， 首先计算查询点与候选特征点之间 的汉明距离， 与此同时， 以这个汉明距离为键， 以候选特征点的内存地址 为值建哈希表。于是，在遍历整个数据库一次 之后能够完整的建立一个 "汉 明距离 -数据地址" 的哈希表。

为了定位前 κ名， 只要从键值最小的桶开始查找， 如果第一个桶中的 候选点个数少于 κ， 则到第二个桶中查找， 以此类推， 直到找满 κ个候选 点为止。 通过这个过程找到的 Κ个候选点一定是与查询点汉明距离最小的 Κ个点。

综上， 本发明图像匹配方法在图像特征点提取与表示 阶段， 首先对两 幅待匹配的图像（ ^和 ₂ )分别进行特征点检测， 然后对检测到的特征点进 行特征向量表示。 例如， 可以用 S I FT方法检测图像的特征点， 并表示成 128维的特征向量。

在基于级联二值编码的特征点匹配阶段， 釆用三层的级联二值编码方 法， 对待匹配图像 ₂ 和1 ₂ 中重叠区域上的特征点进行一对一的匹配 。 对于图 像^中的任何一个特征点 x _s ， 首先釆用一种基于多个哈希表的哈希查找方 法， 按照汉明距离大小， 对图像中 i _:i 的所有特征点 yj进行粗略筛选， 得到 一个候选子集？； 然后把候选子集？中的所有特征点映射到高维 汉明空间； 最后从候选子集 Ϊ中快速查询到前 K个最近匹配点， 这里的 K可以根据不 同应用设置不同的数目， 例如， 三维重建中的图像匹配往往设置 K=2。

对于两幅待匹配的图像（分别记为 ^和 L _s . ) ， 4叚设每幅图像中的特征点 的数量均为 。 计算欧式距离的时间复杂度记为' τ _ε ， 计算汉明距离的时间 复杂度记为 。 需要说明的是， 在现代 CPU架构下， 计算 128维 0-1向量 的汉明距离仅需 1个时钟周期， 因此汉明距离的计算开销 是远小于欧式 距离的计算开销 的。

基于暴力搜索的匹配算法是为确定图像 i中每个特征点的匹配结果， 需要对图像 ¾中的所有特征点进行遍历， 逐个计算欧式距离， 从而确定最 近邻与次近邻， 因此最终的总时间复杂度为 o( ' τ _ε :)。 基于树的匹配算法是对于图像^中每个特征点� �在图像½的特征点集合 中寻找最近邻和次近邻的搜索过程是基于树的 ， 平均情况下需要计算 k W 次欧式巨离， 因此总时间复杂度为

本发明的匹配算法是对于图像 ^中每个特征点， 经过第一轮的基于多 个哈希表的哈希查询 （该步骤的时间开销可忽略） ， 平均会有 个特 征点进入候选集合；对于候选集合中每个特征 点，需要逐个计算汉明距离， 并选出距离最小的 k个元素， 时间复杂度为 0( ΛΓ/2Ί 对于距离最小的 k 个元素， 需要分别计算欧式距离， 时间复杂度为 0(,¾ . )； 因此， 总时间复 杂度为 o(^ ² 7 ■ s

通过上述时间复杂度分析可以看出， 基于暴力搜索的匹配算法的时间 复杂度最高； 基于树的匹配算法与基于哈希的暴力匹配算法 相比， 在图像 中特征点数量较多时，时间复杂度较低，但在 大多数情况下两者较为接近； 而本发明提出的匹配方法， 如果参数选择得当 （m和 L较小的情况下， 如 m=8， L=6 ) ， 匹配速度可以达到基于 KdTree的匹配算法的 1 0倍以上。

专业人员应该还可以进一步意识到， 结合本文中所公开的实施例描述的 各示例的单元及算法步骤， 能够以电子硬件、 计算机软件或者二者的结合来 实现， 为了清楚地说明硬件和软件的可互换性， 在上述说明中已经按照功能 一般性地描述了各示例的组成及步骤。 这些功能究竟以硬件还是软件方式来 执行， 取决于技术方案的特定应用和设计约束条件。 专业技术人员可以对每 个特定的应用来使用不同方法来实现所描述的 功能， 但是这种实现不应认为 超出本发明的范围。

结合本文中所公开的实施例描述的方法或算法 的步骤可以用硬件、 处理 器执行的软件模块， 或者二者的结合来实施。 软件模块可以置于随机存储器 ( RAM ) 、 内存、 只读存储器（ROM ) 、 电可编程 R0M、 电可擦除可编程 R0M、 寄存器、 硬盘、 可移动磁盘、 CD-ROM , 或技术领域内所公知的任意其它形式 的存储介质中。

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