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

• Orginal Article • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] ZHAO Bo, QIN Gui-He, ZHAO Yong-Zhe, YANG Wen-Di. Public key cryptosystem based on semi-trapdoor one-way function [J]. 吉林大学学报(工学版), 2018, 48(1): 259-267.
[2] YU Bin-bin, WU Xin-yu, CHU Jian-feng, HU Liang. Signature protocol for wireless sensor network based on group key agreement [J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[3] WEI Xiao-hui, LI Xiang, LI Hong-liang, LI Cong, ZHUANG Yuan, YU Hong-mei. Flexible Online MapReduce model and topology protocols supporting large-scale stream data processing [J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[4] XIAO Zhong-jie. Recognition of digital image based on wavelet space feature spectrum entropy [J]. 吉林大学学报(工学版), 2015, 45(6): 1994-1998.
[5] FU Shuai, MA Jian-feng, LI Hong-tao, WANG Chang-guang. Improved data aggregation algorithm based on clustered wireless sensor network [J]. 吉林大学学报(工学版), 2014, 44(4): 1118-1125.
[6] WANG Xin, LI Wei-lin, LIU Fu. New algorithm of CT/MRI medical image fusion based on wavelet domain [J]. 吉林大学学报(工学版), 2013, 43(增刊1): 25-28.
[7] XIA Ying-jie, LI Jin-ping, CHEN Rui. Automatic synthetic registration method based on substation multi-modal images [J]. 吉林大学学报(工学版), 2013, 43(增刊1): 47-50.
[8] ZHANG Jiu-wen, MI Jin-cai, ZHANG Tong-feng. Texture image retrieval based on DT-CWT and generalized gaussian density [J]. 吉林大学学报(工学版), 2013, 43(增刊1): 60-63.
[9] BAO Lei, XU Qi-zhi. Spectrum-keeping algorithm for fusing based on PCA [J]. 吉林大学学报(工学版), 2013, 43(增刊1): 88-91.
[10] LIU Yuan-yuan, CHEN He-xin, ZHAO Yan, SUN Hong-yan. New DWT dynamic video watermarking algorithm [J]. 吉林大学学报(工学版), 2013, 43(增刊1): 445-449.
[11] HU Yu-ping, WANG Zhi-jian, ZHANG Ling-hua, YIN Hua. Image-adaptive watermarking algorithm based on chaos map and DWT [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 401-404.
[12] HU Liang, CHI Ling, YUAN Wei, CHU Jian-feng, XU Xiao-bo. Improvements against fault induction attack for RC4 algorithm [J]. , 2012, 42(05): 1231-1236.
[13] LIU San-min, SUN Zhi-xin. P2P traffic identification based on support vector data description [J]. , 2012, 42(04): 947-951.
[14] FU Zhao-yang,GUO Lei,CHANG Wei-wei. Fusion algorithm of hyperspectral images based on wavelet transform and multichannel PCNN [J]. 吉林大学学报(工学版), 2011, 41(03): 838-843.
[15] QIAO Yu-long, ZHAO Chun-hui, PAN Jeng-shyang,. Fast k nearest-neighbor classification algorithm based on Haar wavelet transform [J]. 吉林大学学报(工学版), 2011, 41(01): 231-0234.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[5] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[6] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[7] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[8] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[9] XIAO Yun, LEI Jun-qing, ZHANG Kun, LI Zhong-san. Fatigue stiffness degradation of prestressed concrete beam under multilevel amplitude cycle loading[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .
[10] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd