安 华，张 雄

(太原科技大学电子信息工程学院，太原 030024)



基于遗传算法的SVC非均等差错保护算法研究

安 华，张 雄

(太原科技大学电子信息工程学院，太原 030024)

由于网络传输环境的不稳定性，为了将可伸缩视频编码(Scalable video coding，SVC)的码流能够在异构网络上实现可靠高效的传输质量，采用了联合前向纠错技术的不均等差错保护(Unequal Error Protection).不均等差错保护根据数据重要度的不同对各层给予不同强度的保护量，然而如何合理分配各层所需的保护数据，使恢复的视频质量达到最优是研究中的难点。通过建立信道差错所引起的失真模型，利用遗传算法(Genetic Algorithms)得到了最优码率分配方案，通过实验与传统方法比较，该方法有效提高了解码端的重建视频质量，特别是在高丢包的网络环境下表现的更为出色。

可伸缩视频编码(SVC)；不均等差错保护(UEP)；失真模型；遗传算法(GA)；优化

无线网络技术的快速发展，无线视频传输已经成为视频传输中的重要部分，由于网络的异构性，用户可用的信道带宽不同以及终端设备的多种多样，传统编码方案不能保证各种客户端都能得到良好的视频质量。如何在异构网络上提供强健、高效的视频已成为重大的挑战，可伸缩视频编码(SVC)[1-3]作为H.264的扩展版本为解决这一问题提供了可能。

尽管可伸缩视频编码的比特流能适应不同的网络状况，但是想要获得高效、强健的视频质量仍面临巨大挑战，在网络丢包环境下，很小的丢包率就会显著降低SVC的峰值信噪比(PSNR)[4].为了解决这一难题，传统的做法是利用均等差错保护对各层数据给予相等程度的保护量，但在传输环境恶化时视频质量难以保障，近年来越来越多的研究者联合不均等差错保护解决了这一问题，改善了视频传输的质量[5-8]。在不均等差错保护中如何对码流合理优化成为了当下研究的热点课题，在文献[9-11]中建立了不同的失真模型来分配各层数据，文献[9]中的DAG模型客观呈现了码流相关性，但是没有考虑错误隐藏的影响，文献[10]对基本层错误隐藏的损失给出了评估，但是对增强层引起的损失没有考虑，文献[11]中介绍了一个简单、高效的性能指标模型，但是该算法过于复杂并且在求解过程中易于陷入局部最优解。传输中的另一个主要挑战是信道错误引起的误码，自动重发请求(ARQ)可以用来改善信道错误引起的误码，但是ARQ会带来系统的延迟，前向纠错技术(FEC)可以降低信道传输误码的影响[12-13]，在传输中被广泛的应用，本文中也采用了此项技术。

本文联合时域和质量两个维度的不均等差错保护方案，通过失真模型量化误差传播引起的失真，并在此基础上利用遗传算法求解整体失真的最小值，得到了各层数据的最优码率分配方案，有效提高了解码端的重建视频质量。

1 SVC框架结构及UEP分配方案

1.1 SVC标准框架

2004年4月MPEG组织征集SVC技术草案，同年10月JVT最终确定采用HHI研究所提出的基于H.264扩展的架构作为SVC标准的实现框架和研究起点，2005年1月开始了SVC项目的标准化工作，直到2007年6月确定了最终的SVC标准草案。SVC融合了时间、空间、质量三个维度的可分级特性，经过一次性压缩可生成满足不同帧率、分辨率、质量的伸缩码流。

图1 两个空域层的SVC编码器结构Fig.1 SVC encoder structure with two spatial layers

图2 时域和质量层的混合结构Fig.2 Partition structure for temporal and quality layers

可伸缩视频编码(SVC)实现了空域、时域和质量的可分级编码，如图1所示[2]，其典型结构包含了两个空域层，即空域基本层D0和空域增强层D1，其中空域基本层是由空域增强层下采样输入的视频序列得到的，在每个空域层中使用了运动补偿预测以及帧内预测技术。为了提高SVC的编码效率，空域层中采用层间预测机制，使用基本层中的运动信息以及残差信息来预测空域增强层中的数据，降低了层之间的相关性。在每个空域层中又进行了时域以及质量的可伸缩编码，时域和质量的混合编码结构如图2所示，使用了分级预测结构将一个具有8帧的图像组(GOP)分成了一个时域基本层即T0和三个时域增强层分别为T1、T2、T3[14]，在每个时域层中采用和H.264/AVC相似的变换编码[15]，将纹理和运动信息编码成质量基本层，其它的数据编码成质量增强层用来提高重建的视频质量。这里将时域层中的质量层定义为伸缩单元S.分级预测结构采用了多个参考帧的方式，一方面提高了编码效率，另一方面在编解码时还可以通过限制预测帧的数目来任意的调整结构延迟。

由于SVC采用分级预测结构，时域层级越高依赖的帧数也会越多，一旦较低的时域层发生错误将对更高层产生重大影响，甚至造成数据的不能恢复。因此，当压缩的数据流在有错误的信道环境下传输时会发生数据丢包的现象，对视频的恢复产生影响，因此需要人为增加保护措施。为了纠正视频数据在传输中产生的错误，前向纠错技术(FEC)通过加入一定量的冗余数据，在不稳定的信道环境下，如果解码端接收到的数据丢失数量少于FEC编码加入的冗余数据量，那么原始的数据可以完全得到恢复。FEC编码一般采用Reed-Solomon(RS)编码来实现。

1.2 UEP分配方案

当视频数据在丢包的信道环境下传输时，文献[16]对不均等错误保护编码和多描述编码进行了分析比较，指出在信道固定的条件下不均等错误保护编码方法具有更好的传输性能。时域和质量混合编码的UEP分配方案如图3所示，图中共有T个时域层，每个时域层中再编码成F个质量层，同时对每一层伸缩单元S进行FEC编码，对每层经过FEC编码后的数据进行竖向打包，每层经过FEC编码的保护数据打成包的个数和高度分别表示为k(i，j)、h(i，j)，其中i代表每个伸缩单元S对应的时域层，j代表对应的质量层，i和j的取值范围为i=0，1，…，T-1，j=0，1，…，F-1，每层的信源数据打成包的个数则为N-k(i，j)，N表示每层总的包个数，其中包的大小定义为M.

每一层的伸缩单元S经过FEC编码后的h(i，j)可采用式(1)计算:

(1)

图3 两个维度的可伸缩单元UEP分配方案Fig.3 UEP scheme for scalable units with two dimensions

其中Ri,j表示每层伸缩单元S的数据量即每层信源数据的字节数。为了解决如何合理分配各层的信道比特率，使解码出的视频质量整体失真最小，文献[5]中采用的是将PSNR作为衡量整体失真程度的指标，失真公式可表示为:

(2)

σi,j表示丢失S(i，j)层后的PSNR减小量，其中σi,j值可以由实验求得，首先计算没有丢包情况下的PSNR值，再计算丢弃S(i，j)层后的PSNR值，两个PSNR的差值即是要求的σi,j值，ρi,j表示S(i，j)层丢失的概率。为了求解ρi,j，文献[13]和文献[17]中采用二稳态的马尔科夫模型来近似模拟信道下的丢包，从而计算出从N个包中丢失m个包的概率p(m，N)[18].如果丢失的包个数大于保护包的个数，那么信源数据就不可恢复，所以S(i，j)层丢失概率ρi,j可以用式(3)计算:

(3)

为了使整体失真达到最小(见式(2))，需要合理分配各层的保护数据，得到一组最优的k(i，j)值，即最优矩阵K.

这个优化问题可以描述为：

minDoverall(K)

(4)

s.t.k(i，j)≥k(i+1，j)，i=0，1，2，…，T-2

(5)

k(i，j)≥k(i，j+1)，j=0，1，2，…，F-2

(6)

(7)

(8)

较低时域层和质量层对视频的恢复质量影响较大，因而应给予更多的数据保护，如式(5)、式(6)所示。竖向打包后包的字节数不能超过规定的包的大小，如式(7)所示。信源数据和增加的保护数据不能超过总的目标比特数，如式(8)所示，其中Wtot表示传输一组GOP所需要的目标比特数。

2 基于遗传算法的码率优化算法

为了合理分配UEP方案各层所需要的保护数据，文献[17]中采用了动态规划算法，首先把所求的问题规划分组，然后求出所有组的最大累加值，采用递推计算方式，在去除其中一组条件下，剩余组累加值达到最大时求得去掉那组最优值，依次递推直到求得最后一组的最优值为止，该算法虽然可以求得最优值但是求解过程过于繁琐，并且没有详细说明所有组及剩余组达到最大值时的明确条件。文献[11]中采用了和上坡法相似的搜索算法，该算法也是采用了迭代方式，将各层hi,j的累积和不超过包的最大值作为迭代终止条件，在迭代过程中引用了失真函数作为衡量各层失真是否达到最小，在此基础上求得各层的k(i，j)值，该算法虽然得到了各层k值，但是只是局限于在各层的条件下得到的，并非是在考虑整体失真的角度上得到的最优值。本文在寻求最优值的优化过程中，首先从整体角度考虑，在整体失真最小的情况下寻求简便、有效的优化算法，因此采用的是在整体失真最小条件下利用遗传算法求得的各层最优值，并且在遗传算法求解过程中，需要评价种群中每个个体的优异，这里是将整体失真函数作为了算法的评价标准，为了简化算法过程，在求整体失真函数中引用了失真指标模型，极大地简化了算法复杂度。根据本文中的具体问题，对遗传算法做了适应性的调整将罚函数思想引入到了遗传算法中[19]。

2.1 改进整体失真公式

2.1.1 失真指标模型

知道了式(2)中的σi,j就可以寻求最优值矩阵K，其中σi,j可通过实验得到，这种求得σi,j值的方法在寻优过程中太过于繁琐，本文通过建立失真的性能指标模型将该问题公式化，可以简单快速得到σi,j的值，从而大大减小了算法复杂度。

图4 期望的误差传播区(EZEP)Fig.4 Expected error propagation zone

传输中数据包的丢失会造成视频质量下降，进而会引起时间上的错误传播，量化这一影响造成的误差被称作预期的误差传播。由于分级预测结构，低时域层的数据包丢失会比高时域层的丢失引起更为严重的误差传播。如图4所示，在一个为8帧的图像组(GOP)中，如果在第9帧(即时域层为0)发生错误丢包将会影响到全部高层的帧，那么受到影响的帧数为(2(4-0)-1)，其中4表示GOP中全部的时域层数，0表示当前的时域层数。因此可将模型中时域上误差传播的影响归纳为2(T-igc1)-1，T表示全部的时域层数，i表示当前的时域层数。c1表示缩放因子，其取值与错误传播丢失的帧和受影响的帧相关。

由于SVC在质量维度上的依赖关系，高质量层数据的恢复要依赖于低质量层的数据，所以误差在低质量层上的传播要比在高质量层上的传播，对重建视频的影响更为严重。除了误差传播的影响也要考虑到误差传播的限制，如果在质量基本层发生丢包，为了限制误差进一步扩散，重建视频帧不会使用质量增强层的信息。注意到如果较低的质量层发生丢失，在解码端更高质量的层将不被用于解码，丢失的帧将会被最近位置已经解码的帧所代替，来最小化误差传播的影响。因此误差在质量层上传播的模型应与质量层成反比关系即误差发生的层级越低造成视频质量的降低就会越严重，用公式表示为(1+j)-c2，j表示当前质量层，c2表示缩放因子，如果c2大于1意味着质量基本层比增强层占据更多的权重。

根据以上分析，处于时域层i质量层j的数据发生错误造成的误差，可用如下失真性能指标模型表示:

(9)

本文中使用τi,j作为αi,j的估计值。

2.1.2 简化整体失真公式

根据上述的失真性能指标模型求得的τi,j作为αi,j的估计值，因此要优化的整体失真式(2)可表示为如式(10):

(10)

在求整体失真最小的优化过程中，式(10)仍要满足约束条件式(5)到式(8).

2.2 遗传算法求解最优值

在约束条件下寻求式(10)的全局最优值需要合理有效的优化算法，由于在码率分配中存在的特点即SVC固有特性，混合编码中的同一时域层的不同质量层之间的数据重要度是不同的，基本层数据重要性高于增强层数据的重要性，较低增强层数据重要性高于较高增强层数据的重要性，而在不同时域层的不同质量层重要度是不明确的如层k(1，1)和层k(3，2)，因此在给予各层保护程度上也是不等的。基于上述原因一些传统的优化算法难以到达分配的要求，比如传统优化算法中的上坡法和本地搜索算法，使用这些方法想有效的分配各层的信道比特，但是必须知道各层数据重要性的优先级别，针对本文中的具体问题，各层之间的重要性不是完全明确的，明确的层只有k(i，j)≥k(i+1，j)，i=0，1，…，T-2 和k(i，j)≥k(i，j+1)，j=0，1，…，F-2，对于其他情况，例如层k(1，1)和层k(3，2)的重要性是不确定的，不能明确指出哪一层应该给予更多的信道保护，因此上述算法不适应对本文问题的求解。

遗传算法(GA)通过模拟生物进化的过程，在有约束条件的求解中，可将约束条件进行转化，适应于解决不同的优化问题，并且克服了传统算法只在连续搜索空间求解最值的缺陷。在本文中GA可以将约束条件转化，将有约束的优化问题转化为没有约束的问题进行求解，因此不用在去考虑每层数据的重要性，根据文中的约束条件即可求解最优值，很好的解决传统算法在寻优过程中的不足，因此适用于对本文问题的求解。

2.2.1 改进的适应度函数

求解最优值的过程中，需要判断每代个体的优异，把优秀的个体更多的机会遗传到子代，评价个体优异的函数称作为适应度函数，本文中是将整体失真函数作为了遗传算法的适应度函数。在寻求整体失真最小时，由于存在着大量的约束条件式(5)到式(8)，会使得遗传算法在进化过程中产生大量的不可行解，那么就需要把适应度函数做恰当的调整，引入了惩罚函数将不可行解转换为可行解，把有约束的问题转换成没有约束的问题，引入的惩罚函数对违反约束条件的个体给予相应的惩罚。加入罚函数式(5)至式(8)中的约束条件可改为如下：

kt=k(i,j)-k(i+1,j)≥0，i=0,1,…,T-2

(11)

kn=k(i,j)-k(i,j+1)≥0，j=0,1,…F-2

(12)

(13)

(14)

因此罚函数可定义为:

Lpenalty(γ1,γ2,γ3,γ4)=γ1[min{0,kt}]2+
γ2[min{0,ktt}]2+γ3[min{0,gr}]2+
γ4[min{0,grr}]2

(15)

其中γ1，γ2，γ3，γ4为惩罚因子。

现在，遗传算法中的适应度函数公式表达如下:

Doverall(K)+Lpenalty(γ1,γ2,γ3,γ4)

(16)

2.2.2 遗传算法求解及整体流程图

遗传算法在求解最值的进化过程中，种群中的每一个个体都代表着一种解决方案，每个个体经过选择、交叉、变异等进化操作后，在计算个体的适应度值，得到问题的最优解。

在求解中，首先产生初始种群，种群的规模在进化过程中是保持不变的。第二步是评估种群中个体的优异，首先要检查种群中的个体是否满足约束条件，满足条件的个体直接计算适应度值，不满足约束条件的个体进行约束修正。第三步对种群中个体进行选择，选择目的将种群中的个体进行优胜略汰操作，本文中的选择算子采用的是最优保存策略。第四步是交叉操作，形成两个新的个体。第五步变异，变异操作是将个体二进制串的某些比特值由0变成1，或者由1变成0.种群中的个体经过选择、交叉、变异后，即完成了当前代的操作，按照预设的迭代次数进行下一代的运算，直到达到预设的迭代值，遗传算法结束并输出问题的最优解。

得到各层码率分配值便可实现SVC不均等差错保护编码方案，其整体系统结构如图5所示。

图5 系统结构图Fig.5 The diagram of system structure

3 结果仿真

本节中展示了遗传算法的迭代结果以及本文所提出方案的性能，实验中测试了两组yuv视频序列分别为Foreman(QCIF)和Football(QCIF)各编码成时域、质量两个维度的可伸缩码流，编码工具使用软件为JSVM9.18版本。不同的序列设定不同的参数，Football设定为N=200，M=170，Foreman设定为N=100，M=130.在用遗传算法求解最优值过程中两组序列使用相同的进化因子，交叉概率为0.65，变异概率为0.02，种群大小为规定为100，遗传代数为300，以及缩放因子c1=0.3、c2=3.0.其中GA的迭代结果如图6所示种群进化到100代左右基本处于平衡。

实验中按提出的方案将序列Football在丢包率为5%、10%、15%的网络环境下与均等保护和固定码率保护进行了PSNR的比较，同样序列Foreman在丢包率为5%、10%、15%、20%、25%的不同丢包网络环境下与均等保护和固定码率保护进行了PSNR的比较，比较的结果如图7、图8所示。

在图7中由于三种保护方案都给了不同程度的信道保护，在丢包率小于5%的情况下，均等保护和固定码率保护丢失包的个数，都没有超过每层允许的最大丢包值，所以每层的数据都可以完全恢复出来PSNR值没有降低，而UEP方案由于高层数据给予的保护没有低层数据给予的保护量多，层级别越高给予的保护也会越少，在低丢包情况下高层丢失的数据包超过了允许的最大丢包值，部分高层数据未能恢复整体的PSNR值有所降低，但是丢失的高层数据量对总的PSNR值贡献不大，所以总的来看三种保护方案的PSNR值大体相似，随着丢包率的增大到10%的过程中UEP方案效果开始显现出来，UEP方案的PSNR减小量很缓慢，其余两种方案的PSNR值下降的较快，直到丢包率达到15%时，均等保护和固定码率保护的丢包数，超过了基本层所允许的最大丢包值，关键帧的基本层数据不能恢复发生丢失，视频质量出现了急剧恶化PSNR显著降低，而UEP方案在同样情况下，基本层丢包的个数未能达到基本层允许的最大丢包数，所以视频数据可以恢复出来，视频质量平滑下降且PSNR的下降值很小。

图6 遗传算法迭代结果Fig.6 The iteration result of GA

图7 序列Football性能Fig.7 The performance of Football

图8 序列Foreman性能Fig.8 The performance of Foreman

图8中在丢包率小于5%时，三种方案都给了一定程度的保护，丢失包的个数没有达到每层允许的最大丢包值，都能将视频质量完全恢复PSNR值没有降低，当丢包率达到10%时，均等保护方案的丢包数超过了基本层所允许的最大丢包值，关键帧的基本层数据不能恢复，视频质量出了急剧下滑，UEP方案和固定码率保护方案的丢包数，没有达到基本层所允许的最大丢包数，视频数据能够恢复，其中固定码率保护的PSNR值略高于不均等保护的PSNR值，当丢包率达到15%，两种保护方案的PSNR值达到相同，并且不均等保护的PSNR值的下降量要小于固定码率保护的下降量，不均等保护的视频质量表现的较为平稳，当丢包率到达20%时，固定码率保护的丢包数超过了基本层允许的最大丢包，关键帧中的基本层数据不能恢复基本层丢失，视频质量出现了急剧的恶化，而提出的UEP方案，丢失的包没有达到基本层允许最大丢包数，视频数据可以恢复，表现出了很好的平稳趋势，直到丢包达到25%时，UEP方案的PSNR值下降量都较小，表现出很好的传输性能，提高了视频传输质量的鲁棒性。不均等差错保护在丢包较高的网络环境下对恢复视频质量有了很大的提高。

4 结论

对可伸缩视频编码的码流在不稳定信道环境下传输的问题上，本文中提出了不均等差错保护的一种新的码率优化方案。在对SVC各层数据给予不同信道保护时采用了整体失真模型的做法，并用遗传算法求解失真最小值得到各层的保护数据，极大的降低了算法的复杂度。实验结果表明本文提出的算法与传统保护算法相比，提高了解码端的视频质量，特别是在高丢包的网络环境下，效果更加显著，极大的提高了视频传输的鲁棒性。

[1] GUPTA R，PULIPAKA A，SEELING P，et al.H.264 coarse grain scalable and medium grain scalable encoded video：a trace based traffic and quality evaluation[J].IEEE Transactions on Broadcasting，2012，58(3)：428-435.

[2] SCHWARZ H，MARPE D，WIEGAND T.Overview of the scalable video coding extension of the h.263/avc standard[J].IEEE Transaction on of Information Theory，2007，19(9)：1103-1120.

[3] SEGALL C A，SULLIVAN G J.Spatial scalability within the H.264/AVC scalable video coding extension[J].IEEE Transactions on Circuits and Systems for Video Technology，2007，19(9)：1121-1135.

[4] JI W，LI Z，CHEN Y.Joint source channel coding and optimization for layered video broadcasting to heterogeneous devices[J].IEEE Transactions on Multimedia，2012，14(2)：443-451.

[5] STOUFS M，MUNTEANU A，CORNELS J，et al.Scalable joint source-channel coding for the scalable extension of H.264/AVC[J].IEEE Transactions on Circuits and Systems for Video Technology，2008，18(12)：1657-1670.

[6] 常静.H.264不等差错保护传输策略[J].科技创新报，2010(22)：88.

[7] 陈高华，卓东风，杨铁梅.基于数学形态学的遥感图像边缘检测方法研究[J].太原科技大学学报，2009，30(4)：280-282.

[8] 任通华，李晓峰，谢仕云，等.LDPC码的不等差错保护策略在SVC中的应用[J].计算机应用，2011，31(1)：270-276.6.

[9] CHOU P A，MIAO Z.Rate-distortion optimized streaming of packetized Media[J].IEEE Trans.Multimedia，2006，14(2)：390-404.

[10] MANSOUR H，NASIOPOULOS P,KRISHNAMURTHY V.Modeling of loss-distortion in hierarchical prediction codec[C]∥2006 IEEE International Symposium on signal processing and information Technology,Canada,Vancouver,2006.

[11] HA H，YIM C.Layer-weigted unequal error protection for scalable coding extension of H.264/AVC[J].IEEE Transactions on Consumer Electronics，2008，54(2)：736-744.

[12] LEE T W A，CHAN S H G，ZHANG Q，et al.Allocation of layer bandwidths and FEC for video multicast over wired and wireless networks[J].IEEE Transactions on Circuit Video Technology，2002，12(12)：309-544.

[13] SHI Y，WU C，dU J.A novel unequal loss protection approach for scalable video streaming over wireless networks[J].IEEE Trans.Consumer Electronics，2007，53(2)：363-368.

[14] SCHWARZ ，MARPE D，WIEGAND T.Analysis of hierarchical B pictures and MCTF[J].Proceedings of ICME′06，Toronto，Canada，2006，54(2)：208-471.

[15] AMONOU I，CAMMAS N，KERVADEC S，et al.Optimized rate distortion extraction with quality layers in the scalable extension of H.264/AVC[J].IEEE Transactions on Circuits Video Technology，2007，17(9)：1 186-1 193.

[16] BACCAGLINI E，TILLO T，OLMO G.A comparison between ULP and MDC with many descriptions for image transmission[J].IEEE Signal Processing Letters，2010，17(1)：75-78.

[17] YU WANG，LAP-PUI CHAU，SENIOR MEMBER，et al.Bit-Rate Allocation for Broadcasting of Scalable Video Over Wireless Network[J].IEEE Transactions on Broadcasting，2010，56(3)：175-398.

[18] ELLIOTT E O.A model of the switched telephone network for date communications[J].Bell Syst Tech，1965，56(12)：89-109.

[19] 周明，孙树栋.遗传算法原理及应用[M].北京：国防工业出版社，1999.

Unequal Error Protection with Genetic Algorithm for Scalable Video Coding

AN Hua，ZHANG Xiong

(School of Electronic Information Engineering，Taiyuan University of Science and Technology，Taiyuan 030024，China)

Due to the instability of network transmission environment，in order to transmit the bit stream of SVC in heterogeneous network and realize the transmission quality，the scalable video coding combining unequal error protection scheme with forward error correction technology was adopted.The unequal error protection scheme gives each layer the protection of different intensity according to the importance degree of data.However，it is difficult to allocate protection date that is needed for each layer to restore the most optimal video quality.Through the establishment of distortion model and genetic algorithms， a new rate allocation scheme was proposed.Comparing with traditional approach in the unstable network environment，the results show that the proposed scheme effectively improves the reconstructed video quality of scalable video coding at the decoder，especially in high packet loss environment.

scalable video coding (SVC)，unequal Error Protection (UEP)，the distortion model，genetic algorithms(GA)，optimization

2014-12-29

太原科技大学研究生科技创新项目(20134011)；太原科技大学同州电子科技创新基金项目(TZ201307)

安华(1987-)，男，硕士研究生，主要研究方向为数字媒体与网络传输。

1673-2057(2015)06-0416-08

TN919.72

A

10.3969/j.issn.1673-2057.2015.06.002