基于混合马尔科夫链模型和扩散的图像检索

冯 秋 燕

(河南财经政法大学 河南 郑州 453800)

0 引 言

图像检索在信息检索中占据越来越重要的位置。就目前而言，对图像检索过程进行改进或优化的方法有很多，文献[1]指出对检索结果进行重排可以显著提升检索性能，这方面研究尚不成熟，本文采用混合马尔科夫链模型和扩散方法基于多特征融合对图像检索进行研究。图像检索的目的是根据给定的目标图像寻找相同或相似的图像，其中，给定的目标图像中并不附带文本信息，通常是一个特定的对象，而不是一个类属层，在类属层面，仅需要识别对象类属，如属于人、动物或景色。基于局部特征的BOW[2]、SIFT描述器[3-4]，被广泛的用于检索系统。文献[5-8]讨论了基于BOW性能与规模的改进。文献[9]提出了VLAD来平衡存储足迹与检索性能。

1 研究现状

1.1 通过单一特征的图像索引

文献[2]采用了tf-idf方法，计算查询对象和数据集图像的BOW特征向量之间的相似性进行检索。文献[8]使用了继承聚类算法构造词汇树以减少计算代价，并应用于大规模数据集。文献[10-11]给予单词更多可识别的BOW向量而不是量化描述器给一个可视化单词。为了弥补基于标准BOW方法中空间信息的缺失，文献[5]提出了使用SIFT描述器做图像间的匹配。文献[6-7,12]的查询扩展已经被广泛应用于检索对象的重排。

在特征设计方面，文献[9]提出了VLAD做聚合描述。当查询比较少的存储时，效果比BOW好。文献[13]提出基于VLAD向量标记平方根，是对VLAD的改进。文献[12]基于原始SIFT用Hellinger内核提出RootSIFT以解决标准BOW特征的突发性问题。目前还有一些基于这些工作的改进，如数据集特征聚合[14]、HSV颜色直方图[15]等。

1.2 多重特征的图像检索

尽管单一特征能够达到好的检索结果，但融合多重特征将得到比较好的性能。因为多重特征能从不同的角度描述图像。文献[16]通过具体的特征将初始排列列表转换为无向图，对每个图计算其K-近邻，这样每个图的结点间的边就代表了数据库图像间的关系。图像间的相似性通过Jaccard相似度评估，但Jaccard相似度太粗糙，无法描述图像间的组对关系。文献[17]将从大型数据集中学习的属性应用于检索数据库。

1.3 多重特征学习

文献[18]利用各个特征的信息，提出了一种分层回归算法。文献[19]通过多重特征将多个得分矩阵分解为低秩矩阵，该矩阵附加了特定特征的稀疏误差。

2 提出的方法

2.1 概 况

本文提出了一种受监督的数据驱动方法，融合多重特征，以图形表示方式重排数据库图像。对每一个特征，给定查询对象与初始索引图像，构造一个无向图，结点代表这些图像，边权重是图像之间组对相似性得分。本文使用混合马尔科夫链模型组合多重图至一个图。本文引入概率模型来计算每个特征在朴素贝叶斯公式下的重要性，采用迭代扩散算法，以减少噪声的影响，进一步提升检索性能。

2.2 相关概念与定理

2.2.1 相关概念

定义2易处理图(Gm)。针对特征m，图像间的组对关系被描述为图，Gm=(Vm,Em,em)，其中，Vm是图像结点集合；Em是边；em是边的权重，权重em是在特征m下图像之间的相似性。

定义4转移矩阵(P)。给定亲和力矩阵T，转移矩阵定义为P=D-1T，其中，D是第i个对角元素的对角矩阵，d(i,i)=d(Vi)，d(Vi)是融合图中结点Vi的度。

定义5图间转移概率(pm′(Vi))。假设从易处理图Gm中的结点Vi出发，其中Vi∈V，结点Vi在易处理图Gm′中选择路径的概率即图间转移概率为pm′(Vi)。

定义6结点转移概率(pm(Vj|Vi))。pm(Vj|Vi)=em(Vi,Vj)/dm(Vi)，其中，dm(Vi)=∑jem(Vi,Vj)是易处理图Gm中Vi的度，易处理图Gm的体积为图中所有边的权重的和，即volmV=∑Vi,Vj∈Vem(Vi,Vj)=∑Vi∈Vdm(Vi)。

定义7融合图中结点转移概率(pG(Vj|Vi))。pG(Vj|Vi)为融合图G中从结点Vi到Vj的转移概率。pG(Vj|Vi)=∑mpm(Vj|Vi)pm(Vi)。

定义8结点Vi的静止状态(πm(Vi))。πm(Vi)=dm(Vi)/volmV。其中，dm(Vi)是易处理图Gm中结点Vi的度。volmV是易处理图Gm的体积。

2.2.2 相关定理

定理1p(Vj|Vi)=e(Vi,Vj)/π(Vi)

(1)

证明：由定义5、定义6、定义7、定义8，可得：

p(Vj|Vi)=∑mpm(Vj|Vi)pm(Vi)

(2)

pm(Vj|Vi)=em(Vi,Vj)/dm(Vi)

(3)

πm(Vi)=dm(Vi)/volmV

(4)

(5)

将式(3)、式(4)、式(5)代入式(2)，可得：

(6)

融合图中结点Vi与Vj之间边的权重记为：

(7)

可得式(1)，证明完毕。

2.3 构造易处理图

从所有r特征的初始检索结果，本文完全获得n个图像。原始数据集可能会包含数百种图像，由此可为每个检索图像得到一个查询排列列表，由此，得到一个关于该检索图像的图。本文仅选择每个特征的排序为前L的检索图像根据定义2构造易处理图Gm。前L个检索图像的排列列表被认为是短列表。定义所有图的节点集合为V。对于每个易处理图Gm，本文添加来自V但不是最初由特征m检索的结点至图中，连结先前的缺失结点与图中初始检索结点的边也被添加。以这种方式，本文用缺失结点完成了每个易处理图，每个易处理图中都有相同的节点集合V，也包含了短列表中的结点间的组对关系。

因此，对r个特征，有r个图集：

G={Gi,1≤i≤r}

(8)

根据定义3，有一组相同规模的图像矩阵：

S={Sj,1≤j≤r}

(9)

2.4 构造多特征融合图

在2.3节得到亲和力矩阵S后，然后用这些矩阵融合图G中的图。亲和力矩阵应当是完备的并且不是稀疏矩阵，本文采用了基于文献[20]中启发的混合马尔科夫链模型的概率方法。

根据定义5、定义6、定义7，从一个结点出发，路径选择器首先选择下一步的图，然后选择进入该图或者留在本图中，根据图像矩阵选择相邻结点，如图1所示。直观地，p(Vj|Vi)与结点Vi和它的邻居结点的边相关。根据定义6，本文采用结点的度与图的体积来计算p(Vj|Vi)。根据定义8，在这些步之后，随机路径选择模型将达到一个静止状态。

图1 基于两个图的混合马尔科夫模型

根据定理1基于无向图的马尔科夫链模型简化为常规化的亲和力矩阵的结点集合。因此，常规化所有亲和力矩阵Sm至Tm，其中：

Tm=Sm/volmV

(10)

则有:

T={Tj,1≤j≤r}

(11)

(12)

式中，p(Ij∈P)与p(Ij∈Q)分别代表图像Ij是对给定查询图像相似性或不相似性的边缘概率。

(13)

式中：

(14)

(15)

(16)

ωm(Vi)=ρm(Vi)/∑ρm(Vi)

(17)

对图Gm中的非查询图像Vj，本文设置r特征的权重均为：

ωm(Vj)=1/r

(18)

由此，得到权重向量：

ωm=(ωm(V1),ωm(V2),…，ωm(Vn))T

(19)

代表Gm中所有结点的权重。融合图T的常规化亲和矩阵由下式计算：

T=∑mdiag(ωm)·Tm

(20)

式中：在diag(ωm)∈Rn×n中的第i行的对角元素与ωm(Vi)相关。

2.5 扩散过程

由2.4节可得新的亲和力矩阵T，由T推断新排序。通过对T进行扩散处理减少噪声。方法是计算一个结点到它邻居结点的相似性得分直至达到一种静止状态，本文采用迭代扩散过程提高效率。根据定义4，建立一个矩阵：

(21)

(22)

式中，PK是K-NN图GK的转移矩阵，PK仅由每个结点与其K个最邻近结点的相似性得分构建，各边的权重em(Vi,Vj)=0。

本文的融合方法的整个过程如算法1所示。

算法1基于扩散的多特征重排算法

输入：r阶亲和力矩阵S={Sj}，其中，1≤j≤r；查询图像Ii

输出：对Ii的重排结果

1. form=1 tordo

2.常规化Sm至Tm(见2.3节和2.4节)

4.通过式(13)，计算特定查询置信度ρm(Vi)

5.计算式(19)中的权重向量ωm，其中，对每一个查询结点，根据式(17)，有ωm(Vi)=ρm(Vi)/∑ρm(Vi)，非查询结点，根据式(18)，有ωm(Vj)=1/r

6.end for

7.通过式(20)得到融合图的亲和力矩阵T

8.对T使用融合过程

9.通过对查询结点Ii的相关的行的相似性得分的排序，得出T的新排列。

3 实 验

3.1 实验的建立

本文使用4个广泛使用的数据集，Holidays[22]、UKbench[8]、Oxford5k[5]、Paris6k[10]。本文使用现有的图像检索系统中广泛使用的2个局部特征和2个全局特征。对评估矩阵，在UKbench数据集上使用N-S得分[8]，在Holidays、Oxford5k、Paris6k数据集上使用平均精度(mAP)。

3.2 与已存方法的比较

首先，比较本文方法和已有的方法，见表1。在表1中，在UKbench上使用N-S得分，在其他数据集中使用mAP(in%)。“-”表示结果未报道。B、SV、MA、QE、WGC表示基准(单个特征)、空间认证[5]、多任务分配[10]、查询扩展[6-7,12]、弱几何一致性[22]。在本文中，使用单一特征的基准是没有使用任何其他技术(如，空间认证(SV)，查询扩充(QE),多重任务分配(MA)或者弱几何一致性(WGC)等)的组对相似性的初始检索结果。文献[16]、文献[17]使用了多重特征提升检索性能。与文献[16]、文献[17]相比较，本文仅仅使用了相似性得分，但融合算法极大地提高了基础性能。

表1 与目前方法的比较

在表1中，BOW在不同数据集间的所有基准中获得了最佳的检索性能，本文的多特征融合算法提高了所有数据集的检索性能，并且优于其他算法。在Holidays和UKbench数据集中，得到了88.3%mAP和3.86N-S 得分。与BOW算法相比，本文的融合算法使用简单的概率模型，将结果在Holidays上提升了14.4%、在UKbench上提升了10.3%。文献[16]也是基于图形融合的，在Holidays提升了9.2%(77.5%～84.6%)，在UKbench上提升了6.5%(3.54～3.77)。文献[17]分别提升了9.6%(73.8%～80.9%)和5.4%(3.42～3.6)。与其他基于单一特征的具有复杂处理过程的方法相比，本文的融合方法仅取决于相似性得分计算查询特定权重并执行扩散过程，利用更可靠的图像之间的关系信息，从而产生更好的检索结果。

在Oxford5k和Paris6k数据集中，由于视点变化大、背景混乱、ROI受限约束区域，颜色特征仅仅达到8.5% mAP和8.4%mAP。此外，VLAD和GIST性能也下降。与文献[16]不同，本文并没有删除劣势特征，无偏见的包含了融合中的所有特征。本文的融合大大提升了检索性能。实验揭示了本文的融合是鲁棒的，并没有被单一劣势特征(如颜色特征)所恶化。在Oxford5k上提升了最佳基准 (BOW)13.1%，达到了76.2%mAP，性能优于文献[17]。在Paris6k上，本文的融合将mAP从69.3%提升至83.3%，并没有使用空间认证、查询扩展和其他技术，相对提升了20.1%。在Oxford5k与Paris6k上，单一特征并不能够较好地区分不同的图像和多重特征。重排结果如图2所示。

图2 本文融合方法在Holidays数据集上检索图像的实例

图2是由4个特征和本文融合方法在Holidays数据集上检索图像的例子，最左边的图片是查询对象。如果检索到的图像与查询具有较高相似性分数，则排名靠前，具有黑边虚线框的图像是正确的匹配。

4 讨论与分析

4.1 评估组件

首先评估本文方法的各个组件的重要性。添加或删除组件并测量精度变化。使用多重特征的原始亲和力矩阵，可以通过选择所有基准中最大mAP来测量精度，表示为B。融合方法标记等量权重和特定查询权重分别为EW和QW，这些结果直接从没有扩散的组合亲和矩阵中推断。EW和QW方法使用所有的数据集图像。使用短列表的两个变体表示为SL+QW和SL+EW。本文的整体框架标记为SL+QW+DP，而使用EW和SL扩散的变体表示为SL+EW+DP。在测试数据集中的比较如表2所示。

表2 本文方法中不同变量的检索性能

续表2

QW和DP都提升了性能，同时使用适当的SL也提高了精度。具体来说，在大多数情况下，QW的结果比EW更好，显示了从相似性得分统计得出的概率模型的有效性。并且，如果要查询大量的相关图像(Oxford5k和Paris6K)，需要在短列表中包含更多图像以获得良好的结果；否则性能会下降到最佳基准以下，因为许多相似的图像会从融合图中排除。相比之下，当只有几个相似的图像被检索时，一个小的短列表就足够了。因此，可以控制短列表的长度以实现计算复杂度与准确度的平衡。

4.2 评估参数

本文方法具有几个参数需要设置：短列表L的长度，易处理图中最近邻居数K和用于将欧氏距离转换为VLAD，GIST和颜色特征的相似性得分的σ，为了评估本文方法对这些参数的敏感性，本文每次改变一个参数进行实验。关于不同L的检索结果如表2所示，图3(a)、图3(b)、图3(c)分别表示扩散过程载VLAD、GIST、颜色特征下不同σ取值的性能。图3(d)表示扩散过程中K-NN图中不同K值的性能图。

图3 评估参数性能

在表2中，UKbench的N-S得分，其他数据集的mAP(%)。只要这些参数在一个合理的范围内，本文的方法是鲁棒的、对这些参数并不敏感。

4.3 评估特征组合

本节使用不同的特征组合进行实验，以进一步证明本文融合算法的有效性。B、V、G、C分别代表BOW、VLAD、GIST、颜色特征。图4(a)-(d)分别表示Holidays、Ukbench、Oxford5k、Paris6k不同K值下不同特征组合的性能。在Holidays、UKbench、Oxford5k和Paris6k数据集中，VLAD+GIST+颜色特征的最佳效果分别为52.4%、2.91%、30.5%、40.3%。在大多数情况下，所有4个特征的融合组合都能获得最佳效果，这些数据验证了本文融合算法的有效性，并且不容易受到较差特征(指颜色特征)的影响。本文的融合并不需要对需要融合的特征的数量或者类型进行任何限制。

图4 评估特征性能

5 结 语

本文将多特征融合与扩散引入了图像重排算法用于图像检索。利用图像之间的组对相似性得分来推断其间的关系。基于单一特征的初始排序被描述为一个易处理图，边的权重是相似性得分。通过混合马尔科夫模型将易处理图融合，利用相似性得分统计的概率模型计算特定查询权重。将扩散应用于融合图以减少噪声。本文的方法显著并且持续地提升了基准性能，对参数的变化也是鲁棒的。

下一步的工作是减少人工标注，进一步研究基于子模型目标函数的完全无监督的重排算法，可以通过贪心算法进行有效的优化，基于此，研究一个更明确的有针对性的应用程序。

参考文献

[1] 周晔,张军平.基于多尺度深度学习的商品图像检索[J].计算机研究与发展,2016 54(8):1824-1832.

[2] Sivic J, Zisserman A. Video Google: A Text Retrieval Approach to Object Matching in Videos[C]// IEEE International Conference on Computer Vision. IEEE Computer Society, 2003:1470.

[3] Qin D, Wengert C, Gool L V. Query Adaptive Similarity for Large Scale Object Retrieval[C]// IEEE Conference on Computer Vision and Pattern Recognition. IEEE Computer Society, 2013:1610-1617.

[4] Douze M, Sandhawalia H, Amsaleg L, et al. Evaluation of GIST descriptors for web-scale image search[C]// ACM International Conference on Image and Video Retrieval. 2009:1-8.

[5] Philbin J, Chum O, Isard M, et al. Object retrieval with large vocabularies and fast spatial matching[C]// Computer Vision and Pattern Recognition, 2007. CVPR’07. IEEE Conference on. IEEE, 2007:1-8.

[6] Chum O, Mikulik A, Perdoch M, et al. Total recall II: Query expansion revisited[C]// Computer Vision and Pattern Recognition. IEEE, 2011:889-896.

[7] Chum O, Philbin J, Sivic J, et al. Total Recall: Automatic Query Expansion with a Generative Feature Model for Object Retrieval[C]// IEEE, International Conference on Computer Vision. IEEE, 2007:1-8.

[8] Nister D, Stewenius H. Robust Scalable Recognition with a Vocabulary Tree[J]. Proc Cvpr, 2006, 2(10):2161-2168.

[9] Jégou H, Douze M, Schmid C, et al. Aggregating local descriptors into a compact image representation[C]// Computer Vision and Pattern Recognition. IEEE, 2010:3304-3311.

[10] Philbin J, Chum O, Isard M, et al. Lost in quantization: Improving particular object retrieval in large scale image databases[C]// 2008 IEEE Conference on Computer Vision and Pattern Recognition. 2008:1-8.

[11] Jegou H, Douze M, Schmid C. On the burstiness of visual elements[C]// Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009:1169-1176.

[13] Jégou H, Perronnin F, Douze M, et al. Aggregating local image descriptors into compact codes[J]. IEEE Trans Pattern Anal Mach Intell, 2012, 34(9):1704-1716.

[14] Tolias G, Avrithis Y, Jégou H. To Aggregate or Not to aggregate: Selective Match Kernels for Image Search[C]// IEEE International Conference on Computer Vision. IEEE, 2014:1401-1408.

[15] Mikulík A, Perdoch M, Chum O, et al. Learning a Fine Vocabulary[M]// Computer Vision - ECCV 2010. Springer Berlin Heidelberg, 2010:1-14.

[16] Zhang S, Yang M, Cour T, et al. Query specific fusion for image retrieval[C]// European Conference on Computer Vision. Springer-Verlag, 2012:660-673.

[17] Zhang S, Yang M, Wang X, et al. Semantic-Aware Co-indexing for Image Retrieval[C]// IEEE International Conference on Computer Vision. IEEE Computer Society, 2013:1673-1680.

[18] Yang Y, Song J, Huang Z, et al. Multi-Feature Fusion via Hierarchical Regression for Multimedia Analysis[J]. IEEE Transactions on Multimedia, 2013, 15(3):572-581.

[19] Ye Guangnan, Liu Dong, Jhuo I-Hong, et al. Robust late fusion with rank minimization[C]// Computer Vision and Pattern Recognition. IEEE, 2012:3021-3028.

[20] Qin D, Gammeter S, Bossard L, et al. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors[C]// Computer Vision and Pattern Recognition. IEEE, 2011:777-784.

[21] Yang X, Koknar-Tezel S, Latecki L J. Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval[C]// Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009:357-364.

[22] Jegou H, Douze M, Schmid C. Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search[M]// Computer Vision-ECCV 2008.OAI,2008:304-317.