时间维受限的三维虚拟SPIHT树组织方法

摘要

本发明为一种时间维受限的三维SPIHT虚拟树组织方法，是对视频图像三维小波变换结果进行三维SPIHT压缩的重要改进。本发明提出了对于不能再作真实分解的三维小波系数进行二维与三维相结合的虚拟分解，从而形成了根结点父子关系、二维父子关系及三维父子关系相结合的子女寻找方法，并以此方法重新定义三维SPIHT树。本发明显著提高了的三维SPIHT的编码效率。

说明书

技术领域

本发明属视频压缩技术领域，具体涉及一种时间维受限的三维虚拟SPIHT树的组织方法。

技术背景

小波变换能随频率的变化自动调整分析窗大小，自八十年代中期以来得到了迅猛的发展，并在众多的图像和视频编码领域得到应用。图1(a)是二维的一级小波分解示意图(共4个子带：LL1、LH1、HL1和HH1)，LH1、HL1与HH1是第一级变换的高频部分，LL1是一级分解的低频部分。图1(b)是二维的三级小波分解示意图(共10个子带)，它是对LL1进行小波分解产生LL2、LH2、HL2和HH2，再对LL2进行小波分解产生LL3、LH3、HL3与HH3。三维小波分解是在二维的基础上扩展的。

如何有效地对小波变换系数进行量化和后编码是图像及视频压缩的关键。在嵌入式零树编码算法EZW(Embedded Zerotree Wavelet)[1]出现前，图像压缩，特别是有失真压缩，它的计算复杂性与编码效率是同步增长的。在1993年，J.M.Shapiro所提出的EZW算法突破了该限制，它在低复杂性的同时保持了较高的编码效率。1996年，Amir Said和William A.Pearlman提出的等级树集合分割算法SPIHT(Set Partitioning in HierarchicalTrees)[2]在EZW基础上性能又有所提高，而且即使不加算术编码，SPIHT算法仍可与许多复杂算法的性能相当。2001年杨春玲和余英林将SPIHT推广到三维SPIHT，它对于简单背景且运动较为缓慢的视频流有十分良好的压缩性能。1997年，Q.Wang与M.Ghanbari提出了虚拟零树[4]，在分解级数一定的情况下，它更加合理地利用了树间的相关性。2001年，EI Khan和M.Ghanbari提出了虚拟SPIHT树[5]，实验表明虚拟树的引入使得小波系数的组织更加合理，所以编码效率在分解级数一定的情况下有显著的改善。2002年，H.Danyali和A.Mertins提出三维虚拟SPIHT树[6]，它扩展了二维虚拟SPIHT树，使得可以直接对三维小波变换的结果进行编码，在分解级数一定的情况下编码效率也有显著改善。

下面介绍与本发明相关的一些概念：

1、SPIHT算法

1)父子关系及树的构成：父子关系定义为图2中箭头所指方向(箭头由父亲指向子女)，以图中任意一点(i，j)为根，(i，j)及其所有子孙便构成一棵树。(i，j)的子女的寻找方法分为两种情况：

a、若(i，j)在LLn(n指最高分解级，如图2中的LL3)，SPIHT算法将LLn分为2×2大小的块，块中左上角的点没有子女(如图2中的LL3中被黑点标记的点)，其它点的子女为当前分解级中相应位置的2×2的点(如图2中LL3中一个2×2的块的右上角对应LH3、左下角对应HL3、右下角对应HH3)。

b、若(i，j)在LLn以外的子带中，则其子女为以下四个点：

{(2i，2j)，(2i+1，2j)，(2i，2j+1)，(2i+1，2j+1)，}

2)集合及其分裂

图3是SPIHT算法中集合的示意图，其中每一个圆圈代表一个点，实心表示点存在，空心代表点不存在，线条上面是父亲，下指子女。

T(i，j)是一根完整的树，C(i，j)是根结点，O(i，j)是根结点的子女，D(i，j)为所有子孙，L(i，j)为除子女以外的所有子孙。从图中可以看出

T(i，j)＝C(i，j)+D(i，j)    (1)

D(i，j)＝O(i，j)+L(i，j)    (2)

集合分裂就是将D(i，j)分裂为O(i，j)及L(i，j)，或是将L(i，j)分裂为四个D(k，l)(其中C(k，l)属于O(i，j))。在SPIHT算法中，D(i，j)被标识为A类集合，L(i，j)被标识为B类集合。

3)阈值与重要性判断

SPIHT算法的初始阈值由式(3)算出，式中c_i，j表示点(i，j)的小波系数，符号表示对数α取整，例如阈值Threshold是动态改变的。

对于某一点是否重要由式(4)算出，若当前点的系数大于当前阈值，则认为是重要的，否则认为不重要。

对于一个集合是否重要由式(5)算出，意即集合中有任意一点大于当有阈值，则该集合是重要的，否则不重要。

4)LSP、LIP和LIS

这三个链表是SPIHT编解码过程中用到的工作链表。重要系数链表LSP(List ofsignificant pixels)存放重要的系数；不重要系数链表LIP(List of insignificant pixels)存放不重要的系数；不重要集合链表LIS(List of insignificant sets)存放不重要的集合。

5)SPIHT编码

SPIHT编码由三部分组成：初始化，排序过程和细化过程。它以三个链表实现对小波系数信息的排序。

初始化：计算初始阈值；置LSP为空；将LIP初始化为小波分解最高一级的低频部分(如在图2中的三级小波分解的LL3)；将LIS初始化为LIP中有子女的点(如将图3中最低频子带分成2×2的像素单元，除打星号的点外，其余3个点有子女)，并将其设为A类集合。

排序：算法首先对LIP进行扫描。然后对LIS进行扫描。排序过程见图4，图4中深浅两条线分别代表点(或集合)重要与不重要，线上的比特(0、1及S)表示要输出的比特。①对于LIP中的每一点，若不重要输出0，否则输出1及S(符号)，然后移至LSP表尾。②对于LIS中的每一集合，若重要输出1否则输出0。若重要且为A类集合则按式(2)分裂成为子女(若重要则输出1及S并添加到LSP末尾，否则输出0并添加到LIP末尾)与一个B类集合(移至LIS末尾)；若重要且为B类集合，则将其分裂为四个子集合(A类集合)并添加到LIS表尾，然后删除当前集合。

细化：当排序完成后，需要进行细化过程，即对除当前阈值被排序添加到LSP外的所有点，作重要性测试并输出测试结果。然后将阈值减半，重复排序和细化过程，直到输出达到所需要的输出比特数为止。

2、虚拟树

图5是二维虚拟树的示意图，图中LL5、LH5、HL5及HH5是小波分解的最高级的子带，也是真实分解部分，而LLB、HLB、LHB、HHB、HLA、LHA和HHA是LL5的虚拟分解部分。虚拟分解是指事实上没对LL5进行小波分解，但在构造SPIHT树时，假定在LL5上又作了二次小波分解，从而使一棵虚拟的树可以组合更多的小波系数而提高编码效率。

实验表明，n级真实分解再加上m级虚拟分解共(n+m)级分解比n级真实分解的编码效率高，但是较(n+m)级真实分解的编码效率低。文献[5]与文献[6]均是对可以继续作真实分解的小波系数进行虚拟分解。

参考文献

[1]J.M.Shapiro，“Embedded image coding using zerotrees of waveletscoefficients，”IEEE Trans.Signal Processing，Vol.41，pp.3445-3462，Dec.1993.

[2]A.Said and W.A.Pearlman，“A New Fast and Efficient Image Codec Basedon Set Partitioning in Hierarchical Trees，”IEEE Trans.Circ.and Syst.forVideo Technology，Vol.6，pp.243-250，June 1996

[3]杨春玲，余英林，基于三维小波变换嵌入式视频压缩算法的研究，电子学报，Vol.29，No.10，pp.1381-1383，Oct.2001

[4]Q.Wang and M.Ghanbari，“Scalable coding of very high resolution video usingvirtual zero tree，”IEEE Trans.Circuits Syst.Video Technol.，pp.719-727，June 1997

[5]E.Khan and M.Ghanbari，“Very low bit rate video coding using virtualSPIHT，”IEEE Electronics Letters，Vol.37，no.1，pp.40-42，Jan.2001

[6]H.Danyali and A.Mertins，″A 3-D virtual SPIHT for scalable very low bit-rateembedded video compression，″in Proc.6th Iht.Symposium on Digital SignalProcessing for Communication Systems，Sydney，NSW，Australia，Jan.2002，pp.123-127.

发明内容

本发明的目的在于提出一种时间维受限的三维SPIHT虚拟树组织方法，以便对视频图像三维小波变换结果进行三维SPIHT压缩方法加以改进。

本发明提出时间维受限的SPIHT虚拟树组织方法，是一种采用二维虚拟分解与三维虚拟分解相结合的方法来对时间维受到限制的三维小波系数进行虚拟分解。

在应用三维小波进行视频压缩时，考虑到编解码的实时性及存贮要求，一般以8帧图像为一个图像帧组GOF(Group of Frame)，所以由于帧数较少限制了进一步进行小波分解(最多作三级分解)，若采用[6]中的三维虚拟分解方法在时间维上不能进行虚拟分解。

本发明提出二维与三维相结合的虚拟分解的思路。具体来说，对于8帧图像的GOF，每帧为352×288的图像，作3级小波分解后，LLL3的大小为44×36×1，所以不能在时间维上进行虚拟分解，但是在另外两维上还可进行二级虚拟分解得到11×9的虚拟树根。其方法是把时间方向的两帧(LLL3和HLL3)在空间上分别进行二级虚拟分解，如图6所示。详细作法如下：将LLL3在当前帧向上虚拟分解一级得到LLLA、LLHA、LHLA和LHHA，再将LLLA向上虚拟分解一级得到ROOT、LLHB、LHLB和LHHB；将HLL3在当前帧向上虚拟分解一级得到HLLA、HLHA、HHLA和HHHA，再将HLLA向上虚拟分解一级得到HLLB、HLHB、HHLB和HHHB；ROOT与LLHB、LHLB、LHHB、HLLB、HLHB、HHLB和HHHB在相应位置上有相似性，将ROOT作为上述7个子带的根，便得到有三级虚拟分解的虚拟SPIHT树。

树的构成以及父母与子女关系。

图6中箭头指向关系定义为父母指向子女。在SPIHT算法中，树的构成是关键，而树的构成在于父母与子女的关系定义，本发明中有三种类型的子女，定义ROOT的大小为W_min×H_min，当前节点坐标为(i，j，k)时，这三种子女的定义如下：

(1)根节点子女：这种父母子女关系是对最低频子带与同级子带的虚拟分解。如果节点(i，j，k)在ROOT中，其子女为：

ROOT为三级虚拟根，记为C类型(其子女为B类型)，其中的每一个节点有7个子女，分别是同级子带LLHB、LHLB、LHHB、HLLB、HLHB、HHLB和HHHB中的相应点。

(2)二维子女：这种父母子女关系是在时间维受限的情况下，按二维的方式进行虚拟分解，即对于LLLn和HLLn，分别在LLLn和HLLn内作二维虚拟分解，直到不能再分解为止(不能再分解是指虚拟的低频部分大小至少有一维不能被2整除)。如果节点(i，j，k)在ROOT的同级子带上(而不在ROOT中)，它有4个子女，称为二维子女，其子女为：

{(2i，2j，k)，(2i+1，2j，k)，(2i，2j+1，k)，(2i+1，2j+1，k)}    (2)

如图6中LLHB、LHLB、LHHB、HLLB、HLHB、HHLB和HHHB，它们为二级虚拟根，其中每一点有4个子女，分别在LLHA、LHLA、LHHA、HLLA、HLHA、HHLA和HHHA中对应节点；LLHA、LHLA、LHHA、HLLA、HLHA、HHLA和HHHA为一级虚拟根，其中的每个节点也有4个子女，分别为LLH3、LHL3、LHH3、HLL3、HLH3、HHL3和HHH3中的对应节点。

(3)三维子女：如果节点(i，j，k)在真实小波分解的子带上，它有8个子女，其子女为：

对图6中，LLH3、LHL3、LHH3、HLL3、HLH3、HHL3和HHH3中节各点均有8个子女，其子女也有8个子女(孙子辈)。

改进后的编码方法

A：小波变换：

对图像帧组作三维小波变换，在空间域上用Daubechies9/7小波基分解，在时间域上用Haar小波基分解。

B：SPIHT编码：

步骤1.初始化

对所有的小波系数c_i，j，k，求并以2″为当前阈值，输出n；LSP初始化为空；LIP初始化为LLL3；LIS初始化为ROOT(见图6)，并记为C类型(如果虚拟分解级数增加，则类型将会是D、E、F…以此类推)。

步骤2.排序及细化

步骤2.1对于LIP中的每一点，判断并输出其重要性：

如果重要，输出其符号，并将当前点的系数的绝对值减去当前阈值，然后移至LSP；

步骤2.2对于LIS中的每一个集合，判断并输出其重要性：

1)如果集合重要且为A类集合，判断树根的各子女是否重要并输出重要性，如果不重要则移至LIP，否则输出当前点的系数的符号，并将其绝对值减去当前阈值，然后移至LSP，被移去根结点子女的集合如果为空，则将其从LIS中删除，否则改集合类型为B类型，并移到LIS末尾；

2)如果集合重要且为B(或C、D、E…以此类推)，将其分裂为以根结点子女为根的子集合，设定其集合类型为A(或B、C、D…以此类推)，然后将这些子集合添加了LIS末尾，并删除当前集合。

步骤3.量化

对于LSP中的点，除当前次排序中加入的点，判断并输出其重要性，如果重要则将其绝对值减去当前阈值。

步骤4.更新

将阈值减半，并转向步骤2，直到达到要求的压缩比。

本发明的优点：

二维与三维相结合的虚拟树方法改变了用传统虚拟树组织方法对不能继续作真实分解的小波系数不能作虚拟分解的限制；一棵虚拟树中组合了更多的小波系数，更加合理地利用了SPIHT树间的相关性，从而提高了编码效率。在码率一定的情况下，通过采用本发明的技术，可以减小进行3D-DWT-SPIHT编码的帧数，从而节约内存并利于实时性的实现。

实验证明，采用本发明的技术比不采用该发明技术在相同条件下视频的峰值信噪比提高约0.5～4dB。

附图说明

图1为二维小波分解示意图。

图2为SPIHT算法父子关系。

图3为集合示意图。

图4为排序示意图(图中S表示符号，0与1表示重要性)。

图5为5级小波分解最高分解级及2级虚拟分解示意图。

图6为时间维受限的三维SPIHT虚拟树示意图。

图7为文献[4]与本发明的压缩结果比较。

具体实施方式

下面以公共中间格式CIF(Common Intermediate Format)的MissA(352×288，30帧每秒)视频流为例说明具体的实施方式。编解码以8帧为一个GOF。

A：小波变换

步骤1.空间域变换

对于每一帧图像，用Daubechies9/7小波基对其作二维小波变换。共作3级分解。

步骤2.时间域变换

对每一帧作过二维小波变换的小波系数，取每一帧相应位置的系数(共8个系数)，用Haar小波基对其作一维小波变换，共作3级分解。

B：SPIHT编码

步骤1.初始化

对所有的小波系数c_i，j，k，求并以2ⁿ为当前阈值Threshold，输出n的低5比特；LSP初始化为空；将ROOT中的所有点添加到LIP中；将以ROOT中的点为树根的树添加到LIS中，并记其为C类型集合(如果虚拟分解级数增加，则类型将会是D、E、F…以此类推)。

步骤2.排序及细化

步骤2.1对于LIP中的每一点(i，j，k)：

判断|c_i，j，k|是否大于Threshold，如果大于则输出“1”(重要像素)，否则输出“0”(不重要像素)。如果重要，判断c_i，j，k是否大于0，如果c_i，j，k大于0则输出“1”(正号)并将c_i，j，k减去Threshold，否则输出“0”(负号)并加上Threshold，然后将点(i，j，k)移到LSP末尾。

步骤2.2对于LIS中的每一个集合(i，j，k)(以树根表示)：

判断集合(i，j，k)中是否有一个系数大于Threshold，如果有系数大于Threshold则输出“1”(重要集合)，否则输出“0”(不重要集合)。

1)如果集合重要且为A类集合，判断树根的各子女是否重要(见步骤2.1)，如果重要则输出“1”，否则输出“0”。对于不重要的子女，将其移至LIP末尾。对于重要的子女，判断其系数符号，如果为正号则输出“1”，并将系数减去Threshold；否则输出“0”，并将系数加上Threshold。然后将重要子女移至LSP末尾。被移去根结点的子女的集合如果为空，则将其从LIS中删除，否则集合类型改为B类型，然后移至LIS末尾。

2)如果集合重要且为B(或C、D、E…以此类推)类集合，将其分裂为以根结点子女为根的子集合，设定其集合类型为A(或B、C、D…以此类推)类型，然后将这些子集合添加到LIS末尾，并删除当前集合。

步骤3.量化。对于LSP中的点(i，j，k)(除当前次排序中加入LSP的点外)：

判断|c_i，j，k|是否大于Threshold，如果大于则输出“1”(重要像素)并将其绝对值减去Threshold，否则输出“0”(不重要像素)。

步骤4.更新

Threshold＝Threshold/2。并转向步骤2。

C：压缩比控制

在编码中，每输出一比特，均可进行一次压缩比判断，如果达到所需的压缩比，即可马上停止编码。下面以CIF格式的MissA和Claire序列的0-47帧进行仿真实验。表1第一行摘自文献[3]，GOF为8帧。从表1中可以看出，在压缩比一定时本发明方法较文献[3]在图像质量上有显著改进，而且随着压缩比的增大，其效率提高更加明显。本发明方法的PSNR(峰值信噪比)高出文献[3]0.5-3dB。

表1本发明方法与文献[3]比较(MissA，GOF＝8)

压缩倍数                     100      200      400

峰值信噪比    文献[3]        39.19    36.22    31.57

(dB)

              本文方法       39.72    37.61    34.47

PSNR

图7(a)摘自文献[4]，是对CIF格式的Claire进行视频图像压缩的结果，它的I帧采用1bit/pixel编码，其余帧的速率为600kbit/s或300kbit/s。假设文献[4]的一个GOF大小是16帧，那么它的上述平均信息速率为752.58kbit/s或471.33kbit/s(如果帧数较小，则其平均速率将更大，例如GOF为8帧，则其平均速率分别为905.16kbit/s或642.66kbit/s)。图7(b)是以本发明的方法，按照文献[4]的四种速率进行编解码的结果。从图中可以看出，本发明方法的PSNR值高出文献[4]3-4dB。