毕业论文网
本论文是一篇免费优秀的关于分形论文范文资料，可用于相关论文写作参考。
一种改进的K-均值聚类分形编码方法
摘 要：为了解决分形图像编码耗时过长的问题,该论文主要研究了基于K-均值聚类的快速分形编码算法.首先引入方差法将子块分为简单块和复杂块,随后采用K-均值聚类算法对复杂子块及父块进行分类,并在搜索匹配父块的过程中运用近邻搜索法,使得相应子块仅在近邻范围内与同类的父块进行匹配运算.该方法对匹配块的搜索过程进行了优化,大幅度减少了编码时间.测试结果表明,与基本分形编码算法相比可提速多倍,并且其重构图像效果较好.
关键词：分形图像编码；K-均值聚类；近邻搜索；方差法
中图分类号：TP391文献标识码：A
AnImprovedFractalCodingMethodBasedonK-MeansClustering
GUOHui,HEJie,CHENXiaohong
(LaboratoryofImageProcessingandIntelligentInformationSystem,WuzhouUniversity,Wuzhou543002,China)
Abstract:Inordertosolvetheproblemofoverlylongtimeduringfractalimagecoding,thispaperfocusesonafastfractalcodingalgorithmbasedonK-meansclustering.Firstofall,thevariancemethodisemployedtodividetherangeblocksintosimplerangeblocksandcomplexrangeblocks;then,theK-meansclusteringalgorithmisappliedtoclassifythecomplexrangeblocksanddomainblocks,andthenearestneighborsearchapproachisappliedtosearchmatchingdomainblocks,soastomatchthecorrespondingrangeblockswiththedomainblocksofthesametypeonlywithintheneighboringscope.Thiethodoptimizesthesearchingprocesormatchingblocks,therebygreatlyshorteningtheencodingtime.Testresultsshowthat,comparedwiththebasicfractalcodingalgorithm,thiethodcanincreasetheencodingspeedbymanytimes,withhigh-qualityreconstructedimages.
Keywords:fractalimagecoding;K-meansclustering;nearestneighborsearch;variancemethod
1引言(Introduction)
分形图像编码算法具有压缩比高、快速解码和分辨率无关等优点,但其编码速度慢,使得分形图像编码难以实时化.如何提高分形编码速度成为分形图像压缩的主要研究方向之一.目前对分形编码算法进行改进主要分为两类：子块分类和邻域搜索.
子块分类法是在搜素匹配块之前,先按照某种特征将子块和父块分类,从而在匹配时用类内搜索代替全局搜索,以此来提高编码速度.国内外学者近年来就如何设计准确的分类方法做了很多尝试.文献[1]提出采用边缘分类算法将父块分为边缘类和非边缘类,并将各类父块按平均偏差排序.文献[2]针对在K-均值聚类算法中初始聚类中心难以选取的问题,提出了一种均值-标准差的初始聚类中心选取方法,并将其应用到分形图像编码中,对子块和父块进行聚类.文献[3]利用像素值空间和1D-DCT矢量实现模糊聚类,在解码质量同等的情况下将编码速度提高了40倍.
由于大量的实验数据表明,与子块匹配的父块大多数都在子块的附近,邻域搜索成为近年来研究最为集中的优化方法.文献[4]利用边缘形状相似的块集中于某些特定区域这一现象来实现邻域搜索.文献[5]-文献[7]则取得了持续进展,先后使用三均值特征、四位数特征、转动惯量特征来实现邻域搜索方法.文献[8]-文献[9]则分别提出了基于相似比、基于相对误差的邻域搜索方法.文献[10]利用互惠最近邻聚类算法实现彩像的自动分割.
在以上两类改进方法中,利用K-均值聚类算法对子块和父块进行分类处理,从而在更小范围内进行匹配搜索.这类方法引起了人们的重视,然而现有的K-均值聚类分形编码方法在选取聚类中心时普遍采用了随机选取初始聚类中心的策略,严重影响了分形图像编码的工作效率,而且降低了系统的稳定性.文献[2]结合数据分布的特点,采用基于均值-标准差的初始聚类中心选取方案,能有效减少K-均值聚类算法的迭代次数,加速聚类收敛速度,并将该方法应用于分形图像压缩编码,有效地缩短了编码时间.本文在文献[2]的基础上对分形编码算法进行了改进.首先引入基于方差的分类方法将子块分为简单块和复杂块,并只对复杂块进行编码,随后采用文献[2提出的基于均值-标准差方法来选取初始聚类中心,对子块和父块进行聚类,并在搜索匹配父块的过程中运用了近邻搜索法,使得相应子块仅在近邻范围内与同类的父块进行匹配运算.实验结果表明：本文算法能在保证重构图像质量的前提下,速度是基本分形编码算法的500多倍；与文献[2]提出的算法相比,本文算法能在保证重构图像质量的前提下提速190倍.
2基本分形图像编码(Thebasicfractalimage
coding)
在基本分形图像编码中,图像被分割为互不重叠、大小为B×B的子块(简称R块)集合,然后以步长为、尺寸为2B×2B的窗口从上到下、从左到右滑动生成父块(简称D块)集合.随后将所得D块进行4邻域像素平均操作,生成新的D块集合,以此作为匹配运算的码本Ω,最后对Ω进行八种等距变换,以实现对码本的扩充.对于任意R块,寻找能够满足式(1)的最佳匹配块Dm：
在式(1)中,s和o为D块的灰度平移参数和对比度调整参数.首先计算出满足式(1)内层最小化的s和o值,如式(2)所示,随后采用全域搜索法在扩充后的码本Ω中搜索满足式(1)外层最小化的父块Dm.需对所有的R块重复以上操作,并记录对应匹配块Dm的左上角坐标(x,y),等距变换参数n,灰度平移参数s和对比度调整参数o,直至完成整幅图像的编码.理论上要求,对不满足要求的s值作截断处理,以确保解码迭代过程的收敛.
其中,为向量2-范数,为向量内积运算,I为值全为1的矩阵.
解码时,取尺寸与原图像相同的任意初始图像,对于每个R块,根据编码记录的D块信息,到对应的坐标位置取出该D块进行4邻域像素平均操作、等距变换、灰度和对比度调整,并将其值赋予该R块.对每个R块均操作一次即完成整幅图像的一次迭代,随后将迭代完的图像作为初始图像,再进行8—10次迭代完成解码.
3方差分类法(Thevariance-basedclassification
method)
在基本分形图像编码算法中,为每个R块寻找最佳匹配D块需要对整个码本Ω进行全域搜索,导致编码速度过慢.为解决这个问题,可在编码前先将图像块进行分类.本文首先运用方差法将所有的R块划分为复杂块和简单块,只需要对复杂块进行编码,而简单块不进行编码,只存储该块的左上角坐标及像素平均值.解码时则利用该块的像素平均值在对应位置上进行填充.采用该方法无需对简单块进行编码,大大缩减了编码时间并提高了压缩比.下面式(4)为R块的方差计算.
方差阈值的选取对分形图像编码的各个性能参数都有重要的影响.方差阈值选取过大,复杂块数量变少,编码时间加快,但重构图像质量会降低.本文采用多幅图像进行测试分析,比对方差阈值对各个性能参数的关系.图1和图2是方差阈值与编码时间及重构图像的峰值信噪比之间的关系.
根据图1和图2,当方差阈值为5时,重构图像的峰值信噪比PSNR值仍然有30以上,但编码时间却能减少很多.综合各方面的参数考虑,本文选取方差阈值为5,把R块分为两类：简单块()和复杂块(),只对复杂块进行编码.
4近邻搜索法(Nearestneighborsearch)
大量的统计数据表明,待编码R块的最佳匹配块出现在其附近的概率很大,如图3所示.所以在待编码的R块的邻域范围内搜索它的最佳匹配块,可以大大减少搜索范围.
假定待编码R块的边长是RX,D块的边长是DX,本文以步进值DX/4在此R块的左上、右上与左下、右下四个邻域扫描,以获得匹配的D块.因为图片的尺寸为N*N像素,故扫描至图片的最右侧时则会越过边界.为了避免这一现象,设置水平扫描的D块数量为h-RX,这里h是指D块总数的开方.同理,垂直扫描的D块数量与水平扫描的D块数量相同.则近邻搜索的块数取值范围如下：
在式(5)—式(8)中,该R块所在的x坐标为,y坐标为,在其左上邻域查找过的D块数量为a,在其左下邻域查找过的D块数量为b,c则为其右上邻域查找的D块数量,d则为其右下邻域查找的D块数量.
如果R块的位置处于图片的左上角,即其左上邻域不存在D块时,则从D(I,j)开始搜索,并设a等于1；若a＜1时,同样设a等于1.当R块位于图片的右上角时,其右上角不存在D块,那么就搜索到D(I,h)为止,设b等于h；若b>h,同样设b等于h.当R块位于图片左下角时,其左下角不存在D块,那么就搜索到D(h,j)为止,设d等于h；当d>h,同样设d等于h.
5改进的K均值聚类分形图像编码方法(The
improvedfractalimagecodingmethodbasedon
K-meansclustering)
分形编码耗时过长的主要原因有两个：一是由于D块形成的码本搜索池域太大,二是在寻找最佳匹配块时采用的是全域搜索的方法.目前分形编码的热点是运用分类的方法来解决码本池域过大的问题,而对于搜索方法的问题则采用近邻搜索方法来代替全域搜素.本文在文献[2]的基础上,针对这两方面的问题提出一种改进的K均值聚类分形图像编码方法.
5.1K-均值聚类算法原理
作为划分型聚类方法,K-均值聚类算法应用非常广泛.利用它对图像进行分割,速度快,效果好,并且容易实施.K-均值聚类算法本质是对图像进行灰度的量化.其中心思想是：首先在要处理的元素集合中任意选取K个点作为初始聚类中心,然后计算集合中所有元素至聚类中心点的距离,并将该元素归类到与其距离最短的聚类中心类别中,这样一次聚类就完成了；当一次聚类完成后再计算各个聚类的全部元素的平均值,并用该平均值作为下一次聚类的聚类中心.对每一个元素重复执行迭代运算,计算过程中不断生成新的聚类中心,直到满足收敛条件或没有新的元素再被重新分配,聚类结束.
步骤4：重复步骤2和步骤3的过程,直至数据集合中全部的元素分类完成.
根据K-均值聚类算法的工作原理,可以看出聚类的质量绝大部分依赖于初始聚类中心的选取和聚类数的确定.即K-均值聚类算法的聚类收敛速度和聚类精度取决于聚类数及初始聚类中心的确定.
5.2聚类数的确定及初始聚类中心的选取
(1)聚类数的确定
聚类数对编码速度及解码图像质量有直接影响.若分类数少,那么每个聚类族中的元素就多,对R块来说搜索匹配块的范围就大,执行时间就长,但重构图像质量好；如果分类数多,则每个聚类族中的元素就少,对R块来说搜索匹配块的范围就小,编码速度就快.但由于分类数较多,导致相似匹配块会被分配到其他类中,使得重构图像质量降低,且对元素集合的聚类过程所耗的时间也会随之增加.表1是K取不同的分类值对某幅图像进行编码所对应的PSNR值(峰值信噪比)及编码时间t.
根据表1,若为了缩短编码时间而增加聚类数量是不可取的.综合考虑重构图像质量与编码速度,本文选取经验值K等于4.
(2)初始聚类中心的选取
通过上面对K-均值聚类算法的原理分析,如何将初始聚类中心定在元素分布比较密集的中心领域是很关键的.这样在中心周围的元素就容易被划分到最靠近的类别中,聚类算法的收敛速度也会加快,迭代的次数也会下降.对任意元素分布的特点分析可知,聚类点出现在族类元素平均值周围的概率是非常高的,标准差是衡量元素分布的重要参数.因此对初始聚类中心的选取本文采用文献[2]提出的标准差-均值的方法.
本文将文献[2]提出的标准差-均值的方法引入到分形图像编码算法中,对R块和D块进行分类,以减小匹配块的搜索范围.并使用近邻搜索算法来代替全域搜索法,以提高分形编码的速度.
(3)改进的K-均值聚类快速分形编码方法
为了加快编码速度,本文在对图像块进行聚类运算前,先根据R块的方差,将其分为两类：简单块()和复杂块().本文只对复杂块进行编码,利用K-均值聚类算法对复杂块进行分类,并存储各个块的类别号.然后引入近邻搜索法来减少匹配块的搜索范围.具体算法如下：
步骤1：把待处理图像分割为互不重叠且尺寸为的固定块,即R块.
步骤2：在图像中以作为步长从左到右、自上而下扫描,将图像分割为可重叠且大小为的D块,再采用四邻域像素平均法对D块进行处理,得到尺寸与R块相同的图像块,进行八种等距变换,形成码本.
步骤3：计算各R块的方差,将其分为两类：简单块()和复杂块().简单块不用进行编码,直接保存其左上角坐标,求出其像素平均值并存储.
步骤4：对于复杂块,先设定聚类数量K等于4,随后根据标准差-均值法选取初始聚类中心,并进行K-均值聚类,同时迭代后产生的新聚类中心记录下来,详细请参见5.1节.
步骤5：设定聚类数K等于4,并用R块最终的聚类中心作为初始中心对D块进行K-均值聚类.
步骤6：对于待编码的复杂R块,设定其近邻搜索的范围(参见第3节),且仅在该范围内搜索与其类型相同的匹配D块.若在该范围内没有同类的D块,则在该范围以外的同类D块池中搜索最佳匹配块,并记录最佳匹配块的五个参数：左上角坐标(x,y),等距变换参数n,灰度平移参数s和对比度调整参数o.
解码时对简单块的处理是读取其位置坐标及像素均值,然后将此均值作为填充值,直接将解码图像的对应区域填充.对于复杂块,则依据存储的码本参数,获取各个复杂块所对应的D块及相关信息,通过公式R等于进行多次迭代,还原出复杂块.一般情况下,经过8次左右的迭代可从任意相同尺寸的初始图像上还原出原图像.
6实验结果分析(Analysisofexperimentalresults)
本文在处理器为Pentium(R)Dual-Core,内存为2GB的计算机,运行环境为Matlab7.0,以256×256×8bit标准灰度图像Lena、Plane、Peppers和Parrot这4幅图像为例进行测试,并与基本分形编码算法和文献[2]的算法进行比对.在本实验中,R块的大小选取为4×4,D块的大小选取为8×8,步长为8.图5为其中2幅标准测试图像分别使用三种算法的重构图像效果.
由图5可知,通过人眼观察,使用三种算法编码并解码获得的重建图像质量基本持平,说明本文算法具有可行性.在基本分形编码算法与文献[2]的算法中,对R块、D块均是进行固定分割的,故这两种算法的压缩比C是固定不变的,其计算公式为C等于256×256×8/[H×(8+8+3+5+7)],其中H为R块总量；D块左上角坐标(x,y)分别被量化为8bit；等距变换的序号t则量化成3bit；对比度调整因子s及亮度调整因子o则分别量化成5bit和7bit.当R块的尺寸设置为4×4时,H＝256/4×256/4等于4096,编码压缩比C等于4.13.但在本文算法中,R块分为简单块与复杂块两类且其数量不同.若简单块的总量为S1,复杂块的总量为S2,则本文算法的压缩比C计算公式为：C＝256×256×8/[S1×(1+8)+S2×(7+7+3+5+7)],使用0对简单块进行标记,量化成1bit,块的像素平均值被量化成8bit,左上角坐标(x,y)分别被量化成7bit,其他参数的量化与基本算法相同.表2是分别使用基本分形编码算法、文献[2]算法及本文算法对4幅标准图像进行测试所得的实验数据[编码时间T(单位：s)、峰值信噪比PSNR(单位：dB)、压缩比C及加速比].
由表2的数据可知,本文算法与基本分形编码算法相比,虽然PSNR值略为下降,但编码时间明显缩短,最大加速比可达500多倍；与文献[2]的算法相比,PSNR值没有明显下降,但编码时间已大为减少,最大加速比可达190倍.与前两种算法相比,本文的压缩比也有所提高,的取值越大,所获得的简单块数量随之增多,编码压缩比也会随之升高,重建图像质量则会略为下降,这是由于在解码重建过程中简单块对应区域的原像素值被简单块像素均值代替,简单块越多,则与原图纹理差异越大.实际过程中,可根据解码质量需求来调节值.
7结论(Conclusion)
本文针对分形图像编码算法中搜索匹配块的过程耗时较多的特点,引入基于方差的分类方法将子块分为简单块和复杂块,并只对复杂块进行编码.随后引入文献[2]的方法来选取初始聚类中心,对子块和父块进行聚类,并在搜索匹配父块的过程中运用近邻搜索法,使得相应子块仅在近邻范围内与同类的父块进行匹配运算.实验结果表明,本文算法在保持峰值信噪比在30左右的前提下,编码速度是基本算法的570多倍,且获得更好的压缩比,证明了本文算法的可行性和优越性.
参考文献(References)
[1]裔传俊,刘亮.采用边缘分类和平均偏差比较的分形图像编码[J].计算机应用与软件,2015,32(2):211-214.
[2]王向阳,于雁春.基于改进K-均值聚类的快速分形图像编码算法[J].计算机科学,2008,35(2):219-222.
[3]K.Jaferzadeh,K.Kiani,S.Mozaffari.Accelerationoffractalimagecompressionsingfuzzyclusteringanddiscretecosinetranormbasedmetric[J].ImageProcessing,2012,6(07):1024-1030.
[4]Y.-L.LIN,M.-S.WU.Anedgepropertybasedneighborhoodregionsearchstrategyforfractalimagecompression[J].Computers&MathematicswithApplications,2011,62(01):
310-318.
[5]李高平.三均值特征的快速分形图像编码算法[J].中国图象图形学报,2011,16(01):1-7.
[6]李高平,向慧芬,赵正武.四分位数特征的快速分形图像编码算法[J].计算机工程与应用,2011,47(22):145-148.
[7]李高平,杨军,陈毅红.改进转动惯量特征的快速分形图像编码算法[J].计算机工程与应用,2013,49(24):144-148.
[8]盛飞.分形图像压缩的快速编码算法[D].南京:南京邮电大学,2013:12-15.
[9]杨培.基于分形图像编码的快速搜索方法研究[D].南京:南京邮电大学,2013:13-18.
[10]罗学刚,吕俊瑞,王华军,等.基于超像素的互惠最近邻聚类彩像分割[J].广西大学学报:自然科学版,2013,38(2):374-378.
作者简介：
郭慧(1981-),女,硕士,副教授.研究领域：图像编码.
贺杰(1982-),男,硕士,副教授.研究领域：图像编码,三维可视化应用.
陈晓虹(1993-),女,本科生.研究领域：图像压缩处理.
分形论文范文结:
关于对不知道怎么写分形论文范文课题研究的大学硕士、相关本科毕业论文分形论文开题报告范文和文献综述及职称论文的作为参考文献资料下载。