基于终止扫描阈值的遥感图像压缩算法

徐小乐　刘昌华　张倩妮

(武汉轻工大学数学与计算机学院　武汉　430023)



基于终止扫描阈值的遥感图像压缩算法

徐小乐刘昌华张倩妮

(武汉轻工大学数学与计算机学院武汉430023)

摘要针对遥感图像的压缩,对SPIHT压缩算法中的扫描阈值进行了研究,引入终止扫描阈值,提出了基于终止扫描阈值的改进算法。实验表明,在同一压缩比情况下,不同遥感图像的终止扫描阈值相同,同时在设定了终止扫描阈值之后,大大地减少扫描编码过程中的数据码流存储空间和算法的编解码时间,而算法重建图像的质量与原算法相当,适合遥感图像的实时压缩。

关键词遥感图像压缩; 多级树集合分裂算法; 终止扫描阈值; 终止扫描输出位

Remote Sensing Image Compression Algorithm Based on End Scan Threshold

XU XiaoleLIU ChanghuaZHANG Qianli

(Mathematics and Computer Institution, Wuhan Polytechnic University, Wuhan430023)

AbstractAiming at the compression of remote sensing image, a fast set partitioning in hierarchical tree(SPIHT) algorithm based on the end scan threshold is proposed in this paper. The end scan threshold is used in the encoding process to terminate the scan process when the compression is enough. Experimental results show that the end scan threshold for the different images is the same in the case of the same compression ratio, at the same time it reduces both both the memory reguirement and the time consumption and the quality of reconstructed image are close to SPIHT algorithm.

Key Wordsremote sensing image compression, SPIHT, end scan threshold, end scan output bit

Class NumberTP391.41

1引言

随着卫星遥感成像技术的发展,海量的遥感图像信息的产生使得对遥感图像压缩技术的研究成为一个重要课题。由于小波变换的特性,使其可以很好地运用于图像压缩领域[1~3]。在Shapiro将小波变换引入到图像压缩领域中来,并提出了嵌入式零树小波编码方法,取得了良好的压缩效果[4]。随着研究的深入,Said A和Pearlman W A在EZW算法的基础上,提出SPIHT算法[5],压缩效果有一定的提升。然而,SPIHT算法存在循环重复扫描,需占用大量的数据存储空间,而且编解码时间长,不利于纹理复杂的遥感图像的实时压缩[5]。

本文针对SPIHT算法,研究遥感图像的实时压缩,提出了终止扫描阈值与终止扫描输出位的概念,扫描过程中引入终止扫描阈值与终止扫描输出位可以很好地解决SPIHT算法中的多次重复扫描与存储量大的问题,节省编码时间与存储空间,可以很好地运用于遥感图像的实时压缩。

2基于终止扫描阈值的遥感图像压缩算法

2.1终止扫描阈值概念的提出

SPIHT算法在编码的过程中,初始扫描阈值是根据图像小波系数计算出来的确定值,然后在进行依次扫描时,每次的扫描阈值会在前一次的基础上减半。由于小波变换的特性,图像的能量信息大部分都存在于小波分解的低频部分。

随着循环扫描的进行,扫描阈值越来越小,以前不要的系数会随着扫描阈值的减小变为重要系数,每次扫描就会输出一个重要系数的二进制有效位。当在压缩比一定的情况下,扫描阈值减小到一定值,就终止扫描并停止编码。

表1是当我们选取一定阈值时,对应的重要系数的统计数据。表中图像是512×512大小的pentagon、houseof、cone以及1024×1024大小的b1和三级小波分解结果。

表1　SPIHT算法图像重要系数统计

表1数据表明,随着阈值的减小,表中所用图像重要系数的数量是不断增多的。在实际扫描中,并不需要循环扫描直至阈值减小为1才停止扫描。这样将会带来大量的扫描数据,而这些数据对图像压缩没有太多的实际意义,相反重复的扫描会带来扫描时间延长和数据存储量大的问题。

为了解决这个问题,本文提出了终止扫描阈值的概念。这就是在设定压缩比的情况下,为扫描设定一个终止阈值,当扫描阈值减小到终止扫描阈值后,就不需要再进行循环扫描。

2.2终止扫描阈值设定

引入终止扫描阈值,对解决数据存储量大的问题很有帮助。同时,在设定终止扫描阈值以后,我们根据终止扫描阈值定义了终止扫描输出位bite,如式(1)所示。

(1)

式(1)中Te为终止扫描阈值。

经过大量的实验,表2给出了在不同压缩比情况下图像的终止扫描阈值的统计情况。

分析表2可知,终止扫描阈值有以下特点:

1) 在压缩比相同的条件下,不同图像的终止扫描阈值相同;

2) 设置的压缩比越大,图像的终止扫描阈值越大;

表2　不同压缩比下的图像终止扫描阈值

3) 在不同压缩比条件下,同一图像的终止扫描阈值不同。

在SPIHT编码过程中,通过给定不同的扫描阈值,确定小波分解系数中哪些系数为重要系数,在压缩比一定的条件下终止扫描阈值确定,进而可以确定终止扫描输出位bite,由bite可以确定在精细扫描过程中最高权位与最小输出位的距离Np,进而将bite之前的所有位一次性输出不必再将得到的扫描数据码流存入LSP链表中。这样由于终止扫描阈值的存在,就可以不再需要设置LSP链表,经过这一步处理,使原来的三个数据链表减少为两个,这样不仅可以大大减少扫描次数,节省数据存储空间,同时编码时间也可以大大减少。

2.3基于终止扫描阈值算法编码

2.3.1树结构与分集规则

SPIHT算法中图像经过一级小波变换得到四个子带,以此类推,将得到的所有子带按照频率从低到高的顺序排成一个“空间方向树”结构[6~9],最低频子带在空间方向树最下面,树的每个子带节点对应一个系数,用A(r,c)来标识节点,如式(2)所示。

(2)

式(2)中Z(r,c)为空间方向树;(r,c)为节点;D(r,c)是A(r,c)所有子孙的坐标集;O(r,c)是节点A(r,c)直接后代的子坐标集;L(r,c)是除了直接后代子坐标集以外剩下的所有后代的集[10~12]。设X是一个小波系数集:X={|A(r,c)|},对于正整数n,判断节点和集合重要性的函数Gn(r,c)为:(1表示重要)

(3)

2.3.2基于终止扫描阈值算法流程

在图1中,我们给出了改进SPIHT算法的流程图。

图1　改进SPIHT算法流程图

2.3.3基于终止扫描阈值算法

根据上一节的算法流程图,我们将在这一节详细地介绍基于终止扫描阈值的压缩算法步骤,它主要分为三个步骤:初始化,扫描编码,下一级阈值设定。

step2:扫描编码

1) LIP链表编码,对LIP中的所有A(r,c)做如下处理:

(1)输出Gn(r,c)(函数Gn(r,c)判断A(r,c)的重要性);

(2)若Gn(r,c)=1,就向排序位流输出‘1’和符号位,以及系数二进制表示的bite之前的有效位,并将其移出LIP;

(3)若Gn(r,c)=0,则向排序位流输出‘0’。

2) LIS链表编码:

(1)若A(r,c)是‘D’型

①输出Gn(D(r,c));

②若Gn(D(r,c))=1,对每个(k,l)∈O(r,c)进行下面的操作;

(a)输出Gn(k,l);

(b)若Gn(k,l)=1,则向排序位流输出‘1’和符号位,同时输出对应系数二进制表示的bite之前的有效位;

(c)若Gn(k,l)=0,则向输出‘0’,将(k,l)添加到LIP尾部;

③若Gn(D(r,c))=0,则向排序位流输出‘0’;

④判断L(r,c)是否为空集,如果L(r,c)不是空集,则将A(r,c)作为‘L’类型的系数坐标添加到LIS的尾部,否则就从LIS中删除。

(2)如果A(r,c)是‘L’型表项

①输出Gn(L(r,c));

②若Gn(L(r,c))=1,则A(r,c)的四个子集(k,l)就被标成‘D’类型系数依次添加到LIS的尾部,将‘L’型系数A(r,c)从LIS中删除;

③若Gn(L(r,c))=0,则向排序位流输出‘0’。

step3:下一级扫描阈值指数设置

将本级的扫描阈值指数减1,然后重复step2,进行下一级扫描编码,每级扫描排序位流与精细扫描位流均为空,直到阈值变为Te终止扫描,编码结束。

3实验结果与分析

实验选择“pentagon”、“b1”、“houseof”、“cone”为测试图。从http://vasc.ri.cmu.edu/idb/html/stereo/index.html获得测试图,我们选择测试图对的左图来进行压缩测试,压缩倍率设置为2、4和8。计算和统计本文算法的解压缩时间和峰值信噪比,作为改进算法的压缩性能测试指标,与SPIHT和JPEG2000算法的压缩结果比较。最后给出几种方案的重构图视觉质量比较。其中图像峰值信噪比用式(4)计算[14~16]。

(4)

上式中MSE为重构图的均方误差,其计算公式如式(5)所示。

(5)

在图2中首先给出本文所选取的两幅实验测试图Pentagon、houseof,图3~图4则给出了这两幅测试图在压缩比为2和8时重构图像的人眼视觉质量表现。

图2　压缩算法实验测试图

　　

从图2~图4可以看出,在图像视觉质量的评价方面,本文的算法与SPIHT和JPEG2000重构图像差异不大,不存在明显的人眼可见失真存在。

接下来将讨论本文算法与其它两种算法在压缩质量和编解码时间上的表现,并用表3与表4分别记录四幅遥感测试图在三种算法下的重构图峰值信噪比和算法的编解码时间。

表3　有损压缩值信噪比

表4　不同算法编解码时间统计(单位:ms)

据表3峰值信噪比的计算数据可知,SPIHT算法的PSNR值与JPEG2000的大体相同,而本文算法与前两种方法相比,PSNR值有1dB~2dB的提高。根据表4的编解码时间统计分析,在编解码时间上本文算法与有较明显的节省。

4结语

在压缩比相同的条件下,不同图像的终止扫描阈值是大致相同的。引入终止扫描阈值后,可以大大的减少存储空间的使用量,减少扫描次数,在压缩性能相同的情况下,编解码时间得到了很大的节省,有利于进行遥感图像的实时压缩。改进算法未来可以运用在遥感立体像对的压缩中去,这在后续研究中会重点考虑。

参 考 文 献

[1] Rafael C Gonzalez, Richard E Woods. Digital image processing[M]. 2nd ed. Beijing: Publishing House of Electronics Industry,2002.

[2] Eom, I. K., Kim, Y. S. Robust EZW coding with shared threshold[J]. Electronics Letters,2003,39(21):1514-1515.

[3] Shapiro. Embedded image coding using zerotree of wavelets coefficients[J]. IEEE Trans Signal Processing,1993,41:3445-3462.

[4] Liu, Belyaev, Guo, VLSI Architecture of Arithmetic Coder Used in SPIHT[J]. IEEE Transactions on Very Large Scale integration(VLSI) Systems,2012,20(4):697-710.

[5] Mohammed Gulam Ahamad, Abdullah Al Jumah, Faisal Ahamad, et al. Multiwavelet Transform based Image Compression using Modified SPIHT Compression Scheme[J]. International Journal of Computational Intelligence Research,2012,8(1):35-45.

[6] M. Santhi, R. S. D. Wahida Banu, M. Santhi. Enhancing the Color Set Partitioning in Hierarchical Tree(SPIHT) Algorithm Using Correlation Theory[J]. Journal of Computer Science,2013,7(7):1245-1250.

[7] Brahimi, Melit. An improved SPIHT algorithm for lossless image coding[J]. Digital Signal Processing,2009,19(2):220-228.

[8] Pan, H, Siu, WC, Law, NF. A fast and low memory image coding algorithm based on lifting wavelet transform and modified SPIHT[J]. Signal Processing. Image Communication,2008,23(3):146-161.

[9] Brahimi, T, Meli, A, Khelifi, F. An improved SPIHT algorithm for lossless image coding[J]. Digital Signal Processing,2009,19(2):220-228.

[10] Jin, Y. A Block-Based Pass-Parallel SPIHT Algorithm[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(7):1064-1075.

[11] 王丽,张培珍.基于一种可变分类阈值的SPIHT算法[J].信息与电子工程,2007,5(4):280-283.

WANG Li, ZHANG Peizhen. A New SPIHT Algorithm Based on Variable Sorting Thresholds[J]. Information and Electronic Engineering,2007,5(4):280-283.

[12] Mohammed Gulam Ahamad, Abdullah Al Jumah, Faisal Ahamad. Multiwavelet Transform based Image Compression using Modified SPIHT Compression Scheme[J]. International Journal of Computational Intelligence Research,2012,8(1):35-45.

[13] 秦襄培,郑贤中.MATLAB图像处理宝[M].北京:电子工业出版社,2011.

QIN Xiangpei, ZHENG Xianzhong. Image processing Collection Based on MATLAB[M]. Beijing: Publishing House of Science,2011.

[14] Kai Liu, Jie Lei, YunSong Li, et al. A Novel VLSI Architecture of SPIHT Using Breadth First Search for Real-Time Applications[J]. Journal of Signal Processing Systems for Signal, Image, and Video Technology,2012,68(1):113-125.

[15] Hala H. Zayed, Sherirt E. Kishk, Hosam M. Ahmed. 3D Wavelets with SPIHT Coding for Integral Imaging Compression[J]. International Journal of Computer Science and Network Security,2012,12(1):126-133.

[16] 邓宸伟,赵保军.一种快速改进型SPIHT算法[J].北京理工大学学报,2010,30(4):478-482.

DENG Chenwei, ZHAO Baojun. An Approach to Modify Fast SPIHT Algorithm[J]. Transactions of Beijing Institute of Technology,2010,30(4):478-482.

中图分类号TP391.41

DOI:10.3969/j.issn.1672-9722.2016.01.030

作者简介:徐小乐,男,硕士,研究方向:图像压缩。刘昌华,男,硕士,副教授,研究方向:图像压缩。

基金项目:国家自然科学基金青年基金(编号:61201452);武汉轻工大学研究生创新基金项目(编号:2013cx014)资助。

收稿日期:2015年7月11日,修回日期:2015年8月20日