（通信与信息系统专业论文）用于视频格式转换的全局运动估计与图像插值算法.pdf

用于视频格式转换的全局运动估计与图像内插算法 摘要 ( 视频格式转换一直以来都是视频处理领域中一项非常关键的技 术。长期的国际间广播电视格式的不兼容，高清晰数字电视( h d t v ) 时代的到来，大屏幕c r t 显示器的不断发展，以及新颖的l c d 显示 器材的问世，这些都需要有一种高质量、低成本、易于a s i c 实现的 格式转换算法。目前国际上不少学者和研究机构都提出了各自的格式 转换算法，这些方案各有特色。) 本文结合了笔者在全局运动估计与补 偿方面所作的一些工作，提出了自己的算法。 第一，通过理论分析，将视频格式转换归纳为一个模拟视频采样 网格变换的问题。通过频谱分析，从理论上说明了只有合理利用视频 内的运动信息才能真正解决问题，取得最好的图像质量。 第二，介绍了目前在国际上应用最为广泛的几种格式转换算法， 重点放在对运动补偿算法的介绍上，分析了该种算法的成功之处以及 存在的稳健性方面的问题。通过图示，指出了如果不很好地解决这一 问题，运动补偿算法的优势将不复存在。 第三，为了提高运动估计的准确性与可靠性，可以利用全局运动 估计。在对全局运动模型进行介绍后，指出了全局运动模型能被用于 格式转换的原因。同时，在分析目前国际主流算法的计算思想后，指 出了其运算量过大的缺制通过引入两项新技术：l 。在迭代中使用 固定的h e s s i a n 矩阵；2 。使用一个尺寸可变的基于块的最优化公式； 文中提出了一种全局运动估计的快速算法。通过实验证明，在估计精 度几乎不变的情况下，这一快速算法的计算速度是现有m p e g 4 中推 荐算法的5 到i o 倍。这佐得全局运动估计能够被有效、低成本地运 用在视频格式转换上1 第四，在得到了全局运动估计的快速算法以后，文中提出了一种 基于全局运动补偿、自适应边缘检测的混合算法i f 通过一个“相对运 动”检测器，该系统能够有效地区分视频中的背景物体与独立运动物 体，并据此分别采用运动补偿算法与场内的边缘自适应算法，这既充 分利用了手头已经获得的全局运动信息，又能够有效保证算法的稳健 性。实验证明，该算法既具有帧内算法稳健可靠的优点，又具有运动 补偿算法图像质量清晰、锐利的特点。通过结合上述两种算法的长处， 本文提出的方案可以被很好地应用于视频格式转换领域y 关键词： 视频格式转换，全局运动估计，运动补偿，参数化场景描 述，视频图像内插j 雾泛 g l o b a lm o t i o ne s t i m a t i o na n d i m a g ei n t e r p o l a t i o nf o rv i d e o s t a n d a r d sc o n v e r s i o n a b s t r a c t v i d e os t a n d a r d sc o n v e r s i o ni sak e yt e c h n o l o g yi nv a r i o u sa p p l i c a t i o n so f d i g i t a lv i d e op r o c e s s i n g t h ee x i s t e n c eo fi n c o m p a t i b l ei n t e r n a t i o n a l v i d e of o r m a t s ， t h ea d v e n to ft h eh d t v a g e ，t h ed e v e l o p m e n to fl a r g es c r e e nc r tm o n i t o r s ，a n d t h e i n c r e a s i n gp o p u l a r i t yo f t h el c dd i s p l a y s a l lt h e s ea s kf o rah i g h q u a l i t ya sw e l la s c o s t - e f f i c i e n ts t a n d a r d sc o n v e r s i o na l g o r i t h m d i f f e r e n tk i n d so fa l g o r i t h m sh a v eb e e n p r o p o s e d i nt h el i t e r a t u r e i nt h i sp a p e gw e d e v e l o pa n e w g l o b a lm o t i o n c o m p e n s a t e d v i d e os t a n d a r d sc o n v e r s i o na l g o r i t h m t h e o r e t i c a l l ys p e a k i n g ，v i d e os t a n d a r d sc o n v e r s i o nc a nb es e e na sas a m p l i n g l a t t i c ec o n v e r s i o np r o b l e m f r o ms p e c t r u ma n a l y s i s ，w ec a nc l e a r l ys e et h a t o n l y t h o s em e t h o d st h a tm a k eg o o du s eo fm o t i o ni n f o r m a t i o nc a np r o v i d et h eu l t i m a t e h i g h - q u a l i t ys o l u t i o n s o m eo ft h em o s t p o p u l a rs t a n d a r d s c o n v e r s i o na l g o r i t h m sa r ed e s c r i b e di nt h e p a p e r ，w i t ha ne m p h a s i so nt h em o t i o n c o m p e n s a t e do n e s r o b u s t n e s si s ap o t e n t i a l d r a w b a c ko ft h e s ea p p r o a c h e s w es h o wt h i sp r o b l e mt h r o u g hap a i ro f i m a g e s i no r d e rt os o l v et h i s p r o b l e m ，w et u r n o u ri n t e r e s tt ot h eg l o b a lm o t i o n e s t i m a t i o n w ef i r s td e s c r i b ed i f f e r e n tg l o b a lm o t i o nm o d e l sa n de x p l a i nt h er e a s o n f o ri t s a p p l i c a b i l i t y i nv i d e os t a n d a r d sc o n v e r s i o n a f t e r e x a m i n i n g t h e e x i s t i n g d i f f e r e n t i a l b a s e da p p r o a c h e s ，w ed e v e l o paf a s ta l g o r i t h mb a s e do nt h ef o l l o w i n gt w o t e c h n i q u e s ：1 w eu s e ac o n s t a n th e s s i a nm a t r i xi nt h ec a l c u l a t i o no fd e s c e n d i n g d i r e c t i o n s 2 w eu s eav a r i a b l es i z ep a t c h b a s e da p p r o a c h t h e s et w on e wt e c h n i q u e s c a ng r e a t l yi m p r o v et h ec o m p u t a t i o n a le f f i c i e n c yo ft h ea l g o r i t h m a ss h o w nb yt h e s i m u l a t i o n r e s u l t ，t h ep r o p o s e da p p r o a c h i s5 - 10t i m e sf a s t e rt h a nt h ea l g o r i t h m p r o p o s e d i nm p e g 4 a f t e r g e t t i n g t h e g l o b a l m o t i o n i n f o r m a t i o n ，w e d e v e l o p e d a g l o b a l m o t i o n - c o m p e n s a t e dv i d e os t a n d a r d sc o n v e r s i o ns y s t e m u s i n ga “r e l a t i v e m o t i o n d e t e c t o r ，w ec a ne f f e c t i v e l yd i s t i n g u i s hb a c k g r o u n do b j e c tf r o ml o c a lm o v i n g o b j e c t s f o rt h ef o r m e rr e g i o n s ，w ea p p l ym o t i o n c o m p e n s a t e dd e i n t e r l a c i n ga p p r o a c h ；w h i l e f o rc h el a t t e r r e g i o n s ，w es w i t c h t ot h ei n t r a f i e l d e d g e b a s e da p p r o a c h t h i s c o m b i n a t i o ne n s u r e st h er o b u s t n e s sa sw e l la st h e q u a l i t yo ft h ep r o p o s e dm e t h o d e x p e r i m e n t ss h o wt h a tt h ep r o p o s e dm e t h o do u t p e r f o r m sb o t ht h el i n e a rf i l t e r i n 2 a p p r o a c ha n dt h em o t i o n c o m p e n s a t e da p p r o a c h t h u s ，i ti sas u i t a b l es o l u t i o nt ot h e p r o b l e mo f v i d e os t a n d a r d sc o n v e r s i o n k e y w o r d s ：v i d e os t a n d a r d s c o n v e r s i o n ，g l o b a l m o t i o n e s t i m a t i o n ，m o t i o n c o m p e n s a t i o n ，p a r a m e t r i cs c e n ed e s c r i p t i o n ，i m a g ei n t e r p o l a t i o n 上海交通大学硕士学位论文 2 0 0 2 年1 月 1 1 引言 第一章绪论 数字电视( d t v ) f 1 1 时代的到来无疑是消费电子领域的一次伟大革命。随着信 源编码技术以及信道传输技术的飞速发展，数字高清晰度电视( h d t v ) 使人们在 自己的起居室里就能得到极高品质的视听享受。然而，由于建立全数字电视台需 要高昂的费用、而用高清格式拍摄的节目相对缺乏、以及现在家庭拥有大量的模 拟制式电视机这一切都决定了从模拟到数字电视时代的转变是一个渐进 的过程。可以预见，高清晰度电视( h d t v ) 、标准清晰度电视( s d t v ) 、以及传 统的模拟电视将在相当长的一段时间内同时存在。在这种情况下，用一种格式拍 摄的节目必须经过适当的格式变换，才能在另一个格式的接收设备上播放。例如， 用h d t v 摄像机拍摄的节日必须通过下变换才能在普通电视机上播放。 现代c r t 电视机的一个趋势是变得原来越大，也越来越亮。然而，人眼的频响 范围也会根据所观察物体的变亮而随之扩大。这样，对于越大越亮的电视机，人 们越容易察觉到图像的闪烁。要解决这一问题，就必须提高现有视频的场频率， 而这正是格式转换的任务之一。 液晶显示器材的使用又为格式转换技术提供了广阔的应用舞台。传统的c r t 显示器从本质上说是模拟的，因此对于不同的输入信号格式( 如p a l ： 7 2 0 5 7 6 5 0 f n t s c ：7 2 0 4 4 8 6 6 0 f ，以及h d t v ：1 9 2 0 1 0 8 0 5 0 f 、 1 9 2 0 1 0 8 0 6 0 i 、1 2 8 0 7 2 0 6 0 p ) 都能正确的显示。然而对于液晶显示器材， 问题没有这么简单。每一块液晶面板都是由一个固定规模的液晶点阵所组成，而 这个点阵的规模大小( 即长、宽方向上点的数目) 决定了该液晶面板所能显示图 像的分辨率，也称为本征分辨率( n a t i v er e s o l u t i o n ) ，常见的有( x g a ：1 0 2 4 7 6 8 ， s x g a ：1 2 8 0 1 0 2 4 ，以及u x g a ：1 6 0 0 4 1 2 0 0 ) 。这时，要使液晶显示器能够适 应多种输入格式，我们必须添加一个格式转换模块，将输入信号的分辨率转换到 本征分辨率上去。 综上所述，视频格式转换技术是数字图像及视频处理研究中的一个非常重要， 上海交通大学硕士学位论文2 0 0 2 年1 月 并有着广泛应用领域的问题。从本质上说，视频格式转换等价为视频信号时空采 样结构的变换，包括了空间分辨率的上下变换、时间分辨率的上下变换、及其组 合。 为了后续章节的讨论方便，本章首先介绍了视频信号时空采样及其频谱分析， 这奠定了视频格式转换的理论基础。通过这一理论，我们能很清楚地看出不同格 式转换算法的优缺点及局限性，并能为我们探索新的算法提供指导。在本章的最 后，介绍了本文的组织结构及创造性结果。 1 2 视频信号在三维网格上的时空采样 模拟视频信号是一个三维函数，可以用s c ( x ，x ：，f ) 来表示，其中x = 0 。，x ：) 为空 间坐标矢量，t 为时间坐标，而下标c 表示这是一个模拟信号。为了方便数字处理， 需要对模拟信号在固定的三维网格上进行离散化采样，得到数字视频信号，用 s ( n ，n ：，女) 来表示，其中n = ( h 。，n ：) 以及k 分别为对应( x ，x 2f ) 三个坐标轴方向的整 数下标。其采样过程如下： s p a t i a l t e m p o r a l s a m p l i n g 图卜1 模拟视频采样过程 f i g 1 - 1s a m p l i n g & a n a l o g v i d e os i g n a l s s ( n 1 ，n 2 ，k ) 采样所使用的三维网格可以多种多样，但最为常见的是两种：逐行扫描与隔行 扫描，其网格如下： 为了更简洁地表示网格，我们令v ，v ：，v ，为三维欧式空间中的三个线性无关向 量，则任意网格a 3 可以用这三个矢量的线性组合来表示，即： 人3 = i v - ky z 2 v 2 - k k v 3 1 n ，n ：，te z = v ： n e z 2 ，t e z c ，- ， 上海交通大学硕士学位论文 2 0 0 2 年1 月 其中，v = ( v fv ：fv 3 是一个3 3 的矩阵，被称为采样矩阵。根据上式，采样后的 数字视频信号可以表示为： 咖，栌s ( 1 1 , k ) = ( k ) z 3 ( 1 - 2 ) 图1 - 2 逐行与隔行扫描网格 f i g 1 - 2s a m p l i n gl a t t i c ef o rp r o g r e s s i v ea n di n t e r l a c e ds a m p l i n g i a x l 00 ll 缸l 00 i v = l0 血2 0 i 及v2 l 0 2 a x 2 0 l ( 1 - 3 ) e 00 a t jl 0 a x 2 f 2 j 其中，下标p 和，分别代表逐行( p r o g r e s s i v e ) 和隔行( i n t e r l a c e d ) ，a x i 和血2 分 别为采样网格在x 一轴与y 轴上的间距，而f 则代表相邻帧之间的时间间隔( 如p a l 1 3 在三维网格上采样视频的频谱 根据傅立叶变换定理，连续视频信号s 。( x ，t ) 与其频谱疋( f ) 之间的关系可以表 示为如下形式 2 3 1 1 8 ： 墨。一 ，f 二l，ll+。l ， - + ， 。一 一 圭耋奎鎏查兰翌圭兰竺鎏兰，。，。，。，。，。，。，。，耋：! 圣i 譬星 墨( f ) = j ：r 3s ，( x ，r ) e x p - j 2 疗f r lil d x d t ( x ，) = ，5 。( f ) e x p 2 丌f r ； d f ， 接下来，我们引入带“冲击串”的视频信号s ，【x ，t ) ，定义为： ，c x ，：s 。c x ，r ，。苑，j ( ； 一v ： = 。i ：z n , ，sc n ，t ，占 ； 一v ： c _ s ， 其中，占f x l 为理想冲击函数。从上式可以看到，s p ( x ，f ) 与离散信号s ( n ，女) 一一对 应，但在形式上是连续函数，因此可以方便地使用连续函数的傅立叶变换公式计 算频谱，这正是我们引入( x ，f ) 的目的所在。 同样，为了接下去推导的方便，我们令u 7 为采样矩阵v 的逆，即u r v = i 。 设a3 与a ，分别为由v 和u 生成的三维网格，任取矢量r a ”， x ，f 7 a 3 ，则 两个矢量的内积i x , 叮r 必然是一个整数，这是由u r 与v 互为逆矩阵决定的。a ” 常被称为a3 的互换网格。 下面我们来推导s p ( x ，r ) 的频谱表达式 2 【3 2 5 。将( 1 4 ) 式代入( 1 - 5 ) 式得： s ，( x ，r ) = ，( f ) e x - ，2 ，f 7 ； j d f ， x a 3 。， ：萎s 。( f + r ) e x 一 ，z 万( f + r ，7 ； 卜f 其中，p 是互换网格a ”的一个单位体积。根据互换网格的性质： x ，f 7 r ，必然有 e x r ( ，：丌， i = - ，这样，上式就可以简化为： 州剐，= 幢辨川h 伽f 7 m 7 ) 由傅氏变换的定义，我们可以得到s 。( x ，t ) 的频谱为： )4l( r 一 卜 ， f 扛 上海交通大学硕士学位论文 2 0 0 2 年1 月 州2 羽1 蚤s 。( m ) 2 羽1 弘( 刚k ) ( 1 - 8 ) 从上面的推导我们可以得出以下结论： ( 1 ) 对于一个连续的视频信号s c ( x 。，x 2t ) ，设其基带频谱为s c ( f ) ，如果我们根 据某一固定网格a 对s 。( 一，x ：，f ) 进行采样得到数字视频s ( n ，n ：，) ，则该数 字视频的频谱相当于原有连续信号基带频谱沿着a 的互换网格a + 进行无限 叠加的结果。 ( 2 ) v 矩阵的元素对应于采样间隔的大小，同时a + 的采样矩阵u 与v 互为逆矩 阵，因此对原模拟信号的采样越密，则采样后的数字视频叠加的间距越大， 反之，原有的采样越稀疏，则采样后频谱叠加的间距越小，越容易发生混 替( a l i a s ) 。 1 4 由采样数字视频重建模拟视频 前面已经提到，数字视频格式转换的实质是对原有模拟视频信号进行采样网格 的转换。因此，一种很直观的想法就是：如果我们能根据已知的数字信号无损地 恢复出模拟信号，那么对该模拟信号按照目标网格再次进行采样就能达到格式转 换的目的。接下来，我们通过图示来讨论一下上述方法的可行性。 图i - 3 ( a ) 中的阴影部分表示原始模拟视频信号的频谱，图1 - 3 ( b ) 为采样间隔足 够密时的数字视频频谱。上面已经提到，数字频谱是模拟频谱按照互换网格a ”进 行平移叠加的结果。如果采样网格a 3 足够密，则a ”的间隔就能足够大，使得各个 叠加的基带频谱不互相混叠。图1 - 3 ( b ) 正是这种情况。此时，要恢复原有的模拟视 频，只要施加一个理想的低通滤波器( 图中的正方形方框) 就可以了。但是我们 实际遇到的数字视频信号( 尤其是隔行信号) ，其采样频率往往不够高，这就造成 了数字频谱的各叠加分量发生了重叠，如图i - 3 ( c ) 所示。此时，我们无法用一个低 通滤波器来恢复模拟视频的频谱。从上面的讨论，我们可以得到如下结论： 皇曼蔓皇曼量曼皇皇曼曼曼皇奄曼曼皇曼鲁皇舅毫曼曼曼皇鼍曼曼蔓曼暑笪皇皇曼曼i _： 如果数字视频的采样频率不能达到奈奎斯特频率，则我们无法仅仅根据数字频 谱信息来恢复出原有信号。 f 2 1 怎飘 弋 i i i 一 彗誉妻 = m ( 琏 到瓣8 = 锄 f 2 f l 一j 。0 j 卜 今。 1 ( a ) 模拟信号频谱 ( b ) 采样良好时的频谱 ( c ) 欠采样时的频谱 ( 8 ) s p 。“”o f a n a l o gs i g n a l ( b ) s p e c t r u mi nt h ec a s eo f w e l l - s a m p l i n g ( c ) u n d e r - s a m 衄g 图1 - 3 模拟及数字信号的频谱 f 嘻1 - 3s p e c t r u mf o ra n a l o ga n d d i g i t a ls i g n a l s 然而，我们目常处理的数字视频( p a l ，n t s c 等) 大多不满足奈奎斯特采样。 在这种情况下，利用帧内插值的算法来进行格式转换必然会引入因频谱混叠所造 成的图像失真。这就从理论上说明了帧内插值算法性能的局限性。 要较好地解决格式转换问题，必须利用视频信号内蕴藏的运动信息，即利用带 运动补偿的算法( 我们将在第二章内详细介绍具体算法) 。这种方法的优越性也可 以从频谱分析的角度来说明。 1 。5 考虑视频运动信息后的频谱 为了便于说明问题，我们假设视频中仅存在一个单一的匀速运动，：g i g r 变为 ( h ，v 2 ) ，则我们可以将模拟信号( _ ，r ) 表示为 2 ： s 。( x l , x 2 , t ) 2s 。( x ，一v 。f ，x ：一v ：f ，f ) ss 。( x 一v ，f ，屯一心f ) ( 1 - 9 ) 其中，( x 1x 2 ) 为零时刻处的参考帧。 在加入了( 1 - 9 ) 式的信息后，我们重新计 算5 。( 一，x ：，t ) 的频谱如下 2 5 5 5 ： f l 上海交通大学硕士学位论文 2 0 0 2 年1 月 s o ( r , ，f ) = & ( b 咖删印】嵋”印幽出：d t = 肌( 矿吖，矿吖- j 2 z ( f i x l * f 2 x 2 + f , t 出l 出2 巩 f 1 1 0 1 = i i , o ( x l ，x 2 ) e - j2 r ( f l x , * f 2 x ：) d x d x 2 p 2 州即【峨”怛”d t = 品( ( ，f ) 占( 鼻v 。+ v ：+ j f ：) 其中，s 。( 鼻，f ) 是s 。( x 1x ：) 的二维傅立叶变换，而万( ) 是一维d i r a c 冲击函数。 从上式可以看到，频谱s 。( f ，e ，f ) 只有在f , v 。+ 五v ：+ f = 0 的地方才有非零 值，而f , v ，- ，f 2 v ：+ f = 0 h ( f ，f ) 组成的频率空间中代表了一个过坐标原点， 并与运动矢量f v lv 2 1 正交的平面。这样，我们就得到了如下重要结论： 对于单一匀速运动，模拟视频的频谱只有在一个过原点的平面上才有非零值。 下图展示了在匀速运动情况下的频谱。为了便于观察，我们只提供了频谱在 f f 平面e 的截面投影。 f l b 1 j j j j b t - b t 。 - b 1 图1 4 匀速运动情况下的频谱 f i g 1 - 4s p e c t r u m i nt h ec a s eo f c o n s t a n tv e l o c i t y 如图所示，模拟频谱的二维投影只是一根直线。接下来，我们来观察匀速运动 情况下的数字视频频谱。根据1 5 中得到的结论，数字频谱是模拟频谱进行平移叠 加得到的，如下图所示： 上海交通大学硕士学位论文 2 0 0 2 年1 月 0 父 、；：文之 岭 。蚪弋 弋心义 f 2 沁沁 心心 ( a ) 用帧内滤波器( b ) 用运动补偿滤波器 ( a ) i n t r a f i e l df i l t e r i n g( b ) m o t i o n c o m p e n s a t e df i l t e r i n g 图1 5 考虑运动时的滤波 f i g 1 - 5f i l t e r i n gi nt h ec a s eo f m o t i o n 图( a ) 中的阴影部分为传统的帧内理想低通滤波器。由于采样网格密度达不到奈 奎斯特要求，n ) l 这时候理想低通滤波器是无法将原始频谱正确恢复出来的。我 们再看图( b ) ，其阴影部分是一个方向性的低通滤波器。从图中可以看到，利用这 一滤波器，我们可以完美地恢复出原始频谱，而将其他平移叠加后的频率分量滤 除。但是，构造这一滤波器，需要知道运动矢量( v ，v ：) ，因为其倾斜方向必须与 原始频谱的方向一致，而这又是由运动矢量决定的。综上所述，我们可以得到以 下结论： 如果我们可以求得视频中包含的运动矢量，那么我们就有可能利用这一信息构 造出方向性滤波器，从而将原始信号频谱恢复。而这时的原始信号采样网格不一 定要符合奈奎斯特要求。 根据上述思想得到的格式转换算法，被称为带运动补偿的算法。从上面的讨论 我们可以清楚地看到，这种算法比简单的帧内内插算法有先天的优势。 上海交通大学硕士学位论文 2 0 0 2 年1 月 1 6 本文内容安排和研究成果 以上简单地介绍了数字视频格式转换的理论基础：即数字视频的网格化采样及 其频谱，以及在使用与不使用运动信息这两种情况下进行原始图像的恢复。应该 指出，视频格式转换牵涉到的面相当广泛，包括信号处理、图像分析、运动估计、 图像内插、以及计算机视觉等等。笔者在攻读硕士期间，主要从事了用于视频格 式变换的运动估计及图像插值算法的研究，即使用一种快速可靠的运动估计算法， 再配合自适应的插值算法，来构造一个高性能价格比的视频格式转换系统。 本文的研究方向主要集中在视频空间分辨率的变换上。应当指出，数字视频格 式转换任务还包括对视频进行时间上的帧场频率的变换。但这不在本文的讨论范 围之内。同时，由于空间分辨率的下变换涉及的只是一个单纯的信息量减少的过 程，直接利用数字信号处理理论中的常用滤波器算法就能很好地完成任务，本文 也不再赘述。因此，本文主要围绕利用运动估计与自适应图像插值算法对视频进 行上变换来展开讨论，具体内容安排如下： 第二章首先介绍了视频格式转换系统的一般结构，即先由隔行信号转为逐行信 号，再通过线性滤波进行尺寸变换。第二部分讨论了常用的几类视频去隔行算法， 包括线性的时空滤波器算法，非线性的运动自适应算法、边缘自适应算法、中值 滤波算法，以及本文的重点：基于运动补偿的算法。在第三部分中，笔者指出了 目前一般的运动补偿算法在稳健性上的缺点，并用图示来说明这一点。 第三章介绍的全局运动估计算法正是为了解决上述问题而引进的。在第一部分 中，首先讨论了全局运动模型及其常见计算方法，并指出了全局运动估计适用于 视频格式转换应用的原因。在第二部分中，我们介绍了目前国际上主流的基于微 分的算法，并指出其计算量过大的关键所在。在第三部分中，着重讨论了笔者自 己提出的快速算法。通过第四部分的实验可以证明，该算法在保持估计精度几乎 不变的情况下，能将原有的计算速度提高5 - 1 0 倍。 在第四章里讨论了笔者提出的基于全局运动估计的视频格式转换方案。通过实 验表明，该方案在总体性能上要优于线性滤波算法及普通的运动补偿算法，可以 说是结合了两者的长处。在这一章的最后，笔者讨论了该算法方案的优点以及局 限之处，并指明了进一步工作的方向。 上海交通大学硕士学位论文2 0 0 2 年1 月 i i i 本文的创造性研究成果概括如下： ( 1 ) 分析了造成一般运动补偿算法稳健性不足的原因后，提出了使用全局运动 补偿的方案。 ( 2 ) 在分析了目前国际主流全局运动估计算法的原理后，提出了自己的快速算 法。其中引入了两个新的技术：首先，我们使用一个固定的h e s s i a n 矩阵h ， 来计算收敛方向，这与原来每次迭代都需重新计算h e s s i a n 不同。这一改进 是基于以下考虑：1 所要估计的两幅图像来自同一个3 维场景，因此它们 彼此非常相似。2 在很短的时间间隔内，我们所采用的参数化运动模型是 对真实运动的良好近似。其次，我们采用了一个可变大小的基于分块的方 案。同基于像素的方案相比，这一方案对初始值的偏差更加宽容，同时收 敛速度更快。在实验中，我们将所提出的算法与m p e g 4 中的标准算法进 行了比较。实验结果表明，在几乎没有性能损失的情况下，采用新的算法 的运算速度能够提高5 到1 0 倍，这充分证明了所提算法的有效性。 ( 3 ) 提出了基于全局运动补偿的格式转换算法结构。通过将补偿后的图像送入 一个运动检测器，有效地区分了背景物体与独立运动物体，并据此分别采 用运动补偿算法与场内的边缘自适应算法，这既充分利用了手头已经获得 的全局运动信息，又能够有效保证算法的稳健性。 上海交通大学硕士学位论文 2 0 0 2 年1 月 2 1 引言 第二章视频格式转换的基本算法 在第一章已经提到，视频格式转换的实质就是视频采样网格之间的变换。如果 我们能够从已知的数字信号恢复出原有的模拟信号，则对该模拟信号再按照目标 网格进行采样就能达到目的。其框图如下： _ _ i 一一了= m 以，尼) 毒黯。翟篙也8 = = ：二： 胁唧m 。b 芝( ，l ，他，功 c o n t i n u o u ss i g n a l 。 一、。 图2 1 视频格式转换的原理示意图 f i g2 - 1b l o c kd i a g r a m f o rv i d e os t a n d a r d sc o n v e r s i o n 然而，在实际环境中，问题没有这么简单。前面已经捉到，对于常见的数字视 频( 特别是隔行信号) ，其采样频率都过低，不符合奈奎斯特采样定理。因此，仅 仅凭借帧内重建滤波器是无法恢复原有视频信号的。根据1 5 节的讨论，此时加入 帧间运动信息是很有好处的。 如果我们要提高输入视频的空间分辨率( 例如从s d t v ：7 2 0 x 4 8 6 6 0 f 上变换 到h d t v ：1 9 2 0 1 0 8 0 6 0 i ) ，往往需要经过两个步骤：( 1 ) 隔行转逐行 ( d e i n t e r l a c i n g ) ；( 2 ) 图像内插上变换。如下图所示 4 9 1 3 ： s 酬。d ( 胛l ，z 2 ，k ) 图2 2 实用的视频上变换系统框图 f i g2 - 2b l o c kd i a g r a m f o rp r a c t i c a lv i d e ou p c o n v e r s i o ns y s t e m s 上海交通大学硕士学位论文 2 0 0 2 年1 月 ! i i i i i 皇i i 曼蔓曼蔓! 曼曼曼鼍鼍量曼曼暑曼曼鼍鼍量皇皇皇皇曼曼量邕曼量量皇曼量笪皇皇鲁曼曼曼! 图中，s 。咖硎( m ，n ：，k ) 为输入的低分辨率隔行扫描视频信号( 如 7 2 0 x 4 8 6 6 0 i ) ， 5 ，。( n ，n 2 ，k ) 为经过去隔行处理后的中间信号( 如 7 2 0 4 8 6 6 0 p ) ，而s 。( , ，1 2 ，k ) 则是经过插值处理后输出的高分辨率信号( 如 1 9 2 0 x 1 0 8 0 6 0 i ) 。前面已经提到，之所以不能直接对输入信号进行插值运算是因 为输入信号频谱存在混叠，不符合采样定理，而系统中加入去隔行步骤的目的正 是通过一定的算法去除混叠，使其符合采样定理的要求，然后再进行内插。由此 可见，去隔行( d e i n t e r l a c i n g ) 是视频上变换中的个十分重要的步骤，我们将在 本章内详细介绍其常用的算法。 本章第二节介绍的去隔行算法 3 8 ，包括线性的垂直一时间滤波，非线性的运动 自适应算法，以及运动补偿算法。第三节我们讨论了传统运动补偿算法的内在弱 点，并提出了利用全局运动估计与补偿进行视频去隔行的算法思想，这引出了第 三章我们对于全局运动估计的详细讨论。 2 2 视频去隔行( d e i n t e r l a e i n g ) 算法 2 2 1 问题定义 在当今的广播系统中，绝大部分的视频信号是隔行采样的。采用这种扫描格式， 能够大幅度地减少视频的带宽，但同时图像的主观质量又不会下降太多。这是因 为，它巧妙地利用了人眼的一个视觉特性，即：相比大区域的闪烁，人眼对于局 部细节的闪烁较为不敏感。因此，对于两个具有完全相同带宽的视频信号3 0 h ： 逐行与6 0 h z 隔行，人们会明显觉得后者看起来更舒服。 隔行扫描方式的引入成功地缓解了视频系统对带宽的要求，但同时它也给很多 视频处理工作，如格式转换、运动估计、压缩编码等，带来了更多的难度。因此， 视频去隔行就成了许多视频处理系统中的个重要组成部分。下面，我们用图示 与数学表达式这两种方法来定义视频去隔行的任务。 图2 - 3 是隔行转逐行的示意n 3 0 。其中，实心的圆点表示每一场中的已知信 号，而十字叉点表示每一场中待求的点。而隔行转逐行的任务就是根据已知点的 信息，求得场中未知点。我们也可以将此用公式表达为 6 ： 上海交通大学硕士学位论文 2 0 0 2 年1 月 其中，x = ( x 1x ：) 为像素点的坐标矢量，x ：为垂直坐标，”= ( 一2 , - i ，0 ，1 ，2 ，) 为 各场的序号，r ( x ，”) 为原有隔行场中的像素值，f ( x ，一) 为各场中待求的值，而 e ( x ，y ) 则是最后输出的逐行信号。 、 ( r ，、 一 ，_ 一 ? 一、l 。 八 厂 一，j 一7 图2 - 3 隔行转逐行示意图图2 4 隔行视频信号的频谱 f i g2 - 3d i a g r a mf o rv i d e od e i n t e r l a c i n gf i g 2 - 4s p e c t r u mo fi n t e r l a c e dv i d e os i g n a l 为了讨论的方便，我们在图2 - 4 中再一次给出了隔行视频信号的频谱。从图中 可以看到，由于隔行视频处于亚采样状态，因此其频谱中存在非常明显的混叠， 这给后续的处理带来了较多的困难。 在接下来的几个小节中，我们较详细地介绍几类常见的去隔行算法。 2 2 2 线性滤波算法 线性滤波算法，最早出现在上世纪7 0 年代末，具有简单易实现的优点，目前 仍在计算机图形显示领域内被广泛应用。其基本思想是，各场中需要补齐的像素 点等于它的若干相邻点的加权和。用公式表达为： 苟 m = 2 凼删k 町 、j、j 门 x x ，ll f f ，0，、l i | 、l 胛x ，fl，口 f 上海交通大学硕士学位论文 2 0 0 2 年1 月 只( x ，n ) ( x2r o o d 2 = n m o d 2 ) ( o t h e r w i s e ) ( 2 2 ) ( k + m ) r o o d2 = 1 ) 其中，u ，= ( o ，a x ：) 为垂直方向上的单位向量，h ( k ，川) 为加权系数。从上式可以看 到，线性滤波的相邻点包括两类，即同一场上的相邻像素( 空间相邻点) 以及相 邻场上的像素( 时间相邻点) 。对于相邻点的分类就引出了三种不同的滤波器类型： 空间滤波( s p a t i a lf i l t e r i n g ) ，时间滤波( t e m p o r a lf i l t e r i n g ) ，以及时空滤波 ( s p a t i a l - t e m p o r a lf i l t e r i n g ) 。 ( 1 ) 空间滤波( s p a t i a lf i l t e r i n g ) 所谓空间滤波，就是在求取未知点的时候只使用同一场内相邻点的信息。最简 单的空间滤波就是扫描线重复( l i n er e p e t i t i o n ) ，即一场中未知的像素点直接取它 上面相邻点的值。如果用公式( 2 - 2 ) 的形式来表示的话，那就是取h f l ，0 1 = 1 ， 而其他所有的 f 女，m 1 都为0 。一种稍微复杂一点的形式为线平均( l i n e a v e r a g i n g ) ， 即未知的像素点等于其上下两个相邻已知的点的值的平均。即： ( 一1 ，0 ) = h ( 1 ，0 ) = o 5 ，而其他所有的 ( ，m ) 都为0 。 上述两个空间滤波器的频率相应分别为： 日，：( ) = c 。s ( 万六，) l 以及h ；：( 工：) = 了1 + 了1c o s ( 石六：) ( 2 3 ) 它们有一个共同的特点，即它们在时间频率方向上是全通的，这说明使用空间 滤波器不会造成视频运动信息上的损失。但是，由于其频谱在垂直方向上的低通 形状，使得视频信号在垂直方向上的一些高频分量被抑制，从而降低了图像在垂 直方向上的清晰度。图2 5 展示了空间滤波器的滤波作用，其中灰色阴影部分为滤 波器的通带区域。 ( 2 ) 时间滤波( t e m p o r a lf i l t e r i n g ) 与空间滤波正好相反，时间滤波器就是使用所有相邻场内的点来求取当前场的 未知像素。最简单的时间滤波就是场重复( f i e l dr e p e t i t i o n ) ，即一场中未知的像 素点用上一场对应的已知像素值来代替。如果用公式( 2 - 2 ) 来表示的话，我们取 & ， 一 叭 一 ，盯 吐咚 k f 州 “。 上海交通大学硕士学位论文 2 0 0 2 年1 月 h ( o ，一1 ) = 1 ，而其他所有的 ( 女，所) 都为0 。很显然，如果视频中没有运动的话，这 一滤波器就是最优滤波器。类似地，这一滤波器的频率响应为： h ，( ：) = l c o s ( z j ) 【 ( 2 _ 4 ) 从上式可以看出，时间滤波器在垂直方向上是全通的，因此不会造成图像垂直 清晰度上的损失，但其在时间频率上的频谱的衰降，会造成视频运动信息的损失。 图2 - 6 展示了时间滤波器的滤波作用，其中灰色阴影部分为滤波器的通带区域。 图2 5 典型空间滤波其的通带示意图图2 6 典型时间滤波器的通带示意图 f i g2 - 5p a s s b a n do f at y p i c a ls p a t i a lf i l t e r f i g2 - 6p a s s - b a n do f at y p i c a lt e m p o r a lf i l t e r ( 3 ) 时空滤波( s p a t i a l t e m p o r a lf i l t e r i n g ) 所谓时空滤波，就是在计算像素点的值的时候综合考虑空间邻点与时间邻点。 从理论上说，如果视频信号满足采样定理，即其频