基于相关反馈的一种加权距离法

赵文霞，周海英

（中北大学 电子与计算机科学技术学院，太原 030051）

0 引言

现有的特征提取算法中没有一个能很好地将视觉上相似的图像映射到最近的位置。在图像检索结果中常见一些现象：有时一些图像是与待查询的图像很大程度上是不相关的，仅仅因为这些图像在特征空间中与待查询的图像是接近的就被检索出来。因此，需要采用改进权值的方法来改善检索结果。

底层特征也要表示出高层概念的相似度和人的视觉的主观性。为了让用户更多地参与检索过程，有些检索系统已经允许用户衡量这些底层特征。由于普通用户对专家设计的底层特征并不是很了解，所以通常来说这种方法是不可取的。

最近，修改权值的方法已经在相关反馈技术中得到了广泛的应用。其主要思想是将用户考虑在检索循环中。首先把用户输入的原始查询图像在数据库中进行初始搜索，再在初始搜索结果的基础上，用户根据自己的实际需要把图像分为相关图像和不相关图像。这样就根据交互检索把反馈的信息参与到数据库的搜索中。

在图像数据库检索中,相关反馈方法常用一些信息检索文献中已成型的思想。一种常用的思想是向量空间模型，原始特征向量和由用户标记的相关或不相关图像的特征向量的加权线性组合构成了一个新的查询特征向量。其他的方法包括使用关键词、创建概率用户模型、修改距离测量、重组检索结果、特征密度估计和交互权值更新等。

检索算法依赖于直接从图像中计算出的特征。但是我们仅想使用用户反馈回来的信息而不是使用人工关键词或者启发式的假设,而且我们也不能假设用户的一切信息要求,更不能假设用户要搜索图像的分类,相关或不相关。因此, 在K-近邻搜索中根据用户的反馈得到一些特征，我们赋予这些特征权值。其特征值与整个数据库和用户选择的相关图像的标准偏差的比率既适用于相互独立的权值之间，也适用于增量更新的权值之间。

本文对一个含有1000幅图像的数据库进行了实验，其检索性能也采用平均查准率进行评价。我们还定义了一个新的测量值“增进”来测量其性能。

1 加权距离法

1.1 定义

首先，给出了文中用到的一些定义。

K：交互搜索的次数。

Q：一个特征向量中特征的个数。

Rk={第k次搜索后的检索集合}，k=0，…，K，其中R0表示整个数据库。

在检索过程中，通过计算特征空间中特征向量的距离来得出图像之间的相似度。给定特征向量x和y，加权向量w，用加权后的L1距离：

和加权后的 L2距离：

1.2 算法目的

从模式识别的角度来看，如果描述图像内容的一个特征很好，那么在数据库的所有图像中它的方差可能很大但是在所有相关的图像中它的方差应该很小。所有这种特征中也许并不是每一个都是相互独立的，但是当与其他特征结合时就会表现出这个特征是个好的特征,能够很好地描述图像的内容。

给出这些定义之后，我们就可以用wkj=σ0j/σkrel,j,这里σ0j=std（F0j），σkrel,j=std（Fkrel,j），作为第k+1次迭代中第j个特征的权值。一方面,对于给定的一幅图像，对于整个数据库来说它的相关图像集只是一个很小的集合；另一方面，其他的图像就会归类为不相关的图像。这里我们只用相关的图像集，因为由用户选择的相关和不相关的反馈图像都是个较小的集合,这样可能就更好地概括了前面的检索情况。

对于σ0j和σkrel,j，表1中列出了4种可能出现的情况。

表1 权值的选择

由表1可以看到表中越向上面移动的值更接近其目的。

(a)当σ0j越大，σkrel,j小时，wkj就会很大。这也就意味着数据库中图像的特征有多种集合，但是这些相关图像的特征值却是相似的。这也是一种预期情况而且还表明了在区分某个特定的相关图像集时这个特征是非常有效的，所以就要赋予这个有效的特征更大的权重。

(b)当σ0j和σkrel,j都大时，wkj接近于1。这表明数据库中的这个特征可能也是个很好的特征，但是对于某些特定的相关图像集来说它就不一定是有效的，因而也就没

必要赋予这个特征特殊的权重。

(c)当σ0j和σkrel,j都小时，wkj也会接近于1。这与当σ0j和σkrel,j都大时wkj接近于1的情况类似，但比上面的情形略微差一些。对于图像数据库来说,这个特征一般是没有多大作用的，对于相关图像集也是没有多大作用的,所以也就不用重视这个图像特征。

(d)当σ0j小，σkrel,j大时，wkj就会很小。这种情况是4种可能情况中最差的一种。这个特征一般来说对图像检索是没有作用的,甚至会导致增大了相关图像之间的距离。因此要赋予这个特征很小的权重进而可以忽略掉这个特征的作用。

在理想的检索中，可以证明这四种情况中所有结果种类的权重与预期情况都是一致的。

1.3 交互检索

下面给出了基于相关反馈的加权距离法进行图像检索的算法：

(1)统一初始化所有权值:w0j=1/Q，j=1，…，Q。并且计算σ0j，j=1，…，Q。

(2)for k=1，…，K，

（a）用wk-1j搜索数据库，得到Rk。

（b）当Rkrel，得到用户的反馈信息。

（c）计算σkrel,j，j=1，…，Q。

(3)用wKj进行最后搜索，j=1，…，Q。

其中,检索算法过程2(c)中的σkrel,j的计算有两种方法：

特征权重是相互独立地更新：在每次迭代过程中只用迭代得检索集合相互独立地估计标准偏差。例如：

这里E（Fk

rel，j）2和E（（Fkrel，j）2）分别是样本的一阶和二阶期望。

特征权重是增量更新：我们假设随着迭代过程用户对于相似的概念保持不变，在之后的迭代过程中也保持不变。这样，在每次迭代过程中增量更新的标准偏差的计算为：

当Fkrel中所有值都相同时，所有的图像对于同一个特征都有相同的特征值，就赋予wkj一个大的权重常数。

2 实验和结果

2.1 数据库大小

定义了一个有1000（256×384）幅图像的数据库，其中包括自然景观图像和人物图像等。选取了340幅图像构成7类基本图像：海滨风光、恐龙、建筑物、花、冰川雪山、马和人。文献[1]中已经采用文本描述来表示图像。第一种特征集合是线角概率统计，主要使用了空间关系和线性属性；第二种特征集合是特定空间关系中像素的差异共生统计。

2.2 检索性能

本文采用平均查准率来测量算法的检索性能，查准率是指检索出的图像是相关图像的百分比。图1中给出了一些基本图像检索结果的平均差准率。每次迭代搜索引擎都在数据库中进行一次新的检索，而且每次检索12幅图像。L1和L2距离也都可以用在相互独立地更新。

表2中总结出了检索结果。可以看到用L2距离可以得到更高的平均查准率。我们用了5次迭代，每次迭代后平均查准率最大改善了19%。这种预期情况也证明了其快速收敛性。表2中还给出了每次迭代后较前一次迭代改善情况。

表2 检索12幅图像的平均查准率

如果每次迭代都要搜索整个数据库,一般很少能再搜索到其他的相关图像,并且原始查询后的检索集合中的图像也会以一种新的图像集显示,而不是必须进行反馈或者更多次的搜索才能显示。另一种方法是对于某个特定的图像集，相关反馈性能的好坏可以根据“增进值”来比较迭代搜索的性能和最初搜索的性能。在得到反馈信息之后，搜索引擎就会对数据库进行一次新的搜索，但是不再未反馈前 第一次反馈 第二次反馈‘－’:L1相互独立更新; ‘－－’: L2相互独立更新; ‘…’: L1未反馈; ‘﹎’L2未反馈考虑已经在前面迭代过程中检索到的所有图像。因此，每次迭代只需检索一个新的12幅图像的集合。其性能可以用原始搜索的检索集合中的另外12幅图像的集合（用户界面中显示的下一页）进行比较。假如检索到的图像有n幅，定义“Progress”是两次准确率的比，

图1 前两次的平均查准率

当Progress大于1时，表明反馈算法有效而且收敛的很快。表3分别给出了未反馈前、第一次反馈和第二次反馈的平均Progress值。

表3 检索了12、24、36幅图像后的平均Progress

由表3可以看到距离增量更新比相互独立更新的效果更好。较反馈前，反馈后的Progress最大改善了5.3%。

3 结论

文中给出了一种加权距离法，其权值就是整个数据库和用户选择后的相关图像的特征值的标准方差之比。论文讨论了相互独立的权值更新，在每次迭代中其权值是相互独立的，仅使用本次迭代的反馈信息进行评估。还讨论了增量权值更新，在每次迭代中其权值是增量更新的，要使用本次迭代和前次迭代的反馈信息进行评估。

对一个标准数据库用平均查准率和Progress值评价检索性能，而且每次迭代后平均性能都提高了19%，而且收敛速度也很快。

文中还有一个问题需要进行研究，就是研究权值更新方法的标准方差的其他作用。比如在数据库中也考虑不相关图像的反馈信息，检索结果可能会更好。

[1] S.Aksory and R.M.Haralick.Textural fetures for image database retrieval[J].In Processing of IEEE Workshop on Content-Based Access of Image and Video Libraries,in conjunction with CPVR’98,Santa Barbara,CA,1998:45-49.

[2] P.Wu and B.S.Manjunath.Adaptive nearest neighbor search for Relevance Feedback in Large Image Databases[J]. Department of Electrical and Computer Engineering University of California,Santa Barbara,CA 93106-9560.

[3] 黄德才,胡嘉,郑月锋.交互式图像检索中相关反馈进展研究[J].计算机应用研究，2005,22(9):15-18.

[4] 李庆先.基于内容的图像检索相关反馈算法的改进[J].计算技术与自动化，2002,26(2):38-41.

[5] 刘琳,李仁发,李仲生,刘钰峰.基于内容图像检索中的相关反馈技术研究[J].计算机应用研究,2009,26(7):27-31.

[6] 李云.特征选择算法及其在基于内容图像检索中的应用研究[D].重庆:重庆大学,2005.

[7] 赖欣.基于相关反馈和综合特征的图像内容检索系统研究和实现[D].成都：电子科技大学，2008.

[8] 张洁婧,侯晓慧,刘志镜.基于相关反馈特证权的综合CBIR系统设计[J].计算机应用研究，2007,24(12):365-369.

[9] 韦娜,王涛.一种具有相关反馈的图像检索方法[J].计算机应用与软件，2007,24(12):168-170.

[10] 姜楠楠,齐敏,郝重阳.一种基于SVM的相关反馈图像检索算法[J].计算机仿真，2009,26(1)：219-221.