（信号与信息处理专业论文）视频搜索结果的重排序研究.pdf

摘要 摘要 互联网中视频数据在近几年呈爆炸式增长并且广泛分布 使得视频搜索成 为当前视频研究的重点和热点 由于文本搜索的成功应用 现今通用的大型视 频搜索引擎 如g o o g l e y a h o o l i v e 百度等主要还是利用视频数据周围的 文本信息 采用基于文本搜索的方法实现视频搜索和排序 然而 视频内容及 其所包含的复杂意义通常是语言工具难以完整描述与表达的 为了解决这种原 始文本搜索的缺陷 视频搜索结果的重排序逐渐引起了众多研究者的关注 重 排序 是指基于原始搜索排序的基础上 通过挖掘数据内在关联 或者借鉴外 部知识和人工干预 对原始搜索结果进行重新排序的过程 目的是提高搜索质 量和提升用户搜索体验 本论文首先提出 种新颖的基于查询独立的学习框架 接着从三个阶段研 究了视频搜索结果的重排序中的关键问题 即自重排序 仅从自身挖掘相关知 识 样例重排序 利用用户提供的森询样例 和群重排序 利用从外部搜索引擎的 结果中挖掘的知识 显然这三个阶段涵盖了现今的火部分视觉信息重排序的框 架和方法 本文对视频重排序方法进行了深入的研究 主要工作和创新之处归 纳为以下几点 1 对于查询独立的学习框架 本文提出了在 查询 镜头 对中学习相关性 关系 与传统的查询依赖的学习框架不同 该种方法的训练模型和任何奁 询没有直接关系 故训练样本在所有的裔询中能达到共享 更适用于实际 的应用 在这种查询独立的学习框架下 各种机器学习的方法都可以扩张 并应用 从而进一步提出了一种基于s v m 模型的全监督鹰询独立的学习 方法和一种基于多淄模型的半监督的查询独立学习方法 经过人量实验证 实 查询独立的学习方法明显优于传统的查询依赖的学习方法 从算法的 运算量角度看 焱询独立的学习方法也更具有实用性 2 对于自重排序 本文提出 种基于典型性的视频结果的重排序方法 传统 的基于学习的重排序方法往往只关心训练样本的相关性或多样性 却忽略 了样本的典型性 本文提出在考虑相关性和多样性的同时应兼顾样本的典 型性 首先根据样本的概率分布定义视频 矧像的典型性 并将样本选择 看成一个既考虑样本典型性又兼顾原始搜索结果的优化问题 最后基于选 择的高典型性样本并利用s v m 构建霞排序模型 实验表明该模型具有较 好的泛化能力昶l 较盥的鲁棒性 3 对于样例重排序 本文提出一种基于禽询样例的全监督视频重排序方法 传统的全监督的视频重排序方法常根据经验将重排序问题转化为二二类的 摘要 分类问题 样本完全根据分类的置信度进行排序 文中提出了重排序实际 上应是一个优化问题 即一个序列中的任意两个样本都能正确排序即可达 到全局最优 而不是简单地区分每一个样本是否相关 在这样的框架下 迸一步提出两种重排序算法 即直接重排序和插入重排序 实验证实 新 的重排序方法可以较大程度地改进原始的搜索结果 与其他一些经典的重 排序方法相比 也具有较火的优势 4 对于群重排序 是本文中提出的重排序问题的新的发展阶段 旨在从互联 网中挖掘相关的视觉原型并利用到重排序中 据大量资料的调研 群重排 序是茵次将互联网中的群包数锯应用到搜索结果的重排序当中 与传统的 自重排序和样例重排序有显著的不同 首先利用多个搜索引擎返回的结果 图像构建一组视觉荤词 接着在此视觉单词中挖掘两种视觉原型 显著度 和共存性 最终基于该视觉原型将重排序问题转化为一个优化问题 并 给出封闭解 实验表明 群重排序对原始搜索结果的提高是较稳定的 与 传统的重排序方法相比有较明显的提升 关键词 视频搜索重排序基于内容的j j 频搜索 语义分析全监督学习 半 监督学习优化概念检测样本选择群重排序 i i a b s t r a c t t h ee x p l o s i v eg r 0 叭ha n dw i d e s p r e a da c c e s s i b i l i 哆o fc o m m u l l i 够 c o n 仃l b u t e d m u l t i m e d i ac o n t e n t s0 nt h ei n t e m e th a v e1 e dt os u r g eo fr e s e a r c ha c t l 够mv l d e o s e a r c h d r l l et ot h eg r e a ts u c c e s so ft e x ts e a r c h m o s tp o p u l a rv 1 d e os e a r c he n 母n e s s u c ha sg o o g l e y 刁 h o o l i v ea n db a i d u b u i l du p o nt e x ts e a r c ht e c h n l q u e sb yu s m g t h et e x t 协f b 肌a t i o na s s o c i a t e dw 醯lv i d e od a 组 t h i sh n d o fv i d e os e 豺c ha p p r o a c h h a sp r o v 朗u n s a t i s 助n ga si to r e ne n t i r e l yi g n o r e st h ev i s u a lc o n t e 鹏孤dh 哪a n p e r c e p t i o no nt h es e a r c hr e s u l t s t oa d d r e s st h i si s s u e v i d e os e a r c hr 蛐g h a s r e c e i v e di n c r e a s i n ga 舰血0 n mr e c e n ty e a r s i ti sd e f i n e da sr e o r d e r i n gv i d e os h o t s b a s e do nm u l t i m o d a lc u e st 0i i n p r 0 v es e a r c hp r e c i s i o n i nm i st h e s i s w ef i r s tp r o p o s ean o v e lq u e r y 一协d e p e n d e n tl e a r n j n gb a s e d v i d e o s e a r c h 缸 a m 蹦曰r k t 王1 e nw ei n v e s t i g a t et l l ek e yp r o b l e m so f v i d e 0s e a r c hf e f a n k l n gl n t h r e e p a r a d i g m s s e l f 二r e m n k i n w h i c ho n l y u s e si n i t i a l s e a r c h r e s u l t s q u e r y e x a m p i eb a s e dr e r a n k i n w h i c hi e v e m g e s l l s e rp r 0 v i d e dq u e 盯e x 锄p l e s c r o w d r e r a n l i n w h i c ha i m st 0 埘n er e l e v a n t v i s u a lp 甜e r n s 舶mt h es e a r c hr e s l l l t s o fe x t e m a ls e a r c he n g i n e s o b v i o u s l y s u c ht h r e ep a r a d i g m sc o v e rm o s to f e s t m g 础 a n k i n gf r 2 i n l e w o r k0 ra p p r o a c h e s a c c o r d i n g l y t h i s t 1 1 e s i sc o n d u c t sad e e p r e s e a r c h0 nv i d e os e a r c hr e l 彻舾n g a n d0 b t a i n st h ef o l l o w i n ga c h i e v e r n e n t s 1 w ef l r s t l yp r o p o s ean o v e lq u e 巧一i n c l e p e n d e n tl e a r n i n g q i l 仃a m e w o r kf o r v i d e os e a r c h b yi n v e s t i g a t i n g r e l e v a n c e盘o mq u e r y s h o tp a i r s u n l i l e c o n v e n t i o n a lq u 叫 d e p e n d e n tl e a r n i n g胁m e w o r k i ti sm o r eg e n e r a la n d s u i t a b l ef o rr e a l w o r l ds e a f c ha p p l i c a t i o i l s u n d e rt l l i s 盘锄e w o r k w ec a n u s e v a l r i o u sr m c h i n e1 e 枷i n gt e c h n o l o g i e s t h e r e f o r e w e 缸胁e rp r o p o s e a s v m b a s e d s u p p o r tv b c t o rm a c l l i n e s u p e r v i s e dq u e 巧一i n d 印e n d e n tl e 锄h 培 a n dam u l t i g r a p h b a s e ds e i l l i s u p e r v i s e dq u e r y 抽d e p e n d e n t i e a m l n g a p p r o a c h 2 f 0 rs e l f r e r a n k i n g w ep r o p o s eat y p i c a l i t r b a s e dv i d e os e a r c h r e r a n k l n g c 0 n v e n t i o n 2 l ll e a r n i n g b a s e da p p r o a c h e st 0v i d e os e a r c hr e l 加k m go n l yc a r e t h er e l e v a n c e0 rm v e r s i 够o ft h es e l e c t e de x a m p l e sf o rb u i l d i n gt h er e r a n k l n g m o d e l w h i l ev i e ot y p i c a l 时i su s u a l l yn e g l e c t e d i nt h i st h e s i s w ep r o p o s et o s e l e c tt h em o s tq l r p i c a ls a m p l e st ob u i l dr e r a n k i l l gm o d e l c o n s l d e n n gt h a t 啪i c a l 畸i n d i c a t e st h er e p r e s e n t a t i v e n e s so fe a c hs a m p i e s ot h a tm o r er o b u s t m r e r a n 舾n gm o d e lc o u l db el e a m e d w r ef i r s td e f i n et h et y p i c a i i t ys c o r eo f l 工1 1 a g e v l d e ob a s e do ns a m p i ed i s t r i b u t i o n a n dt l l e nf o r m u l a t et h ee x a 瑚d l e s e i e c t l o na s 卸o p n 姗z a t l o ns c h e m em a tt a k e si n t oa c c o u n tb o t ht h ei m a g e t y p i c a l i t y 卸dt h ei n j t i a l r a n k i n go r d e ri nt h ei n i t j a is e a r c hr e s u l t s b a s e do nt 1 1 e s e l e c t e de x a m p l e s 代b u i l dt h e r e r a l l l i n gm o d e lb yu s i n gs v m f o rq u e 妒e x 锄p l e b a s e dr e r a n k i n g w ep r e s e n ta n o v e ls u p e n r i s e da p p r o a c ht o v l d e os e a f c i lr e r 觚幻n gw i ms e v e r a lq u e 哆e x a m p l e s c o n v e n t i o n a ls u p e i s e d r e 础l n ga p p r o a c h e se n 叩i r i c a l l yc o n v e r tt h er e r a n k i n ga sac l a s s i f i c a t i o n p r o b l e mi i lw h i c he a c hd o c u m e n ti sd e t e i m 妯e dr e l e v a n t0 rn o t f o l l o w e db v r e o r d e n 昭t l l ed o c 啪e n t sa c c o f d i n gt 0t h ec o n f i d e n c es c o r e so fc l a s s i f i c a t i o n w r ea r j g u e 出a tf e r a n k i n gi se s s e n t i a l l ya no p t i i n i z a t i o np r o b i e mi nw h i c ht h e r a n k e dl i s ti sg l o b a l l yo p t i m a li fa n yt w oa 而i t r a 呵d o c u m e n t s 丘o m t l l eh s ta r e c o n e c t i ym n k e di nt e 功 1 so fr e l e v a i l c e r a t h e rt h a l l s i m p l yc l a s s i 囟i n ga d o c u m e n ti n t or e l e v a n to rn o t u n d e rt h e 舰m e w r o r kw e 内吡e r p r o p o s e 铆o e 施c t i v ea l g o r i t h m c a l l e ds 妇i 曲tr e i 诎i n ga i l d 血s e r t i o nr e i a 1 1 k i i l g t os o l v e t 1 1 ep b l e m1 1 1 0 r ep r a c 石c a l m f 0 rc r o w 投e r a n k i n 蜀w eh a v ep f o p o s e dan e wp a r a d i g mf o fv i s u a ls e a r c h f e 删 1 k i n gc a l l e dc r o w d r e r a l l l i n w h i c hi sc h a r a c t z e db ym i n i l l gr e l e v a n t v l s i l a lp a t t e m sf r o mi m a g es e a r c hr e s u l t so f m u i t i p 王es e a r c he n g i l l e sa v a i l a b l e 0 nt h ei n t 锄e t t 0t h eb e s to fo u fl 1 l o w l e d g e m ep r o p o s e dc r o w d r e m i l 王 i n g r 印r e s 朗t st h ef i r s ta 缘m l p tt o w a r d sl e v e r a g i n gc r o w d s o 眦i n gk n o w l e 1 9 e 南r v l s u a l r e r a n k i n g 1 1 1 i si sag r e a td i 髓r e n c e 蠡 me x i s t i n gs e l r e 脚 1 l 堍龇1 d q u e 妒e x 觚1 p l e b a s e dr e r a l l l i n g w ef i r s tc o n s t m c tas e to fv i s u a lw o r d sb a s e d o nt h el o c a li m a g e 阳t c h e sc o l l e c t e d 如mm u l t i p l ei m a g es e a r c he n g i n e s w r e 也e ne p l i c i t l yd e t e c lt w ok i n d so f i s u a lp a t t e m s i e s a l i e i l ta n d c o n c u n e n t p a t t e m s 锄o n gm ev i s u a lw o r d s f i n a l l y w ef 咖1 a l j z et l l er e r a u 止i n g 嬲a n o p t l l i l l z a t l o np r o b l e m 伽t h eb a s i so ft h em i n e dv i s u a lp a t t e m sa i l dp r o p o s ea c l o s e f b n i ls o l l l d o n k e yw b r d s v i d e os e a r c hr e r a j l k i n gc o n t e n t b a s e dv j d e os e a r c h s e n l a n t i ca n a l y s i s s u p e i s e dl e 觚1 i n g s 砌一s u p e i s e dj e 锄i n g o p t j m i z a 石咀c o n c e p t d e t e c t i o n s a m p l es e l e c t i o n c r o w d r e r a n k i n g 插图目录 插图目录 图1 1 查询词为 海滩 的前1 2 个搜索结果 3 图1 2 视频搜索和重排序的一般框架 6 图2 1 基于机器学习的视频搜索框架 1 2 图2 2 基于全监督学习和半监督学习的视频搜索框架 1 3 黼2 3 联合假设的学习 1 4 陶2 4 排序学习的一般框架 1 4 陶2 5g l r a n k 的框架和流程 1 6 图2 6 基于焘询依赖学习和查询独立学习的视频搜索 1 7 图2 7 蠢询独立学习的训练流程嘲 1 8 陶2 8l s c o m l i t e 中定义的部分概念的缩略图 1 9 图2 9 多恻的一个例予 个主图和四个子图 2 2 图2 1 0t r e c v i d 2 0 0 5 查询及查询样例 2 7 图2 1 lt r e c d 2 0 0 6 褒询及轰询样例 2 7 糊2 1 2t r e c d 2 0 0 7 惫询及务询样例 2 7 陶2 1 3 不同a 取值时的m a p 3 6 图3 1 务询 f i n ds h o t sw i t hs h e e po r9 0 a t s 的三个原始搜索结果 4 0 图3 2 查询 a n i m a l 动物 的不同相关性和典型性 4 2 图3 3 特征空问中样本典型性 a b c 一4 2 图3 4 基于典型性分析的视频重排序框架图 4 3 图3 5l i v e 数据集的杏询样例缩略图 4 6 图3 6 相关样本的相关等级和典型性的相关系数嘲 4 7 图3 7 查询 p a n d a 熊猫 选择的样本图例 4 8 图3 8 针对查询 f o x 狐狸 的样本选择图例 一4 9 图3 9 多种重排序方法的比较 n d c g 力 5 0 图3 1 0 多种重排序方法的比较 m a p 国 5 0 图3 1 1 单个螽询的基于典型性的重排序结果 n d c g 1 0 5 l 图3 1 2 奄洵 p a n d a 熊猫 的前6 个结果 5 l 削3 1 3 查询 t r e e 树 的前6 个结果 5 l 吲3 1 4 查询 f o x 狐狸 的前6 个结果 5 2 i 插图目录 陶4 1 次优的重排序和全局最优的重排序 5 3 幽4 2 基于优化方法的重排j 系统框陶 5 5 矧4 3 不同a 对应的重排序结果 m a p 6 7 劁4 4 不同m 对应的重排序结果 m a p 6 8 图5 1 镬淘词为 车 的原型例子 7 l 图5 2 查询词为 杯子 的原型例子 7 l 幽5 3 视觉数据重排序方法的发展的三人阶段 7 2 矧5 4t r e c d 评测中的一个例子 7 3 削5 5 群重排序流程阿 7 5 图5 6 视觉原型的计算 7 7 陶5 7 针对w e b 数据集中的查询 g o o g l e 搜索引擎返回的前三个结果缩略图 8 0 烈5 8 各种重排序方法的比较 m a p 和n d c g 8 2 图5 9 挚个查询的重排序结果 n d c g l o 8 3 圈5 1 0 不同重排序的结果示例 8 4 图5 1l 参数 对结果的影响q d c g l o 8 5 图5 1 2 搜索引擎个数对结果的影响 d c g l o 8 7 图5 1 3t v 0 7 数据集中不同搜索引擎的重排序结果q d c g l o 8 7 x 表格目录 表格目录 表2 1t r e c v i d 2 0 0 5 自动视频搜索任务的查询语句列袭 2 8 表2 2t r e c d 2 0 0 6 自动视频搜索任务的查询语句列表 2 9 表2 3t r e c d 2 0 0 7 自动视频搜索任务的套询语句列表 3 0 表2 4 相关概念选择结果 3 l 表2 5 视频搜索方法的比较 m a p 3 3 表2 6 视频搜索方法的比较 t r e c d 0 5 中孽个查询的a p 3 3 表2 7 视频搜索方法的比较 t r e c d 0 6 中瞥个查询的a p 3 4 表2 8 视频搜索方法的比较 t r e c d 0 7 中单个查询的a p 3 5 表2 9 重排序实验结果 3 7 表3 1 样本选择的结果比较 4 8 表4 1t r e c d 2 0 0 5 2 0 0 7 测试集数据 6 3 表4 2 相关和非梢关概念检测结果 6 4 表4 3 概念检测的主观评价 6 5 表4 4 熏排序方法的结果比较 m a p 6 6 表4 5 重排序方法的结果比较 婀m p r o v e 6 6 表5 1w 曲数据集中的蠢询列表 8 0 x i 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工 作所取得的成果 除已特别加以标注和致谢的地方外 论文中不包 含任何他人已经发表或撰写过的研究成果 与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明 本人授权中国科学技术大学拥有学位论文的部分使用权 即 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 予版 允许论文被查阅和借阅 可以将学位论文编入有关数据库进 行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论 文 保密的学位论文在解密后也遵守此规定 第l 章绪论 第1 章绪论 本章首先介绍视频搜索研究方向的产生 发展和存在的问题 并山此引出 视频搜索中重排序的研究意义 接着介绍嘲内外研究现状 分析其中存在的关 键问题 最后介绍本文的主要工作和贡献 给出全文的结构安排 1 1 视频搜索的产生 发展和存在的问题 随着多媒体计算技术的迅猛发展 网络传输速度的刁i 断提高 以及各种视 频压缩技术和人容量存储技术的相继出现 使得视频信息的获取 存储和传播 变得越来越方便 也使得视频作为一种信息记录方式得到了越来越广泛的应用 从地质探测 科学考察 监控系统到生活录像 电视节目 人们越来越倾向于 采用视频的形式存储各种各样的信息 1 为了实现对视频数据的描述 组织和 管理 尽可能满足人们的夯询需求 基于语义理解的视频搜索已经成为多媒体 研究领域 项重要的研究课题并且 具有广泛的应用背景和深远的研究意义 视频搜索是指 c 寸视频数据中所蕴含的物理结构和语义内容进行分析和理解 以方便用户螽询 其本质是对无序的视频数据进行结构化 提取语义信息 从 而使得视频内容能像文本 样被快速 准确的搜索 3 现今通用的人型视频搜 索引擎 如g o o g i e 鼬0 0 m s n 百度等主要还是利用文本信息 采用基于 文本搜索的方法实现视频搜索和排序 文本信息主要包含两种 对视频进行人 工标注的关键词和内容无关的元数据似e t a d a 神 利用人工标注关键词的方法得 到的文本信息尽管是基于视频内容的 但由于人工标注非常耗时耗力 因而在 实际应用中受到了限制 而利用无数据的方法多数是被利用在w e b 上的视频搜 索中 4 3 常常通过提取视频所在的阚贞上的文本信息得到 例如视频名称 视频描述和评论等 这种方法省时省力 但是由于这类文本信息跟视频内容无 关 导致了这类文本信息往往噪声较大 有时候甚至完全是错误或者不相关的 信息 2 4 4 另一方厦 当视频周围没有任何可用的元数据时候 研究者考虑将 音频信息转换成文本信息 即利用话音自动识别技术 a s r a u t o m a t i cs p e e c h r e c o 盟i t i o n 3 将视频中人的说话声音提取出来 并利用机器翻洋技术 m t m a c h i n et r a l l s l a t i o n 4 将语音翻译成查询所使用的语言 然而 视频中的话音 和视频的内容仍有差距 例如新闻节目的播音员的语音和当前视频内容显然就 不相关 无声电影就没有任何语音可以提取出来 凶此 利用a s r m t 技术提 取的文本信息噪声依然较人 可靠性也不够高 第l 章绪论 为了根本摆脱基于文本的视频搜索所衙临的刚境 人们又转向研究视频数 据中所包含的内容信息作为索引 这就是基于内容的视频信息搜索 基于内容 的视频搜索是利用视频的视觉 音频和文本特征 进行视频的相似性匹配 输 出特征相似的视频作为搜索结果 视频的相似性体现在视频各种特征的年甘似性 上 这些特征可以向动的从视频数据中客观的提取出来 大入减少人工干预 避免了人工标注的主观性 早期的基于内容的视频搜索系统常常利用一些基本的底层特征进行搜索 然而 由于底层特征不包含语义信息 无法结合用户的搜索意图将视频内容的 语义表达清楚 凶此到了9 0 年代末期 基于学习方法的视频搜索开始兴起 形 成了视频搜索中一个重要的研究方向 即基于视频自动标注 n o t 撕o n 的视频 搜索 视频标注又称为高层语义特征提取 h i 曲 l e v e lf e 狐 ee x t r a c t i o n 或概念 检测 c o n c e p td e t e c t i o n 是指预先定义一些高层语义概念集合 如物体 人 道 路 汽车 天空等 场景 室内 室外 城市 风光 办公室 车间等 事件 游 行 爆炸 野餐 足球赛等 等等 在视频标注中 首先提取这些概念的人工标 注的训练样本的底层特征 然后进行建模和学习过程 得到这些概念的检测子 并将标注结果推广到整个视频数据集 在搜索时以这些概念作为索引 得到最 终的搜索结果 这种基于视频标注的视频搜索常又被称为基于语义的视频搜索 然而 针对视频标注的研究也才处于起步状态 基于视频标注的视频搜索 也存在一些弊端 首先 目前预先定义的概念的数量是非常有限的 完全不能 满足实际的众多用户的不同需求 其次 有限数量的概念检测子的检测精度还 不够高 从美圈n i s t n a t i o m li n s t i t u t eo fs t a n 1 a r d sa n dt e c l l l l o l o g 每年主办的 火规模视频检索圈际评测会议t r e c v i d t r e cv i d e or e t r i e v a le v a l u a t i o n 结果 来看 检测予的平均检测精度的l 司际最高水平还不到o 2 4 显然这样的结果 很难应用到实际系统当中 最后 训练每个检测子都需要大量的训练样本 这 些训练样本也同样需要大量的时间和人力来手工标注 也存在主观性和不精确 性等问题 因而基于标注的视频检索距离真正的实用化还比较远 综上所述 尽管视频搜索技术经过了多年的研究和发展 取得了一定的成 绩 但现阶段各种视频搜索系统都存在不吲的弊端 基于当前视频搜索的技术 和水平 研究如何更有效的理解视频语义内容 提高搜索精度使之更好的服务 于大众 还需要进行进一步的研究和探索 1 2 视频搜索结果的重排序的研究意义 在实际的搜索过程中 众多研究者已经发现 用户不仅关心搜索结果的正 2 第l 帝绪论 确性 埘外搜索结果的排序情况也会很人程度地影响到用户的搜索体验 2 观 察研究发现 j 甘户往往更希望j f 确的搜索结果出现在整个搜索排序的前h l 位置 很多情况下 糟户对姐搜索结果的小满意往往是凶为搜索的排序不佳所导致 以剀ll 为例 陶中显示的是查询为 海滩 的前1 2 个搜索结果 第一行是利 川常规的文本搜索方法 0 k a p lb m 2 5 详见 4 0 得到的结果 第二行是利用 6 史中的方法重排序后的结果 两行结果包含的是完全相同的1 2 幅罔像 但是用 户往往更希望得到的足重排序后的结果 因为更多的 l e 确结果分布枉排列的前 帕j 位簧 f 翟巳豳一肇图墨 j 蘸蒌矗 j j ota 圈l l 查询词为 坶滩 的前1 2 十搜索结果 注 红色圆圈标注的是正确结果 从上面的例子可以看出 在原始搜索结果的基础上 通过调整搜索结果的 排列顺序 可以在很大程度上提高 户对搜索结果的满意程度 另一方面 l 刮一般的搜索排序问题相比 由于重排序是基于原始的 非j 芋结 果 凼此有根多独特的性质和处理方法 以原始搜索结果为基础 与搜索排序问题相比 重排序侧重十对原始搜 索结果的挖掘 m m e 和提炼 r e f m e 因而重排序问题的前提是原始搜 索结果中必须含有一定数量的正确结果 如果原始排序中的正确结果极 少 将直接影响到重排序后的结果 待处理的数据量较小 重排序往往是针对比较靠前的搜索结果 实际 般仪针对前5 0 们0 0 0 个搜索结果m 1 2 与传统的捏索方法相比较 数据盘大大降低 因而复杂度较高的方法也可以考虑采纳 例如一些机 器学习的方法 但同时也导致了重排序算法几乎都1 i 能宏观掌握数据的 全局分布的缺陷 可利j 扫的信息量有限 对于重排序算法来说 无法知道原始搜索结果的 优劣程度 更无法知道原始搜索排序所采用的具体算法 特征及索引方 式 因而对任意的搜索排序结果都采j h 统 的重排序算法 是非常具有 挑战性的 实践证明 一些重排序算法在某些数据集中运用 不仅不能 提高反而降低了原始搜索结果的精确度 8 第l 章绪论 侧重于排序的评估方式 在重排序阶段 用户更在意的是排序而非搜索 凶而有些侧重于正确结果数量的搜索评估方法 例如诲全率 a c c u r a c y 6 9 对于重排序铭法来说是没有意义的 综上所述 方面 现阶段的视频搜索系统远远不能达到用户的要求 而 搜索结果的排列顺序很人程度地影响到了用户的搜索体验 因而对视频搜索结 果的重排序的分析和研究近几年已经成为视频搜索的研究热点 具有重要的理 论和应用价值 另一方l 街 尽管重排序是基于原始搜索结果 但由于对原始搜 索算法可得到的知识有限 可利川的信息量较小 因而重排序问题同样是一个 富有挑战性的研究课题 1 3 国内外研究和发展现状 视频信息检索 搜索是多媒体信息检索领域内重要的研究课题 目标是有效 描述 存储 组织和焱找用户所需的视频信息 1 3 它跨越了矧像处理 计算 机视觉 人工智能 模式识别以及数据库等领域的交叉学科 具有重要的理论 意义 同时 它是对文本 图像 声音等多种媒体形式的综合分析和查洵 是 理论与实践紧密结合的 项研究 具有巨大的应用前景 然而 现今通用的人型视频搜索弓l 擎 例如g 0 0 9 l e m s n y r 址0 01 西度 等主要还是利用文本信息 采用基于文本搜索的方法实现视频搜索和排序 正 如1 1 节中的分析 利用文本信息的搜索存在着较多的缺陷 另一方面 大多 数用户通常更关心搜索结果的排列顺序 视频搜索结果的重排序技术山此产生 近几年来引起很多研究单位和研究者的注意和深入研究 4 1 2 目前针对视频搜 索结果的重排序的研究可以粗略地分成两犬类 6 即无监督重排序 q n s u p e r 以s e di k r a n k i n 曲和有监督重排序 s u p e r v i s e dr e r a n l i n g 无监督重排序 是指不借助外部任何知识 研究的重点在于从原始搜索结果中挖掘信息 进而 自身调整原始结果的排列顺序 经典的无监督重排序方法主要是基于虚相关反 馈 p r f p s e u d or e l e v a n c ef e e d b a c k 1 4 1 5 的框架建立重排序模型 p r f 框架 假设人部分正确搜索结果分布在原始搜索结果的前i l i f 人部分错误搜索结果分 布在原始搜索结果的后面 这样排列在前面和后断的搜索结果就常被当作币样 本和负样本 考虑到这个假设并不是总是成立 凶而依照这个假设而选择的正 负样本常被称作 虚正样本 和 虚负样本 例如 k e n n e d y 等 9 利用虚正样 本和虚负样本发现查询的相关概念 r e l a t e dc o n c 印t 接着利用这些相关概念的 检测子 c o n c e p td e t e c t o r 对样本进行预测 预测得到的概念存在的概率被当成 高层语义特征 送入支持向量机模型 s v m s u p p o r t v e c t o rm a c h i n e 构造务询的 4 第l 章绪论 分类器 与传统选择虚正负样本不同 l i u 等人 l o 提出从原始搜索结果中选择 样本对 s a m p l ep a i r 将样本的相关等级考虑到重排序模型的建立当中 实验证 实比瞥独选择正 负样本效果要好 另外 种无监督的重排序方法是根据 平滑假设 而提出 即对于某个森 询 视觉相似的视频镜头应该具有相近的相关度 这类方法侧重于如何在原始 搜索结果中分析和发现重复出现的视觉原型 v i s u a lp a t t e m 例如 h s u 等人 1 2 利用信息瓶颈理论 i n f o f m a t i o nb o 砌e n e c k 对原始的搜索结果进行聚类 c l u s t e r i n g 达到发现原型的目的 根据原始搜索的得分获得每个类的条件概 率 c o n d i t i 叩a lp r o b a b i i i w 概率火的类被看成是艄关的原型 概率小的类被看 成是原始搜索结果中的噪声 接着重排序被分成2 个独立的过程 首先根据条 件概率对类进行排序 然后按照原始搜索得分对每个类中的结果进行排序 最 终得到完整的重排序后的结果 最近 h s u 等人 1 l 和t i a l l 等人网依据平滑假 设把罔理论 q a p h 弓l 入重排序问题 通过不断迭代 更新每个样本相关性的得 分 最终实现重排序 无监督的重排序方法的优点在于不依赖外部的知识 也不需要人的参与 然而 这类方法却很难解决 二义性 的问题 6 在任何语苦当中都存在多义 词 当用户输入一个查询 如果没有外部知识的指导 系统很难确定用户的真 j f 含义 例如 当用户输入 t r a i n 系统无法确定用户是想搜索 火车 还 是想找到 训练的场景 在这种情况下 很多研究者就提出 重排序尤其当原 始搜索结果不理想的情况下的重排序 应该采用有监督的方法 y 觚等人 1 5 声称现今视频搜索效果不理想 盲目把排在前而的搜索结果当成正样本是不合 理的 因此引入一些惫询的i 冬 像或视频镜头作为套询样例 q l l e 可e x a i n p l e 把 这些例子当作正样本 构造s v m 分类器 t e i 6 等人 1 6 利用有限的查询样例 通过聚类的方法在原始搜索结果中选择并扩充正样本 并随机选择类中心的样 本作为典型的负样本来构建重排序模型 l i u 等人 6 借助一组概念检测子在镬 询样例中发现与查询相关和不相关的概念 然后将重排序问题定义成一个全局 优化的问题 即最优的排序应该包含与森询相关概念的信息量最人 同时包含 与森询不相关概念的信息董最小 与上述利用有限的奁询样例不同 近期l i u 等人 8 最新提出利用w r e b 上火量免费的数据资源来指导当前的重排序 问题的 关键在于如何在含有噪声的海量数搦中挖掘出有用信息 这是一个1 f 常有潜力 但i 司样具有挑战性的研究课题 值得 提的是 在视频搜索和重排序领域 嗣内很多高校和研究机构都非 常关注并积极参与到研究当中 如渍华人学 中圈科学技术人学 复旦大学 上海交通人学以及微软亚洲研究院等 在n i s t 组织的t r e c d 评测中 取得 5 第l 章绪论 了很好的结果 0 国际研究水平相比 树内的这些高嵌和研究机构毫不逊色 甚至在很多技术上处于领先地位 例如在2 0 0 7 年的豫e c d 视频自动搜索任 务中 微软 洲研究院和中幽科学技术大学的联合团队在所有的参赛团队中排 名第 4 视频搜索结果的重排序的关键问题 木讧首先介鲥视频搜索和重排序的 般框架 接着山一般框架引入该课题 中的关键问题和主要的研究方向 141 视频搜索和重排序的一般框架 常见的视频搜索乜括特征提取 结构分析 桃顿内存理解 排j 牛和洲览以 及重排序等主噩步骤 空 hl2 所示 盘 留f 蕾 r 一翻 口 目t 罱 圈l 2 视频搜索和重拊 的一般框架 特征提取 作为视频搜索系统中的重要基础 其后续环竹的有效性根太 程度上依赖j 一返步骤的有效性 特征提取是指通过建市从测垃空间到 特征空问的映射 得到捕述视频序列的 茄述于f 4 6 1 结构分析 土要是指分割视频的时 f 结构 n 文本搜索中 首先将文档 分解成段 客 讲句和7 词 1 刮样可以将视频史档分解成系列的片段t 如镜头 s h 0 0 关键帧 k o y f h m e 场景 s c e n e 赦事 s t o r y 等语义尊 6 趴而实现视频序列的层次化组织 使之催于随机访问 镜头定义为 摄像机一次连续拍摄的坷 间断帧序州 是视频数据流中的物理结构单元 关键帧是指在一个镜头中被挑选出束可以用采代表镜头内容的刚像 场 景定义为语义上午h 关和时间上十h 邻的若干镜头 具有一定的抽象语义 i r 日习蔫 厕 第l 章绪论 故事肇元由一组语义相关的场景组成 这些场景组合在一起可以描述 段完整的故事情节 是视频所蕴含的岗层抽象概念和语义的表达 视频内容理解 是指进行自动内容分析 跨越 语义鸿沟 实现基于 内容的处理 通过模式识别 机器学习等先进的智能信息处理方法建立 底层特征与高层信息之间的联系与映射 得到标注语义特征的概念 动 作及痔件等元数据 并根据这些高层无数据进行索引 归档 以便于后 续处理 排序和浏览 是为用户和系统之间建立一个有效的交互手段 用户利用 视频检索得到自己需要的视频内容 并可以通过视频浏览 b r o w s m 曲 快速地 线性或非线性方式 了解视频内容 用户还可以通过检索反馈实 现对查询结果进一步修正 重排序 是指基于原始搜索排序的基础上 通过挖掘数据内在关联 或 者借鉴外部知识和人工干预 对原始搜索结构重新排序的过程 目的是 提高搜索质量和提升用户搜索体验 从框架流程上来看 重排序位于视 频搜索框架的最后环节 凶而前f 酐步骤处理的好坏都会影响到重排序后 的效果 另外 对于重排序来说 前l f l 的特征提取 分层结构分析等步 骤的方法以及中间结果往往都是不透明的 凶而在重排序的过程中 往 往需要重复上新的步骤 视频内容的表达有多种方式 包括文本捕述 样例描述 草图描述等 因 此 视频检索可以分为多种类型 如关键词查询 q u e r y b y k e y w o r d q b k 样 例查询 q u e 巧 b y e x a m p l e q b e 草图查询 q u e 叮一b y s k e t c h q b s 以及它们的 组合等 在关键词香询中 用户以文字形式表示待锈询的概念 套询与该概念 相关的视频内容 在样例奁询和草图查询中 用户以样例或草图作为输入 查 询与该输入在目标纹理 颜色 形状 运动等属性上比较相似的视频 本文的 研究主要针对关键词奁询为主 样例套询为辅的重排序方法 1 4 2 关键问题及研究方向 由上一小节介绍的视频搜索和重排序的 般框架流程 可以看出对重排序 的分析和研究较人的自由度 具体来说 重排序问题的关键问题和研究方向主 要包括以下几个方面 分层结构分析 视频具有时问和空间双重埔性 与文本和吲像数据有着 很人