On the burstiness of visual elements

1.论文介绍

这篇文章主要解决了图像检索过程当中的突发(Burstiness)问题。
在BoW模型当中，
一个视觉元素在一个图片中多次出现可能导致匹配效果的降低。

2.图像检索的框架

该研究采用Hessian-afine检测子进行SIFT特征求解，并基于Flickr数据集应用k-means算法构建了一个包含约20,000项的视觉词汇表。针对提取的新特征向量，在计算其与各视觉中心之间的欧氏距离后确定其所属位置。这将有效将原始特征空间划分为多个子区域或细分区域，并用q(x)表示该特定特征向量x对应的Visual Word位置索引

Hamming Embedding
Hamming Embedding 通过实现特征的二元表示来提取图像的关键信息，并基于特征间的海明距离对同一视觉区域内的相距较远的图像进行筛选。在Hamming Embedding框架下进行特征匹配的过程如下：
基于一个特征描述子s(x)及其核心位置的相关表征

该公式显示，在具有相同视觉中心的目标样本特征与其他相关联的其他目标样本特征中，如果这些特征对之间的海明距离小于 h_t = 24 ，则该目标样本将为其所属图像进行投票。

加权Hamming Embedding
上述Hamming Embedding匹配结果仅限于投票与未投票两种状态。然而，在考虑具有相似特性的特征对象时，应预期其间的Hamming距离会较为接近。因此可知，在这种情况下Hamming距离能够反映特征间的相似程度。基于此考虑，在计算得到的Hamming距离基础上可采用以下基于Hamming距离的加权方式来评估两个特征间的相似程度。

可以看出，在距离越近时相似度越高，并可将其视为tf的一种延伸形式。下面就是通过结合idf来获得一个特征与另一个特征之间的得分，并以此为依据对特定图片进行投票。

弱几何验证
弱几何验证是一种基本实现旋转和平移效果的方法。对于匹配上的特征点位置进行检测后判断是否存在旋转和平移关系，并剔除那些不符合旋转与缩放关系匹配点。
得分归一化处理
对于上述特征点计算出的得分(score(x,y))值，则会对整幅图像的所有得分进行归一化处理，在计算时会将其除以视觉单词出现次数所构成直方图的L2范数长度作为归一化因子。

多个视觉中心所承载的特征信息
在信息检索的过程中（即从数据中提取有用信息的过程），传统的信息处理方法通常会将单一特征属性分配至单一视觉区域。然而，在某些情况下（如基于k近邻的方法），可能会将同一特征分配至多个相关区域以增强识别能力。研究者采用加权汉明距离这一度量标准来评估不同区域间的相似性程度，并通过多维空间建模技术实现查询结果在多维空间中的分布情况，在这一阶段仅关注于查询过程而不涉及索引构建步骤。

同时作者会对查询特征与视觉中心之间的距离施加限制以防止将特定的特征归类到不相关的位置这种限制机制基于距离参数d和调节因子\alpha来实现具体来说这种机制通过设定不同的距离阈值来确保只有那些满足条件的特征才会被归类到这里实验中设定调节因子\alpha=1.2. 在这种设置下当该特征与其他所有候选单元的距离均小于\alpha d_0时则将其归类至此

校验空间
即通过一个二维仿射变换矩阵来验证两个匹配点集合间的正确性。然而，在这一过程中需要确定该二维矩阵的具体参数会导致较大的计算量。因此，在实际应用中我们仅在前200个搜索结果中进行应用。

3.突发情况的解决

作者针对上述出现的突发情况的问题提出了三套方案以供选择。
第一方案通过消除多处匹配来实现问题解决。
第二方案及第三方案则分别通过减少图片内部以及图片之间可能出现的突发情况来实现问题解决。

去重处理 在布料编码（Bag of Features）的过程中，在实际操作中需要排除重复匹配的情况以提高算法效率和结果质量。具体而言，在BoF过程中可能会出现单个特征描述符为同一图像生成多个响应的情况，在这种情况下需要采取措施避免出现这种情况。为了避免出现这种情况，在设计算法时可以通过这种方式实现：即通过设置机制确保每个描述子仅对数据库中的每张特定图像投一次票。这样就能保证每次查询都能高效准确地找到最相似的结果而不至于因为重复响应而影响结果的质量和稳定性

在图像内部发生的突然事件可能导致系统异常运行。为了实现高效的检索性能研究者们提出了多种优化方法。这些方法通常基于以下基本假设：相似性度量能够有效反映图像间的语义关联性。基于此我们采用如下符号系统进行建模：设x_i为查询图像的第i个特征描述子；设b_j^{db}为数据库中第b张图片的第j个特征向量；定义m(i,b,j)为第i个查询特征与数据库中b图像的第j个特征之间的匹配分数；当查询目标与数据库中的某张图像是不同类别的时匹配分数$m(i,b,j)=0；若两者类别一致但空间距离超过预设阈值则计算其相似度得分并赋予非零值；最后通过统计所有匹配得分的方式完成检索任务

通过变换可以得到一个匹配的最后得分：

作者在试验的过程当中使用到了其他的变换，以此来提高得分的可靠性。

图片之间的突然情况
对于图片之间可能出现的突然情况, 可以通过采用IDF技术来解决这个问题. IDF技术能够降低同一特征在多个位置重复出现所带来的权重过高问题. 然而该方法并未考虑匹配质量以及数据库中各特征间的近邻关系, 因此这种方法无法直接应用于计算海明距离. 随后提出了 一种关于IDF延伸的方法: 对于一个查询特征, 定义这个特征在数据库中的查询得分为...

t_b(i)代表了该特征与库内相关特征之间的匹配得分。
符号定义可参考上方公式部分。
更新得分为：

该公式对于一个特征对多个图片实施投票过程的同时施加了惩罚项，并将其视为IDF的一种扩展形式。

4.实验

4.1数据集**

4.1.1. Kentucky object recognition benchmark

这个数据集包含2550个目标。每个目标会有四个不同角度的图片表示。

4.1.2. Oxford building dataset

该数据集源自Flickr平台，在每张查询图片中呈现的是一个矩形建筑区域。正确检索的结果是该建筑所在区域内的其他图片。
该数据集经过裁剪和变换处理，并仅包含55张用于查询的图片。

4.1.3.Holidays dataset

1491幅风景照片共计分成500个类别，在每个类别中首次出现的照片都被定为查询图象，在类内部剩余的照片则用于查找相似的照片

4.1.4.大规模检索数据集

作者融合了Flickr1M的图片，作为影响集合，来测试算法的可扩展性。

4.1.5.评估方法

所有数据集均将采用评估指标mAP进行测试。Kentucky数据集的作者会采用搜索结果中前四个正面实例的平均值作为评价标准。

4.2.参数的影响

4.2.1Hamming Embedding 权重影响

探讨Hamming Embedding权重对mAP的作用。
研究者在实验过程中设定σ值范围为10至20，并通过图形展示了不同σ值下mAP的变化趋势。

研究表明，在σ=16时表现最佳。此外，作者在海明距离阈值方面进行了实验。实验结果显示如图所示。

基于传统单一归属视觉中心设计的方法，在测试集上的平均精度（mAP）表现较为理想。然而，在允许一个特征被多个视觉中心分配的情况下（即多分配策略），经过多次实验比较分析可知，在theshold设置为22时能够获得更好的分类效果。通过实验结果对比分析可知，在theshold增大至一定程度后会使mAP显著下降（即出现较大的分类误差）。值得注意的是，在后续研究工作中作者采用了theshold=24的设计方案，并成功筛选出误匹配项的比例达到93%左右。

4.2.2 突发函数的影响

该作者在后续的两种方法中阐述了关于数据分类的具体函数。这里该作者列举了其他一些优化机制。实验结果如下：

其中N(i,b)被定义为视觉中心q(x_i)在图像b中的出现次数。 通过调用这些函数（例如函数3、4和5）可以得到一个近似的计算结果。

4.3.和传统的方法比较

4.3.1BoF 方法的Baseline

如下图所示：

4.3.2海明权重和特征多归属(MA)

海明权重与多特征赋予权重在holidays与Oxford数据集上的mAP指标提升幅度为0.06。上述两个数据集上mAP值可分别达到0.606与未采用加权策略时的对比实验结果相比，在Hamming Embedding的基础上增加了约11.3%（从0.493提升至当前值）。

4.3.2突发情况的结果

Kentucky数据集

Oxford数据集

Holidays数据集

大量数据
作者引入了Flickr1M数据集到上述三个数据集中展开实验验证。具体结果如图所示：

观察到该方法在数据集规模扩大时表现得更加稳定，在结果下降速度上优于其他方案，并由此可推断出该方法在处理大规模数据时展现出良好的扩展性能