范文一：四叉树编码

四叉树编码

一、 原理

四叉树编码的基本思想是：首先将把一副图像或栅格地图（2k?2k,k>1,不足则补网）等分成四个一级字块，顺序为左上，右上，左下，右下；然后逐块检查其中所有格网属性值（或灰度值），若相同，则该字块不再分；若不同，则将该子块进一步分成四个二级子块；如此递归地分割，直到每个子块的属性或灰度均相等为止。

二、 实现

本程序实现将一个（2k?2k,k>1,不足则补网）数组（一维数组表示），打印出每个字块的等级和值。

//实现四叉树编码

#include"stdio.h"

void Qutree(int arysize,int level,float curary[] )//arysize 表示矩阵长度，level 表示等级，curary[]表示当前矩阵

{

float fi=curary[0];

int i;

//遍历当前数组，是否同构

for(i=0;i<>

{

if(fi!=curary[i])

{

break;

}

}

if(i==arysize*arysize)

{

printf("%d,%f",level,fi);

printf("\n");

return;

}

else

{

arysize/=2;

float *ary1=new float[arysize*arysize];

float *ary2=new float[arysize*arysize];

float *ary3=new float[arysize*arysize];

float *ary4=new float[arysize*arysize];

for(i=0;i

{

for(int j=0;j

{

//左上

ary1[i*arysize+j]=curary[i*(arysize*2)+j]; //右上

ary2[i*arysize+j]=curary[i*(arysize*2)+(arysize+j)];

//左下

ary3[i*arysize+j]=curary[(arysize+i)*(arysize*2)+j];

//右下

ary4[i*arysize+j]=curary[(arysize+i)*(arysize*2)+(arysize+j)];

}

}

level++;

Qutree(arysize,level,ary1);

Qutree(arysize,level,ary2);

Qutree(arysize,level,ary3);

Qutree(arysize,level,ary4);

}

}

int main()

{

//float aa[16]={1,1,2,2,1,1,3,3,4,2,1,2,3,4,3,4};

//Qutree(4,0,aa);

float

aa[64]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

Qutree(8,0,aa);

return 0;

}

参考资料：地理信息系统原理与算法（吴立新，史文中编著）

范文二：四叉树编码的原理

2.2.4 四叉树编码

(quad-tree code)[四叉树分割演示]

四叉树结构的基本思想是将一幅栅格地图或图像等分为四部分，逐块检查其格网属性值(或灰度) ，如果某个子区的所有格网值都具有

相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区。这样依次地分割，直到每个子块都只含有相同的属性值或灰度为止。

四叉树的生成算法：

从上而下的分割算法：需要大量的运算，因为大量数据需要重复检查才能确定划分。当矩阵比较大，且区域内容要素又比较复杂时，

建立这种四叉树的速度比较慢。

从下而上的合并算法：如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这种方法重复计算

较少，运算速度较快。

为了保证四叉树能不断的分解下去，要求图像必须为2n*2n的栅格阵列，n 为极限分割次数，n+1是四叉树的最大高度或最大层数。

四叉树编码的特点：

①容易而有效地计算多边形的数量特征；

②阵列各部分的分辨率是可变的，边界复杂部分四叉树较高即分级多，分辨率也高，而不需表示许多细节的部分则分级少，分辨率

低，因而既可精确表示图形结构又可减少存贮量；

③栅格到四叉树及四叉树到简单栅格结构的转换比其它压缩方法容易；

④多边形中嵌套异类小多边形的表示较方便。

四叉树结构分类：

（1）常规四叉树

①常规四叉树除了记录叶结点之外，还要记录中间结点。

②结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。

③这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。

（2）线性四叉树

①线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。

②线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进

制或十进制的Morton 码。

基于十进制的Morton 码及四叉树的建立 ：

（a ）四叉树分割示意图

基于按位操作的运算计算Morton 码：

设十进制表示的行、列号在计算机内部的二进制数字分别为：(b) 基于十进制的线性四叉树Morton 码

十进制的Morton 码实际上是II 、JJ 中的二进制数字交叉结合的结果，即

线性四叉树存储结构：

（a ）线性四叉树存储结构

二维行程编码：(b) 二维行程编码存储结构

在生成的线性四叉树表中，仍存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成

一个值，形成二维行程编码（Two Dimensional Run Encoding，简称 2DRE）表。在这种二维行程编码中，前后两个地址码之差表达了该行程段的格网数，它可以表示该子块的大小。

范文三：【doc】二维图形数据的线性四叉树编码方法研究

二维图形数据的线性四叉树编码方法研究

第32卷第4期陕西师范大学(自然科学版)Vo1.32No.4

2004年12月JournalofShaanxiNormalUniversity(NaturalScienceEdition)Dee.2004 文章编号:1672—4291(2004104—0098—05

二维图形数据的线性四叉树编码方法研究

付炜

(燕山大学信息学院通信与电子工程系,河北秦皇岛066004)

摘要:介绍了二维图形数据的线性四叉树编码数据结构.用该数据结构研究了二维

图形数据的四

叉树编码的转换,缩放,显示,存储等算法,讨论了二维图形数据由叉树编码数据转

换为光栅扫

描显示图形的方法以及用C语言实现二维图形四叉树编码数据结构的各种算法.

该算法适用于二

维图形数据的四叉树编码数据的压缩存储和各种逻辑图形操作,可节省大量的存

储空间,加快图形

/图像数据的运算速度,为计算机图形学的压缩编码技术提供了新的研究手段.

关键词:二维图形;线性四叉树编码;图形处理

中图分类号:TP302.4;0235文献标识码:A

Linearquadtreecodingapproachfortwo-dimensiongraphicdata FUWei

(DepartmentofCommunicationandElectronicEngineeringofInformationInstitute, YanshanUniversity,Qinhuangdao066004,Hebei,China)

Abstract:Thedatastructureoflinearquadtreecodingfortwo-dimensiongraphicdataispresented.

Withthedatastructure,thealgorithmsoftransformation,oontraction,andmagnification,storage,

etc.ofquadtreecodingfortwo-dimensiongraphicdataarestudied.Andtheapproacheswhich

canbe

usedtotransformthedatastructureofquadtreecodingfortwo-dimensiongraphicsdataintograting

scandisplay.Meanwhile,withtheClanguageprogramming,variousalgorithmsarediscussedwhich

canbeusedtOrealizestore,display,transformationofquadtreecodingdata,andtotransformpixel

matrixintodatastructureofquadtreecodingfortwo-dimensiongraphics.Thealgorithmsaresuitable

tooompressingstorageofquadtreecodingdatafortwo-dimensiongraphics,andvariouslogical

operationofimages.Bythemethods,lotsofstoreunitsareeconomized,andoomputingspeedof

graphicsorimagesisquickenedgreatly.Theapproachesmentionedaboveprovideanewkindof

researchmeadsforoompressingcodingtechnologyofoomputergraphics. Keywords:two-dimensiongraphics;linearquadtreecoding;figureprocessing 图形/图像数据结构的研究在地理信息系统

(GIS)中起着重要的作用.目前在GIS中普遍应用

的数据结构是矢量结构和栅格结构,矢量结构主要

应用于地学专题图形数据的拓扑关系处理,栅格(网

格)结构主要应用于图像数据的显示与变换处

理…1.四叉树结构是由栅格结构模式发展起来的一

种层次树的数据结构.由于四又树结构查询速度快,

压缩效果好,可变比例尺等优点,使其在GIS中得

到日趋广泛地应用.在四叉树结构中,结点除了记录

图形的属性值外,还需为其父辈结点和四个子结点

开辟存储空间以建立1:4的关系【2J.如果树的深度

较大且结点较多时,为建立上述关系而引入的指针

字段所占空间是很大的.此外,树中的全部结点占用 的记录数为:(4+1))一1)/3(其中为树的最大 深度),而中间结点占去了(4一1)/3个记录.这些 中间派生值对于应用往往是不需要的.如果图形的 收稿日期:2004—10—15

基金项目:新疆维吾尔自治区自然科学基金资助项目(69662001)

作者简介:付炜(1949__),男,山东青岛人,燕山大学教授,博士研究生导师

第4期.付炜:二维图形数据的线性四叉树编码方法研究 负载量很大,则上述结构额外消耗的空间是不可忽 视的.为克服该缺陷,本文提出一种线性链表的方 法,将二维四叉树映射为一维连续矢量的线性四叉 树.这种线性链表结构省略了父子结点所占用的指 针字段,消除了中间派生结点及其所占空间.试验表 明,该结构对于处理载有大量信息的地学图形数据 是十分有效的J.

1二维图形的线性四叉树编码表示

设给定二维图形为由N×N个像素构成的正 方形图形,且N=2(m?1).对该图形进行四叉树 编码,首先对图形进行西北(NW),东北(NE),西南 (SW),东南(SE)4个象限的相等分割.如果等分后 的象限不是属性均匀的,则对该象限继续上述等分 过程,直至象限完全具有同一属性的叶子组成为止 (图1).如果用自然数序列表示图形的像素排列次 序或逻辑存储地址,则可将二维地址表示转化为线 性四叉树的地址【引.该四叉树在递归形成时将四个 相邻象限的地址物理地排列在一起,而且具有线性 的特点(图2),即M(k+1)=M(k)+C,其中

M(k)为地址,k为下标,C为常数.因上述逻辑地

址的排列顺序与四叉树的后序遍历相一致,故可采

用后序遍历递归分解整个图形.当遍历到叶结点时,

可利用Morton函数以完成地址的线性化.为实现二

维地址到一维地址的线性变换,采用地理索引线性

???

l

_-_-_-

3

_-_-?-

9

?-_-_-

ll

???

???

2

_-_-_-

4

_-_-_-

l0

_-_-?-

l2

???

''?

6;--?

8;-??

4;

--?

6;

图1四叉树结构

Hg.1Structureof

quu.~ttree

编码的原理建立Morton函

数:M=Morton(d,i,), 其中M为线性地址,d为树

的最大深度,,为图形的行

列坐标.为简便计,以树的深

度m=3为例,说明线形四叉

树的编码原理(图3).此时i,

所对应的二进制数分别为:

l23456789l0lll2131415l6 图2四叉树的线性编码

Fig.2Linearcodingofqtmdtree

i?{000,001,…,111};?{000,001,…,111}.对 任一i,,使i,按位交错存储,即从i,的高位 起算,i的第一位紧接的第一位之后存储,.的第 二位紧接i的第一位之后存储,的第二位又紧接 的第二位之后存储,重复上述过程,直到第m位为 止,这样就形成了一个新的地址【5I.例如当i取2, 取1时,生成的地址为000110,其四进制地址为 012.如图3所示,如果用四进制码表示2×2的 图形,则字长为m的线性地址码M可以描述该图 0

0l234567

001l010

003l012

021l030

023l032………

201l210

203l212

221l230

223l232

图3图形数据的四叉树编码示意

Hg.3Sketchmapofquu'~ttreef研graphicdata 形的所有地址.本试验建立了一维数组C[m]来表 示这个地址码M,其中m为数组的上界,其值为树 的最大深度.这里地址M是一个数组元素的有序 集合:M={C[k]lC[k]?{0,1,2,3}},其中下标k ?{0,1,2,…,m}.有序集合c[k]反映了从树根到 结点(或象限)的路径.而元素c[i]值及其在M中 的位置则反映了该结点所在的位置和深度.根据 地址M的上述性质可以很容易地处理属性合并的 情况.如果某深度级的某一象限的所属儿子为同属 性的,则可在该级以下各数字位添加补充位A以表 示属性合并情况.A可以是除了0,1,2,3以外的任 何值.为了与四进制数字统一,这里取A:4.例如 图3中的东南象限是属性均匀的,则用344表示该 象限地址,这样,M的结构就可以反映具有不同深 度的叶结点的物理状况.例如,如果M中不存在补 充位A(此处是4),则该叶结点具有最大深度,其线 度为L×2一(L为整个图形的最大线度).如果M 中存在k个A,则其深度为m—k,其叶结点线度为 L×2一.如上例的地址344就有k=2,则该值表 示在最大深度m=3时该地址在m—k=1级上的 东南象限上为一棵属性均匀的结点.上述算法的程 序设计如下:

,m一一如一一一一一,

-1.1.1.1...1J.-

一0一,2,一,一一一

rr;r._;.??rrr;r;.,?一一加一一一,一,

rrr;r;rrr;r;.,…,,一,川一,,,

,?,一呦,,枷一,,,

100陕西师范大学(自然科学版)第32卷

NodeProcedureLQT(L,z,Y) /*IJ(为线形四叉树子程序;L为树的深度;z,Y为 原始图像数据二维数组的界长,初值为z=Y=O;S[4]

为结点记录数组,分别代表某结点的四个子结点*/ begine

if(L=O){begin

形成叶结点,其中包括属性值C和线性地址 M,通过调用Morton(L,z,Y)实现,返回结点记 录.}end

elsebegin{

L=L一1:

st0]=LQT(L,z一2**L,Y一2**

L);

S【1J=LQT(L,z,Y一2**L);

S【2J=LQT(L,z一2**L,Y);

S【0J=LQT(L,z,Y);

判断四个子结点S[i],如果四个子结点属性相 同返回s[0],否则返回中问结点值.}end;end. 经过地址变换处理的线性四叉树文件与内存中 未经处理的二维数组一般不存在一一对应关系.例 如,给出二维数组的i,地址值,经过变换的M值 不在线性表中,因此需要做相应的处理,这种处理一 般使用分割象限和插补压缩掉的M值.数据组织 成线性表后,可采用B树技术进行大型数据文件的 组织.其方法是首先将原始文件变换成一个线性四

叉树,然后再将它们按照B树的要求组成B树的外 部结点,再使用B树处理内外存数据交换技术以减 少对磁盘的存取次数.这样既达到了虚拟压缩的目 的.又提高了数据处理速度[.

2二维图形四叉树编码的存储结构

2.1链式四叉树编码的存储结构

该存储结构用2个代码表示各结点的特性.即 用定位码表示结点的位置.用层次码表示结点所在 四叉树的层次,层次码反映了结点的深度.以这种方 式编码的四叉树的每一个4分区,其细分格网的编 码具有继承性,即定位码具有可压缩性.将定位码的 每一位用一个结点表示,则该结点仅由2个区域构 成,即由一位四进制数字表示的数字区和指向下一 层数字的指针区.用该编码方式可建立表示四叉树 链式编码的数据结构.链式四叉树编码的特点为: (1)结点结构中,同一分支各结点的定位码前缀数 字相同,且在链式编码结构中是共有的,这使得链式 四叉树编码的总代码得以压缩;(2)在链式结点结 构中,层与层之间的搜索用指针传递,而在同一层各 结点之间的搜索以线性方式进行;(3)在搜索过程 中,由第一层出发到达某个指针为空结点所经历的 各层数字形成的序列为相应线形四叉树结点的定位 码[8I.

2.2一对四式四叉树编码的存储结构

在一对四式四叉树编码中,一个非叶结点有4 个子结点,分别标为0,1,2,3号子结点.对这些结点 对应的区域四等分后形成原图形的4个子图形,按 顺序标为西北(NW),东北(NE),西南(),东南 (SE)4个子图形.该数据结构用5个字段的记录表

示四叉树的结点,其中4个字段用来描述该结点的 4个子结点的属性,另一个字段用来存放指向其子 结点记录位置的指针.这种存储结构要求该结点的 4个子结点对应的记录是按NW,NE,SW,SE次序 依次连续存放的.这种存储结构的一个记录与一个 结点相对应,该记录描述了相应结点的4个子结点 的状态值,而指针则给出该结点的4个子结点所对 应记录的存放位置,且隐含地表示了这些结点存放 的次序.在这种结构中,即使某个记录是不必要的 (如该结点是叶结点),其对应的存储位置也必须闲 置在那里,这样可以保证在存取其他同辈结点记录 时不发生错误,因此会造成存储空间的浪费. 为减少误差和克服存储空间被问隔闲置的缺 点,一个改进的存储结构算法是设计一种紧凑的一 对四式四叉树的编码结构【9I.这种数据结构以增加 计算量来达到节省存储空问的目的,在存取结点记 录之前,首先检查其父辈结点记录,考察在它之前有 几个叶结点,从而确定应如何存取所需结点的记录. 在上述存储结构中增加一些信息可使计算量相应减 少.例如在原记录中增加1个字节,每个子结点对应 2位,表示它的子结点的指针在指向区域中的偏移. 因此要寻找它的子结点的位置.只要将指针指向的 位置加上该偏移值(O,3)再乘上记录所占的字节 数,即得所要求的记录位置.这种方法所描述的记录 结构如表1所示.采用一对四式四叉树存储结构进 行光栅显示器转换时,可简化图形显示算法,减少计 算量.

第4期付炜:二维图形数据的线性四叉树编码方法研究101

表1描述结点的记录结构

Tab.1RecordstructureofIl0dedescription

8bit24bit8bit8bit8bit8bit 1oo00100Pl1202203150420 1001O0o0P2a150b20C20d20 oo0100o0P3e20f150g20h150 O0O0O0o0P4i20j150k150l150 O0O0O0o0A150B150C160D160 O0O0O0o0E150F150G150H160 O0O0O0o0I160J160K160L150 oo00O0o0M160N1500160P160 O0O0O0o0Q160R160S150T160 0oo0O0o0U150V160W160X160 3四叉树编码的光栅扫描图形显示

二维图形的四叉树的编码转换成光栅式扫描图 形显示是地学专题图形由矢量数据结构向栅格数据 结构转换的基础,也是图形/乜日像计算机分析处理的 基本算法.以下给出由C语言编写的上述算法的程 序片段:

qudtree—ast(intm,voidpo) {intY,side;

route—top-bit=1《(m一1);

for(Y=0;<exp(m*log(2));Y++)

{side=exp((m一1)*log(2));

.

Z:pos=150;linescan=Y;scanwalk(IX),side,y);

}}

/*这里po为指针,指向四叉树的第一个记录;m 是光栅显示器的大小,表示为2×2;.~Ypos,

linescan和route-top-bit是全局变量.*/

scanwalk(structpoint,ptrl,intside,introute)

{if(side!=0)

{if((route&route.top-bit=0) {=0;testrecurse(ptll,

(ptr1).a);

(structpoint,ptrl,intside,intway) {intcolor;

intoffset,side,routeh;

structpointptr;

colorway;

if(color<129)

{offset=(((ptr1),offset)>>)&7;nptr=

((ptr1).poi)+offset;

sidel=side>>1;routel=route<<1;scanwalk

(ptr,sidel,route1);}

else

{display(.rpOS,side,linescan,color);.Z:pos=

.

Z:pos+side;}}

display(intz,intS,intlscan,intC); {inti;

for(i=z;<z+S;i++)

{putpixel(i,lscan,C一128);}}

/*上述程序中调用的函数display(z,side,y, eolor)~使位于(z,)和(z+side一1,Y)之间的像

素置上值color一128).*/

side,rou

4二维图形的四叉树编码变换

1;testrecurse(ptll,side,route,(ptr1).b);}4.1图形的缩放 else

{=2;testrecurse(ptll,side,route,

(ptr1),C);

=3:

(*ptr1),d);}}}

testrecurse(ptll,side,route,

/*上述程序中的route参数是不断变化的,当其约 等于2I1时,要取子图形的下半部分*/testrecurSe

用两种方法可对四叉树编码的二维图形进行放 大和缩小.一种方法是基于显示设备的大小为2× 2这一特性,只要改变m值的大小就可以对二维 图形进行缩放处理.如将m值增加1,则可使图形放 大一倍;相应地m值减少1,则图形可缩小1/2.另 一

种方法是利用光栅扫描型图形显示系统中帧存储 器具有灵活的读写性能,可直接产生图形的缩放效

102陕西师范大学(自然科学版)第32卷

果,该方法可避免费时的光栅扫描转换操作.其具体 方法为,利用近景命令Zoom(ixscale,iyscale)读出帧 存储器中的内容并在相邻位置上重复显示图形,即 可使原图形成整数倍放大和缩小.

4.2图形的增删

用四叉树编码数据结构对图形进行增删,其简 单方法是改变叶结点的灰度值.如要删除图形的灰 结点(灰度值为1),则将其变为白结点(灰度值为0) 即可.如要删除整个灰结点,则将其4个子结点均变 为白结点.运用上述方法的逆过程,则可对图形进行

增添.以上方法所用改变叶结点灰度值的技术可由 帧存方式实现.具体方法是将像素的灰度值写入帧 存,其写入值即可改变帧存的内容.写入的模式有涂 层,擦除,取补和取反等【10J.其中擦除模式是用屏幕 背景值写入帧存,从而擦除帧存中的图形;取补模式 是用系统规定的最亮灰度值与帧存中已有的灰度值 之差写入帧存而产生新的图形,如果进行两次这种 写入方式,可恢复帧存中原来的灰度值.在需要暂时 改变局部图形时,这种方法很有效;而取反模式是将 帧存中的原图形灰度值取反,原来背景部分的灰度 值用图形的灰度值显示,而原图形的灰度值用背景 的灰度值显示.

4.3图形的旋转

用四叉树编码数据结构对二维图形进行旋转变 换,其简单方法是改写上述程序中的函数quadtree ,

raster(po,m),并使用一维数组.只要改变一维数组 的值就可使图形旋转不同的角度.

5结语

二维图形数据的四叉树编码数据结构对于地学 空间数据的检索,多要素图形数据的叠置分析,地学 数据之间的空间关系的运算等操作都非常方便,并 可实现地学专题图形的压缩,存储,缩放,增删,旋 转,显示及数字图像的各种逻辑操作.特别当地学专 题图形的图斑较大时,用该编码方法可节省大量的 存储空间.如果图形的栅格矩阵很大,存储和处理整 幅图形很困难时,采用四叉树编码存储方法,可以根 据需要将其等分为4,16,64块等,每块分别进行四 叉树编码存储.需要时,可将它们合并成一棵树,而

合并的方法对四叉树来说是很容易的.例如,如果要 将相邻4块的四叉树合并成一棵树,只要将4块子 图的四叉树当作新树中的4棵子树,4棵子树的根 指向一个共同的父亲,即重新生成一个共同的根结 点.在实际应用中,由于地学图形常常不是2×2 个像素构成的方阵,为了能对不同的行列数的栅格 数据进行四叉树编码,在程序设计时,对不足2× 2个像素的部分以"0"补足.在建树时,对于补足部 分生成的叶结点可不存储,这样存储量不会增加.此 外,考虑到许多地学栅格数据是用游程长度编码方 式存储的,故可直接应用游程长度编码数据建立四 叉树.这样可使地理信息系统中地学图形数据的分 析处理更加简便和快速.

参考文献:

[1]黄杏元,马劲松,汤勤.地理信息系统概论[M].北京:高 等教育出版社,2001.37,50.

[2]付炜.地学专题图形的对象模型研究[J].陕西师范大学 (自然科学版),1999,28(1):101,105.

[3]ShafferC,SametH.Optimal~adtreeconstruction

algorithm[J].ComputerVisionGraphicsandImage

Processing,1987,37(12):402--419.

[4]SametH.Thequadtreeandrelatedhierarchicaldata

s廿uctur[J].ComputerScience,2001,36(10):306, 412.

[5]王汝传.用四叉树对一维图形进行处理的算法[J].南京 邮电学院,1997,17(1):83--86. [6]周洞汝,姜海涛.用于区域表达的线性数字搜索树[J].计 算机辅助设计与图形学,1992,4(3):12,17. [7]谈国新,林宗坚.基于自然数的线形四叉树优化构造算

法[J].测绘,2000,24(3):204--210.

[8]周洞汝,杨荣.线形四叉树的一种改进最优构造算法[J].

计算机辅设计与图形学,1992,4(1):1,7.

[9]SameH.Neghl:x~rfindingtechniques[orimagerepresented byQuadtree[J].ComputerScience,2000,30(10):206-- 217.

[10]JohnL,FredericPS.Computer-basedlandusesuitability mapping[J].TheCartographicJatmal,1983,10(2):256 --

260.

[责任编辑李乃英]

范文四：基于纹理四叉树的快速HEVC帧内编码算法_李晓波

第 40卷 一 第 12期 一 Vol. 40一 No. 12一 计 算 机 工 程

Computer Engineering

一 一

2014年 12月 December 2014

四 多媒体技术及应用 四

文章编号 :1000-3428(2014) 12-0272-05一 一 一 文献标识码 :A一 一 一 中图分类号 :TP391

基金项目 :国家自然科学基金资助项目 (61171163);宁波市自然科学基金资助项目 (2012A 610041); 新一代移动互联网用户端软件科技 创新团队基金资助项目 (2010R 50009)三

作者简介 :李晓波 (1989-), 男 , 硕士 , 主研方向 :视频编码 , 图像处理 ; 彭宗举 , 副教授 二 博士 ; 陈 一 芬 , 副教授 二 硕士 三 收稿日期 :2013-12-04一 一 修回日期 :2014-02-17一 一 E-mail :shakingwaves @163. com

基于纹理四叉树的快速 HEVC 帧内编码算法

李晓波 , 彭宗举 , 陈 一 芬

(宁波大学信息科学与工程学院 , 浙江 宁波 315211)

摘 一 要 :针对高效视频编码 (HEVC ) 中编码单元 (CU ) 进行四叉树递归遍历时间较长的问题 , 提出一种基于纹理四 叉树的快速 HEVC 帧内编码算法 三 采用 Sobel 算子对当前视频图像提取边缘 , 利用最大类间方差法剔除弱边缘并 保留强边缘 三 通过递归方式对边缘图中的每个 64? 64单元建立纹理四叉树 , 使用视频图像的纹理四叉树结构对 CU 最优分割组合进行预测 三 对于不同大小的分割单元 , 无需完全递归遍历所有的 CU 深度 , 从而缩小 CU 搜索范 围 , 节省编码时间 三 实验结果表明 , 与 HEVC 标准算法相比 , 该算法亮度分量的码率平均增加了 0. 50%, 信噪比和 编码时间分别减少了 0. 03dB 和 28. 70%三

关键词 :高效视频编码 ; 帧内预测 ; 快速编码 ; 纹理四叉树 ; 边缘提取 ; 编码单元深度

中文引用格式 :李晓波 , 彭宗举 , 陈 一 芬 . 基于纹理四叉树的快速 HEVC 帧内编码算法 [J ]. 计算机工程 ,2014, 40(12):272-276.

英文引用格式 :Li Xiaobo , Peng Zongju , Chen Fen. Fast Intra Coding Algorithm of HEVC Based on Texture Quadtree [J ]. Computer Engineering ,2014,40(12):272-276.

Fast Intra Coding Algorithm of HEVC Based on Texture Quadtree

LI Xiaobo , PENG Zongju , CHEN Fen

(College of Information Science and Engineering , Ningbo University , Ningbo 315211, China )

? Abstract ? Aiming at high computing complexity of recursive quadtree partitioning of a large Coding Unit (CU ) in High Efficiency Video Coding (HEVC ), a fast intra coding algorithm of HEVC based on texture quadtree is proposed in this paper. The edges of the whole frame are extracted by Sobel operator. The weak edges are removed and the edge map is formed using maximum between-cluster variance method. Then , the texture quadtree is recursively built for each 64? 64of edge map. The texture quad-tree is applied to predict the CU partition combination. For different partition size , full searching all CU depth is avoided. Hence , CU search range is narrowed and the encoding time is reduced. Experimental result shows that the proposed algorithm saves 28. 70%of the encoding time on average , while it only leads to increase 0. 50%Bjontegaard Delta Bit Rate (BDBR ) and decrease 0. 03dB Bjontegaard Delta Peak Signal-to-Noise Ratio (BDPSNR ) for luminance component.

? Key words ? High Efficiency Video Coding (HEVC ); intra prediction ; fast coding ; texture quadtree ; edge extraction ; Coding Unit (CU ) depth

DOI :10. 3969/j. issn. 1000-3428. 2014. 12. 051

1一 概述

随着人们对高清以及超高清数字视频需求的增 加 , 高清以及超高清视频的编码和传输日益成为最 主要的问题 三 因此 ,2010年国际电信联盟视频编码 专家组和国际化标准组织及国际电工委员会运动图 像专家组成立了视频编码联合专家组研究下一代高

效视频编码 (High Efficiency Video Coding , HEVC ) 标准 三 HEVC 是继 H. 264之后的新一代视频编码标 准 , 它主要解决传统 H. 264/AVC 标准的低分辨率和 不能并行处理的问题 , 并在保持相同视频重建质量 的前提下节省 50%的码率 [1]三

HEVC 采用和 H. 264类似的混合编码框架 , 帧 内编码采用基于四叉树结构的编码技术和多角度帧

第 40卷 一 第 12期 李晓波 , 彭宗举 , 陈 一 芬 :基于纹理四叉树的快速 HEVC 帧内编码算法 一 一

内预测 技 术 [2-3]三 HEVC 中 使 用 编 码 单 元 (Coding Unit , CU )二 预测单元 (Prediction Unit , PU ) 和变换单 元 (Transform Unit , TU )3种更灵活的编码元素来描 述整个编码过程 三 相比于 H. 264/AVC , HEVC 编码 复杂度较高 [4], 帧内编码部分的复杂度主要有 2个 方面的原因 :(1)为了提高预测精度 , HEVC 采用比 H 264更多的 35种帧内预测模式 ;(2)HEVC 编码标 准中 , CU 大小可以为 64? 64,32? 32,16? 16和 8? 8三 在编码过程中 , 根据率失真优化准则确定最优 CU 分割组合 三 在确定最优 CU 划分组合的过程中 , 需要进行 341(40+41+42+43+44=341) 次递归过 程 , 完成 11935(341? 35) 次 SATD (Sum of Absolute Hadamard Transformed Difference ) 和 SAD (Sum of Absolute Difference ) 计算 三 为减少编码时间 , 目前已 有很多学者提出了多种解决方案 三 文献 [5]提出从 35种帧内 预 测 模 式 中 粗 选 出 N 个 候 选 模 式 进 行 RDO 计算 三 由于该方案的计算复杂度仍然很高 , 文 献 [6]根据空间相关性的原理 , 利用左边和上边等相 邻 PU 的预测模式 , 进一步减少候选预测模式的个 数 三 文献 [7]通过 Sobel 算子计算的纹理方向来减 少 H. 264帧内候选预测模式的个数 三 文献 [8-10]通 过 Sobel 算子或者梯度算子计算纹理方向来减少 HEVC 的候选模式 三 由于纹理方向和 HEVC 选择的 预测模式之间并不总是一致的 , 因此会给上述算法 带来较大的率失真性能损失 三 文献 [11]认为相邻 LCU (Large CU ) 之间纹理具有延续性 , 当前 LCU 的 编码深度与其相邻 LCU 的编码深度也具有一定的 相关性 , 由此提出了 CU 深度快速判断算法 (Fast CU Size Decision Algorithm , FCSDA )三 该算法未实现对 相邻 LCU 深度的自适应加权 , 同时以 LCU 作为一 个深度的预测整体 , 未实现较小 CU 分割的深度预 测 三 文献 [12]提出基于视频序列时间相关性的快速 HEVC 帧内预测算法 三

目前 , 很少有学者对视频图像的纹理复杂度与 CU 的最优分割组合方式进行研究 三 本文研究了纹 理复杂度与 CU 最优组合方式的关系 , 根据视频图 像的纹理复杂度建立纹理四叉树 , 进而确定 CU 的 最优组合方式 , 减少编码过程中不必要的递归计算 过程 , 从而节省大量的编码时间 三

2一 基于纹理复杂度的快速帧内编码算法 2. 1一 算法思想

在 HEVC 编码过程中 , 通过率失真优化准则确 定最优 CU 分割组合 三 图 1为 Traffic 序列 PU 分割 结果 三 PU 的范围为从 64? 64到 4? 4三 PU 和 CU 的关系为 :当 CU 大小为 64? 64二32 ? 32和 16? 16时 , 其大小和 CU 相同 ; 当 CU 大小为 8? 8时 , PU 采 用 8? 8和 4? 42种预测模式 三 可以看出 , 在视频图 像中纹理丰富的地方 PU 分割较小 , 在平滑区域所采 用的 PU 分割也越大 三 本文算法是基于 CU 分割组 合与视频图像的纹理复杂程度的关系而提出的 三 算 法框图如图 2所示 , 首先对当前视频图像使用 Sobel 算子提取图像中的对象边缘 , 对提取结果通过最大 类间方差方法剔除弱边缘 , 剩下强边缘 三 然后根据 强边缘建立纹理四叉树 , 最后使用纹理四叉树进行 帧内快速编码

三

图 1一 Traffic 序列 PU

分割图

图 2一 快速帧内编码算法

2. 2一 纹理图像的获取

定义变量 f? (i , j ) 表示 (i , j ) 处的边缘强度 , 具体 计算如下 :

f? (i , j ) =

x (i , j ) 2+G y (i , j ) 2(1)其中 , G x (i , j ) G y (i , j ) 分别表示水平和垂直方向 的梯度 , 采用 Sobel 算子来计算 三

G

x (i , j ) =

-101

-202

-101

四 A (2)

G

y (i , j ) =

121

000

-1-2-1

四 A (3)

其中 , A 为以 (i , j ) 为中心的 3? 3窗口的像素矩阵 三 图 3(a ) 为 Traffic 序列第 75帧边缘强度图 三 在 本文算法中 , 通过最大类间方差方法确定阈值来滤 除视频图像中弱边缘 , 保留强边缘 , 为纹理四叉树的 建立奠定基础 三 阈值计算公式为 :

T =argmax

0? k ? L -1

ω0(1-ω0)(μ0-μ1) 2(4)其中 , L 是纹理图像的最大灰度值 ; ω0, ω1分别是纹 理图像中灰度值小于等于 k 和大于 k 的概率 ; μ0是 372

一 一 一 一 一 一 一 计 一 算 一 机 一 工 一 程

2014年 12月 15日

纹理图像中灰度值小于等于 k 的像素的灰度均值 ; μ1是纹理图像中灰度值大于 k 的像素的灰度均值 三 图 3(b ) 为最终的强边缘纹理图 三 可以看出 , 纹理平 缓区域基本被消除

三

图 3一 Traffic 序列第 75帧边缘强度图

2. 3一 纹理四叉树的建立

在本文算法中 , 纹理四叉树是根据边缘提取结 果建立的用于对 LCU 最优分割组合进行预测的一 种四叉树结构 三 图 4(a ) 是一种纹理四叉树的示例 , 该四叉树的根结点对应 LCU , 每个结点有 0或者 4个子结点 三 该纹理四叉树的深度为 5, 分别表示 64? 64,32? 32,16? 16,8? 8和 4? 4大小的分割 三 图 4(b ) 表示该纹理四叉树对应的 LCU 分割

三

图 4一 HEVC 中纹理四叉树的结构

一 一 利用本文提取的边缘图 , 对每个 64? 64单元以 递归方式建立纹理四叉树 , 伪代码具体如下 :

Proc built (d ) {

一 一 一 一 If (d <4and containedge="" (current="" d="">

For (i =1; i <4; ++i="">

built (d +1)

}

其中 , d (0?d <5) 表示纹理四叉树的深度="" ;="" i="" 表示对="" 应深度层次的第="" i="" 个分割="">

如果某分割块内有纹理 丰富区域并且深度层次 d <4, 则对其="" 4个子分割="" ,="" 依="" 次调用该递归过程="">

图 5为 Traffic 序列第 75帧根据算法建立的纹 理四叉树分割图 三 其中 , 每个 LCU 对应一棵纹理四 叉树 三 图中白色区域表示深度为 4二 大小为 4? 4的 分割 三 对比图 5和图 1, 基于纹理四叉树对视频图像 的分割与 HM 标准算法对 CU 的划分基本吻合 三 因 此 , 在本文算法中 , 用视频图像的纹理四叉树结构来 对 CU 最优分割组合进行预测 , 不用完全递归遍历 所有的 CU 深度 (0~4)三 这样缩小了编码过程中 CU 搜索范围 , 节省编码时间 三 具体预测规则为 :

(1)对 64? 64和 32? 32的分割 , 编码时的深 度范围为 0~1三 在建立纹理四叉树时使用最大类间 方差 , 会造成一部分的纹理区域被分割为纹理平缓 区域 三 为弥补最大类间方差错误分割带来的率失真 性能损失 , 对纹理四叉树的 64? 64CU 将采用和 32? 32CU 一样的编码策略 三

(2)16? 16的分割内存在边界 , 编码时的深度 范围为 0~2三

(3)大小为 8? 8的分割内纹理复杂 , 编码时的 深度范围为 0~3三 在深度层次为 3时 , 不需要进一 步对 4? 4的 PU 单元进行预测编码 三

(4)大小为 4? 4的分割一般位于对象边界 , 纹理复杂 , 编码时的深度范围为 0~3三 在深度层 次为 3时 , 需要进一步对 4? 4的 PU 单元进行预测 编码 三

图 5一 Traffic 序列第 75帧纹理四叉树

3一 实验结果与分析

为验证本文提出的快速帧内编码算法的率失真 性能 , 在 HM 11. 0rc 软件平台上采用标准测试中的 帧内高效编码测试环境 [13], 采用 A , B , C , D , E 和 F 6类视频测试序列 , 其中 , A ~E 类视频对应分辨率 分别为 2560? 1600,1920? 1080,832? 480,416? 240和 1280? 720, F 类视频包含 832? 480,832? 480和 1280? 7203种不同的分辨率 三 每个序列测

472

第 40卷 一 第 12期 李晓波 , 彭宗举 , 陈 一 芬 :基于纹理四叉树的快速 HEVC 帧内编码算法 一 一

试 100帧 三 测试实验的计算机 CPU 主频为 3. 30GHz 二 内存大小为 8GB 三 其中 , 编码节省时间是测试算法的 编码时间和标准算法的编码时间之差 , 再与标准算法 编码时间的比值 三 同时为了验证本文算法的有效 性 , 与 FCSDA 算法进行对比 , 实验结果如表 1和表 2所示 三

表 1一 本文算法和 FCSDA 算法 Y 分量的 BDBR , BDPSNR 和编码节省时间对比

类别 视频测试序列

BDBR /%

FCSDA 本文算法

BDPSNR /dB

FCSDA 本文算法

编码节省时间 /% FCSDA 本文算法

A 类

Traffic 0. 040. 330. 00-0. 02-9. 69-29. 47 PeopleOnStreet 0. 060. 300. 00-0. 02-12. 64-29. 54

B 类

Kimono -0. 060. 200. 00-0. 02-1. 49-31. 51 ParkScene 0. 030. 110. 00-0. 00-10. 05-22. 89 Cactus 0. 050. 500. 00-0. 02-10. 89-32. 32 BasketballDrive 0. 040. 940. 00-0. 02-6. 35-48. 11 BQTerrace 0. 090. 32-0. 01-0. 02-13. 44-28. 38

C 类 BasketballDrill 0. 221. 04-0. 01-0. 05-13. 66-29. 66 BQMall 0. 090. 280. 00-0. 02-12. 81-20. 18 PartyScene 0. 030. 170. 00-0. 01-18. 41-9. 47 RaceHorses 0. 020. 210. 00-0. 01-9. 48-24. 08

D 类

BasketballPass 0. 050. 100. 00-0. 01-5. 10-23. 93 BQSquare 0. 040. 210. 00-0. 02-10. 36-12. 08 BlowingBubbles 0. 010. 140. 00-0. 01-6. 99-11. 67 RaceHorses 0. 020. 230. 00-0. 01-8. 62-14. 85

E 类 Vidyo 1-0. 021. 250. 00-0. 06-8. 12-46. 37 Vidyo 30. 080. 560. 00-0. 03-7. 39-37. 78 Vidyo 40. 060. 770. 00-0. 03-7. 73-44. 61

F 类

BasketballDrillText 0. 121. 110. 010. 0513. 5628. 79 ChinaSpeed 0. 050. 850. 000. 0711. 1436. 12 SlideEditing 0. 320. 170. 010. 0216. 3815. 60 SlideShow 0. 061. 170. 010. 103. 9553. 88平均 0. 070. 500. 00-0. 03-9. 92-28. 70

表 2一 算法 U , V 分量的 BDBR 对比 %

序列 类别

U

FCSDA 本文算法

V

FCSDA 本文算法

A 类 0. 20-0. 200. 30-0. 30

B 类 0. 30-0. 100. 30-0. 10

C 类 0. 300. 000. 200. 10

D 类 0. 200. 000. 10-0. 10

E 类 0. 60-0. 500. 40-0. 70

F 类 0. 100. 200. 100. 10平均 0. 28-0. 100. 23-0. 17一 一 表 1为 本 文 算 法 和 FCSDA 算 法 的 码 率

(BDBR ), 信 噪 比 (BDPSNR ) 和 编 码 节 省 时 间 对 比 [14]三 采用 FCSDA 算法 , Y 分量的 BDBR 平均增 加 0. 07%, BDPSNR 平均减少 0. 00, 编码时间平均 节省了 9. 92%三 该算法能够利用相邻 LCU 的编码 深度 信 息 , 减 少 编 码 时 间 三 由 于 FCSDA 算 法 将 LCU 作为一个深度预测的整体 , LCU 下所有的 CU 分割层次没有进行相应深度的预测 , 因此编码时间 减少有限 三

与 HEVC 的标准算法相比 , 本文提出算法中的 Y 分量 BDBR 增加 0. 50%, BDPSNR 减少 0. 03dB , 编码时间平均节省了 28. 70%三 本文算法对 C 类和 D 类序列编码时 , 时间节省较少 , 其主要原因在于 : C 类和 D 类序列分辨率较小 , 纹理比较丰富 , 利用纹 理四叉树对视频图像分割的结果中 , 有更多的 8? 8和 4? 4的分割单元 , 对应的 CU 需要更多的 CU 深 度搜索层 次 , 时 间 节 省 较 少 三 表 2为 本 文 算 法 和 FCSDA 算法 U 二 V 分量的 BDBR 对比结果 三 视频序 列中亮度分量 Y 主要表示场景的亮度信息 , 变化范 围大 二 纹理复杂 , 而色度分量 U 和 V 主要表示场景 颜色的色度和饱和度 , 变化范围窄 二 纹理简单 , 如图 6所示 三 在 HEVC 以及 H. 264/AVC 编码标准中主要 考虑亮度分量 Y 的率失真性能 , 在编码时色度分量 预测单元与亮度分量共享相同的 CU 深度 , 其分割 572

一 一 一 一 一 一 一 计 一 算 一 机 一 工 一 程 2014年 12月 15日

大小是亮度预测单元的 1/2三 本文算法能够减小色 度分量的编码深度 , 降低色度分量的码率 , 由于亮度 分量编码深度减少导致亮度分量残差变大 , 率失真 性能降低

三

图 6一 Traffic 序列第 75帧的 Y , U 和 V 分量

4一 结束语

本文研究了视频图像纹理分布与 PU 分割的关 系 , 提出基于 PU 的快速帧内预测编码算法 三 通过提 取视频图像的纹理 , 对 PU 分割组合进行预测 , 建立 相应的纹理四叉树 , 减少了不必要的递归计算 三 实 验结果表明 , 本文算法能够较准确地对 PU 分割层次 进行预测 , 相比于 FCSDA 算法 , 在对率失真性能影 响较小的前提下 , 节省了 28. 70%的编码时间 三

参考文献

[1]一Sullivan G J , Ohm J R , Han Woo-Jin , et al. Overview of

the High Efficiency Video Coding (HEVC ) Standard [J ]. IEEE Transactions on Circuits and Systems for Video Technology ,2012,22(12):1649-1668.

[2]一Pourazad M T , Doutre C , Azimi M , et al. HEVC :The

New Gold Standard for Video Compression :How Does HEVC Compare with H. 264/AVC ? [J ]. IEEE Transactions on Consumer Electronics Magazine ,2012, 1(3):36-46.

[3]一朱秀昌 , 李 一 欣 , 李 一 杰 . 新 一 代 视 频 编 码 标 准

HEVC [J ]. 南 京 邮 电 大 学 学 报 :自 然 科 学 版 ,2013, 33(3):1-11.

[4]一Schwarz H , Sullivan G , Tan Thiow-Keng , et al.

Comparison of the Coding Efficiency of Video Coding Standards Including High Efficiency Video Coding (HEVC )[J ]. IEEE Transactions on Circuits and Systems for Video Technology ,2012,22(12):1669-1684.

[5]一Piao Y , Min J , Chen J. ISO /IEC JCTVC-C 207-2010

Encoder Improvement of Unified Intra Prediction [S ]. 2010.

[6]一Zhao Liang , Zhang Li , Ma Siwei , et al. Fast Mode

Decision Algorithm for Intra Prediction in HEVC [C ]//Proceedings of Visual Communications and Image Processing. Tainan , China :[s. n. ],2011:1-4.

[7]一Pan F , Lin X , Rghardja S , et al. Fast Mode Decision

Algorithm for Intraprediction in H. 264/AVC Video Coding [J ]. IEEE Transactions on Circuits and Systems for Video Technology ,2005,15(7):813-822.

[8]一Jiang W , Ma H , Chen Y. Gradient Based Fast Mode

Decision Algorithm for Intra Prediction in HEVC [C ]//Proceedings of the 2nd International Conference on Consumer Electronics , Communications and Networks. Piscataway , USA :IEEE Press ,2012:1836-1840.

[9]一Zhang Yongfei , Li Zhe , Li Bo. Gradient-based Fast

Decision for Intra Prediction in HEVC [C ]//Pro-ceedings of 2012IEEE Visual Communications and Image Processing. San Diego , USA :IEEE Press ,2012:1-6.

[10]一Zhang Mengmeng , Qu Jianfeng , Bai Huihui. Fast Intra

Prediction Mode Decision Algorithm for HEVC [J ]. TELKOMNIKA Indonesian Journal of Electrical Engine-ering ,2013,11(10):5703-5710.

[11]一Shen Liquan , Zhang Zhaoyang , An Ping. Fast CU Size

Decision and Mode Decision Algorithm for HEVC Intra Coding [J ]. IEEE Transactions on Consumer Elec-tronics ,2013,59(1):207-213.

[12]一成益龙 , 滕国伟 , 石旭利 , 等 . 一种快速 HEVC 帧内预

测算法 [J ]. 电视技术 ,2012,36(21):4-7.

[13]一Bossen F. ISO/IEC JCTVC-G 1200-2011Common HM Test

Conditions and Software Reference Configurations [S ]. 2011.

[14]一Bjontegarrd G. Calculation of Average PSNR Differences

Between RD Curves [Z ]. 2001.

编辑 一 陆燕菲

672

范文五：自适应四叉树分形图像编码并行算法

Y e R u iso n g L u J ian Zo u Y u ru

(), , , 515036D ep a r tm en t of M a th em a t icsS h an tou U n iv e rs ity S h an tou C h ina

. A bstrac t A p a ra lle l a lgo r ithm fo r th e adap t ive quad t ree f rac ta l im age co d ing w a s p re sen tedE xp e r im en ta l re2

, , su lt s show th a tw ith th e sam e P SN R and a lit t le lo ss o f th e com p re ssio n ra t io th e p ropo sed p a ra lle l a lgo r ithm

, .im p ro ve s th e enco d ing sp eed la rge lyw h ich is abo u t fo u r t im e s o f th e o r ig ina l co d ing’ s

Key words F rac ta l Co d ing Q uad t ree P a ra lle l a lgo r ithm

值域块查找匹配的相似定义域块具有独立性特点, 实

现了一种基于自适应四叉树分块的分形编码并行算 1 引言

法, 并做了相应的数值实验, 结果显示该算法在信噪比

保持不变, 压缩比微弱减小的情况下, 在此的算法的编 80 年代后期, 等人研究了利用分形几何 B a rn sley 码速度显著提高, 为原编码速度的近 4 倍。 学的思想进行图像压缩的方法, 并提出了一种适合图 1 像压 缩 的 分 形 模 型—迭 代 函 数 系 统 。 后 来,T F S

在迭代函数系统基础上, 提出了分块迭代函数 J acqu in 2 自适应四叉树分形图像编码并行算法2 系统, 实现了分形图像压缩的自动算法。利用分形模

型进行图像压缩时, 一幅复杂的图像可以用只占很少 采用自适应四叉树分块编码的递归算法, 把原图

像分为 4 大块如图 1 示。 字节的 参数表示, 因而可以实现很高的压缩比。与IF S

其它图像编码方法相比, 分形编码的优点是在高倍压

缩时仍能实现较好地恢复图像质量, 其缺点是编码速

度太慢。传统的分形编码方法中, 由图像划分出的定义

域块和值域块具有固定的尺寸, 值域块尺寸的调整往

往导致压缩比、信噪比和编码时间 3 个指标的急剧变

动, 很难满足实际应用的需要。90 年代初期, 提 F ish e r 3 出了一种自适应的图像分块方法。 其特点是可以在 图 1 一幅图像被分成四大块保证一定恢复图像质量的前提下尽可能地提高压缩

由于分形编码过程中查找匹配块的各值域块间的无关 比, 但是并没有本质地改善编码的速度问题。

性, 从而 4 大块中每块的分形编码过程相互独立, 可并 在 F ish e r 自适应分形编码方法的基础上, 针对各行运算。

考虑一个简单的分形编解码过程: 对编码过程, 首 ?

() ( ) Ξ 数学天元基金 0324649和广东省自然科学基金资助项目 032035。 A

( ) ( ) 先, 按上述算法 4 块图像数据、 、, 、K 并行编码, 产 I ?3计算机 1 收到所有数据包后, 合并生成编码数据

( ) 生 4 块分形编码数据设为, , , , K ; 然后,文件。 在上述环境下, 用 算法和并行算法分别对I ? Q Q Q Q F ish e r

() 4 块编码数据合并= I + ? + , + K 输出,2563 256 的 8 位灰度图像和做了实验比较。 Q Q Q Q Q L ena D o g 生成整幅图像的编码数据文件。对解码过程, 只需按顺序从 在并行算法编码时, 对 2563 256 的 8 位灰度图像, 给定每

个数据包的包头长度为 16。 表 1 给出了图像在 b it sL ena 编码数据文件读出数据进行解码即可。但是, 在分形编码过 () 信噪比分别为 29. 16和 32. 18时两种算法 P SN R dB dB ( ) 程中, 为了尽量提高压缩比, 编码参数以“位”为单位 b it 的编码时间及压缩比的比较。表 2 给出了对图像在信 D o g 来存放, 而 语言读?写内存或文件的最小单位为“字节”C () 噪比分别为 32. 42和 33. 09时两种算法的 P SN R dB dB ( ) 编码时间及压缩比的比较。 , 因而可能各编码数据块出现在尾部字节有未满情 by te

表 1 ( ) 况如图 2。在这种情况下, 若仍然按上述方法 4 块编码数

据简单合并, 解码器将把各块间的空闲位当做有用数据, 从

而解码无法成功。 ( )( ) 编码时间 编码时间 ss算法压缩比压缩比

算法 5. 0 9. 106: 1 27. 2 4. 107: 1 F ish e r

并行算法1. 4 9. 093: 1 6. 9 4. 104: 1

表 2

图 2 分形编码一个数据包的结构 ( ) ( ) 算法 编码时间 压缩比 编码时间 压缩比ss( 为解决上述问题, 在编码过程, 我们为每块I 或? 或

) , 或K 编码产生的数据以包的形式在内存存放, 包头根 算法 3. 8 10. 508: 1 8. 9 6. 924: 1 F ish e r

1. 1 10. 429: 1 2. 4 6. 919: 1 并行算法据图像大小用一给定的足够位数用于存放该包的有效数据

( ) 长度数据长度以“位”为单位。 4 个数据包合并即生成编

码数据文件。对解码过程, 首先, 按给定位数读出第 个数 I

据包有效长度; 接着读该数据包有效数据, 并统计所读的长

() ( 度“位”为单位; 当第I 个数据包读完统计长度= 包头

) 记录的有效长度, 跳过第 包尾部的空闲位, 按给定位数 I

读第 个数据包包头数据, 进行第 个数据包解码; 如此 ??

下去, 直到解码完成。

图 4

() () ()为 原图像; 、分别为aD o g b c

为 32. 42 和 33. 09 的 解码图像P SN R D o g

从上述对 和 图像的实验结果可知, 由 L ena D o g 3 并行算法的实现及实验结果

于增加 4 个数据包的包头使压缩比微弱下降的情况

下, 采用并行算法的编码时间约为 算法时间的F ish e r 本文在 4 台 , 450 环境的局域网内模拟了该分 P

14, 从而大大缩短了编码时间。? 形编码并行算法, 实现的基本模型如图 3。

参考文献

. . . . : 1 M FB a rn sleyF rac ta ls eve ryw h e reSan D iegoA ca2

, 1988.dem ic P re ss

. . . 2 AEJ acqu inIm age co d ing ba sed o n a f rac ta l th eo ry o f

. ite ra ted co n t rac t ive t ran sfo rm a t io n sIE E E T ran sac t io n s 图 3 分形编码并行算法实现模型, 1992, 1: 18, 30.o n Im age P ro ce ssing

在计算机 1、2、3、4 分别计算图像块 、 、, 、K , I?. . : 3 YF ish e rF rac ta l im age com p re ssio nth eo ry and app li2

其简要过程为:2. : . 1995.ca t io nN ew Yo rkSp r ingV e r lag

叶瑞松. 快速四叉树分形图像压缩算法. 中国神经网络与 ( ) 1计算机 1 向计算机 2、3、4 发出开始运算指令 4 信 号 处 理 学 术 会 议 论 文 集. 北 京: 电 子 科 学 出 版 社, 后, 并自己开始计算图像块 ; I1999: 339, 342. () ( ) 2计算机 2 3 或 4计算完成, 编码数据包返回

为计算机 1;

转载请注明出处范文大全网 » 四叉树编码