王燕妮,樊养余

(1.西安建筑科技大学信息与控制工程学院,西安 710055;2.西北工业大学电子信息学院,西安 710072)

1 引 言

视频对象形状编码是基于内容的视频编码特有的,有对象就有形状,而基于链码的形状压缩是视频传输中的重要环节,也体现了形状编码的重要性。目前的形状编码有四方向链码和八方向链码[1],主要由形状和位置编码组成,形状边界处有断开或错误划分情况,这样将导致图像编码质量下降。因此,本文在对视频图像进行区域生长[2-3]分割的基础上,为了提高对象形状边界的精确性,提出七方向差分链码的轮廓形状编码,预测达到满意的恢复图像质量和很高的压缩比。

2 常规轮廓形状链码

链码用于表示图像的边界线,一般由顺次连接的具有有限长度和方向的直线段组成。线段的方向用四方向链码和八方向链码表示,如图1所示。

链码是对图形边界按顺时针方向每对像素的连接线段赋予一个方向而生成的。对于任意的图像形状轮廓,以图形下部中点为出发点,可编出四方向链码和八方向链码。从链码生成可知,边界线必须是连续的,不能断开和缺口,也不能噪声太多,使得在一个点周围有多个点,难以确定连接线段的方向。为此,在原图像中选择比像素间隔大的网格而对边界进行重新取样,产生近似处理,近似精度取决于网格的大小,这样就可以消除原图像边界点和噪声点的影响。

图1 两种常规链码Fig.1 Two conventional chain codes

编码[4-5]的目标是被编码的结构信息最小化。对于四方向Freeman链码(4F),有4个码值,需要2位二进制位对其进行编码,码长为2。八方向Freeman链码(8F),有8个码值,需要3位二进制位对其进行编码,码长为3。可以看到,每个小直线段表示每个码的移动,而码字的编码是根据链码中的一个码与其前一个码前进方向之间的角度差。在表示对象形状曲线或边界时,其中每个码与其后一个码的码值通常是相同的或是相邻的,或者说在链码中,一个码所表示的方向与其前一个码的方向相同或相近情况出现的概率大大高于两者之间方向变化很大的情况。因此,提出新的七方向差分链码(Seven Differential Chain,SDC),每个码值被定义来表示该码与其前一个码之间的方向变化角度值。

3 七方向差分链码的视频对象轮廓形状编码

3.1 七方向差分链码

七方向差分链码编码方法可以用较短的链码表示区域的边界,缩短链码表示法的链码长度,减少视频图像信息的存储量。用链码表示一个图像边界时,定义7个码值表示链码的7个前进方向,对其方向定义如图2所示,以逆时针方向旋转,上半部分采用45°角5个方向,下半部分采用60°角2个方向的小直线段表示每个码的移动,通过统计各种应用中的1500多条数字曲线或区域边界中前后码元素间的方向变化的各种角度差值的出现概率。统计结果表明,大部分区域边界编码的码值是相同或相邻的,或者说在链码中一个码所表示的方向与其前一个码的方向相同或相近情况的概率大大高于两者之间方向变化很大的情况。因此,七方向新链码中的7个小直线段被定义来表示一个码与其前一个码前进方向之间的角度差。

图2 七方向差分链码Fig.2 Seven differential chain

将七方向差分链码中前后码元素间的方向变化的各种角度差值,对可能出现的概率进行了统计,如表1所示。

表1 各种角度差值出现的概率Table 1 The probability of value in angle difference

当存储视频图像区域或数字曲线的信息时,则可根据上述概率对边界的每一个像素进行编码,形成链码来表示和存储信息。

3.2 七方向差分链码编码

霍夫曼编码是一种可变字长编码方式,是由David.A.Huffman发展起来的。它是根据每一个源字符出现的估算概率而建立起来的,出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的。例如,在英文中,“e”的出现概率很高,而“z”的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,“e”则用一个位(bit)来表示,而“z”则可能花去25个位。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。两者相比,“e”使用了一般编码的1/8的长度,“z”则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确估算,就可以大幅度提高无损压缩的比例。

霍夫曼编码算法步骤如下:

(1)首先统计信源中各符号出现的概率,按符号出现的概率从大到小排序;

(2)把最小的两个概率相加合并成新的概率,与剩余的概率组成新的概率集合;

(3)对新的概率集合重新排序,再次把其中最小的两个概率相加,组成新的概率集合。如此重复进行,直到最后两个概率的和为l;

(4)分配码字:码字分配从最后一步开始反向进行,对于每次相加的两个概率,给大的赋“1”,小的赋“0”(也可以全部相反,如果两个概率相等,则从中任选一个赋“0”,另一个赋“1”即可),读出时由该符号开始一直走到最后的概率和“1”,将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好,就是该符号的霍夫曼编码。

以七方向差分链码的7个码值符号和其概率作为输入,用霍夫曼编码方法对其编码,可得到具体的编码过程如图3所示。

图3 新链码编码过程Fig.3 The process of new chain coding

码值如下:

根据信息论理论,该编码的平均码长(bit)为

式中,li表示第i个码值的编码长度,pi表示其出现的概率大小。则该编码的信源熵(bit)为

该编码的效率为

3.3 区域填充

区域填充算法是将指定不规则区域内部像素填充为填充色的过程,在计算机辅助设计和图像处理等领域有广泛应用,包括种子填充(Seed Filling)算法、扫描线填充(Scan-Line Filling)算法等。种子填充算法又称为边界填充算法,其基本思想是:从多边形区域的一个内点开始,由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的,则种子填充算法可逐个像素地处理直到遇到边界颜色为止。该算法优点是非常简单,缺点是需要大量栈空间来存储相邻的点。

为了减少递归次数、提高效率,在此采用扫描线算法,即通过沿扫描线填充水平像素段,来处理四连通或八连通相邻点,这样就仅仅只需要将每个水平像素段的起始位置压入栈,而不需要将当前位置周围尚未处理的相邻像素都压入栈,从而可以节省大量的栈空间。

扫描线填色算法,其基本思想是:用水平扫描线从上到下扫描由点线段构成的多边形。每根扫描线与多边形各边产生一系列交点。将这些交点按照横坐标进行分类,将分类后的交点成对取出,作为两个端点,以所填的色彩画水平直线。多边形被扫描完毕后,填色也就完成。

SDC算法流程如图4所示。

图4 SDC算法流程图Fig.4 The flow chart of SDC algorithm

3.4 各种链码间的比较

对于平均码长,4F链码和8F链码采用固定长度编码,其4个码值和8个码值分别使用2位和3位二进制数进行编码,码长为2和3;而七方向差分链码编码的平均码长为每码2.203位。对于链码总位数,是平均码长乘以链码的长度,则以上3种链码的总位数如表2所示。

表2 链码所需位数比较Table 2 The comparison of required chain code number

4 仿真实验

采用区域生长法对视频图像进行对象分割,在此基础上,用SDC编码跟踪视频对象边缘进行压缩编码并进行区域填充。

4.1 实验1:重建帧的比较

采用missamerica(360×288)序列,以第一帧作为参考帧,进行视频分割后,再对其对象轮廓进行七方向差分链码编码,分别用4F、8F和SDC得到第二帧的重建帧,结果如图5所示。可看出,八方向Freeman链码和七方向差分链码编码重建的视频图像非常接近视频图像的原始帧。

图5 重建帧的比较Fig.5 The comparison of reconstruction frame

4.2 实验2:误差帧的比较

采用代表运动剧烈的susie(352×240)序列的第十帧作为参考帧,进行视频分割,再对其对象轮廓进行七方向差分链码编码。分别用4F、8F和SDC得到第十一帧的误差帧,结果如图6所示。

图6 误差帧的比较Fig.6 The comparison ofmsE

4.3 实验3:性能的比较

采用football(352×240)序列,以第五帧作为参考帧,分别用4F、8F和SDC算法恢复下一帧,依次传输10帧视频图像,得到误差MSE和相应的峰值信噪比(PSNR),结果如图7所示。

4.4 实验4:搜索时间的比较

选取视频序列forman(352×288)的第五帧作为测试帧,对于4F、8F和SDC算法,分别得到第六帧的恢复帧。压缩编码的时间如表3所示。

表3 各种算法的压缩编码时间Table 3 The time of compression coding

图7 各种算法的性能比较Fig.7 The performance comparison of different algorithms

在实验1中,对于missamerica序列,以第一帧作为参考帧,进行对象分割后,分别用4F、8F和SDC算法得到第二帧的重建帧。可以看出,SDC算法总体上优于其它两种算法,只是在一些个别的区域劣于8F算法。在实验2中,采用susie序列对恢复图像的误差帧进行比较。可以看出,4F算法的误差最大,8F和SDC算法的误差相差不大,但8F算法的误差略低于SDC算法。在实验3中,采用football序列对恢复图像的性能进行比较。可以看出,在传输帧数较多的情况下,SDC算法的性能均优于其它两种算法,其中PSNR比8F算法提高了1.2dB。在实验4中,用4F、8F和SDC算法进行形状压缩编码,比较可得4F算法的编码时间最短,但SDC算法比8F算法的运行时间减少了2.1ms。综合以上实验结果,考虑到算法运行时间和恢复图像质量之间的矛盾关系,选取SDC算法,在获得较清晰图像的前提下,可实时地传输视频。

5 结 论

通过研究常规轮廓链码编码,根据对象形状曲线或边界上每个码与其相邻码的码值通常是相同的或是相邻的这一特征,提出基于对象分割的七方向差分链码的形状压缩编码,使用前后码元素间的方向变化的角度差值作为链码值,这样码值则集中在其中几个码元上,编码时需要的码长较短。从实验结果可知,七方向差分链码编码算法的峰值信噪比及运行时间都优于几种经典的链码编码,在实时视频通信中编码效果优良。

[1] 贺贵明,吴元保,蔡朝晖,等.基于内容的视频编码与传输控制技术[M].武汉:武汉大学出版社,2005.HE Gui-ming,WU Yuan-bao,CAI Zhao-hui,et al.Content based video coding and transmission control technology[M].Wuhan:Wuhan University Press,2005.(in Chinese)

[2] FAN J P,YAU D K Y.Automatic image segmentation by integrating color-edge extraction and seeded regiong rowing[J].IEEE Transactions on Image Processing,2001,10(10):1454-1466.

[3] FRANK Y SHIH,CHENG Shouxian.Automatic seeded region growing for color image segmentation[J].Image and Vision Computing,2005(23):877-886.

[4] 丁学君,田勇.一种利用SA-DWT的任意形状ROI编码方法[J].电讯技术,2006,46(6):150-153.DING Xue-jun,TIAN Yong.An Arbitrary Shape ROI Coding Method with SA-DWT[J].Telecommunication Engineering,2006,46(6):150-153.(in Chinese)

[5] 申杰,郑小玉,朱维乐.降低头肩视频序列编码码率的一种新方法[J].电讯技术,2005,45(5):18-22.SHEN Jie,ZHENG Xiao-yu,ZHU Wei-le.A New Method for Reducing Bit-Rate in Head and Shoulder Video Sequences[J].Telecommunication Engineering,2005,45(5):18-22.(in Chinese)