用于视觉搜索的可扩展查询

摘要

本发明揭示了一种用于渐进式查询的系统和方法，其中所述渐进式查询为从通信网络的发送器发送到接收器的用于图像的视觉搜索的查询序列。可以顺次选择基于图像的特征点集合及其相关位置的查询。发送器将第一查询发送到接收器，其中所述第一查询包含某一数目个特征点，其为所述图像的在形成所述图像时具有旋转与尺度不变性的所述特征点集合的子集。所述发送器从所述接收器接收反馈，其中所述反馈由所述接收器基于使用来自所述第一查询的信息对图像存储库进行搜索而产生。然后，所述发送器基于所述所接收的反馈而决定所述图像存储库中是否存在所述图像的匹配。

说明书

相关申请案的交叉参考

本申请案主张2011年7月14日申请的标题为“用于视觉搜索的可扩展传输和验证方案的系统及方法（System and Method for ScalableTransmission and Verification Schemes for Visual Search）”的第61/507,972号美国临时申请案的在先申请优先权，该在先申请的内容以引用的方式并入本文本中。本申请案还主张2011年12月29日申请的标题为“用于视觉搜索的可扩展查询（Scalable Query for Visual Search）”的第13/340,089号美国申请案的在先申请优先权，该在先申请的内容以全文引入的方式并入本文本中。

技术领域

本发明大体上涉及图像处理；更确切地说，涉及视觉搜索中的具有应用程序的图像查询构造。

背景技术

现代的移动电话、手机、平板计算机、移动终端、移动装置或用户设备已发展为功能强大的图像和视频处理装置，该类图像和视频处理装置配备有高分辨率相机、彩色显示器，和硬件加速图形处理装置（hardware-accelerated graphics）。随着像android、iPhone一样的移动装置迅速发展，基于移动服务的多媒体视觉服务正经历着深刻的变革及开发。移动视觉搜索服务的应用场景可以是基于位置的服务、徽标搜索（logosearch）等等，其中从移动装置中发送的一个图像或多媒体与存储在数据库或图像存储库中的另一图像或多媒体相匹配。移动视觉搜索系统的第一推广应用包括谷歌的Goggles、诺基亚的Point and Find、Kooaba和Snaptell。

移动装置经由无线网络而发送的图像查询通常在计算上开销很大，需要相当高的通信成本，而且无法支持实时操作。在流行的应用程序中，其中移动装置捕获某些对象的图片，并经由无线网络将这一图片作为查询而发送以搜索较大的存储库，降低位速率同时保持匹配准确度是在MPEG下进行标准化努力所面临的主要问题和主要重点。

视觉描述符或图像描述符（而非图像）可以用作用于视觉搜索目的的查询。然而，对于移动装置，视觉描述符通常还是非常多，这是因为它们由成百上千个具有尺度与旋转不变性的特征点及其位置组成。尺度不变特征变换（SIFT）的一个实例特征点由具有2048位的128维组成。快速鲁棒特征（SURF）的另一实例特征点由具有1024位的64维组成。减小特征点的大小可能会有损视觉搜索服务中的搜索及匹配准确度的性能。

在另一方面，可以由移动装置发送图像的点集而非完整图像以对图像存储库进行搜索。点集可以在发送用于视觉搜索的图像特征点的同时发送，或者分开发送。因此可以在视觉搜索以及（外加）特征点搜索中使用点集来搜索并匹配图像。

如何借助于特征点和点集来降低位速率同时保持匹配准确度，仍然是个主要问题。

发明内容

通过本发明的实例实施例，当前搜索机制的上文所指出的不足与缺点得以克服。例如，本文本中所描述的实施例用于在视觉搜索应用程序中构建渐进式查询。应注意，本发明内容是为了以简化形式来介绍所选择的概念，对于这些概念，下文会在具体实施方式中进一步加以描述。此发明内容并不意图识别本发明的关键特征或基本特征，也并非意图用于协助确定本发明的范围。

随着互联网中视觉内容存储库的迅速发展，可以在无线链路上支持捕获内容查询（query-by-capture）的系统在许多视觉搜索应用程序中有很大吸引力。在本发明中，呈现了用于在视觉搜索应用程序中构建渐进式查询的系统、设备、计算机程序产品及方法。渐进式查询是一个图像的查询序列，它从通信网络的发送器发送到接收器。图像的渐进式查询可以基于图像的特征点集合及其相关位置的表示而构建。每一查询经由网络单独传送，并与图像存储库匹配。不需要完全发送完整的特征点集合，由序列中的第一查询或某一查询找到图像的匹配内容是可能的。

根据一项实例实施例，提供了一种用于由网络的发送器处理图像的方法。所述发送器可以是无线网络的用户设备（UE）或基站（eNB）。所述发送器可以将所述图像的第一查询发送到接收器，其中所述第一查询包含第一数目个特征点，其为所述图像的在形成所述图像时具有旋转与尺度不变性的第一特征点集合的子集。所述发送器可以从所述接收器接收反馈，其中所述反馈由所述接收器基于使用来自所述第一查询的信息对图像存储库进行搜索而产生。然后，所述发送器基于所述所接收的反馈而决定所述图像存储库中是否存在所述图像的匹配。当所述发送器基于所述第一查询而决定所述图像存储库中不存在所述图像的匹配时，所述发送器可以将所述图像的第二查询发送到所述接收器，其中所述第二查询包含第二数目个特征点，其为所述图像的在形成所述图像时具有旋转与尺度不变性的所述第一特征点集合的子集。所述第一查询与第二查询可以不相交，不存在任何共同特征点。

根据另一项实例实施例，提供一种用于由网络的发送器处理图像的方法。所述发送器可以将所述图像的第一查询发送到接收器，其中所述第一查询包含第一数目个特征点，其为所述图像的在形成所述图像时具有旋转与尺度不变性的第一特征点集合的子集。所述第一特征点集合可以为所述图像的尺度不变特征变换（SIFT）特征点，或者为所述图像的快速鲁棒特征（SURF）特征点。所述第一查询可以由通过维数缩减方法、散列/量化方法或自适应量化方法而被压缩的特征点组成。所述第一查询可以从位于所述图像进行空间分割之后所得的所述图像的子区域中的特征点中随机选择。所述第一查询也可以基于位于所述图像进行空间分割之后所得的所述图像的子区域中的特征点的拉普拉斯值而选择。所述图像的所述空间分割可以位于所述第一特征点集合的相关位置点的重心为中心，并且按照与所述图像的四叉树分割相同的方式执行所述空间分割。

根据一项实例实施例，提供一种用于由网络的发送器处理图像的方法。所述发送器可以将所述图像的第一查询发送到接收器，并且从所述接收器接收反馈。所述反馈可以是第一数目个位的矢量，在所述第一数目个位中存在第二数目个位经设置以指示经匹配的特征点，其中所述第一查询包含第一数目个特征点，所述接收器在所述第一数目个特征点中找到来自所述图像存储库的第二数目个经匹配的特征点。所述发送器可以在所述第二数目与所述第一数目的比值大于阈值时决定所述图像存储库中存在所述图像的匹配，其中所述阈值为基于有关所述图像存储库的信息而产生。

根据一项实例实施例，提供一种用于由网络的发送器处理图像的方法。所述发送器可以将所述图像的第一查询发送到接收器，并且从所述接收器接收反馈。所述发送器可以接收第一反馈，所述第一反馈是第一数目个位的矢量，在所述第一数目个位中存在第二数目个位经设置以指示经匹配的特征点，其中所述第一查询包含第一数目个特征点，所述接收器在所述第一数目个特征点中找到来自所述图像存储库的第二数目个经匹配的特征点。所述发送器可以接收第二反馈，其为与所述第二数目个经匹配的特征点相关联的点集有关的拓扑信息。例如，所述第二反馈可以是拓扑编码矢量，其为与所述第二数目个经匹配的特征点相关联的所述点集的图谱。然后，所述发送器可以在所述第二数目与所述第一数目的比值大于阈值时决定所述图像存储库中存在所述图像的匹配，其中所述阈值为基于有关所述图像存储库的信息而产生，并且所述第二反馈中的所接收的所述拓扑编码矢量与所述发送器产生的拓扑编码矢量匹配，其中所述发送器产生的拓扑编码矢量来自所述经匹配的第二数目个特征点的相关定位。

根据一项实例实施例，提供一种用于由网络的接收器处理图像的方法。所述接收器从发送器接收所述图像的第一查询，其中所述第一查询包含第一数目个特征点，其为所述图像的在形成所述图像时具有旋转与尺度不变性的第一特征点集合的子集。所述接收器可以向所述发送器发送第一反馈，其中所述反馈由所述接收器基于使用来自所述第一查询的信息对图像存储库进行搜索而产生。所述第一反馈可以是第一数目个位的矢量，在所述第一数目个位中存在第二数目个位经设置以指示经匹配的特征点，其中所述第一查询包含第一数目个特征点，所述接收器在所述第一数目个特征点中找到来自所述图像存储器的第二数目个经匹配的特征点。所述接收器也可以将第二反馈发送到所述发送器，其为与所述第二数目个经匹配的特征点相关联的点集有关的拓扑信息。

根据一项实例实施例，揭示了一种用于处理图像的设备。所述设备可包含：传输单元，所述传输单元用于发送所述图像的第一查询，其中所述第一查询包含第一数目个特征点，其为所述图像的在形成所述图像时具有旋转与尺度不变性的第一特征点集合的子集；接收单元，所述接收单元用于接收反馈，其中所述反馈为基于使用来自所述第一查询的信息对图像存储库进行搜索而产生；以及决策单元，所述决策单元用于基于所述所接收的反馈而决定所述图像存储库中是否存在所述图像的匹配。所述设备可以进一步包含：查询选择单元，所述查询选择单元用于从所述图像的所述第一特征点集合中选择所述第一查询，其中对位于所述图像进行空间分割之后所得的图像子区域中的特征点随机执行所述选择，或是基于特征点的拉普拉斯值而执行所述选择。所述决策单元用于在第二数目与所述第一数目的比值大于阈值时决定所述图像存储库中存在所述图像的匹配，其中所述第一查询的所述第一数目个特征点中存在来自所述图像存储器的所述第二数目个经匹配特征点，且所述阈值为基于有关所述图像存储库的信息而产生。

以下说明将阐明本发明的额外特征和优点，并且这些特征和优点的一部分将在说明中显而易见，或者通过实践本发明能够推导出。本发明的特征和优点可以通过所附权利要求书中特别指出的仪器和组合来实现和获得。结合以下说明和所附权利要求书，本发明的这些和其他特征将变得更加显而易见，或者可以通过如下文所述实践本发明而习得。

附图说明

为了描述可以获得本发明的上述和其他有利特征的方式，参考附图中示出的本发明的具体实施例，将呈现出对上文简要描述的本发明的更具体说明。应理解，这些附图仅描绘了本发明的典型实施例，因此不应视为限制本发明的范围。为了更完整地理解本发明及其优点，现在参考下文结合附图进行的描述，其中：

图1（a）和图1（b）图示了根据本文本中所描述的实例实施例的具有移动装置的内容分布网络和视觉搜索系统的实例；

图2图示了根据本文本中所描述的实例实施例为通过点集和特征点集合来表示图像而对图像执行的实例操作序列，其中所述点集和特征点集合用以执行视觉搜索；

图3图示了根据本文本中所描述的实例实施例的使用特征点集合和点集来构建用于视觉搜索的由多个查询组成的一个序列的实例过程；

图4（a）和图4（b）图示了根据本文本中所描述的实例实施例的用于匹配由查询序列表示的两个图像的实例协议；

图5图示了根据本文本中所描述的实例实施例的用于使用由多个查询组成的一个序列来进行视觉搜索的实例设备；以及

图6图示了根据本文本中所描述的实例实施例的一种方法的实例实施方案。

具体实施方式

下文详细论述当前优选实施例的制作和使用。然而，应了解，本发明提供可以在各种具体上下文中体现的许多适用发明性概念。所论述的具体实施例仅仅说明用以制作和使用本发明的具体方式，而不限制本发明的范围。

如下文中将全面解释的，揭示了用于构建渐进式查询的系统、设备、计算机程序产品及方法的实施例，所述渐进式查询可以是一个图像的用于视觉搜索的查询序列，并且它从通信网络的发送器发送到接收器。可以顺次发送基于特征点集合及其相关定位的表示的查询序列，而不是发送整个图像、完整的特征点集合或其相关位置来作为用于视觉搜索应用程序的一个查询。每一查询可以经由网络单独传送，并与图像存储库匹配。不需要完全发送完整的特征点集合，由序列中的第一查询或某一查询找到图像匹配是可能的。

图1（a）图示了视觉搜索系统的实例实施例，其中移动装置或用户设备（UE）UE1101或UE2103经由基站105和内容分布网络（CDN）107发送多媒体查询111或113。术语移动电话、手机、平板计算机、移动终端、移动装置或用户设备能以互换方式使用。查询111、113由服务器129内的接收器121接收为查询117，其中该查询117由搜索单元119用以对图像存储库109进行搜索。UE1101、UE2103或基站eNB105可以统称为客户端，并且包含接收器121、搜索单元119及图像存储库109的服务器129可以统称为服务器129。

视觉搜索系统可以是基于位置的服务、徽标搜索等等。UE101和103可以经由无线通信信道连接到基站eNB105。UE101和103可以是移动电话、用户终端、移动台、iPHONE或任何其他类似装置。可以存在连接到基站eNB105的不同数目的UE。UE101或103可以将多个查询发送到基站。

UE101、103、基站105和CDN107可以是长期演进（LTE）无线系统、长期演进高级（LTE-A）系统、IEEE802.16m系统，或任一其他种类的无线系统的一部分。图1（a）中所图示的视觉搜索系统可以按照其他形式实施，或可以表示在根据一项实例实施例的图1（b）中所图示的抽象层（abstract level）中，其中UE1101连接到包括图像存储库109的服务器129，并且UE1101发送由接收器121接收的查询111，该查询作为查询117而由服务器129接收，用于在服务器129内对图像存储库109进行搜索。

查询111或113从UE101或103发送到基站105。基站105可以将查询111或113作为查询115而直接传送到服务器，该查询从而由服务器接收为查询117。基站105可以对查询111或113执行某些操作以产生另外的查询115，然后经由CDN107发送查询115，该查询从而由服务器接收为经接收的查询117。

如果从UE101中发送的查询111以及经接收的查询117是一个图像，那么图像查询可以用以搜索存储在数据库或图像存储库109中的图像并与之匹配。通常使用特殊的索引结构来实现这一目的。基于图像的查询通常在计算上开销很大，需要额外的相当高的通信成本，并且无法支持CDN应用程序所需的实时操作。

查询111或查询117可以是视觉描述符。视觉描述符或图像描述符是对图像、视频或产生此类描述的组件或模块中的内容的视觉特征点的描述。这些描述符可以描述例如形状、颜色、纹理或动作的基本特性，以及其他基本特性，并且这些描述符实现了音频-视频内容的快速且有效率的搜索。高鉴别性的描述符包括快速鲁棒特征（SURF）和尺度不变特征变换（SIFT），这些是鲁棒图像（robust image）检测符和描述符。在视觉搜索应用程序中，查询图像的描述符与数据库图像的描述符之间的匹配能力对于成功匹配来说很关键。

视觉描述符可以将视觉对象及兴趣点表示为一个特征点集合，该特征点集合可以具有尺度与旋转不变性或任何其他性质。当视觉描述符用以匹配图像时，经接收的查询117可以是从图像中提取的特征点集合。对于这些特征点及其拓扑信息的收集，例如特征点集合{F_k|k=1,…,n}，其中每一特征点F_k位于图像定位{x_k,y_k}处，提供了在尺度、旋转及某程度视角变化上不变的某些对象的唯一表示。特征点可以表示为F_k，或F_j，或一些其他的类似变量。该集合可以由数百个（例如242个）特征点组成。匹配两个图像等于匹配图像中的两个特征点集合，并且经匹配的特征的数目用作用于匹配的指示符。

特征点F_j为中的点，其中n_j为特征点F_j的维数，并且特征点F_j的特征维数具有由p_i个位表示的p_i位精度。这可以被称为特征点在维数i下的分辨率。对于特征点集合，该集合中的特征点的维数可以相同也可以不同。

然而，对于移动装置，视觉描述符通常还是非常多，这是因为它们由数百个具有尺度与旋转不变性的特征点及其位置组成。尺度不变特征变换（SIFT）的一个实例特征点由具有2048位的128维组成。快速鲁棒特征（SURF）的另一实例特征点由具有1024位的64维组成。减小特征点的大小可能会有损视觉搜索服务中的搜索及匹配准确度的性能。

查询111或查询117可以是由移动装置发送以对图像存储库进行搜索的图像的点集（而不是整个图像）或视觉描述符。点集可以在发送用于视觉搜索的图像特定点的同时发送，或分开发送。因此点集可以用于在视觉搜索以及（外加）特征点搜索中搜索并匹配图像。点集可以用以独立地在视觉搜索中搜索且匹配图像，而不是连同特征点一起使用。

图2图示了用于使用特征点集合或点集来表示用于视觉搜索的图像的操作流程的实例实施例。图2中所图示的操作可以由移动装置、基站和服务器，或由这些组件的组合，或由网络中的任何其他组件执行。

在步骤201提供图像。在步骤2031，可以使用由移动终端或基站执行的可重复特征提取器来从该图像中提取特征点集合。当对例如SURF和SIFT特征点的具有尺度与旋转不变性的特征点进行收集所得的集合用作视觉描述符时，通过跨越多个尺度的边缘检测而在视觉对象中找到这些特征点。作为一项实例实施例，仅仅将具有在尺度上一致的强边缘信息的那些点选择为特征点。旋转不变性是由描述边缘定向的描述符来实现。特征点集合可以由数百个具有尺度与旋转不变性的特征点组成。特征点集合在图像中的位置被称为该特征点集合的相关位置。位置可以是该特征点集合中的一个特征点的相关定位。也可以提取其他视觉描述符特征点来代替SURF或SIFT。SURF和SIFT的使用仅仅是出于说明的目的，并非是限制性的。

在步骤205，表示特征点，例如，以不同的方式表示例如SURF和SIFT特征点的各种特征点。例如，SURF的每个特征点为由2048位形成的128维。另一方面，SIFT的特征点具有由1024位形成的64维。由于通常的索引方案在使用高维数时会出现故障，因而特征点的高维数会使得大尺度视觉对象和兴趣点存储库搜索无效。

因此，可能需要对特征点进行压缩，以降低位速率。作为一项实例实施例，在步骤207，执行特征点压缩操作，该特征点压缩操作缩减表示的大小。该压缩操作可以由特征点压缩单元执行。特征点压缩单元可以位于终端上，或位于基站上。经压缩的特征点被传输到服务器端，该服务器端将会处理搜索并把结果发回到移动终端。

在步骤207中可以存在用以缩减特征点大小的不同方法，例如由单元2071执行的维数缩减、由单元2072执行的散列/量化，或由单元2073执行的自适应量化。可以将这些不同的方法组合，从而对同一特征点集合执行该经组合的方法，以实现进一步缩减。

维数缩减方法使用维数缩减途径，在保留某些信息的同时缩减特征点维数。散列方法尝试为每个特征点使用一个索引。在某些条件下，输入特征点被映射在分辨率较小的某个存储桶（bucket）中。存储桶中所有的点都被视为匹配。位置敏感散列（locality sensitive hashing）、谱散列（spectralhashing）及矢量量化（vector quantization）属于这一类别。自适应量化进一步将每个特征点映射到不同的分辨率。例如，特征点具有针对第一维数的第一精度以及针对第二维数的第二精度。该自适应量化可以基于某一标准而进行，例如特征点方差。在一些实施例中，特征点具有针对第一维数的第一精度和针对第二维数的第二精度，其中针对特征点方差较大的第一维数的第一精度大于针对特征点方差较小的第二维数的第二精度。

在步骤219，使用经压缩的特征点来对图像存储库进行搜索和匹配，以便找到由特征点表示的图像的正确匹配。该操作可以由服务器或一些其他网络组件执行。

除了使用特征点来进行视觉搜索之外，也可以将其他点集用于视觉搜索。根据另一项实施例，如图2中所示，在步骤201提供图像。在步骤2032，可以从图像中提取点集。作为一个实例，可以提取与例如SURF和SIFT的特征点集合有关的点集，由移动装置或基站来执行。特征点集合可以由数百个具有尺寸与旋转不变性的特征点，以及这些特征点在原始图像中的位置组成。特征点集合在原始图像中的位置可以是步骤2032中所产生的点集。也可以提取其他视觉描述符特征点来代替SURF或SIFT。SURF和SIFT的使用仅仅是出于说明的目的，并非是限制性的。也可以在步骤2032中使用图像的其他点集来代替SURF和SIFT特征点的位置。

在步骤209，产生点集的拓扑编码矢量，例如，可以使用拓扑编码单元来产生步骤203中所产生的点集的拓扑编码矢量。图像的拓扑编码矢量在形成图像时具有旋转与尺度不变性，并且是基于点集的拓扑信息而产生。作为一项实例实施例，拓扑编码矢量可以是产生自图像点集的成对位置距离矩阵的图谱（graph spectrum）。例如，拓扑编码矢量可以计算为拉普拉斯矩阵L=S–W的本征值，其中W为通过而定义的关联矩阵（affinity matrix），||X_j-X_k||为图像点集的第一点X_j与第二点X_k之间的距离。

在步骤211，对点集的拓扑编码矢量进行压缩以产生经压缩矢量，例如，压缩可以由压缩单元使用压缩方法而执行，其中该压缩方法压缩点集的拓扑编码矢量以产生经压缩矢量。作为一个实例，该压缩方法可以是离散余弦变换（DCT）。也可以使用其他压缩方法。可以顺次使用多个压缩方法来压缩点集的拓扑编码矢量。

在步骤213，点集的经压缩的拓扑编码矢量可以用以搜索经匹配的图像。服务器或一些其他网络组件可以提取点集的拓扑编码矢量，并将其与另一图像的另一点集的另一拓扑编码矢量匹配，并且在这些拓扑编码矢量满足某些性质时确定两个图像相匹配。

图2中所图示的操作仅仅出于说明的目的，且并非是限制性的。根据一项实施例，所执行的操作可以遵循所图示的序列，或者也可以遵循不同序列。例如，在发送点集的拓扑编码矢量时可以不使用压缩单元211。作为另一项实例实施例，步骤207可以执行从2071维数缩减、2072散列/量化或2073自适应量化中选择的一或多个操作。可以同时进行步骤2032中的点集提取，以及步骤2031中的特征点集合提取，并且2032中的点集是步骤2031中的表示特征点位置的特征点集合的相关点集。图像可以通过特征点集合、点集或两者的组合的各种形式进行表示。

图3图示了用于构建用于图像视觉搜索的渐进式查询的操作流程的实施例，其中该渐进式查询为查询的序列。将图像的全部特征点作为查询而经由网络发送对于很多视觉搜索应用程序来说可能并非必要的。例如，大小为1024*768的图像可以具有多达1500个特征。这些特征点中只有一些特征点对于成功图像检索来说是有用的。可以顺次发送基于特征点集合及其相关位置的表示的查询序列，而不是发送整个图像、完整的特征点集合或其相关位置来作为一个查询。每一查询经由网络单独传送，并与存储在服务器中的图像存储库匹配。不需要完全发送完整的特征点集合，由序列中的第一查询或某一查询找到图像匹配是可能的。以下图示了操作的更多细节。

在步骤301提供图像。可以由移动装置捕获图像，并且将其发送到eNB或服务器。在步骤303，图像可以由例如Q₀={F_k|k=1,…,n}的特征点集合及点集{x_k,y_k}使用图2中所图示的技术进行表示。使用图2中所图示的各种技术，特征点和一些种类的经压缩特征点两者在步骤303均可用是可能的。可以存在某个功能单元，以从在步骤303可用的特征点中产生经压缩的特征点。一个特征点可以意味着一个经压缩的特征点。

在步骤303处可用的点集可以是作为特征点位置的特征点集合Q₀={F_k|k=1,…,n}的相关点集{x_k,y_k}。基于特征点集合及其相关点集，移动装置或基站构建一个查询序列，以搜索且匹配可以存储在服务器中的图像存储库中的图像。

作为一项实例实施例，步骤305到步骤313中图示为Q₁到Q_m+1的查询为渐进式查询，其中每一查询包含来自步骤303中所图示的特征点集合Q₀={F_k|k=1,…,n}中的一些特征点，这些特征点划分为子集序列Q₁到Q_m+1。对于一些实施例，子集可以彼此之间不相交例如，点集划分以及特征点的子集划分可以通过点集的分级四叉树分割而实现。对于一些其他实施例，这些子集可以具有非空交集为了以渐进方式执行图像的视觉搜索，在迭代i中发送包含n_i个特征点的Q_i的子集，以对图像存储库进行搜索。当没有找到匹配时，在迭代i+1中发送包含n_i+1个特征点的下一迭代Q_i+1。

可以示出两种不同方式来从原始特征点集合Q₀中选择特征点集合Q_i。第一种方式可以是在空间分割之后随机选择一些特征点。对于所有特征点，找到特征点的所有相关位置点的重心（centroid）。接着，将以相关位置点重心为中心的整个图像区域以与四叉树分割相同的方式分割为四个区域。在每个子区域中，随机地选择位置点，并且针对特征点集合Q_i挑选所选择的位置点的特征点。

第二种方式可以基于拉普拉斯值选择特征点。对于所有特征点，找到特征点的所有相关位置点的重心。接着，将以相关位置点重心为中心的整个图像区域以与四叉树分割相同的方式分割为四个区域。在每个子区域中，特征点(x,y)的拉普拉斯值D(x,y,σ)计算如下：D(x,y,σ)=L(x,y,kσ)–L(x,y,σ)，其中L(x,y,kσ)为原始图像I(x,y)的卷积，其中高斯模糊G(x,y,kσ)处于尺度kσ(k>1)下，即，L(x,y,kσ)=G(x,y,kσ)*I(x,y)。因此D(x,y,σ)表示特征点的二阶导数。D(x,y,σ)的值越大，特征点的鲁棒性越强。因此，可以在特征点具有更大的拉普拉斯值时选择若干特征点。

根据一项实施例，可以在图像处理的空间分割的同时构建所有查询Q_i。如果同时构建了这些查询，那么将其存储在存储器中以供稍后检索。查询Q_i可以在需要时产生，一次构建一个。

图4（a）和图4（b）图示用于发送用于图像视觉搜索的渐进式查询序列的协议的实例实施例。在图4（a）和图4（b）中，发送器向接收器发送查询序列。该发送器可以是UE或基站。该接收器可以是基站或服务器。发送器或接收器也可以是执行视觉搜索以将一个图像与存储在图像存储库中的另一图像匹配的其他网络组件，其中该图像存储库可由接收器访问以执行搜索。此外，根据一项实施例，图4（a）和图4（b）中所图示的思想可以不用于网路中的设置，而是用在单个计算机或任何其他计算装置内的设置中，其中发送器和接收器可以由计算机或任何其他计算装置内的不同软件或硬件组件实施。

如图4（a）中所示，在i时刻，在步骤401，发送器可以发送包含一个特征点子集的查询Q_i。查询Q_i可以如图3中所示进行构建。作为一项实例实施例，可以在发送第一查询之前同时一起构建所有的Q_i。发送器也可以在图3中所示的操作流程之后视需要一次构建一个Q_i。

当接收器接收到查询Q_i时，在步骤403，接收器在图像存储库中搜索存储于图像存储库中的或产生自存储于存储库中的图像的经匹配特征点的集合。例如，Q_i可以包含n_i个特征点，且作为一个实例，接收器能够对n_i个特征点中的m_i个特征点进行匹配。图像存储库可以存储很多用以匹配所搜索的图像的图像。存储于图像存储库中的图像可以按照完整图像的形式而存储。图像存储器可以存储额外的特征点以及图像本身，或与图像本身分开存储。可以事先存储特征点，或在执行搜索时产生这些特征点。

接收器在步骤405发送回反馈信息以指示搜索结果。根据一项实施例，反馈信息可以是指示在图像存储库中所找到的经匹配特征点的数目的矢量。例如，反馈信息可以是n_i个位的矢量，其中m_i个位被设置为1来指示匹配。反馈信息可以是n_i个位的矢量，其中m_i个位被设置为0来指示经匹配特征点的数目。可以由发送器或接收器议定使用位1还是位0来指示匹配。

当发送器接收反馈信息时，在步骤407，该发送器例如基于经匹配特征点的数目来决定在图像存储库中是否找到图像的匹配。在一项实施例中，发送器可以只计算m_i/n_i的比值，并且将该比值与阈值进行比较，从而决定是否表明图像的匹配。用于决定此类匹配的阈值可以事先产生自图像存储库。例如，如果比值m_i/n_i大于阈值，那么发送器可以表明所搜索的图像匹配，并且停止发送任何进一步的查询。

如果发送器在步骤407决定尚不存在所搜索的图像的匹配，那么发送器可以在下一步骤409发送下一查询Q_i+1。接收器接收查询Q_i+1，并且遵循已图示的相同模式。此过程可以继续，直至发送完所有查询或者找到匹配为止。

在步骤405，接收器可以发送不同于图4（a）中所图示的反馈信息的一条反馈信息。根据一项实施例，在图4（b）中，反馈4051为图4（a）中所图示的反馈，这一反馈例如可以是n_i个位的矢量，其中m_i个位被设置为1以指示匹配。根据另一项实施例，接收器可以发送额外的反馈信息4052，这一反馈信息例如可以是401查询的相关查询。相关查询4052可以与该查询的经匹配特征点的相关点集有关。相关查询可以是m_i个经匹配特征点的点集的拓扑编码矢量，或是点集自身，或是其他拓扑信息。图2的步骤209中图示了产生此类拓扑编码矢量的操作。图像的拓扑编码矢量在形成图像时具有旋转与尺度不变性，并且例如是基于点集的拓扑信息而产生。拓扑编码矢量可以是产生自与经匹配特征点相关联的点集的成对位置距离矩阵的图谱。

如图4（b）中所示，当发送器接收反馈信息时，在步骤407，该发送器例如基于经匹配特征点的数目来决定是否找到图像的匹配。发送器可以首先计算m_i/n_i的比值，并且将该比值与阈值进行比较，从而决定是否表明图像的匹配。用于决定此类匹配的阈值可以事先产生自图像存储库。如果比值m_i/n_i小于阈值，那么发送器可以表明所搜索的图像无匹配，并发送另一个查询。例如，如果比值m_i/n_i大于阈值，那么发送器可以将所接收的拓扑编码矢量（其作为相关查询而被接收）与将产生自m_i个特征点的相关位置的一个拓扑编码矢量进行比较。如果这两个拓扑编码矢量的距离小于第二阈值，那么它们可以匹配。用于决定此类匹配的第二阈值可以事先产生自图像存储库。所添加的作为相关查询而接收的拓扑编码矢量的匹配可以提高匹配准确度。一般来说，发送器可以使用从接收器接收的相关查询，以在发送器侧验证某些额外的图像性质，从而提高匹配准确度。

继续参看图4（b），如果发送器在步骤407决定尚不存在所搜索的图像的匹配，那么发送器可以在下一步骤409发送下一查询Q_i+1。接收器接收查询Q_i+1，并且遵循已图示的相同模式。此过程可以继续，直至发送完所有查询或者在找到匹配为止。

图4（a）和图4（b）中所示的协议仅仅是出于说明的目的，且并非是限制性的。可以发送其他形式的查询，并且可以执行不同的匹配。例如，发送器可以除拓扑编码矢量之外再发送401查询Q_i，并且，可以使用特征点集合Q_i与拓扑编码矢量两者来执行搜索403，以提高匹配准确度。

其他形式的反馈可以由接收器发送到发送器。例如，接收器可以做出不同于或代替图4（a）和图4（b）中所示的决策的决策。例如，可以由接收器（其可以是服务器）决定已经使用查询找到了经匹配的图像，而不是由发送器、移动终端或基站决定。如果服务器决定图像存储库中是否存在所搜索的图像的匹配，并将反馈结果发送回发送器，那么发送器可以仅仅将服务器的决策反馈接受为其自己的决策。

可以由发送器在从接收器接收反馈时形成其他形式的决策。例如，如果服务器决定图像存储库中是否存在所搜索的图像的匹配，并将反馈结果发送回发送器，那么发送器可以仍决定该匹配，这将仅仅是检查来自接收器的反馈结果。

图5图示使用渐进式查询来执行视觉搜索的一个实施例设备500。设备可以包含传输单元501、接收单元503、决策单元505、匹配单元507、存储单元509以及查询选择单元511。

对于所图示的实施例，传输单元501用于发送图像的查询，其中该查询包含第一数目个特征点，其为图像的在形成图像时具有旋转与尺度不变性的第一特征点集合的子集。图像的第一特征点集合可以存储在存储单元509中。根据一项实例实施例，查询可以由查询选择单元511基于已发送的查询的迭代数目来选择，例如，其中对位于图像进行空间分割之后所得的图像子区域中的特征点随机执行该选择，或是基于特征点的拉普拉斯值而执行该选择。

接收单元503用于接收反馈，其中该反馈为基于使用来自查询的信息对图像存储库进行搜索而产生。该反馈可以由服务器或某个其他网络组件或其他搜索组件发送。决策单元505用于基于所接收的反馈而决定图像存储库中是否存在图像的匹配。如果该反馈含有一些额外的相关查询，那么匹配单元507可以基于所接收的相关查询而执行匹配验证。当所接收的相关查询为拓扑编码矢量时，匹配单元507可以将所接收的拓扑编码矢量与将产生自特征点的相关位置的拓扑编码矢量进行匹配。如果这两个拓扑编码矢量的距离小于第二阈值，那么它们可以匹配。用于决定此类匹配的第二阈值可以事先产生自图像存储库。所添加的作为相关查询而接收的拓扑编码矢量的匹配可以提高匹配准确度。一般来说，发送器可以使用从接收器接收的相关查询，来在发送器侧验证某些额外的图像性质，从而提高匹配准确度。

作为一项实例实施例，基于所接收的反馈，决策单元505可以例如在第二数目与第一数目的比值大于阈值时决定图像存储库中存在图像的匹配，其中查询的第一数目个特征点中存在来自图像存储器的第二数目个经匹配特征点，且该阈值为基于有关图像存储库的信息而产生。

经由前述实施例的描述，本发明可以仅仅使用硬件来实施，或者可以使用软件和必要的通用硬件平台来实施。图6图示根据本发明的一项实施例的单元或控制器600的一个实例。单元600可以结合本发明而使用，并且可以执行本发明中所描述的功能。在同一实施例或替代实施例中，控制器600可以存在于一或多个UE、eNB、服务器或任何其他网络装置或组件中，成为其组件，或是可以由其使用。

单元600可以含有处理器602，其通过执行定义控制器600的总体操作的计算机程序指令来控制此类操作。处理器602可以包括一或多个中央处理单元，只读存储器（ROM）装置和/或随机存取存储器（RAM）装置。处理器602可以是ASIC、通用处理器、数字信号处理器、处理器的组合、具有专用电路的处理器、用作处理器的专用电路，以及以上装置的组合。

计算机程序指令可以存储在存储装置604（例如，磁盘、数据库等）中，并且在需要执行计算机程序指令时载入存储器606中。因此，用于执行本文本中所述的例如预编码、调度、传输和接收数据的方法步骤的应用程序可以由存储在存储器606或存储装置604中的计算机程序指令定义，并且由执行这些计算机程序指令的处理器602控制。

在替代实施例中，硬接线电路或集成电路可以用来代替用于实施本发明的过程的软件指令，或与所述软件指令结合使用。因此，本发明的实施例并不限制于硬件、固件或软件的任何特定组合。存储器606可以存储用于控制器600的软件，该软件可以用于执行软件程序，且由此根据本发明，具体来说根据上文详细描述的方法操作。然而，如本文本中所描述的本发明可以使用各种编程技术以及通用硬件子系统或专用控制器按照很多不同方式来实施。

单元600还可以包括用于经由网络而与其他装置通信的一或多个网络接口608。在网络的无线部分中，网络接口可以包括天线及相关处理。在网络的有线部分，网络接口可以包括其与将该单元连接到其他单元的缆线的连接。在每一情况中，网络接口可以被视为用于接入物理通信部分（例如天线）的电路。

单元600也可以包括实现用户与控制器600的互动的输入/输出装置610（例如，显示器、键盘、鼠标、扬声器、按钮等）。这些用户I/O装置是可选的，且如果单元600仅仅由网络接口接入，那么将不需要这一装置。

单元600的实施方案也可以含有其他组件，且出于说明性目的，图6的控制器为此类控制器的一些组件的高层次表示。

本发明的实施例提供了若干新的有利特征。例如，一项实施例提供一种新的视觉特征描述压缩方案，该方案在非常低的位速率下获得非常高的准确度。另一项实施例提供一种位速率和准确度可扩展的压缩方案。本发明的实施例可以用于多种产品、过程和服务中。这些实施方案的一些实例包括基于云的媒体处理、下一代CDN产品、CDN方法及操作。实施例是可取的，因为它们可以在客户端提供实时的、低计算/通信成本的体验质量（QoE）估计。例如，可以获得具有较轻重量的视频签名（video signature）且在计算和通信资源中成本最小的鲁棒性QoE估计器。这在CDN和无线多媒体市场中将会是有用的。

尽管详细描述了各项实施例及其优势，但应理解，可以在不脱离由所附权利要求书界定的本实施例的精神和范围的前提下，对本文做出各种改变、替代和更改。举例来说，上文所论述的许多特征和功能可以用软件、硬件、固件或其组合来实施。

此外，本申请案的范围不意图限于本说明书中所描述的过程、机器、制造、物质成分、构件、方法和步骤的特定实施例。所属领域的一般技术人员容易从本发明的揭示内容中了解到，可以根据本发明利用执行与本文本中所描述的对应实施例大致相同的功能或实现与本文本中所描述的对应实施例大致相同的结果的目前存在或稍后将开发的过程、机器、制造、物质成分、构件、方法或步骤。因此，所附权利要求书意图在其范围内包括此类过程、机器、制造、物质成分、构件、方法或步骤。