基于内容的视频检索

基于内容的视频检索基于内容的视频检索 曹亚光 北京理工大学现代远程教育学院 北船院 计算机专升本2001级 2001023011076 摘摘 要要 视频检索有着广泛的应用和广阔的发展前景 是当前多媒体研究领域的热点 系统地 介绍了基于内容的视频检索的一般实现步骤 从分析基于内容的视频检索的系统结构出发 全 面地探讨了系统中所涉及的视频结构的构造 镜头切变检测技术 关键帧提取技术 从视频流 中构造场景或组的技术 特征提取技术以及视频检索 浏览和检索反馈技术 重点分析了其中 一些关键技术中各种实现方法的优缺点 并介绍了一些新的技术方法 最后提出了一些需要进 一步研究的问题 关键词关键词 视频数据库 基于内容 视频检索 镜头切变检测 关键帧提取 特征提取 检索反 馈 1 1前言前言 随着多媒体技术和网络技术的飞速发展 视频在多个领域得到广泛地应用 对 这些海量的而且包含大量非结构化信息的数据进行组织 表达 管理 查询和检索 成为迫切的需求 因此基于内容的视频检索 Content Based Video Retrieval CBVR 成为近年来研究的热点 基于内容的视频检索系统如图1所示 图1 基于内容的视频检索系统框图 首先要进行视频结构分析 将视频序列分割为镜头 并在镜头内选择关键帧 这是实现一个高效的CBVR系统的基础和关键 然后提取镜头的运动特征和关键帧中 的视觉特征 作为一种检索机制存入视频数据库 最后根据用户提交的查询按照一 定特征进行视频检索 将检索结果按相似性程度交给用户 当用户对查询结果不满 意时可以优化查询结果 自动根据用户的意见灵活地优化检索结果 2 2视频结构的构造及有关的算法视频结构的构造及有关的算法 为了对视频数据库进行基于内容的查询 首要要构造便于检索的视频结构 视 频数据可以按照由粗到细的顺序划分为四个层次结构 视频 Video 场景 Scene 镜头 Shot 和图像帧 Frame 镜头是视频数据的基本单元 它代表一个场景中在时间上和空间上连续的动作 是摄像机的一次操作所摄制的视频图像 任何一段视频数据流都是由许多镜头组成 的 镜头的切换有两种 突变和渐变 突变是指从一个镜头直接切变到另一个镜头 而渐变根据视频编辑手法的不同可以分为3种 淡化 Fade 又细分为Fade in和 Fade out 融化 Dissolve 和滑变 Wipe 渐变是切变检测中的难点 整个视频结构构造过程分以下三个步骤 从视频流中提取镜头 从镜头中选择 关键帧和从视频流中构造场景或组 2 12 1 从视频流中提取镜头 即对视频流的切变检测 从视频流中提取镜头 即对视频流的切变检测 镜头是视频数据的基本单元 视频处理首先就需要把视频自动地分割为镜头 以作为基本的索引单元 这一过程就称为镜头边界的检测 它是实现基于内容的视 频检索的第一步 其核心处理是镜头切变检测 视频结构的构造中 镜头切变检测是重点 而且其算法和思想可用于其它步骤 故应重点研究 2 1 12 1 1 基于颜色特征的方法基于颜色特征的方法 1 模板匹配法 对应像素法 模板匹配法是将两帧对应像素差的绝对值之和作为帧间差 当帧间差大于某个 阈值t时 则认为有镜头的切换 模板匹配法的缺点是 由于与像素的位置密切相 关 因此对噪声和物体运动十分敏感 容易造成误识别 张宏江等人 3 提出将各帧 划分为8 8像素的子块 并对每个块取平均 再用这个平均值对前后帧的对应子块 进行比较 这种方法对小的噪声和运动不敏感 2 直方图法 直方图法是使用得最多的计算帧间差的方法 它丢失了颜色的位置信息 因而 抗噪声能力要比模板匹配强 颜色直方图法的缺点是 两幅图像可能内容完全不同 但直方图相似 也容易造成误识别 一种改进的方法是将图像划分成若干子块分别 对各子块进行匹配 A Nagasaka和Y Tanaka 4 提出了一种将视频帧划分为4 4相 同大小的子块并比较相应子块的方法 其它改进方法还有X2直方图匹配法 5 和 Swanberg等人 6 采用的模板匹配法和直方图匹配法相结合的方法 2 1 22 1 2 基于边缘的方法基于边缘的方法 由于在镜头切变时新旧边缘应在不同的位置 所以可先提取两幅图像的边缘 计算新边缘在旧边缘的基础上增加和减少像素比例 当大于某一个阈值时便认为发 生镜头切换 缺点是计算量大 当边缘不明显时效果差 2 1 32 1 3 光流检测法光流检测法 张宏江等人 3 还提出了光流检测法 该方法的原理是镜头切换时无光流 而镜 头运动应适合某种特定的光流类型 它能将渐变切换与镜头的运动区分开来 但计 算复杂且在光照变化很大情况下检测失败 2 1 42 1 4 基于模型的方法基于模型的方法 Hampapur等人 7 8 通过对视频制作过程的研究 提出了一种可用于镜头边界检 测的视频编辑模型 它的缺点是 建模过程比较复杂 需要对每种切换类型建立模 型 这种方法适用于专业领域 2 1 52 1 5 压缩域的方法压缩域的方法 由于越来越多的视频数据是以压缩的形式保存 因此 最好能直接在压缩域中 进行边界检测 1 DC系数法 DC 图像是原图像8 8的平均 它包含了原图像的基本全局信息 且具有压缩 性处理过程更加快捷的特点 可以先从各帧中提取DC图像 再用帧间差的方法进行 检测 2 运动矢量法 张宏江等人 3 根据统计发现镜头转换处的BP帧中有效运动向量个数较少 因此 可以对这些帧进行解压 用非压缩视频的边界检测方法进行镜头边界检测 文献 9 中从视频流中提取宏块的运动矢量 宏块的相似度与它们的运动矢量 成反比 帧的相似度由各宏块的相似度取平均求得 文献 10 中将各帧的类似度进 行了归一化 公式 结果是多帧类似度加权相加的结果 可以取比较简单的门限 进行判断 减少了计算复杂度 多帧加权减小了误检 但对渐变检测效果不佳 这类方法的缺点是 目前的MPEG算法是面向数据压缩的 而不是面向视频内容 表示的 随着基于内容的编码标准MPEG 4和多媒体数据内容表示MPEG 7成为国际标 准后 上述问题将得到解决 3 模糊查找法 一种方法是只用视频流中的I帧进行检测 它适用于检测精度不是很高的需求 另一种方法是先找出差异大的相邻两个I帧作为可能存在镜头切换处 再用两帧间 的B和P帧确定准确位置 这种方法精度较高 两种方法均受编码算法优劣的影响 2 1 62 1 6 几种改进的算法几种改进的算法 张宏江等人 3 提出了双阈值比较法 当两帧间差在阈值d1和d2之间时 便认为 潜在渐变开始 将差值开始累加 直到累加和大于d2时认为有渐变 当帧间差小于 d1时认为渐变结束 这种方法对渐变检测有较好的效果 但对镜头的缓慢运动仍可 能会造成误识别 Yeo B L 11 提出了一种滑动窗口检测法 先以待检的帧作为中心开一个窗 计 算各帧与邻帧的帧间差 若该帧的差值大于窗口内的其它所有帧的差值 且大于第 二大差值的某倍数 则认为是发生切换 用双重窗口法 12 可进一步改进以减小搜索量 先选取一个大的窗口 取平均 值 将大于均值一定倍数的差值作为候选切变帧 再以候选切变帧为中心取小窗口 检测具体位置 大窗口可避免误检并减小搜索量 小窗口可避免大运动造成的漏检 由于在很多情况下 人们仅对图像中的某一区域感兴趣 因此 先进行图像分 割 仅利用某一区域的信息进行检索 近几年来这一领域的研究逐渐引起了人们的 兴趣 2 22 2 从镜头中选择关键帧从镜头中选择关键帧 关键帧 也称代表帧 是用于描述一个镜头的关键图像帧 它通常会反映一个镜 头的主要内容 关键帧的使用大大减少了视频索引的数据量 同时也为检索和浏览 视频提供了一个组织框架 关键帧的提取原则是 宁滥勿缺 关键帧选取的方法 有以下几类 2 2 12 2 1 基于镜头的方法基于镜头的方法 一段视频分割成镜头后 将每个镜头的首帧 或首帧与末帧 作为镜头的关键帧 该方法实现起来比较简单 无论镜头的内容如何 关键帧的数量都是一定的 1帧或 2帧 但效果不是很稳定 因为每个镜头的首帧或末帧不一定总是能够反映镜头的 主要内容 2 2 22 2 2 基于内容分析的方法基于内容分析的方法 这种方法基于每一帧的颜色 纹理等视觉信息的改变来提取关键帧 当这些信 息有显著变化时 当前的帧即可作为关键帧 张宏江等人 3 依据帧间的显著变化来 选择多个关键帧 首先把镜头的第一帧作为关键帧 然后计算前一个关键帧与剩余 帧之差 如果差值大于某一阈值 则再选取一个关键帧 这种方法可以根据镜头内 容的变化程度选择相应数目的关键帧 但所选取的帧不一定具有代表意义 而且在 有镜头运动时 容易选取过多的关键帧 帧平均法和直方图平均法 13 统计所有帧的像素值或直方图平均 取最接近平 均值的帧作为代表帧 2 2 32 2 3 基于运动分析的方法基于运动分析的方法 Wolf 14 通过光流分析来计算镜头中的运动量 在运动量取局部最小值处来选 取关键帧 它反映了视频数据中的静止 视频中通过摄像机在一个新的位置上停留 或通过人物的某一动作的短暂停留来强调其本身的重要性 Wolf的这种基于运动分 析的方法可以根据镜头的结构选择相应数目的关键帧 如果先把图像中的运动对象 从背景中取出 再计算对象所在位置的光流 可以取得更好的效果 合成法将镜头中的所有运动转换拼接成一个合成帧作为关键帧 2 2 42 2 4 基于聚类的方法基于聚类的方法 聚类提取 15 的方法首先要确定一个初始类心 然后根据当前帧与类心的距离 来判断是归为该类还是作为新的类心 再将镜头中帧分类后取各类中离类心最近的 帧作为关键帧 另外 Zhao 16 提出了一种基于最近特征线 Nearest Feature Line NFL 的端点检测算法用于选取关键帧 该方法的主要原理是用某些特征点 的连线 特征线 近似并代表某个类的所有特征样本轨迹 而这些特征点就是关键帧 2 32 3 从视频流中构造场景或组从视频流中构造场景或组 计算镜头间的相似性 实际是关键帧间的比较 选择合适的聚类算法进行分 析 按时间顺序和关键帧的相似程度可分为场景 17 也可以只按关键帧的相似程 度进行分组 3 3 特征提取特征提取 视频分割成镜头后就要对各个镜头进行特征提取 得到一个尽可能充分反映镜 头内容的特征空间 这个特征空间将作为视频聚类和检索的依据 特征提取包括关 键帧中的视觉特征和镜头的运动特征的提取 3 13 1 颜色特征颜色特征 颜色是图像最显著的特征 与其它特征相比 颜色特征计算简单 性质稳定 对于旋转 平移 尺度变化都不敏感 表现出很强的鲁棒性 颜色特征包括颜色直 方图 主要颜色 平均亮度 3 等 其中利用主要颜色和平均亮度进行图像的相似匹 配是很粗略的 但是它们可以作为层次检索方法的粗查 对粗查的结果再利用子块 划分的颜色直方图匹配进行进一步的细查 为了能够在大规模图像数据集中进行快 速的搜索 Smith和Change 18 等人提出了颜色集的概念 首先将RBG颜色空间转换 为视觉上一致空间HSV 然后量化为m个颜色条 颜色集就定义为量化后的颜色空间 中颜色的一种选择 由于颜色集特征向量是二叉的 因而可以通过构造二叉树来进 行快速的搜索 3 23 2 纹理特征纹理特征 20世纪70年代初Haralick 19 等人提出了纹理特征的共生矩阵表示法 即利用 纹理在灰度级的空间相关性 先根据图像像素间的方向和距离构造一个共生矩阵 再从中提出有意义的统计数据作为纹理的特征表示 该方法的缺点是这些统计特征 没有和人在视觉上对纹理特征的感知之间建立对应 于是不少人提出了其它的纹理 特征度量方法 其中Tamura提出的纹理特征集可以很好地与人类视觉感知相对应 这些特征包括 粗糙度 对比度 方向性 线像度 规则性 粗略度 其中最重要 的特征是纹理粗糙度 对比度和方向性 另外 许多研究者开始将小波变换应用于纹理特征表示 Manjunath等人对三 种小波变换方法 角 树结构 Galbo 做了比较之后 发现Galbo小波变换最符合人 类视觉特征的表达 随着小波理论的建立 Gross M IT 20 等人提出了基于小波的 纹理表达 参考文献 21 中有综合性的描述 3 33 3 形状特征形状特征 形状分析首先需要采用合适的图像分割算法把不同对象从图像中分割出来 再 用各种方法进行匹配测量 形状特征表示的一个重要准则是要求对位移 旋转 缩 放的不变性 通常形状的表示可以分为基于边界和基于区域两类 它们分别采用傅 里叶 21 描述和矩不变量 22 表述特征 另外新的研究方向有弹性变形模板和边界方 向直方图 最近的表达方法还有Chamfer匹配 23 Borgerfos提出的层次Chamfer匹 配算法 以及Wallace和Mitchell提出的局部形状分析算法的3D形状表达 3 43 4 运动特征运动特征 运动特征是视频镜头的重要特征 它反映了视频的时域变化 也是用视频例子 进行检索的重要内容 运动分析的方法有基于光流方程的方法 基于块的方法 像 素递归方法和贝叶斯方法 24 等 但这些方法计算量大 于是 Tonomura等人 25 提 出了X线断层分析的方法 将整个视频序列沿时间轴进行切片 从切片图像中分析 运动情况 Patel和Sethi 26 提出利用MPEG中的B和P帧的运动向量来避免光流计算 和块匹配 该方法利用宏块的运动得到一个有九个分量的特征向量 再用这个特征 向量判断镜头的运动 张宏江等人 3 用计算镜头内各帧平均亮度和主要颜色的均值 和方差作为镜头运动量大小的度量 在新闻视频中取得了较好的效果 3 53 5 其它其它 其它的特征主要有物体间的方位关系 特征点 即满足一定要求的像点 如曲 线交点 基于目标的特征等 目前研究得较少 4 4 视频检索和浏览视频检索和浏览 在对视频流中各镜头提取关键帧并进行特征提取后 还要建立基于视频特征的 索引 通过索引 就可利用基于关键帧特征 或是基于镜头动态特征 或是将二者 相结合进行对视频进行检索和浏览了 于内容的检索是一个近似匹配 逐步求精的 循环过程 主要包括初始查询说明 相似性匹配 返回结果 特征调整 人机交互 检索反馈等步骤 直至获得用户满意的查询结果 1 基于关键帧的检索 视频被抽象为关键帧后 搜索就变成按照某种相似度来检索数据库中与查询描 述相似的关键帧 通常使用的查询方法是通过目标特征说明 直接 的查询和通过可 视实例 示例 的查询 检索时 用户也可以指定使用特定的特征集 如果检索到关 键帧 用户就可以利用播放来观看它所代表的视频片断 浏览可以跟随检索 作为 检验检索到的关键帧的上下文边界联系 浏览也可以初始化查询 即当浏览时 用 户可以选择一个图像来查询所有与该图像相似的关键帧 2 基于镜头动态的检索 基于镜头和主体目标的运动特征来检索镜头是视频查询的进一步要求 可以利 用摄像机操作的表示来查询镜头 可以利用运动方向和幅度特征来检索运动的主体 目标 在查询中还可以将运动特征和关键帧特征结合起来 检索出具有相似的动态 特征但静态特征不同的镜头 3 视频浏览 对于视频来说 浏览与有明确目的的检索同样重要 浏览需要视频具有在语义 层次上的表示 有学者提出了场景转换图 STG 的概念 以一个有向图的节点表示 场景 边表示时间上的转换 通过对STG的化简 可以去掉不重要的镜头 得到视 频的紧凑的表示 由于单纯从图像从获得语义信息非常困难 也有学者提出了综合 采用视频中的图像 语音以及文字信息的方法 4 视频的检索反馈 在检索的实现中除利用图像的视觉特征进行检索外 还应根据用户的反馈信息 不断学习改变阈值重新检索 实现人机交互 直到达到用户的检索要求 如何定义是否两个视频相似 仍然是尚未解决的问题 限制了检索系统的应用 范围 而且由于视频内容的复杂性 不同用户在检索过程中 即使对同一部视频 其注重的角度也有可能不同 因此接受用户的反馈意见 当用户对查询结果不满意 时可以优化查询结果 突出用户的需要 在综合了人类视觉心理特征的基础上 介 绍了一种视频相似衡量的模型 从镜头 视频等多个层次 多种视觉判断角度 对 视频间相似度进行衡量 并在此基础上提出了从多个粒度 镜头层次和视频层次 进行检索反馈的方法 整个过程是自动进行的 根据用户的意见灵活地优化检索结 果 5 5 总结与讨论总结与讨论 基于内容的视频检索技术是一种综合集成技术 其一些关键技术如镜头边界检 测 关键帧提取 特征提取等的研究虽然取得了一定的进展 但由于各种理论和相 关技术都不尽完善 所以还有许多问题需要进一步深入研究 1 提高识别率 尽管目前已有多种算法 对突变切换和简单的渐变切换识别率可以达到80 以 上 但由于视频内容的丰富性 尚存在许多问题 如大物体和镜头运动的区分 高 速的物体或镜头运动 灯光背景的照射和闪烁 复杂的剪辑效果 如碎裂 波纹 变形等 等复杂情况下 误识别和漏识别率普遍较高 镜头的检测所用到的颜色 纹理 运动等特征还用于最后的检索处理 因此 有必要对镜头切换识别进行重点 研究 2 合适阈值的选取 阈值选取不当会造成误检和漏检 有的视频变化缓慢 应选取较小的阈值 反 之则应选取较大的阈值 从而应不断地试验 尽量达到均衡 并综合利用人的知识 进行人机交互式学习选取合适的阈值 以上所介绍的各种方法多受阈值选取优劣的 限制 近年来趋向于更加鲁棒性的研究 如利用K均值法的检测 28 可以减少阈值 选取的限制 3 提高速度 由于视频的数据量大 处理时间长 算法处理的速度也很重要 由于大量的视 频数据是以压缩形式存放的 直接对压缩数据进行处理可以节约时间 目前 很多 算法的识别速度与实际应用相距还很远 4 有效的特征提取 特征提取是基于内容的视频检索技术的关键 以往的研究主要集中在颜色 纹 理 形状等低级特征上 但这些特征不能完全准确地描述出图像的含义 如何提取 高级特征使检索更接近人类视觉生理 心理特点是一个研究课题 另外由于视频数 据具有时空性 如何更好地提取物体和对象的运动特征也是一个研究课题 5 高层语义检索 目前在切变检测和检索算法中底层语义特征比较成熟 检测结果比较理想 故 用得最多 但高层语义 如用户感兴趣的事件 运动 物体特征的变化等等 也是 用户的检索需求 在实际的视频检索服务中 用户的最终要求是能够直接访问视频 中的对象 如对某种动物行为现象的收集 某个球星历次参赛录像的查询等 这些 要求更多的是从高层语义出发的检索方式 基于对象的检索 高层语义和低层特征 的关联 视频数据高级语义的提取都是视频检索算法方向 6 综合的多特征检索技术 声音和文字是伴随视频的高层次内容 包含着与其密切相关的许多信息 它们 还间接地对视频分类 场景分割 对象识别等起很大作用 因此 在视频检索中加 入声音和文字信息辅助检索能大大简化视频处理的复杂度 增加视频检索的效率 是完善基于内容的视频检索技术的可行方法 7 检索效果的评价尚没有标准 由于视频内容的丰富性和复杂性 以及人对视频内容评判的主观性 使得其检 索性能的优劣很难有一个统一的标准 这也是CBVR技术研究的一个方向 目前主要 使用多媒体信息检索中的两个指标 查全率 recall 和准确率 precision 定义为 recall correct correct missed precision correct correct falsePosition 其中 correct为正确检测到的数目 missed为漏检的个数 falsePosition为 误检的个数 参考文献 参考文献 1 张洪德 刘雨 唐波 基于内容的视频检索技术研究 电视技术 2001 6 30 39 2 陆燕 陈福生 基于内容的视频检索技术 计算机应用研究 2003 11 1 4 3 Zhang H J Wu Jianhua et al An Integrated System for Content Based Video Retrieval and Browsing J Pattern Recognition 1997 30 4 643 657 4 A Nagasaka et al Automatic Video Indexing and Full Video Search for Object Appearances C Second Working Conference on Visual Database Systems IFIP WG2 6 1991 119 133 5 Haitao Jiang Abdel Salam Helal Scene Change Detection Techniques for Video Databases System Multimedia Systems 1998 6 186 195 6 Deborah Swanberg Chiao Fe Shu Ramesh Jain Knowledge Guided Parsing in Video Database C Storage and Retrieval for Image and Video Databases Proc SPIE 1908 1993 13 24 7 Song S Moon Ho et al On Detection of Gradual Scene Changes for Parsing of Video Data C Storage and Retrieval for Image and Video Databases Proc SPIE 3312 1998 404 413 8 Hampapur A et al Digital Video Segmentation C Proc Second Annual ACM New York NY USA 1994 357 364 9 Zhang H J Kankanhalli A Smoilar S W Automatic Partitioning of Full Motion Video Multimedia System 1993 10 28 10 一种新的基于运动矢量的MPEG视频码流cut检出算法 Journal of Image of Graphics 1999 4 323 326 11 Yeo B J Liu B Rapid Scene Analysis on Compressed Video IEEE Trans Circuits and Systems for Video Technology 1995 5 533 544 12 陆海斌等 一种高效的视频切变检测算法 图形图像学报 1999 4 805 809 13 Bilge Gunsel Tekalp A Murat Content based Access to Video Objects Temporal Segmentation Visual Summarization and Feature Extraction Singal Processing 1998 66 261 280 14 Wolf Wayna Key Frame Selection by Motion Analysis On Proc of IEEE Int Conf On Acoustics Speech and Signal Processing ICASSP Atlanta 1996 7 10 15 Yueting Zhuang Yong Rui Huang T S Adaptive Key Frame Extraction Using Unsupervised Clustering In Proc IEEE Int Conf on Image Proc Chicago USA 1998 76 81 16 L Zhao et al Key frame Extraction and Shot Retrieval using Nearest Feature Line NFL C Proc of International Workshop on Multimedia Information Retrieval in conjunction with ACM Multimedia Conference 2000 Los Angeles USA 2000 217 220 17 Yong Rui Huang T S et al Exploring Video Structure Beyond the Shots In Proc IEEE Conf on Multimedia Computing and System Austin Texas USA 1998 54 57 18 Smith J R Chang S F Single Color Extraction and Image Query In Proc IEEE Int Conf on Image Proc 1995 80 88 19 Haralick R M Shanmugam K Dinstein I Texture Features for Image Classification IEEE Trans on Sys Man and Cyb 1973 SMC 3 6 768 780 20 Gross M IT Koch R Lipper