一种贝叶斯和支持向量机相结合的相关反馈策略

陈长江, 侯 进

（西南交通大学信息科学与技术学院,四川成都 610031）

0 引言

近年来,基于内容的图像检索已成为较为热门的研究课题。传统的图像检索系统自动提取图像特征,通过比较图像间的相似度,从图像库中返回相似度大的图像。在这种系统中,最大的问题是计算机自动提取的低层特征和用户理解间存在“语义鸿沟”,使检索结果不尽人意。于是,相关反馈技术被引入到基于内容的图像检索领域。

相关反馈方法的基本思路是在检索过程中,允许用户对检索结果进行评价和标记,找出结果中哪些与查询图像相关,哪些不相关,然后将用户标记的相关信息,作为训练样本反馈给系统进行学习,指导下一轮检索,从而使检索结果更符合用户的需要。相关反馈有多种算法,如基于查询向量转移的方法[1],基于权重调整的方法[2],基于机器学习的方法[3-5]等。

相关反馈建立在图像检索[6]结果基础上,是用户和系统反复交互的过程,提高反馈的效率,减少用户与系统的交互次数始终是相关反馈研究的关键问题。Bayesian反馈算法多数会受到小样本问题和训练样本不对称问题的制约,如何克服这个问题对提高反馈效果至关重要。针对以上问题,在传统的反馈算法基础上提出结合贝叶斯[7-8]和SVM（SVM+Bayesian,S+B）的反馈策略。该算法用贝叶斯分类器对图像库进行分类,聚集相关的图像,去除无关的图像,实现图像库的压缩,然后用SVM分类器对缩小后的图像库反馈,从而缩小算法的搜索范围,减少反馈次数,提高了反馈效果。对小样本问题和训练样本不对称问题也有帮助。首先,虽然检索开始时贝叶斯分类器的训练样本有限,但随着反馈次数增加,用户标注的样本数增加,训练样本逐渐累加,样本个数逐渐增多,贝叶斯分类器效果会变好;其次,算法中的贝叶斯分类器的参数不是固定的,它随着样本数的改变更新自身的参数,所以每次反馈用的贝叶斯分类器都不同,这样构造的贝叶斯分类器会更合理,效果会更好;最后,反馈过程中用户标注的是前K幅图像,只标注相关图像,剩下的为不相关图像,而不是把图像库中所有未标注的图像作为不相关图像,所以基本不可能产生训练样本不对称问题。

1 多维正态分布条件下的贝叶斯分布

1.1 多维正态分布

高斯分布模型是一种通用的概率分布模型。这种模型运算简单,而且现实世界的很多事件和高斯分布有着极大的相似性。假定 n维空间Rn中的向量x满足高斯分布,则x的概率密度函数为:

其中,x=（x1,x2,…,xd）T为d维特征向量,u=（u1,u2,…,ud）T为d维均值向量,∑为 d×d维协方差矩阵,∑-1为∑的逆矩阵,为∑的行列式。

1.2 多维正态分布条件下的贝叶斯判别原理

贝叶斯分类以贝叶斯定理为基础,通过训练大量样本来估算后验概率。贝叶斯分类器把样本划分到后验概率大的一类中,因此可以定义 ωi类的判别函数为:

因为在同一模式识别问题中,对于不同的类,贝叶斯公式中全概率都是相同的,所以各类的判别函数也可以定义为:

判别函数中,先验概率P（ωi）是一个与特征向量无关的常量,类条件概率密度P（x|ωi）则满足一定的概率分布,假定 P（x|ωi）符合 d维正态分布,则判别函数为:

该函数含指数,不方便计算,考虑到对数函数是单调递增函数,对它取对数,去掉与类无关的项得到:

得到判别函数后,就有了分类判别的依据,就能通过比较两类判别函数的大小对数据进行分类。

2 支持向量机原理

支持向量机是一种基于统计学习理论的机器学习方法,它建立在VC维和结构风险最小化理论上,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳的折中,从而期望获得更好的泛化能力。

作为一种可训练的机器学习方法,假定训练数据为{（x1,y1）,（x2,y2）,…,（xl,yl）},x∈Rn,y∈{-1,1},其中y是类别标号。假定n维空间下的线性判别函数为g（x）=ω.x+b,它对应的分类超平面为 ω.x+b=0。将g（x）归一化,让两类的样本 x满足|g（x）|≥1,通过它得到分类间隔2/‖ω‖。分类间隔最大等价于‖ω‖或‖ω‖2最小,所以寻求最优超平面的问题转化为解决下面目标函数的二次规划问题:

对于线性不可分情况,SVM引入松弛变量ξ和惩罚因子C,目标函数变成:

通过核函数K（x,y）=（φ（x）,φ（y））的非线性转换,SVM把输入空间转换到高维空间,在高维空间中求最优分类面,得到高维空间的分类函数为:

因此,SVM通过选择适当的核函数K,可以很好的应用于非线性分类。

3 结合贝叶斯和SVM的相关反馈算法

3.1 多维正态分布条件下的贝叶斯分类

根据多维正态分布条件下的贝叶斯分布,可以容易实现贝叶斯分类。由多维正态分布条件下贝叶斯分布的判别函数公式（5）,类i的判别函数有3个参数:均值ui,协方差矩阵∑i和先验概率P（ωi）。相关反馈过程中,假定用户标注的相关图像和不相关图像为两类。每次反馈,根据标注得到的两个图像类,分别更新两个类的贝叶斯分类器参数,就可不断提高两个类分类器的性能。以下为两个贝叶斯分类器的3个参数更新方程:

其中,Pr与Pn分别为相关图像类和不相关图像类的先验概率,Nr与Nn分别为标注的相关图像和不相关图像个数,ur与un分别为两个类的均值,I+与I-分别代表相关图像和不相关图像,∑r与∑n分别为两个类的协方差矩阵。

由公式（10）分别更新两个类的分类器参数之后,就可以对图像库进行分类判别了。通过分类,把图像库中属于相关图像类的图像保存起来,构成相关图像库,把不属于相关图像库的图像排除掉。

3.2 基于SVM的分类

SVM分类依据支持向量机原理。由非线性支持向量机的分类函数公式（9）,求图像 x到分类超平面的距离需要知道核函数K（xi,x）,拉格朗日乘子 αi和偏移因子b*。核函数选择径向基核函数,拉格朗日乘子和偏移因子可通过求目标函数 φ（ω）=‖ω‖2/2的二次规划问题求出,这样就有了非线性条件下SVM的分类函数。

每次反馈过程中,用户标注的相关图像和不相关图像都会进行更新变化,根据每次反馈更新后的结果训练SVM,得到SVM 的非线性分类器。然后,用SVM分类器对贝叶斯分类得到的相关图像库进行分类,并返回最终结果。

3.3 贝叶斯与SVM相结合的反馈技术

结合以上两种分类算法,提出一种贝叶斯和SVM相结合的反馈算法。首先,每次反馈标注的结果跟前面几次反馈的标注结果合并,得到相关图像类和不相关图像类;其次,利用正态分布下的贝叶斯建立相关图像类和不相关图像类的分类器,同时用标注结果训练SVM得到SVM分类器;最后,用两个贝叶斯分类器对图像库进行分类,得到属于相关图像类的图像集合,也就是相关图像库,然后用SVM分类器对相关图像库进行分类,并返回最终结果。其流程如图1所示,具体的算法流程如下:

（1）根据用户的需要,选择前K幅图像作为检索结果返回给用户。用户对K幅图像进行标注,点击当前相关的图像I+1,剩下的为不相关的图像I-1,分别更新相关图像类 I+和不相关图像类 I-。相关图像类:I+=（I+∪I+1）-I-,不相关图像类:I-=（I-∪I-1）-I+。

（2）根据更新得到的相关图像类I+和不相关图像类I-,利用公式（10）分别更新相关图像类和不相关图像类的贝叶斯分类器参数,同时训练SVM,得到SVM分类器。

图1 反馈流程图

（3）经过每次更新参数后,相关图像类和不相关图像类就有了各自的分类判别函数gr（x）、gn（x）,把图像库中的图像代入两个判别函数进行判定,如果gr（x）＞gn（x）,就把 x归属于相关图像库。这样,经过贝叶斯判别后,就得到了本次反馈的相关图像库U+。

（4）用第二步得到的SVM分类器对相关图像库U+中的图像进行反馈。在相关图像库中,每一幅图像Ii对应着相应的分数score（Ii）=f（xi）,分数越大,与查询图像的相似度就越大。根据分数的大小进行排序,把分数最大的前K幅图像反馈给用户。

（5）保存检索结果,如果用户感到满意,反馈的过程就可以停止了。否则,用户再提交标注图像,转到第一步,然后再次反馈,直到反馈结果满足用户需要。

4 实验分析

从Corel图像库中选取30个语义类,每类选取30幅图像,一共有900幅图像,包括鸟、海浪、猴子等。系统界面如图2所示,界面中左边部分用来标注图像,右边用来显示反馈结果。颜色特征通过计算HSV颜色直方图来提取每个区域的主色,也就是HSV均值,这个特征是1×3维的,纹理特征利用曲波系数即尺度为5,方向为4的曲波特征,它是1×84维的特征。实验中的SVM 基于Libsvm,采用径向基核函数K（x,y）=exp（-λ‖x-y‖2）,λ＞0,其中 λ=0.1,SVM算法中的惩罚系数C=100,参数λ和C是经过多次试验之后选取的最优值。

图2 系统界面

假定用户查询的是每一个语义类的图像,考虑到用户的耐心和贪婪性,假定反馈次数为3次,用户每次反馈标识的图像数目为界面中的前5页,即45幅图像。使用图像检索领域通用的评价标准,即平均查准率评价系统的性能。实验中选取bird、mountain、monkey、bonsai、wave、flower、bear作为它们对应类的检索关键词,然后分别统计这7个关键词每次反馈过程中前27幅图像和前36幅图像中相关图像个数,分别求出各个关键词的前27幅图像和前36幅图像的反馈精度,最终求出通过3次反馈后的平均反馈精度。反馈精度公式定义为:P=a/b,其中a为前K幅图像中相关图像个数,b为前K幅图像的个数。

图3和图4分别是实验中选取的7个关键词的前27幅图像和前36幅图像的平均查准率。利用文中提出的贝叶斯和SVM相结合的反馈算法跟单独用传统SVM或贝叶斯反馈算法进行比较,分别计算3种算法通过1至3次反馈后每次反馈的平均反馈精度,比较结果如图中反馈精度曲线所示。

图3和图4表明Top27和Top36的平均查全率,从图中曲线可以看出,单独用SVM算法的平均反馈精度要比用贝叶斯算法的效果好;利用SVM和贝叶斯结合的算法要比单独使用两种算法的效果好;结合SVM和贝叶斯的算法在3次反馈的时候已经达到了比较高的反馈精度,而单独使用两种算法的时候反馈精度要差。

图3 Top27的平均查全率

图4 Top36的平均查全率

为了进一步说明贝叶斯结合SVM算法的有效性,将该算法同基于动态学习的SVM算法[9]（Active SVM,S+A）进行比较,并在同一数据集上做反馈结果测试。图5和图6是两种算法在前27和前36幅图像中平均查全率的比较结果。

图6 Top36的平均查全率

图5和图6表明S+B和S+A通过3次反馈后的平均查全率,通过图中曲线看出,无论是在前27幅图像还是前36幅图像中,贝叶斯和SVM相结合的反馈算法的平均反馈精度都好于基于动态学习的SVM反馈算法,从而进一步证明该算法的有效性。

从以上实验结果可以看出,提出的结合贝叶斯和SVM的反馈方法,先用贝叶斯对图像库进行分类,去除了很多不相关图像,而且得到属于相关图像类的相关图像库。这让用SVM进行反馈时,仅仅针对得到的相关图像库,而不是整个图像库,大大缩小算法搜索范围,减少了反馈次数,提高了反馈的效率和效果。

5 结束语

相关反馈在基于内容的图像检索中有重要意义,减少交互的次数,提高反馈的精度是相关反馈必须解决的问题。文中提出一种结合贝叶斯和SVM的反馈算法,来减少反馈次数,提高反馈效果。该算法通过多维正态分布条件下的贝叶斯分类,对图像库进行压缩,让SVM分类针对经过贝叶斯压缩后的相关图像库,从而在减少反馈次数的基础上,提高了反馈精度。如何进一步优化贝叶斯分类器的性能,是以后需要解决的问题。

[1] Y Rui,T S Huang,S Mehrotra.Content-based image retrieval with relevance feedback in mars[C].Proceedings of International Conference on Image Processing,USA,1997.

[2] Y Rui,T S Huang,S Mehrotra.Relevance feedback:a power tool for interactive content-based image retrieval[J].Circuits and Systems for Video Technology,1998,8（5）:56-59.

[3] JI Ai-bing,NIU Qi-ming,HA Ming-hu.Support vector machine learning from positive and unlabeled samples[C].Proceedings of International Conference on Intelligent System andKnowledge Engineering,China,2008.

[4] WAND Xue-jun,YANG Ling-ling.Yang.Application of SVM relevance feedback algorithms in image retrieval[C].Proceedings of International Conference on Information Science andEngineering,China,2008.

[5] YU Xia,HUANG Xiao-sha.Image retrieval combined color,texture,shape and SVM relevant feedback[J].Research of the Application of Computers,2007,11（11）:292-294.

[6] Hou Jin,Zhang Deng-sheng,Chen Zeng.Web image search by automatic image annotation and translation[C].Proceedings of International Conference on Signals and Image Processing,Brazil,2010.

[7] 苏中,张宏江,马少平.基于贝叶斯分类器的图像检索系统相关反馈算法[J].软件学报,2002,13（10）:2001-2006.

[8] SU Zhong,ZHANG Hong-jiang.Relevance feedback in content-based image retrieval:bayesian framework,feature subspaces,and progressive learning[J].Image Process,2003,12（8）:924-937.

[9] S Tong,E Chang.Support vector machine active learning for image retrieval[C].Proceedings of the 9th ACM International Conference on Multimedia,2001.