CN104067272A - 用于图像处理的方法和装置 - Google Patents

Abstract

本发明涉及一种方法，其中接收与图像的兴趣点有关的一个或者多个局部描述符。基于一个或者多个局部描述符来确定用于所述图像的全局描述符；并且压缩全局描述符。本公开内容也涉及一种包括处理器和包括计算机程序代码的存储器的装置以及存储介质，该存储介质具有在其上存储的用于由装置使用的计算机可执行程序代码。

Description

用于图像处理的方法和装置

技术领域

提供一种用于内容识别和取回的方法、装置和计算机程序产品。

背景技术

本节旨在提供在权利要求中记载的本发明的背景或者情境。这里的描述可以包括如下概念，这些概念可以被探求、但是未必是先前已经设想或者探求的概念。因此，除非这里另有指示，在本节中描述的内容不是在本申请中的说明书和权利要求书之前的现有技术并且未因包含于本节中而被承认为现有技术。

图像内容识别和从数据库取回图像内容可以在许多情形中是希望的性质。例如移动设备可以用来拍摄产品、对象、建筑物等的图片，然后可以确定图像的内容。可能的是，可以从数据库搜索具有相似内容的图片。为此，执行一些内容识别。

这也可以适用于其它设备、比如机顶盒和其它计算设备。

对于图像中的任何对象，可以有许多特征、在对象上的兴趣点。可以提取这些兴趣点以提供对象的特征描述，可以在尝试在可能包含许多其它对象的图像中对该对象进行定位时使用该对象的特征描述。对于图像特征生成，一些方式取得图像并且将它变换成局部特征矢量的大型汇集。这些特征矢量中的每个特征矢量可以随着图像的缩放、旋转或者平移而不变。

在包括手持产品识别、博物馆向导、行人导航、机顶盒视频内容检测、web规模图像搜索和增强现实的广泛应用中使用图像内容描述。许多这样的应用受它们的平台的计算能力约束。即使在无约束情况、比如web规模图像搜索中，处理数以百万计的图像可能导致计算瓶颈。因此，具有低计算复杂性的算法总是希望的。增强现实应用还可能由于在相机姿态跟踪与图像内容识别之间共享移动设备的资源而受约束。这两项任务可以总是相互去耦合。对于实时跟踪足够快的技术可能在从大规模数据库识别时未表现良好。反言之，在识别时表现良好的算法可能对于在移动设备上的实时跟踪而言不足够快。

除了兼容性之外，用于可视搜索算法的紧凑描述符应当是小的并且在硬件或者软件中计算高效。更小的描述符可以更高效使用存储器和存储装置并且可以更快通过网络传输和从数据库取回。低复杂性的描述符可以实现在低功率移动设备上的应用以及延伸大规模数据库处理能力。

移动增强现实系统在现实内容的实况视频流之上叠加虚拟内容。这些系统依赖于内容识别和跟踪以生成这一叠加。

为了在大规模取回任务上良好表现，可以在位置和比例二者上被定位的兴趣点(即特征)可能是有帮助的。可以使用不同算法、比如加速分段测试从图像搜索兴趣点、比如拐角、边缘等。一个图像可以根据图像的内容包括大量兴趣点。一些图像可以包括数以十计的兴趣点，而一些其它图像可以包括数以百计或者甚至数以千计的兴趣点。另外，可以缩放图像以提供图像的不同比例。然后，兴趣点检测器可以使用来自不同比例的像素以确定在当前像素附近是否存在兴趣点。

尽管可以以不同比例检测来自加速分段测试(FAST)拐角的特征，但是它们对比例改变固有地不敏感。以许多比例复制它们也可能产生过大的数据库和不想要的冗余性。反言之，团点(blob)检测器、比如高斯拉普拉斯(LoG)、高斯差值(DoG)、海赛行列式(DoH)和箱差值(DoB)都对比例变化敏感并且因此可能在比例空间上有局限。

发明内容

本发明引入一种用于为视觉搜索提供紧凑描述符的方法。在本发明中，提取局部图像特征并且从这些局部特征形成全局图像签名。全局特征可以比局部特征小得多。使用可以最适合用于目标比特率的嵌入形式来压缩局部签名。可以通过使用位置编码来压缩局部描述符的位置元数据。在一些实施方式中，通过从全局签名开始并且用压缩的局部描述符填充目标比特率的其余部分来形成完整查询。这一方法可以在广泛比特率下提供良好性能并且可以维持不同速率的查询之间的兼容性。换言之，包括全局描述符并且用局部描述符填充可能可用预算的其余部分。

多比例箱差值(DoB)滤波器可以用来发现图像比例空间中的团点。在一些实施方式中，比例空间的每级被子采样至它的关键防混叠频率。这向数据提供最少处理。另外，重用滤波器的结果以提供可以对于以后特征描述而言需要的图像比例空间。也可以在每个兴趣点处计算径向梯度并且将它们放入预先计算的、定向的空间仓中。

根据本发明的第一方面，提供一种方法，该方法包括：

接收与图像的兴趣点有关的一个或者多个局部描述符；

压缩所述描述符；以及

基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符。

根据本发明的第二方面，提供一种装置，该装置包括处理器和包括计算机程序代码的存储器，存储器和计算机程序代码被配置为与处理器一起使该装置：

接收与图像的兴趣点有关的一个或者多个局部描述符；

压缩所述描述符；以及

基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符。

根据本发明的第三方面，提供一种存储介质，该存储介质具有在其上存储的用于由装置使用的计算机可执行程序代码，所述程序代码包括用于以下操作的指令：

接收与图像的兴趣点有关的一个或者多个局部描述符；

压缩所述描述符；以及

基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符。

根据本发明的第四方面，提供一种设备，该设备包括：

用于接收与图像的兴趣点有关的一个或者多个局部描述符的装置；

用于压缩所述描述符的装置；以及

用于基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符的装置。

本发明提供具有相对低复杂性的兴趣点检测器。描述符计算重用兴趣点检测的结果。兴趣点检测器可以提供恰当混叠和子采样的比例空间而无附加成本。另外，无需像素插值或者梯度旋转。这之所以是可能的，原因在于，径向梯度实现在恰当空间仓中放置梯度而无任何修改。

根据本发明的旋转不变快速特征描述符可以是充分快速的以在移动设备上进行计算和实时跟踪并且对于大规模图像识别而言足够健壮。

这一跟踪方案的一个优点在于，可以匹配相同旋转不变快速特征描述符与用于图像识别的数据库而无需分离的描述符流水线。这可以减少查询延时从而促成更积极响应的用户体验。在一些实施方式中，可以延伸基本旋转不变快速特征描述符为使用极性空间建仓和排列距离的特征描述符，其中还可以增加准确性。

附图说明

为了更好地理解本发明，现在将通过示例参照附图，在附图中：

图1示意地示出运用本发明的一些实施方式的电子设备；

图2示意地示出适合用于运用本发明的一些实施方式的用户设备；

图3进一步示意地示出使用无线和有线网络连接而连接的运用本发明的实施方式的电子设备；

图4示意地示出如在装置内并入的本发明的一个实施方式；

图5示意地示出根据本发明的一个实施方式的旋转不变快速特征描述符流水线；

图6图示子采样的比例空间的示例；

图7a图示用于比例内模式的兴趣点检测的示例；

图7b图示用于比例间模式的兴趣点检测的示例；

图8图示径向梯度的示例；

图9图示在不同查询方向上的按对特征匹配的数目；

图10图示对于径向梯度变换的旋转不变性；

图11是示出本发明的一个实施方式的操作的流程图；

图12以框图示出如在装置内并入的根据本发明的一个实施方式的空间转动的示例；

图13图示可以从基本描述符推导的描述符集合的示例；

图14描绘从描述符的位置生成的2D直方图的示例；

图15图示在计算残差增强视觉矢量签名时的步骤的示例；

图16图示残差聚合的示例；

图17描绘两阶段图像取回的示例的框图；以及

图18描绘在m＝3个维度中的量化的概率分布的若干示例集合。

具体实施方式

以下进一步具体描述用于提供对图像内容识别和从数据库取回图像内容进行改进的适当装置和可能机制。就这一点而言，首先参照图1，该图示出示例装置或者电子设备50的示意框图，该装置或者电子设备可以并入根据本发明的一个实施方式的装置。

电子设备50可以例如是无线通信系统的移动终端或者用户设备。然而将理解，可以在可能需要图像内容识别和/或取回的任何电子设备或者装置内实施本发明的实施方式。

装置50可以包括用于并入和保护设备的壳体30。装置50还可以包括形式为液晶显示器的显示器32。在本发明的其它实施方式中，显示器可以是适合于显示图像或者视频的任何适当显示器技术。装置50还可以包括键区34。在本发明的其它实施方式中，可以运用任何适当数据或者用户接口机制。例如，可以实施用户接口为虚拟键盘或者数据录入系统作为触敏显示器的一部分。装置可以包括麦克风36或者任何适当音频输入，该音频输入可以是数字或者模拟信号输入。装置50还可以包括如下音频输出设备，该音频输出设备在本发明的实施方式中可以是以下各项中的任何一项：耳机38、扬声器或者模拟音频或者数字音频输出连接。装置50也可以包括电池40(或者在本发明的其它实施方式中，设备可以由任何适当移动能量设备、比如太阳能电池、燃料电池或者时钟机构生成器供电)。装置还可以包括用于与其它设备的近程视线通信的红外线端口42。在其它实施方式中，装置50还可以包括任何适当近程通信解决方案、比如蓝牙无线连接或者USB/火线有线连接。

装置50可以包括用于控制装置50的控制器56或者处理器。控制器56可以连接到存储器58，该存储器在本发明的实施方式中可以存储形式为图像的数据和音频数据二者和/或也可以存储用于在控制器56上实施的指令。控制器56还可以连接到适合于实现音频和/或视频数据的译码和解码或者辅助控制器56有可能实现的译码和解码的编码解码器电路装置54。

装置50还可以包括用于提供用户信息并且适合于提供用于在网络处认证和授权用户的认证信息的读卡器48和智能卡46、例如UICC和UICC读取器。

装置50可以包括无线电接口电路装置52，该无线电接口电路装置连接到控制器并且适合于生成例如用于与蜂窝通信网络、无线通信系统或者无线局域网通信的无线通信信号。装置50还可以包括天线44，该天线连接到无线电接口电路装置52用于向其它装置发送在无线电接口电路装置52生成的射频信号以及用于从其它装置接收射频信号。

在本发明的一些实施方式中，装置50包括能够记录或者检测个别帧的相机61，这些帧然后向编码解码器54或者控制器传递以供处理。在本发明的一些实施方式中，装置可以在传输和/或存储之前从另一设备接收图像数据用于处理。在本发明的一些实施方式中，装置50可以无线或者通过有线连接接收图像以用于处理。

关于图3，示出可以在其中利用本发明的实施方式的系统的示例。系统10包括可以通过一个或者多个网络通信的多个通信设备。系统10可以包括有线或者无线网络的任何组合、这些有线或者无线网络包括但不限于无线蜂窝电话网络(比如GSM、UMTS、CDMA网络等)、比如IEEE802.x标准中的任何标准定义的无线局域网(WLAN)、蓝牙专用网络、以太网局域网、令牌环局域网、广域网和因特网。

系统10可以包括适合用于实施本发明的实施方式的有线和无线通信设备或者装置50二者。

例如，图3中所示系统示出移动电话网络11并且示出因特网28的表示。与因特网28的连通可以包括但不限于远程无线连接、近程无线连接和各种有线连接，这些有线连接包括但不限于电话线路、线缆线路、功率线路和相似通信途径。

系统10中所示示例通信设备可以包括但不限于电子设备或者装置50、个人数字助理(PDA)和移动电话14的组合、PDA16、集成消息接发设备(IMD)18、台式计算机20、笔记本计算机22。装置50可以静止或者在由移动的个人携带时可移动。装置50也可以位于运输模式中，该运输模式包括但不限于小汽车、卡车、出租车、公共汽车、火车、船只、飞机、自行车、摩托车或者任何相似的适当运输模式。

一些或者更多装置可以发送和接收呼叫和消息并且通过与基站24的无线连接25与服务提供商通信。基站24可以连接到网络服务器26，该网络服务器允许在移动电话网络11与因特网28之间的通信。系统可以包括附加通信设备和各种类型的通信设备。

通信设备可以使用各种传输技术来通信，这些传输技术包括但不限于码分多址(CDMA)、全球移动通信系统(GSM)、通用移动电信系统(UMTS)、时分多址(TDMA)、频分多址(FDMA)、传输控制协议-网际协议(TCP-IP)、短消息接发服务(SMS)、多媒体消息接发服务(MMS)、电子邮件、即时消息接发服务(IMS)、蓝牙、IEEE802.11和任何类似的无线通信技术。参与实施本发明的各种实施方式的通信设备可以使用各种介质来通信，这些介质包括但不限于无线电、红外线、激光、线缆连接和任何适当连接。

在下文中，将参照图4的装置和图11的流程图更具体公开根据一个示例性实施方式的方法。装置50从图像源接收102图像400，该图像源可以是相机、数据库、比如因特网的通信网络、或者另一位置。在一些实施方式中，图像可以已经被存储到装置的存储器58，控制器56可以从该存储器读取它以用于处理。图像可以是所谓快照图像或者静止图像，或者它可以是视频信号的帧。在图像是快照或者静止图像时，装置50可以使用该方法以例如从数据库、从网络等搜索相似图像。在图像是视频序列的一部分时，装置50可以将该方法用于跟踪视频序列中的一个或者多个对象并且有可能突出显示对象在视频序列中的位置或者基于对象在视频序列中的位置和移动显示另一可视指示。

在一些实施方式中，图像400可以在处理之前被重设大小402，或者可以对接收的图像执行处理而不先对它重设大小。在亮度通道406中，从图像提取亮度信息、即如下像素值，这些像素值表示在图像中的像素的位置处的亮度。

控制器56可能已经确定存储器58中的用于存储图像和用于处理图像的区域。图像可以被读取到图像存储器并且被提供到一个或者多个滤波器，该一个或者多个滤波器将图像的一个或者多个滤波的表示形成到存储器58中。这些表示也可以称为比例或者比例级(scalelevel)。在一些实施方式中，不同比例数可以在1到5之间，但是也可以形成更大数目的比例。第一比例(s＝0)是原始图像。第二比例(s＝1)——该第二比例是原始图像的第一滤波版本——可以具有原始图像的比例的一半。因此，可以通过按照2对原始图像下采样来形成第二比例的图像。在一些实施方式中，通过在沿x和y方向二者上向下采样的图像中包括原有像素的像素的仅一部分来执行采样。例如，在第二比例级的图像可以包含原始图像的每隔一个像素，在第三比例级的图像可以包含原始图像的每隔两个像素，在第四比例级的图像可以包含原始图像的每隔三个像素，等等。在一些其它实施方式中，下采样使用原始图像的两个或者更多像素以形成经缩放的图像的一个像素。

换言之，可以例如通过对原始图像进行滤波以形成更粗略图像而以不同分辨率表示图像。更粗略图像可以被进一步滤波以形成又一图像等。可以减少图像在每个滤波级的分辨率。例如，原始图像先被下采样至原始图像的分辨率的一半，该图像被下采样至原始图像的分辨率的三分之一，下一级是原始图像的四分之一，等等。这一种类的图像跟踪也可以称为图像金字塔。换言之，图像金字塔是以不同分辨率的图像表示。图像金字塔的一个类型是mip图(mipmap)金字塔。mip图金字塔是原始图像的滤波版本分级，从而连续级对应于经滤波的频率。换言之，mip图金字塔将图像分解成一系列滤波的图像。mip图金字塔可以使用包括箱式滤波器和高斯滤波器在内的多种滤波器。

向滤波器部408提供原始图像和缩放的图像以进行滤波。在一些实施方式中，为了不受图像比例改变影响，针对滤波器比例范围计算滤波器响应从而产生滤波的图像堆。因此，F是转换3维比例空间的标幅度函数。如果I的维度是w×h个像素并且N是比例数，则比例空间具有维度w×h×N个像素。为了合理覆盖可能比例，可以选择覆盖～3个倍频程(上至8×比例改变)的范围。在一些实施方式中，选择N大于或者等于8(N≥8)，并且s覆盖所有整数1…N。这是比例空间线性覆盖。这在大比例时给予比指数覆盖更细微的分辨率。然而在小比例时，分辨率对于两种比例空间覆盖是相似的。

在一些实施方式中，使用箱式滤波器，这些箱式滤波器在滤波时使用在选择的像素周围的像素。滤波器响应可以是以相同点(选择的像素)为中心、但是具有不同比例的两个箱式滤波器的简单加权差值。对于比例参数s，内箱可以具有宽度2s+1，并且外箱可以大小为粗略两倍而宽度为4s+1。滤波器响应因此由下式给出：

(2s+1)^-2∑_in-(4s+1)^-2∑_out (1a)

其中∑是在箱内的像素值的总和。可以通过使用积分图像来高效计算这些总和。

可以通过定义下式来推广等式(1a)：

F(x，y，s)＝B(x，y，s)-B(x，y，2s) (1b)

可以实施滤波器例如为控制器56可执行的计算机代码。这些滤波器在本申请中称为内箱式(inner-box)滤波器412和外箱式(outer-box)滤波器414。内箱式滤波器412以在选择的像素周围的一些像素值为输入并且计算输出值B(x，y，s)、例如(2s+1)^-2∑_in。这些值被存储到存储器58中的图像比例空间存储器缓冲器416中，用于以后在描述符计算中使用。相似地，外箱式滤波器414以在选择的像素周围的一些像素值为输入并且计算输出值B(x，y，2s)、例如(4s+1)^-2∑_out。这些值以及滤波产生的值F(x，y，s)也可以被存储到存储器58中。

在一些实施方式中，可以通过使用积分图像(II)来计算在某个宽度(例如2s+1或者4s+1)的箱内的像素值的总和。令I(x，y)是输入图像400并且S(x，y)是关联积分图像，那么：

$S(x,y)=\underset{v=0}{\overset{y}{\mathrm{\Σ}}}\underset{u=0}{\overset{x}{\mathrm{\Σ}}}I(u,v)---\left(2a\right)$

并且

$\mathrm{\Σ}(x,y,s)=\begin{array}{c}S(x+s,y+s,s)+S(x-s-1,y-s-1)-\\ S(x+s,y-s-1)-S(x-s-1,y+s)\end{array}---\left(2b\right)$

利用这一方法，有可能根据单个积分图像计算在任何比例或者位置处的滤波器响应。

比例空间的值由局部极值检测器420检查以从值中发现局部最大值和最小值。考虑到滤波器响应，可以发现比例空间中的其绝对值在门限以上的局部最大值和最小值。对于这些极值中的每个极值，可以通过在某个数目的像素、例如5s个像素的半径内设定哈里斯拐角分数(Harris corner score)的门限来消除边缘响应。其余兴趣点可以按照它们的绝对响应来排序。

为了根据比例空间中的给定位置计算104描述符，在正确比例上计算防混叠的像素值。取代用积分图像或者利用三线性插值经由mip图来重新计算这些值，重用向图像比例存储器缓冲器416中存储的箱差值(DoB)滤波器结果B(x，y，s)。

如以上描述的那样，使用金字塔比例空间，其中按照与滤波器比例匹配的倍率对每个比例下采样。在一些实施方式中，在全分辨率上计算第一比例，并且按照倍率2×、3×、4×等对后续比例下采样。为了使像素位置在比例之间一致，可以在计算滤波器响应时通过简单地略过适当数目的像素来实施子采样。这一方式可以减少兴趣点检测的复杂性。

为了在下采样时防止混叠，图像被低通滤波。出于这一目的，使用来自DoB计算的内箱式滤波器值。在比例s处的每个像素因此被宽度为2s+1的矩形滤波器滤波。为了表明这一滤波器适合用于防混叠，可以考虑1D冲激响应，

关联的频率响应H(ω)由下式给出：

$H\left(\mathrm{\ω}\right)\frac{\sin \left[\mathrm{\ω}(s+1/2)\right]}{(2s+1)\sin (\mathrm{\ω}/2)}$

第一过零落在ω₀＝2π/(ω/2)。为了在按照倍率s下采样之时防止混叠，应当抑制大于奈奎斯特速率ω_c＝ω/s的频率。由于ω₀＜ω_c，所以在奈奎斯特速率内包含滤波器响应的主瓣，并且混叠的频率被抑制至少10dB。

不仅RIFF计算更少滤波器响应值，而且每个滤波器响应显著地更易于计算。加速健壮特征(SURF)使用近似海赛行列式|H|＝D_xxD_yy+(κD_xy)²。这需要共计8个箱式滤波器：2个用于D_xx和D_yy中的每一项并且4个用于D_xy。每个箱式滤波器需要3次加法和4次存储器访问。D_xx和D_yy中的每一项也需要乘法。将滤波器组装成|H|需要另外3次乘法、1次加法和1次存储器访问以存储结果。对照而言，RIFF仅使用2个箱式滤波器，每个箱式滤波器需要3次加法、一次与加权项的乘法和4次存储器访问。将滤波器组装成DoB响应需要更多一次加法和两次存储器访问以存储滤波器和图像比例空间并且每个响应需要许多操作的三分之一。

图6图示经过子采样比例空间的示例分片。存在从原有w×h个像素图像形成的N个比例。根据比例对像素子采样，但是相对于全比例来存储它们。有影线的像素602是用于比例间局部极值检测的黑像素601的邻居。也示出用于每个比例的(内，外)滤波器大小。

局部极值检测器420所发现的局部极值可以用来发现比例空间中的可重复点。然而比例空间的相邻层无相同分辨率。由于这一点，简单的27像素3D邻域是不可能的，因此使用一种用于补偿分辨率改变的方法例如如下：

在全分辨率图像堆中存储比例空间，但是如图6中所示仅计算具有与比例参数相等的采样步幅的像素值。为了发现在位置(x，y，s)处的像素的邻居，先考虑{(x±s，y±s，s)，(x，y±s，s)，(x±s，y，s)}给出的在相同比例内的8个邻居。然后搜索在更高和更低比例中的最近的现有像素(x+，y+，s+1)和(x-，y-，s-1)，其中：

考虑到上面和下面的这些中心像素，如前那样搜索中心像素的一些邻居(例如8个邻居)。这可以称为比例间检测方案。此外，如果点相对于其在相同比例上的邻居中的一些邻居、例如8个邻居为最大或者最小，则该点被确定为局部极值。尽管比例间方案提供全比例空间定位，但是比例内方案描述在多个显著比例上的点并且可以更快。图7a图示用于比例内模式的兴趣点检测的示例，并且图7b图示用于比例间模式的兴趣点检测422的示例。应当指出，在这些图中呈现的兴趣点已经在后续描述符计算期间被定向。在图7a、7b中描绘检测到的兴趣点为矩形。

即使DoB滤波器可以对团点进行强激发(fire)，但是它也可以对高对比度边缘敏感。这些边缘可能不是希望的兴趣点，因为它们被不良地定位。因此，在一些实施方式中，边缘响应以通过确定兴趣点是否为拐角或者边缘来以被去除为目标。这可以例如通过计算在每个检测到的兴趣点周围的哈里斯拐角分数来执行。哈里斯拐角分数的计算仅需计算一阶导数。令D_x和D_y是在x和y方向上的偏导数。哈里斯矩阵H由下式给出：

$H=\left[\begin{array}{cc}\⟨D_x^2\⟩& \⟨D_x{D}_y\⟩\\ \⟨D_x{D}_y\⟩& \⟨D_y^2\⟩\end{array}\right]---\left(8\right)$

其中<·>表示在局部像素窗内的平均值。可以使用以兴趣点为中心的具有某个半径、比如5s的圆形窗。这一大小的窗大到足以覆盖箱式滤波器而保持低计算成本。拐角分数Mc然后由下式给出：

M_c＝λ₁λ₂-κ(λ₁+λ₂)²＝det(H)-κtr(H)² (9)

其中λ是H的特征值，并且κ是敏感度参数。在一些实施方式中，κ＝0.1，并且仅保持具有正M_c值的兴趣点。

在计算特征描述符时，可能需要考虑一些约束。例如，在旋转期间，图像内容改变位置，并且梯度矢量改变方向。因此，算法应当对这两种改变是不变的。兴趣点检测器提供对图像内容位置改变的不变性。然而在兴趣点周围的局部补丁(patch)仍然可以经历旋转，描述符应当对该旋转是不变的。描述符由少数主分量构成；强度归一化、空间建仓(binning)和梯度建仓。在这些主分量之中，空间和梯度建仓应当是旋转不变的。在图12中图示了描述符流水线424的一个示例性实施方式。在流水线中，针对每个描述符提取补丁，并且计算方向和像素强度标准偏差。量化并且在空间仓(bin)中放置径向梯度从而产生由直方图构成的描述符。

考虑到兴趣点位置和图像比例空间，特征描述符可以由特征描述符计算部424、426计算。如图12中所示，可以计算描述符如下。

在某个直径为D的圆形补丁上的描述符由提取补丁部440计算。直径D例如是25s、以点(x，y，s)为中心。用s个像素的步幅从在兴趣点检测期间预先计算的图像比例空间418对补丁中的像素进行采样。

然后执行方向指定442。使用以[-1，0，1]为中心的差值滤波器针对补丁中的每个像素计算444(x，y)梯度，并且形成448梯度方向的72仓、幅度加权的直方图。查找表可以用来将像素差值转换成角度和幅度446。利用8比特像素值，有512×512个可能的梯度值。为了健壮性，可以向直方图应用简单的[1，1，1]低通滤波器450。可以发现452主导方向例如如下。如果第二最主导角度仓的值在某个门限、比如主导仓的值的90％内，则选择在二等分两个仓的角度右侧的仓。应当指出补丁无需被实际旋转，但是仅应当发现角度。

图8图示径向梯度的示例。

对于径向梯度量化，计算460补丁的标准偏差σ。然后可以计算454近似径向梯度变换(ARGT)。近似径向梯度变换应当并入恰当的基线归一化，因为对角像素邻居比水平或者竖直邻居更远。令b在近似径向梯度变换中是两个像素之间的距离，并且q是希望的梯度量化器步长大小。通过将像素差值乘以(bqσ)^-1来组合量化器参数、强度和基线归一化。通过对每个分量取整成{-1，0，1}来获得456量化的径向梯度，从而产生九个可能梯度之一。

在图12中描绘径向旋转为块458。考虑到描述符方向θ，选择被旋转-θ的空间布局。对于速度，可能已经为每个可能方向预先计算了空间仓。可以如图13中所示使用对于共计9个仓具有中心仓和各自为4个仓的两个外环的布局。在每个空间仓中，形成被归一化以求和成一的量化的梯度的直方图。所得描述符为81维。径向梯度已经是旋转不变的，因此通过将它们放置于恰当空间仓中，整个描述符428是旋转不变的。

为了示范RIFF流水线对于图像旋转是不变的，可以使用按对图像匹配。对来自MPEG数据集的100对CD图像执行按对匹配。按照5°增量旋转图像之一，并且记录几何验证的特征匹配的数目。为了保证无边缘影响，裁剪图像为圆形区域，并且在所有侧上用100个像素填充边界。在图9中，对于有和无近似径向梯度的RIFF以及对于SURF示出这些结果。在SURF中的振荡结果有90°的周期，这归因于箱式滤波器的各向异性。在来自DoB滤波器的确切RGT RIFF中有相似振荡。使用近似RFT引入更高频率的振荡，该振荡具有45°的周期，这是由8方向RFT近似引起的。然而这一近似一般提高匹配性能。

由于RIFF描述符由归一化的直方图组成，所以可以应用一些压缩技术。可以量化和压缩整个直方图，从而保留L₁范数。具体而言，可以使用具有与梯度仓的数目相等的量化参数的编码技术。这可以产生可以使用固定长度代码在135比特中或者用可变长度代码在～100比特中存储的压缩RIFF(C-RIFF)描述符。这是每维度8比特、未压缩的描述符的6.5分之一。

在下文中，更具体讨论描述符的压缩的一个示例性实施方式。空间和梯度建仓配置的精确选择可以显著更改描述符的性能和大小。然而具有不同配置的描述符可能不兼容。为了实现兼容性而允许描述符配置的变化，可以定义嵌入的描述符。对于这样的描述符，可以从称为基础描述符的单个高维描述符推导多个较小的描述符。使用这一基础描述符，可以提取空间/梯度仓的子集和/或可以组合邻近的空间/梯度仓。

图13图示可以从基础描述符推导的描述符的集合。在描述符下方示出配置编号。在这一示例性实施方式中，基础描述符使用9个梯度仓和17个空间仓。空间仓由中心圆盘组成，该圆盘由8个角度仓的两个环包围。为了减少空间仓的数目，可以例如通过平均在角度仓中包含的分布来组合角度仓和/或可以去除外环。为了减少梯度仓的数目，例如通过将仓的值彼此相加而将邻近仓组合成固定风车图案。表1示出用于每个嵌入的描述符配置的大小参数的示例以及描述符的大小。为了估计描述符大小，可以测量后续量化所产生的符号的熵。在一些实施方式中，3×4-SQ5配置在4096字节的查询大小和以下表现最好，并且3×8-SQ9配置在4096字节以上表现最好。

名称	梯度仓数目	空间仓数目	维度	熵(比特)
					3x8-SQ9	9	17	153	206.16
2x8-SQ9	9	9	81	108.97
					3x8-SQ5	5	17	85	103.06
3x4-SQ9	9	9	81	101.25
					2x4-SQ9	9	5	45	55.89
2x8-SQ5	5	9	45	53.85
					3x4-SQ5	5	9	45	47.07
2x4-SQ5	5	5	25	25.71

表1

在每个空间仓中将梯度信息作为分布进行存储。这允许应用基于直方图的压缩技术。为了压缩106描述符，在每个空间仓中个别量化梯度直方图。一些量化方案可以对于压缩分布起良好作用：通过霍夫曼编码、类型编码的量化和最优Lloyd-Max矢量优化(VQ)。这里简要讨论基于A_n格(lattice)的量化方案之一。A_n格在复杂性方面与直方图仓的数目成线性并且表现出接近最优Lloyd-Max VQ。令m表示梯度分布中的直方图仓的数目并且令是如梯度直方图描述的原有分布并且令是量化的概率分布。先构造具有以下概率的分布Qn＝Q(k1，...，km)的格：

$q_i=\frac{k}{n},k_i,n\&Element;Z_{+},\underset{i}{\mathrm{\&Sigma;}}{k}_i=n---\left(10\right)$

图18描绘在m＝3个维度中的这样的集合的若干示例。

从格论的角度来看，集合Q_n是A_n格的有界子集。参数n控制量化保真性，并且n参数值越高，保真性就越高。n＝m提供在大小与准确性之间的良好折衷。其次，在对分布P进行量化之后，计算用于类型的索引。类型K(m，n)的总数是使n成为m项k₁+...+k_m＝n的分割的数目：

$K(m,n)=\left(\begin{array}{c}n+m-1\\ m-1\end{array}\right)---\left(11\right)$

可以用固定长度或者熵编码在每个空间单元中对索引进行编码。例如上下文自适应二进制算术编码器(CABAC)可以用于对符号进行熵编码。这里描述的量化方案表现出接近最优Lloyd-Max VQ并且无需在移动客户端上存储码本。

每个兴趣点具有与它关联的位置、比例和方向。在几何验证步骤中需要兴趣点位置以使潜在候选匹配生效。可以存储每个兴趣点的位置为两个数：在子像素精度方面、在图像中的x和y坐标。在浮点表示中，每个特征位置将需要64比特，用于x和y各32比特。这在大小上与CHoG描述符本身可比较，因此位置数据的紧凑表示可能是重要的。

为了压缩位置数据，可以利用可以按照任何顺序发送特征这一事实。考虑表示N个特征的采样空间。存在由于顺序无关紧要而表示相同特征集合的、数目为N！的代码。因此，如果固定用于特征集合的排序、也就是使用以上描述的LHC方案，则可以实现log(N！)的比特节省。例如对于750个特征的特征集合，可以实现每特征log(750！)/750～8比特的速率节省。

在一些实施方式中，使用基于重新排序的压缩方案。可以通过对描述符重新排序或者对与它们关联的位置数据重新排序来获得排序增益。用于对描述符重新排序的方案包括树形直方图编码和基于数字搜索树的方案。在这一示例中，使用位置直方图编码(LHC)方案，因为它表现良好。已经指出图像中的兴趣点可以被空间聚类。为了对位置数据进行编码，根据描述符的位置生成2D直方图。在图14中描绘这一点的示例，在该示例中，使用位置直方图来表示描述符的位置。将图像划分成空间仓，并且对每个空间仓内的特征的数目进行计数。压缩指示哪些空间仓包含特征的二元图和表示所占用的仓中的特征的数目的特征计数序列。使用训练的基于上下文的算术编码器对二元图进行编码而使用邻近仓作为用于每个空间仓的上下文。

LHC导致log(N！)的比特率减少。另外，使用邻近仓作为上下文，可以利用不同描述符的位置之间的附加空间相关性。

已经发现将(x，y)位置量化成4像素块可以足以用于集合验证。如果使用简单的固定长度编码方案，则速率对于VGA大小图像将为log(640/4)+log(480/4)～14比特/特征。使用LHC，可以用～5比特/描述符发送相同位置数据——与64位浮点表示比较的～12.5×数据减少和与固定长度编码比较的～2.8×速率减少。可以在比特流中不包括比例和方向数据，因为在取回设置中未使用它们。

除了局部特征之外，还使用全局描述符108。这一全局描述符可以称为残差增强视觉矢量(Residual Enhanced Visual Vector，REVV)。REVV描述符在局部聚合的描述符矢量(VLAD)上构建。如图15中所示，在计算REVV签名时的步骤可以如下。对于量化502，针对局部描述符500离线创建视觉词的码本。最高维的嵌入的描述符(或者基础描述符)用于计算质心。令c₁...c_k是d维质心的集合。在第一步骤中，将图像中的每个描述符量化成最近视觉词。可以使用小的字典大小k＝192。

对于在量化之后的聚合504，词残差(WR)矢量的集合将如图16中所示那样包围每个视觉词。聚合在每个视觉词周围的均值。可以为这一步骤定义特征的最大值。在这一示例性实施方式中，最大值为720。对特征数目设置门限使得能够保持全局签名紧凑。全局描述符的维度由k×d给出，d个维度用于每个质心。

使用适当方法、比如线性判别式分析(LDA)将残差的维度减少506至某个值dLDA、例如32。利用LDA，可以减少全局签名的维度并且也可以提高性能。

在通过LDA减少维度之后，根据符号将变换的残差的每个分量二值化508成+1或者-1。这一有符号的二值化创建紧凑图像签名，该紧凑图像签名仅需至多k×dLDA比特以表示残差和k比特以指示已经访问了哪些视觉词。如果图像的特征未访问一些质心，则需要更少比特。对于dLDA≤32，可以将在视觉词的二值化的残差分量方便地紧缩成32比特无符号整数。二值化产生图像的紧凑全局签名510。可以仔细选择参数，这些参数产生～512字节的全局签名。紧凑签名可以用于快速编索引和低比特率取回二者。

特征提取的一个目的是通过匹配如上所述那样获得的描述符与数据库图像的集合并且发现如下图像来进行图像识别，这些图像的描述符提供足够准确的匹配。

利用RIFF流水线，可以通过在每帧处提取特征并且使用跟踪算法来执行视频跟踪和内容识别二者。对于移动站，应当在移动设备上实时提取增强现实特征。

可以例如在按对图像匹配中使用本发明。为了匹配一对图像，可以比较它们的全局签名。由于签名是二进制的，所以可以在压缩域中通过使用汉明距离来很高效地执行比较。如果距离在门限以下，则可以断言该对图像为匹配。然而如果距离未在这一门限以下或者为了定位图像内容，则可以执行局部特征匹配。

在一些示例性实施方式中，查询大小大于512字节，查询包含局部特征和它们在图像中的关联位置。为了使用这些特征，先将它们解码成它们的原始分布，并且形成描述符。使用比值测试、使用近似最近邻居搜索来比较局部特征集合。这产生特征匹配集合。使用这些匹配和特征的位置，可以例如使用RANSAC在两个图像之间发现仿射几何模型。如果几何一致的特征匹配的数目在门限以上，则可以断言图像匹配。所得仿射模型允许定位图像内容。有可能的是全局签名测量断言图像匹配而可能仍未发现几何一致的局部特征匹配集合。这可能在大小为小的查询时产生，其中有很少局部特征。在这一情况下，可以用在图像的中心内的固定矩形来定位图像内容。

对于数据库取回而言，可以如图17中所示使用两级方式。数据库图像先使用全局描述符712、按照它们与查询的相关性702来排序。然后对在排序的候选列表704中的靠前的图像706(例如前50个图像)如先前描述的那样执行按对匹配708。然后使用按对特征匹配的数目对这些靠前的图像重新排序。用每个数据库图像计算全局描述符相关性分数可能是计算成本高的。为了加速这一过程，可以先使用部分全局描述符来执行部分相关。每个全局描述符由N＝192个质心残差组成、因此使用n<N个质心计算部分相关性产生N/n×加速。在这一示例性实施方式中，n＝80为2.4×加速。然后使用全相关性对前12,500个图像重新排序。为了提高MAP性能，可以预处理数据库以发现相似图像。然后增加与最高打分图像有关的数据库图像的分数。这一预处理给出MAP性能的约百分之2至3增加。

用户设备可以包括移动设备、机顶盒或者能够处理图像的另一装置、比如以上在本发明的实施方式中描述的装置。

应当理解，术语用户设备旨在覆盖任何适当类型的用户设备、比如移动电话、便携式数据处理设备或者便携式网络浏览器。

另外，公共陆地移动网络(PLMN)的单元也可以包括如以上描述的视频编码解码器。

一般而言，可以在硬件或者专用电路、软件、逻辑或者其任何组合中实施本发明的各种实施方式。例如，可以在硬件中实施一些方面而可以在控制器、微处理器或者其它计算设备可以执行的固件或者软件中实施其它方面，但是本发明不限于此。尽管本发明的各种方面可以被图示和描述为框图、流程图或者使用一些其它图形表示来图示和描述，但是很好理解可以在作为非限制示例的硬件、软件、固件、专用电路或者逻辑、通用硬件或者控制器或者其它计算设备或者其某个组合中实施这里描述的这些块、装置、系统、技术或者方法。

可以通过移动设备的数据处理器、比如在处理器实体中可执行的计算机软件、或者通过硬件、或者通过软件和硬件的组合实施本发明的实施方式。另外就这一点而言，应当注意如各图中的逻辑流程的任何块可以代表程序步骤或者互连的逻辑电路、块和功能或者程序步骤和逻辑电路、块和功能的组合。软件可以存储于比如在处理器内实施的存储器芯片或者存储器块、磁介质、比如硬盘或者软盘和光学介质、如例如DVD及其数据变体CD这样的物理介质上。

存储器可以是适合于本地技术环境的任何类型并且可以使用任何适当数据存储技术、比如基于半导体的存储器设备、磁存储器设备和系统、光学存储器设备和系统、固定存储器和可拆卸存储器来实施。数据处理器可以是适合于本地技术环境的任何类型并且可以包括作为非限制示例的通用计算机、专用计算机、微处理器、数字信号处理器(DSP)和基于多芯处理器架构的处理器中的一项或者多项。

可以在各种部件、比如集成电路模块中实现本发明的实施方式。集成电路的设计主要是高度自动化过程。复杂而强大的软件工具可用于将逻辑级设计转换成准备好在半导体衬底上蚀刻和形成的半导体电路设计。

程序、比如加利福尼亚州山景城的Synopsys公司和加利福尼亚州圣何塞的Cadence Design提供的程序使用建立好的设计规则以及预存的设计模块的库在半导体芯片上自动对导体布线和对部件定位。一旦已经完成用于半导体电路的设计，就可以按照标准化电子格式(例如Opus、GDSII等)向半导体制作设施或者“工厂(fab)”发送所得设计用于制作。

前文描述已经通过示例性而非限制的示例提供对本发明示例性实施方式的完全而有启发的描述。然而，各种修改和适配鉴于在与附图和所附权利要求结合阅读时的前文描述可以变得为相关领域技术人员所清楚。然而对本发明的教导的所有这样和相似的修改仍将落入本发明的范围内。

Claims (20)

1.一种方法，包括：

接收与图像的兴趣点有关的一个或者多个局部描述符；

压缩所述描述符；以及

基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符。

2.根据权利要求1所述的方法，还包括：

确定比特率；

将压缩的全局描述符包括于比特流中；以及

如果在包括所述压缩的全局描述符之后存在可用比特率，则向所述比特流添加一个或者多个压缩的局部描述符。

3.根据权利要求1或者2所述的方法，还包括提供所述比特流以用于从数据库搜索图像。

4.根据权利要求1、2或者3所述的方法，还包括定义具有梯度仓和空间仓的基础描述符。

5.根据权利要求4所述的方法，还包括组合所述基础描述符的所述梯度仓中的两个或者更多梯度仓。

6.根据权利要求4或者5所述的方法，还包括组合所述基础描述符的所述空间仓中的两个或者更多空间仓。

7.根据权利要求1至6中的任一权利要求所述的方法，还包括将梯度信息作为分布进行存储；以及量化所述梯度直方图。

8.根据权利要求1至7中的任一权利要求所述的方法，还包括对与所述描述符关联的位置数据重新排序以用于压缩。

9.根据权利要求1至8中的任一权利要求所述的方法，还包括根据所述描述符的位置生成直方图。

10.根据权利要求1至9中的任一权利要求所述的方法，还包括将图像划分成空间仓；以及对在每个空间仓内的特征的数目进行计数。

11.根据权利要求10所述的方法，还包括形成指示哪些空间仓包含特征的二元图；以及形成表示在所占用的仓中的特征的所述数目的特征计数序列。

12.根据权利要求10或者11所述的方法，还包括压缩所述特征计数序列。

13.一种装置，包括处理器和包括计算机程序代码的存储器，所述存储器和所述计算机程序代码被配置用于与所述处理器一起使所述装置：

接收与图像的兴趣点有关的一个或者多个局部描述符；

压缩所述全局描述符；以及

基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符。

14.根据权利要求13所述的装置，还包括如下计算机程序代码，所述计算机程序代码被配置为与所述处理器一起使所述装置：

确定比特率；

将压缩的全局描述符包括于比特流中；以及

如果在包括所述压缩的全局描述符之后存在可用比特率，则向所述比特流添加一个或者多个压缩的局部描述符。

15.根据权利要求13或者14所述的装置，其中所述比特流被提供以用于从数据库搜索图像。

16.根据权利要求13、14或者15所述的装置，还包括如下计算机程序代码，所述计算机程序代码被配置为与所述处理器一起使所述装置定义具有梯度仓和空间仓的基础描述符。

17.根据权利要求13至16中的任一权利要求所述的装置，还包括如下计算机程序代码，所述计算机程序代码被配置为与所述处理器一起使所述装置：将图像划分成空间仓；以及对在每个空间仓内的特征的数目进行计数。

18.根据权利要求17所述的装置，还包括如下计算机程序代码，所述计算机程序代码被配置为与所述处理器一起使所述装置：形成指示哪些空间仓包含特征的二元图；以及形成表示在所占用的仓中的特征的所述数目的特征计数序列。

19.一种包括计算机指令的存储介质，所述计算机指令用于：

接收与图像的兴趣点有关的一个或者多个局部描述符；

压缩所述描述符；以及

基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符。

20.一种设备，包括：

用于接收与图像的兴趣点有关的一个或者多个局部描述符的装置；

用于压缩所述描述符的装置；以及

用于基于所述一个或者多个局部描述符来确定用于所述图像的全局描述符的装置。