在网络中执行视觉搜索

摘要

总体来说，本发明描述用于在网络中执行视觉搜索的技术。包括接口、特征提取单元和特征压缩单元的客户端装置可实施所述技术的各种方面。所述特征提取单元从图像提取特征描述符。所述特征压缩单元以第一量化等级量化所述图像特征描述符。所述接口将第一查询数据经由所述网络发射到视觉搜索装置。所述特征压缩单元确定加强所述第一查询数据的第二查询数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述图像特征描述符。所述接口将所述第二查询数据经由所述网络发射到所述视觉搜索装置以连续精炼所述第一查询数据。

说明书

技术领域

本发明涉及图像处理系统，且更特定来说涉及用图像处理系统执行视觉搜索。

背景技术

在计算装置或计算机的情境中的视觉搜索指的是使计算机或其它装置能够执行针对一个或一个以上图像内的若干对象和/或特征当中的对象和/或特征的搜索的技术。视觉搜索中的最近关注已带来使得计算机能够在广泛多种变化的图像条件下识别部分被遮挡的对象和/或特征的算法，所述变化的图像条件包含图像比例、噪声、照明和局部几何失真的改变。在此同时，以相机为特征的移动装置已出现，但其可能具有用于输入文本或以其它方式与移动装置介接的有限用户接口。移动装置和移动装置应用程序的开发者已寻求利用移动装置的相机来增强用户与移动装置的交互。

为了说明一种增强，移动装置的用户可采用移动装置的相机来在商店购物的同时俘获任一给定产品的图像。移动装置可随后在用于各种图像的一组归档特征描述符内起始视觉搜索算法以基于匹配图像识别产品。在识别出产品之后，移动装置可随后起始因特网搜索并呈现含有关于所识别产品的信息的网页，包含可从附近的商人和/或在线商人购得所述产品的最低价格。

虽然存在配备相机和能够进行视觉搜索的移动装置可采用的许多应用，但视觉搜索算法经常涉及大量的处理资源，其通常消耗大量的电力。用依赖于电池供电的电力宝贵的装置(例如上述移动便携式和手持式装置)执行视觉搜索可能受限，尤其是在其电池接近耗尽其电量时。因此，已开发若干架构来避免这些电力宝贵的装置完全地实施视觉搜索。而是，与电力宝贵的装置分开来提供执行视觉搜索的视觉搜索装置。电力宝贵的装置起始与视觉搜索装置的会话，且在一些实例中，在搜索请求中将图像提供到视觉搜索装置。视觉搜索装置执行视觉搜索且返回搜索响应，该搜索响应指定由视觉搜索识别的对象和/或特征。以此方式，电力宝贵的装置能够进行视觉搜索，但不必执行消耗大量电力的处理器集约型视觉搜索。

发明内容

大体上，本发明描述用于在网络环境中执行视觉搜索的技术，所述网络环境包含可称为“客户端装置”的移动、便携式或其它电力宝贵的装置以及视觉搜索服务器。并非将图像完整地发送到视觉搜索服务器，客户端装置局部地执行特征提取以用所谓的“特征描述符”的形式从存储在客户端装置上的图像提取特征。在若干实例中，这些特征描述符包括直方图。根据本发明中描述的技术，客户端装置可以连续可精炼方式量化这些直方图特征描述符。以此方式，客户端装置可基于以第一粗略量化等级量化的特征描述符而起始视觉搜索，同时如果视觉搜索需要关于此特征描述符的额外信息则精炼特征描述符的量化。因此，可能发生某一量的并行处理，因为客户端装置和服务器可能同时工作以执行视觉搜索。

在一个实例中，描述一种用于在网络系统中执行视觉搜索的方法，其中客户端装置将查询数据经由网络发射到视觉搜索装置。所述方法包括用客户端装置存储界定查询图像的数据，以及用客户端装置从所述查询图像提取一组图像特征描述符，其中所述图像特征描述符界定所述查询图像的至少一个特征。所述方法还包括用所述客户端装置以第一量化等级量化所述组图像特征描述符以产生表示以所述第一量化等级量化的所述组图像特征描述符的第一查询数据；用所述客户端装置将所述第一查询数据经由所述网络发射到所述视觉搜索装置；确定加强所述第一查询数据的第二查询数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述组图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更准确的对所述组图像特征描述符的表示；以及用所述客户端装置将所述第二查询数据经由所述网络发射到所述视觉搜索装置以精炼所述第一查询数据。

在另一实例中，描述一种用于在网络系统中执行视觉搜索的方法，其中客户端装置将查询数据经由网络发射到视觉搜索装置。所述方法包括：用所述视觉搜索装置经由所述网络从所述客户端装置接收第一查询数据，其中所述第一查询数据表示从图像提取且通过以第一量化等级量化而压缩的一组图像特征描述符；用所述视觉搜索装置使用第一查询数据执行所述视觉搜索；以及经由所述网络从所述客户端装置接收第二查询数据，其中所述第二查询数据加强所述第一数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述组图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更精细更准确的对所述图像特征描述符的表示。所述方法还包括用所述视觉搜索装置以所述第二查询数据更新所述第一查询数据以产生表示以所述第二量化等级量化的所述图像特征描述符的经更新第一查询数据；以及用所述视觉搜索装置使用所述经更新第一查询数据执行所述视觉搜索。

在另一实例中，描述一种客户端装置，其将查询数据经由网络发射到视觉搜索装置以便执行视觉搜索。所述客户端装置包括：存储器，其存储界定图像的数据；特征提取单元，其从所述图像提取一组图像特征描述符，其中所述图像特征描述符界定所述图像的至少一个特征；特征压缩单元，其以第一量化等级量化所述图像特征描述符以产生表示以所述第一量化等级量化的所述图像特征描述符的第一查询数据；以及接口，其将所述第一查询数据经由所述网络发射到所述视觉搜索装置。所述特征压缩单元确定加强所述第一查询数据的第二查询数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更精细更准确的对所述图像特征描述符的表示。所述接口将所述第二查询数据经由所述网络发射到所述视觉搜索装置以连续精炼所述第一查询数据。

在另一实例中，描述一种用于在网络系统中执行视觉搜索的视觉搜索装置，其中客户端装置将查询数据经由网络发射到所述视觉搜索装置。所述视觉搜索装置包括：接口，其经由所述网络从所述客户端装置接收第一查询数据，其中所述第一查询数据表示从图像提取且通过以第一量化等级量化而压缩的一组图像特征描述符；以及特征匹配单元，其使用所述第一查询数据执行所述视觉搜索。所述接口进一步经由所述网络从所述客户端装置接收第二查询数据，其中所述第二查询数据加强所述第一数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更精细更准确的对所述图像特征描述符的表示。所述视觉搜索装置还包括特征重构单元，其以所述第二查询数据更新所述第一查询数据以产生表示以第二量化等级量化的所述图像特征描述符的经更新第一查询数据。所述特征匹配单元使用所述经更新第一查询数据执行所述视觉搜索。

在另一实例中，描述一种装置，其将查询数据经由网络发射到视觉搜索装置。所述装置包括：用于存储界定查询图像的数据的装置；用于从所述查询图像提取一组图像特征描述符的装置，其中所述图像特征描述符界定所述查询图像的至少一个特征；用于以第一量化等级量化所述组图像特征描述符以产生表示以所述第一量化等级量化的所述组图像特征描述符的第一查询数据的装置。所述装置还包括：用于将所述第一查询数据经由所述网络发射到所述视觉搜索装置的装置；用于确定加强所述第一查询数据的第二查询数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述组图像特征描述符的装置，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更准确的对所述组图像特征描述符的表示；以及用于将所述第二查询数据经由所述网络发射到所述视觉搜索装置以精炼所述第一查询数据的装置。

在另一实例中，描述一种用于在网络系统中执行视觉搜索的装置，其中客户端装置将查询数据经由网络发射到视觉搜索装置。所述装置包括：用于经由所述网络从所述客户端装置接收第一查询数据的装置，其中所述第一查询数据表示从图像提取且通过以第一量化等级量化而压缩的一组图像特征描述符；用于使用所述第一查询数据执行所述视觉搜索的装置；以及用于经由所述网络从所述客户端装置接收第二查询数据的装置，其中所述第二查询数据加强所述第一数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述组图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更准确的对所述图像特征描述符的表示。所述装置还包括：用于以所述第二查询数据更新所述第一查询数据以产生表示以所述第二量化等级量化的所述图像特征描述符的经更新第一查询数据的装置；以及用于使用所述经更新第一查询数据执行所述视觉搜索的装置。

在另一实例中，一种包括指令的非暂时性计算机可读媒体，所述指令在被执行时致使一个或一个以上处理器：存储界定查询图像的数据；从所述查询图像提取图像特征描述符，其中所述图像特征描述符界定所述查询图像的特征；以第一量化等级量化所述图像特征描述符以产生表示以所述第一量化等级量化的所述图像特征描述符的第一查询数据；将所述第一查询数据经由所述网络发射到所述视觉搜索装置；确定加强所述第一查询数据的第二查询数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更准确的对所述图像特征描述符数据的表示；以及将所述第二查询数据经由所述网络发射到所述视觉搜索装置以连续精炼所述第一查询数据。

在另一实例中，一种包括指令的非暂时性计算机可读媒体，所述指令在被执行时致使一个或一个以上处理器：经由所述网络从所述客户端装置接收第一查询数据，其中所述第一查询数据表示从图像提取且通过以第一量化等级量化而压缩的图像特征描述符；使用所述第一查询数据执行所述视觉搜索；经由所述网络从所述客户端装置接收第二查询数据，其中所述第二查询数据加强所述第一数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更准确的对所述图像特征描述符的表示；以所述第二查询数据更新所述第一查询数据以产生表示以第二量化等级量化的所述图像特征描述符的经更新第一查询数据；以及使用所述经更新第一查询数据执行所述视觉搜索。

在另一实例中，描述一种用于执行视觉搜索的网络系统。所述网络系统包括：客户端装置；视觉搜索装置；以及网络，所述客户端装置和视觉搜索装置介接到所述网络以彼此通信以执行所述视觉搜索。所述客户端装置包含：非暂时性计算机可读媒体，其存储界定图像的数据；客户端处理器，其从所述图像提取图像特征描述符，其中所述图像特征描述符界定所述图像的特征且以第一量化等级量化所述图像特征描述符以产生表示以所述第一量化等级量化的所述图像特征描述符的第一查询数据；以及第一网络接口，其将所述第一查询数据经由所述网络发射到所述视觉搜索装置。所述视觉搜索装置包含：第二网络接口，其经由所述网络从所述客户端装置接收所述第一查询数据；以及服务器处理器，其使用所述第一查询数据执行所述视觉搜索。所述客户端处理器确定加强所述第一查询数据的第二查询数据，使得当以所述第二查询数据更新所述第一查询数据时，所述经更新第一查询数据表示以第二量化等级量化的所述图像特征描述符，其中所述第二量化等级实现比当以所述第一量化等级量化时实现的情形更准确的对所述图像特征描述符的表示。所述第一网络接口将所述第二查询数据经由所述网络发射到所述视觉搜索装置以连续精炼所述第一查询数据。所述第二网络接口经由所述网络从所述客户端装置接收所述第二查询数据。所述服务器以所述第二查询数据更新所述第一查询数据以产生表示以第二量化等级量化的所述图像特征描述符的经更新第一查询数据，且使用所述经更新第一查询数据执行所述视觉搜索。

附图说明

图1是说明实施本发明中描述的连续可精炼特征描述符量化技术的图像处理系统的框图。

图2是更详细说明图1的特征压缩单元的框图。

图3是更详细说明图1的特征重构单元的框图。

图4是说明视觉搜索客户端装置在实施本发明中描述的连续可精炼特征描述符量化技术时的示范性操作的流程图。

图5是说明视觉搜索服务器在实施本发明中描述的连续可精炼特征描述符量化技术时的示范性操作的流程图。

图6是说明特征提取单元确定用于执行关键点提取的高斯差(DoG)金字塔的过程的图。

图7是说明在确定高斯差(DoG)金字塔之后的关键点的检测的图。

图8是说明特征提取单元确定梯度分布和定向直方图的过程的图。

图9A、9B是描绘特征描述符以及根据本发明中描述的技术确定的重构点的图。

图10是说明关于实施本发明中描述的技术的系统的等待时间的时间图。

具体实施方式

大体上，本发明描述用于在可称为“客户端装置”和视觉搜索服务器的包含移动便携式或其它电力宝贵的装置的网络环境中执行视觉搜索的技术。并非将图像完整地发送到视觉搜索服务器，客户端装置局部地执行特征提取以从存储在客户端装置上的图像以所谓的“特征描述符”的形式提取特征。在若干实例中，这些特征描述符包括直方图。根据本发明中描述的技术，客户端装置可以连续可精炼方式量化这些特征描述符(其也经常是以直方图的形式)。以此方式，客户端装置可基于在第一粗略量化等级下量化的特征描述符而起始视觉搜索，同时如果视觉搜索需要关于此特征描述符的额外信息则精炼特征描述符的量化。因此，可能发生某一量的并行处理，因为客户端装置和服务器可能两者同时工作以执行视觉搜索。

举例来说，客户端装置可首先以第一粗略量化等级量化特征描述符。随后将此粗略量化的特征描述符发送到视觉搜索服务器作为第一查询数据，可继续基于此第一查询数据而执行视觉搜索。在以粗略量化的特征描述符执行此视觉搜索的同时，客户端装置可确定加强第一查询数据的额外或第二查询数据，使得当以第二查询数据更新第一查询数据时，经更新的第一查询数据代表在第二量化等级下量化的直方图特征描述符。

以此方式，所述技术可减少与执行视觉搜索相关联的等待时间，因为查询数据是反复确定的且与视觉搜索服务器执行视觉搜索同时地由客户端装置提供到视觉搜索服务器。因此，并非发射整个图像(可消耗大量带宽)且接着等待视觉搜索服务器完成视觉搜索，所述技术可发送特征描述符且进而节省带宽。而且，所述技术可避免完整地发送图像特征描述符，且提供以减少等待时间的方式连续精炼图像特征描述符的方法。所述技术可通过以促进对先前发送的查询数据的更新以使得经更新查询数据提供以更精细、更完整或更准确量化水平量化的图像特征描述符的方式谨慎地使位流或查询数据结构化来实现此等待时间减少。

图1是说明实施本发明中描述的连续可精炼量化技术的图像处理系统10的框图。在图1的实例中，图像处理系统10包含客户端装置12、视觉搜索服务器14和网络16。客户端装置12在此实例中表示移动装置，例如膝上型计算机、所谓的迷你笔记本、个人数字助理(PDA)、蜂窝式或移动电话或手持机(包含所谓的“智能电话”)、全球定位系统(GPS)装置、数码相机、数字媒体播放器、游戏装置或能够与视觉搜索服务器14通信的任一其它移动装置。虽然在本发明中相对于移动客户端装置12来描述，但本发明中描述的技术在此方面不应限于移动客户端装置。而是，所述技术可由能够经由网络16或任一其它通信媒体与视觉搜索服务器14通信的任一装置实施。

视觉搜索服务器14表示通常以传输控制协议(TCP)连接的形式接受连接且以其自己的TCP连接进行响应以形成用以接收查询数据并提供识别数据的TCP会话的服务器装置。视觉搜索服务器14可表示视觉搜索服务器装置，因为视觉搜索服务器14执行或以其它方式实施视觉搜索算法以识别图像内的一个或一个以上特征或对象。在一些实例中，视觉搜索服务器14可位于将移动客户端装置互连到包交换或数据网络的蜂窝式接入网络的基站中。

网络16表示使客户端装置12和视觉搜索服务器14互连的公用网络，例如因特网。通常，网络16实施开放系统互连(OSI)模型的各个层以促进客户端装置12与视觉搜索服务器14之间的通信或数据的传送。网络16通常包含任一数目的网络装置，例如交换机、集线器、路由器、服务器，以实现客户端装置12与视觉搜索服务器14之间的数据传送。虽然展示为单个网络，但网络16可包括经互连以形成网络16的一个或一个以上子网络。这些子网络可包括服务提供者网络、接入网络、后端网络或在公用网络中通常采用以提供通过网络16的数据传送的任一其它类型的网络。虽然在此实例中描述为公用网络，但网络16可包括通常不可被公众接入的专用网络。

如图1的实例中所示，客户端装置12包含特征提取单元18、特征压缩单元20、接口22和显示器24。特征提取单元18表示根据特征提取算法执行特征提取的单元，所述算法例如是经压缩梯度直方图(CHoG)算法或以直方图形式提取特征且将这些直方图量化为类型的任一其它特征描述提取算法。通常，特征提取单元18对图像数据26进行操作，所述图像数据可使用包含在客户端装置12内的相机或其它图像俘获装置(图1的实例中未图示)局部地俘获。或者，客户端装置12可借助于局部地经由与另一计算装置的有线连接或经由任一其它有线或无线通信形式从网络16下载此图像数据26来存储图像数据26而不自己俘获此图像数据。

虽然下文更详细描述，但特征提取单元18概括来说可通过对图像数据26进行高斯模糊以产生两个连续的高斯模糊图像来提取特征描述符28。高斯模糊通常涉及在经界定尺度下将图像数据26与高斯模糊函数进行卷积。特征提取单元18可递增地卷积图像数据26，其中所得的高斯模糊图像通过尺度空间中的常数彼此分离。特征提取单元18随后堆叠这些高斯模糊图像以形成可称为“高斯金字塔”或“高斯差金字塔”的事物。特征提取单元18随后比较两个连续堆叠的高斯模糊图像以产生高斯差(DoG)图像。DoG图像可形成称为“DoG空间”的事物。

基于此DoG空间，特征提取单元18可检测关键点，其中关键点指代围绕图像数据26中的特定样本点或像素的从几何角度来看受到潜在关注的像素区或像素片。通常，特征提取单元18将关键点识别为经构造DoG空间中的局部最大值和/或局部最小值。特征提取单元18随后基于其中检测到关键点的片的局部图像梯度的方向为这些关键点指派一个或一个以上定向或方向。为了表征这些定向，特征提取单元18可依据梯度定向直方图来界定定向。特征提取单元18随后将特征描述符28界定为位置和定向(例如，借助于梯度定向直方图)。在界定特征描述符28之后，特征提取单元18将此特征描述符28输出到特征压缩单元20。特征提取单元18可使用此过程输出一组特征描述符28。

特征压缩单元20表示相对于由特征提取单元18用以界定这些特征描述符的数据量来说压缩或以其它方式减少用以界定特征描述符(例如特征描述符28)的数据量的单元。为了压缩特征描述符，特征压缩单元20可执行称为类型量化的形式的量化以压缩特征描述符28。在此方面，并非完整地发送由特征描述符28界定的直方图，特征压缩单元20执行类型量化以将直方图表示为所谓的“类型”。通常，类型是直方图的经压缩表示(例如，其中类型表示直方图的形状而非完整直方图)。类型通常表示符号的一组频率，且在直方图的上下文中可表示直方图的梯度分布的频率。换句话说，类型可表示产生了特征描述符28中的对应一者的源的真实分布的估计。在此方面，对于类型的编码和发射可视为等效于对于分布的形状的编码和发射，因为其可基于特定样本(例如，在此实例中其为由特征描述符28中的对应一者界定的直方图)来估计。

给定特征描述符28和量化等级(此处可在数学上表示为“n”)，特征压缩单元20针对特征描述符28中的每一者计算具有参数k₁，...k_m(其中m表示维度的数目)的类型。每一类型可表示具有给定公分母的一组有理数，其中所述有理数总和为1。特征描述符28可随后使用词典枚举将此类型编码为索引。换句话说，对于具有给定公分母的所有可能类型，特征压缩单元28基于这些类型的词典排序而有效地将索引指派给这些类型中的每一者。特征压缩单元28进而将特征描述符28压缩为单一词典排列的索引，且以查询数据30A、30B的形式将这些经压缩特征描述符输出到接口22。

虽然关于词典排列来描述，但可关于任一其它类型的排列来使用所述技术，只要为客户端装置和视觉搜索服务器两者提供此排列即可。在一些实例中，客户端装置可将排列模式以信号发送到视觉搜索服务器，其中客户端装置和视觉搜索服务器可协商排列模式。在其它实例中，此排列模式可在客户端装置和视觉搜索服务器两者中静态地配置，以避免与执行视觉搜索相关联的信令和其它开销。

接口22表示能够经由网络16与视觉搜索服务器14通信的任一类型的接口，包含无线接口和有线接口。接口22可表示无线蜂窝式接口，且包含经由无线蜂窝式网络与网络16以及经由网络16与视觉搜索服务器14进行通信所必要的硬件或其它组件，例如天线、调制器和类似物。在此实例中，虽然在图1的实例中未图示，但网络16包含无线蜂窝式接入网络，无线蜂窝式接口22通过所述网络与网络16通信。显示器24表示能够显示例如图像数据26的图像或任一其它类型数据的任一类型的显示单元。显示器24可例如表示发光二极管(LED)显示装置、有机LED(OLED)显示装置、液晶显示器(LCD)装置、等离子显示装置或任一其它类型的显示装置。

视觉搜索服务器14包含接口32、特征重构单元34、特征匹配单元36以及特征描述符数据库38。接口32可类似于接口22，因为接口32可表示能够与例如网络16的网络通信的任一类型的接口。特征重构单元34表示对经压缩特征描述符进行解压缩以从经压缩特征描述符重构特征描述符的单元。特征重构单元34可执行与由特征压缩单元20执行的操作相反的操作，因为特征重构单元34执行逆量化(经常称为重构)以从经压缩特征描述符重构特征描述符。特征匹配单元36表示执行特征匹配以基于经重构特征描述符识别图像数据26中的一个或一个以上特征或对象的单元。特征匹配单元36可存取特征描述符数据库38以执行此特征识别，其中特征描述符数据库38存储界定特征描述符且使这些特征描述符中的至少一些与识别数据相关联的数据，所述识别数据识别从图像数据26提取的对应特征或对象。在基于例如经重构特征描述符40A(此处也可称为“查询数据40A”，因为此数据表示用以执行视觉搜索或查询的视觉搜索查询数据)的经重构特征描述符成功识别从图像数据26提取的特征或对象后，特征匹配单元36即刻返回此识别数据作为识别数据42。

起初，客户端装置12的用户与客户端装置12介接以起始视觉搜索。用户可与由显示器24呈现的用户接口或其它类型的接口介接以选择图像数据26，且随后起始视觉搜索以识别作为存储为图像数据26的图像的焦点的一个或一个以上特征或对象。举例来说，图像数据26可指定一件著名艺术品的图像。用户可能已使用客户端装置12的图像俘获单元(例如，相机)俘获此图像，或者从网络16或经由与另一计算装置的有线或无线连接本地地下载此图像。在任一情况下，在选择图像数据26之后，在此实例中，用户起始视觉搜索以通过例如名称、艺术家和完成日期来识别所述件著名艺术品。

响应于起始视觉搜索，客户端装置12调用特征提取单元18来提取描述通过对图像数据26的分析发现的所谓的“关键点”中的一者的至少一个特征描述符28。特征提取单元18将此特征描述符28转发到特征压缩单元20，特征压缩单元20继续压缩特征描述符28且产生查询数据30A。特征压缩单元20将查询数据30A输出到接口22，接口22将查询数据30A经由网络16转发到视觉搜索服务器14。

视觉搜索服务器14的接口32接收查询数据30A。响应于接收到查询数据30A，视觉搜索服务器14调用特征重构单元34。特征重构单元34尝试基于查询数据30A重构特征描述符28且输出经重构特征描述符40A。特征匹配单元36接收经重构特征描述符40A且基于特征描述符40A执行特征匹配。特征匹配单元36通过存取特征描述符数据库38且遍历由特征描述符数据库38存储为数据的特征描述符以识别大体上匹配的特征描述符而执行特征匹配。在基于经重构特征描述符40A成功识别从图像数据26提取的特征后，特征匹配单元36即刻输出与存储在特征描述符数据库38中的在某种程度上匹配(经常表达为阈值)经重构特征描述符40A的特征描述符相关联的识别数据42。接口32接收此识别数据42且将识别数据42经由网络16转发到客户端装置12。

客户端装置12的接口22接收此识别数据42且经由显示器24呈现此识别数据42。也就是说，接口22将识别数据42转发到显示器24，显示器24随后经由用户接口呈现或显示此识别数据42，所述用户接口例如为用以起始针对图像数据26的视觉搜索的用户接口。在此实例中，识别数据42可包括所述件艺术品的名称、艺术家的名字、所述件艺术品的完成日期以及与此件艺术品有关的任何其它信息。在一些实例中，接口22将识别数据转发到在客户端装置12内执行的视觉搜索应用程序，所述应用程序随后使用此识别数据(例如，通过经由显示器24呈现此识别数据)。

虽然本发明中描述各种组件、模块或单元以强调经配置以执行所揭示技术的装置的功能方面，但这些单元不一定需要通过不同硬件单元来实现。而是，各种单元可在硬件单元中组合或由互操作硬件单元(包含如上所述的一个或一个以上处理器)的集合结合存储到计算机可读媒体的合适软件和/或固件来提供。在此方面中，本发明中对单元的参考既定表示可能或可能不实施为单独硬件单元和/或硬件与软件单元的不同功能单元。

在执行这种形式的联网视觉搜索时，客户端装置12消耗电力或能量来提取特征描述符28且随后压缩这些特征描述符28以产生查询数据30A，所述电力或能量在移动或便携式装置情境中在这些装置采用电池或其它能量储存装置来实现便携性的意义上经常是有限的。在一些实例中，可不调用特征压缩单元20来压缩特征描述符28。举例来说，客户端装置12在检测到可用电力或能量低于可用电力的某一阈值(例如可用电力的20％)时可不调用特征压缩单元20。客户端装置12可提供这些阈值以平衡带宽消耗与电力消耗。

通常，带宽消耗是与无线蜂窝式接入网络介接的移动装置要关注的一个问题，因为这些无线蜂窝式接入网络可能针对固定费用仅提供有限量的带宽或在一些实例中针对消耗的每千字节带宽进行收费。如果未启用压缩，例如当超过上述阈值时，客户端装置12发送特征描述符28作为查询数据30A而不会首先压缩特征描述符28。虽然避免压缩可节省电力，但发送未经压缩特征描述符28作为查询数据30A可增加消耗的带宽量，这又可增加与执行视觉搜索相关联的成本。在这个意义上，当执行联网视觉搜索时，电力和带宽消耗两者都是问题。

与联网视觉搜索相关联的另一要关注的问题是等待时间。通常，特征描述符28经界定为已从16个直方图导出的128个元素的向量，这些直方图中的每一者具有8个区间(bin)。特征描述符28的压缩可减少等待时间，因为传送较少数据通常比传送相对较多数据花费更少时间。虽然压缩可在发送特征描述符28的总时间方面减少等待时间，但网络16在网络16将特征描述符28从客户端装置12发射到视觉搜索服务器14所花费的时间量方面引入了等待时间。此等待时间可减少或以其它方式不利地影响用户体验，尤其是引入大量等待时间的情况下，例如当需要若干特征描述符来肯定地识别图像的一个或一个以上对象时。在一些实例中，并非通过要求插入额外延迟的额外特征描述符来继续执行视觉搜索，视觉搜索服务器14可停止或以其它方式暂停视觉搜索且返回指示所述搜索已失败的信息数据42。

根据本发明中描述的技术，客户端装置12的特征压缩单元20执行一种形式的特征描述符压缩，其涉及特征描述符28的连续可精炼量化。换句话说，并非完整地发送图像数据26、未经压缩特征描述符28或甚至在给定预定量化等级(通常借助于实验来得到)下量化的特征描述符28，所述技术产生表示在第一量化等级下量化的特征描述符28的查询数据30A。此第一量化等级通常没有常规上用以量化例如特征描述符28的特征描述符的给定预定量化等级那样精细或完整。

特征压缩单元20可随后以加强查询数据30A的方式确定查询数据30B，使得当以查询数据30B更新查询数据30A时，经更新第一查询数据30A表示在第二量化等级下量化的特征描述符28，所述第二量化等级实现比当以第一量化等级量化时实现的情况更完整的对特征描述符28的表示(即，较低量化程度)。在此意义上，特征压缩单元20可连续地精炼特征描述符28的量化，因为第一查询数据30A可产生且随后以第二查询数据30B连续更新以实现对特征描述符28的更完整的表示。

考虑查询数据30A表示以通常不如用以常规地量化特征描述符的量化等级精细的第一量化等级量化的特征描述符28，根据所述技术得出的查询数据30A可在大小上小于经常规量化的特征描述符，这可减少带宽消耗，同时也改善等待时间。而且，客户端装置12可在确定查询数据30B的同时发射加强查询数据30B的查询数据30A。视觉搜索服务器16可随后接收查询数据30A且还与客户端装置12确定查询数据30B同时地开始视觉搜索。以此方式，由于在确定加强查询数据30A的查询数据30B的同时执行视觉搜索的同时特征，可大大减少等待时间。

在操作中，客户端装置12存储界定查询图像的图像数据26，如上所述。特征提取单元18从界定查询图像的特征的图像数据26提取图像特征描述符28。特征压缩单元20随后实施本发明中描述的技术以在第一量化等级下量化特征描述符28以产生表示以第一量化等级量化的特征描述符28的第一查询数据30A。第一查询数据30A是以用实现在由第二查询数据30B更新时对第一查询数据30A的连续加强的方式界定。特征压缩单元20将此查询数据30A转发到接口22，接口22将查询数据30A发射到视觉搜索服务器14。视觉搜索服务器14的接口32接收查询数据30A，借此视觉搜索服务器14调用特征重构单元34来重构特征描述符28。特征重构单元34随后输出经重构特征描述符40A。特征匹配单元36随后基于经重构特征描述符40A通过存取特征描述符数据库38来执行视觉搜索。

与特征匹配单元36使用经重构特征描述符40A执行视觉搜索同时，特征压缩单元20确定加强第一查询数据30A的第二查询数据30B，使得当以第二查询数据30B更新第一查询数据30A时，经更新第一查询数据30A表示以第二量化等级量化的特征描述符28。又，此第二量化等级实现比当以第一量化等级量化时实现的情况更精细或更完整的对特征描述符28的表示。特征压缩单元20随后将查询数据30B输出到接口22，接口22将第二查询数据30B经由网络16发射到视觉搜索服务器14以连续精炼第一查询数据30A。

视觉搜索服务器14的接口32接收第二查询数据30B，然后视觉搜索服务器14调用特征重构单元34。特征重构单元34可随后通过以第二查询数据30B更新第一查询数据30A以产生经重构特征描述符40B(又可称为“经更新查询数据40B”，因为此数据涉及用以执行视觉搜索或查询的视觉搜索或查询数据)而以较精细等级重构特征描述符28。特征匹配单元36可随后使用经更新查询数据40B而非查询数据40A来重新起始视觉搜索。

虽然图1的实例中未图示，但使用越来越精细的量化等级连续精炼特征描述符28且随后重新起始视觉搜索的此过程可继续，直到特征匹配单元36肯定地识别从图像数据26提取的一个或一个以上对象和特征、确定此特征或对象无法识别或以其它方式到达可终止视觉搜索过程的消耗电力、等待时间或其它阈值为止。举例来说，客户端装置12可例如通过将当前确定的电力量与电力阈值进行比较来确定其具有足够电力来再次精炼特征描述符28。

响应于此确定，客户端装置12可调用特征压缩单元20以与此重新起始的视觉搜索同时地确定加强第二查询数据30B的第三查询数据，使得当以此第三查询数据更新查询数据40B时，此经更新第二查询数据产生已以比第二量化等级甚至更精细的第三量化等级量化的经重构特征描述符。视觉搜索服务器14可接收此第三查询数据且相对于此相同但以第三量化等级量化的特征描述符重新起始视觉搜索。

因此，不同于基于第一组特征描述符且随后基于连续不同特征描述符(因为其通常不同于第一特征描述符或是从完全不同图像提取且因此描述完全不同图像)执行视觉搜索的常规系统，本发明中描述的技术起始针对以第一量化等级量化的特征描述符的视觉搜索，且随后重新起始针对相同但以第二不同且通常更精细或更完整的量化等级量化的特征描述符的视觉搜索。此过程可如上论述基于反复而继续，使得相同特征描述符的连续版本以连续变小的程度量化，即从粗略特征描述符数据到较精细特征描述符数据。通过在一些实例中以足够细节发射查询数据30A以起始视觉搜索，同时确定实现视觉搜索的重新起始(但是相对于比第一查询数据40A更精细或更完整量化的查询数据40B)的第二查询数据30B，考虑到视觉搜索是与量化同时执行，所述技术可改善等待时间。

在一些实例中，所述技术可在仅将粗略量化的第一查询数据提供到视觉搜索服务器之后终止，假定视觉搜索服务器能够在某个可接受程度上基于此粗略量化的第一查询数据识别特征。在此实例中，客户端装置无需连续量化特征描述符以提供界定足够数据以使视觉搜索服务器能够以第二更精细量化程度重构特征描述符的第二查询数据。以此方式，所述技术可相比于常规技术改善等待时间，因为所述技术提供较粗略量化的特征描述符，其可比常规系统中通常的较精细量化的特征描述符需要更少的时间来确定。因此，视觉搜索服务器可相比于常规系统更快地识别特征。

而且，查询数据30B并不重复来自查询数据30A的任何数据，所述数据随后用作执行视觉搜索的基础。换句话说，查询数据30B加强查询数据30A且不代替查询数据30A的任何部分。在此方面中，所述技术可不会比发送常规量化的特征描述符28消耗网络16中的更多带宽(假定所述技术采用的第二量化等级大约等于常规上采用的量化等级)。带宽消耗的仅有增加的发生是因为查询数据30A、30B两者需要包标头来遍历网络12并且需要其它非实质量的元数据，这常规上不需要，因为任一给定特征描述符仅被量化和发送一次。又，此带宽增加与通过应用本发明中描述的技术实现的等待时间减少相比通常是微小的。

图2是更详细说明图1的特征压缩单元20的框图。如图2的实例中所示，特征压缩单元20包含可精炼晶格量化单元50和索引映射单元52。可精炼晶格量化单元50表示实施本发明中描述的技术以提供特征描述符的连续精炼的单元。可精炼晶格量化单元50除了实施本发明中描述的技术之外还执行确定上文所述的类型的一种形式的晶格量化。

当执行晶格量化时，可精炼晶格量化单元50首先基于基本量化等级54(可在数学上称为n)和特征描述符28计算晶格点k′₁，...，k′_m。可精炼晶格量化单元50随后对这些点进行求和以确定n′且将n与n进行比较。如果n′等于n，则可精炼晶格量化单元50将k_i(其中i＝1，...，m)设定为k′_i。如果n′不等于n，那么可精炼晶格量化单元50将误差计算为k′_i、n和特征描述符28的函数且随后对这些误差进行分类。可精炼晶格量化单元50随后确定n′减n是否大于0。如果n′减n大于0，那么可精炼晶格量化单元50将具有最大误差的那些k′_i值递减1。如果n′减n大于0，那么可精炼晶格量化单元50将具有最小误差的那些k′_i值递增1。如果以此方式递增或递减，则可精炼晶格量化单元50将k_i设定为经调整k′_i值。可精炼晶格量化单元50随后将这些k_i值作为类型56输出到索引映射单元52。

索引映射单元52表示将类型56唯一地映射到索引的单元。索引映射单元52可在数学上将此索引计算为识别针对具有与确定类型56的维度相同的维度的特征描述符计算的所有可能类型的词典排列(又以直方图的形式表达为概率分布)中的类型56的索引。索引映射单元52可计算类型56的此索引且输出此索引作为查询数据30A。

在操作中，可精炼晶格量化单元50接收特征描述符28且计算具有k₁，...，k_m参数的类型56。可精炼晶格量化单元50随后将类型56输出到索引映射单元52。索引映射单元52将类型56映射到唯一地识别具有维度m的特征描述符可能的所有类型的集合中的类型56的索引。索引映射单元52随后输出此索引作为查询数据30A。此索引可视为表示位于在概率分布上均匀界定的Voronoi单元的中心的重构点的晶格，如关于图9A、9B更详细展示和描述。如上所述，视觉搜索服务器14接收查询数据30A、确定经重构特征描述符40A且基于经重构特征描述符40A执行视觉搜索。虽然关于Voronoi单元来描述，但所述技术可关于能够促进空间的分段以实现索引映射的类似分类的任一其它类型的均匀或不均匀单元来实施。

通常，虽然查询数据30A在客户端与服务器14之间通行和/或虽然视觉搜索服务器14确定经重构特征描述符40A和/或基于经重构特征描述符40A执行视觉搜索，但可精炼晶格量化单元50实施本发明中描述的技术以用一方式确定查询数据30B，以使得当由查询数据30B加强查询数据30A时，经加强或经更新查询数据30A表示以比基本或第一量化等级更精细的量化等级量化的特征描述符28。可精炼晶格量化单元50将查询数据30B确定为一个或一个以上偏移向量，其识别从重构点的偏移q1，...，qm，它们是类型参数k₁，...，k_m的函数(即，)。

可精炼晶格量化单元50以两种方式中的一种确定查询数据30B。以第一方式，可精炼晶格量化单元50通过用查询数据30A将用以表示特征描述符28的重构点的数目加倍来确定查询数据30B。在此方面中，第二量化等级可视为第一或基本量化等级54的两倍。关于图9A的实例中所示的实例晶格，这些偏移向量可将额外重构点识别为每一Voronoi单元的面的中心。如下文更详细描述，虽然将重构点的数目加倍且进而以较大粒度界定特征描述符28，但连续量化特征描述符28的此第一方式可需要界定基本量化等级54以使得其充分大于在此实例中表达为直方图的概率分布的维度(即，n界定为大于m)以避免与仅以第二较高量化等级发送重构点的晶格相比在发送这些向量所需的位数目方面引起过多开销(且进而过多带宽消耗)。

虽然在大多数或至少一些实例中，基本量化等级54可界定为大于概率分布(或在此实例中为直方图)的维度，但在一些实例中，基本量化等级54无法界定为充分大于概率分布的维度。在这些实例中，可精炼晶格量化单元50可替代地根据使用双晶格的第二方式来计算偏移向量。也就是说，并非将由查询数据30A界定的重构点的数目加倍，可精炼晶格量化单元50借助于由索引映射单元52映射的索引来确定偏移向量以便填充表达为查询数据30A的重构点晶格中的空穴。又，关于图9B的实例更详细展示和描述此加强。考虑这些偏移向量界定落在Voronoi单元的相交点或顶点处的重构点的额外晶格，表达为查询数据30B的这些偏移向量可视为除了由查询数据30A表达的重构点晶格之外还界定重构点的又一晶格；因此，这引起此第二方式采用双晶格的特征化。

虽然连续精炼特征描述符28的量化等级的此第二方式不需要基本量化等级54界定为大体上大于下伏概率分布的维度，但此第二方式在计算偏移向量所需的操作数目方面可能较复杂。考虑到执行额外操作可增加电力消耗，在一些实例中，可仅在可获得足够电力时使用连续精炼特征描述符28的量化的此第二方式。电力充足性可相对于用户界定的、应用界定的或静态界定的电力阈值来确定，使得可精炼晶格量化单元50仅在当前电力超过此阈值时采用此第二方式。在其它实例中，可精炼晶格量化单元50可总是采用此第二方式来避免在基本量化等级无法界定为与概率分布的维度相比充分足够大的那些实例中引入开销。或者，可精炼晶格量化单元50可总是采用第一方式来避免与第二方式相关联的实施方案复杂性和所得电力消耗。

图3是更详细说明图1的特征重构单元34的框图。如图3的实例中所示，特征重构单元34包含类型映射单元60、特征恢复单元62和特征加强单元64。类型映射单元60表示执行索引映射单元52的逆过程以将查询数据30A的索引映射回到类型56的单元。特征恢复单元62表示基于类型56恢复特征描述符28以输出经重构特征描述符40A的单元。特征恢复单元62在将特征描述符28精简到类型56时执行上文关于可精炼晶格量化单元50描述的操作的逆操作。特征加强单元64表示接收查询数据30B的偏移向量且通过基于偏移向量将重构添加到由类型56界定的重构点晶格而加强类型56的单元。特征加强单元64将查询数据30B的偏移向量应用于由类型56界定的重构点晶格以确定额外重构点。特征加强单元64随后以这些确定的额外重构点更新类型56，将经更新类型58输出到特征恢复单元62。特征恢复单元62随后从经更新类型58恢复特征描述符28以输出经重构特征描述符40B。

图4是说明视觉搜索客户端装置(例如图1的实例中所示的客户端装置12)在实施本发明中描述的连续可精炼量化技术时的示范性操作的流程图。虽然关于特定装置(即，客户端装置12)来描述，但所述技术可由能够关于概率分布执行数学运算的任一装置实施，以便减少此概率分布的另外使用中的等待时间，例如针对执行视觉搜索。另外，虽然在视觉搜索的情境中描述，但所述技术可在其它情境中实施以促进概率分布的连续精炼。

起初，客户端装置12可存储图像数据26。客户端装置12可包含用以俘获图像数据26的俘获装置，例如照相机或摄像机。或者，客户端装置12可下载或以其它方式接收图像数据26。客户端装置12的用户或其它操作者可与由客户端装置12提供的用户接口(但为了容易说明而在图1的实例中未图示)交互以起始相对于图像数据26的视觉搜索。此用户接口可包括图形用户接口(GUI)、命令行接口(CLI)或用于与装置的用户或操作者介接而采用的任一其它类型的用户接口。

响应于视觉搜索的起始，客户端装置12调用特征提取单元18。一旦被调用，则特征提取单元18以本发明中描述的方式从图像数据26提取特征描述符28(70)。特征提取单元18将特征描述符28转发到特征压缩单元20。在图2A的实例中更详细展示的特征压缩单元20调用可精炼晶格量化单元50。可精炼晶格量化单元50通过以基本量化等级54量化特征描述符28来将特征描述符28精简到类型56。如上所述，此特征描述符28表示梯度直方图，其为较一般的概率分布的特定实例。特征描述符28可在数学上表示为变量p。

特征压缩单元20执行一种形式的类型晶格量化以确定经提取特征描述符28的类型(72)。此类型可表示在数学上由变量Q表示的一可再生分布集合中的重构点或中心集合，其中Q可视为在离散事件集合(A)上的概率分布集合(Ω_m)的子集。又，变量m指代概率分布的维度。Q可视为重构点晶格。变量Q可用变量n修改以得到Q_n，其表示具有参数n的晶格，参数n界定所述晶格中的点密度(在某种程度上可视为量化等级)。可通过以下等式(1)在数学上界定Q_n：

$>Q_n=\left\{\right[q_1,...,q_m]\in Q^m|q_i=\frac{k_i}{n},{\Sigma }_i{k}_i=n\},...n,k_1,...,k_m\in Z^{+}.---\left(1\right)$>

在等式(1)中，Q_n的元素表示为q₁，...，q_m。变量Z⁺表示所有正整数。

对于具有给定m和n的晶格，晶格Q_n可含有由以下等式(2)在数学上表达的数目的点：

$>\left|Q_n\right|=\left(\begin{array}{c}n+m-1\\ m-1\end{array}\right).---\left(2\right)$>

而且，以基于L范数的最大距离表达的针对此类型晶格的覆盖半径是在以下等式(3)到(5)中表达的那些覆盖半径：

$>{\max }_{p\in {\Omega }_m}{{\min }_{q\in Q}}_n{d}_{\infty }(p,q)=\frac{1}{n}(1-\frac{1}{m}),---\left(3\right)$>

$>{{\max }_{p\in \Omega }}_m{{\min }_{q\in Q}}_n{d}_2(p,q)=\frac{1}{n}\sqrt{\frac{a(m-a)}{m}},---\left(4\right)$>

$>{{\max }_{p\in \Omega }}_m{{\min }_{q\in Q}}_n{d}_1(p,q)=\frac{1}{n}\frac{2a(m-a)}{m}.---\left(5\right)$>

在以上等式(3)到(5)中，变量a可由以下等式(6)在数学上表达：

另外，类型索引的直接(不可缩放或不可精炼)发射引起量化器的以下半径/速率特性，如以下等式(7)到(9)在数学上表达：

$>d_{\infty }^{*}\left[Q_n\right]({\Omega }_m,R)~2^{-\frac{R}{m-1}}\frac{1-\frac{1}{m}}{\sqrt[m-1]{(m-1)!}},---\left(7\right)$>

$>d_2^{*}\left[Q_n\right]({\Omega }_m,R)~2^{-\frac{R}{m-1}}\frac{\sqrt{\frac{a(m-a)}{m}}}{\sqrt[m-1]{(m-1)!}},---\left(8\right)$>

$>d_1^{*}\left[Q_n\right]({\Omega }_m,R)~2^{-\frac{R}{m-1}}\frac{\frac{2a(m-a)}{m}}{\sqrt[m-1]{(m-1)!}}.---\left(9\right)$>

为了以给定基本量化等级54产生此重构点集合或所谓的“类型”(可表示上述变量n)，可精炼晶格量化单元50首先根据以下等式(10)计算值k′_i：

$>n^{\prime }=\underset{i}{\Sigma }{k}_i^{\prime }.---\left(10\right)$>

等式(10)中的变量i表示来自1，...，m的值集合。如果n′等于n，则最近类型由k_i＝k′_i给定。否则，如果n′不等于n，则可精炼晶格量化单元50根据以下等式(11)计算误差δ_i：

δ_i＝k′_i-np_i，    (11)

且对这些误差分类以使得满足以下等式(12)：

$>-\frac{1}{2},,{{\delta }_j}_1,,{{\delta }_j}_2,,...,,{{\delta }_j}_m,,\frac{1}{2}.---\left(12\right)$>

可精炼晶格量化单元50随后确定n′与n之间的差，其中此差可由变量Δ表示且由以下等式(13)表达：

Δ＝n′-n。    (13)

如果Δ大于0，那么可精炼晶格量化单元50将具有最大误差的那些k′_i值递减，其可由以下等式(14)在数学上表达：

$>{k_j}_i=\left(\begin{array}{cc}{k}_{j_i}^{\prime }& j=i,...,m-\Delta -1,\\ k_{j_i}^{\prime }-1& i=m-\Delta ,...,m,\end{array},-,-,-\right)\left(14\right)$>

然而，如果Δ确定为小于0，那么可精炼晶格量化单元50将具有最小误差的那些k′_i值递增，其可由以下等式(15)在数学上表达：

$>{k_j}_i=\left(\begin{array}{cc}{k}_{j_i}^{\prime }+1& i=1,...,\left|\Delta \right|,\\ k_{j_i}^{\prime }& i=\left|\Delta \right|+1,...,m\end{array}\right).---\left(15\right)$>

假定基本量化等级或n已知，而不是以q₁，...，q_m来表达类型，可精炼晶格量化单元50将类型56表达为k₁，...，k_m的函数，如经由上述三种方式中的一者所计算。可精炼晶格量化单元50将此类型56输出到索引映射单元52。

索引映射单元52将此类型56映射到包含在查询数据30A中的索引(74)。为了将此类型56映射到索引，索引映射单元52可实施以下等式(16)，其计算指派给类型56的索引ξ(k₁，...，k_m)，其指示针对具有维度m的概率分布的所有可能类型的集合中的类型56的词典排列：

$>\xi (k_1,...,k_n)=\underset{j=1}{\overset{n-2}{\Sigma }}\underset{i=0}{\overset{k_j-1}{\Sigma }}\left(\begin{array}{c}n-i-\underset{l=1}{\overset{j-1}{\Sigma }}{k}_l+m-j-1\\ m-j-1\end{array}\right)+k_{n-1}.---\left(16\right)$>

索引映射单元56可使用二项式系数的预计算阵列来实施此等式。索引映射单元52随后产生包含经确定索引的查询数据30A(76)。客户端装置12随后将此查询数据30A经由网络16发射到视觉搜索服务器14(78)。

与索引映射单元52确定索引和/或客户端装置12发射查询数据30A和/或视觉搜索服务器14基于查询数据30A执行视觉搜索同时地，可精炼晶格量化单元50确定加强先前确定的类型56的偏移向量30B，使得当以偏移向量30B更新类型56时，此经更新或经加强的类型56可以比用以量化包含在查询数据30A内的类型56的量化等级更精细的量化等级来表达特征描述符28(80)。如上所述，可精炼晶格量化单元50起初以类型56的形式接收晶格Q_n。可精炼晶格量化单元50可实施计算偏移向量30B的两种方式中的一者或两者。

以第一方式，可精炼晶格量化单元50将基本量化等级54或n加倍以得到第二较精细量化等级，其可在数学上表达为2n。使用此第二较精细量化等级产生的晶格可表示为Q2_n，其中晶格Q_2n的点以由以下等式(17)界定的方式与晶格Q_n的点相关：

$>[\frac{{2k}_1+{\delta }_1}{2n},...,\frac{{2k}_m+{\delta }_m}{2n}],---\left(17\right)$>

其中δ₁，...，δ_m∈{-1，0，1}，使得δ₁+...+δ_m＝0。对计算偏移向量30B的此方式的评估通过考虑可在原始晶格Q_n中的点周围插入的点的数目而开始。点的数目可根据以下等式(18)计算，其中k_₁，k₀，k₁表示在位移向量[δ₁，...，δ_m]的元素当中值-1、0、1的出现次数。给定δ₁+...+δ_m＝0暗示k_₁＝k₁的条件，点的数目可由以下等式(18)计算：

根据等式(18)可确定此点数目随着η(m)～αm！而渐进地(具有大m)增长，其中α≈2.2795853。

为了对指定晶格Q_2n中的类型相对于晶格Q_n的位置所需的向量进行编码，最多需要的位的数目可使用以下等式(19)导出：

$>\log \eta \left(m\right)~m\log \left(m\right)-m\log e+\frac{1}{2}\log m+\log \left(\sqrt{2\pi }\alpha \right)+O\left(\frac{1}{m}\right).---\left(19\right)$>

将发送偏移向量所需的位的数目的此量度与发送Q_2n中的点的直接编码所需的位的数目进行比较得到以下等式(20)：

$>\frac{\log \left(\begin{array}{c}n+m-1\\ m-1\end{array}\right)+\log \eta \left(m\right)}{\log \left(\begin{array}{c}2n+m-1\\ m-1\end{array}\right)}~1+\frac{\log m-1-\log 2+O\left(\frac{\log m}{m}\right)}{\log n}+O\left(\frac{1}{{\left(\log n\right)}^2}\right).---\left(20\right)$>

大体上考虑等式(20)可观察到，为了确保类型索引的递增发射的小开销，此第一方式应以索引从晶格Q_n的直接发射开始，其中n比m大得多(＞＞)。实施第一方式的此条件可能并非总是实际的。

可精炼晶格量化单元50可替代地实施不受此条件限制的第二方式。此第二方式涉及以置于Voronoi单元的空穴或顶点中的点来加强Q_n，其中所得晶格可表示为其是根据以下等式(21)界定：

$>Q_n^{*}=\underset{i=0...m-1}{Y}{Q}_n+v_i.---\left(21\right)$>

在本发明中此晶格可称为“双类型晶格”。变量v_i表示指示到Voronoi单元的顶点的偏移的向量，其可根据以下等式(22)在数学上表达：

每一向量v_i允许其值的$>\left(\begin{array}{c}m\\ i\end{array}\right)$>置换。给定此置换次数，通过将其转换为双类型晶格而围绕Q_n中的点插入的点的总数目满足以下等式(23)中陈述的等式：

$>\kappa \left(m\right)=\underset{i=1}{\overset{m-1}{\Sigma }}\left(\begin{array}{c}m\\ i\end{array}\right)=2^m-2.---\left(23\right)$>

给定等式(23)，双类型晶格中的点相对于晶格Q_n中的点的已知位置的编码可通过最多发射在以下等式(24)中表达的位的数目来实现：

$>\log \kappa \left(m\right)~m+O\left(\frac{1}{m}\right)---\left(24\right)$>

在评估确定偏移向量30B的此第二方式时，需要在从晶格Q_n切换到时的覆盖半径的减少的估计。对于类型晶格Q_n，以下等式(25)表达覆盖半径

同时，对于双类型晶格以下等式(26)表达覆盖半径：

$>d_2^{*}\left(Q_n^{*}\right)=\underset{p\in {\Omega }_m}{\max }\underset{{q\in Q}_n^{*}}{\min }{\left|\right|p-q\left|\right|}_2=\frac{1}{n}\sqrt{\frac{(m-1)(m+1)}{12m}}~\frac{1}{2\sqrt{3}n}\sqrt{m}.---\left(26\right)$>

将这两个不同覆盖半径值进行比较，可确定从Q_n到的转变使覆盖半径减少了的因子，同时造成约m位速率的开销。此第二译码方式与基于不可精炼的Q_n晶格的译码相比的效率可根据以下等式(27)来估计：

$>\frac{\log \left(\begin{array}{c}n+m-1\\ m-1\end{array}\right)\log \kappa \left(m\right)}{\log \left(\begin{array}{c}\sqrt{3}n+m-1\\ m-1\end{array}\right)}~1+\frac{\log (2/\sqrt{3})+O\left(\frac{1}{m}\right)}{\log n}+O\left(\frac{1}{{\left(\log n\right)}^2}\right).---\left(27\right)$>

从等式(27)，可观察到，此第二译码方式随着开始晶格的基本量化等级(即，在此实例中如参数n界定)而减小，但此参数n不必相对于维度m来说相对大。可精炼晶格量化单元50可利用相对于先前确定的类型56确定偏移向量30B的这两种方式中的任一者或两者。

可精炼晶格量化单元50随后产生包含这些偏移向量的额外查询数据30B(82)。客户端装置12以上文描述的方式将查询数据30B发射到视觉搜索服务器12(84)。客户端装置12可随后确定其是否已接收到识别数据42(86)。如果客户端装置12确定其尚未接收到识别数据42(“否”86)，则客户端装置12在一些实例中可通过使用上述两种方式中的任一者确定加强已经加强的类型56的额外偏移向量来继续进一步精炼经加强类型56，产生包含这些额外偏移向量的第三查询数据，且将此第三查询数据发射到视觉搜索服务器14(80到84)。此过程在一些实例中可继续，直到客户端装置12接收到识别数据42为止。在一些实例中，当客户端装置12具有足够电力来执行此额外精炼时，客户端装置12可仅继续精炼类型56经过第一精炼，如上文论述。在任一情况下，如果客户端装置12接收到识别数据42，则客户端装置12经由显示器24呈现此识别数据42(88)。

图5是说明视觉搜索服务器(例如图1的实例中所示的视觉搜索服务器14)在实施本发明中描述的连续可精炼量化技术时的示范性操作的流程图。虽然关于特定装置(即，视觉搜索服务器14)来描述，但所述技术可由能够关于概率分布执行数学运算的任一装置实施，以便减少此概率分布的另外使用中的等待时间，例如针对执行视觉搜索。另外，虽然在视觉搜索的情境中描述，但所述技术可在其它情境中实施以促进概率分布的连续精炼。

起初，视觉搜索服务器14接收包含索引的查询数据30A，如上所述(100)。响应于接收到查询数据30A，视觉搜索服务器14调用特征重构单元34。参见图3，特征重构单元34调用类型映射单元60以用上述方式将查询数据30A的索引映射到类型56(102)。类型映射单元60将经确定类型56输出到特征恢复单元62。特征恢复单元62随后基于类型56重构特征描述符28，从而输出经重构特征描述符40A，如上所述(104)。视觉搜索服务器14随后调用特征匹配单元36，其以上述方式使用经重构特征描述符40A执行视觉搜索(106)。

如果由特征匹配单元36执行的视觉搜索不产生特征的肯定识别(“否”108)，则特征匹配单元62不产生且随后发送任何识别数据到客户端装置12。由于未接收到此识别数据，因此客户端装置12以查询数据30B的形式产生且发送偏移向量。视觉搜索服务器14接收包含这些偏移向量的此额外查询数据30B(110)。视觉搜索服务器14调用特征重构单元34以处理所接收查询数据30B。特征重构单元34一旦被调用则又调用特征加强单元64。特征加强单元64基于偏移向量而加强类型54以用较精细粒度等级来重构特征描述符28(112)。

特征加强单元64将经加强或经更新的类型58输出到特征恢复单元62。特征恢复单元62随后基于经更新类型58恢复特征描述符28以输出经重构特征描述符40B，其中经重构特征描述符40B表示以比由特征描述符40A表示的等级更精细的等级量化的特征描述符28(113)。特征恢复单元62随后将经重构特征描述符40B输出到特征匹配单元36。特征匹配单元36随后使用特征描述符40B重新起始视觉搜索(106)。此过程可继续直到识别出特征(106到113)或直到客户端装置12不再提供额外偏移向量。如果识别出特征(“是”108)，则特征匹配单元36产生且发射识别数据42到视觉搜索客户端，即在此实例中的客户端装置12(114)。

图6是说明已经确定用于特征描述符提取的高斯差(DoG)金字塔204的图。图1的特征提取单元18可通过计算高斯金字塔202中的任何两个连续高斯模糊图像的差来构造DoG金字塔204。在图1的实例中展示为图像数据26的输入图像I(x，y)经逐渐地高斯模糊以构造高斯金字塔202。高斯模糊通常涉及将原始图像I(x，y)与高斯模糊函数G(x，y，cσ)在尺度cσ下进行卷积，使得高斯模糊函数L(x，y，cσ)经界定为L(x，y，cσ)＝G(x，y，cσ)*I(x，y)。此处，G是高斯核，cσ表示用于模糊图像I(x，y)的高斯函数的标准偏差。由于c是变化的(c₀＜c₁＜c₂＜c₃＜c₄)，因此标准偏差cσ变化且获得逐渐的模糊。西格马σ是基本尺度变量(基本上为高斯核的宽度)。当初始图像I(x，y)与高斯G递增地卷积以产生模糊图像L时，模糊图像L在尺度空间中用常数因子c分离。

在DoG空间或金字塔204中，D(x，y，a)＝L(x，y，c_nσ)-L(x，y，c_n-1σ)。DoG图像D(x，y，σ)是两个邻近高斯模糊图像L在尺度c_nσ和c_n-1σ下的差。D(x，y，σ)的尺度位于c_nσ与c_n-1σ之间的某处。随着高斯模糊图像L的数目增加且为高斯金字塔202提供的近似接近连续空间，所述两个尺度也接近变为一个尺度。经卷积图像L可通过八元组来分组，其中八元组对应于标准偏差σ的值的两倍。而且，选择乘数k的值(例如，c₀＜c₁＜c₂＜c₃＜c₄)以使得每个八元组获得固定数目的经卷积图像L。随后，可从每个八元组的邻近高斯模糊图像L获得DoG图像D。在每一八元组之后，将高斯图像向下取样因子2，且随后重复所述过程。

特征提取单元18可随后使用DoG金字塔204来识别图像I(x，y)的关键点。在执行关键点检测时，特征提取单元19确定围绕图像中的特定样本点或像素的局部区或片是否为潜在受到关注的片(几何上来说)。通常，特征提取单元18识别DoG空间204中的局部最大值和/或局部最小值，且使用这些最大值和最小值的位置作为DoG空间204中的关键点位置。在图6中说明的实例中，特征提取单元18识别片206内的关键点208。找出局部最大值和最小值(也称为局部极值检测)可通过将DoG空间204中的每一像素(例如，关键点208的像素)与其八个相邻像素在同一尺度下进行比较且与两侧上的九个相邻像素(在邻近片210和212中)在相邻尺度中的每一者中进行比较(总共26个像素(9x2+8＝26))来实现。如果关键点206的像素值是片206、210和208中的全部26个进行比较的像素当中的最大值或最小值，那么特征提取单元18将此选择为关键点。特征提取单元18可进一步处理关键点以使得其位置被更准确地识别。在一些实例中，特征提取单元18可丢弃关键点中的一些，例如低对比度关键点和边缘关键点。

图7是更详细说明关键点的检测的图。在图7的实例中，片206、210和212中的每一者包含3x3像素区。特征提取单元18首先将一关注像素(例如，关键点208)与其八个相邻像素302在同一尺度(例如，片206)下进行比较且与关键点208的两侧上的邻近片210和212中的九个相邻像素304和306在相邻尺度中的每一者中进行比较。

特征提取单元18可基于局部图像梯度的方向而为每一关键点指派一个或一个以上定向或方向。通过基于局部图像性质将一致的定向指派给每一关键点，特征提取单元18可相对于此定向来表示关键点描述符，且因此实现对图像旋转的不变性。特征提取单元18随后在高斯模糊图像L中和/或关键点尺度下计算关键点208周围的相邻区中的每个像素的量值和方向。位于(x，y)处的关键点208的梯度的量值可表示为m(x，y)，且(x，y)处的关键点的定向或方向可表示为Γ(x，y)。

特征提取单元18随后使用关键点的尺度来选择具有与关键点208的尺度最接近的尺度的高斯平滑图像L，使得以尺度不变方式执行所有计算。在此尺度下对于每一图像样本L(x，y)，特征提取单元18使用像素差来计算梯度量值m(x，y)和定向Γ(x，y)。举例来说，可根据以下等式(28)计算量值m(x，y)：

$>m(x,y)=\sqrt{(L(x+1,y)-L(x-1,y){)}^2+{(L(x,y+1)-L(x,y-1))}^2}.---\left(28\right)$>

特征提取单元18可根据以下等式(29)计算方向或定向Γ(x，y)：

$>\Gamma (x,y)=\arctan \left[\frac{\left(L(x,y+1)L(x,y-1\right)}{(L(x+1,y)-L(x-1,y)}\right].---\left(29\right)$>

在等式(29)中，L(x，y)表示高斯模糊图像L(x，y，σ)在尺度σ下的样本，σ也是关键点的尺度。

特征提取单元18可针对高斯金字塔中位于上方的平面在比DoG空间中的关键点的平面高的尺度下或针对高斯金字塔中位于下方的平面在比关键点低的尺度下，一致地计算关键点的梯度。无论哪种方式，对于每一关键点，特征提取单元18在围绕关键点的矩形区域(例如，片)中均在同一尺度下计算梯度。而且，图像信号的频率在高斯模糊图像的尺度中反映。但是，SIFT和例如经压缩梯度直方图(CHoG)算法等其它算法简单地使用片(例如，矩形区域)中的所有像素处的梯度值。片是围绕关键点界定，子块是在块内界定，样本是在子块内界定，且此结构对于所有关键点保持相同，即使当关键点的尺度不同时也是如此。因此，虽然图像信号的频率随着高斯平滑滤波器在同一八元组中的连续应用而改变，但在不同尺度下识别的关键点可以用相同数目的样本来取样，无论由尺度表示的图像信号的频率改变如何。

为了表征关键点定向，特征提取单元18可通过使用例如经压缩梯度直方图(CHoG)来产生梯度定向直方图(见图4)。每一相邻像素的贡献可通过梯度量值和高斯窗来加权。直方图中的峰对应于主要定向。特征提取单元18可测量关键点相对于关键点定向的所有性质，这提供对旋转的不变性。

在一个实例中，特征提取单元18计算每一块的高斯加权梯度的分布，其中每一块是2子块乘2子块，总共4个子块。为了计算高斯加权梯度的分布，特征提取单元18形成具有若干区间的定向直方图，其中每一区间覆盖围绕关键点的区域的一部分。举例来说，定向直方图可具有36个区间，每一区间覆盖360度定向范围的10度。或者，直方图可具有8个区间，每一区间覆盖360度范围的45度。应清楚，本文描述的直方图译码技术可适用于具有任一数目的区间的直方图。

图8是说明例如特征提取单元18等特征提取单元用以确定梯度分布和定向直方图的过程的图。此处，将二维梯度分布(dx，dy)(例如，块406)转换为一维分布(例如，直方图414)。关键点208位于围绕关键点208的片406(也称为单元或区)的中心。针对金字塔的每一级预计算的梯度展示为每一样本位置408处的小箭头。如图示，样本408的区形成子块410，也可称为区间410。特征提取单元18可采用高斯加权函数来对子块或区间410内的每一样本408指派权重。通过高斯加权函数指派给每一样本408的权重从区间410的质心209A、209B和关键点208(也是质心)平滑地下降。高斯加权函数的目的是避免窗的位置具有小改变的描述符的突然改变，以及对较远离描述符的中心的梯度给予较少的强调。特征提取单元18确定在直方图的每一区间中具有8个定向的定向直方图412的阵列，从而得到维度特征描述符。举例来说，定向直方图413可对应于子块410的梯度分布。

在一些实例中，特征提取单元18可使用其它类型的量化区间群集(例如，具有不同的Voronoi单元结构)以获得梯度分布。这些其它类型的区间群集可同样地采用一种形式的软区间化，其中软区间化指代重叠区间，例如当采用所谓的DAISY配置时界定的那些区间。在图8的实例中，界定三个软区间，然而，可使用多达9个或9个以上、其中质心通常以围绕关键点208的圆形配置来定位。也就是说，区间中心或质心208、209A、209B。

如本文使用，直方图是对落到称为区间的各种不相连类别中的观测、样本或出现(例如，梯度)的数目进行计数的映射ki。直方图的图表仅是表示直方图的一种方式。因此，如果k是观测、样本或出现的总数目且m是区间的总数目，则直方图中的频率ki满足表达为等式(30)的以下条件：

$>n=\underset{i=1}{\overset{m}{\Sigma }}{k}_i,---\left(30\right)$>

其中∑是求和算子。

特征提取单元18可通过以关键点的尺度的1.5倍的标准偏差由高斯加权函数界定的其梯度量值来对添加到直方图412的每一样本进行加权。所得定向直方图414中的峰对应于局部梯度的主要方向。特征提取单元18随后检测直方图中的最高峰，且随后检测在最高峰的某一百分比(例如80％)内的任何其它局部峰(其也可用来还产生具有所述定向的关键点)。因此，对于具有类似量值的多个峰的位置，特征提取单元18提取在相同位置和尺度下产生但定向不同的多个关键点。

特征提取单元18随后使用称为类型量化的一种形式的量化来量化直方图，所述类型量化将直方图表达为类型。以此方式，特征提取单元18可提取每一关键点的描述符，其中此描述符可以用类型的形式由高斯加权梯度的分布的位置(x，y)、定向和描述符来表征。以此方式，图像可由一个或一个以上关键点描述符(也称为图像描述符)表征。

图9A、9B是分别描绘特征描述符502A、502B以及根据本发明中描述的技术确定的重构点504到508的曲线图500A、500B。图9A和9B中的轴(表示为“p1”、“p2”和“p3”)指代特征描述符空间的参数，其界定上文论述的直方图的单元的概率。首先参见图9A的实例，特征描述符502A已划分为Voronoi单元512A到512F。在每一Voronoi单元的中心处，特征压缩单元20在基本量化等级54(图2的实例中所示)等于2时确定重构点504。特征压缩单元20随后根据本发明中描述的技术，根据上文描述的确定这些额外重构点的第一方式确定加强重构点504的额外重构点506(图9A的实例中由白/黑点表示)，使得当以额外重构点506更新重构点504时，所得特征描述符500A是以较高量化等级(即，在此实例中n＝4)重构。以此第一方式，额外重构点506确定为位于Voronoi单元512的每一面的中心处。

接着参见图9B的实例，特征描述符502B已划分为Voronoi单元512A到512F。在每一Voronoi单元的中心处，特征压缩单元20在基本量化等级54(图2的实例中所示)等于2时确定重构点504。特征压缩单元20随后根据本发明中描述的技术，根据上文描述的确定这些额外重构点的第二方式确定加强重构点504的额外重构点508(图9B的实例中由白/黑点表示)，使得当以额外重构点508更新重构点504时，所得特征描述符500A是以较高量化等级(即，在此实例中n＝4)重构。以此第二方式，额外重构点508确定为位于Voronoi单元512中的每一者的顶点处。

图10是说明关于系统的等待时间的时间图600，例如图1的实例中所示的系统10，其实施本发明中描述的技术。底部的线表示从用户起始搜索(由0表示)到特征描述符的肯定识别(在此实例中以1/6时间单位发生)的时间的经过。客户端装置12起初在提取特征描述符、以基本等级量化特征描述符以及发送特征描述符时引入一个单位的等待时间。然而，客户端装置12在此实例中不引入更多等待时间，因为其在网络16中继查询数据30A且视觉搜索服务器14执行相对于查询数据30A的视觉搜索的同时根据本发明的技术计算连续偏移向量以进一步精炼特征描述符。随后，仅网络16和视觉搜索网络14带来等待时间，但这些贡献是重叠的，因为在网络16递送偏移向量的同时，服务器14执行相对于查询数据30A的视觉搜索。随后，每一更新使得网络16和服务器14同时执行，使得等待时间与常规系统相比可大大减少，尤其是考虑到客户端装置12和服务器14的同时执行。

在一个或一个以上实例中，所描述的功能可以用硬件、软件、固件或其任一组合来实施。如果以软件实施，那么功能可作为一个或一个以上指令或代码存储在计算机可读媒体上或经由计算机可读媒体传输。计算机可读媒体可包含计算机数据存储媒体或包含促进计算机程序从一处传送到另一处的任何媒体的通信媒体。数据存储媒体可为可由一个或一个以上计算机或者一个或一个以上处理器存取以检索用于实施本发明中描述的技术的指令、代码和/或数据结构的任何可用媒体。举例来说且并非限制，此类计算机可读媒体可包括RAM、ROM、EEPROM、CD-ROM或其它光盘存储装置、磁盘存储装置或其它磁性存储装置、快闪存储器或可用来以指令或数据结构的形式载运或存储所要程序代码且可由计算机存取的任何其它媒体。而且，任何连接均适当地称为计算机可读媒体。举例来说，如果使用同轴电缆、光纤电缆、双绞线、数字订户线(DSL)或例如红外线、无线电和微波等无线技术从网站、服务器或其它远程源传输软件，那么同轴电缆、光纤电缆、双绞线、DSL或例如红外线、无线电和微波等无线技术包含在媒体的定义中。如本文中所使用，磁盘和光盘包含压缩光盘(CD)、激光光盘、光学光盘、数字多功能光盘(DVD)、软磁盘和蓝光光盘，其中磁盘通常以磁性方式再生数据，而光盘使用激光以光学方式再生数据。上文的组合也应包含在计算机可读媒体的范围内。

可由例如一个或一个以上数字信号处理器(DSP)、通用微处理器、专用集成电路(ASIC)、现场可编程逻辑阵列(FPGA)或其它等效集成或离散逻辑电路等一个或一个以上处理器来执行代码。因此，如本文中所使用的术语“处理器”可指上述结构或适合于实施本文中所描述的技术的任一其它结构中的任一者。另外，在一些方面中，本文描述的功能性可提供于经配置以用于编码和解码的专用硬件和/或软件模块内，或并入在组合式编解码器中。并且，可将所述技术完全实施于一个或一个以上电路或逻辑元件中。

本发明的技术可在广泛多种装置或设备中实施，包含无线手持机、集成电路(IC)或一组IC(例如，芯片组)。本发明中描述各种组件、模块或单元以强调经配置以执行所揭示技术的装置的功能方面，但不一定需要通过不同硬件单元来实现。而是，如上所述，各种单元可在编解码器硬件单元中组合或由互操作硬件单元(包含如上所述的一个或一个以上处理器)的集合结合存储到暂时性或非暂时性计算机可读媒体的合适软件和/或固件来提供。