收稿日期 : 2008- 05- 22; 修回日期 : 2008- 07 - 11 基金项目 : 国家自然科学基金资助项目 ( 60773197 ) ; 浙江省自然 科学基金资助项目
( Y107750)
作者简介 : 文春勇 ( 1978- ) , 男 , 江西宜春人 , 硕士研究生 , 主要研究方向为模式识别与图像处理 ( chriswen_2006 @ 126. com) ; 朱信忠 ( 1975- ) ,
男 , 江苏沛县人 , 副教授 , 硕士 , 主要研究方向为模式识别、制造业信息化 ; 徐慧英 ( 1976 - ) , 女 , 浙江永康人 , 讲师 , 硕士 , 主要研究方向为模式识别与
图像处理 ; 赵建民 ( 1951- ) , 男 , 上海人 , 教授 , 硕导 , 硕士 , 主要研究方向为人工智能、模式识别 .
基于最小风险的贝叶斯决策理论相关反馈方法 *
文春勇, 朱信忠, 徐慧英, 赵建民
( 浙江师范大学 数理与信息工程学院 , 浙江 金华 321004)
摘 要: 在对之前的相关反馈技术的问题和不足进行总结的基础上, 提出一种基于最小风险的贝叶斯决策理论
相关反馈方法 , 通过一种自适应机制产生记忆, 同时应用最小风险来使用户获得满意的检索结果。实验结果表
明该方法准确率高、响应速度快。
关键词: 贝叶斯决策理论 ; 适应机制 ; 最小风险
中图分类号: TP391 文献标志码: A 文章编号: 1001- 3695( 2009) 03- 1171- 03
Bayesian decision theory relevance feedback method based on minimum risk
WEN Chun-yong, ZHU Xin-zhong, XU Hui-ying, ZHAO Jian-min
( College Mathematics-Physical & Information Engineering, Zhejiang Normal University, Jinhua Zhejiang 321004, China)
Abstract: Based on the summing up of some problems and deficiencies of relevance feedback the day before, this paper pro-
posed Bayesian decision theory relevance feedback method based on minimum risk , in which producing memory through a a-
daptive mechanism, and applying minimum risk to satisfy users with the retrieval results. Experimental result shows that it is a
method with high accuracy and fast response speed.
Key words: Bayesian decision theory; adaptive mechanism; minimum risk
0 引言
近年来 , 基于内容的图像检索已经成为一个研究热点 , 并
成为数字图书馆等重大研究项目中的关键技术。而与之对应
的相关反馈模型和框架也相继被提出 , 如 Rui 等人 [ 1] 通过采用
内容相关的图像检索系统 , 阐述了一个最优化问题 , 增加了基
于使用者的评价先验知识及找回图像的低层次特征权重。在
多媒体方面, 使用相关反馈的例子有 PicHunter[ 2] 、MindRea-
der[ 3] 和 Lee 等人 [ 4] 提出的框架; 对于基于内容的图像检索系
统的相关反馈方法 , 有文献[ 5 ～7] 提出的贝叶斯相关反馈以
及文献[ 8] 中最新提出的动态相似度度量反馈策略 ; 文献[ 9]
中详细地描述了当前相关反馈的几种常用的检索模型 , 即基于
向量距离度量、基于概率模型、基于机器学习。相关反馈方法
可以把用户也作为检索中的一部分 , 能够得到更使用户满意的
检索结果 , 但是相关反馈还有很多问题需要解决: a) 多少次反
馈是必需的 , 而多少次反馈将是多余的。由于没有一个对图像
检索有效的量化评判标准 , 现在对检索结果的评判还是基于人
们自己的主观感觉 , 在检索中并不能判断多少次相关反馈对用
户而言是足够的。b) 大多数相关反馈技术都有一个缺点 , 就是
反馈过程没有记忆 ( memory) , 导致用户过去的反馈操作并不
能帮助未来的查询 , 因此 , 检索的性能并不能维持很久。
本文针对当前相关反馈面临的两大问题 , 提出一种在最小
风险基础上的反馈方法 , 解决反馈中的两大难题。最后通过实
验证明本文提出的方法能很好地提高准确率 , 满足用户对系统
查询结果的要求。同时在图像数据库小的前提下 , 响应速度
快, 适合于实时系统。
1 贝叶斯决策理论
贝叶斯决策理论 [ 10 ] 为不确定性理论提供了坚实的理论基
础, 它可以描述为 : 设观察数据为随机分布的样本集合 X, 其中
每个样本表示为 x。令 y∈Y表示一个类别。每个样本都可能
被分类到某个类别中 , 概率 P( x |y) 表示样本 x 属于类别 y 的
条件概率。令 A = { a1 , a2 , ⋯, an } 表示一组可能的决策行为
( 不同具体应用对决策行为的定义可能不相同) 。根据贝叶斯
决策理论 , 每个决策行为 ai 都有一个损失函数 L( ai , x, y) ( 例
如: 损失函数可以定义为将样本 x 分类到类别 y 损失) , 固定 Y
和 A, 对样本采取决策行为 ai 的风险定义为
R( ai |x) =?L( ai, x, y) P( y |x) dy ( 1 )
贝叶斯决策问题的求解是要发现每个样本的最优决策行
为 ai ( 即风险最小行为) , 进而发现整个策略的全局最优行为
{ ai} 。每个样本的最优行为定义为
a* = arg min R( a|x) ( 2 )
分类可以作为贝叶斯决策理论的一个特殊应用 , 这时决策
行为 A 和分类类别 Y 表示的意义一致 , 行为即表示将样本 x 分
类到类别 y。例如 , 在贝叶斯分类中, 发现风险最小化的决策
行为 a* 等价于将样本分类到后验概率最大的类别中。
2 自适应贝叶斯反馈机制
在基于内容的图像检索中, 如果说两幅图是否相似 , 是指
第 26 卷第 3 期
2009 年 3 月
计 算 机 应 用 研 究
Application Research of Computers
Vol. 26 No. 3
Mar. 2009
它们的特征是否相似。关于特征的相似关系理论通常采用的
是几何模型 , 把图像的特征看做是坐标空间中的点 , 用两点之
间的距离来表示它们的相似程度 , 距离越近越相似 , 距离越远
表明越不相似。大量的研究集中在特征的选择和距离的定义
方面, 如对色彩直方图而言 , 可以采用直方图交、直方图欧式距
离、余弦距离、海明距离、马氏距离 [ 9] 等。当某些特征和相应
的距离度量方法适合某些特定的图库时 , 检索结果会相对好一
些, 但对一般图库而言, 其检索效果会受到影响。本文提出的
自适应反馈机制建立在目前被广泛采用的贝叶斯方法决策理
论的基础上 , 结合了相关反馈图像检索系统的时序特性, 在图
像的相似性度量中嵌入了人的主观性 , 在某种程度上使图像检
索结果与人的主观感知更加接近。
基于内容的相关反馈检索是一个逐步求精的过程。首先
是用户提交查询实例 ( 可能是一幅或者一组图像) , 系统获取
查询实例的特征 , 并结合贝叶斯决策理论, 通过求取类条件概
率和损失函数得到的最小风险值 , 求取类条件概率时加入对上
一次查询的记忆 , 这样每次得到的风险值比上一次要小, 从而
返回给用户的结果也是比较满意的。用户还可以在反馈的交
互中调整最小风险的阈值来获得自己最满意的结果。实质上
图像检索系统也是一个分类问题 , 可以把交互的过程看做是一
个训练过程 , 用户认为比较满意和不满意的图片可以分别当作
相关例训练数据和非相关例训练数据 , 而进一步查询的过程是
一个分类问题。把图像检索问题转换为分类问题是本文用贝
叶斯方法来解决图像检索问题的基本思路。下面给出该思路
的具体描述。
用 Ω±表示根据用户提供的相关训练数据和非相关数据
对样本空间进行的一个划分 ; P( Ω+ ) 和 P( Ω- ) 分别表示相关
例类和非相关例类的先验概率; xj 表示图像 j 的视觉特征;
P( xj |Ω+ ) 是根据相关例训练数据得到的类条件概率密度;
P( xj |Ω
- ) 是根据非相关例训练数据得到的类条件概率密度 ;
P( Ω+ |x j) 表示图像 j属于相关例类的概率。
按照贝叶斯理论 , 可以用下式来表示
P( Ω+ |x j) = [ P ( x j |Ω+ ) P( Ω+ ) ]
/[ P( xj |( Ω+ ) P( Ω+ ) + P( xj |( Ω- ) P( Ω- ) ] ( 3)
由于图像的低层次特征并不能很好地反映图像的语义特
征, 按照上述分类器产生的分类结果并不能完全满足用户的需
求。本文的图像检索系统提供一种自适应的学习功能, 允许用
户对当前分类结果进行评价 , 通过反复学习以提高检索精度。
本文把用户指定的相关例类和非相关例类当做新的训练数据 ,
随着用户 提供的训练数据的变化 , 相应地 , P( Ω+ ) 、P( Ω- ) 和
Ω±均在发生变化。图 1 表示了这一过程。
图 1 表示了在相关反馈图像检索系统中 , 随着用户不断提
供新的相关例类训练数据和非相关例类训练数据 , 相关例类和
非相关例类在不断变化的过程。“+”表示相关例类训练数据
的中心 ; “- ”表示非相关例类训练数据的中心。随着用户的
交互, 相关例类与非相关例类的分界线在不断发生变化。针对
相关反馈图像检索系统的这种动态特性 , 引入查询时刻的概
念, 对式( 3) 进行了修正 , 用 Ω±( t) 表示 t 时刻提供的相关例类
和非相关例类对样本空间进行的一个划分 , P( Ω±( t) ) 用来表
示 t 时刻的 P( Ω±) , 而 t 时刻的后验概率 P( Ω+ |xj) 用 P( Ω
±
( t) |xj) 来表示, P( Ω±( t) |xj) 则表示 t 时刻的类条件概率密
度。式( 3) 经过上述修正后 , 变为如下形式 :
P( Ω+ |xj) = P( x j |Ω
+ ( t) ) P( Ω+ ( t) ) /[ P( xj |Ω
+ ( t) ) P
( Ω+ ( t) ) + P( xj |Ω
- ( t) ) P ( Ω- ( t) ) ] ( 4 )
式( 4) 表示在 t 时刻, 图像 j属于相关例类的概率 , 那么图
像 j属于非相关例类的概率为
P( Ω- ( t) |x j) = 1 - P( Ω+ ( t) |xj) ( 5 )
上面描述了贝叶斯方法应用于相关反馈图像检索中的基
本思路。具体的检索过程可以概括为 : 通过用户提供的相关和
非相关例类训练数据 , 得到相应的类模式 , 对每幅图像计算出
它属于相关例类的概率 P( Ω+ |xj) 。在具体的实现过程中本
文用函数 similarity( ) 来近似类条件概率密度。即计算出相关
例类样本的中心 X + 和非相关例类样本的中心 X - , 对每个 xj
观测它在 t 时刻的类条件概率密度 P( xj |Ω
+ ( t) ) 和 P( xj |Ω
-
( t) ) 。
P( xj |Ω+ ( t) ) = similarity( xj, X + ) ( 6 )
P( xj |Ω
- ( t) ) = similarity( xj, X - ) ( 7 )
其中 similarity( xj, X ±) 表示图像 j与相( 非相) 关例的相似度 ,
取值是 [ 0, 1] ,1 表示两者完全相似 , 0 表示根本不相似。根据
式( 4) 可以计算得 t - 1 时刻图片 j属于相关例类的概率 P( Ω+
( t - 1) |xj) 。显然 , 与相关例训练数据比较相似的图片 , P( Ω+
( t - 1) |xj) 比较大 ; 反之则 P( Ω
+ ( t - 1 ) |xj) 比较小。为了使
检索结果逐步向用户期望的状态发展 , 不断强调有希望的图像
( 离相关例比较近 , 离非相关例比较远的图像) , 分别用 P( Ω+
( t - 1) |xj) 和 P( Ω- ( t - 1) |xj) 代替式( 7) 中的 P( Ω+ ( t) ) 和
P( Ω- ( t) ) , 这就是本文提出的带记忆的自适应贝叶斯机制。
P( Ω+ ( t) |xj) = [ P( xj |Ω
+ ( t) ) P( Ω+ ( t) ) ] /
[ P( xj |Ω+ ( t) ) P( Ω+ ( t - 1 ) |x j) +
P( x j |Ω- ( t) ) PΩ- ( t - 1) |x j) ] ( 8 )
P( Ω- ( t) |xj) = [ P( xj |Ω- ( t) ) P( Ω- ( t) ) ] /
[ P( xj |Ω+ ( t) ) P( Ω+ ( t - 1 ) |x j) +
P( x j |Ω- ( t) ) PΩ- ( t - 1) |x j) ] ( 9 )
通过式( 8) 系统建立了一个自适应的机制 , 使得与用户给
出的相关例训练数据比较相似的图片可以快速地获得一个比
较大的 P( Ω+ ( t) |xj) 。根据贝叶斯决策理论 , 下面描述求得
最小风险的才是最优行为 , 才能获得用户满意的结果。
3 最小风险的贝叶斯反馈算法
令 L( Ft, Ω, xj) 为损失函数 ( Ft 是 t 时刻的反馈行为与后
验概率 P( Ω+ ( t) |xj) 相对应的概念) , 对于 xj 与 Ω的反馈风险
定位为
R( Ft |x j) = ?xjL( Ft, Ω, xj) P( Ω
- ( t) |x j) dΩ ( 10 )
其中 : xj 是查询实例; P( Ω
+ ( t) |xj) 是后验概率。定义损失函
数为
·2711· 计 算 机 应 用 研 究 第 26 卷
L( Ft , Ω, xj) =δ( Ω±, xj) ( 11)
其中: δ( Ω±, xj) 表示当 Ω
+ 和 xj 相关时 L( F t, Ω, xj) = δ( Ω
+ ,
xj) = - 1, 而当不相关时 L( Ft, Ω, xj) = δ( Ω
- , xj) = 1。当后验
概率 P( Ω+ ( t) |x j) 越大时, 相关性越强 , 风险越小 ; 反之 , 当 P
( Ω- ( t) |xj) 风险越大 , 相关性越弱。
风险定义为
R = ?R( F t |xj) dxj ( 12)
求解最小风险相关反馈过程为
R* = { F * } = arg{ Ft } min( { Ft } , Ω, xj) ( 13)
很显然 , 可以在多次的检索反馈后得到同类 R* 的阈值,
从而在之后的检索反馈中对 R 进行相应的比较, 决定反馈的
次数, 从而能节约系统的资源并能使用户得到满意的结果。
4 实验分析
为了客观地评价相关反馈策略的性能 , 实现基于内容的图
像检索原型系统 , 进行了大量实验。该原型系统的图像数据库
中存储了两组图片 , 分别为 1 000 幅和 5 000 幅图片。第一组
图片是从 Corel 图像库随即抽取的 10 类图片; 第二组是从
Corel 图像库中随机抽取的 50 类图片 , 每类 100 幅图片。由于
不同的用户对同一幅图像的理解存在差异 , 对同一个查询请
求, 不同用户得到的最终结果不同 , 很难对实验结果进行评价。
因为 Corel 图像库中每一类图片是在内容上相关的( Corel 图像
库中的每一类反映一个主题 , 图片被分成了“鸟”“虎”“玫瑰
花”等) , 本文用计算机进行了模拟。具体方法是选一幅图像
作为查询实例 , 进行第 1 次查询, 对具有最小风险的图像进行
考察, 如果它与被查询的图像在同一个类 , 则将其作为相关类 ;
否则作为非相关类 , 然后开始下一时刻的查询。
为了突出本策略的有效性, 分别按照式( 3) 贝叶斯式方法
和最小风险方法在第一个图像库作了 450 次查询 , 在第二个图
像库上作了 600 次查询并把这些查询结果进行平均 , 得到相应
的平均准率 , 具体如图 2、3 所示。另外本文还与文献[ 7] 提出
的贝叶斯反馈算法进行了比较。图 3 显示了文献提出的方法
在第二个图像库上进行 600 次查询后得到的平均准确率。具
体实验结果数据如表 1 所示。
上述结果表明本文策略能够使查询准确率明显提高 , 尤
其在图像数据库比较大的情况下。在第二个图库上的实验结
果表明 , 基于低层次特征的平均准确率只有 9. 90% , 采用了本
文策略第 1 次反馈后的平均准确率提高一倍达到 20% , 第 2
次反馈后的平均准确率提高了大约两倍达到 28. 7% , 在 25 次
反馈后速度放缓 ; 第 50 次的反馈后的平均准确率为 81. 1% ,
第 100 次反馈后平均准确率达到 86. 2% 。从表 1 的最后两列
看, 本文提出的方法明显优于文献 [ 8] 提出的贝叶斯反馈算
法, 它使每次反馈后的平均准确率提高了 5% ～15% 。
5 结束语
本文提出了一种新的基于内容图像检索的相关反馈方法
策略 , 并利用该方法进行了大量图像检索实验。实验结果表
明, 使用本文的方法比未使用本文方法有明显提高 , 具有准确
率高、相应速度快的优点 , 具有用户满意的查全率。与一般的
相关反馈方法相比 , 它更适用于实时系统。该方法不仅可以用
于一般的图像检索系统, Internet 网上的图片检索 , 还可以直接
应用到基于内容的视频检索中 , 视频中的一帧对应着一幅图
像, 因此它对基于内容的视频检索非常有意义。
参考文献 :
[ 1] ong R, HUANG T S H, ORTEGA M, et al. Relevance feedback: a
power tool for interactive content-based image retrieval [ J] . IEEE
Trans on Circu its and Vid eo Te chnology , 1998, 8 ( 5 ) : 644-655.
[ 2] COX I J, MILLER M L, MINKA T, et al. The Bayesian image retrieval
system, PicHunter: theory, implementation, and psychophysical ex-
periments[ J] . IEEE Tra ns On Image Proce ssing, 2000, 9 : 20- 37.
[ 3 ] ISHIKAWA Y, SUBRAMANYA R, FALOUTSOS C. Mindreader:
query databases through multiple examples [ C ] / / Proc of the 24 th
VLDB Conference. New York: Morgan Kaufmann, 1998 : 218- 227.
[ 4 ] LEE C, MA W Y, ZHANG H J. Information embedding based on us-
er’s relevance feedback for image retrieval[ C] / / Proc of SPIE Pho-
tonic. Bellingha Press: SPIE, 1999 : 20- 22.
[ 5] SU Zhong, ZHANG Hong-liang, MA Shao-ping. Using Bayesian classi-
fier in relevant feedback of image retrieval [ C] / /Proc of the 12 th
IEEE International Conference on Tools with Artificial Intelligence.
Washington DC: IEEE Computer Society, 2000 : 258- 261.
[ 6] SU Zhong, ZHANG Hong-ping , MA Shao-ping. Relevant feedback
using a Bayesian classifier in content-based image retrieval[ C] / /Proc
of the SPIE Storage and Retrieval for Media Database. San Jose: SPIE
Press, 2001 : 97- 106 .
[ 7 ] 苏中 , 张宏江 , 马少平 . 基于贝叶斯分类器的图像检索相关反馈算
法 [ J] . 软件学报 , 2002, 13 ( 10) : 2001 - 2006.
[ 8] 段立娟 , 高文 , 林守 勋 , 等 . 图像检 索中的动 态相似性度 量方法
[ J] . 计算机学报 , 2001, 24 ( 11) : 1156 - 1162.
[ 9 ] 吴洪 , 卢汉清 , 马颂德 . 基于内容图像检索中相关反馈技术的回顾
[ J] . 计算机学报 , 2005, 28 ( 12) : 1969 - 1979.
[ 10] 唐杰 , 梁邦勇 , 李涓子 , 等 . 语义 Web 中的本体自动映射 [ J] . 软件
学报 , 2006, 29 ( 11) : 1956 - 1976 .
·3711·第 3 期 文春勇 , 等 : 基于最小风险的贝叶斯决策理论相关反馈方法
