罗 骁,李卫忠
(空军工程大学 防空反导学院,陕西 西安710051)
多描述编码 (multiple description coding,MDC)是一种能够在兼顾数据实时性的同时解决数据失真问题的联合信源信道编码[1]。近年来不断有新的MDC算法被提出,但其中很多研究主要考虑的是两信道的情况[2-5],Huihui Bai等[6]提出针对小波变换后的图像不同子带,按不同的扫描方向生成多个描述,再采取格型矢量量化的方式对各个描述中的系数进行量化,由于矢量量化过程中计算复杂度高,使其应用空间受到限制。Khelil等[9]提出了另一种基于小波的 多 描 述 变 换 编 码 (multiple description transform coding,MDTC)方法,首先把源图像分为4个描述 (一级小波变换后4个子带系数组成的矢量),这4个描述使用相同的步长进行均匀量化,然后使用相关变换的方法形成多个描述,该方法能够在不占用过多计算资源的条件下得到较好的重构图像,是当前较为简单实用的MDTC 方法之一。但是,在系数量化时,由于每个子带的能量和重要程度不一样,使用同样的步长进行均匀量化是不合适的。为此,本文在文献 [9]的基础上提出对子带量化的改进技术,该方法根据子带各自的能量进行量化,步长优化方法采取遗传算法。实验结果表明,改进后的方法在重构图像的客观PSNR 表现和主观视觉感受上均有改善。
传统的单描述编码 (如DCT)方案引入变换往往是为了去除信源的相关性来提高编码效率,而多描述变换编码(MDTC)系统则是通过变换在描述中引入可控的冗余信息,使在丢包情况下,可以利用描述间的相关性从接收到的描述中把丢失的描述估计出来。图1是两个描述情形下的编码过程,信源数据经编码后形成描述1和描述2,通过不同的信道传输到解码端,当解码端只接收到描述1或描述2时,通过重建可以恢复出质量较低但可以接受的x∧1或x∧2,当两个描述都能正常接收时,可以得到高质量的重构x∧0。
图1 两个描述的变换编码框架
通常,一个信源矢量x 的多描述变换编码包括以下步骤:
(1)使用变换 (如DCT、DWT……)去除信源相关性。
(2)将信源矢量x 标量量化为xq:xq=[x]Q。其中,[.]Q表示量化取整。
(3)再对xq进行离散变换引入冗余得到矢量y:y =T∧(xq)=[T1[T2…[Tkxq]Q]Q]Q。其中,T∧是连续变换T 的离散变换,T 为k 个主对角线为1的上三角或下三角矩阵的乘积。
(4)将矢量y 的系数划分为M 个集合 (描述),最后进行熵编码。
当接收到所有内容后,重构过程是编码的逆过程。假如部分系数丢失,这部分系数可以通过相关变换引入的统计相关从已接受到的系数中估计出来,估计值通过相关变换和量化的逆过程生成,参考文献 [9]给出了详细的编码和重构过程。
离散小波变换 (DWT)是最好的图像编码技术之一。本文采用在图像压缩领域广泛使用的Daubechies 双正交小波。一级小波分解将图像分为4个子带 (一个光滑的LL子带和3个细节子带:垂直HL 子带,水平LH 子带,对角HH 子带)。其中,LL 子带集中了大部分能量,其余3 个细节子带只得到少量的能量 (其中HH 子带最少)。因此,这就启发我们在均匀量化方案中根据子带能量大小来设计量化步长,让最重要的信息 (LL子带)可以进行高质量的量化,而对代表高频部分的系数 (HL、LH、HH)进行粗糙的量化。
文献 [9]提出MDTC.DWT/UQ 编码过程如下:
(1)对源图像使用1级正交B9/7小波变换生成4个子带:LL1,HL1,LH1,HH1。
(2)形成4个矢量 (描述)。
(3)DWT 系 数 (4 个 矢 量)通 过 一 量 化 步 长Δ 均 匀量化。
(4)相关变换应用于4个矢量。
(5)与JPEG 类似的熵编码应用于4个矢量[9]。
在第 (2)步,本文提出不同子带的系数用不同尺寸步长的均匀量化器进行子带均匀量化,而不是用一种不变的量化步长进行均匀量化。图2描述了这种基于DWT 的图像编码过程。每个子带或每个描述desi归属于一个量化步长Δi。对一给定比特率,量化步长 {Δ1,Δ2,Δ3,Δ4}的设置与各自的描述{des1,des2,des3,des4}相对应,使在丢包情况下图像的重构失真最小化。为了达到根据各子带所包含的能量进行均匀量化的目的。4 个量化步长的尺寸需要满足关系Δ1<Δ2≤Δ3<Δ4或者Δ1<Δ3≤Δ2<Δ4。我们通过遗传算法来解决这个最优化问题。
图2 基于小波变换的多描述编码
遗传算法 (GA)是一种通过效仿生物进化过程来搜索最优解的随机化搜索方法,具有鲁棒性强、随机搜索、控制简单等特点,适合于解决复杂和非线性系统优化的问题,目前已经在生产调度、人工生命、图像处理等领域获得了广泛的运用。图像子带量化步长的优化为一个非线性过程,因此这里采用遗传算法对量化步长进行优化。当给定目标比特率Rt时,使用遗传算法优化4个量化步长过程如下:
遗传算法首先要通过编码将问题的状态空间转换为算法的码空间,然后才能随机产生一定数量染色体 (问题的解)组成的初始种群。针对步长优化问题,最初随机产生一个由20条染色体 (问题的解)组成的种群,染色体是与4个量化步长所构成矢量Δ={Δi,i=1,2,3,4}相对应的编码串。编码方式采用能够协调搜索和效率之间关系的二进制编码方法。在本文中,步长范围设定为5≤Δi≤35,每个量化步长Δi由5位二进制进行编码,编码串的长度为20位,如图3所示。
图3 量化步长Δi 的编码方式
因为5位二进制可产生32种不同的编码,步长的编码区间是 [5,35],所以各步长编码对应的解码公式为
种群中个体 (染色体)的生存能力取决于其适应度。适应度函数f(Δ)分配给种群中每个个体Δ 一个数值,用于衡量解决方案的质量优劣。适应度高的个体即认为其质量高,遗传到下一代的机会就大,在本文中,使用实际码率与码率误差平方的比值作为适应度函数
约束条件
其中Ra(Δ)是实际码率,Rt是目标码率。
遗传算法通过选择、交叉、变异3 种方式控制种群的进化过程。首先用某种方法选择出当前种群中一些适应度值高的个体,然后以一定的概率对这些个体以进行交叉,变异操作。最后在保持种群个体数目不变的情况下,用它们替代原种群中适应度值最差的个体形成新种群。
(1)选择。即按照适应度选择当前种群中生命力强的个体,经常使用的选择策略包括比例选择、保存最优个体选择、期望值选择、排序选择、确定式采样选择等。在本文中我们采用比例选择策略,根据个体适应度与总适应度的比值进行选择,比值大的个体拥有更大的概率被选择。
(2)交叉。即将种群中的个体进行随机配对,然后以一交叉概率交换它们中的部分基因。
交叉体现了信息交换的思想,控制着遗传算法的全局搜索能力。通常交叉概率的取值范围为0.40~0.99,本文中设定初始交叉概率Pc(1)为0.8,从第二代种群开始采用自适应的交叉概率
式中:N——遗传代数,Pc(N)——第N 代的交叉概率,Nmax——最大遗传代数,本文中Nmax=500。代入式(4)可得
(3)变异。即为了提高种群的多样性,以一定的概率对种群中个体串的某些基因座上的基因值作改变。通常变异概率的范围为0.001~0.100,本文中设定初始变异概率Pm(1)为0.05,从第二代种群开始采用自适应的交叉概率
式中:Pm(N)——第N 代的变异概率。将数据代入式(6)得
不断重复上述步骤直到满足终止条件。生存下来的染色体具有良好的适应度,作为优化问题的最优解输出,图4是GA 优化过程的流程。
图4 遗传算法流程
为了验证所提出量化方法的效果,将本文方法和文献[9]中的方法MDTC.DWT/UQ 应用在真实图像上,测试图像使用512×512 ‘bridge’,512×512 ‘lena’,512×512‘barbara’,用0.1bit/sample的 冗 余[9]分 配 给4 个 描 述。两种方法的比较如图5、图6和表1所示。
图5是两种技术在不同丢包情况下 (丢失一数据包、丢失二数据包、丢失三数据包)的PSNR 值和码率的关系曲线。从这些曲线中不难发现,在一个数据包丢失情况下,两种方法的结果相差不多。然而,当2或3个数据包丢失时,随比特率增加本文方法比MDTC.DWT/UQ 在PSNR 上的表现更好。表1是目标码率为2.0bits/sample时,各测试图像在不同丢包情况下重构后的PSNR 值,从中可以看出,在2或3 包丢失情况下,利用本文方法比MDTC.DWT/UQ 在PSNR 值 上 提 升2-4dB。图6 比 较 了 目 标 码 率 为2.0bits/sample, ‘bridge’图像在0,1,2,3包丢失情况下两种方法的重构。其中a、b、c、d使用MDTC.DWT/UQ方法,e、f、g、h使用本文方法,重构后的PSNR 值分别为(a)39.67dB、(b)39.52dB、(c)32.40dB、(d)27.91dB、(e)39.35dB、(f)39.14dB、(g)34.62dB、(h)29.95dB。容易注意到,使用新方法重建后的图像视觉效果明显改善。
图5 bridge的峰值信噪比和码率的关系曲线
图6 bridge在0,1,2,3包丢失情况下两种方法的重构
表1 不同丢包数量下两种方法的对比
(1)假设检验:考虑到本文使用的遗传算法具有一定的随机性,而且图像重建质量往往与具体的丢失信息相关,需要更具统计意义的数据证明本文方法的有效性。因此,本文对‘bridge’图像进行了更多的测试,然后利用测试结果和参数假设检验的方法 (U 检验)对网络环境较差情况下 (2包丢失或3包丢失)两种方法的优劣做出进一步分析。
将本文方法和文献 [9]中的方法MDTC.DWT/UQ 在网络环境较差情况下的PSNR 值分别看作母体X1和X2,给定目标码率为2.0bits/sample,用两种方法对 ‘bridge’图像进行50次测试,得到两组容量为100的子样PSNR 数据,经计算:n1=n2=100,珡X1=30.12,S1=2.6,珡X2=32.51,S2=5.2。其中n1,珡X1,S1和n2,珡X2,S2分别为两组数据的子样容量、平均数、标准差。给定小概率a =5% ,查表得=1.96,使
括号内的事件为小概率事件,平均进行20次抽样只发生一次。假设H0:μ1 ≥μ2,H1:μ1 <μ2 ,拒绝区域为
计算得
易见珡X1-珡X2≤-1.14,故拒绝H0,即认为在网络环境较差情况下使用本文方法后图像的PSNR 值有显著提高。
(2)复杂性分析:在运行速度上,本文方法比文献[9]提出的MDTC.DWT/UQ 方法慢,原因在于子带量化过程中使用遗传算法,计算适应度值时需要大量时间,我们评估候选方案时使用的适应度函数f(Δ)对于L×L 图像至多需要L2+2L 次乘法和2L 次加法。实验结果表明GA找到最优解需要大概400 次估值。因此,至少需要400×(L2+2L)次乘法和400×(2L)加法,对于512×512图像,优化量化步长需要总计约1.1亿次计算,这样的计算量对于专用的数字信号处理器 (DSP)是完全可以接受的。
本文提出一种集成遗传算法和小波变换的多描述编码方法,该方法考虑到应用小波变换后图像低频信息 (第一个描述)的重要性,使用遗传算法优化的量化步长对4个子带进行不同程度的量化,很好地保护了在引入相关后各个描述中的低频系数。与文献 [9]相比本文方法既保证了多个描述同时到达时的编码性能,又提高了任意描述到达时图像的主客观重建质量,更适于在误码多发网络环境下的图像传输。不足之处在于本文提出的量化策略没有对感兴趣区中复杂的纹理特征 (高频系数)进行保护,下一步研究工作将围绕感兴趣区编码ROI和本文方法的结合,进一步提高图像的视觉质量。
[1]ZHANG Yang,ZHANG Nan,YIN Baocai.Overview of researches on multiple description coding [J].Chinese Journal of Computers,2007,30 (9):1613-1624 (in Chinese). [张洋,张楠,尹宝才.多描述编码研究现状 [J].计算机学报,2007,30 (9):1613-1624.]
[2]Nan Z,Yan L,Feng W,et al.Efficient multiple description image coding using directional lifting-based transform [J].IEEE Transactions on Circuits and Systems for Video Technology,2008,18 (5):646-656.
[3]ZHENG Yi,SHI Ping.Wavelet-based multiple description video coding [J].Video Engineering,2012,36 (23):43-46(in Chinese).[郑义,史萍.一种基于小波变换的多描述视频编码方法 [J].电视技术,2012,36 (23):43-46.]
[4]LI Yan,WANG Shengqian,DENG Chengzhi,et al.Multiple description coding scheme based on redundant Ridgelet transform [J].Computer Engineering and Applications,2011,47(24):146-149 (in Chinese). [李彦,汪胜前,邓承志,等.一种基于冗余Ridgelet变换的图像多描述编码方法 [J].计算机工程与应用,2011,47 (24):146-149.]
[5]JIANG Yuzhen,ZHU Yinghui,OUYANG Chunjuan.Multiple description video coding research based on complementary segmentation in compressed domain [J].Computer Engineering and Design,2009,30 (14):3362-3364 (in Chinese).[江玉珍,朱映辉,欧阳春娟.基于压缩域互补分割的视频多描述编码研究 [J].计算机工程与设计,2009,30 (14):3362-3364.]
[6]Huihui B,Ce Z,Yao Z.Optimized multiple description lattice vector quantization for wavelet image coding [J].IEEE Transactions on Circuits and Systems for Video Technology,2007,17 (7):912-917.
[7]Zhang G.Efficient error recovery for multiple description video coding [C]//International Conference on Image Processing.Singapore:IEEE,2012:829-832.
[8]Choupany R,Wong S,Tolun M.Scalable video transmission over unreliable networks using multiple description wavelet coding [C]//Proceedings of IDCTA,2011.
[9]Khelil K,Bekka RE,Djebari A,et al.Multiple description wavelet-based image coding using correlating transforms [J].AEU-International Journal of Electronics and Communications,2007,61 (6):411-417.
[10]Lin Chunyu,Zhao Yao,Zhu Ce.Two-stage multiple description image coding using TCQ [J].International Journal of Wavelets,Multiresolution and Information Processing,2009,7 (5):665-673.
[11]LI Yun,LIU Gang,LAO Songyang.A genetic algorithm for community detection in complex networks [J].Journal of Central South University,2013,20 (5):1269-1276.
[12]LI Cuiping,ZHENG Yaoxia,ZHANG Jia,et al.Ore grade interpolation model based on support vector machines optimized by genetic algorithms[J].Journal of University of Science and Technology Beijing,2013 (7):838-843(in Chinese).[李翠平,郑瑶瑕,张佳,等.基于遗传算法优化的支持向量机品位插值模型[J].北京科技大学学报,2013 (7):838-843.]
[13]Zhang Wen,Ghogho M.Hypothesis testing analysis and unknown parameter estimation of GPS signal detection [J].Journal of Central South University,2012,19 (5):1290-1301.