（信号与信息处理专业论文）基于自适应网格的视频对象分割与追踪.pdf

一1 一 基于自适应网格的视频对象分割与追踪 摘要 随着m p e g 一4 和m p e g 一7 标准的逐步推广，视频对象分割的 问题也就逐渐成为视频应用领域中的一个很重要的研究课题。 目前，国际上许多研究机构都在进行这方面的研究，并提出了 一些解决办法，主要分为两大类：自动分割方法与半自动分割 方法。自动分割的方法是指由计算机自动探测并追踪视频对 象。由于计算机无法确切理解“语义对象”的概念，因而也就 无法自动有效地找到我们所需的视频对象。所以，从目前来讲， 采用自动分割的方法带有很大的局限性。而由用户的辅助来获 取视频对象的半自动分割方法则具有更大的实用性。厂一、一一 本文首先对一些重要的运动分割和视频对象分割算法作 了一个简单的比较分析，然后在此基础上提出了一种新的、基 于自适应网格的半自动视频对象分割方法。该方法主要包括两 个步骤：在初始帧中应用自适应网格算法分割视频对象；在后 续帧中应用h w s 光流分析法跟踪对象并调准对象轮廓。整个系 统的核心在于自适应网格算法的应用。它能够给出对图像内容 的匹配描述，并保留对象的所有轮廓信息。整个自适应网格算 法包括两部分：网格的产生和网格的融合。f 网格的产生是根据 图像的彩色特征与同一性标准的比较来递归二分根三角形而 得到的。网格的融合是网格产生的逆过程。在应用该算法前， 采用相应的滤波技术及彩色空间变换技术将图像简单化，使得 图像内容更趋向于同一。算法结束后，采用一定的后处理措旖 来优化分割结果。对象的初始模型是由用户的辅助来获得的。 在后续帧中，系统采用h - s 光流分析法来估计运动场，然后根 据初始的对象模型来进行跟踪，并根据每一帧的自适应网格分 割结果来调准对象轮廓，从而不断更新对象模型。最后，根据 ? 。i 。一一一一 。逡潮懿眺涵。， 对象模型提取出相应的视频对象。系统执行过程中，误差的控 制是由算法的优化以及用户的交互来实现的实验结果表明了 这种方法的有效性。卜一一 关键词：视频对贰用户辅助，自适应网格i 自动半自麴坌趔y h - s 光流v 追踪 v i d e oo b j e c t s e g m e n t a t i o n a n dt r a c k i n gb a s e d o na d a p t i v em e s h w 汕t h ep o p u l a r i t yo fm p e g - 4a n dm p e g 7s t a n d a r d s ，v i d e oo b j e c t ( v o ) s e g m e n t a t i o nb e c o m e s av e r y c h a l l e n g i n g r e s e a r c ha r e a i nv i d e o a p p l i c a t i o n a tp r e s e n t ，m a n yi n s t i t u t e si n t h ew o r l da r ed o i n gt h er e s e a r c h ， a n dh a v e p r o v i d e ds o m e m e t h o d st os o l v et h ep r o b l e m t h e s em e t h o d sc a nb e s u m m a r i z e di n t ot w ot y p e s ：a u t o m a t i cs e g m e n t a t i o na n ds e m i - a u t o m a t i c s e g m e n t a t i o n a u t o m a t i cs e g m e n t a t i o n i so n em e t h o dt h a t a u t o m a t i c a l l y d e t e c t sa n dt r a c k sv i d e oo b j e c t s i n c ec o m p u t e rc a n tu n d e r s t a n d “s e m a n t i c o b j e c t ”e x a c t l y , i t c a l l tf i n do u rd e s i r e dv i d e oo b j e c t a u t o m a t i c a l l ya n d p r e c i s e l yt h e r e f o r e ，a p p l i c a t i o n o fa u t o m a t i c s e g m e n t a t i o n i sl i m i t e d r e c e n t l y , w h i l es e m i a u t o m a t i cs e g m e n t a t i o nw i t hu s e r a s s i s t a n c ei s m o r e p o p u l a r i na p p l i c a t i o n i nt h i s p a p e r , ab r i e fr e v i e ws u m m a r i z e ss o m eo ft h e m o s ti m p o r t a n t m o t i o ns e g m e n t a t i o na n dv i d e oo b j e c ts e g m e n t a t i o nt e c h n i q u e s t h e n ，an e w a d a p t i v e - m e s h - b a s e ds e m i - a t t t o m a t i cv i d e oo b j e c ts e g m e n t a t i o nt e c h n i q u ei s p r e s e n t e d t w om a i ns t e p s a r ei n c l u d e di n t ot h et e c h n i q u e ：s e g m e n tv i d e o o b j e c ti nt h ef i r s tf l a m ew i t l la d a p t i v em e s ha l g o r i t h m ；t r a c kv i d e oo b j e c t w i t hh - so p t i c a lf l o wa n a l y s i sa n da d j u s t o b j e c t s c o n t o u ri n f o l l o w i n g 矗a m e s t h ec o r eo ft h e t e c h n i q u ei sa d a p t i v em e s ha l g o r i t h m w h i c hm a t c h e s t h ew h o l ei m a g ea n dc o n t a i n sa l li n f o r m a t i o na b o u to b j e c t sc o n t o u r t h e a d a p t i v em e s ha l g o r i t h mc o n s i s t so f t w op a r t s ：m e s hg e n e r a t i o na n dm e s h m e r g i n g a d a p t i v em e s h e sc a l lb eg e n e r a t e db y r e c u r s i v es u b d i v i s i o no fr o o t t r i a n g l e s ，b a s e do n t h ec o m p a r i s o nb e t w e e ni m a g ec o l o ri n f o r m a t i o na n dt h e c r i t e r i o nf o rh o m o g e n e i t y m e s hm e r g i n gi so n er e v e r s ep r o c e s st om e s h g e n e r a t i o n b e f o r et h e m e s ha l g o r i t h m ，t h e i m a g ei ss i m p l i f i e db ys o m e f i l t e r i n gt e c h n i q u e sa n dc o l o rs p a c et r a n s f o r m a t i o nt e c h n i q u e ，a n db e c o m e s m o r eh o m o g e n e o u s a f t e rt h e a l g o r i t h m , o n ep o s t - p r o c e s s i n gt e c h n i q u ei s a p p l i e d t o o p t i m i z e t h e s e g m e n t a t i o nr e s u l t t h e i n i t i a l o b j e c t m o d e li s p r o d u c e db yu s e r s a s s i s t a n c e i nf o l l o w i n gf r a m e s ，t h es y s t e me s t i m a t e s m o t i o nv e c t o rf i e l dw i t hh so p t i c a lf l o w a l g o r i t h m , t r a c k sv i d e oo b j e c tb a s e d 0 1 at h ei n i t i a lo b j e c tm o d e l ，a d j u s t so b j e c t sc o n t o u rb a s e do nt h er e s u l to f a d a p t i v e m e s hs e g m e n t a t i o no ne v e r yf r a m e ，a n du p d a t e s o b j e c t m o d e i f i n a l l y , v i d e oo b j e c t i se x t r a c t e d b yo b j e c tm o d e l d u r i n gt h ec o u r s eo f r u n n i n gt h es y s t e m ，e r l o r sa r ec o n t r o l l e db ya l g o r i t k m so p t i m i z a t i o na n d u s e r si n t e r a c t i v i t y e x p e r i m e n tr e s u l t sd e m o n s t r a t et h ep e r f o r m a n c eo fo u r a l g o r i t h m k e yw o r d s ：v i d e o o b j e c t ，u s e r sa s s i s t a n c e ，a d a p t i v em e s h ， a u t o m a t i c s e m i - a u t o m a t i cs e g m e n t a t i o n ， h - s o p t i c a lf l o w ，t r a c k i n g 圭查奎墨查茎堡主兰丝兰苎j ! l 羔l ! i 一 1 1 问题的提出 1 绪论 长久以来，分割这个概念一直是图像处理中的核心问题。过去，人们总是把它和 图像分析紧密地联系在一起，并根据不同的应用场合提出了许多静态图像的分割算 法，比如：卫星图像和医学图像的分析、加工过程的控制等等。这些方法各自都是基 于不同的图像模型、利用不同的特性，有各自一定的适用范围和优缺点。事实上，到 目前为止，仍然无法找出一种普遍适用的分割算法来解决这个图像处理课题中的核心 问题。 随着计算机这个强大的辅助工具在各行各业的逐渐普及，分割问题不再仅仅局限 于静态图像领域，同时也在视频领域得到要求。由于多媒体技术和网络技术的发展， 以及一些特殊的视频处理应用场合的需要，如何在视频序列中引入用户对某些感兴趣 的对象( 视频对象) 的交互也就成为视频处理中比较热门的课题，特别是i v i p e g - 4 和 m p e g - 7 标准的提出，使得视频领域的分割问题变得更为迫切。 可能是受静态图像分割算法的影响，在过去的二十多年里，人们一喜在致力于自 动分割视频对象的算法研究，并取得了相应的成果，而把用户的介入看成是所用方法 的负面特征。( 值的一题的是，甚至m p e g - 4 核心实验n 2 也被称为是“自动分割算 法的比较”。) 然而，应当指出的是，许多自动分割方法都有一个共同的弱点：方法执 行的效果依赖于太多的参数。而这些参数仍需要由用户来设置。这种细调的过程从某 种程度上可以把它作为一种隐性的交互。因此，在处理视频分割的问题时，适当地引 入用户的交互不但可以使算法变得简单，而且可以通过用户的校正得到更好的处理结 果。目前，在处理过程中加入某种形式的交互已经成为共识。在任何一种算法中，与 不同类型的信息进行交互的可能性代表的是该算法肯定性方面的一个附加值，而不是 它的局限性。 所以，如何找到一种有效的方法来分割视频对象是我们课题研究的主要目标。在 算法执行过程中，应当能够适当地引入用户的交互。 tj 、 遴凌燃酝赫戳 ；一f 一j j 瀚滋测滋 奇 圭塑奎墨奎兰堡主兰垡兰兰苎= 兰整丝一 1 2 相关背景的介绍 始于7 0 年代的数字视频处理技术至今为止已经经历了将近3 0 年的发展，并形成 了专门的研究领域( 参考文献【l 】) 。服务于该领域的m p e g 、1 t u 等专家组通过制定 一系列标准使得整个数字视频处理技术向着标准化、通用化的方向发展目前已有的 视频标准主要有：m p e g - 1 2 ，m p e g - 4 7 ，h 2 6 1 h 2 6 3 ，等等正在发展的有m p e g - 2 1 等。每一标准的制定总是和相应的技术发展以及社会的需要相对应，同时也是人们对 视频处理技术要求的集中反映。 相对来说，d p e g - i 2 ，h 2 6 1 h 2 6 3 视频标准在经历了一段比较长的发展时期后， 各方面的技术变得比较成熟，应用也很普遍。从8 0 年代初期出现的第一套视频会议 系统开始，随后又立即出现了压缩光盘这一高效的信息载体，从而使得利用c d - r o m 光盘进行视频存储和放像的技术变成现实。继m p e g - 1 标准推出后，m i ： e g 专家组 又制定了m i ： e g - 2 标准，这就使现存的模拟电视系统数字化成为可能，并有力地促进 了广播电视事业的发展，使广播电视系统可以通过卫星、电缆和地面u h f 网络同时 广播多套电视节目。然而，由于这些标准的制定是为了提高数据的压缩比率，是一种 压缩编码标准，而且整个过程的处理是基于帧实现的，因而在过程中无法实现基于内 容的交互控制。也就是说，m p e g - 1 、m p e g - 2 标准均为高层媒体的表示与结构标准， 其交互性及灵活性较低。这从场景分割或场景分析的要求上讲，应该是属于比较低级 的技术。 随着网络技术和多媒体技术的发展，如何实现对自然的和合成的视觉对象( 包括 视频、动画、图片和文本) 进行有效控制、压缩和索引也越来越受人们的关注。为了 实现这一目标，m p e g 专家组于1 9 9 4 年开始制定全新的m p e g - 4 标准，并于1 9 9 9 年1 月批准为国际标准。紧接着，又制定并通过了m p e g - 7 标准。m p e g - 4 标准是一 个多媒体标准。它兼顾了工具、算法、层面三个方面的编码对象，是一个包括了未来 编码技术发展的开放式标准。m p e g - 7 标准是多媒体描述接口标准。它将对各种不同 类型的多媒体信息进行标准化的描述，并将该描述与所描述的内容相联系，以实现快 速有效的搜索。m p e g - 4 标准的核心在于“音视频对象”的概念引入( 参考文献 2 】) 。 所谓的“视频对象”实际上是一种语义视觉信息，它代表着输入数据中的一个有意义 的实体。比如：一个小球、一架飞机、一幢建筑物、一个人等等都代表着自然界中的 一些有意义的实体语义视频对象是一个在许多领域都很有用的概念在广播和通讯 澎糍 掰，誓蕊辩；。蠡黼& 舔懿遂意氛 圭堂塞里查茎堡圭兰堡垒苎 一j 生j 巳- 蔓! ! 一 领域，压缩比总会受到人们的普遍关注而视频对象的引入就很有可能能够提高存储 和传输的编码效率。在计算机领域，引入视频对象后，在静态或动态场景中有效地控 制和搜索感兴趣的对象就成为可能。由于m p e g - 4 是基于对象的标准，能够满足用户 对相应视频信息的控制，所以可以说它是一种比较高级的视频处理技术。 然而，在实现基于视频对象的功能描述之前，一个很重要的问题就是：如何提取 或分割视频对象。庆幸的是，如今的电影、电视中有很多片断都是蓝荧幕的( 以蓝色 为主色调) 。也就是说，单个的视频对象是在蓝背景下用分离的镜头拍摄的。比如电 影中演员的特技动作、电视中的天气预报等都是这方面的例子。这时候只要通过分割 主色调就有可能提取出所需的视频对象。但对于其它的( 非主色调) 视频信号源，要 准确地提取出所需的视频对象就是一个很棘手的问题。正如前面所提到的一样，虽然 国际上已经有很多研究人员提出了各种各样的方法来解决这个问题，其中包括自动分 割方法和复合用户辅助的半自动分割方法，但仍无法找到一种普遍适用的方法。 1 3 本文的结构 这篇文章的大体结构如下。在第二章，我们首先从运动分割开始，详细地分析了 目前国际上已经提出的一些比较有效的运动分割和视频对象分割算法。随后给出了我 们整个系统设计方案的形成过程，最后对该系统框图作了简单分析。在第三章，我们 对自适应网格算法作了理论上的研究与分析。从第四章开始，我们进入系统每一步的 音析，首先详细描述了静态帧图像分割的原理以及实现过程，包括图像的预处理过程 和用户的辅助过程。随后在第五章，我们对动态的追踪系统作了描述。最后，对整个 研究做出总结。 3 圭堂壅苎查兰堡主兰竺丝苎 一j 笠! l 墨簦盟查墨丝! ! 一 2 系统的方案设计 2 1 视顿对象分割算法的研究现状 将分割问题引入视频领域后，运动便以其不可取代的重要性而成为视频对象分割 系统中的主要特征，相应地，运动信息也就成为许多视频分割算法中首先要考虑的线 索。事实上，对视频对象分割问题的研究总是从运动分割开始的。在过去的十几年里， 基于对象运动信息的分割处理技术得到了很大的发展。针对不同的应用，人们提出了 许多不同的运动分割算法( 参考文献【1 】【3 】【1 9 】) 。 贝叶斯法是一种很流行的运动分割方法。它有一套很严谨的理论推导形式。该算 法的核心思想是：对于给定的观察场0 ，寻找使后验概率最大的分割标记x ，也即， 寻找x ，使得p ( x i d ) o c 尸( 0 | x ) p ( x ) 。m u r r a y 和b u x t o n 【4 】首先提出了m a p 分割法。这里用分段的二次流场模拟光流数据，并将这估计的光流场作为观察场0 。 和其它方法一样，为了保证分割标记x 的连续性，算法假设分割模型( 或者说先验 模型) 是一马尔可夫随机场( i v i r f ) 的取样，因而e ( x ) 服从吉布斯( g i b b s ) 分布【l 】。 算法中m r f 的能量方程包括三部分：空间平滑项、时域连续项以及一个允许不连续 运动的线性场。为了定义观察模型p ( o l z ) ，算法采用了线性回归的方法来计算每一 区域的：次流场模型的参数。同时，算法还将合成流场与观察场0 之间的误匹配假 。设为零均值高斯白噪声最后，采用模拟退火的方法来使后验概率函数最大化。这种 方法最主要的缺陷在于计算的复杂性，而且，对于视频系列中可能由该算法找到的对 象个数必须预先指定。 在b o u t h e m y 和f r a n c o i s 5 】所建议的分割系统中采用了同样的方法。他们的算法 中m r f 能量方程仅包括空间平滑项。观察场0 包含了强度函数的时空梯度，这和光 流约束方程所包含的信息是一样的。对于每一区域，计算最小均方意义上的仿射运动 参数，并用合成流场与观察场o 之间的偏差来定义模型p ( 0i ，在这里仍假设这个 偏差满足零均值高斯白噪声分布。优化法采用迭代模型( i c m ) 来实现。i c m 方法能 够减少随机模拟退火法的计算量，因而比模拟退火法收敛的块，但有可能陷入局部最 圭苎皇塑查兰要主兰堡堕苎一曼三兰j 塑竺型塑型! i l 小值。在算法中，为了获得时域上的连续性，前一帧的分割结果被用作当前帧的初始 估计。这样，整个系统就不停地在分割标记x 的更新、仿射运动参数估计、l 夏域数 目更新三个过程中切抉。 从这两种算法来看，由于它们仅仅把光流数据作为分割判断的依据，因而算法的 效果必然会因为光流场估计的准确性而受到限制。相比之下，c h a n ge t c 6 】在观察场 中引入强度信息。他的算法中m r f 能量方程包括空间连续项和运动补偿的时域项， 用以加强时域的连续性。同时假设观察流与合成流间的偏差以及像素灰度级与区域平 均灰度级之间的差分皆服从零均值高斯分布。通过控制这两种分布的方差，可以给光 流数据或强度数据赋予不同的权重值。当光流数据比较准确可靠时，也就是说位移帧 差的值比较小时，它们将被赋予更大的权重值。而当光流数据不可靠时，更大的权重 值将赋给强度数据。后来，考虑到所估算的光流场对分割的重要性，为了得到最佳结 果，一些研究人员提出了同时进行估算和分割的算法 1 】，这种算法提供了改进的光 流估算，能够获得比较满意的结果。从上面的分析来看，这些利用了贝时斯定理和马 尔可夫随机模型的技术看起来似乎比一些特别的方法更合理，而且它们能够很容易地 获得时间和空间上的连续性。然而，由于很高的计算量，以及许多算法中区域或对象 的数目可能需要预先指定的问题，使得贝叶斯法盼应用受到很大的限制。 后来，随着视频处理技术的发展，形态处理方法在分割与编码领域受到了越来越 多的关注。比如，分水岭算法( w a t e r s h e da l g o r i t h m ) 、图像简单化滤波就是形态处理 方法的应用。s a l e m b i e r 和p a r d a s 7 建议了一种典型的采用形态处理技术的分割算法。 首先，算法采用“重构开闭”形态滤波器来简单化图像，从而去处图像上一些小的 亮块或暗块。这些小块的大小与形态处理所采用的结构元素的大小有关。经过简单化 后的图像在彩色或强度上比较同一这种形态滤波器最大的优点在于它们不会像低通 滤波器或中值滤波器那样模糊或改变对象轮廓。接下来便是采用定的算法来探测同 一性区域，从而提取出相应的分割标记，然后将每一个所提取出的分割标记作为相应 区域的种子点。最后，采用分水岭算法来给那些未分割的像素分配相应的标记，这和 区域生长方法类似。之后，c h o ie t c f s 又建议了一种新的形态视频分割算法。算法中， 他们的标记提取过程主要是探测那些不仅在亮度上，而且在运动上皆具有同一性的区 域，即所谓的联合标记。同样地，分水岭算法也采用了亮度与运动联合的周一性标准。 最后，算法将那些具有相同仿射运动的区域融合起来，从而使结果简单化。这个算法 圭堂塞墨查兰塑主兰丝堡奎墨三兰j 望堕堕茎望! l 的缺陷在于缺乏时域上的对应，以至于无法及时保证时域上的连续性比_ 较于贝叶斯 方法，形态分割技术不仅运算简单，而且也不必预先给定区域或对象的数量，因为它 可以通过标记或特征提取算法自动获得。然而，从分水岭算法的根本上讲，由于它仍 是一种近似于区域生长的方法，因而必然会遇到区域生长技术有关的各种问题【9 】。 到此为止，我们所讨论的算法还是集中在编码领域。它们把视频序列分割成许多 具有同一性的区域，这种同一性可以是运动、彩色或亮度等特征。而对于m p e g - 4 标准中所提到的基于内容的功能，则需要我们把视频帧分割成一个个的对象，这些对 象相对于人而言都是有一定语义的。因此，我们前面所提到的一些分割技术在一些实 际情形中往往是不够的，因为语义对象与那些基于简单特征( 如运动、彩色) 的分块 区域并不是完全对应的。近几年来，随着m p e g - 4 标准的发展，又有许多新的分割算 法被提出来，这些算法大多数都特别强调了视频对象平面( v o p ) 的产生这个核心问 题。 w a n g 和a d e l s o n 1 0 提出了图像系列分层描述的概念，这与m p e g - 4 中的v o p 技术是一致的。在他们的系统中，当前帧根据运动信息而分割成相应的对象或层，这 些对象或层的运动都是以仿射变换模型为基础的。算法首先估算光流场，然后再将帧 图像子分成规则的方块。对于每一块，采用线性回归的方法计算仿射运动参数，从而 得到一组初始的运动假设。接着，采用递归的自适应k 均值聚类算法对所有像素进 行分组。当像素( x ，y ) 处的光流数据与从层i 的仿射参数合成的流矢量之间的差分 比与任何其它的层之间的差分要小，那么像素( x ，y ) 就认为属于层i 。为了形成这 些层，有必要利用到长视频系列的信息。这些视频帧皆按照层的仿射运动进行变换， 从而将具有相同运动的对象排列在一起。然后再采用一个时域中值滤波器用以获得每 一个对象单独描述的图像。这个算法有几个不足的地方。如果在一个系列中存在着同 一个对象不同观察角度的图像，该算法就无法用一幅单一的图像来表述这个对象。而 且，当对象的非刚体运动十分明显时，算法中采用的仿射运动模型也无法对其进行描 述。光流估计的准确性也对该算法产生影响。同时，算法中要用到长系列图像，这就 使得层的构造过程无法实时执行。 由于自动化概念的优越性，自动分割方法( 1 2 】 1 6 】) 一直是视频对象分割领域的 一个重要分支，人们对该种方法所做的努力甚至远远超过其它方法，这是因为它代表 着技术发展的趋势。m e c h 和w o u b o m 1 1 提出了从估计的变化探测模板中( c d m ) - 6 圭塑奎塑查兰堡圭兰垡兰苎 一j 苎三苎2 塑堕堕墨堡! ! 一 产生视频对象面或对象模板的方法。开始时，使用一个全局门限在连续的两帧中隶差 分，从而产生变化探测模板( c d m ) 。随后，采用一种递归松弛算法来实现该模板的 精确化，同时，算法还采用了局部自适应门限来加强空间的连续性a 图像简单化采用 了形态闭运算的处理方法，用以去除小区域而获得最后的c d m 。最后，去除c d m 中显露的背景，获得对象模板这种算法也是i s o m p e g - - 4n 2 核心实验的一部分。 不同的是，核心实验中的算法还包括一个附加的场景变化或切换探测器，一个基于八 参数模型( 透射模型) 的全局运动估计与补偿模块。c h o ie t c 1 4 3 z 给出了一种空间域 上的形态分割技术。算法是从全局运动与补偿模块开始的。首先用块匹配算法估算出 对应场，进而估算出全局仿射运动参数。之后，进行场景切换检测。接下来就开始进 入分割程序。首先采用重构形态开一闭运算来简单化当前帧，得到门限化的形态梯度 图像。然后将该梯度图像作为分水岭算法的输入来探澳j 对象的边界。为了避免过分割， 将所有小于某门限的区域融合到它们的相邻区域中去。最后，采用一种前景背景 决策方案来产生视频对象平面。对于每一区域，如果有一半以上的像素属于c d m ， 那么就认为该区域属于前景对象。 在m e i e r 和n g a i l 1 5 】建议的方法中，系统首先通过形态运动滤波技术从背景中分 离出前景对象，并获得该对象的二值模型。随后，利用h a u s d o r f f 距离跟踪对象。这 里，h a u s d o r f f 距离的输入是视频对象和后一帧图像的二值边缘像素点，而图像的边 缘是用c a n n y 边缘探测器得出的。接下来，综合h a u s d o r f f 跟踪和对象运动补偿的结 果，得到下一帧中对象的模型。最后，对对象的模型做后处理，并提取出相应的视频 对象。这个算法中最重要的一部分就是h a u s d o r f f 跟踪器。为了加强时域上的连续性， 用于追踪的对象模型要不断进行更新。 从这些自动分割算法的分析来看，它们无一例外地仅仅使用了运动信息来分离对 象，这在某些特定的场合下是可行，而且，有效的追踪技术和后处理技术使得整个分 割过程能够顺利完成。但在大多数场合中，它们却仍然无能为力。这其中主要涉及到 对语义对象的理解。因为计算机是无法确切地知道“语义对象”这个概念的，只有人 才能对此做出正确的描述。而只有真正获得感兴趣的对象模型，后续的追踪与分割过 程才能达到我们预期的目标。为此，许多半自动分割算法( 1 7 1 2 0 】) 也就相应地提了 出来。 m a r q u e s 和m o l i n a 1 7 建议了一种基于形态学的二重分割方法。最开始，由用户 占塑銮望查堂堡主兰堡堕苎一一一羔e 皇j 塑塑坚塑堕! l 来选择感兴趣的对象，从而导致初始帧在对象级上的分割这些对象从彩色或运动上 来讲一般都是不同一的，需要再分割才能获得一个具有空间同一性的好的分割结果。 然后采用块匹配来估算密度运动场，并利用运动补偿将前一帧再分割后的结果投影到 下一帧，用以提取下一帧中的分割标记。这些分割标记是用分水岭算法根据亮度特征 分割出的结果。为了提高时域上的稳定性，分割过程是由一变化探测模板( c d m ) 来引导的，目的是防止静态区域的标记与运动区域的标记相互混迭。最后，根据所投 影的对象和分割的精细结果，可以在下一帧中得到新的对象级的分割。算法必须跟踪 每一区域的标记，从而获得精细的分割区域与对象间的对应。g 帕和l e e 在【1 9 】中提 出了另外一种半自动的分割方法。算法中，对于i 帧的分割是由用户的辅助和计算机 共同完成的。首先由用户描绘出对象的大概轮廓，之后采用形态开和形态闭运算对对 象的轮廓进行处理，得到对象的“里”边界和“外”边界，最后根据分水岭算法找出 初始对象的近似轮廓。接下来，在p 帧中跟踪对象的轮廓。系统采用了 l e v e n b e r g - m a r q u a r d 递归非线性算法求解透射运动模型的参数。运动补偿后，系统还 采用了反向透射变换来决定p 帧中对象的轮廓，并在最后进行轮廓调整，得到较为精 确的对象轮廓模型，用以提取相应的对象。 这两种分割算法有一个共同的特点，即在算法开始时由用户辅助来获取所需的视 频对象模型，之后调准对象模型并对模型进行跟踪。总的来看，半自动分割算法的分 割效果比自动分割方法的效果要好，而且系统运行效率比较高，应用范围广。但由于 初始用户辅助的工作量比较大，这在一定程度上对整个系统的运行效率会产生影响。 2 2 系统的方案讨论 从以上的分析可以看出，视频对象分割的过程一般包括三个步骤：首先是在第一 帧图像中获得所需的对象模型。这步骤的方法很多，有的算法采用静态图像分割与 用户辅助的方法，有的算法利用运动信息和静态图像处理技术进行自动分割等等；然 后再利用运动信息在后续帧中跟踪所选对象。目前，跟踪技术也很多，有运动跟踪、 模式匹配跟踪，或者两者的结合。而对运动场的估计也可分为基于参数模型的方法和 基于非参数模型的方法两大类；最后对跟踪的结果作相应的后处理并不断更新对象模 型，从而在后续帧中提取出相应的对象。有时候，前面几帧得出的结果往往不是十分 、“ j 矗溉；漉o 。彰。h ；漱麟漱簸潮癌。 占堂窭璺盔堂堡主兰丝丝苎! 【三兰l 墨苎塑查墨堡! ! 一 理想，需要靠后续的反馈学习过程来逐步获得改善因此，总的来看，如何把用户的 辅助、静态图像处理技术以及视频对象运动信息有效地结合起来是处理视频对象分割 问题的关键。单纯地利用某一方面的技术是很难解决这个问题的 由于自动分割算法的局限性，采用半自动分割的方法在处理视频对象分割阎题时 往往具有更大的普遍性。这也就是说，在整个系统的实现过程中，可以在相应的步骤 中引入用户的交曩，以期达到用户的目标。但同时又要注意，对用户介入程度的考虑 也是很重要的。如果用户介入过多，那么程序的独立性就差，相应地，实用性就降低。 毕竟智能化的产品往往更容易普及。 基于以上的因素考虑，在课题之初，我们曾设想首先利用运动信息和用户的简单 辅助( 如加框) 进行分割，然后采用模式识别中的图像匹配技术( 参考文献 2 1 】i 2 3 】) 进行跟踪，最后根据输出的二值模型提取出相应的对象。这样做的好处在于用户介入 少、追踪结果较为准确且能处理非刚体运动的变形、旋转等情形。但由于系统实现时 运算量太大、过程太复杂、使用的参数太多，使得它很难在实际场合中得到应用。而 且，这样处理时，最初得到的对象轮廓可能很不准确，而这种误差会传递下去，使得 最后不得不通过用户的校正来消除累积误差的影响。为此，经过讨论、查询、论证后， 我们修改了设计方案。 在新的设计方案中，我们注重第一帧的处理，希望能够在第一帧中通过静态图像 的分割与用户的交互首先获得对象的一个较为精确的轮廓，然后再对该对象进行跟 踪，并在跟踪的过程中不断调准对象的轮廓，使之向实际轮廓方面逐步接近。同时我 们也将在系统中引入误差控制技术，从而降低或消除累积误差对结果造成的影响。 如前所述，静态图像分割是个经典难题，很难找出一种普遍适用的算法。但这并 不意味着这个问题就没有再讨论的意义了。实际上，如果我们只是希望利用图像处理 技术对图像进行区域分割从而得到一些具有某种同一性特征的图像小块。这往往是可 以做到的。当然，为了使相应的结果符合我们的要求，这些小块应该能够根据对象的 轮廓加以区分，这就需要发展一定的算法来解决这个问题。如果得到的结果令人满意， 接下来就可以由用户根据需要来选取自己所感兴趣的对象。完成第一帧的分割。这样 看来，如何发展一种有效的图像分割算法是第一帧乃至以后帧处理的核心。在这个系 统中，我们采用并发展了一种基于自适应网格的图像分割算法。 一旦在第一帧中得到用户所需的对象，接下来就是如何利用运动信息和初始的对 象籀锅j 。蠢| _ 莓蕾瓤糕滋黼瓣瓣 圭塑奎墨查兰堡圭兰垡堡塞墨三! j 望望叟塑壁堕：一 象模型在后续帧中进行跟踪并提取出相应的对象。在视频处理领域中，运动信息主要 是指像素的速度矢量和位移矢量信息，它们是通过估计相应的运动场来获得的对运 动场的估计，国际上也已经发展了许多有效的算法，大概可分为两类：基于参数模型 的方法和非参数模型的方法【1 】。由于参数模型的方法仅适用于剐体运动，具有较大 的局限性，不如非参数模型方法用的普遍。比如，基于块的分析方法、光流估计、像 素递归法、贝叶斯法等等，都是非参数模型的方法；在运动估计过程中( 这里生要指 二维运动估计) ，往往存在着解的存在性、唯一性和连续性的问题【1 】。而这些问题往 往对运动估计产生很大的影响。所以，如何克服这些问题对于运动估计与跟踪是很重 要的。考虑到效率和准确性等因素，我们决定选用传统的h - $ 光流分析法来估计运动 场。同时在实现过程中引入了一定的预处理措施来提高该算法的准确性。 由于图像分割和运动估计的不准确性，必然会给结果带来一定的误差。而且，随 着算法的执行，如果不做出相应的处理，则误差会随着时间的增长而累积，最后会使 结果面目全非。这显然不是我们所希望见到的。为此，引入相应的误差处理技术既是 必要，又是必然。对于图像分割中的误差处理，我们仍决定采用半自动处理的方式进 行，即：首先对结果作后处理。然后根据静态分割与运动补偿的结果对该帧中的视频 对象轮廓进行调准，从而不断更新对象模型，这是一个动态的过程：而对于运动估计 的误差，采用视频处理中的时间掩蔽技术，在一定数量的帧中进行追踪后，由用户重 新设置后续分割的初始帧。这样，误差的累积就被限定在一定范围内，不会无限制地 扩散下去。 同时我们考虑到在实际应用中实时性的要求是个很重要的因素。因此，如何对算 法进行优化、如何提高程序的运行效率是整个系统实现过程中一喜要仔细研究的问 题。 l o 占篓苎塑奎堂堡圭兰垡兰苎苎三兰l 塑塑叟塑墅墅l 2 3 系统的整体框图 根据上面的讨论，我们可以得出整个系统的框图( 图2 1 ) s t i l ll m a l es e j m e n t a t l o n ， 、- 、 m o w n s o 叼吐t m c l c m g f i g u r e 2 - 1t h e s y s t e m s c h e m e 图2 - 1 系统的整体框图 整个系统可分为四部分：第一部分是静态图像的处理；然后是用户的交互；接下 来是运动对象的跟踪；最后是运动对象模型的调整与更新；误差控制技术贯穿于整个 处理过程。在静态图像处理部分包括几个过程：图像的预处理，这是图像简单化的过 程，包括图像的锐化、e p s i l o n 滤波、彩色空间变换等处理技术；图像的块分割，这 是由自适应网格算法来执行的；而块区域链接作为自适应网格算法的后处理过程，目 的是使图像分割后的块数目满足系统的要求。用户是通过点击对应的块来选择对象 的，这是一种简单有效的交互过程。在运动追踪的过程中，为了获得较好的梯度估算， 我们首先对输入帧进行预平滑处理，之后才进行h - s 光流估计与跟踪。最后，利用每 一帧的静态分割以及动态追踪的结果来调整对象轮廓，更新对象模型，并获得我们所 需的视频对象。 瓠氯疆；o l 、奠；。；二；凌i 建潞滋l 鬣；i 鬣萄i j 圭堂皇墨盔兰璺主兰垡笙苎 一苎三兰j 墅墅墅墅型墅型堕墅堕一 3 自适应网格算法的研究 在计算机视觉领域，三维多边形网格的概念已经被广泛应用于自然对象的几何描 述。它们常被用来描述对象在不同角度的观察结果，并通过纹理映射把从这些不同角 度的相片中所得到的合成图像重现出来( 即：虚拟现实) 。比如，我们可以将一幅静 态图像通过全局变换映射到( 比如：纹理映射) 一个兰维网格上，这样就可以产生动 画的效果。同样地，也可以通过二维动态网格的描述来产生动画和编辑一些特殊效果。 三维网格是v r m l ( 三维虚拟现实模型语言) 标准的基本出发点；而二维动态网格 也包含于m p e g 4 标准中，用于处理基于对象的多媒体信息的压缩和组合。由此来看， 二维网格处理技术将会逐渐成为视频处理领域中的一种有效的处理方式。 二维网格是一种平面图形。利用它可以将图像区域分成许多多边形小块。这些多 边形小块的顶点被称为网节点。在大多数情况下，这些小块的形状皆为三角形或四边 形，相应地，把这种网格称为三角形网格或四边形网格。这些网格可以分为两类：一 致性( 规则的) 网格，这类网格的小块大小是同一的；不规则( 分级的或基于内容的) 网格，这类网格的子块大小与特定的场景内容相适应。由于一致性网格在处理物体轮 廓和物体运动的边缘时效果较差，所以基于内容的网格相对来说就有更大的适用性 ( 参考文献 2 4 】- 【2 9 】) 。本文所发展的网格算法就是以不规则网格为基础的。为了更好 地近似对象的轮廓，我们决定采用三角形网格。 由于我们使用网格的目的是希望利用网格的特性来达到静态图像区域分割的效 果，同时保持对象的轮廓。所以如何产生一种二维网格使其能够按照对象的边缘特性 来对图像进行划分就成为该算法首先要解决的问题。 3 1 网格的产生 在许多基于网格模型的算法中，网格的产生往往是根据一定的图像内容( 如运动、 彩色、纹理等) 和对象表面特性( 如曲率、深度、梯度等) 而得到的。也有的网格是 先在对象区域内和对象边缘放置一定数量的节点，然后连接这些节点构成三角形网 格许多三角形网格都遵循一定的拓扑结构，其中比较有名的有d e l a u n a y 拓扑结构 2 9 】。在这一章中，我们要研究一种新的自适应网格产生算法( 参考文献【3 1 ) 】【3 4 】) 。在 ：& 瓣ji 。、：im _ i 逢懑蕊燃灏，强 圭塑窒墨查量堡主堂堡望兰 苎三兰皇要生坠苎i 塑! 墅! ! 一 这个算法中，我们将按照区域的同一性标准，通过不断地增加网格节点来递归二分区 域，直到满足区域的同一性为止。 算法的输入包括两方面：( 1 ) 初始的规则网格；( 2 ) 由一组准确率门限构成的准 确性标准。图3 1 显示了自适应网格产生的步骤。初始的规则网格是由一系列网格节 点组成的，这些节点沿着观察平面上的x ，y 坐标系规则排列。每个网格都包含有相 同大小( n i t q u a d s i z e ) 2 的区域( 圈3 - 1 ( a ) ) a 每个四边形所包围的区域( 即网格区域) 都被初始化为两个根三角形，这两个三角形由相应的四边形网格节点所构成。这样， 接个图像平面的三角形初始化就是由这样组根三角形来定义的。理论上来说，网格 的初始大小( n i t q u a d s i z e ) 2 是可以任意选择的。也就是说，网格的初始化与最后三角 形化的准确率是不相关的。但在实现时，我们常取i n i t q u a d s i z e = 2 “，其中n 为正整 数 i n i t q u a d s i z e _ “t q d s i 2 ( a ) 雕隧 ( b ) ( c ) ( d ) f i g u r e3 - 1i l l u s t r a t i o no