一种基于树状结构的视频图像压缩改进方法

摘要

本发明为一种运用“自适应码流分配”的基于树状结构的视频图像压缩改进方法。该算法能有效地提高基于树状结构的SPIHT算法的编码效率。SPIHT是一种简单、高效的压缩编码算法，但是该算法存储空间需求大，不利于硬件实现，一直阻碍着它进一步的发展和应用。文献[2]提出了一种基于树状结构的SPIHT编码算法，大大节省了计算过程中的内存使用，实现了SPIHT算法的硬件移植，本发明在文献[2]的基础上提出了“自适应码流分配”优化方法，大大提高了重建图像的峰值信噪比(PSNR)指标，克服了基于树状结构的SPIHT算法图像质量明显下降的缺点。试验结果表明，改进后的基于树状结构的SPIHT视频图像压缩算法能用较少的存储空间，达到与标准算法基本相当(甚至在某些情况下更好)的视频图像压缩效果。

说明书

技术领域

本发明属于视频图像压缩技术领域，具体涉及一种运用“自适应码流分配”的基于树状结构的视频图像压缩改进方法。

背景技术

SPIHT(set partitioning in hierarchical tree)^[1]是一种简单、高效的小波零树图像压缩编码算法，它通过中间链表保存像素点坐标来简化对小波系数的扫描过程，从而大大提高了压缩效率和实现简便性。但是，SPIHT算法的中间链表占用了大量的存储空间，不利于在硬件上实现，阻碍着SPIHT算法进一步的发展应用。因此，如何在不影响图像压缩效果的前提下，缩短链表长度，减少内存的存储量已经成为近来研究的热点。

文献[3]提出了“STTP-SPIHT(Spatio-Temporal Tree Preserving 3-D SPIHT)算法”，首先提到了将三维SPIHT按照空间及时间域进行划分的概念。文献[2]考虑到了SPIHT的硬件移植问题，提出了“基于树状结构的等级树集合划分(SPIHT)视频图像压缩方法”，它根据小波系数之间的相关性，将各级的小波系数按照树状结构进行划分处理，该算法可以大大地节省计算过程中的内存使用量，实现了SPIHT算法的硬件移植。但是，该算法重建图像的峰值信噪比(PSNR)指标对比划分前的SPIHT算法降低了0.1～1db，图像质量受到了一定的影响。

参考文献(References)

[1]A.Said and W.A.Pearlman，“A New Fast and Efficient Image Codec Based on SetPartitioning in Hierarchical Trees，”IEEE Trans.Circ.and Syst.for Video Technology，Vol.6，pp.243-250，June 1996

[2]专利：基于树状结构的等级树集合划分视频图像压缩方法  申请号：200410017558.7发明人：华赟，胡波，徐晟，高佳

[3]S.Cho and W.A.Pearlman.Error resilient compression andtransmission of scalable video.Applications of Digital ImageProcessing XXIII，Proceedings SPIE，4115，2000.

[4]丁文奇，胡佳，张立明，充分减小树间冗余的优化三维VSPIHT视频编码方法，计算机辅助设计与图形学学报

[5]王向阳，杨红颖，基于改进逐次逼近量化与复杂关联模型的零树图像编码算法，计算机辅助设计与图形学学报，Vol.14，No.6，pp.586-589，June 2002

[6]林刚，刘泽民，三维小波多分等级树视频压缩编码，电路与系统学报，Vol.4，No.1，pp.31-35，March 1999

发明内容

本发明的目的是提出一种基于树状结构的视频图像压缩改进方法，以便有效地提高SPIHT算法的编码效率。

基于小波变换的图像编码中小波系数的后编码是十分重要的，现公认的后编码方法是嵌入式的SPIHT算法^[1]。嵌入式编码中首先传输的是最重要的信息，也就是幅值最大的变换系数的位信息。同时这种嵌入式编码可根据目标码流率的要求，在任何时候结束编译码，精确地控制比特率。基于树状结构的SPIHT算法^[2]是在所有的树状结构的小波系数编码结束后，根据符合压缩比要求的目标码流，将每棵树的编码结果合成为目标码流。由于这种算法不能实时控制比特率，因此会给编码效果带来一定影响。

改进前基于树状结构的SPIHT算法的缺陷分析

[文献1]中合成码流的方法是将每棵树编码结果中阈值大于截断阈值(2^P)的码流直接作为目标码流，目标码流不足的部分由每棵树编码结果中阈值小于等于截断阈值的码流平均分配。其中，“码流不足部分的平均分配”便是造成PSNR降低的主要原因之一。图1是各树在截断阈值2^P时的码流长度示意图，显然，码流大于平分长度的一些树(如T2等)并不能完全输出它在2^P时部分码流，而码流小于平分长度的一些树(如T1等)却输出了阈值小于2^P的部分码流。这明显违背了重要信息优先输出的原理，从而造成了相应的误差。

本发明提出的基于树状结构的视频图像压缩改进方法，是一种自适应的码流分配算法，它能根据每棵树在2^P时的实际码流长度，遵循“高阈值(即高重要性)的码流优先输出”的原则，自适应地分配码流，从而避免了由于码流平分所带来的编码误差。具体步骤如下：先求出所有树大于2^P时的总码流长度N_p，求出平分给每棵树等于2^P时的平均码流长度L，依次扫描每棵树在阈值为2^P时的码流长度，确定小于L的码流进入目标码流；所有树扫描完毕后，对还未确定码流的树重新统计平均码流长度L′，按照上述方法再次扫描，循环操作直到目标码流全部分配完毕为止。

本发明所提出的一种运用“自适应码流分配”的基于树状结构的视频图像压缩编码改进算法，能有效地提高重建图像的PSNR指标，确保在大量减少内存使用量的同时，依然能达到与标准算法基本相当(甚至在某些情况下更好)的图像压缩效果。

附图说明

图1为各树在2^P时的码流长度示意图。

具体实施方式

(一)自适应码流分配算法的具体实现

假设有M棵树，要求的目标码流长度为Q，按照文献[1]中所述的SPIHT方法得到所有树在阈值降到2^P+1时的总码流长度N_p+1根据 $>ver>>L>‾>>=>>>Q>->>N>>p>+>1>>>>M>>>s>求出平分给每棵树在2P时的平均码流长度L；$

假设第j棵树在阈值为2ⁿ时的码流长度为L_j，n，依次扫描M棵树，如果L_j，p≤L，则可以立即确定第j棵树进入目标码流的码流长度为 $>>>N>j>>=>>\Sigma >>m>=>P>>N>>>L>>j>,>m>>>>s>(N为最大阈值)；$

重新统计 $>ver>>>L>\prime >>‾>>=>>>Q>-sup>>N>p>\prime sup>>>>M>\prime >>>,>>s>其中N\prime$_p为当前已经确定的总码流长度，M′为不满足L_j，p≤L的树的数量，依次扫描M′棵树，对于满足L_i，p≤L′条件的树，确定它们进入目标码流的码流长度；

再重新统计L″……直到目标码流全部分配完毕为止。

采用自适应码流分配算法可以保证目标码流中传送的系数重要性始终大于等于2^p，避免了在平均分配中出现传送重要性小于2^p的部分码流而带来的性能误差。

二、仿真的结果

具体的仿真条件如下：

Miss American、Salesman、Claire以及children2_foreground四类视频图像组1～48帧图像的Y值数据，每帧图像大小为352×288。进行三级三维离散小波变换，再对低频区域进行两级二维离散小波变换，小波基选用Daubechies 9/7双正交小波(行方向和列方向)和Haar小波(时间方向)。共有99棵树。

试验结果如下：

视频序列  压缩比文献[4]文献[2]  改进后MissA  100 40.2897 40.0059  40.1700  200 38.8853 38.6159  38.7334  400 36.6659 36.2236  36.5605Salesman  100 31.2074 31.0684  31.1732  200 29.1255 28.8977  29.0406  400 27.3353 27.1932  27.2444Claire  100 40.0866 39.3839  39.9613  200 36.4408 35.7811  36.2372  400 31.8750 31.3502  31.9923 Children  100 30.4015 29.3993  30.3135  200 28.0576 27.6246  27.9077  400 26.4079 25.7313  26.2300

通过上面的实验结果我们可以发现，“自适应码流分配”优化算法都有效地提高图像压缩效果，改进后的基于树状结构的SPIHT算法与改进前相比，重建图像的PSNR指标提高了0.164～0.914db，在高压缩比下的某些图像质量甚至比标准的SPIHT算法还有好。