基于时空特性自适应插值的混合去隔行方法

张 涛，陈有志，雷志春



基于时空特性自适应插值的混合去隔行方法

张 涛1，陈有志1，雷志春2

(1. 天津大学电气自动化与信息工程学院，天津 300072；2. 天津大学微电子学院，天津 300072)

为了实现隔行扫描到逐行扫描的视频格式转换，需要使用去隔行插值技术．针对传统运动补偿插值算法的误差传递、运动估计不准、计算复杂度较高等缺陷，提出一种基于奇偶一致性搜索的运动补偿去隔行方法；针对传统基于边缘方向插值算法的边缘定位不准等缺陷，提出一种基于梯度辅助的场内多方向插值方法．将上述两种方法与场合并插值和行平均插值相结合，提出一种新的基于时空特性自适应插值的混合去隔行方法．该方法能够利用视频中的时空特性，有效地解决传统去隔行算法因运动估计错误和边缘定位不准导致的插值失真等问题．实验结果表明，与传统去隔行算法相比，该方法能够在降低总体计算复杂度的情况下获得0.7,dB左右的PSNR提升．

时空特性；奇偶一致性；梯度辅助；去隔行

在视频信号的传输过程中，为了减少传输带宽，通常采用隔行扫描的方式处理视频信号，例如主流电视广播系统NTSC、PAL和SECAM等[1]．但是隔行扫描会造成锯齿现象、边缘闪烁和场间混叠等视觉上的问题．为了解决这些问题，并且填补缺失的像素，人们提出了各种各样的去隔行算法[2-11]．它们可以粗略地分为3类：时域插值算法、空域插值算法和时空混合插值算法．

时域插值算法一般是利用场间信息进行去隔行插值，主要有场合并、场平均、运动补偿等算法，其中场合并、场平均算法运算简单，在静止区域表现良好，但在运动区域会产生羽化等不良现象[2]．运动补偿算法是一种比较特殊的时域插值算法，它通过场间信息预测出物体的运动轨迹，然后沿着运动轨迹进行像素插补，是目前性能较好的一种去隔行算法，但是这类算法容易受到运动矢量误差的干扰而导致重建图像质量低下，另外还存在误差传递和计算复杂度较高等缺陷[2-3]．

空域插值算法是利用场内信息进行去隔行插值，主要包括行平均、行复制、基于边缘方向插值等算法．其中行平均和行复制算法结构简单，应用范围较广，但容易造成锯齿、褶皱等插补缺陷．而基于边缘方向插值算法则利用人眼对物体边缘敏感的特性，沿着边缘方向进行插值，较好地保护了边缘的连续性和锐利度，从而明显增加图像的主观质量效果，例如ELA[2]、MELA[4]和FELA[5]等算法．但是这些算法基本都是通过像素值相似度信息预测边缘，由于使用的信息较少，导致边缘方向预测不准确．

时空混合插值算法利用场间信息和场内信息进行去隔行插值，主要表现形式是结合时域插值算法和空域插值算法，形成一个混合的去隔行算法．目前一般是通过运动检测或者权值来结合时域插值和空域插值算法，比如Trocan等[6]使用运动检测结合运动补偿插值、基于边缘方向插值和行平均插值等算法，Chang等[7]利用权值自适应结合场内插值算法和运动补偿插值算法．这些算法取得了一定的去隔行效果，但是结合过程中的判决较为复杂，总体的计算复杂度还需要降低．

鉴于以上问题，本文提出一种基于时空特性自适应插值的混合去隔行方法．其中对运动补偿算法和基于边缘方向插值算法进行改进，并且通过运动检测和边缘检测进行算法融合，较好地利用视频中的时空特性保护图像边缘的锐利度和连续性，抑制因运动估计不准而造成插值失真现象的发生．

1 基于奇偶一致性搜索的运动补偿场间插值

传统的运动补偿去隔行算法大部分使用块匹配、全搜索的方式进行插值，同时参考帧一般会选取之前的重建图像，但是这样会产生误差传递、运动估计不准、计算复杂度较高等问题，因而也严重影响了去隔行性能，比如时域递归(time recursive，TR)去隔行算法[2]等．本文针对这些问题提出一种基于奇偶一致性搜索的运动补偿场间插值算法．

在该算法中，选取与当前待插值场相邻的前一个重建图像为参考帧，同时选取大小为4像素×3像素的待匹配块和16像素×15像素的搜索窗，采用奇偶一致性搜索方式进行搜索．其中如图1所示，上下相邻待匹配块共用一行．图2是匹配示意图，当18与18最接近时，就认为该匹配块是最佳匹配块，那么待匹配块中14就由14进行填充，进而获得运动补偿的插值，其中，参考块与待匹配块接近程度用式(1)表示，即当SAD值最小时就认为对应的参考块是最佳匹配块．

图2 块匹配过程示意

针对搜索过程，本文引入了奇偶一致性搜索的概念．本文中的奇偶一致性是指参考块与待匹配块之间相对应像素点都处在原始图像中的奇行或偶行，而满足该要求的搜索过程称之为奇偶一致性搜索，如图2所示，参考块中的已插值像素18和待匹配块的原始像素18同属于原始图像中的奇行或偶行．部分实验结果表明，在这种情况下，参考块与待匹配块之间的相关性比不符合奇偶一致性的参考块与待匹配块之间的相关性更大．相比较全搜索，奇偶一致性搜索在计算复杂度上减少了50%,，针对部分测试序列，PSNR提升了0.2,dB左右．这是因为全搜索方法搜索出来的最佳匹配块是SAD值最小的参考块，但这个块可能不满足奇偶一致性特征，因而获得的运动补偿值可能并不准确．

虽然搜索过程考虑了奇偶一致性，但是仍然存在因运动估计错误而导致运动补偿插值失真的情况．针对这一问题，采用4抽头的中值滤波在一定程度上抑制这种情况的发生．传统上，针对运动补偿失误所使用的中值滤波一般是3抽头，即运动补偿值和待插值位置的上下最相邻的2个像素值[2]，比如使用3抽头中值滤波的时域递归去隔行算法(TR_MID)[2].因为最近的相邻像素具有最高的相似性，从而使得行平均算法具有较好的客观性能[8]，因此本文考虑行平均算法的插值结果，采用4抽头的中值滤波．具体如式(2)所示，其中MC(，)是上述运动补偿获得的插值，(－1，)和(＋1，)是该插值位置垂直方向上最相邻的2个像素值，LA(，)是利用行平均算法获得的该点的插值，(，)是最终的插值结果．

     (2)

2 基于梯度辅助的场内多方向插值

传统的基于边缘方向插值算法主要是通过像素值相似性来确定边缘方向，可以大致分为两类：基于像素点差值求边缘方向和基于像素块差值求边缘方向．基于像素点差值求边缘方向灵敏度高，但易于受到噪声干扰，比如ELA、EFLA等；基于像素块差值求边缘方向对噪声有较强的抵抗力，但针对一些窄边缘却难以检测出来，比如MELA、HEDI[9]等．因此，近几年有一些新的算法引入了相邻像素之间的梯度相似性信息进行边缘预测，取得了较好的去隔行效果，比如FDD[10]、FSID[8]、GGI[11]等．本文结合梯度信息与像素值相似性信息，提出一种基于梯度辅助的场内多方向插值方法．

在本方法中，使用像素值相似度信息和梯度信息预测边缘方向．如图3所示，本文先使用相邻像素之间的像素值相似度信息确定大致的边缘方向．其中，和由式(3)计算所得，分别表示钝角方向和锐角方向的像素块绝对差值和．如果＞，那么边缘方向的角度是锐角，在此基础上，若利用梯度的相位信息求得边缘方向的角度为钝角，那么使用该角的补角；如果＜，那么边缘方向的角度是钝角，在此基础上，若利用梯度的相位信息求得边缘方向的角度为锐角，那么使用该角的补角；如果＝，那么中心待插值像素采用行平均的方法进行插值．在确定了大致的边缘方向之后，利用梯度信息中的相位信息进行更小范围的边缘方向预测．本文使用的梯度算子是sobel算子，如式(4)所示．

图3 像素值相似度信息确定大致的边缘方向

   (3)

   (4)

   (5)

因此利用梯度信息中的相位信息求得的边缘方向dir＝tan，然后取与方向dir最接近的数，作为最终的插值方向．其中，如图4所示，插值方向∈{-5，-4，-3，-2，-1，-1/2，0，1/2，1，2，3，4，5}．如果超过这个集合的范围就认为插值方向与水平方向接近平行，那么此时就使用行平均算法处理该种情况．根据最终求得的插值方向，由式(6)获得最终的插值结果．

   (6)

图4 插值方向示意

3 自适应插值的混合去隔行方法

时域插值算法和空域插值算法一般是通过运动检测或者权值进行结合，比如文献[7]提出使用权值自适应地结合多种时域和空域插值算法，但是权重计算异常复杂，往往难以很好地结合这些算法的优点，有时候会导致总体算法性能的降低．鉴于这种情况，本文利用运动检测和边缘检测对图像进行划分，自适应结合基于奇偶一致性搜索的运动补偿场间插值、场合并插值、基于梯度辅助的场内多方向插值和行平均插值等算法．

3.1 运动检测

本文采取的运动检测方法通过比较当前图像和前一个图像对应位置大小为4像素×3像素的块之间差值diff确定图像不同区域的运动情况．具体如式(7)所示．

(7)

式中：表示当前待测的4像素×3像素区域；th_low和th_high为设定的阈值．

3.2 边缘检测

本文采用的边缘检测方法是比较阈值与当前像素点的水平方向梯度G和垂直方向梯度G之间的大小，来确定当前像素是否处于边缘区域．具体如式(8)所示．

   (8)

式中：表示当前待测像素点；TH为设定的阈值．

3.3 自适应插值

通过上述的运动检测和边缘检测对图像进行划分，针对不同区域使用不同的去隔行方法，因而自适应地结合了时域插值和空域插值的优点．本文主要把图像分为3类：静止区域、运动幅度较小区域、运动幅度较大区域．针对静止区域使用场合并的方式进行插值，提高图像的垂直分辨率，恢复视频图像原有的帧结构．针对运动幅度较小区域，使用基于奇偶一致性搜索的运动补偿场间插值方法进行插值，使得该区域的插补像素值更加精确．针对运动幅度较大区域，通过边缘检测再一次划分为边缘区域和平滑区域，边缘区域使用基于梯度辅助的场内多方向插值方法进行插值，较好地保护物体边缘的连续性和锐利度，平滑区域使用客观性能较好的行平均算法进行插值，降低总体算法的计算复杂度．如图5所示．

图5 本文所提算法的流程

4 实验结果及讨论

本节从视频质量评价和计算复杂度两个方面分析本文所设计的混合去隔行算法的性能，其中参与比较的传统去隔行算法有LA、ELA、MELA、FDD、TR_MID．参与比较的典型测试视频序列如下：352像素×288像素(akiyo)，720像素×576像素(clown、horsecab、rally、splash)，1,280像素×720像素(sailormen、spincalendar)，1,920像素×1,080像素(kimono)．实验使用C++语言，在VS2010上进行，CPU为Intel i3-4160，3.60,GHz．表1是针对这些典型测试视频序列，各个去隔行算法获得的视频平均PSNR值．

由表1可以发现，本文算法相比较这几个传统的经典去隔行算法，在平均PSNR上提升0.7,dB左右，展现了较好的去隔行效果．其中，相比较使用中值滤波的运动补偿插值算法TR_MID，本方法获得了0.7,dB左右的PSNR提升；相比较使用梯度信息插值的FDD算法，本方法获得将近0.8,dB左右的PSNR提升；而比较传统的基于边缘方向插值算法，本方法则获得1,dB左右的PSNR提升．这些说明使用像素值相似性和梯度信息结合的方式进行边缘预测是有效的，同时也说明了本文算法能够较好地融合时域插值和空域插值的优点．

图6是各种去隔行算法对测试序列rally处理后所得结果的部分截图，从这些图中得出的初步主观感受可以发现，ELA、MELA、FDD和TR_MID等算法由于不正确的边缘估计和运动估计，导致车身边缘出现了褶皱问题．而在本文算法的效果中，物体的边缘和原图基本一致，并没有出现褶皱现象．这说明本文算法的运动估计和边缘处插值方向的估计更加准确，基本保持了物体边缘的连续性，因而也在一定程度上提升了图像的清晰度和锐利度．

表1 各种去隔行算法的平均PSNR比较

Tab.1 Comparison of average PSNR of different de-interlacing algorithms

图6 各种去隔行算法的主观效果比较

关于计算复杂度，表2是各种去隔行算法处理每场图像所需平均时间的比较．从表中数据可得，对使用到的所有测试视频序列，LA、ELA、MELA这3种算法所需的平均处理时间都要比其他3种算法所需平均处理时间短，展现出计算复杂度较低的特点．而本文所提算法在处理akiyo这类包含较多静止场景内容的测试视频序列时，所需平均处理时间也要短于FDD和TR_MID算法的平均处理时间，同样具有计算复杂度较低的特点．在处理horsecab这类包含较多运动场景内容的测试视频序列时，本文所提算法需要的平均处理时间要比FDD算法的平均处理时间稍高，但是远少于TR_MID算法的平均处理时间，这也展示本文所提算法的计算复杂度不是很高的特点．总体上，与这几个传统的去隔行算法相比，本文所提算法的计算复杂度适中．

表2 各种去隔行算法处理每场图像所需平均时间比较

Tab.2 Comparison of average computation time of different de-interlacing algorithms

5 结 语

本文通过运动检测和边缘检测对图像的内容进行划分，自适应地结合时域插值算法(基于奇偶一致性搜索的运动补偿场间插值、场合并插值)和空域插值算法(基于梯度辅助的场内多方向插值、行平均插值)．其中基于奇偶一致性搜索的运动补偿场间插值算法考虑了参考块与待匹配块之间对应像素点的奇偶一致性关系，基于梯度辅助的场内多方向插值算法考虑了像素值相似性信息和梯度信息．这些措施降低了算法的计算复杂度，同时在一定程度上避免了因为错误的运动矢量和不正确的边缘方向造成的插补问题，表现了比传统算法更优良的性能．但是，在算法中像素值相似性信息和梯度信息的结合使用还有改进的空间，另外运动检测和边缘检测的性能还可进一步加强．

［1］ Lee K，Lee C. High quality spatially registered vertical temporal filtering for deinterlacing[J].，2013，59(1)：182-190.

［2］ Haan G D，Bellers E B. Deinterlacing：An overview[J].，1998，86(9)：1839-1857.

［3］ Mahvash Mohammadi H，Savaria Y，Langlois J M P. Enhanced motion compensated deinterlacing algorithm [J].，2012，6(8)：1041-1048.

［4］ Kim W，Jin S，Jeong J. Novel intra deinterlacing algo-rithm using content adaptive interpolation[J].，2007，53(3)：1036-1043.

［5］ Brox P，Baturone I，Sanchez-Solano S，et al. Edge-adaptive spatial video de-interlacing algorithms based on fuzzy logic[J].，2014，60(3)：375-383.

［6］ Trocan M，Mikovicova B，Zhanguzin D. An adaptive motion-compensated approach for video deinterlacing[J].，2012，61(3)：819-837.

［7］ Chang J，Kim Y D，Shin G S，et al. Adaptive arbitration of intra-field and motion compensation methods for de-interlacing[J].，2009，19(8)：1214-1220.

［8］ Chen X，Jeon G，Jeong J. Filter switching interpolation method for deinterlacing[J].，2012，51(10)：2002-2009.

［9］ Fan Z. Hierarchical edge-directed interpolation for de-interlacing[C]// 2011Berlin，Germany，2011：249-250.

［10］ Jin S，Kim W，Jeong J. Fine directional de-interlacing algorithm using modified sobel operation[J].，2008，54(2)：587-862.

［11］ Zhang H，Rong M. Deinterlacing algorithm using gradient guided interpolation and weighted average of directional estimation[J].，2015，9(6)：450-460.

(责任编辑：王晓燕)

Hybrid De-Interlacing Algorithm with Adaptive Interpolation Based on Temporal-Spatial Characteristics

Zhang Tao1，Chen Youzhi1，Lei Zhichun2

(1. School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China；2. School of Microelectronics，Tianjin University，Tianjin 300072，China)

De-interlacing is a key technology in the process of converting a interlaced video into a progressive video．But the traditional motion compensated de-interlacing algorithms often suffer from some troubles，such as error propagation，inaccurate motion estimation and high computation complexity．Thus，a motion compensated de-interlacing algorithm based on parity consistency search was proposed．In addition，in view of the problem that the edge direction wasn’t detected exactly in the traditional de-interlacing algorithms based on the edge direction，a multi-direction interpolation algorithm based on gradient-assistance was proposed in this paper．Finally，the above proposed de-interlacing algorithms，field merging interpolation and line averaging interpolation were merged adaptively to form a hybrid de-interlace with adaptive interpolation based on temporal-spatial characteristics．Making use of the temporal-spatial characteristics of the video，the finally proposed algorithm effectively solves the problems that the wrong motion estimation and the inaccurate edge direction resulted in mistaken interpolation．The experimental results show that compared with traditional de-interlacing algorithms，the proposed algorithm could offer 0.7,dB PSNR gain under low computational complexity.

temporal-spatial characteristics；parity consistency；gradient-assistance；de-interlacing

10.11784/tdxbz201611010

TP391

A

0493-2137(2018)01-0073-06

2016-11-04；

2017-04-24.

张 涛（1975—  ），男，博士，副教授．

张 涛，zhangtao@tju.edu.cn.

天津市科技支撑计划重点资助项目(16YFZCGX00760)．

the Key Science and Technolgoy Support Program of Tianjin，China(No.,16YFZCGX00760).