9512.net
甜梦文库
当前位置:首页 >> >>

基于相关反馈的高维图像检索方法


!""& 年 ! 月 第 (( 卷- 第 % 期

-

西安电子科技大学学报 ( 自然科学版) !"#$%&’- "(- )*+*&%- #%*,-$.*/0

-

P<R+ !""& O45+ ((- W4+ %

基于相关反馈的高维图像检索方法
! 崔 江 涛% , 孙 君 顶% , , 周 利 华%

( %, 西安电子科技大学 计算机学院, 陕西 西安- *%""*% ; !, 河南理工大学 计算机学院, 河南 焦作- ’#’%#) ) 摘要:传统索引方法在高维情况下会面临维数灾难问题, 基于向量近似的索引方法是有效的高维检索 方法+ 对向量近似方法中 ! 近邻搜索算法加以改进, 应用到基于相关反馈的交互式图像检索系统中" 根 据反馈过程前后的距离变化特性, 在进行 ! 近邻搜索过程中, 将上轮次的查询结果和用户反馈信息用作 过滤信息, 可减少特征向量的访问数量" 在大容量真实图像数据库上的实验表明, 将新算法应用于相关 反馈过程的图像检索中, 可提高 ! 近邻搜索速度+ 关键词:基于内容的图像检索; 高维索引; 相关反馈; 向量近似; ! 近邻搜索 中图分类号: ./(%%+ %(’+ (- - 文献标识码: 0- - 文章编号: %""%$!’"" ( !""& ) "%$""&!$"’

!" #$$%&%#"’ (%)(*+%,#"-%."/0 %,/)# %"+#1%") ,#’(.+ $.2 2#0#3/"&# $##+4/&5
! #$% &’()*+,(-% ,.$/ &0)+1’)*%, ,234$ 5’+60(%

( %+ 123445 46 7489:;<= 12><?2< @?A B?C>?<<=>?C ,D>A>@? E?>F+ ,D>G@?- *%""*% ,73>?@;!+ 123445 46 7489:;<= 12><?2< @?A B?C>?<<=>?C,H<?@? /45I;<23?>2 E?>F+ ,J>@4K:4- ’#’%#) , 73>?@) !4-’2/&’: - L@?I ;=@A>;>4?@5 >?A<M>?C 8<;34AN 9<=64=8 944=5I >? ;3< 3>C3$A>8<?N>4?@5 F<2;4= N9@2<+ .3< O<2;4= 099=4M>8@;>4? P>5< @99=4@23 4F<=248<N N48< 46 ;3< A>66>2:5;><N 46 2:=N< 46 A>8<?N>4?@5>;I+ 0 ?<Q !$?<@=<N; ?<>C3R4= N<@=23 @5C4=>;38 R@N<A 4? O0$P>5< 64= =<5<F@?2< 6<<AR@2S >8@C< =<;=><F@5 >N >?;=4A:2<A >? ;3>N 9@9<=+ T@N<A 4? ;3< 6<<AR@2S ,;3< 24==<5@;>4?N 46 ;3< :?A<=5I>?C N>8>5@=>;I 8<;=>2 R<;Q<<? ;Q4 24?N<2:;>F< N<@=23<N >N <M954>;<A,@?A ;3<? ;3< N<@=23 =<N:5; @?A 6<<AR@2SN @?A :N<A ;4 6>5;<= ;3< @99=4M>8@;< F<2;4=N >? ;3< ?<M; N<@=23 =4:?A+ BM9<=>8<?;N 4? ;3< 5@=C< =<@5$Q4=5A A@;@N<; N34Q @ =<8@=S@R5< =<A:2;>4? 46 F<2;4=N @22<NN<A @?A @? >89=4F<8<?; 4? ;3< >?A<M>?C 9<=64=8@?2< 2489@=<A Q>;3 ;3< <M>N;>?C N<@=23 @5C4=>;38+ 6#7 8.2+-: - 7TUV ( 24?;<?;$R@N<A >8@C< =<;=><F@5 ) ; 3>C3$A>8<?N>4?@5 >?A<M>?C; =<5<F@?2< 6<<AR@2S ; F<2;4= @99=4M>8@;>4? ; !$?<@=<N; ?<>C3R4= N<@=23 基于内容的图像检索 ( 7TUV) 已经成为图像数据库中的一项重要应用+ 由于图像语义的丰富性和用户需 求判断的主观性, 基于低层视觉特征的 7TUV 系统往往不能满足以高层语义为特征的检索需求+ 为了解决这
[ %] 一问题, 近期 7TUV 系统大都采用了基于相关反馈的交互机制 + 由于表示图像特征的向量往往具有高维特 [ !] 性, 高维特征空间中的近邻搜索也成为目前多媒体数据库领域的一个研究热点 + 最近的一些研究表明, 传 [ (] 统的检索技术 ( 7 ! 树, 8 树, .7 树和网格文件等) 在特征维数足够高的情况下 ( 超过几十维) 进行近邻搜 [ ’, #] 索时会产生维数灾难 + [ #] 基于向量近似 ( O0$P>5<) 的索引方法是目前在高维情况下惟一能优于顺序查询的精确索引方法 , 目前

收稿日期: !""#$"%$"& 基金项目: 十五国家部委预研资助项目 ( ’%(%&"#"% ) 作者简介: 崔江涛 ( %)*#$) , 男, 讲师, 博士+

第 6 期8 8 8 8 8 8 8 8 8 8 8 8 8 8 崔江涛等: 基于相关反馈的高维图像检索方法

(;

[ (] 的研究趋势是在 !"# 变换域中构建 !"#$%&’ ) 但是这种基于正交变换的 !"#$%&’ 方法不能应用到相关反馈

的高维检索中) 笔者在分析相关反馈技术的基础上, 提出一种新的 $ 近邻搜索算法, 可充分利用上轮的查询 结果和用户提供的反馈信息, 提高 !"#$%&’ 方法的 $ 近邻搜索性能)

!" 相关反馈技术
在 *+,- 系统中, 图像可表示为特征空间中的向量形式, 相似性查询也就成为向量空间中的 $ 近邻搜索 问题) 从向量模型的角度出发, 目前常用的相关反馈技术包括查询向量优化算法和特征权重调整算法) 在经
[ 0] [ 5] 典的相关反馈图像检索系统 ."-/ 和 .%12-’32’4 中都采用了这两种反馈技术)

假定图像 % 的特征向量可表示为 ! % &[ ’ %6 , ’ %7 , …, ’ %( ] , 查询特征向量为 " & [ )6 , )7 , …, )( ] , ( 是特征向 量的维数* ’ % 与 ) 之间的距离定义为8
9 ( ( ), ’ % ) &( ) + ’ % ) # ( ) + ’% ) 8 ,

(6)

# 称为相似矩阵, 它是一个实对称矩阵, 通过奇异值分解技术, # 可变换为一个对角阵, 上述距离就变换为 加权欧式距离形式, 文中假定 # 是一个实对角阵, 并且 " , -- & 6 * 假设用户对训练图像标记为正的图像数目为 ., 为使查询向量和反馈正例的距离达到最小, 经过反馈过
[ 0] 程后, 查询向量 $ 和相似矩阵 # 的最优表达式为

$9

!

& !9 %

( " !/ ) 8
/ &6

.

61 ( , 8 8 0 ! &( 2’: ( &) ) & +6 8 ,

(7)

& 是 % 的加权协 ! / 是用户对反馈正例图像 / 给出的反馈分值* 矩阵 % 是由反馈正例向量组成的 . 2 ( 矩阵,
.

方差矩阵, 即8 8

& 3, 4 &

" / &6

8 8 3, 4 & 6, …, (8 * ( 5 /4 + ) 4 ) ( " ! / ) 8 , !( / 5 /3 + ) 3 )
/ &6

.

(;)

#" 支持相关反馈的检索方法
!" #$ %&’()*+ 文件生成 8 8 !"#$%&’ 方法是对特征向量进行近似 (压缩) 表示, 用更少的位数表示 原向量, 从而达到减少系统 , < = 时间的目的) 在向量空间内对向量进行近 似时, 对每一维空间 - 分配一定的近似位数 6- , 将坐标轴分割成 7 - 个区间,
( 6

6" - &6

& 6, ( 是向量空间维数, 整个向量空间被分成 76 个超立方体形状的

胞腔* 如图 6 所示, 在二维空间内对每一维空间各分配 7 位近似位数, 则 !% 所处的胞腔可表示为 6>66, 所以 !% 可由近似向量 ’% & 6>66 表示) 所有特征 向量的近似向量顺序排列可组成一个近似向量文件 !"#$%&’) 上 " 与 ! % 的距离上下界, 8 % 和 7 % 分别为[ ?]
图 68 !"#$%&’ 示例

根据近似向量 ’ % , 可计算查询向量 " 与 ! % 之间的距离上界 7 % 和下界 8 % * 假设 8 %, - 和 7 %, - 分别是第 - 维空间

{

9 8 % &[ 8 %6 , 8 %7 , …, 8 %( ]# [ 8 %6 , 8 %7 , …, 8 %( ] 8 , 9 7 % &[ 7 %6 , 7 %7 , …, 7 %( ]# [ 7 %6 , 7 %7 , …, 7 %( ] 8 *

(@) (?)

根据距离上下界的定义, 可得到 !" !$ %&’()*+ 方法中的 ! 近邻搜索算法

8 % # ( ’ %, ) # 7% 8 *

$ 近邻搜索过程分为两个阶段, 第 6 阶段只对近似向量进行操作) 首先顺序扫描 !"#$%&’, 根据 ’ % 计算特 征向量 ! % 和查询向量 " 之间距离下界和上界, 采用一个 $ 维数组 7 A%B: 保存到目前为止 $ 个最小的距离上界 7 % , 数组中元素由 小 到 大 排 列* 如 果 某 个 向 量 的 距 离 下 界 8 % 大 于 目 前 为 止 遇 到 的 第 $ 小 的 距 离 上 界, 即 8 % 9 7 A%B: [ $] , 此向量就可被过滤掉, 因为已经存在至少 $ 个更好的候选向量* 否则, 将 ! % 作为候选向量, 并用 7 % 更新数组 7 A%B: * 所有候选向量的集合用 .6 表示) 在第 7 阶段中, 对候选集中的候选向量, 按照距离下界由小到大的顺序访问具体特征向量, 并按照公式

. 8.9 . . . . . . . . . . . . .

. 西安电子科技大学学报 ( 自然科学版) . . . . . . . . . . . .

. . . . 第 CC 卷

(!) 计算与查询向量的精确距离" 一般来说只有很少一部分候选向量需要计算, 如果某个候选向量的距离下 界大于目前的第 ! 个最近邻距离, 整个查询过程就结束" 该阶段中需要访问的特征向量集合用 ## 表示" !" #$ 支持相关反馈的 ! 近邻搜索算法 由于近似位串的存储空间远小于原始特征向量, 对近似位串的访问可显著减少系统的 $ % & 时间, 在过滤 阶段过滤掉更多的向量, 即减少 #! 和 ## 中特征向量的数目, 就可获得更好的查询性能" 在相关反馈过程中, 由于特征权重和查询向量的改变, 需要重新扫描整个 ’()*+,-, 这时每个轮次的查询时间基本上是相同的" 由 于 #! 集合中近似向量的数目很少, 而且 #! $## , 可在内存中保存这些集合, 在新一轮的查询过程中加以利 用, 提高检索效率" 采用 $ 表示反馈过程的轮次, $ % !, #, …, &, 用 ! $ 和 " $ 表示第 $ 次反馈过程后计算所得的查询向量和相
$ $ 似矩阵, 分别用 #! , ## 表示第 $ 次查询过程后的候选向量集合和特征向量集合" $ $ $ 从 #! 中取出所有近似向量, 根据改变后的 ! $ 和 "$ 重新计算出 #! 中 ! 个最小的距离上界, 用数组 ’! 表示" $ $ $ 集合中包含具体的特征向量, 从 ## 中取出所有特征向量, 根据 "$ 计算 ! $ 与这些向量的实际距离, 用数组 ’# ## $ $ 保存 ! 个最小的实际距离" 可证明, 采用 ’! 或 ’# 作为初始的距离上界来进行第 ! 阶段过滤, 不会造成错误遗漏" $ $ 证明. ! )’! 是由 #! 中 ! 个最小的距离上界组成, 可作为初始距离上界进行第 ! 阶段过滤" $ $ 是由 ## 中 ! 个最小的实际距离组成, 假定 $ ( ! 轮查询后, 近邻结果集中第 ! 小的距离为 . . . # )’#

!

$ (!

$ $ (! $ , 那么 ’[ 如果某个向量与查询向量之间的距离下界大于 ’[ , #! " 在 $ ( ! 轮次第 ! 阶段过滤中, # !] # !]

$ $ $ (! $ , 那么 , - $ (!, 即 ) * + ’[ % ) * + ’[ %! 成立" 上式保证了采用 ’# 过滤的有效性" 证毕" # !] # !] .*

下面给出 $ ( ! 轮次近邻搜索算法中的第 ! 阶段过滤算法, 第 # 阶段过滤算法与常规 ’()*+,- 方法相同"
$ $ $ $ 分别计算数组 ’! 和 ’# ; ! 根据第 $ 轮查询后的 #! 和 ## 集合, $ $ 组成数组 ’ /+01 ; " 选择数组 ’! 和 ’# 中最小的 ! 个值, 计算 ’ * 和 ) * ; # 根据 # * ,! $ 及 " $ ,

[ !] , 则排除向量 $ * , 否则将 $ * 插入到候选集中, 并用 ’ * 更新数组 ’ /+01 " $ 如果 ) * + ’ /+01 与常规 ’()*+,- 相比, 新算法利用上轮反馈信息增强了上界距离的逼近程度, 从而提高了过滤能力"

!" 实验结果与分析
[<] 测试图像数据库包含 !2 222幅不同类别图像, 采用 3456)7 标准中的 89 维的 :;/ 作为图像颜色特征向量 ,

实现了颜色特征相关反馈的近邻搜索, 反馈轮次为 = 轮" 此实验不针对查询结果的准确率和查全率, 只对常规 ’() *+,- 方法中的过滤算法和新算法进行了检索性能比较" 采用 ’()*+,- 方法和应用于相关反馈的 ’()*+,- 方法 ( *-->?@AB ’()*+,-) , 平均位串长度为 C 位 % 维、 9 位 % 维、 = 位 % 维和 8 位 % 维, 这 9 种方案中每维空间内分配的位数相 同" 每维空间的分割算法采用 *-DE@1F0G@HFI,J 等人提出的
[8] 非均匀的分割方法 " 从测试集中随机选择 !22 个向量作

为 !)KK 搜索的查询向量, 最后的测试结果是这 !22 个查 询向量性能数据的平均值" 图 # 给出了两种算法在扫描过程中 ’ /+01 [ !]的变 化情况" 实验数据在 8 位 / 维位串长度下取得, 每相隔 =2 个点进行一次 ’ /+01 [ !]的统计, 给出了扫描前 # 222
图 #. 第 ! 小的距离上界 ’/+01 [ !]的变化曲线

个数据点 ’ /+01 [ !]的变化曲线" 由图 # 可看出, 两种算法都是在扫描数据点达到 ! =22 左右时 ’ /+01 [ !]趋于稳 定, 但是 ’()*+,- 方法中 ’ /+01 [ !]值变化比较明显, 而 *-->?@AB ’()*+,- 方法中 ’ /+01 [ !]初始值与稳定值相差 不大, 由此可见, 新方法可提高第 ! 阶段的过滤效率"

第 + 期5 5 5 5 5 5 5 5 5 5 5 5 5 5 崔江涛等: 基于相关反馈的高维图像检索方法

QP

值得注意的是, 新方法并不能提高第 ! 阶段的过滤效率, 由 "#$%&’( 方法扫描过程可知, 下界距离对实 际距离的逼近程度决定了第 ! 阶段的过滤性能) 图 * 给出了两种算法在第 + 阶段扫描后 !+ 集合中候选向量 %((,-./0 "#$%&’( 方法是经过反馈过程后的测试结果) %((,-./0 "#$%&’( 方法在第 + 阶段的过滤 的数量比较, 性能明显大于 "#$%&’( 方法, 而且近似位串长度越小, !+ 集合越大时, 性能提升越大) 图 1 给出了两种算法在 第 + 阶段过滤过程的 234 运行时间比较)

图 *5

!+ 集合大小比较

图 15 第 + 阶段搜索时间比较

!" 结 束 语
笔者对高维检索结构 "#$%&’( 中的 " 近邻搜索算法进行改进, 提出一种新的 " 近邻搜索算法, 应用到采 用相关反馈技术的 2678 系统) 反馈过程中相邻两次查询结果具有一定的相关性, 利用用户提供的反馈信息 和上轮次的查询结果, 提高了 "#$%&’( 方法第 + 阶段的过滤性能, 也提高了 "#$%&’( 方法在基于相关反馈的 图像检索中的应用能力) 参考文献:
[ + ] 89& :,;9.<= > ?,@AB(=. C,(B .’) 8(’(D.</( %((,-./0:. 3EF(A >EE’ &< 7<B(A./B&D( 2E<B(<B$-.G(, 7H.=( 8(BA&(D.’ [ I] ) 7JJJ >A.<G E< 2&A/9&BG .<, ?KGB(HG LEA "&,(E >(/M<E’E=K, +NNO , O (P) : Q11$QPP) [ ! ] 89& :,;9.<= > ?,2M.<= ? %) 7H.=( 8(BA&(D.’:29AA(<B >(/M<&R9(G,3AEH&G&<= S&A(/B&E<G,.<, @T(< 7GG9(G [ I] ) IE9A<.’ EL "&G9.’ 2EHH9<&/.B&E< .<, 7H.=( 8(TA(G(<B.B&E<, +NNN , ( +U ) : *Q$N!) [ * ] 6EMH 2,6(A/MBE’, ?,V(&H S) ?(.A/M&<= &< ;&=M$S&H(<G&E<.’ ?T./(G$7<,(W ?BA9/B9A(G LEA 7HTAED&<= BM( 3(ALEAH.</( EL C9’B&H(,&. S.B.-.G(G [ I] ) #2C 2EHT9B&<= ?9AD(KG, !UU+ , ** (*) : *!!$*X*) [ 1 ] 6(A/MBE’, ?,6EMH 2,V(&H S,(B .’) # 2EGB CE,(’ LEA Y(.A(GB Y(&=M-EA ?(.A/M &< ;&=M$S&H(<G&E<.’ S.B. ?T./( [ #] ) 3AE/ #2C ?KHT E< 3A&</&T’(G EL S.B.-.G( ?KGB(HG [ 2] ) #A&ZE<.:#2C, +NNX) XO$OQ) [ P ] [(-(A 8,?/M(0 ; I,6’EBB ?) # \9.<B&B.B&D( #<.’KG&G .<, 3(ALEAH.</( ?B9,K LEA ?&H&’.A&BK$G(.A/M C(BME,G &< ;&=M$S&H(<G&E<.’ ?T./(G [ #] ) 3AE/ !1BM 7<B 2E<L "]S6 [ 2] ) Y(F :EA0:7JJJ, +NNO) +N1$!UP) [ Q ] %(AM.BEGH.<E=’9 ;,>9</(’ J,#=A.F.’ S) "(/BEA #TTAEW&H.B&E< 6.G(, 7<,(W&<= LEA YE<$9<&LEAH ;&=M S&H(<G&E<.’ S.B. ?(BG [ #] ) 3AE/ EL BM( #2C 7<B^’ 2E<L E< 7<LEAH.B&E< .<, V<EF’(,=( C.<.=(H(<B ( 27VC!UUU ) [ 2] ) Y(F :EA0:#2C,!UUU) !U!$ !UN) [ X ] 89& :,;9.<= > ?) @TB&H&Z&<= ](.A<&<= &< 7H.=( 8(BA&(D.’ [ #] ) 3AE/ 7JJJ 2"38 [ 2] ) Y(F :EA0:7JJJ, !UUU) !*Q$!1*) [ O ] 7GM&0.F. :,?9-A.H.<K. 8,%.’E9BGEG 2) C&<,A(.,(A:\9(AK S.B.-.G(G >MAE9=M C9’B&T’( JW.HT’(G [ #] ) 3AE/ EL !1BM "]S6 2E<L(A(</( [ 2] ) Y(F :EA0:CEA=.< V.9LH.<<, +NNO) !+O$!!X) [ N ] C.<_9<.BM 6 ?,@MH I 8,".G9,(D.< " ",(B .’) 2E’EA .<, >(WB9A( S(G/A&TBEAG [ I] ) 7JJJ >A.<G E< 2&A/9&BG .<, ?KGB(HG LEA "&,(E >(/M<E’E=K, !UU+ , ++ (Q) : XU*$X+1)

( 编辑:郭5 华) 5 5

" !"! " " " " " " " " " " " " "

" 西安电子科技大学学报 ( 自然科学版) " " " " " " " " " " " "

" " " " 第 ## 卷


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图