基于超像素的图像的实际货架图景象分析

摘要

本发明公开了一种基于超像素的图像的实际货架图景象分析。所包括的图像识别系统接收包括多个被组织的对象的实际货架图图像，并且检测和识别零售货架上的一个或多个货品的实际货架图图像中的对象，识别货架前端和货架前端上的标签，识别货架下的空闲空间，识别可能存在未被识别的产品的区域，以及识别产品“缺货”的区域。

说明书

背景技术

本公开文本主要涉及图像处理中的对象检测的领域，本公开文本尤其涉及用于分 析多个被组织的对象的图像的系统和方法，以识别图像中的对象、货架前端和货架前端上 的标签、货架之下的空闲空间、可能存在未识别出的对象的区域和空置区域。

发明内容

所述技术包括接收多个被组织的对象的图像的图像识别系统。图像识别系统基于 多个被组织的对象的图像中的各组像素生成图像分段(例如，超像素)，并且利用从对多个 被组织的对象的图像进行的图像分析得到的信息和观察值对图像分段加标签。此外，系统 基于图像分段对多个被组织的对象的图像的区域进行分类。区域例如可以包括图像中的识 别出的对象、货架前端和标签、货架之下的空闲空间、可能存在未识别出的对象的区域、以 及产品“缺货”的区域。

其他实施例包括用于识别图像中的对象的对应的方法和计算机程序产品。本文中 描述的特征和优势并不是完全包括形式的，并且许多额外的特征和优势对于阅读了本说明 书和附图的本领域技术人员而言是清楚的。此外，还应当注意的是，本说明书中选用使用的 词语主要用于易于理解本申请和指示性的目的，而并不限制本申请的范围。

附图说明

通过附图中的示例非限制性地描述本申请，在附图中，相似的附图标记用于指代 相似的单元。

图1是说明了用于分析零售货架的图像的系统100的一个示例性实施例的高层框 图；

图2是说明了包括实际货架图(realogram)分析应用的示例性实际货架图分析系 统的框图；

图3是基于超像素的实际货架图景象分析的示例方法的流程图；

图4说明了示例性的实际货架图；

图5A示出了包括货架和货架上的产品的示例性的实际货架图；

图5B示出了叠加有超像素的示例性的实际货架图；

图6是用于基于超像素以及在一些实施例中的其他观察值来识别实际货架图区域 的示例性方法的流程图；

图7A和图7B示出了用于识别实际货架图图像中示出的货架前端的示例性方法的 流程图；

图8示出了叠加有超像素以及示出了用于确定货架外观特征的超像素之间的关系 的箭头的示例性实际货架图的一部分；

图9是用于检测可能的货架边界的处理的示例性图示；

图10是以各自的角度示出了超像素列表的示例性图示；

图11是示出了用于确定货架外观特征的超像素之间的关系的示例性图示；

图12A是示出了超像素边界处的量化梯度的示例性图示；

图12B是示出了一对超像素的量化梯度的示例性数据结构；

图13是用于检测和确定实际货架图图像中示出的货架前端上的标签的位置的示 例性方法的流程图；

图14A是示出了叠加有超像素的示例性实际货架图的一部分，其中所述超像素被 编号以示出货架分段的集群；

图14B是示出了叠加有超像素的示例性实际货架图的一部分，其中所述超像素被 编号以示出货架分段的集群；

图15是示出具有最少超像素和具有最多非水平线的超像素的集群之间的交叉的 示例性图示；

图16示出了叠加有超像素的连通分量的示例性的实际货架图的一部分，其中所述 连通分量被编号以示出货架超像素的集群并且示出假设的标签位置；

图17是用于确定实际货架图图像中的多个特定对象的存在和位置的示例性方法 的流程图；

图18示出了图中的多个匹配点的描述符差异的示例性条形图；

图19A示出了相同高度的货品的堆叠的示例性图示；

图19B示出了叠加有识别出图中的未被索引的对象的边界框的示例性实际货架图 的一部分；

图20是用于在实际货架图图像中找到空闲空间的示例性方法的流程图；

图21A示出了识别通过分段算法分段的“缺货”和“其他”区域的示例性实际货架图 的一部分；

图21B示出了识别“缺货”和“其他”区域的示例性实际货架图的一部分；

图22示出了识别被扩展有超像素的“缺货”和“其他”区域的示例性实际货架图的 一部分；

图23A和图23B分别示出了在进行分段算法的1次迭代和10次迭代之后指示缺货或 其他区域的被叠加有超像素的示例性实际货架图；

图24是示出了用于潜在未知产品的被叠加有连通分量多边形的示例性实际货架 图；

图25是用于从图像中提取价格的示例方法的流程图；以及

图26以表格示出了货架假设的示例。

示出了本文中描述的本申请各个实施例的附图仅用于说明目的。从以下论述中容 易理解的是，可以采用本文中说明的结构和方法的替代实施例，而不偏离本文中描述的技 术的主旨。

具体实施方式

图1是说明了用于分析零售货架的图像的系统100的一个示例性实施例的高层框 图。所示的系统100包括成像设备115和实际货架图分析服务器101。在所示的实施例中，经 由网络105可通信地耦接系统100的实体。

网络105可以是常规类型的有线或无线网络，并且可以具有各种不同的配置，包括 星形配置、令牌环配置或其他配置。此外，网络105可以包括局域网(LAN)、广域网(WAN)(例 如互联网)和/或其他互连的数据路径，其中多个设备可以跨过网络105进行通信。在一些实 施例中，网络105可以是对等网络。网络105还可以耦接到或包括通信网络的一部分，用于以 各种不同的通信协议发送数据。在一些实施例中，网络105包括用于发送和接收数据的蓝牙 通信网络或蜂窝通信网络，包括经由短消息服务(SMS)、多媒体消息服务(MMS)、超文本传输 协议(HTTP)、直接数据连接、WAP、电子邮件等。尽管图1中所示的一个网络105耦接到了成像 设备115和实际货架图分析服务器101，但在实际上一个或多个网络可以连接到这些实体。

在所示的实施例中，系统100包括与网络105耦接的实际货架图分析服务器101。实 际货架图分析服务器101可以是计算设备，该计算设备包括处理器、存储器、网络通信能力 和数据存储(例如数据存储143)。在图1的示例中，实际货架图分析服务器101的组件被配置 为实现实际货架图分析应用103，在下文中对此进行更详细地描述。实际货架图分析服务器 101可以从成像设备115或从另一个源接收例如经由互联网浏览器或电子邮件等上传的一 个或多个图像以进行分析。尽管图1的示例包括一个实际货架图分析服务器101，但系统100 也可以包括一个或更多的实际货架图分析服务器101。

数据存储143是存储用于提供本文中描述的功能的数据的非暂时性存储器。数据 存储143可以是动态随机存取存储器(DRAM)设备、静态随机存取存储器(SRAM)设备、闪速存 储器或一些其他的存储器设备。在一些实施例中，数据存储143还可以包括非易失性存储器 或其他类似的永久性存储设备和介质，包括硬盘驱动器、软盘驱动器、CD-ROM设备、DVD-ROM 设备、DVD-RAM设备、DVD-RW设备、闪速存储器设备或其他一些大容量存储设备，用于更持久 地存储信息。

在一个实施例中，数据存储143存储由实际货架图分析服务器101接收的图像和与 图像相关联的数据，以供实际货架图分析服务的用户访问。例如，数据存储143可以与所接 收到的图像一起存储图像分析结果，并且可以被经由网络105访问。尽管图1中的示例包括 单个数据存储143作为实际货架图分析服务器101的部件，但应当理解数据存储可以位于系 统100中的其他位置。例如，离散的存储设备可以经由本地连接或通过网络105耦接到实际 货架图分析服务器101。

在一个实施例中，实际货架图分析应用103包括软件和/或逻辑以检测和识别零售 货架上的一个或多个货品的图像中的对象，识别货架前端和货架前端上的标签，识别货架 下的空闲空间，识别可能存在未被识别的产品的区域，以及识别空闲货架空间(例如产品 “缺货”的区域)。在一些实施例中，可以使用本文中所述的硬件和软件的组合来实现实际货 架图分析应用103。

通过示例使用图1中所示的成像设备115。在一些实施例中，成像设备115可以是计 算设备，包括存储器、处理器和相机，该计算设备例如是膝上型计算机、平板计算机、移动电 话、个人数字助理(PDA)、移动电子邮件设备或网络摄像头等。在其他实施例中，图像捕获设 备可以是数码相机等。尽管图1中示出了单个的图像捕获设备115，但本公开也适用于具有 一个或多个图像捕获设备115的系统结构。

图2是说明了包括实际货架图分析应用103的示例性实际货架图分析系统200的框 图。例如，实际货架图分析系统200可以是实际货架图分析服务器101，如上所述。在图2的示 例中，实际货架图分析系统200包括实际货架图分析应用103、处理器235、存储器237、通信 单元241和数据存储243。实际货架图分析应用103包括对象识别模块201、分段模块203、货 架/标签检测模块205、空闲空间模块207和倍数模块209。在一个实施例中，总线220可通信 地耦接实际货架图分析系统220的组件。总线220可以代表一个或多个总线，包括工业标准 结构(ISA)总线、外围组件互连(PCI)总线、通用串行总线(USB)或现有技术中的提供类似功 能的一些其他总线。

处理器235可以通过执行各种输入/输出、逻辑和/或数学操作来执行软件指令。处 理器235可以具有各种计算结构来处理数据信号，包括例如复杂指令集计算机(CISC)结构、 缩减指令集计算机(RISC)结构、图形处理单元(GPU)和/或实现指令集的组合的结构。处理 器235可以包括单个处理单元或多个处理单元和/或内核。在一些实施例中，处理器235能够 生成电子显示信号并将电子显示信号提供给显示设备，支持图像的显示，捕获并发送图像、 执行复杂任务，所述复杂任务包括各种类型的特征提取和采样等。在一些实施例中，处理器 235可以经由总线220耦接到存储器237来从其访问数据和指令并在其中存储数据。总线220 可以将处理器235耦接到实际货架图分析系统200的其他组件，所述其他组件例如包括对象 识别模块201、分段模块203、货架/标签检测模块205、空闲空间模块207、倍数模块209、存储 器237、通信单元241和数据存储243。显然还可以使用其他的处理器、传感器、显示器和物理 配置。

存储器237可以为实际货架图分析系统200的其他组件存储数据并提供对数据的 访问。存储器237可以被包括在单个计算设备或多个计算设备中，如本文中其他位置所述。 在一些实施例中，存储器237可以存储可以由处理器235执行的指令和/或数据。例如，在一 个实施例中，存储器237可以存储指令，所述指令当被处理器执行时，使得处理器实现实际 货架图分析应用103，包括对象识别模块201、分段模块203、货架/标签检测模块205、空闲空 间模块207和倍数模块209。存储器237还能够存储其他指令和数据，包括例如操作系统、硬 件驱动器、其他软件应用、数据库等。存储器237可以耦接到总线220以与处理器235和实际 货架图分析系统200的其他组件进行通信。

存储器237可以包括一个或多个非暂时性计算机可使用(例如可读、可写等)介质， 其可以是能够包括或存储供处理器235处理或与处理器235相关联的指令、数据、计算机程 序、软件、代码、例程等的任何有形装置或设备。在一些实施例中，存储器237可以包括一个 或多个易失性或非易失性存储器。例如，存储器237可以包括但不限于一个或多个动态随机 存取存储器(DRAM)设备、静态随机存取存储器(SRAM)设备、嵌入的存储器设备、分离的存储 器设备(例如PROM、FPROM、ROM)、硬件、光盘(CD、DVD、蓝光(Blu-ray^TM)等)。应当理解，存储器 237可以是单个设备，或可以包括多种类型的设备和配置。

通信单元241是用于通过将处理器235和实际货架图分析系统200的其他组件耦接 到网络105和其他处理系统来接收和发送数据的硬件。通信单元241被配置为例如接收来自 成像设备115的一个或多个图像和/或分析结果。在一个实施例中，通信单元241可以包括与 网络105或另一个通信通道的直接物理连接的端口。例如，通信单元241可以包括RJ45端口 或与网络105进行有线通信的类似端口。在另一个示例中，通信单元241可以包括无线收发 器(未示出)，用于使用一个或多个无线通信方法(例如IEEE802.11、IEEE802.16、蓝牙 或另一种适当的无线通信方法)经由网络105或任何其他通信通道交换数 据。

在另一个实施例中，通信单元241可以包括蜂窝通信收发器，用于通过蜂窝通信网 络经由例如经由短消息服务(SMS)、多媒体消息服务(MMS)、超文本传输协议(HTTP)、直接数 据连接、WAP、电子邮件或另一种适当类型的电子通信等发送和接收数据。在另一个实施例 中，通信单元241可以包括有线端口和无线收发器。通信单元241还向网络105提供其他的常 规连接，以使用诸如TCP/IP、HTTP、HTTPS和SMTP之类的标准网络协议分发文件和/或媒体对 象。

数据存储243是存储用于提供本文中描述的功能的数据的非暂时性存储器。例如， 数据存储243可以存储从图像捕获设备或其他源接收的图像、图像的分析结果、和在图像分 析中使用的数据结构，该数据结构例如是具有用于识别图像中的对象的特征点的已知的对 象索引。数据存储243可以是动态随机存取存储器(DRAM)设备、静态随机存取存储器(SRAM) 设备、闪速存储器或一些其他的存储器设备。在一些实施例中，数据存储243还可以包括非 易失性存储器或其他类似的永久性存储设备和介质，包括硬盘、软盘、CD-ROM设备、DVD-ROM 设备、DVD-RAM设备、DVD-RW设备、闪速存储器设备或其他一些大容量存储设备，用于更持久 地存储信息。

对象识别模块201包括软件和/或逻辑以检测和识别图像中的对象。尽管在说明书 中作为对象的示例使用了零售货架或显示的图像，但对象也可以是任何环境的图像中的其 他可识别的特征，例如文档或书籍等。对象识别模块201可以根据现有的公共和/或专有的 图像识别算法来检测和识别图像中的对象。例如，对象识别模块201可以使用计算机视觉 BoW(词袋，BagofWords)方法来将所检测到的对象与数据存储243上的搜索数据库中存储 的已知对象的图像进行匹配。例如，使用尺度不变性特征变换(SIFT)算法，对象识别模块 201提取所检测到的对象的特征点，并且将特征点与搜索数据库进行比较。为了比较，基于k 最邻近距离法(k-nearestneighbors，KNN)或类似算法，来匹配所检测到的对象的特征点 和搜索数据库中的图像。

在一些实施例中，可以使用可编程或专门的硬件(包括现场可编程门阵列(FPGA) 或专用集成电路(ASIC))来实现对象识别模块201。在一些实施例中，可以使用可由处理器 235执行的硬件和软件的组合来实现对象识别模块201。在一些实施例中，对象识别模块201 是可由处理器235执行的指令集。在一些实施例中，对象识别模块201是在存储器237中存储 的指令，并且可被处理器235访问和执行。在一些实施例中，对象识别模块201适用于经由总 线220与处理器235、存储器237和实际货架图分析应用103的其他组件进行协作和通信。

尽管图2的示例中所示的实际货架图分析应用103包括单个的对象识别模块201， 但应当认识到一个或多个额外的对象识别模块可以用于产品检测和识别。同样，对象识别 模块201可以顺序或并行处理单独的图像。此外，对象识别模块201可以将从成像设备115接 收的多个图像合并到单个图像中以用于处理。在一些实施例中，对象识别模块201可以对从 成像设备115接收的图像执行识别，同时成像设备115仍捕获要在创建最终实际货架图中使 用的图像。

分段模块203包括软件和/或逻辑以在每个图像中生成多个图像分段(例如，超像 素或粗糙网格等)，以供在图像分析中使用，将在下文中对此进行更详细地描述。将认识到 的是，尽管出于说明的目的在以下示例中可以使用一个或另一个如下技术，但这里所论述 的技术可以适用于各种图像分段和分段方法，包括粗糙网格、超像素等。

货架/标签检测模块205包括用于识别货架前端和货架前端上的产品标签(例如价 格标签、条形码等)的软件和/或逻辑，将在下文中对此进行更详细的描述。空闲空间模块 207包括用于识别实际货架图图像中的货架上的空闲空间以确定产品“缺货”的区域的软件 和/或逻辑，将在下文中对此进行更详细的描述。倍数模块209包括用于检测利用对象识别 模块201并未识别出的具有类似特征的多个对象并且将对象识别为未知或未被识别出的产 品的软件和/或逻辑。

可以使用可编程或专门的硬件(例如现场可编程门阵列(FPGA)或专用集成电路 (ASIC))或使用可由处理器235执行的硬件和软件的组合来实现实际货架图分析应用103的 各个模块。例如，模块可以是在存储器237中存储的指令集，并且可被处理器235访问和执 行。在下文中更详细地描述各个模块的功能。

图3是基于超像素的实际货架图景象分析的示例方法300的流程图。在一些实施例 中，图像可以被划分为超像素。在一些实施例中，方法300用于识别图像中的特征，例如商店 中的货架的实际货架图。实际货架图(例如图4中所示的实际货架图)是表示货架图 (planogram)的主体的实际生活实现的图。表示货架图是零售环境中显示的产品的视觉表 示，例如货架单元上的产品的放置和数量。在本文中使用的词语“表面”是产品的堆叠(或并 不作为堆叠的一部分的单个产品)。在表示货架图(例如，计划的产品布局的表示)中，如果 表面具有多于一个产品，则这些产品是相同的。在实际货架图(例如，商店中的实际产品布 局的图像)中，表面可能具有不同的产品。方法300可以用于例如在实际货架图中确定货架 的位置、标签、被索引的产品(例如，被索引以利用图像识别算法识别的产品)、未被索引的 产品(例如，未被索引以利用图像识别算法识别的产品)、空闲空间(例如产品缺货的区域) 等。

图4说明了示例性的实际货架图(例如，商店货架上的产品的图像)。在图4的示例 中，图像中的产品包括多个盒子的各种护牙产品。然而，应当认识到，图像可以包括要由实 际货架图分析应用103检测和识别的任何数量、尺寸和变形的产品(或其他对象)。示例性的 实际货架图还示出了未被索引的产品402、被索引的产品(例如利用边界框标示的产品)和 缺货区域404。在一些实施例中，审计/销售人员代表可以使用成像设备115(例如膝上型计 算机、平板计算机、移动电话、个人数字助理(PDA)、移动电子邮件设备、网络摄像头或数码 相机等)捕获实际货架图图像。在一个实施例中，审计/销售人员代表在零售商店处捕获大 型货架的多个图像，其中每个图像覆盖货架的一部分，实际货架图分析应用103可以将这些 图像合并在一起或顺序或并行地进行分析，将在下文中对此进行描述。在其他实施例中，可 以由自动的图像捕获设备自动捕获实际货架图。例如可以周期性地进行该自动图像捕获。 尽管这里的示例将实际货架图描述为货架的图像(例如零售显示)，但应当理解图像可以包 括被组织的对象的任何布置。例如，图像可以是仓库、库房、储藏室、陈列室等的图像。类似 地，除了零售产品之外，对象还可以是在制造、建造或维护中使用的工具或部件、医药用品、 急救用品、紧急或安全设备等。

回到图3的示例，在302处，实际货架图分析应用103接收被组织的对象的实际货架 图图像(例如,零售展示)。例如，图像可以被由成像设备115(例如数码相机、安装在机器人 上的相机等)捕获，并被上传到实际货架图分析应用103以进行分析。

在304处，对象识别模块201可以根据现有的公共和/或专有的图像识别算法来检 测和识别图像中的对象，以将所检测到的对象与在数据存储243上的搜索数据库中存储的 已知对象的图像进行匹配。在一些实施例中，对象识别模块201生成一个或多个图像中的每 个被识别出的对象的被识别出的区域或边界框，并且输出识别结果。在一些实施例中，对象 识别模块201生成作为像素位置的内围层(inlier)的列表，在该列表中，图像中的特征匹配 搜索数据库中存储的特征。在零售货架上的产品的示例中，每个产品的识别结果可以包括 例如对象ID(例如，库存单元(SKU))。每个被识别出的对象的识别结果还包括其他信息，该 其他信息包括对象识别模块201识别出产品的可能性。

在306处，分段模块203从实际货架图图像生成超像素。在各个实施例中，分段模块 203可以对同期捕获的实际货架图图像或先前捕获并被存储在数据存储中实际货架图图像 进行访问并创建超像素。在本文中使用的超像素是包括一组像素的图像的分段。超像素还 可以被称为部分、一部分或区域。例如，超像素是数字图像的紧凑部分，其大于常规像素，其 中每个部分包括大约相同颜色和亮度的像素。使用超像素来对实际货架图图像进行分段的 优势在于通过限制需要分析的离散的数据点(例如超像素对单独像素)的数量简化了图像 的分析。超像素代表纯色区域的粗糙网格以及纯色区域之间的边缘之间良好妥协。与粗糙 网格类似，图像的超像素分段允许选择能够对对象进行良好建模并且帮助生成有用数量的 假设的尺度。超像素算法尝试创建将具有不同纯色的区域分离并且与图像中的主要边缘对 齐的边界，从而通过超像素算法生成的边界是实际对象边界的优秀候选。超像素特别用于 将作为点、线段、边界框等的观察值彼此映射并且映射到局部图像区域。超像素还用于利用 最小邻居模型估计可能性并做决定，将在下文中对此进行更详细的描述。

分段模块203通过基于下层图像的特征将图像分段为紧凑部分，来从被组织的对 象的图像(例如实际货架图)生成超像素。在各个实施例中，分段模块203可以使用各种已知 算法来生成超像素。例如，分段模块203可以使用简单线性迭代集群(SLIC)算法、经由能量 驱动的采样提取的超像素(SEEDS)算法、超像素轮廓算法或其他已知的公共和/或专属的超 像素生成算法。

在一些实施例中，为了提高计算效率并减少生成超像素过程中每像素的噪声，实 际货架图分析应用103将所接收到的实际货架图图像缩放到减少的分辨率。在一些实施例 中，可以通过每个维度中的因数2、3、4等缩放具有至少1000像素或更大像素的最小维度的 图像，使用这些因子中的最大的一个，使得最小维度介于500和1000像素之间。例如，对于具 有3264×2448像素的图像(例如最小维度2448)，可以使用因数4以将图像缩放到816×612 像素的尺寸。

在一个实施例中，基于物理产品尺寸与实际货架图图像中的产品的像素维度的比 率来确定缩放因数。可以使用来自特定产品的图像识别结果的信息(其可以识别产品并给 出像素中的图像位置)和与这些产品相关的尺寸知识来确定大致比率。例如，可以缩放图 像，使得大约14个像素对应于一英寸。

图5A示出了包括货架和货架上的产品的示例性的实际货架图。图5B示出了叠加有 由分段引擎203生成的超像素(例如超像素)的示例性实际货架图。

返回到图3的示例，在307处，实际货架图分析应用103利用其它观察值为超像素加 标签。在一些实施例中，分段模块203可以利用额外的信息或观察值为超像素加标签。例如， 分段模块203还可以包括与预期的产品相关的知识(例如尺寸(长宽高))和/或产品是被展 示在货架还是被悬挂、特定产品的图像识别结果、被分组到表面(例如堆叠)的特定产品的 图像识别结果、以及图像中检测到的线段。在一些实施例中，特征(例如用于为超像素加标 签的其他观察值)是纯色区域、纯色区域之间的边缘、主要边缘、点、线段、边界框、类似颜色 或亮度的区域等。在一个实施例中，可以利用来自特定产品识别结果的结果为超像素加标 签。例如，作为被识别出的产品的边界框的超像素具有被识别出的产品的内围层(例如与用 于产品识别的特征的位置相对应的超像素的一个或多个像素)，位于表面以下，或者与长水 平线段的相交被相应地加标签。在一个实施例中，实际货架图分析应用103使用线分段检测 器(LSD)算法来检测实际货架图图像中的线段。如果水平方向上的程度至少是垂直方向上 的程度的两倍，则确定线段是水平的。在一个实施例中，分段模块203仅利用并未处于被识 别出的产品中的线段来对超像素加标签。在另一个实施例中，分段模块203仅利用比最长的 预期产品更长的线段来对超像素加标签。在另一个实施例中，分段模块203仅利用比最长的 被识别出的产品更长的线段来对超像素加标签。

在308处，实际货架图分析应用103基于超像素并且在一些实施例中还基于其他观 察值来识别实际货架图的区域。例如，其他观察值包括实际货架图的属性，例如对象识别结 果、在实际货架图图像中检测到的线段、超像素的集群(例如基于颜色的集群)或实际货架 图的区域，但也可以使用其他的观察值。使用超像素和其他观察值，实际货架图分析应用 103可以识别区域，例如货架、货架上的标签、具有未被索引的产品的存货区域、缺货区域 和/或在实际货架图图像中呈现的其他区域。在下文中进一步详细描述识别实际货架图的 区域的方法和操作。

在一些实施例中，由实际货架图分析应用103识别出的区域可以是用于零售执行 或用于另一目的关键性能指示符(KPI)。区域还可以用于确定KPI。例如，货架区域可以用于 将通过货架被索引的对象分组为线性组。货架、被索引的对象和未被索引的对象区域可以 用于估计度量，例如货架的份额和种类的份额。

在一些实施例中，图像分段和加标签是可选的，并且实际货架图分析应用103可以 基于图像中检测到的特征点省略这些步骤并且对图像的区域进行分类。图像分析应用103 可以例如使用尺度可变特征变换(SIFT)算法、卷积神经网络(CNN)、深度学习或机器学习等 来识别图像中的特征点。

图6是用于基于超像素以及在一些实施例中的其他观察值来识别实际货架图区域 的示例性方法308的流程图。在各个实施例中，为了基于超像素识别实际货架图的区域，实 际货架图分析引擎103及其组件将观察值分配给超像素作为属性，基于超像素生成具有模 型的假设，对超像素验证带有模型的假设，并且输出分析结果。在以下附图中详细地解释实 际货架图景象分析的此生成。在602处，货架/标签检测模块205识别被组织的对象的图像中 示出的货架的前端。在一些实施例中，货架/标签检测模块205可以基于图像中的像素组来 识别特征，并且创建和估计与可能的货架位置相关的假设。例如，货架/标签检测模块205就 可以使用在下文中更详细地描述的方法来确定货架的位置。

在604处，货架/标签检测模块205确定货架前端上的标签的位置。在一些实施例 中，货架/标签检测模块205可以通过基于颜色和其他观察值(例如图像中检测到的线段)将 与货架前端相关联的超像素(例如，如块602中所示)集群到各个组中，来确定货架前端上的 标签的存在和位置。在其他实施例中，货架/标签检测模块205可以使用在图像中识别出的 特征点来确定货架前端上标签的存在和位置。例如，货架/标签检测模块205就以使用参照 图7和图13描述的方法来确定标签的存在和位置。可以从标签提取信息，例如价格、通用产 品代码(UPC)或产品名称等。

在606处，倍数模块209确定具有类似特征的多个对象的存在和位置。该操作特别 适用于对尚未被索引的实际货架图图像中的对象(例如，不属于如上所述的由图像处理器 识别出的那些对象)进行定位。在一些实施例中，倍数模块209将同一图像(例如实际货架 图)中的特征点、集群点对(clusterspointpair)进行匹配，以及在一些实施例中找到相 同或类似产品的产品堆叠(例如垂直的群)、水平的组和/或孤立的实例。例如，倍数模块209 使用参照图17更详细地描述的方法来确定多个对象的存在和位置。

在608处，空闲空间模块207确定货架之下的空闲空间的存在和位置。在一些实施 例中，空闲空间模块207通过确定缺少对象的区域(例如，暗区域、同质颜色区域和/或与货 架的背部相对应的诸如挂板之类的区域)来识别出缺货区域。例如，空闲空间模块207使用 参照图20更详细地描述的方法来确定货架之下的空闲空间的存在和位置。

图7A和图7B示出了用于确定实际货架图图像中示出的货架和标签位置的示例性 方法700的流程图。在701处，货架/标签检测模块205接收多个被组织的对象的图像。如上所 述，图像可以是零售货架或展示的实际货架图图像。

在702处，货架/标签检测模块205基于图像中的像素的组来识别特征。例如，图像 分析应用103可以例如使用尺度可变特征变换(SIFT)算法、卷积神经网络(CNN)、深度学习 或机器学习等来识别图像中的特征点。在其他实施例中，特征可以是基于相邻超像素之间 的梯度的超像素货架特征。本文中使用的超像素货架特征是指这样的超像素，在该超像素 中，超像素边界的一部分可以基于超像素和相邻超像素的边界的特征对应于货架前端的一 部分的顶部或底部边缘。货架/标签检测模块205基于在水平边缘处找到四个相邻超像素的 组来确定超像素是否是超像素货架特征。对于每个超像素，其邻居是其他超像素，在所述其 他超像素中，包括超像素的像素是(8个连接的)邻居。在一个实施例中，货架/标签检测模块 205使用超像素标签的图像尺寸的2D阵列的光栅扫描来找到邻居。在其中3x3邻居的中心与 任何周围环境不同的每个光栅位置处，与中心和超像素对应的超像素或与每个唯一的不同 周围环境相对应的超像素都是邻居。对于该对或该多对邻居，如果该对中的其他超像素并 不处于邻居的列表中，则更新该对/每对的邻居的列表。

在一个实施例中，对于每个超像素，基于超像素的中心和每个邻居的中心的关系 来创建其邻居的九个列表。存在彼此紧密联系的几个中心的一个列表。在当前的实现中，彼 此紧密联系是这样的位置，其中X距离小于所有超像素的中间X宽度，并且Y距离小于所有超 像素的中间高度。对于并未紧密联系的邻居，从超像素到邻居的矢量的角度被量化到0、45、 90、135、180、225、270或315度，并且超像素的八个列表对应于这八个角度。图10是以各自的 角度示出了超像素列表的示例性图示。

在一个实施例中，边缘检测梯度(Sobelgradient)被在图像的X和Y方向上计算， 并且被转换为极(量度和角度)坐标。在一个实施例中，货架/标签检测模块205无关于R、G和 B分量地计算该梯度，并且使用具有最大量度的分量的量度和角度。图12A是示出了超像素 边界处的量化梯度的示例性图示。量度和梯度被量化到九个索引中的一个索引。图12B是示 出了一对超像素的量化梯度的示例性数据结构。当量度小于阈值(例如16)时使用一个索引 (“小量度”索引)。该索引用于指示在它们之间并不具有显著边界的超像素。否则，角度被量 化到0、45、90、135、180、225、270或315度，并且对应的索引被用于这八个角度。这八个索引 指示在它们之间具有显著边界的超像素。

在一个实施例中，对于每对相邻超像素(例如图12A的示例中的S1和S0)以及对于 每个梯度量化值，计数的整数、X坐标和Y坐标被初始化到0。执行超像素标签的图像大小的 2D阵列的光栅扫描。在3x3邻居的中心与任何周围环境不同的每个光栅位置处，邻居和梯度 量化值的对应的对被确定并且被用于指明与每个对相对应的数据结构中的两个位置。对于 每个数据结构位置，计数增加1，并且光栅位置的X和Y坐标被分别在数据结构中增加X和Y 值。在光栅扫描之后，数据结构中的计数值是具有相同量化梯度的一对超像素的边界像素 的数量。最后，通过利用对应的计数进行分割来标准化数据结构中的X和Y值。现在，数据结 构中的X和Y值是具有相同量化梯度的一对超像素的边界像素的中心。

为了确定每个超像素是否为超像素货架特征，货架/标签检测引擎205首先从产品 识别结果中排除被加标签为带有内围层的超像素的超像素。货架/标签检测引擎随后排除 具有带有显著边界的侧边邻居(例如左侧或右侧)的超像素。在一个实施例中，对于左侧或 右侧邻居(带有被量化的角度0或180度的邻居)，检查每个邻居的量化的梯度计数。如果具 有最大计数的索引并不是至少一个邻居的小量度索引，则该超像素并不是超像素货架特征 (例如，邻居具有显著的边界)。其中带有最大计数的索引的邻居是小量度索引的邻居是不 带有显著边界的边侧邻居。

货架/标签检测引擎205随后从剩余的超像素确定“上侧”和“下侧”的超像素货架 特征。如果带有上侧邻居的边界处的梯度(例如，当到邻居的角度被量化到45、90或135度) 是垂直的(例如，梯度角度被量化到90或270度)，则超像素是“上侧超像素货架特征”，存在 不带有显著边界的边侧邻居，该边侧邻居具有带有相同的梯度索引的不同的上侧邻居，超 像素的边界的Y中心及其上侧邻居和边侧邻居的边界的Y中心及其上侧邻居相同地位于阈 值内(例如，小于5个低分辨率像素)。如果带有下侧邻居的边界处的梯度(例如，当到邻居的 角度被量化到225、270或315度)是垂直的(例如，梯度角度被量化到90或270度)，则超像素 是“下侧超像素货架特征”，存在不带有显著边界的边侧邻居，该边侧邻居具有带有相同的 梯度索引的不同的下侧邻居，超像素的边界的Y中心及其下侧邻居和边侧邻居的边界的Y中 心及其下侧邻居相同地位于阈值内(例如，小于5个低分辨率像素)。在图11中示例性地示出 了这种关系。

以下是用于识别实际货架图图像中的超像素货架特征的示例算法：

为每个超像素找到邻居

通过距离和角度分离邻居

获得邻居之间的边界的梯度信息

计算量化的图像梯度

初始化每对邻居的数据结构

累积计数值、X和Y坐标

标准化X和Y坐标

For每个超像素（确定其是否为超像素货架特征）

if超像素具有来自特定产品识别的内围层then

continue

if所有边侧超像素具有显著边界then

continue

if上侧超像素具有显著边界then

如果边界处的最大计数梯度是垂直的then

if不具有显著边界的边侧邻居

具有带有相同最大计数梯度的上侧超像素

then

if超像素和侧边邻居的Y边界位置相同

then

超像素是“上侧超像素货架特征”

if下侧超像素具有显著边界then

if边界处的最大计数梯度是垂直的then

if不具有显著边界的边侧邻居

具有带有相同最大计数梯度的下侧超像素

then

if超像素和侧边邻居的Y边界位置相同

then

超像素是“下侧超像素货架特征”

图8示出了被叠加有超像素和示出了作为超像素货架特征的那些超像素的箭头的 示例性实际货架图的一部分。通过从超像素中心向上指向其上侧边界的箭头来示出上侧超 像素货架特征。通过从超像素中心向下指向其下侧边界的箭头来示出下侧超像素货架特 征。如上所述，基于四个邻近超像素的边界来确定超像素货架特征。在图8的示例中，超像素 802是超像素货架特征，这是因为超像素802及其边侧邻居804之间的梯度较小，并且上侧邻 居806之间的边界指示水平边缘(例如，边界处的最频繁量化的梯度值是相同的垂直方向和 这些边界像素的Y中心类似)。

返回到图7的示例，在704处，货架/标签检测模块205使用特征基于外观识别可能 的货架位置。在一个实施例中，货架/标签检测模块205通过利用颜色对超像素货架特征进 行集群、基于线段找到角度、并使用颜色和角度来搜索超像素以确定货架位置假设，来确定 货架位置假设。下面更详细地描述该处理。在其他实施例中，货架/标签检测模块205通过确 定对应于货架边缘的特征点来识别可能的货架位置。

在各个实施例中，通过使用K平均集群、聚合集群(例如Ward集群)、高斯混合模型 (GMM)、其他已知的专属或公共集群技术、或用于生成和量化到调色板的技术，利用平均颜 色来对超像素货架特征进行集群。在一个实施例中，货架/标签检测模块205使用五个集群 (例如k＝5，5高斯混合模型(GMM)分量)。集群可以基于各种颜色空间，例如RGB或LAB等。在 一个实施例中，货架/标签检测模块205可以可选地忽略被加标签为位于被识别出的产品边 界框内的超像素货架特征的颜色。例如，用于被识别出的产品的边界框中的超像素被加标 签为颜色0，其他超像素货架特征被加标签为颜色1、2、3、4或5。类似地，在一些实施例中可 以忽略悬挂的产品的超像素货架特征。在一个实施例中，货架/标签检测模块205确定每个 集群的灰度或亮度值。例如，货架/标签检测模块205可以从GMM确定平均值，以确定灰度值。 在图9的示例中，在906中是示出了基于颜色对超像素货架特征进行集群的示例。

为了从由货架/标签检测模块205识别出的超像素货架特征中确定可能的货架位 置，模块搜索形成接近水平的线的超像素货架特征，如图9的示例中的902中所示。例如，在 一个示例中，货架/标签检测模块205以0.005弧度为步长搜索从-0.3弧度到+0.3弧度的接 近水平的角度(0.3度为步长的大约-17度到+17度)。货架/标签检测模块205基于长水平线 段(例如，具有接近水平范围内的角度的线段，并非位于被识别出的产品中，并且长于预期 的产品)中其出现的频率以及产品底部边缘中出现的频率通过角度来进行分类。货架/标签 检测模块205以频率角优先的原则来对角度进行分类。如果没有来自长线段或产品的信息， 分类为0弧度（0度，水平）优先。在说明书中，（针对特定假设的）特定迭代下的搜索角度被称 为θ（theta）。

以下是在theta和宽度上搜索超像素货架特征的示例算法：

对于角度搜索中的每个theta

将超像素货架特征坐标转动theta

将超像素货架特征坐标分组到线的仓中

如果为先前的theta已经考虑了组，则继续（可选）

将表面中心和底部坐标转动theta（可选）

将表面中心和底部坐标转换为仓索引

对于每个仓

通过颜色、梯度和顶部/底部来分割超像素货架特征

对于每个分割的仓

对超像素货架特征的数量进行计数

对具有长边缘的超像素货架特征的数量进行计数（可选）

对被识别出的产品中的超像素货架特征的数量进行计数（可选）

对表面之下的超像素货架特征的数量进行计数（可选）

对于厚度搜索中的每个厚度

当前-假设=基于外观评估货架假设

当前-假设+=基于上下文评估货架假设

if当前-假设良好：

if存在先前的良好假设：

融合假设

else

使用当前-假设作为新的假设

对于紧密在一起的每对货架假设：

去除假设

对于每个最佳货架假设：

获得货架边界的坐标

找到假设附近的超像素货架特征，从未来考虑中去除（可选）

如果货架边界良好或如果没有更多的超像素货架特征需要考虑，则中断(可选)

可选地，在一个实施例中，货架/标签检测模块205可以旧的theta值跟踪超像素货 架特征的组，并且仅处理给出不同组的角度。

货架/标签检测模块205创建足够尺寸的仓以将相同水平线(其中水平只是在转动 theta之后水平)上的超像素货架特征边界的坐标分组为与水平线相对应的仓，如图9的示 例的904中所示。在一个实施例中，货架/标签检测模块205使用六个低分辨率像素的仓大 小。例如，模块使用50％的重叠的仓，从而存在转动的Y坐标0..5、3..8、6..11、9..14等的 仓。

如在这里所述的，货架的前边缘的厚度是货架的顶部边缘和货架的底部边缘之间 的距离。在一个示例中，货架/标签模块搜索从4到20的仓索引(对于具有50％重叠的仓而 言，其为以仓尺寸为单位的2到10)。在一个实施例中，“当前-假设良好”标准基于发现的标 签的数量、发现的货架的数量和得分(在一些实施例中为重要性的量级)。如果找到标签的 最小数量(例如3)或如果当前假设优于任何之前的假设，则货架/标签检测模块205确定“当 前-假设良好”。

在一个实施例中，当融合假设时，保持宽度上来自循环的所有假设。或者，当找到 接近于其它假设的假设时，融合以类似的方式仅保留它们中的一部分以选择组中的一个假 设，如下所述。

在考虑所有厚度之后，货架/标签模块205从紧密在一起的每组假设中选择一个假 设。例如，模块205通过考虑假设对来选择假设。考虑各对，以便首先考虑紧密在一起的对。 在一个实施例中，货架之间的最小预期距离用于确定过分紧密在一起的货架假设的对(例 如，如果上部货架的底部和下部货架的顶部之间的距离小于预期距离的话)。在一个实施例 中，货架/标签检测模块205使用最小的预期产品的高度作为货架之间的最小预期距离。在 预期的产品(例如，在搜索数据库中被索引的产品)中找到最小预期的产品。或者，货架之间 的最小预期距离可以是最短的被识别出的产品的高度。或者，在另一个实施例中，最小预期 的高度可以是最短的被识别出的产品的高度的分数，例如最短的被识别出的产品的高度的 一半，以便应对当未被识别出的产品可能短于被识别出的产品时的情况。当选择假设时，具 有类似厚度(例如差别不大于仓尺寸的两倍)的假设可以被作为一个组一起考虑。可选地， 当选择假设时，基于如下所述的超像素货架特征的柱状图的比较具有类似外观的假设可以 被作为一个组一起考虑。

当从过于紧密在一起的一对货架假设去除一个假设时，如果该对假设中的一个假 设的评估基于如下结合706所述的外观(例如基于超像素货架特征得分)并且另一个假设的 评估基于如下接合708所述的上下文(例如表面下的搜索)，则去除来自上下文的一个。否 则，如果较低假设更暗得多(更小的灰度值或亮度，例如对于0..255个像素大于64)，则将其 去除。否则，可以使用用于评估如下所述的假设的其他标准来确定去除哪个。或者，如果货 架/标签检测模块提供与(如下更详细描述的)标签的顶部和底部相关的信息，则标签顶部 和底部位置可以用于对匹配货架顶部和底部位置进行投票，并且可以去除据具有较少票数 的假设。或者，去除具有较少检测到的标签的假设。或者，可以去除假设，从而对于所有剩余 的假设而言货架颜色、标签颜色和/或货架厚度是一致的。

在一个实施例中，考虑到theta的其他值，去除所选择的假设附近的超像素货架特 征。货架之间的最小预期距离用作此情况下附近的阈值。考虑如果小于超像素货架特征的 阈值数(例如6)，在theta上的搜索停止。这应对了当图像中不同货架的角度不同时的情况， 如果成像设备的位置使得货架并不与图像平行，则可能出现这样的情况。

在另一个实施例中，可以使用贪婪算法，一旦在theta的某个值处找到标签，则算 法停止。在另一个实施例中，在所有的超像素货架特征上在theta上搜索继续，并且使用来 自最佳theta值的结果。

货架/标签检测模块从可能的货架位置(例如上述的假设)确定货架位置。如下描 述用于评估和选择假设的示例算法：

对于每对顶部仓和底部仓：

计算该对的得分并且找到最佳颜色

对于图像底部附近的每个顶部仓(可选)：

仅计算顶部的得分并且找到最佳颜色

对于图像顶部附近的每个底部仓（可选）：

仅计算底部的得分并且找到最佳颜色

删除最低得分的邻近对

初始化假设以与最佳颜色和良好得分进行配对

如果颜色匹配并且良好得分，则仅将顶部增加到假设（可选）

如果颜色匹配并且良好得分，则仅将底部增加到假设（可选）

循环（以查找产品之下的更多的货架）（可选）

找到并不由货架支撑的所有表面

if（并非第一次迭代）并且（不存在被支撑的表面）then

break

if所有表面都被支撑则

break

找到可能存在一个货架的仓的范围

找到最佳颜色的范围内的最佳得分

if找到最佳得分then

增加货架位置假设

else

break

获得与每个货架的假设相对应的超像素货架特征

使用超像素货架特征获得货架边界的坐标

找到货架假设中的所有超像素

检测货架上的标签

对于每个货架假设：

对找到的标签的数量进行计数

在706处，货架/标签检测模块205基于外观评估货架位置。通常，如上所述，基于下 述找到货架假设：超像素货架特征，该超像素货架特征代表在线内具有相同颜色的两个平 行线，并且在表面之下还可以具有长水平边缘或具有顶部平行线，或在底部平行线之下具 有更暗的超像素货架特征。可选地，预期货架边缘比货架之下的暗区域较亮，并且暗的超像 素货架特征并不被考虑作为平行线内的超像素货架特征。对于5个集群颜色(带有0...255 的灰度值，其中0是黑色，255是白色)，如果其小于64加上5个颜色的最小灰度值并且小于64 减去5个颜色的最大灰度值，则该颜色为暗。

在一个实施例中，货架/标签检测模块205如下所述计算一对仓(apairofbins) 的得分。对于每个颜色(例如，对于每个GMM分量1、2、3、4和5)，模块找到上部仓的两个垂直 梯度方向的每一个的最大数目的顶部超像素货架特征(例如，被假设为处于货架顶部的那 些超像素货架特征)。而且，模块205还找到具有长水平边缘的超像素货架特征和表面之下 的超像素货架特征的对应计数的最大值。类似地，对于每种颜色，货架/标签检测模块205找 到较低仓的两个垂直梯度方向的每一个的最大数目的底部超像素货架特征。而且，模块205 还找到具有长水平边缘的超像素货架特征的对应计数。可选地，模块205找到更暗(例如， 0..255灰度上的灰度的64个或更多的差异)的底部平行线的顶部超像素货架特征的数量。 例如，对于每个颜色，模块205找到该颜色的顶部和底部计数的最小值。具有最大值的颜色 是最佳颜色(例如，货架假设颜色)，并且最大值是最佳计数。货架/标签检测模块205确定该 假设得分作为所剪切的该颜色的长边缘/表面/更暗超像素货架特征计数中较大的那个和 最佳计数的总和，从而该总和不大于最佳计数的两倍。

在另一个实施例中，货架/标签检测模块205计算一对仓的矩形图。存在这样的一 个柱状图，其基于上部仓的顶部超像素货架特征、上部仓的底部超像素货架特征、底部仓的 顶部超像素货架特征和底部仓的底部超像素货架特征中的每一个的颜色。可以通过比较柱 状图来比较不同的货架假设。

在另一个实施例中，货架/标签检测模块205通过仅考虑顶部和底部超像素货架特 征邻近的超像素货架特征，来计算一对仓的另一个得分。如果两个超像素货架特征的X坐标 的差异小于阈值，则这两个超像素货架特征邻近。在一个实施例中，阈值是T/tan(arcsin (B/T)，或等同地，T2×sqrt(1-(B/T)2)/B，其中T是货架厚度，B是仓间距。在一个实施例中， X坐标是原始图像X坐标。在另一个实施例中，X坐标在坐标系统中转动了theta。

在708处，货架/标签检测模块205基于上下文评估货架位置。在各个实施例中，上 下文可以用于评估货架位置。这可以包括来自对象识别模块201的信息、来自重叠的图像中 的货架检测的信息、基于假设货架之间的常规间距的假设或其他现有信息等。可以为假设 的得分增加奖励，以改善最佳假设的选择。如果产品位于货架上，则产品的底部边缘与货架 的顶部边缘处于相同位置。类似地，表面的底部边缘与货架的顶部边缘位于相同的位置。在 实际货架图图像(其中图像中的垂直位置不一定仅对应于3D空间中的垂直位置的2D投影) 中，位置的比较应当明确地采用3D几何形状或使用允许3D效果的相同位置的近似。例如，在 一个实施例中，货架/标签检测模块将表面的底部仓坐标与货架的顶部仓坐标进行比较，并 且考虑不由货架支撑T个仓内不具有货架顶部的任何表面，例如T＝1.5×厚度，其中厚度是 当前货架假设的仓中的货架顶部和货架底部之间的距离。

需要注意的是，通过在并未找到货架时停止迭代来应对并非位于货架上的悬挂产 品的情况。可选地，如果已知任何被识别出的产品是悬挂产品，则可以考虑将这些产品移除 作为不由货架支撑的产品。

为了找到一个货架可能存在的范围，货架/标签检测模块205对具有小于分离的货 架厚度底部的表面进行分组，并且使用小于组的最小仓坐标的一个和大于组的最大仓坐标 的一个(如果这些仓并不存在，则忽略小于的一个和大于的一个的位置)。

在一些实施例中，使用相同景象的多个重叠的图像。使用现有的公共和/或专属合 并算法来确定图像之间的几何关系。对多个图像执行货架检测。货架假设的位置被转换为 通过合并算法确定的坐标系统。在一个实施例中，选择假设以在多个重叠图像中的连续位 置中联合最大化货架的得分。在另一个实施例中，如果在一个图像中的对应位置中存在货 架假设，则向另一个图像中的货架假设给出奖励。

在一些图像中，货架之间的间距是规则的。在706处找到如基于外观计算的每对货 架假设之间的间距。这些间距的唯一值(例如通过仓间距指明的公差内的相同值)是货架间 距的估计值。通过结果大于或等于最小货架间距的小正整数分割的这些间距(例如2、3、4、 5)是货架间距的其他估计值。如在706处基于外观计算的作为离开货架假设的多个估计的 货架间距的位置用于找到范围，所述找到范围的方式可以类似于如上所述找到并不由货架 支撑的表面的方式。

在710处，基于所选择的货架假设，货架/标签检测模块205确定货架边界。在一个 实施例中，为了确定货架边界的坐标，货架/标签检测模块(仅)返回货架的原始图像Y坐标。 这些Y坐标代表跨过图像的整个宽度的水平货架。在一个实施例中，模块205选择货架的顶 部(顶部内围层)的超像素货架特征的顶部边界中心Y坐标的最大值作为货架的顶部坐标。 类似地，模块205选择货架的底部(底部内围层)的超像素货架特征的底部边界中心Y坐标的 最小值作为货架的底部坐标。

可选地，货架边界可以代表以下各项中的一项或多项：处于离开水平的角度的货 架、并不跨过图像(例如具有多个隔间(bay)的图像(隔间是存储特定货架配置的特殊区域) 或具有并不处于任何隔间内的区域的图像)的宽度的货架、由于3D或相机效果造成图像中 并不直(例如不同角度处的线性分块)的货架、货架边缘的可视部分、没有受阻挡的边缘的 部分。在一个实施例中，可以通过将两条线或一对平行线适配到顶部内围层和底部内围层 来表示处于一定角度的货架。由于3D或诸如枕形或桶形失真之类的相机效果，图像中的货 架可能不是直的。可以将分块连续的不同角度的货架假设组合为多边形以代表货架边界。

来自货架假设的信息包括货架的超像素货架特征的位置和它们的颜色。可选地， 存在这样的额外信息，所述额外信息例如是处于特定被识别出的产品的边界框中的超像素 或具有特定被识别出的产品的内围层的超像素。可以基于并不是超像素货架特征的完整宽 度货架假设中的超像素来检测货架并不跨过整个图像的情况，它们在颜色上并不类似和/ 或并不关联于特定的被识别出的产品。对隔间边界的搜索可以被限制为应用到所有货架的 每个图像的单个边界(例如，搜索可以针对单个垂直的隔间边界)。在一个实施例中，四侧多 边形或平行四边形可以代表货架。

在各个实施例中，可以不对落入所选择的货架边界范围内的一些超像素加标签来 作为货架的一部分。例如，如果在货架假设超像素中从特定产品的识别存在任何内围层，则 这些超像素可以被处理为并不匹配货架。预期这些超像素来自于阻挡货架边缘的货架边缘 的前端中的对象。可以组合这些超像素的区域，并且可以确定排除这些区域的代表货架边 缘的多边形。在一些实施例中，可以利用货架假设超像素作为前台（作为来自假设的超像素 货架特征的超像素的特定前台以及可能的其他）和作为（特定）背景之上和之下的相邻超像 素来初始化图像分段方法，例如抓切方法（GrabCut）。可以随后使用抓切方法来找到并不匹 配货架的货架假设中的超像素。

在712处，货架/标签检测模块205检测货架假设上的标签和价格。在下文中结合图 13更详细地描述标签检测。为了检测价格，货架/标签检测模块205使用光学字符识别（OCR） 从图像中提取价格。如下描述用于从图像中提取价格的示例算法：

将价格列表初始化为空

对于每个货架候选：

将货架候选的界限剪切到图像的界限

if被剪切的区域过小then：

continue

if缓存中存在候选（可选）then：

将候选的缓存的价格增加到价格列表

else:

擦除并不处于货架候选中的被剪切的区域中的任何区域（可选）

文本检测

OCR

对于每个OCR结果：

if结果是价格then：

将结果增加到价格列表

在缓存中保存候选的价格（可选）

在一些实施例中，货架/标签检测模块205使用多个阈值，并且可以在对应于每条 文本的区域（例如，标签上的价格）上多次运行OCR，这通常会针对相同的文本得到多个OCR 结果。当这出现时，找到最佳OCR结果（例如，具有最高置信度的结果），并且在后续处理中使 用该结果。逻辑上，如果货架/标签检测模块205并不针对相同的文本产生多个OCR结果，则 选择最佳OCR结果并不是必要的。

图25是用于从图像中提取价格的示例方法的流程图。以及在2502处，货架/标签检 测模块205使用已知的公共和/或专属文本检测方法检测图像中的文本，并且在2504处，货 架/标签检测模块205使用已知的公共和/或专属OCR方法识别文本并且将文本图像转换为 符号文本。

OCR方法将带有印刷的文本的图像转换为符号文本。在一些实施例中，OCR方法可 以执行文档布局分析、景象文本检测和/或类似的预处理步骤，以生成二进制图像用于识 别。文档布局分析识别包括文字、照片、图像和其他内容的文档(例如报纸、杂质等)中的文 本，例如标题、栏等。景象文本检测可以包括分析图像以找到文本。例如，图像可以包括包含 文本的对象，例如产品盒/容器、货架标签等。景象文本检测类似地处理带有多个颜色的文 本以创建OCR的二进制图像。在一些实施例中，OCR方法(例如并不包括文档布局分析、景象 文本检测或类似的先进预处理的方法)可以采用通过分别的预处理步骤生成的二进制图像 作为输入。在一个实施例中，使用抓切来对图像区域进行二进制处理以输入到OCR。

OCR软件对于印刷的文本的良好图像(例如，高分辨率、高对比度、良好的聚焦、没 有抖动模糊、亮度均匀等)通常是准确的。然而，景象图像(例如存储货架的图像)包括了较 低质量的图像，其中分辨率相对于文本的大小较低，对比度低，并且可能包括图像劣化，例 如由于聚焦不佳或抖动造成的模糊或由于使用闪光灯而造成的眩光。常常，存储货架的图 像具有各种各样颜色的大量的景象文本。这些图像还具有并非文本的大量的图形或线条 (条形码、企业标识等)，但可以共享低水平特性的文本(例如，可以包括笔划)。

在商店货架图像上使用现有的景象文本检测软件可能无法找到例如价格标签上 的价格之类的文本。为了增加找到文本的可能性，货架/标签检测模块205将景象文本检测 限制到图像中的被确定为对应于货架或货架假设的区域(如在本文中其他部分所描述的)。

在2506处，标签/货架检测模块205可以对被识别出的文本执行后处理。由于分辨 率低、模糊和/或其他劣化，OCR也许无法准确地区分商店货架的图像中的诸如“S”、“5”和 “$”之类的类似字符。为了处于价格检测的目的来区分这些字符，标签/货架检测模块205可 以限制OCR许可的字符，例如“$.0123456789”，而排除其他字符(例如字母)。一些价格标签 可能包括OCR软件无法处理的字符，例如分符号取而代之的是，OCR可能混淆未被处 理的字符和某个其他字符(例如和“c”)，从而允许字符替换实现包括替代字符，例如“$ c.0123456789”。

常规表达或其他样式可以定义字符的预期的顺序。示例性的常规表达是“^\$\d +\.\d\d$”，其匹配以“$”开始的字符串，该字符串具有一个或多个数字、小数点，并以两位 数字结束。另一个示例性的常规表达是“^\d\d？c$”，其匹配以数字开始的字符串，该字符串 可选地具有两位数字并且以“c”或结束。一些OCR方法可以包括支持使用字符的预期的 顺序以辅助识别。或者，货架/标签检测模块205是应用字符的预期的顺序作为后处理步骤。 货架/标签检测模块205因此拒绝并不匹配预期的样式的OCR输出。

类似地，OCR方法可以为每个字符提供替代的识别，并且货架/标签检测模块205可 以使用后处理来选择匹配预期的样式的结果，并且仅拒绝当没有替代匹配时的识别。在一 些实施例中，OCR方法为替代识别提供得分或置信度值，并且货架/标签检测模块205可以选 择具有最高得分或置信度值的匹配。

在一些实施例中，货架/标签检测模块205可以相关于字符界限框内的其他字符地 使用字符的位置以识别价格文本。例如，当标签在不同于字符的不同位置(例如价格中的上 标)中包括“$”或字符时，字符界限框位置可以用于区分价格和其他文本。

此外，由货架/标签检测模块205执行的后处理可以校正在文本识别期间丢掉的字 符(例如，如果小数点“.”被丢掉，OCR就在其位置处返回断字)。例如，由货架/标签检测模块 205执行的后处理步骤可以创建被丢掉的字符的替代，并且使用模式匹配来确定替代的适 当字符以替换被丢掉的字符。

如在上述示例中所示，可以可选地使用高速缓存，从而对于相同的货架假设执行 文本检测和OCR并不超过一次。例如，可以针对第一检测以找到一些价格和随后第二检测以 试图找到更多价格两者使用单独的货架的相同假设。可以使用货架假设的线的坐标作为高 速缓存密钥。

一些货架候选可以在图像底部的顶部处延伸到图像之外。这些货架候选可以被剪 切到图像的边界以创建剪切的图像区域来输入文本检测。OCR方法通常具有最小的分辨率 来检测文本，其暗示被剪切的区域的最小尺寸。比最小尺寸还要小的区域可以被假定为不 具有可提取文本而无需执行文本检测或OCR。例如，小于10像素高的区域被假定为不具有可 提取文本。通常，具有较小高度的图像的仅顶部或底部处的货架候选过小。

一旦检测到了价格和标签，货架/标签检测模块205就识别出图像中检测到的标签 和匹配价格以验证标签和/或价格的位置。如果价格与标签重叠并且重叠的高度是价格的 高度的至少一半并且重叠的宽度是价格的宽度的至少一半，则价格匹配标签。在一些实施 例中，价格周围的边界框的高度和宽度用于确定价格的高度和宽度。

在一些实施例中，当标签紧密在一起时，可以检测到多个标签作为组合的标签区 域而并非单独、分离的标签。如果在单个标签区域中存在水平可分离的多个标签，货架/标 签检测模块205就分割该标签区域。在一个实施例中，货架/标签检测模块基于从标签检测 确定的标签的中间宽度将被组合的标签区域分割为单独的标签。在另一个实施例中，货架/ 标签检测模块205基于价格边界框的位置和/或尺寸来分割被组合的标签区域。

在一个实施例中，基于外观评估货架位置和基于上下文评估货架位置包括从考虑 中移除一个或多个假设。这对于减少仅对数量减少的假设执行标签检测所需的总计算的量 是有益的。在另一个实施例中，在从考虑中移除假设之前对假设执行标签检测。

在714处，货架/标签检测模块215使用来自基于外观的货架位置假设、基于上下文 和标签以及价格检测的货架位置假设的信息，来选择最佳货架和标签位置。在一个实施例 中，基于发现的标签的数量和价格、发现的货架的数量和得分(在一些实施例中为重要性的 量级)来选择最佳位置。在另一个实施例中，基于如上所述的宽度和/或超像素货架特征柱 状图来一起考虑各组假设。在另一个实施例中，使用诸如决定树学习、提升、随机树或SVM (支持矢量机器)之类的机器学习方法来选择位置。

图26以表格示出了货架假设的示例。该表格例如被存储在数据存储243中。表格中 的每行是一个假设。通过顶仓值和底仓值来描述每个假设。其他表格列是仓中的宽度，使用 标签检测、得分(基于超像素货架特征)、该假设的超像素货架特征的1..5颜色索引、超像素 货架特征的亮度或灰度值、以及来自标签之下的搜索的表面信息是否用于生成该假设，来 找到标签的数量。过于紧密在一起而无法分离货架的各组假设被通过粗黑线分割(例如每 组一个货架)。对于每个组，选择作为最佳假设的假设被(利用阴影背景)高亮标记。这四个 最佳假设对应于四个检测到的货架。

可能的是，使用上述方法没有找到图像中所有的货架。货架/标签检测模块205可 以通过生成货架和标签模型以帮助寻找额外的货架和/或标签检测来尝试找到之前未发现 的货架。在716处，货架/标签检测模块基于来自714的最佳货架位置来生成货架外观的模 型。在一个实施例中，货架模型具有一个几何参数，其是货架前端的厚度的估计值。估计值 是之前检测到的货架的平均厚度。在其他实施例中，货架模型可以包括额外的几何或颜色 参数。

在718处，货架/标签检测模块205基于来自714的最佳标签位置来生成标签外观的 模型。在一个实施例中，标签模型可以包括几何和颜色参数。一个几何参数可以是例如在标 签和价格检测712期间确定的标签的宽度的估计值。标签模型中的额外的几何参数可以包 括例如价格文本和货架/标签边缘之间的垂直空白。

颜色参数可以包括标签颜色的高斯混合模型(GMM)、与该GMM相关的可能性阈值和 先前检测到的标签如何匹配此GMM的示例。在一些实施例中，标签模型可以学习并代表标签 的主要颜色之间的与-或关系，例如“标签是红色和白色的或标签是蓝色和绿色的”。标签颜 色可以是通过标签检测712识别出的标签区域中的超像素的平均颜色。例如，对这些标签颜 色计算出的GMM可以包括五个分量，其中每个分量具有三个单元平均矢量和3×3协方差矩 阵。

在一个实施例中，通过使用GMM来确定可能性阈值以计算标签颜色的可能性。例 如，可以使用25％作为阈值(例如，可能性大于或等于来自标签颜色的可能性的25％并且小 于这些可能性的75％)。

通过计算柱状图、包或每个检测到的标签的标签颜色的多个组，来确定检测到的 标签在GMM中匹配的示例。每个柱状图仓(或等同的包元素或多组元素)对应于GMM分量索引 中的一个(通常是五个索引中的一个)。每个仓的计数(或元素的计数)是通过GMM分配给GMM 分量的标签颜色的数量，其中分配的高斯可能性大于或等于阈值。在一个实施例中，通过出 现多于一次的所有GMM中最频繁的一组GMM索引(例如至多三个)来总结每个检测到的标签 的示例。在另一个实施例中，可以使用类似的总结或可以直接使用柱状图(或包/多组)来替 代总结。

在一个实施例中，使用相同的标签颜色来构建GMM，以计算阈值的可能性并计算示 例。在另一个实施例中，可以分割这些标签颜色，从而出于这些用途来使用不同的标签颜 色。

在720处，货架/标签检测模块205使用特征基于外观更新可能的货架位置并且基 于货架和标签外观的模型更新可能的货架位置的上下文。长水平线段有时指示货架的边 缘。在一个实施例中，货架/标签检测模块205可以识别并非位于任何货架假设附近的长水 平线段，并且匹配可能的货架位置的角度(来自704)。这些长水平线段可以对应于先前并未 检测到的货架的边缘。货架/标签检测模块205尝试识别货架外观是位于被识别出的水平线 之上还是之下，以生成额外的货架假设。此外，货架/标签检测模块205检查特征(例如超像 素货架特征)并不位于货架假设之内的位置，以确定货架是位于特征之上还是之下，来生成 额外的货架假设。

货架/标签检测模块205可以使用货架模型(例如货架厚度估计)来搜索货架的存 在。在下文中描述搜索水平线或其他特征之上和之下的示例算法：

对于(y，y+厚度)和(y-厚度，y)中的顶部和底部位置：

从顶部和底部位置创建货架假设

确定货架边界

检测标签或价格

验证标签

如果货架/标签检测模块205找到任一个假设(例如，特征之上和之下的假设)的价 格或标签，则返回具有更大数量的价格或标签的假设作为检测到的货架假设。如果货架/标 签检测模块205未能找到任一个假设的价格或标签，则假设并不对应于货架，并且不返回结 果。

在722处，货架/标签确定模块205基于更新的货架位置假设确定货架边界。货架/ 标签检测模块205在这里与上述参照710描述的方法类似地确定货架边界。

在724处，货架/标签确定模块205基于标签模型来检测标签和价格。货架/标签检 测模块205通过提取价格来检测标签和价格(并且随后验证价格在标签上)，如参照图13所 述。可选地，通过标签检测、删除任何先前检测到的标签、并且随后验证标签来在假设之间 进行选择，确定其中无法提取价格的标签的位置。在726处，货架/标签检测模块205选择最 终的货架的标签位置，如上参照714所述。

图13是用于检测和确定实际货架图图像中示出的货架前端上的标签的位置的示 例性方法的流程图。在1302处，货架/标签检测模块205识别与货架相关联的超像素，如上所 述。在1304处，货架/标签检测模块205通过颜色将货架超像素量化到集群中。例如，在一个 实施例中，货架/标签检测模块205使用k平均集群将货架超像素集群到五个集群中。显然的 是，可以使用各种数量的集群或集群算法来对货架超像素进行集群。图14A是示出了叠加有 超像素的示例性实际货架图的一部分，其中所述超像素被编号以示出货架超像素的集群。

返回到图13的示例，在1306处，货架/标签检测模块205可选地确定可能对应于标 签的集群。例如，货架/标签检测模块205将具有最少超像素(例如最少流行颜色)的集群识 别为可能对应于标签的集群。在一个实施例中，货架/标签检测模块205识别具有最少超像 素的三个集群。图14B是示出了叠加有超像素的示例性实际货架图的一部分，其中所述超像 素被编号以示出货架超像素的集群。在图14B的示例中，集群1包括最多超像素(例如最流行 颜色)，并且集群2、4和5包括最少的超像素。

类似地，货架/标签检测模块205识别具有在它们的边界中完全包括的非水平线的 货架超像素。在一个实施例中，模块205通过使用LSD结果(如下所述)进行此操作。非水平线 可以用于识别可能作为标签的各部分的超像素，这是因为线通常对应于货架标签上印刷的 数字和/或条形码。在一个实施例中，货架/标签检测模块205识别包括具有非水平线的大部 分超像素的三个集群。在图14B的示例中，集群3、4和5包括具有非水平线的大部分超像素。

在1308处，货架/标签检测模块205基于集群形成标签位置的假设。在一个实施例 中，货架/标签检测模块通过找到一个或多个集群中相邻超像素的连通分量基于集群来形 成标签位置的假设。

在另一个实施例中，货架/标签检测模块205确定即处于具有最少超像素的颜色集 群中也处于具有最多非水平线的集群中(例如这些集群的交叉)的货架超像素以形成标签 位置的假设。图15是示出具有最少超像素和具有最多非水平线的超像素的集群之间的交叉 的示例性图示。在图15的示例中，基于颜色具有最少超像素的集群的组被加标签有C3，并且 具有最多非水平线的集群的组被加标签有M3。从图15中可以看出，集群5和4落入了这两个 组的交叉中。货架/标签检测模块205使用该交叉以确定包含标签特征的集群的假设。例如， 模块205可以测试存在来自集群4的超像素的区域的假设、存在来自集群5的超像素的区域 的假设、以及存在来自集群4和集群5两者的超像素的区域的假设。在另一个示例中，除了如 上所述生成第一组假设之外，货架/标签检测模块205使用并未处于具有最少超像素的集群 或并未处于最多非水平线的集群中的集群来额外地生成第二组假设。可以对第一组执行如 下所述的验证标签假设的尝试，并且如果并未找到标签，则对第二组进行验证。在其他实施 例中，可以通过一个或多个其他现有的公共和/或专属的图像特征提取算法来替换颜色流 行标准和/或非水平线标准。

在1310处，货架/标签检测模块205确定是否存在标签模型。如果存在标签模型，则 在1312处，货架/标签检测模块找到匹配模型的组件。例如，货架/标签检测模块205从模型 中确定匹配GMM标签颜色的超像素。如果没有超像素匹配GMM，则连通分量并不匹配模型。在 另一个示例中，如果连通分量的宽度大于标签(例如其宽度大于1.5×来自模型的中间标签 宽度)，并且如果在连通分量中的所有位置处中间标签宽度的一半内不存在匹配超像素，则 连通分量并不匹配模型。

在1314处，货架/标签检测模型205从标签模型获取中间宽度，在1320处，确定接近 于中间值宽度的标签候选(例如，具有匹配模型的组件的假设标签位置)，在下文中对此进 行更详细地描述。在一个实施例中，货架/标签检测模块205确定接近于中间宽度的整数倍 数的标签候选。

如果标签模型并不存在，则货架/标签检测模块205在1316处找到图像中具有多于 一个超像素的组件，并且在1318处基于所选择的组件来确定中间宽度。在1320处，货架/标 签检测模块205确定接近于中间宽度的标签候选。

图16示出了叠加有超像素的连通分量的示例性的实际货架图的一部分，其中所述 连通分量被编号以示出货架超像素的集群并且示出假设的标签位置。在1322处，货架/标签 检测模块205选择最佳的标签假设。例如，货架/标签检测模块205通过下述确定最佳标签假 设：计算每个宽度和中间值的差值并将该差值与阈值(例如中间值的一半或比中间值小10) 进行比较，基于有多少检测到的标签具有相同的宽度并且有多少检测到的标签并不位于阈 值内来对每个假设进行评分，选择具有最高得分的假设，并且确认存在至少阈值数量(例如 5)的具有沿货架前端的类似宽度的非相邻标签。可选地，拒绝宽度上并不大于超像素的中 间宽度两倍的标签假设。可选地，考虑比中间宽度大阈值(例如，50％的中间宽度)的标签假 设是多个标签。可选地，将多个标签的假设分割为单个标签的假设。可选地，对于类似(重 叠)的假设，仅对假设中的一些假设执行标签检测。例如，以得分从高到低的顺序对假设执 行标签检测，跳过其中先前假设重叠(例如，顶部和底部之差小于超像素中间高度的一半) 或先前检测到的标签重叠的任何假设。

货架/标签检测模块205基于颜色和几何参数验证所选择的标签假设。例如，货架/ 标签检测模块205可以为标签假设生成边界框，将边界框宽度从模块扩展到标签宽度，确定 边界框内的超像素是否匹配模型，并且如果超像素匹配模型则增加边界框作为标签。为了 确定超像素是否匹配标签模型，与用于构建标签模型的超像素平均颜色类似地计算超像素 平均颜色的柱状图(或袋或多组)。如果任何示例匹配，则超像素匹配标签模型。例如，如果 来自假设的一组索引相同于模型示例中的一组索引，则示例匹配模型。在使用用于匹配柱 状图的替代实现中，可以使用柱状图比较计算来确定匹配。

在一个实施例中，基于几何参数的验证包括识别相对于货架/标签的垂直位置限 制文本的垂直位置的参数。例如，标签模型可以包括这样的参数，该参数指明货架/标签的 顶部和价格的顶部之间的预期空白以及价格的底部和货架/标签的底部之间的预期空白。 为了无关于尺度，空白参数被标准化到价格文本的高度。在一个实施例中，当实际空白位于 预期空白的文本的高度之内时，空白匹配。作为货架和标签的示例，顶部空白是文本的高 度，并且底部空白是文本高度的两倍。

在另一个示例中，验证标签假设包括使用现有的公共和/或专属文本检测算法并 拒绝没有检测到文本的假设。在另一个示例中，验证标签假设包括使用现有的公共和/或专 属文本识别(OCR)算法并拒绝没有识别出文本的假设。在另一个实施例中，验证标签假设包 括使用现有的公共和/或专属对象识别或检测算法，并拒绝并未识别出或检测到对象的假 设，其中所述算法被训练为识别标签(例如其中从标签学习模板的模板匹配)。

在一些实施例中，可以通过实际货架图分析应用来接收同一景象的多个重叠图 像，并且在实际货架图分析中使用所述多个重叠图像。使用现有的公共和/或专属合并算法 来确定图像之间的几何关系。对多个图像执行标签检测。标签假设的位置被转换为通过用 于组合多个重叠图像的合并算法确定的坐标系统。在一个实施例中，具有重叠的图像区域 中的标签假设的验证包括确定在多个图像中的对应位置中是否存在标签假设。

在一些实施例中，对同一图像中的不同货架假设或对不同的重叠图像多次执行标 签检测。在第一次之后，标签检测可以使用上一次的估计宽度(例如假设的中间宽度)来替 代计算新的估计宽度。

在一些实施例中，对于处于多个重叠图像中的标签位置，评估每个图像中的每个 重叠标签区域中的图像质量。评估可以是对其中检测到标签的整个子图像进行的或对其中 检测到标签的中心内的子图像进行的。在一个实施例中，利用指示高质量的高对比度来评 估区域的对比度。在另一个实施例中，利用指示高质量的高锐度来评估区域的锐度。在另一 个实施例中，利用指示高质量的低光谱反射来评估光谱反射。对于每个标签区域，使用最高 质量区域来进行进一步分析和/或显示给用户。或者，被判断为足够的高质量的所有区域用 于进一步分析。例如，考虑区域的0..255灰度值，如果最暗像素小于128，则判断区域的质量 足够高。当非漫射光造成对一个图像中的特定标签的光谱反射但没有造成对另一个图像中 的特定标签的光谱反射时，从多个重叠图像中使用一个最高质量区域或多个高质量区域是 有益的。

在一些实施例中，在检测到标签之后，提取来自标签的信息(例如，价格、UCP代码、 产品名称等)。可以使用OCR、条形码读取软件或其他类似的现有公共和/或专属算法来提取 信息。标签检测可以包括找到标签的元素(例如，价格、条形码、产品名称等)、产生一个或多 个特定的元素并且在一个或多个特定的元素上提取信息。在一个实施例中，可以由人(包括 使用群众外包)提取信息。

图17是用于确定被组织的对象的图像中的多个特定对象的存在和位置的示例性 方法606的流程图。图像中的多个特定对象(特别是对象识别模块并未识别出的那些对象) 可以被用于帮助实际货架图分析应用103确定区域并且在各种未被索引的产品之间进行区 分，所述区域包括在由对象识别模块使用的图像搜索数据库中未被索引的产品。在1701处， 倍数模块209接收多个被组织的对象的图像。如上所述，图像可以是零售货架或展示的实际 货架图图像。

在1702处，倍数模块209从被组织的对象的图像中提取特征。可以采用各种已知特 征提取算法来提取图像特征。在1704处，倍数模块209找到图像中的匹配特征点。例如，倍数 模块209可以使用FLANN或KDD树算法来匹配图像中的特征点。在一个实施例中，倍数模块使 用k最近邻居算法匹配描述符矢量，其中k＞2。在一个实施例中，k＝25，使得匹配产生了24 个良好的匹配。

在一个实施例中，倍数模块209选择良好匹配(允许多个匹配)。图18示出了图像中 的多个匹配点的描述符距离的示例性条形图。本文中使用的描述符距离是两个特征点有多 类似的指示，其中更小的距离表示更类似的特征。D1，D2，...，D8是特定特征点和所有特征 点之间的升序的距离。在图18的示例中，条形图仅示出了八个最小的距离，但应当理解在分 析中可以使用任何数量的描述符距离。超过D1、D2、...、D8标签的条的高度代表距离。这是 因为，当在同一图像中进行匹配时，特征点总是将其自身与0距离匹配，D1总是0并且被忽 略。D2是忽略与其自身(D1)匹配的最小距离(例如最佳匹配)。由于D3和D4接近于D2并且由 于D5比D2大得多，因此良好的匹配是D2、D3、D4(例如其中索引j是2、3或4)。使用阈值1/β× D2确定接近于D2。使用阈值1/α×D2确定比D2大得多。对于这些阈值，0<α<β<1。在一个实施 例中，α是0.667并且β是0.800。如果在1/β×D2和1/α×D2之间不存在距离并且至少一个距 离大于1/α×D2，则D2和所有其他小于1/β×D2的距离对应于良好匹配。否则，不存在良好匹 配。

在1706处，倍数模块209利用匹配距离和点之间的角度对匹配特征点进行集群。在 一个实施例中，所有集群至少包括阈值数目的对(例如10)，其中集群矢量之间的距离(例如 L1或L2距离)小于阈值(例如20或32)。在一些实施例中，有益的是执行高密度搜索以找到集 群。在一个实施例中，第一集群步骤将点分离到使用闸刀切割通过至少距离阈值分离的集 群中(例如基于矢量的X或Y坐标中的一个通过递归地将点分割到集群中来进行分离)，并且 随后对来自第一步骤的每个集群使用第二集群步骤，所述第二集群步骤使用现有的公共或 专属集群方法，例如k-平均。在一个实施例中，利用从2开始并且增加来自先前使用的集群 数量的多个k值、并且在所有集群小于阈值数量的对或具有距离小于阈值(或到达集群的最 大数量，例如200，或迭代的最大数量，例如20)的矢量的情况下结束，来使用k-平均集群，所 述先前使用具有的矢量的距离大于阈值。在一个实施例中，在k-平均集群之后，如果所得到 的集群具有的矢量之间的距离小于距离阈值，则融合(merge)集群。

所得到的特征点对的集群代表实际货架图图像中的类似对象之间的匹配点。在 1708中，倍数模块209利用集群信息为超像素加标签。例如，针对集群中的每个特征点对，倍 数模块209识别出包括特征点的超像素的对应对，并且递增超像素对的计数。对于作为至少 一对的部分的每个超像素，倍数模块209利用其中找到匹配并且可选地具有集群矢量和特 征点的超像素的标识符和计数为超像素加标签。

使用被加标签的超像素，在1710处，倍数模块209基于集群(例如类似维度的相同 对象的堆叠)来找到多个相同的对象。图19A示出了相同高度的货品的堆叠的示例性图示。 在一个实施例中，为了找到相同高度的货品的堆叠，倍数模块209确定匹配之间的中间垂直 距离(在图19A的示例中被示为d)，基于各个匹配的范围和距离找到堆叠中的最大数量对 象，确定具有高度d的堆叠中的对象的数量的坐标，并且确定相同产品的多个堆叠(例如，图 19A的示例中的d1和d2)。图19B示出了叠加有识别未被索引的对象的堆叠的边界框1904的 示例性的实际货架图的一部分，其中在实际货架图的图像中与由倍数模块（如虚线边界框 所示）类似地识别出所述未被索引的对象的堆叠。

以下是识别堆叠的示例性算法：

对于可能存在未被索引的产品的每个区域

对于具有匹配的区域中的每个超像素（例如，被标记有一个或多个集群）

对于对当中的每个其他超像素

If（如果）中心之间的线是垂直的（例如63-117度）

将中心的边界框附加到列表

If列表具有小于3个唯一对的超像素，则continue（继续）

通过X坐标对边界框进行分类

If连续的X坐标的差大于一个阈值，则将类表分割成多个列表（例如2×最小预期 的产品宽度）

对于每个列表

找到中间Y距离d用于（例如，特征的超像素中心之间的）匹配

可选地，If许多距离与中间值并不一致，则continue

找到Y坐标的最小和最大值（可选地忽略偏离值）

确定堆叠中的最大数：num=max（（Ymax-Ymin）/d,1）+1

确定以（Ymax‐Ymin）/2为中心的宽度d的数量行的坐标

对于每行

搜索被分类的X坐标以找到在行中具有Y坐标的匹配

If连续的X坐标的差大于阈值，则分割被分类的X坐标

对于每组X坐标

将行的X坐标和Y坐标的范围增加到最终输出

图20是通过使用分段算法（例如抓切）找到实际货架图图像中货架之下的空闲空 间以从货架前端和产品分段出货架背景的示例性方法608的流程图。在2002处，空闲空间模 块207通过例如选择直接位于货架之下（并且并不位于被识别出的产品的边界框中）的最暗 的超像素来识别货架之下的空闲空间。图21A示出了识别通过分段算法分段的“缺货”和“其 他”区域的示例性实际货架图的一部分。在2004处，空闲空间模块207对分段算法进行扩展 （seed）以寻找“缺货”和“其他”区域，所述区域具有在2002中识别出的超像素并且被由对象 识别模块201和货架/标签检测模块205识别出。例如，如图21B的示例中所示，空闲空间模块 207对直接位于具有“缺货”超像素的货架之下的暗像素以及通过被识别出对象的边界框识 别出的区域和具有“其他”超像素的货架前端进行扩展。图22示出了识别被扩展有超像素的 “缺货”和“其他”区域的示例性实际货架图的一部分。在图22的示例中，未被加标签的超像 素没有被分类，被标记有1的超像素是“缺货”区域，并且被标记有2的超像素是特定或可能 的“其他”区域。

在2006处，空闲空间模块对超像素扩展的实际货架图图像迭代诸如抓切之类的图 像分割算法，以提炼出对“缺货”区域的识别。抓切使用被分类为已知和可能的超像素中选 择的颜色来创建前景和背景高斯混合模型。初始地忽略未知的超像素。使用GMM，空闲空间 模块207将未知的超像素分类为可能的“缺货”或“其他”。此外，空闲空间模块207对一些可 能的超像素进行重新分类。基于重新分配的超像素计算新的GMM，并且基于新的GMM对超像 素进行再次重新分类。空闲空间模块207可以重复此迭代多次以获得可接受的结果。在一个 实施例中，空闲空间模块207执行10次迭代以获得可接受的结果。图23A和图23B分别示出了 在进行分段算法的1次迭代和10次迭代之后被叠加有指示缺货或其他区域的超像素的示例 性实际货架图。

在获得可接受的结果之后，空闲空间模块207可以从总区域排除在分段迭代之后 保留的对象识别结果、货架和“缺货区域”，从而为潜在未知的产品创建连通组件多边形 2401，如图24的示例中所示。在一些实施例中，空闲空间模块207可以通过将多边形2401与 最少已知产品的尺寸进行比较来提炼未知产品区域，并且删除小于最小已知产品的那些未 知产品区域。

已经描述了实际货架图景象分析的系统和方法。在上述描述中，出于解释的目的， 阐述了许多具体细节以便提供对本申请中介绍的技术的彻底理解。但应当理解的是，对于 本领域技术人员而言，可以在没有这些具体细节的情况下实现本申请中的技术。在其他示 例中，以框图形式示出了结构和设备，以便避免对说明书造成模糊并便于理解。例如，在上 文中主要参照软件和特定硬件在一个实施例中描述了所述技术。然而，可以使用任何类型 的计算系统来实现所述技术，所述计算系统接收数据和命令，并且呈现信息作为任何外围 设备提供服务的一部分。

在本说明书中对“一个实施例”或“实施例”的引用表示与实施例相关联而描述的 特定的特征、结构或特性被包括在说明书的至少一个实施例中。本说明书中各处出现的词 语“在一个实施例中”不一定都指示相同的实施例。

以对计算机存储器内的数据比特进行操作的算法和符号表示的形式呈现了以上 描述的详细说明中的一部分。这些算法描述和表示是数据处理技术领域的技术人员使用的 手段，用于最有效率地将它们工作的设置传输给本领域中的其他技术人员。这些的算法通 常被构思为能够得到期望的结果的自身一致的步骤的序列。这些步骤需要物理量的物理操 作。尽管并非必要，但这些量一般采用能够被存储、传输、组合、比较或进行其他操作的电或 磁信号的形式。已经证实了在一些情况下主要出于公共使用的原因以比特、值、单元、符号、 字符、词语或数字等参照这些信号是有益的。

但应当理解，所有这些和类似词语将关联于适当的物理量，并且仅是被应用于这 些量的方便标签。除非在以下论述中另有明确说明，否则应当理解在说明书中使用诸如“处 理”或“计算”或“算术”或“确定”或“显示”之类的词语进行的论述是指计算机系统或类似的 电子计算设备的动作或处理，所述计算机系统或类似的电子计算设备操作并将被表示为计 算机系统的寄存器和存储器中的物理(电子)量的数据转换为被类似表示为计算机系统的 存储器或寄存器或其他这样的信息存储、传输或显示设备中的物理量的其他数据。

本说明书还涉及用于执行本文中所述的操作的装置。可以为了所需的目的专门构 造该装置，或者其可以包括被选择性地激活的通用计算机或通过在计算机中存储的计算机 程序被重新配置。这样的计算机程序可以被存储在计算机可读存储介质中，例如但不限于 任何类型的盘片(包括软盘、光盘、CD-ROM和磁盘)、只读存储器(ROM)、随机存取存储器 (RAM)、EPROM、EEPROM、磁或光卡、包括具有非易失性存储器的USB密钥的闪速存储器或适合 于存储电子指令的任何类型的介质，上述存储介质均耦接到计算机系统总线。

本说明书可以采用完全硬件实施例的形式，完全软件实施例的形式或包括硬件和 软件单元两者的实施例的形式。在一个实施例中，以软件实现说明书，所述软件包括但不限 于固件、驻留软件、微代码等。

此外，说明书可以采用从计算机可使用或计算机可读介质可访问的计算机程序产 品的形式，所述介质提供程序代码，以供由计算机或任何指令执行系统使用或与计算机或 任何指令执行系统相关联。出于本说明的目的，计算机可使用或计算机可读介质可以是能 够包含、存储、通信、传播或传输程序的任何装置，所述程序由指令执行系统、装置或设备使 用或与指令执行系统、装置或设备相关联地使用。

适用于存储和/或执行程序代码的数据处理系统将包括通过系统总线与存储器单 元直接或间接耦接的至少一个处理器。处理器单元包括在程序代码实际执行期间采用的本 地存储器、大容量存储器或高速缓存存储器，所述高速缓存存储器提供至少一些程序代码 的临时存储，以便减少在执行期间必须从大容量存储器获取代码的次数。

输入/输出(I/O)设备(包括但不限于键盘、显示器、指向设备等)可以被直接或通 过中间I/O控制器耦接到系统。

网络适配器还可以耦接到系统，以使得数据处理系统能够通过中间私有或公共网 络耦接到其他数据处理系统或远程打印机或存储设备。调制解调器、线缆调制解调器和以 太网卡仅仅是当前可用类型的网络适配器中的一些。

最后，本文中出现的算法和显示并不内在地涉及任何特定的计算机或其他装置。 可用根据本文中的技术与程序一起使用各种通用系统，或可以证明便捷地构件更专门的系 统来执行所需的方法步骤。从以下的描述中可以看出各种这些系统所需的结构。此外，并不 参照任何特定的编程语言来描述说明书。应当理解，可以使用各种编程语言来实现在本文 中描述的说明的教诲。

处于说明和描述的目的已经呈现了实施例的以上描述。其并不意在是穷尽的或将 技术限制到所公开的精确形式。根据上述教诲可以进行许多修改的变更。并非由详细的说 明书、而是由本申请的权利要求来限制实施例的范围。如本领域技术人员所熟悉的那样，本 文中描述的实施例可以被体现为其他具体形式，而不偏离其精神和实质特征。同样，模型、 例程、特征、属性、方法或其他方面的特定名称和划分并不是必要或重要的，并且实现技术 或特征的机构可以具有不同的名称、划分和/或格式。此外，如对于本领域一般技术人员而 言显而易见的，本技术的模型、例程、特征、属性、方法或其他方面可以被实现为软件、硬件、 固件或这三者的任意组合。而且，在组件(其示例是模块)被实现为软件的情况下，组件可以 被实现为单独的程序、大型程序的一部分、多个分离的而程序、静态或动态的链接库、内核 可加载模块、设备驱动器，如计算机编程领域的一般技术人员已知的那样。此外，技术并不 被限制为任何特定编程语言的实施例，或并不被限制为任何特定的操作系统或环境。相应 地，说明书意在是说明性的，而非限制所附权利要求的范围。

本申请基于并要求于2014年12月10日提交的美国专利申请No.62/90,177、于2015 年3月6日提交的美国专利申请No.14/641,290、于2015年3月6日提交的美国专利申请 No.14/641,292以及于2015年3月6日提交的美国专利申请No.14/641,296的优先权，上述申 请的全部内容通过引用方式并入到本文中。