用于DT网格模型基视频编码的三角形分割准则.doc

第5期郭大波等：用于DT网格模型基视频编码的三角形分割准则93用于DT网格模型基视频编码的三角形分割准则郭大波1,2，卢朝阳1，焦卫东1，胡星星1（1. 西安电子科技大学 ISN国家重点实验室，陕西 西安 710071;2.山西大学 物理电子工程学院，山西 太原 030006）摘 要：在分析DT(Delaunay triangulation)网格已有的2种分割准则灰度误差最小化准则和灰度分布均匀化准则在网格基编码不足的基础上，提出了一种新的DT网格分割准则灰度误差平方和最小化准则，使三角形分割更加合理有效，编码性能比以前的方法有明显提高。在此基础上提出了帧内变换编码/帧间网格基运动估计的混合编码方案，该方案可应用于复杂运动和背景的视频序列中，突破了以往模型基编码只能应用于视频会议的限制。实验结果表明,该编码方案在复杂运动和背景的应用场合高出了H.263的编码性能。关键词：Delaunay三角化；网格模型基编码；图像分割准则；彩色视频编码中图分类号：TN919 文献标识码：B 文章编号：1000-436X(2009)05-0088-06Triangular segmentation criterion for DTmesh based video codingGUO Da-bo1,2, LU Zhao-yang1, JIAO Wei-dong1, HU Xing-xing1 (1. State Key Lab. of Integrated Service Networks, Xidian Univ.,Xian 710071,China; 2. College of Physics & Electronics Engineering, Shanxi Univ., Taiyuan 030006,China)Abstract: Based on the analysis of the deficiency of two previous Delaunay triangular mesh segmentation criterionsminimize difference of gray and minimize variance of gray, a new triangular mesh criterion, minimize sum of squared difference of gray, was proposed. The new segmentation was more rational and efficient so that the coding performance on it was improved obviously than before. Furthermore, a new hybrid coding scheme was also proposed under the criterion with transformation coding for intra frame and mesh-based motion estimation for inter frame, which could be applied in video sequence with complex motion and background. The restriction that mesh model based coding was only applicable in video conference applications was broken. Experimental result shows that the proposed scheme has a better performance than H.263 in applications with complex motion and background.Key words: Delaunay triangulation; mesh model based coding; image segmentation criterion; color video coding1 引言收稿日期：2008-03-19；修回日期：2009-03-30基金项目：国家自然科学基金资助项目（60472083,60872141）Foundation Item: The National Natural Science Foundation of China(60472083, 60872141)对于DT网格模型基编码，如何高效地用三角形网格分割图像，直接关系到帧间节点的运动跟踪与三角形片的运动估计和补偿的精度，从而最终影响到编码效率。本文在文献14的基础上，提出了一种新的DT网格分割的数学准则，使DT网格分布更加合理高效，以提高预测图像的PSNR，最终减少码率。本文在分析过去算法的不足之处的基础上，导出了新的算法准则。过去的有关模型基编码的文献主要针对具有简单背景、简单运动及少数物体的视频会议和可视电话等场合的甚低码率传输5, 6。存在的问题有，网格模型基的帧内编码方案采用基于节点灰度或彩色值稀疏表示，三角形或四边形平面内各点的灰度和彩色值由节点的灰度和彩色值内插得到79。但以往的三角形网格的帧内编码算法对头肩像视频有较好的编码效率，对复杂背景下的视频图像的帧内编码效率并不高(这一点将在2.3节进行详细的分析)。鉴于目前网格逼近的数学模型还不具有普适性，本文提出的编码器的帧内编码将采用目前流行的变换编码+量化+熵编码模式，由于它的普适性和主客观效果上都有较好的表现，可保证编码器在复杂背景序列有较好的表现。这一技术已十分成熟，在本文中不作详细说明。基于以上想法，本文提出一种帧内变换编码+帧间DT三角形网格运动估计的混合编码框架，并对3种方法(包括H.263的高级预测模式)在3种不同的测试序列进行了实验比较。本文将着重讨论网格生成的导出过程，简单介绍编码器的构造及原理，其详细介绍可参考文献2, 4。2 DT网格生成的数学模型的分析和导出本节将首先回顾和分析过去提出的2种DT网格的生成准则1,3，分析其存在的不足之处，然后导出新的生成准则。本文所用的数学符号意义如下所示。M：三角形片总数，M=1,2,M。N：节点总数(N与M有关)，N=1,2,N。K：各三角形的节点号，K=3,K=1,2,3。n(m, k) ：第m个三角形的第k个节点所对应的节点号索引函数。D：网格所表示的图像域。p：图像域D中点的位置, p=x, yT。m, k (p)：第m个三角形中第k个节点的形状函数, kK, m M。Dm：第m个三角形的域, DmDn=,if mn。：第n-1帧恢复图像。2.1 基于内插的图像逼近图像可看作一个二维域上的曲面，它可由DT网格生成的多个平面逼近，这种方法是有限元法在图像领域的应用10。图像中任意一点的灰度值由该点所在三角形的3个顶点的灰度值内插后逼近，这样图像可由三角形的节点处的灰度值稀疏表示，为基于内插的帧内压缩编码方法1,7, 8奠定了基础。设原始图像为I=f (p)，pD，用三角形平面的逼近值可表示为(1)(2)如用平面线性插值逼近，则根据三角形公式(3)可以得到式(2)中的3个形状函数为(4)其中，。2.2 基于仿射变换的图像逼近(预测)图像中任意一点的灰度值由该点在参考图像的对应三角形内的对应映射点的灰度值得到，这一方法称作为仿射变换，这样当前帧图像可由参考帧图像预测，可用于帧间编码2。(5)(6)式(6)的矢量表示形式为，或 (7)仿射变换除了能描述物体平移这一简单运动外，还可以描述物体的转动以及摄像机的变焦、摇、倾和滚，而这一特性是基于块的运动估计所不具有的11。2.3 灰度误差极小化(MD, minimize difference)准则与块和规则网格分割图像不同，DT网格是一种与图像内容有关的自适应网格，它根据图像内容将图像分割成大小不一的三角形片。一般地，均匀区域的三角形片较大，纹理丰富区域的三角形片较小。文献1提出了一种逐渐逼近的迭代DT网格的生成算法，每一迭代过程选择逼近原图像最差的三角形为分裂三角形，并根据一定的规则在其中选择一个插入点，然后根据最大最小角准则或与其等价的圆规则，对DT结构进行局部的合并和分割，直至满足一定的条件迭代结束。在生成DT网格迭代分裂合并算法的第一步迭代过程中，分裂三角形和插入点的选择是关键的，令为第m个三角形的最大逼近差异值，则分裂三角形为(8)最佳插入点为(9)准则函数为(10)其中，C0是描述精度阈值。如准则函数小于该阈值，则迭代终止。其优点是对只有少量物体和简单背景的逼近效率高，缺点是对复杂背景的图像(如Aqua)逼近效率不高，容易受噪声的影响。2.4 灰度分布均匀化(MV, minimize variance)准则用如下两式计算每个三角形区域内灰度的均匀程度，即(11)(12)分裂三角形的选择准则为(13)这样，对于等面积的三角形，高纹理区优先于低纹理区，低纹理区优先于均匀区。文献3对文献1进行了改进，插入点由原来的重心改为灰度变化最大的特征点，这是因为特征点在运动估计过程中比普通点更容易可靠地搜索到。(14)(15)其优点是适合于帧间的仿射变换预测，缺点是过于强调了特征点，当特征点位于插入三角形的边或顶点附近时，会出现狭长三角形。如图1所示，设cgfedb是图像中的一条强边缘，abc是某次迭代时的分裂三角形，则根据此准则，插入点一定在该边缘上，设为d点，分裂后的三角形cdb为狭长三角形，在以后的分裂迭代中，插入点还会在这条边缘上，假设为g、f、e，与它们相连所构成的三角形逐渐变得狭长，会造成过分割，并可能对今后的运动估计产生不良影响。图1 MV准则下狭长三角形的形成过程2.5 灰度误差平方和最小化(MSSD，minimize sum of squared differences)准则2.5.1 分裂三角形的选择笔者认为，每次迭代时分裂三角形应选择在PSNR最差的三角形上，因此选择目标函数为灰度误差平方和。令为第m个三角形的差异值之平方和，最优过程为(16)为防止过分割，可定义一个三角形片面积的下限，如16像素，并假设如果最差三角形片的描述精度不低于32dB就停止迭代，则迭代终止条件可定义为，即(17)实际算法的迭代终止条件有3个：预定节点数、预定三角形数和式(17)，三者是“或”的关系。2.5.2 插入点的选择插入点的选择关系到下一层网格的形状和描述效率，MD准则下得到的插入点一般会位于分割三角形的内部，不会位于邻近三角形顶点或边的附近，这是由内插函数所决定的。因此得到下一层的三角形形状较好，一般不会出现狭长三角形，但最大误差点往往不一定是特征点，易受噪声的干扰，在帧间的节点运动估计和补偿时表现不好。MV准则下得到的插入点是典型的特征点，在帧间的节点运动估计和补偿时表现良好，但其极易在下一层形成狭长三角形，并造成过分割。本文的方案是结合两者的优点，令(18)(19)构造代价函数(20)(21)其中，为形状控制权重，1-为边缘控制权重。实验观察到，随着的增大，尖锐三角形会逐渐增多，经大量实验得到的最佳情况是=0.4。实际算法中计算插入点需要二步，第一步搜索计算式(18)和式(19)；第二步搜索计算式(21)。3 DT网格模型基混合编码方案图2为本文提出的帧内变换编码+帧间DT三角形网格运动估计的混合编码框架的框图。图中帧内/帧间指示信号p控制开关和DT网格发生器DT(MSSD)，图2 适用于复杂背景序列的DT网格基编码模型帧内信号触发帧内编码的同时触发网格发生器工作，产生的网格结构存储在网格存储器Mesh中，以便进行帧间连续运动估计，游程编码后的节点信息n送往复合输出端，图中的其他标记同H.26312。有关彩色视频的编码细节可参考文献4，本文不再赘述。4 实验结果及分析为测试新准则MSSD的性能，本文先在相同的平台下对MV准则进行比较，MD准则是针对帧内编码的，在帧间运动估计和补偿表现不佳，无需比较；然后再与相同平台下的H.263高级运动模式进行比较。实验环境是Pentium IV 1.6GB，512MHz内存，Windows XP + VC 6.0，模型基编码是寄生在H.263校验模型上实现的。实验序列有Miss American(109帧)、Mother and Daughter(208帧)和Foreman(298帧)。在2种准则下的三角形分割结果如图3所示，在头发和左右两肩处，MSSD准则的三角形数比MV准则要多，这对运动估计和补偿是有好处的。实验中发现，MSSD准则下的多数P帧的编码比MV准则下的P帧的编码少1 0002 000bit。(a) MV准则(b) MSSD准则图3 2种准则下的三角形分片分布(200个节点，390个三角形)本文从预测图像(未加残差)的亮度分量的PSNR、亮度和色度3分量的平均PSNR以及码率综合考察2种准则的性能。观察图4可看出，MSSD准则的预测精度比MV准则的高，而码率却比MV准则低。折衷考虑精度和码率，可以粗略地得到最 (a) Miss American (b) Mother and Daughter (c) Foreman图4 2种准则的性能比较佳节点数，如：Miss American是200点、Mother and Daughter是150点、Foreman是250点。表1 实验结果综合比较综合性能Miss AmericanMother and DaughterForemanDTH.263DTH.263DTH.263帧间量化因子/节点数8/2008/8/1508/12/2508/亮度分量的PSNR37.183 739.110 434.958 935.634 129.456 429.213 13分量的平均PSNR38.040 739.642 439.911 039.559 335.535 333.402 6码率0.008 7510.006 9340.010 1320.008 0440.022 440.023 55预测图像的主观效果多数帧效果良好，少数帧有三角形畸变所有帧有方块效应多数帧效果良好，少数帧有三角形畸变所有帧有方块效应多数帧效果良好，少数帧有三角形畸变所有帧有方块效应编码时间/帧率663/ 0.16101.5/1.1758/ 0.5150.2/1.42119/0.14285.4/1解码时间/帧率3.8/28.70.7/1557.1/29.31.4/148.610.9/27.33.2/93表1所列的是在MSSD准则下DT网格基编码和H.263高级运动模式综合性能比较，两者帧内量化参数均为8。从实验结果来看，前2个序列DT模型基的性能不及H.263，第3个序列DT模型基的性能比H.263好。这说明了网格基编码模型的仿射变换适合描述复杂运动模型11，因为在Foreman序列中有较多的身体转动，脸部夸张变形，摄像机镜头的摇(panning)、倾(tilting)和变焦(zooming)，所以仿射变换适合于描述这些运动；同时Forman序列也是复杂背景序列，说明本文提出的混合编码方案对适合复杂背景序列也有较好的压缩效率。另外，DT模型基的预测图像的视觉效果好于H.263，这在甚低码率下的视频传输是非常有用的，如残差编码只传输部分能量较大宏块的情形2。DT模型基的编码运算时间是H.263的6倍左右，但解码可满足实时要求。5 结束语本文提出了DT模型基编码的三角形分割的新数学准则，在编码性能上，较以前的方法有了比较明显的提高。模型基编码不仅能在视频会议等简单情形应用，而且可以应用于复杂运动和复杂背景的视频编码中，并有一定的优势。其不足是编码效率较低，相信随着运算器性能的不断提高和算法的优化改进，最终可达到实时性要求。H.264的多模式编码技术是模型基编码可借鉴的方向，如帧内预测可大幅度提高I帧精确度，同时为运动估计奠定了良好的基础；帧间双向多帧运动估计可解决运动遮挡问题等。参考文献：1卢朝阳, 颜尧平, 吴成柯. 多分辨率DT模型基图像表示方法J. 西安电子科技大学学报, 1999, 26 (3): 278-285.LU Z Y, YAN Y P, WU C K. Multiresolution delaunay triangulation model-based image representation schemeJ. Journal of Xidian University, 1999, 26 (3): 278-285.2卢朝阳, 周幸妮, 高西全等. 三角形网格基活动图像编码研究运动估计、运动补偿和残差图像处理J. 通信学报, 2002, 23 (11): 65-73.LU Z Y, ZHOU X N, GAO X Q, et al. Triangular mesh model based video coding: motion estimation, compensation and residual image processing J.Journal on Communications, 2002, 23(11):65-73.3韩军功, 卢朝阳. 基于Delaunay 三角形网格的立体图像编码算法J. 计算机辅助设计与图形学学报, 2004, 16 (12): 1708-1712.HAN J G, LU Z Y. Delaunay triangulation mesh based stereo image coding algorithmJ. Journal of Computer-Aided Design & Computer Graphics, 2004, 16 (12): 1708-1712.4焦卫东, 卢朝阳, 何华君等. Delaunay三角形网格的彩色视频帧间编码方法J. 通信学报, 2007, 28 (9): 119-124.JIAO W D, LU Z Y, HE H J, et al. Inter-frame image coding scheme of color video based on Delaunay triangulation meshJ. Journal on Communications, 2007, 28 (9): 119-124.5AIZAWA K, HUANG T S. Model-based image coding: advanced video coding techniques for very low bit-rate applicationsJ. Proceedings of the IEEE, 1995, 83(2): 259-270.6吴枫, 高鹏, 高文. 基于网格模型的运动估计技术J. 电子学报, 2000, 28 (5): 47-51.WU F, GAO P, GAO W. Motion estimation technologies based on mesh modelJ. Acta Electronica Sinica, 2000, 28 (5): 47-51.7卢朝阳, 周幸妮, 高西全等. 三角形网格基活动图像编码研究基本框架和I帧编码J. 通信学报, 2002, 23 (10): 66-70.LU Z Y, ZHOU X N, GAO X Q, et al. Triangular mesh model-based video coding- basic framework and intra-frame coding J. Journal on Communications, 2002, 23 (10): 66-70.8焦卫东, 卢朝阳,何华君等. 基于Delaunay三角形网格的彩色视频帧内编码方法J. 西安电子科技大学学报, 2007, 34(4): 543-548.JIAO W D, LU Z Y, HE H J, et al. Intra-frame image coding scheme of color video based on dlaunay triangulation meshJ. Journal of Xidian