基于分布式和暴力匹配的室外大规模物体识别方法和系统

摘要

本发明公开了一种基于分布式处理和暴力匹配的室外大规模物体识别方法和系统，首先终端采集当前场景的待识别图像以及GPS信息，提取所述待识别图像的局部特征，并转化为描述符特征向量，将待识别图像的GPS信息以及描述符特征向量打包成一个描述符文件，发送给分布式处理系统；分布式处理系统根据GPS信息查询当前正在处理的匹配任务中是否存在相同的匹配任务，如果没有则在数据库中搜索与待识别图像相关的样本图像的样本特征向量，分摊加载到多个计算节点中并进行匹配，匹配率最高样本图像就是匹配图像反馈给终端。使用本发明能够实现智能终端的大规模图像识别和检索，而且减少了数据运算量，提高了图像识别和检索的速度。

说明书

技术领域

本发明属于移动增强现实技术领域，具体涉及一种基于分布式处理和暴力 匹配的室外大规模物体识别方法和系统。

背景技术

物体识别的本质就是建立一个能够识别出图像中感兴趣物体类别的计算系 统，在现实生活中有着广泛的应用需求，具有相当高的应用价值和研究意义。

随着互联网的发展，人类正在步入一个信息化的社会，互联网已经成为人 类发布、获取、交换信息的重要平台。互联网上信息量的指数级增长，使得如 何让用户能够快速准确地在海量的数据中找到其所需信息成为了一个重要的课 题。近些年来，随着数字摄影和存储设备的进步和普及，室外的图像数量在互 联网上的飞速增长，也已经达到成千上万了。如何有效的利用这些数据信息， 给当前处于相同位置的用户提供这些已有的信息，是商业界和学术界的一个重 要研究方向。然而，随着图像库规模的极大增长，要保证图像搜索的实时性， 相应的数据库索引技术和图像检索技术也必须做相应的调整或加速。

同时计算机软、硬件技术的迅猛发展，为增强现实技术走出室内应用进而 支持复杂的分析、决策和管理打下了坚实的基础。一些移动终端设备（像PDA、 智能手机等）的功能也越来越丰富，并且拥有了嵌入式操作系统、触摸屏、GPS 定位、视频摄像头等功能，同时也具备了较强的计算和处理能力。这些功能的 集成为开发基于移动终端的增强现实系统奠定了基础。据有关资料，截止到2010 年我国移动电话用户可达7.4亿，其中拥有智能手机的用户占了相当的比重， 智能手机作为增强现实的应用平台将具有很大的应用潜力。3G网的逐步开通、 运行，意味着移动增值业务全新时代的开始，增强现实技术和LBS相结合可以 实现信息的实时交互、三维动态显示，可使人机界面更加友好和具有智能性。

基于上述分析，结合具有摄像头的终端以及服务器端的图像搜索和匹配技 术，可以将大规模物体的在线识别变为可能，而且结合分布式处理技术可以大 大缩短在线识别时间。

发明内容

有鉴于此，本发明提供一种基于分布式处理和暴力匹配的室外大规模物体 识别方案，该方案将分布式处理技术与计算机视觉技术相结合使智能终端具备 大规模图像的识别功能，实现智能终端的大规模图像识别和检索，进而实现移 动增强现实的多种应用。而且，本发明利用GPS信息缩小数据匹配范围，减少 了数据运算量，从而进一步提高了图像识别和检索的速度，实现了在线实时的 室外大规模物体识别。

该方案是这样实现的：

首先提供了一种基于分布式处理和暴力匹配的室外大规模物体识别方法， 预先获取带GPS信息的样本图像，提取每幅样本图像的局部特征并转换为描述 符特征向量，称为样本特征向量，将GPS信息、样本图像信息与样本特征向量 对应存储到样本文件系统中；

所述的识别方法包括如下步骤：

步骤1：终端采集当前场景的待识别图像以及GPS信息；

步骤2：提取所述待识别图像的局部特征，并转化为描述符特征向量；

步骤3：将待识别图像的GPS信息以及描述符特征向量打包成一个描述符 文件，发送给分布式处理系统；

步骤4：分布式处理系统中设有调度处理集群、多个计算节点和所述样本文 件系统；调度处理集群接收到所述描述符文件后，从该描述符文件中提取GPS 信息，在调度处理集群内查询当前正在处理的匹配任务中是否存在与提取的 GPS信息相同的匹配任务，如果是，说明已经将与待识别图像相关的样本特征 向量加载到各计算节点中，则将描述符文件发送给每个计算节点，然后执行步 骤6；否则，执行步骤5；

所述匹配任务的查询标准为：如果当前正在处理的匹配任务对应的GPS信 息与待识别图像的GPS信息一致或者相差一个预设阈值，则认为存在相同的匹 配任务；

步骤5：调度处理集群为待识别图像加载相关的样本特征向量：

以待识别图像的GPS信息为圆心，按照预先设定的筛选半径确定一个圆形 区域，从样本文件系统中筛选出GPS信息在所述圆形区域内的样本特征向量， 将筛选出的样本特征向量分摊加载到各个计算节点中；同时，调度处理集群还 将描述符文件发送给每个计算节点；

步骤6：每个计算节点从描述符文件中解析出待匹配描述符特征向量，将待 识别图像的待匹配描述符特征向量与已加载的与该待识别图像相关的样本特征 向量进行逐个匹配即暴力匹配，将匹配结果汇总到调度处理集群；

步骤7：调度处理集群统计各个计算节点的匹配结果，选出匹配比率最高的 样本图像作为匹配图像，将匹配图像的信息返回给所述终端。

本发明还提供了一种基于分布式处理和暴力匹配的室外大规模物体识别系 统，包括分布式处理系统、无线网络和具有图像采集和GPS定位功能的终端； 分布式处理系统包括交换设备、调度处理集群、至少2个计算节点和样本文件 系统；调度处理集群通过交换设备接入无线网络，并且与样本文件系统、所有 的计算节点连接；

所述样本文件系统，预先存储有各类场景的样本图像以及每幅样本图像的 描述符特征向量，称为样本特征向量，还有样本图像的GPS信息；样本图像的 GPS信息、样本图像信息和样本特征向量对应存储；

所述终端，用于采集当前场景的待识别图像以及GPS信息，提取所述待识 别图像的局部特征，并转换为描述符特征向量；将待识别图像的GPS信息以及 描述符特征向量打包成一个描述符文件，发送给分布式处理系统；

所述调度处理集群，用于在接收到所述描述符文件后，从该描述符文件中 提取GPS信息，查询当前正在处理的匹配任务中是否存在与提取的GPS信息相 同的匹配任务，如果是，说明已经将与待识别图像相关的样本特征向量加载到 各计算节点中，则将描述符文件发送给每个计算节点；否则，为待识别图像加 载相关的样本特征向量；

其中，所述匹配任务的查询标准为：如果当前正在处理的匹配任务对应的 GPS信息与待识别图像的GPS信息一致或者相差一个预设阈值，则认为存在相 同的匹配任务；

所述为待识别图像加载相关的样本特征向量为：以待识别图像的GPS信息 为圆心，按照预先设定的筛选半径确定一个圆形区域，从样本文件系统中筛选 出GPS信息在所述圆形区域内的样本特征向量，将筛选出的样本特征向量分摊 加载到各个计算节点中；同时，调度处理集群还将描述符文件发送给每个计算 节点；

所述计算节点，用于从描述符文件中解析出待匹配描述符特征向量，将待 识别图像的待匹配描述符特征向量与已加载的与该待识别图像相关的样本特征 向量进行逐个匹配即暴力匹配，将匹配结果汇总到调度处理集群；

所述调度处理集群进一步用于，统计各个计算节点的匹配结果，选出匹配 比率最高的样本图像作为匹配图像，将匹配图像的信息返回给所述终端。

有益效果：

本发明基于分布式系统的大规模的物体识别方法，使用成熟的分布式架构， 实现基于视觉的增强现实，能够使用智能设备实时获取当前场景的图像，通过 对图像提取局部特征和进行暴力匹配，实时准确地识别出当前场景，进而为提 供进一步的附加信息奠定了基础，可以扩展智能终端的交互式应用，满足了旅 游、导航、交通、酒店服务等在智能终端上的扩展应用，使网络运营商和内容 提供商能够利用其丰富的服务器资源和优越的服务器性能发展其业务。

本发明在为当前任务加载样本特征向量时，根据GPS信息判断是否已经由 类似或相同的任务，如果有，不需要再次加载，直接采用已经加载的样本特征 向量即可，节省了加载数据的时间。

而且在加载样本特征向量时，只加载一定范围内的样本特征向量，这样可 以进一步缩小运算量。

附图说明

图1为本发明基于分布式系统与暴力匹配的大规模物体识别原理图；

图2（a）为非结构化存储的示意图；

图2（b）为结构化存储的示意图；

图3为本发明识别系统的组成结构示意图。

具体实施方式

下面将结合附图对本发明的物体识别分析方法做详细描述。

图1示出了本发明的基于分布式系统和暴力匹配的增强现实（AR）物体识 别方法的原理图。如图1所示，实现该方法的系统包括分布式处理系统、无线 网络、具有图像采集和GPS定位功能的终端。终端和分布式处理系统通过无线 网络互通。分布式处理系统具体包括交换设备（网关）、调度处理集群、多个计 算节点和样本文件系统。调度处理集群通过网关接入无线网络，并且与样本文 件系统、所有的计算节点连接。

基于上述系统，本发明的具体实现流程如下：

识别之前的准备工作：预先获取带GPS信息的样本图像，一般来说可以按 场景获取图像，例如从网络或实地拍摄，每个场景从不同角度获取几幅样本图 像，场景的GPS信息就是样本图像的GPS信息。提取每幅样本图像的局部特征 并转换为描述符特征向量，称为样本特征向量，将GPS信息、样本图像信息与 样本特征向量对应存储到样本文件系统中。

识别过程如下：

步骤1：用户打开终端的拍摄设备，终端采集当前场景的待识别图像；再调 用终端的GPS传感器接口，获取当前位置的GPS信息。

步骤2：为了降低运算量，终端对采集到的待识别图像进行降采样处理（即 降低分辨率），以降低图像分辨率；然后再采用局部特征检测算法（SIFT、SURF 或ORB）进行特征点检测，以提取所述场景图像的局部特征，再用特征向量的 形式表现，称为描述符特征向量。一幅图像可能有上百个描述符特征向量。

步骤3：将待识别图像的GPS信息以及全部描述符特征向量以及特征向量 个数打包成一个描述符文件，GPS信息和特征向量个数放在文件的开头，特征 向量个数便于接收端判断一个描述符文件是否接收完毕。然后将描述符文件通 过无线网络发送给分布式处理系统。

步骤4：分布式处理系统中的调度处理集群通过网关接收到描述符文件后， 从该描述符文件中提取GPS信息，在调度处理集群内查询当前正在处理的匹配 任务中是否存在与提取的GPS信息相同的匹配任务，如果是，说明已经将与待 识别图像相关的样本特征向量加载到各计算节点中，则将描述符文件发送给每 个计算节点，然后执行步骤6；否则，执行步骤5。

匹配任务的查询标准为：如果当前正在处理的匹配任务对应的图像GPS信 息与待识别图像的GPS信息一致或者相差一个预设阈值，则认为存在相同的匹 配任务。其中，当前正在处理的匹配任务可以缓存在一个调度列表中以便查询。

步骤5：调度处理集群为待识别图像加载相关的样本特征向量。具体为：

以待识别图像的GPS信息为圆心，按照预先设定的筛选半径确定一个圆形 区域，从样本文件系统中筛选出GPS信息在所述圆形区域内的样本特征向量， 将筛选出的样本特征向量分摊加载到各个计算节点中；同时，调度处理集群还 将描述符文件发送给每个计算节点。其中，筛选范围可以为10米、20米、30 米、40米或50米。

步骤6：每个计算节点从描述符文件中解析出待匹配描述符特征向量，将待 识别图像的待匹配描述符特征向量与该待识别图像相关的已加载样本特征向量 进行逐个匹配即暴力匹配，将匹配结果汇总到调度处理集群。

其中，这里所述的“与该待识别图像相关的已加载样本特征向量”就是GPS 信息在圆形区域内的样本特征向量，它们参与待识别图像的暴力匹配。对于在 步骤4中找到相同匹配任务的待识别图像，哪些样本特征向量参与其暴力匹配 可以由计算节点根据已加载样本向量的GPS信息再次判断，其判断计算量很小， 不会影响计算速度；当然，也可以由调度处理集群告知计算节点哪些样本特征 向量参与暴力匹配。

步骤7：调度处理集群统计各个计算节点的匹配结果，选出匹配比率最高的 样本图像作为匹配图像，将匹配图像的信息返回给所述终端。此后，终端可以 显示上述识别结果，用户可以点击上述分类结果，查看详细信息。

暴力匹配就是通过穷举的方法，将待匹配特征向量与样本向量的所有描述 符进行逐个对比，计算向量的距离，求取距离最近的特征向量。通常判断两个 特征点是否匹配，是通过设定一个全局的阈值，当特征描述距离小于等于该阈 值的两特征点为匹配点，实验表明这种方法会产生大量的误匹配。一种更好的 方法是计算最近邻与次近邻的比值来确定这两个特征点是否匹配，如果这个比 值小于某个阈值，则表示两特征点匹配，实验证明方法非常有效。本发明也可 以该种特征点匹配方法。下面会分别进行详细描述。

至此，本流程结束。

在上述流程中，向终端返回的匹配图像信息可以是图像ID，也可以是图像 本身或者与匹配图像有关的其他信息。如果返回的是图像本身，还需要在样本 文件系统中存储样本图像。那么如图1所示，样本文件系统中建立图像库和特 征库。为每个场景采集的带GPS信息的样本图像可以存储在图像库中，图像库 记载样本图像、样本图像ID、以及样本图像采集地点的GPS信息。而根据样本 图像提取的样本特征向量存储在特征库中，特征库记载样本图像ID、样本图像 对应的样本特征向量、以及样本图像采集地点的GPS信息。

在实际中，样本文件系统中的特征库可以采用结构化或非结构化方式存储。 下面介绍这两种存储方式，以及针对每种存储方式设计的较优的特征向量匹配 方案。

（1）采用非结构化方式存储样本特征向量：

如图2（a）所示，采用文件块组织数据，每个描述文件块对应一个场景， 与该场景相关的样本特征向量均存储在同一个描述文件块中。参见附图，描述 文件块存储对应场景的GPS信息、针对该场景获取的样本图像数量，每个样本 图像的ID、每个样本图像对应的样本特征向量和样本特征向量数量。

由于以描述文件块为单位存储特征向量，且描述文件块的读取操作需要自 行设计，速度较慢，因此每次载入一个描述文件块，匹配完再载入另一个描述 文件块比较合适。那么本发明的步骤6和7的较佳处理方式为：

①每个计算节点接收载入的描述文件块和终端发来的描述符文件，从描述 符文件中解析出待匹配描述符特征向量；以样本图像为单位，用待匹配描述符 特征向量逐个与单个样本图像的所有样本特征向量进行匹配，统计匹配率，即 匹配成功的特征向量数量占单个样本图像的所有样本特征向量的比例，将匹配 率汇总到调度处理集群；然后再载入一个描述文件块，将匹配率汇总到调度处 理集群，直到处理完所有的相关文件块。

②调度处理集群从所有计算节点反馈的匹配率中的寻找最大匹配率，最大 匹配率对应的样本图像就是匹配图像；

③将匹配图像的信息返回给所述终端。

（2）采用结构化方式存储样本特征向量：

如图2（b）所示，样本特征向量以记录的形式存储。每个记录存储一条样 本特征向量；各条记录的格式相同。对于结构化存储，较佳的加载方式为根据 索引进行快速加载。因此，每条记录的内容包括：引ID、样本图像ID、GPS信 息、样本特征向量序号、样本特征向量。

其中索引ID的构建方式是常规技术手段，在识别前的准备阶段，在样本文 件系统中存储索引表，该索引表记载了GPS信息与记录存储位置的索引关系。 那么根据GPS信息查找索引表就可以将GPS信息在圆形区域内的所有记录内容 加载到各个计算节点中。在建立索引时，也可以采用多个计算节点进行分布式 计算，以节省计算时间；同理对图像库中的图像进行特征提取也可以采用分布 式计算的方式实现。

由于以记录为单位存储特征向量，且建立了索引表，因此可以采用已有的 数据库技术进行快速读取记录并加载到计算节点中，速度较快，因此可以直接 将所有与待匹配图像相关的记录均加载到计算节点中。那么本发明的步骤6和7 的较佳处理方式为：

①每个计算节点从描述符文件中解析出待匹配描述符特征向量，找一个待 匹配描述符特征向量x与加载到自身的所有样本特征向量逐一进行匹配，找到 与描述符特征向量x最近的样本特征向量A和次近的样本特征向量B，并汇总 到调度处理集群进行整体排序，找到与描述符特征向量x最近的样本特征向量A’ 和次近的样本特征向量B’，计算A’与B’的比值，如果该比值小于预设阈值，则 确定样本特征向量A’为描述符特征向量x的匹配点；

②针对每个待匹配描述符特征向量均进行上述操作，然后调度处理集群针 对每个样本图像，计算匹配点占该样本图像的比例，比例最高的样本图像就是 匹配图像；

③将匹配图像的信息返回给所述终端。

实际上，无论是结构化存储还是非结构化存储，以上两种匹配过程均适用， 只是相对来说，结构化存储优选后者，非结构化存储优选前者。

在分布式系统里面，除各个计算单元之间进行分布式计算意外，计算单元 里面还可以进行并行计算。这样1000幅样本图像的描述符，例如用10个计算 单元，每个计算单元承担100个样本的匹配任务，每个计算单元开辟10个并行 计算的线程，每个线程承担10个样本图像的匹配任务，这样对1000样本图像 进行匹配时只需要10个图像暴力匹配的时间，通常在四核的CPU2.8G，内存为 8G的机器上，图像分辨率为320×240,用SIFT描述符对10个样本图像进行匹 配，消耗时间为126ms左右。所以，用分布式系统对大规模图像进行匹配能达 到很好的实时性，同时用暴力匹配的方式进行特征点最近邻查找，能实现较高 的匹配精度。

在上述流程中，涉及智能终端拍摄视频图像，处理并显示来自网络端的分 布式系统服务器发送的返回结果，这些步骤在目前的智能终端上均已经广泛实 施，这些已有实施方式均可用于本发明，且本发明的视频图像拍摄、处理并显 示来自网络服务器端的数据不限于现有的方式。

基于上述方法可知，本发明提供的室外大规模物体识别系统中各组成模块 的功能为：

所述样本文件系统，预先存储有各类场景的样本图像以及每幅样本图像的 描述符特征向量，称为样本特征向量，还有样本图像的GPS信息；样本图像的 GPS信息、样本图像信息和样本特征向量对应存储；

所述终端，用于采集当前场景的待识别图像以及GPS信息，提取所述待识 别图像的局部特征，并转换为描述符特征向量；将待识别图像的GPS信息以及 描述符特征向量打包成一个描述符文件，发送给分布式处理系统；

调度处理集群，用于在接收到所述描述符文件后，从该描述符文件中提取 GPS信息，按照前述查询标准查询当前正在处理的匹配任务中是否存在与提取 的GPS信息相同的匹配任务，如果是，说明已经将与待识别图像相关的样本特 征向量加载到各计算节点中，则将描述符文件发送给每个计算节点；否则，为 待识别图像加载相关的样本特征向量；其中，为待识别图像加载相关的样本特 征向量的具体方式与方法流程中的描述相同，这里不赘述。

计算节点，用于从描述符文件中解析出待匹配描述符特征向量，将待识别 图像的待匹配描述符特征向量与为该待识别图像加载的样本特征向量进行逐个 匹配即暴力匹配，将匹配结果汇总到调度处理集群；

调度处理集群进一步用于，统计各个计算节点的匹配结果，选出匹配比率 最高的样本图像作为匹配图像，将匹配图像的信息返回给所述终端。

优选地，终端在提取所述待识别图像的局部特征之前，进一步对所述待识 别图像进行降采样处理，以降低图像分辨率。

综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保 护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等， 均应包含在本发明的保护范围之内。