吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (3): 865-869.doi: 10.13229/j.cnki.jdxbgxb201603028

• 论文 • 上一篇    下一篇

一种基于大顶堆的SPIHT改进算法

车翔玖1, 梁森2   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.吉林大学 符号计算与知识工程教育部重点实验室, 长春 130012
  • 收稿日期:2015-05-06 出版日期:2016-06-20 发布日期:2016-06-20
  • 作者简介:车翔玖(1969),男,教授,博士生导师.研究方向:医学图像分割,图像传输与信息隐藏,大数据三维可视化及其在地学和医学中的应用.E-mail:chexj@jlu.edu.cn
  • 基金资助:
    国家自然科学基金项目(61170005,61133011); 国土资源部地球深部探测专项(SinoProbe-09-01).

Improved algorithm of SPIHT based on Max-Heap tree

CHE Xiang-jiu1, LIANG Sen2   

  1. 1.College of Computer Science and Technology, Jilin University,Changchun 130022,China;
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering, Jilin University, Changchun 130022,China
  • Received:2015-05-06 Online:2016-06-20 Published:2016-06-20

RICH HTML

0   

PDF (PC)

125

摘要： 多级树集合(SPIHT)算法在多次排序扫描过程中需要进行大量重要性测试,由此导致算法的压缩编码效率显著降低。为提高SPIHT算法的压缩效率,本文利用大顶堆方法,提出了一种 SPIHT改进算法。改进算法优化了SPIHT中的重要性测试,并将函数时间复杂度从O(logn)降为O(1)。实验结果表明本文方法在进行多次小波变换时效果尤为显著,使得SPIHT 编码时间趋于一个常数,压缩效率比未改进前提升数倍。

关键词: 计算机系统结构, 多级树集合算法, 小波变换, 大顶堆

Abstract: The Set Partitioning in Hierarchical Trees (SPIHT) algorithm requires a large number of tests to determine its significance during several times of scanning in sequence, which severely damages the efficiency of compression. To raise the SPIHT's compression efficiency, an improved algorithm of SPIHT used by Max-Heap Tree is proposed. It optimize the test function of significance and reduce the algorithm's time complexity from O(logn) to O(1). Experimental results show that the improved SPIHT is particularly efficient in continuous wavelet transforms, and its encoding time goes to be a constant and compression efficiency is improved by several times.

Key words: computer system organization, set partitioning in hierarchical trees(SPIHT), wavelet transform, max-heap

中图分类号: 

  • TP301
[1] Shapiro J M. Embedded image coding using zero trees of wavelet coefficients[J]. IEEE Transactions on Signal Processing, 1993, 41(12): 3445-3462.
[2] Said A, Pearlman W A. A new, fast, and efficient image codec based on set partitioning in hierarchical trees[J]. IEEE Transactions on Circuits and Systems for Video Technology, 1996, 6(3): 243-250.
[3] Li Xiao-fei, Ma Da-wei, Fan Xiao-lin. New region of interest coding method based on SPIHT algorithm[J]. Computer Applied Research, 2007, 24(2):189-191.
[4] 汤敏, 陈秀梅, 陈峰. 基于 Contourlet 变换和 SPIHT 算法的彩色医学图像压缩[J]. 计算机科学, 2014, 41(1): 303-306.
Tang Min, Chen Xiu-mei, Chen Feng. Colorful medical image compression based on contourlet transform and SPIHT algorithm[J]. Computer Science, 2014, 41(1): 303-306.
[5] 刘号, 董育宁. 基于 SPIHT 的 ROI 图像压缩编码新算法[J]. 南京邮电大学学报:自然科学版, 2011, 31(1): 70-75.
Liu Hao. Dong Yu-ning. A new method for ROI coding based on SPIHT[J]. Journal of Nanjing University of Posts & Telecommunications(Nature Science Edition),2011,31(1):70-75.
[6] 李毅, 龚建华. 基于SPIHT小波的DEM自适应压缩方法研究[J]. 地理与地理信息科学, 2009, 25(4):22-24.
Li Yi, Gong Jian-hua. Study on DEM self-adaptation compression method based on SPIHT wavelet[J]. Geography and Geo-Information Science, 2009, 25(4):22-24.
[7] 丁晓峰, 何凯霖. 基于改进提升小波变换SPIHT的图像压缩算法[J]. 计算机测量与控制, 2014, 22(11) :3670-3672.
Ding Xiao-feng,He Kai-lin. A lossy image coding for wireless multimedia sensor networks[J]. Computer Measurement & Control, 2014,22(11):3670-3672.
[8] 孙延奎. 小波分析及其应用[M]. 北京.清华大学出版社,2012:121-128.
[9] 李哲涛,王仕果,王灵矫.一种改进的 SPIHT 图像压缩方法[J].科学技术与工程, 2008,14(8),4009-4012.
Li Zhe-tao, Wang Shi-guo, Wang Ling-jiao. Novel image compression method based on improved SPIHT[J]. Science Technology & Engineering, 2008,14(8),4009-4012.
[10] 顾海明, 王明翠. SPIHT算法的改进[J]. 青岛科技大学学报:自然科学版, 2008, 29(2):185-188.
Gu Hai-ming, Wang Ming-cui.Improvement of SPIHT algorithm[J]. Journal of Qingdao University of Science and Technology(Natural Science Edition).2008,29(2):185-188.
[11] 宋春林, 冯瑞, 金炜,等. 改进的多分辨率SPIHT算法[J]. 计算机工程, 2008,34(4):241-243.
Song Chun-lin, Feng Rui, Jin Wei, et al. Improved multi-resolution SPIHT algorithm[J]. Computer Engineering, 2008, 34(4):241-243.
[12] 杨海英, 张志军, 李昕. 基于平衡多小波的SPIHT图像压缩算法研究[J]. 辽宁工业大学学报:自然科学版, 2009, 29(4):214-216.
Yang Hai-ying, Zhang Zhi-jun, Li Xin. Algorithm study of SPIHT code in image compression based on balanced multiwavelets[J]. Journal of Liaoning University of Technology (Nature Science Edition),2009,29(4):214-216.
[13] 王建军, 刘波. 一种改进的基于无链表SPIHT的图像压缩算法[J]. 科技导报, 2010, 28(6):42-45.
Wang Jian-jun. Liu Bo.Improved listless SPIHT based image compression algorithm[J]. Science & Technology Review, 2010, 28(6):42-45.
[14] 王爱丽, 张晔, 谷延锋,等. 基于多小波变换的SAR图像压缩[J]. 吉林大学学报:工学版, 2008, 38(4):966-969.
Wang Ai-li, Zhang Ye, Gu Yan-feng, et al. SAR image compression based on multiwavelet transform[J]. Journal of Jilin University(Engineering and Technology Edition), 2008, 38(4):966-969.
[15] 丁媛媛, 司玉娟, 郎六琪,等. 基于提升小波变换的图像压缩编码的VLSI实现[J]. 吉林大学学报:工学版, 2007, 37(3):675-680.
Ding Yuan-yuan, Si Yu-juan, Lang Liu-qi, et al. VLSI implementation of image compression coding based on lifting wavelet transform[J]. Journal of Jilin University(Engineering and Technology Edition), 2007.37(3):675-680.
[1] 余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592.
[2] 董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604.
[3] 赵博, 秦贵和, 赵永哲, 杨文迪. 基于半陷门单向函数的公钥密码[J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[4] 刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267.
[5] 董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272.
[6] 于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[7] 邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600.
[8] 魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207.
[9] 郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234.
[10] 魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[11] 季彦婕, 陈晓实, 王炜, 胡波. 基于小波变换和粒子群小波神经网络组合模型的有效停车泊位短时预测[J]. 吉林大学学报(工学版), 2016, 46(2): 399-405.
[12] 肖钟捷. 基于小波空间特征谱熵的数字图像识别[J]. 吉林大学学报(工学版), 2015, 45(6): 1994-1998.
[13] 董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259.
[14] 匡哲君，师唯佳，胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605.
[15] 张忆文，郭锐锋. 实时系统混合任务低功耗调度算法[J]. 吉林大学学报(工学版), 2015, 45(1): 261-266.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 刘松山, 王庆年, 王伟华, 林鑫. 惯性质量对馈能悬架阻尼特性和幅频特性的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] 初亮, 王彦波, 祁富伟, 张永生. 用于制动压力精确控制的进液阀控制方法[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] 李静, 王子涵, 余春贤, 韩佐悦, 孙博华. 硬件在环试验台整车状态跟随控制系统设计[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] 胡兴军, 李腾飞, 王靖宇, 杨博, 郭鹏, 廖磊. 尾板对重型载货汽车尾部流场的影响[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[5] 王同建, 陈晋市, 赵锋, 赵庆波, 刘昕晖, 袁华山. 全液压转向系统机液联合仿真及试验[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[6] 张春勤, 姜桂艳, 吴正言. 机动车出行者出发时间选择的影响因素[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[7] 马万经, 谢涵洲. 双停车线进口道主、预信号配时协调控制模型[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[8] 于德新, 仝倩, 杨兆升, 高鹏. 重大灾害条件下应急交通疏散时间预测模型[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[9] 肖赟, 雷俊卿, 张坤, 李忠三. 多级变幅疲劳荷载下预应力混凝土梁刚度退化[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .
[10] 肖锐, 邓宗才, 兰明章, 申臣良. 不掺硅粉的活性粉末混凝土配合比试验[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发