基于稀疏分解的交通图像压缩

1、第27卷 第6期2010年6月 公 路 交 通 科 技JournalofHighwayandTransportationResearchandDevelopmentVol 27 No 6 Jun 2010文章编号:1002 0268(2010)06 0112 05基于稀疏分解的交通图像压缩王 庆,张葛祥,荣海娜,张雪白(西南交通大学 电气工程学院,四川 成都 610031)摘要:随着道路实时监控系统的广泛应用,需要处理的数据量激增,为了解决传统图像压缩方法随压缩比增大解码图像质量急剧下降的问题,提出一种新的基于稀疏分解的交通图像压缩算法。该算法将稀疏分解引入到交通图像压缩中,先根据交通图像特点

2、,引入背景差法对交通图像进行预处理,然后采用稀疏分解算法对图像进行分解,最后通过分析交通图像稀疏分解后的数据分布规律,并根据低比特率图像压缩要求,提出改进的排序差分编码方案进行编码,以期在低比特率下,获得较好的解码图像质量。仿真试验结果表明,与现有的排序差分编码算法相比,该算法能够更有效地实现交通图像的压缩,相同压缩比下,解码图像有更高的峰值信噪比和主观图像质量。关键词:交通工程;交通图像压缩;改进编码方案;稀疏分解;背景差法中图分类号:TN919 81 文献标识码:ATrafficImageCompressionBasedonSparseDecompositionWANGQing,ZHANG

3、Gexiang,RONGHaina,ZHANGXuebai(SchoolofElectricalEngineering,SouthwestJiaotongUniversity,Chengdu Sichuan 610031,China)Abstract:Alongwiththeextensiveapplicationofthereal timemonitoringsystem,theamountofdatawhichrequiresprocessingincreasessharply Inordertosolvetheproblemthatthequalityofthedecodingpictu

4、refallssuddenlywithariseofthecompressionratiowhenusingthetraditionalmethodsofimagecompression,akindofnewtrafficimagecompressionalgorithmbasedonsparsedecompositionwasproposed,inwhichsparsedecompositionwasintroducedintotrafficimagecompression Firstofall,accordingtothecharacteristicsofthetrafficimage,b

5、ackgroundsubtractionwasintroducedinpre processingtrafficimages Thenthesparsedecompositionalgorithmwasadoptedinimageprocessing Afterwards,thedistributionofsparsedecomposeddataoftrafficimageswasanalysed Atlast,animprovementoftheorderdifferentialcodingschemeswasproposedtogetbetterdecodedimagequalityatl

6、owbitrate Theexperimentalresultshowsthatthealgorithmcanachieveamoreefficienttrafficimagecompressioncomparedwiththeexistingorderdifferentialcodingalgorithm Thedecodedimage speaksignal noiseratioandsubjectivequalityarebetteratthesamecompressionratioKeywords:trafficengineering;trafficimagecompression;i

7、mprovedencodingscheme;sparsedecomposition;backgroundsubtraction0 前言随着交通需求急剧增长,交通运输所带来的交通拥堵、交通事故等负面效应也日益突出,逐渐成为制约经济和社会发展的全球性问题。道路实时视频监控收稿日期:2009 09 28基金项目:国家自然科学基金资助项目(60702026);四川省青年科技基金资助项目(09ZQ026-040)作者简介:王庆(1985-),女,四川广安人,硕士研究生,研究方向为图像压缩 (1091645755qq com)系统的广泛应用,一定程度上缓解了该问题,但却使需要处理的数据激增,对图像压缩提出

8、了更高的要求1-2。现有的图像压缩标准是基于图像的正交变换,在较低压缩比时取得了良好压缩效果,重建图像质量优良,但随着压缩比的增大,重建图像质量急剧第6期 王 庆,等:基于稀疏分解的交通图像压缩 113下降,无法满足低比特率下图像压缩要求。1993年Mallat和Zhang提出了完备原子库的思想3,1994年Mallat把该思想用于二维图像表示研究上,提出了图像稀疏分解MatchingPursuit(MP)方法。为了更好地表示图像内容,Vandergheynst提出了非对称原子库5。在低比特率条件下,很多研究结果都优于现有的图像压缩国际标准。目前,国内在此方面的研究较少,但近年来已受到较大关注

9、,并取得了一些研究成果9-116-84对比分析。1 背景差法与一般普通图像不同,交通图像往往是在同一观测点所拍摄,图像的背景很相似,如图1(a)和图1(b)所示。虽然2幅图像不同,但背景部分含有极大的相似性。因此,可以在图像进行稀疏分解前,引入背景差法12对交通图像进行预处理,去除交通图像背景部分信息,减少分解图像的冗余性。背景差法是用待分解图像与一个背景图像作图像差,即将2幅图像进行点对点相减,数学表示式为:R(i,j)=F(i,j)-G(i,j),(1)式中,F(i,j)、G(i,j)和R(i,j)分别表示待分解图像(目标图像)、背景图像和结果图像。采用公式(1)和图1(e)所示的背景图像

10、分别对图1(a)和图1(b)显示的2幅交通图像进行图像差操作后得到图1(c)和图1(d)。与图1(a)和图1(b)相对比,图1(c)和图1(d)的背景部分所含的信息量明显减少,保留的信息主要是车辆图像。由此可见,背景差法可以有效地去除交通图像背景信息,减少图像冗余性。根据查到的资料,将稀疏分解思想和交通图像特点相结合,用于交通图像压缩的相关文献还没有报道。为了解决交通图像压缩问题,本文首先将MP算法引入到交通图像压缩中。根据交通图像特点,采用背景差法,去除交通图像背景,提高重构图像质量。然后在介绍图像稀疏分解的基础上,分析交通图像稀疏分解的数据分布规律和常用的差分排序编码方案10的不足,并根据

11、交通图像稀疏分解的数据分布规律和低比特率下图像压缩的要求,提出改进的排序差分编码方案。最后对基于背景差法分解和直接分解效果进行对比分析,以及将改进的排序差分编码方案和文献10中的排序差分编码方案的压缩效果进行图1 交通图像和背景差分处理后的图像Fig 1 Trafficimageandprocessedimagebybackgroundsubtraction2 图像稀疏分解2 1 图像稀疏分解的基本思想 匹配追踪算法设研究的图像为f,其大小为N1!N2,其中N1和N2分别为图像的高和宽。图像稀疏分解的完备原子库为D=g ,其中,g 为由参数组 定义的原子, 为参数组 的集合。MP方法分解图像过

12、程如下4-5:首先从过完备原子库中选出与待分解图像最为匹配的原子g 0,满足以下条件:|<f,g 0>|=sup|f,g |。 信息2部分,即f=R0f=<f, 0>g +R1f,(2)这样,可将图像分解为在最佳原子g 上的分量和残余0(3式中,R1f是用最佳原子对原图像进行匹配后的残余。对匹配后的残余不断进行上面同样的分解过程,即:Rkf=<Rkf,g >g k+Rk+1f,k其中,g k满足:k|<Rkf,g >|sup<Rf,g >|。k (4)(5)由公式(3)和(4)可知,经过n步分解后,图像被分解为n-1f=k=0#<

13、;Rf,g >g +Rf,kkkn(6)式中,Rkf随k的增大而成指数衰减到0,因此用少数原子(与图像大小相比较而言)就可以表示图像的主要成分,即图像可以分解为114 公 路 交 通 科 技 第27卷n-1f%k=0#<Rkf,g >g k。k(7)有原子的投影分量采用相同量化的位长。但实际上,由于原子幅度的差异,采用均匀量化表示每段内的所有原子,存在较大的冗余。例如,当排序差分后投影分量为3时,用二进制表示为11,只需要2位就可以表示,如果分配5位或6位码来表示,则产生了较大的编码冗余。为了分析旋转分量的分布规律,对旋转分量绘制了频率直方图,如图2(d)所示。从图2(d)可

14、知,旋转参数在边界处分布的原子较多,呈非均匀分布。如对该参数采用文献10中所述的均匀量化,也会产生较大编码冗余。2 2 图像稀疏分解结果表示非对称原子5在图像稀疏表示中显示出良好性能,所以本文在稀疏分解中采用非对称原子。非对称原子的基本形式表示如下(未经过规一化处理):g(x,y)=(4x2-2)e-(x+y)22。(8)通过对基本非对称原子进行旋转、平移和伸缩变换,可以得到一系列原子g ,从而形成过完备原子库D=g 。g =g!,sxsy(9)式中, =(!,u,v,sx,sy),而!,u,v,sx,sy分别代表原子的旋转分量、原子在x、y方向上的平移分量和原子在x、y方向上的伸缩分量(或称

15、为尺度分量)。图像稀疏分解的最终结果为:<Rf,g k>,!k,uk,vk,sx,sy,kk式中,k=0,1,2,&,n-1,参数的取值范围为:!=360,!1,max(M,N);max(M,N)u1,M;v1,N;2,k(10)sx=s t 0,NNlogM2-NN),NN=5;Nsy=2,s t 0,NNlog2-NN),NN=5。(11)3 改进的差分编码方案3 1 图像稀疏分解结果的数据分布规律为了对图像稀疏分解的最终结果进行编码,需要分析其分布规律。本文使用匹配追踪算法3-4,9和非对称原子5图2 部分分解结果数据分布规律Fig 2 Distributionofp

16、artialsparsedecompositiondata3 2 图像稀疏分解结果数据的编码为了减少编码冗余性,本文提出一种改进的排序差分编码方案。该方案根据排序差分后投影分量和旋转旋分量的非均匀分布规律,以赫夫曼编码和排序差分编码相结合。先将稀疏分解结果数据按投影分量的值由大到小进行排序,其他分量的顺序也相应改变,对排序后的投影分量进行差分处理。然后对进行差分后的投影分量和平移变换后的旋转分量进行赫夫曼编码。具体实施步骤如下:步骤1:对投影分量<Rkf,g >的值由大到小进k行排序,使投影分量<Rkf,g >呈单调递减排列,其k他分量也随之相应发生改变。步骤2:对投影

17、分量采用式(12)做差分,即<Rf,g >=kk作为原子库,对图1(d)进行分解获得500个原子,其部分分解结果的数据如图2所示。图2(a)表示排序差分后的投影分量<Rkf,g >k的分布规律。图2(b)表示排序差分后,第100个原子到第400个原子的投影分量。图2(c)表示旋转分量。图2(d)表示旋转分量的频率直方图,显示了旋转分量的分布情况。文献10采用排序差分编码方案对投影分量<Rf,g k>进行预处理,在一定程度上减少编码冗余,但投影分量<Rkf,g >仍然包含很大的编码冗余。k在图2(a)和图2(b)中,对于排序差分后的投影分量,不同原

18、子幅度相差较大,虽然大部分原子幅度都集中在(0,10)以内,但仍有部分原子排序差分后的投影分量的幅度较大。文献10的编码方案采用在整个k<Rkf,g >k<Rk-1f,g >k-1k=1,(12)k>1,式中,<Rkf,g >,<Rk-1f,g >和<Rkf,g k>kk-1k-第6期 王 庆,等:基于稀疏分解的交通图像压缩 1151个原子的投影分量和排序后第k个原子的投影分量。步骤3:对差分后的投影分量进行赫夫曼编码。在进行赫夫曼编码时,每个投影分量被描述为(size,amplitude)符号对。其中,size表示用于编码am

19、plitude所需要的比特数,采用赫夫曼编码;amplitude表示差分后投影分量幅值,采用二进制编码。步骤4:对旋转分量!采用式(13)进行变换:!=!max(m,n)-!,!(max(N1,N2)/2,!>max(N1,N2)/2,(13)和直接进行稀疏分解这2种情况下的峰值信噪比。从图3可以看出,采用背景差法进行预处理,在分解相同原子数目的情况下,可以得到更高的峰值信噪比。图4是这2种方法处理后的解码图像,从视觉效果来看,基于背景差法预处理后进行分解的图像质量更高。式中,N1和N2为图像的高和宽。对变换后的旋转角采用赫夫曼编码,即每个旋转分量!被描述为(size,amplitude

20、)符号对。其中,size表示用于编码amplitude所用的比特数,采用赫夫曼编码。amplitude表示旋转分量的幅值,当amplitude为正时,采用二进制编码;当amplitude为负时,对旋转分量-1,取补码的最后size位。步骤5:对x、y方向的平移分量和尺度参数u、v、sx、sy采用均匀量化编码。平移分量量化位长取为8,尺度分量量化位长取为6。步骤6:输出编码,计算压缩比。步骤7:重构图像,计算峰值信噪比。4 仿真试验及结果分析试验中,采用256!256,8bit量化图1(c)的交通图片,过完备库的构建采用文献5提供的方法。为了兼顾时间复杂度和空间复杂度,本文在具体试验中采用了文献

21、9所提出的粒子群算法搜索最佳原子,在本质上用局部最优代替全局最优,实现图像在过完备库上的分解。试验分为2部分:第1部分是用背景差法对交通图像进行预处理后分解效果和直接分解效果的对比试验。第2部分是本文编码方案和文献10的编码方案的效果对比试验。本文使用峰值信噪比(PSNR)来衡量图像质量,其计算公式如式(14)所示。其中,xi,j为原始图像)图3 2种基于稀疏分解方法的结果比较Fig 3 Comparisonofresultsobtainedbasedonsparsedecomposition图4 解码图像Fig 4 Decodedimages4 2 基于稀疏分解的图像压缩编码方法的对比本试验

22、数据采用基于差分背景方法的分解结果。图5对比了改进的差分编码方案和文献10中的排序差分编码方案的压缩效果。从图5中可以看出,当比特率从0开始逐渐变大时,本文方法的峰值信噪比始终比文献10中的方法的峰值信噪比高。由此可知,在低比特率变化情况下,与文献10中的方法相比,本文方法效果更好。5 结语的像素;xi,j为重建图像的像素;N1、N2为图像的长和宽。PSNR=10!10!#0N1N2j=N1Ni=0#(xi,j-2)xi,j)2。(14)目前在各式各样图像压缩方法中,基于离散余弦变换和小波变换的传统压缩方法,随着压缩比的增大,图像质量急剧下降,已不能满足交通图像处理的需要。为此,本文将稀疏分解

23、方法引入到交通图像压缩中,结合交通图像的特点,提出了一种压缩编码方4 1 图像稀疏分解之间的对比116 公 路 交 通 科 技 第27卷Proceedingsofthe1995InternationalConferenceonImageProcessing Washington,1995:330-3335 VANDERGHEYNSTPP,FROSSARDP EfficientImageRepresentationbyAnisotropicRefinementinMatchingPursuitC/ProceedingsoftheAcoustics,Speech,andSignalProcessi

24、ngonIEEEInternationalConference Washington,D C :IEEEComputerSociety,2001:1757-17606 FROSSARDP,VANDERGHEYNSTP,IVENTURARMF,etal APosterioriQuantizationofProgressiveMatchingPursuit图5 低比特率下2种基于稀疏分解的图像压缩方法结果对比Fig 5 Comparisonofresultsobtainedbytwoimagescompressionmethodsbasedonsparsedecompositionwithlowb

25、it rateStreamsJ IEEETransactionsonSignalProcessing,2004,52(2):525-5357 ALIREZAS,SHAHRAMS ProgressiveCodingofaGaussianSourceUsingMatchingPursuitJ IEEETransactionsonSig nalProcessing,2008,56(2):636-6498 CHANHT,FUCM,HUANGCL ANewErrorResilientVideoCodingUsingMatchingPursuitandMultipleDescriptionCodingJ

26、IEEETransactionsonCircuitsandSystemsforVideoTechnology,2005,15(8):1047-10529 杨愚 图像稀疏分解快速实现及初步应用D 成都:西南交通大学,2007YANGYu FastAlgorithmforOMP basedImageSparseDecompositionandItsPrimaryApplicationD Chengdu:SouthwestJiaotongUniversity,200710张跃飞,姜玉亭,王建英,等 基于稀疏分解的图像压缩J 系统工程与电子技术,2006,28(4),513-537ZHANGYuefe

27、i,JIANGYuting,WANGJianying,etal ImageCompressionBasedonSparseDecompositionJ SystemsEngineeringandElectronics,2006,28(4),513-53711刘利雄,廖斌,贾云得,等 基于小波和匹配跟踪的分层图像编码算法J 北京理工大学学报,2007,27(10):891-895LIULixiong,LIAOBin,JIAYunde,etal Multi-layeredImageCodingBasedonWaveletandMatchingPursuitTrans formsJ JournalofBeijingInstituteofTechn