CN1281065C - 基于树状结构的等级树集合划分视频图像压缩方法 - Google Patents

Abstract

本发明为一种基于树状结构的等级树集合划分(SPIHT)视频图像压缩方法。编码端首先通过离散小波变换得到图像能量在时频率域上的分布；根据小波系数之间的相关性，将各级的小波系数按照树状结构进行划分；然后对每棵树的小波系数分别进行SPIHT编码，编码结果分别暂时存放在编码端；最后将每棵树的编码结果合成为一个码流用于存储或者传输。解码过程为编码过程的逆过程。本发明在不消耗多余计算量的前提下，大大节省计算过程中的内存使用，从而适应视频流实时高效的压缩，特别适用于硬件实现的专用系统，是用较少的存储空间，就能实现高压缩比和低失真度的视频压缩。

Description

基于树状结构的等级树集合划分视频图像压缩方法

技术领域

本发明属于视频图像压缩技术领域，具体涉及一种基于树状结构的等级树集合划分视频图像压缩方法。

背景技术

等级树集合划分(SPIHT)算法充分考虑了数据之间的相关性，并且在编码时还考虑了同一数据中高比特数据重要性高于低比特数据的特性。所以使用SPIHT方法来压缩、解压缩视频图像可以得到比较高的压缩比而不增加解压缩结果的失真度，所以该方法受到了日益广泛的关注。在具体实现的过程中，编码系统需要建立三个链表，即重要像素链表(LSP)、不重要像素链表(LIP)和不重要像素集合链表(LIS)，这三个链表用来记录树状结构分裂的中间数据。通过链表的使用，编码码流可以按照阈值(重要性)下降的顺序排列，从而保证重要信息的传输而可以截断非重要信息，得到任意截断码流的高压缩比的压缩效果。为了提高压缩效果，要求树状结构包括更多的数据。但是随着树状结构中数据量的增加，三个链表的长度就越来越长，在实际应用中就要求有巨大的内存空间，这就增加了系统的成本和复杂度。所以在不降低压缩效果的前提下，缩短链表长度的方法正成为研究的热点。

发明内容

本发明的目的是提出一种基于树状结构的等级树集合划分(SPIHT)视频图像压缩方法，以保证压缩效果不下降的前提下，大大缩短链表的长度，节省系统的内存空间开销。

本发明提出的基于树状结构的等级树集合划分(SPIHT)视频图像压缩方法，编码的具体步骤如下：首先通过离散小波变换得到图像能量在时频率域上的分布，由于图像的平滑性，图像能量集中在低频部分；根据小波系数之间的相关性，将各级的小波系数按照树状结构进行划分；然后对每棵树的小波系数分别进行SPIHT编码，编码结果分别暂时存放在编码端；最后将每棵树的编码结果合成为一个码流用于存储或者传输。

根据小波系数之间的数据相关性，将各级的小波系数按照树状结构进行划分是指以最低频子带的每个系数为树根，按照不同级别之间小波系数位置的数据相关性得到树状结构中每个点的数据。树状结构中，上一级小波系数和下一级小波系数之间的关系称为父母和子女或后代的关系。在小波系数中，不同子带相同位置的系数，往往在数值上有相似性，根据这样的关系，将最低频子带的每个系数作为树的根节点，高一级的子代中相同位置的系数作为树状结构的第一级子女，更高一级的子代中与每个第一级的子女相同位置的系数作为第一级子女的子女，也是树状结构的第二级子女……直到最高频子带的系数作为最后一级的子女。

对每棵树的小波系数分别进行SPIHT编码，可以减少同时处理的小波系数，产生的中间结果较少，缩短了重要像素链表(LSP)、不重要像素链表(LIP)和不重要像素集合链表(LIS)的长度。其方法就是将每棵树的编码结果都按照阈值下降的顺序依次得到，直到阈值下降到可以满足压缩要求为止。阈值下降极限可以由前一帧组的最小阈值或者经验阈值得到的预测阈值决定。每棵树的小波系数进行SPIHT编码的结果不予直接传输，而是暂存在编码端，存放时将各阈值情况下的编码码流依次存放，并且记录各阈值情况下的编码码流长度。

在所有的树状结构的小波系数编码结束后，为了得到符合压缩比要求的目标码流，需要将每棵树的编码结果合成为目标码流。合成码流的方法是确定最小的阈值，称为截断阈值，使得每棵树编码码流中不小于该阈值的码流之和不大于目标码流长度，将这些编码码流和码流长度合成为目标码流，剩余的目标码流再由每棵树的其余编码码流平均分配。就是将每棵树编码结果中阈值不小于截断阈值的码流和这些码流的长度直接作为目标码流，目标码流不足的部分由每棵树编码结果中阈值小于截断阈值的码流平均分配。

编码过程的重点在于树状结构的划分、树状结构小波系数编码结果的存放和目标码流的合成。

在解码端，解码过程是编码过程的逆过程：首先将待解码的码流分配给每棵树的缓存，再对每棵树分配到的码流依次进行SPIHT解码，得到树状结构的小波系数，再将树状结构的小波系数还原为按子带排布的小波系数，通过小波逆变换得到解码图像。

本发明所提出的基于树状结构的等级树集合划分(SPIHT)视频图像压缩方法，有效的解决了图像数据量和链表长度之间的矛盾。为了提高压缩效果，可以将多帧的图像(帧组)一起进行离散小波变换，使得每棵树可以包括足够多的小波系数；由于每棵树分别编码，并不会导致重要像素链表(LSP)、不重要像素链表(LIP)和不重要像素集合链表(LIS)长度的过度加长。

附图说明

图1为根节点和前三代子女的寻找关系。

图2为后两代子女寻找的关系。

具体实施方式

以下对发明中的各个组成分别加以论述。

1.离散小波变换结果的树状结构划分

离散小波变换可以使用三维的离散小波变换，即在行方向、列方向和时间方向分别进行离散小波变换。变换结果的最低频每个系数作为一棵树的根节点，并且按照下面的关系，构成树状结构。假设最低频系数的大小为W_min×H_min，其中W_min和H_min分别是最低频帧的最低频子带的宽度和高度。

1)根节点子女寻找方法     其子女为；

$\left\{\begin{array}{c}(x,y,z)\left|\begin{array}{c}(x+W_{\min },y,z),(x,y+H_{\min },z),\\ (x+W_{\min },y+H_{\min },z),(x,y,z+1),\\ (x+W_{\min },y,z+1),(x,y+H_{\min },z+1),\\ (x+W_{\min },y+H_{\min },z+1)\end{array}\right.\end{array}\right\}---\left(1\right)$

2)二维子女寻找方法       其子女为：

$\left\{\begin{array}{c}(x,y,z)\left|\begin{array}{c}(2x,2y,z),(2x+\mathrm{1,2}y,z),\\ (2x,2y+1,z),(2x+\mathrm{1,2}y+1,z)\end{array}\right.\end{array}\right\}---\left(2\right)$

3)三维子女寻找方法       其子女为：

$\left\{\begin{array}{c}(x,y,z)\left|\begin{array}{c}(2x,2y,2z),(2x+\mathrm{1,2}y,2z),\\ (2x,2y+\mathrm{1,2}z),(2x+\mathrm{1,2}y+\mathrm{1,2}z),\\ (2x,2y,2z+1),(2x+\mathrm{1,2}y,2z+1),\\ (2x,2y+1,2z+1),\\ (2x+\mathrm{1,2}y+\mathrm{1,2}z+1)\end{array}\right.\end{array}\right\}---\left(3\right)$

图1和图2所示，图1表示的是根节点和前三代子女的寻找关系，图2表示的是后两代子女寻找的关系，图中只画出了七个分支中的一支。

2.每棵树状结构小波系数SPIHT编码结果的存放

D_M，N表示阈值从2^N+1下降到2^N时第M棵树阈值为N的编码数据。L_M，N表示阈值从2^N+1下降到2^N时第M棵树阈值为N的编码数据长度。所有树的编码结果存放的格式如下：

阈值	2N	2N-1	……	2-1
					第1棵树	D1，N	D1，N-1	……	D1，-1
第2棵树	D2，N	D2，N-1	……	D2，-1
					第3棵树	D3，N	D3，N-1	……	D3，-1
					第M棵树	DM，N	DM，N-1	……	DM，-1

3.目标码流的合成

如果有M棵树，要求的目标码流长度为Q。在阈值降到2^P时，所有树的总码流长度为

$N_1=\underset{n=1}{\overset{M}{\mathrm{\Σ}}}\underset{m=P}{\overset{N}{\mathrm{\Σ}}}{L}_{n,m},$ 在阈值降到2^P-1时，所有树的总码流长度为 $N_2=\underset{n=1}{\overset{M}{\mathrm{\Σ}}}\underset{m=P-1}{\overset{N}{\mathrm{\Σ}}}{L}_{n,m},$ 并且满足N₁＜Q≤N₂，那么2^P即为截断阈值。先将M棵树阈值降到2^P时的所有码流和码流长度作为目标码流，如果每棵树进入目标码流的码流长度要用X比特表示，此时目标码流约为N₁+X，再将剩余的Q-N₁-X的目标码流平均分配到M棵树中其余的编码码流中，也就是将每棵树阈值为2^P-1的前(Q-N₁-X)/M码流作为目标码流。具体在目标码流中，各棵树的编码码流是这样安排的：

第1棵树 $\underset{m=P}{\overset{N}{\mathrm{\Σ}}}{L}_{1,m},D_{1,N}-D_{1,P};$

第2棵树 $\underset{m=P}{\overset{N}{\mathrm{\Σ}}}{L}_{2,m},D_{2,N}-D_{2,P};$

……

第M棵树 $\underset{m=P}{\overset{N}{\mathrm{\Σ}}}{L}_{M,m},D_{M,N}-D_{M,P;}$

D_1，P-1中的第1个比特；D_2，P-1中的第1个比特；……D_M，P-1中的第1个比特；

D_1，P-1中的第2个比特；D_2，P-1中的第2个比特；……D_M，P-1中的第2个比特；

……

直到目标码流长度达到要求。

解码的过程完全为编码的逆过程。首先将待解码的码流分配给每棵树的缓存，再对每棵树分配到的码流依次进行SPIHT解码，得到树状结构的小波系数，再将树状结构的小波系数还原为按子带排布的小波系数，通过小波逆变换得到解码图像。

仿真的结果

具体的仿真条件如下：

Miss American视频图像组1-8帧图像的Y值数据，每帧图像大小为352×288。进行三级三维离散小波变换，再对低频帧进行两级二维离散小波变换，小波基选用Daubechies9/7双正交小波(行方向和列方向)和Haar小波(时间方向)。共有99棵树。

实验结果如下：

原始图像	8帧352×288Y值			共811008字节
						小波变换结果	每个小波系数用16bits表示			共1622016字节
每棵树	一个帧组分为99棵树			共16384字节
						压缩倍数/目标码流长度		指标	优化前		优化后*
200/4055字节		LIP链表长度	6642		4433
						LSP链表长度	6084		6459
		LIS链表长度	3521		536
						PSNR效果	39.3690		39.0733
		150/5406字节		LIP链表长度	10752					4429
LSP链表长度	7851						6419
				LIS链表长度	4651			536
PSNR效果	39.9526						39.5110
				100/8110字节		LIP链表长度		14384		4443
LSP链表长度	12134		6448
						LIS链表长度	5216		536
PSNR效果	40.7056		40.4405
						50/16220字节		LIP链表长度	44952		4390
LSP链表长度	22792		6462
				LIS链表长度	13988			536
PSNR效果	41.4691		41.3303

^*优化后的LIP、LIP、LIS是99棵树中最大的长度，并且每棵树编码都进行到阈值降为8为止，试验证明阈值降到8，一般就能满足压缩比的要求。

通过上面的实验结果我们发现，本SPIHT编码方法的结果虽然降低了PSNR(降低得非常小)，但是用于存储链表的空间可以大大的减小。

Claims (3)

1一种基于树状结构的等级树集合划分视频图像压缩方法，其特征在于通过离散小波变换得到图像能量在时频率域上的分布，再将各级的小波系数按照树状结构进行划分：以最低频子带的每个系数为树根，按照不同级别之间小波系数位置的数据相关性得到树状结构中每个点的数据；然后对每棵树的小波系数分别进行等级树集合划分编码，编码结果分别暂时存放，最后将每棵树的编码结果合成为一个码流用于存储或者传输，其中，合成码流的方法是确定最小的阈值，使得每棵树编码码流中不小于该阈值的码流之和不大于目标码流长度，将这些编码码流和码流长度合成作为目标码流，剩余的目标码流再由每棵树的其余编码码流平均分配。

2根据权利要求1所述的基于树状结构的等级树集合划分视频图像压缩方法，其特征在于每棵树都分别进行等级树集合划分编码，每棵树的编码结果都按照阈值下降的顺序得到，直到阈值下降到可以满足压缩要求为止。

3根据权利要求1或2所述的基于树状结构的等级树集合划分视频图像压缩方法，其特征在于每棵树的编码结果先暂存在编码端，存放时将各阈值情况下的编码码流依次存放，并且记录各阈值情况下的编码码流长度。

Images