四叉树阵列

2024-06-20

四叉树阵列（精选5篇）

四叉树阵列篇1

在数控加工仿真中,工件的几何建模方法直接影响着仿真精度和速度,合理的工件建模方法不仅能够高速地仿真加工过程,而且可以精确地反映加工表面的细节,保证铣削仿真过程的高效性和仿真结果的可用性。

国内外众多学者对加工仿真中的工件建模方法进行了深入的研究,建模方法可分为图像空间法、实体造型法和离散法3类。图像空间法是利用图像空间的像素属性设置来表示加工过程,如Hook[1]提出的Z-Buffer法。该建模和仿真方法算法简单,易于实现,但视向固定,精度较低。实体造型法是通过刀具沿加工轨迹运动形成的刀具扫描体,与工件直接进行布尔差运算来实现材料的去除过程仿真,如Sungurtekin和Velcker[2]利用基本体素之间的集合运算仿真加工过程。该建模方法精度高,但算法复杂,效率较低。离散法是将工件按照一定的精度进行离散处理,并以此为基础展开求交运算,受到普遍的关注和应用。如Chappel[3]基于点-矢量模型,提出的离散矢量求交法;Navazo[4]将空间递归八等分,提出了八叉树建模方法;Hsu和Yang[5]基于Z-map数据结构,将工件离散成小四棱柱的集合,提出了适于三轴铣削仿真的方法;Chonglin Liu[6]提出了扩展的四叉树结构的建模方法;S.Q.Liu[7]将层次细节(LOD)思想引入到三轴铣削仿真建模方法当中,采用四叉树模型,提出了一种均匀自适应网格小样抽取算法等。该类方法存在仿真精度和仿真速度的矛盾。

但针对仿真精度和仿真速度矛盾的工件仿真建模方法依然是研究的热点。本文集成了单元离散法和四叉树表示方法的优点提出了四叉树阵列工件建模方法,并进行了相关技术的研究,以改善三轴铣削仿真的效率。

1 四叉树阵列结构原理

四叉树作为一种层次化的数据结构,能够动态控制面片的密度,优化加工表面。四叉树阵列是将表面区域离散为若干小区域后再以四叉树表示,形成四叉树阵列的“森林”。对比用单棵四叉树表示加工表面,阵列中四叉树的层次被降低,减小访问路径和仿真耗时,提高了仿真效率,如图1所示。

1.1 单元离散表示法

单元离散模型是将工件上表面按仿真精度均匀地离散成点阵进行表示,离散点的高度值由数组纪录。加工仿真时,沿刀具路径不断修改上表面点阵的高度值,实时更新和构造上表面并渲染,模拟材料的去除过程。该模型数据结构简单,数据访问、修改速度快,但仿真速度在很大程度上决定于仿真精度。

1.2 四叉树模型

在模型表示中,一个正方形区域被均匀地细分为4个子正方形区域,分别对应4个子节点,每个子节点按此规律进一步细分。这样区域被递归细化,直至满足要求的离散精度为止,表示为四叉树结构。该模型实现不同细节的表示,数据量小,但当模型层次过高时,访问速度明显降低。

在构造四叉树过程中,需要考虑到以下两点:(1)细化表面时,必须消除不同分辨率的网格之间裂缝;(2)在区域内,过于细化的网格需要实时合并,即表面优化。详细内容请参考文献[7]。

1.3 四叉树阵列

如图2所示,工件表面首先被均匀分割为若干小正方形区域,每一棵四叉树管理一个小正方形区域。仿真前,四叉树以根节点的形式存在;仿真过程中,随着离散点高度值的改变和加工表面的递归细分,四叉树不断生长。同时,根据离散点的高度值需对节点进行合并,四叉树被剪枝;最后逐棵遍历四叉树及其节点,输出三角面片描述优化后的加工表面。合理地确定阵列划分可降低四叉树的层次,降低数据量和仿真中的计算量。

2 算法

2.1 数据结构

对于一个尺寸已知的工件,根据仿真表面的特点设定的四叉树阵列进行划分。然后根据给定的仿真精度对工件上表面进行离散,用若干离散点表示,开辟一个离散点数组array,按一定顺序存储离散点数据。本文离散点数据结构point主要包括高度值Z和标志值flag(标示该离散点是否用于构造三角面片)。在仿真加工过程中,程序根据四叉树节点中离散点的坐标直接访问array数组,获得离散点信息。

图3为四叉树节点的网格模型,对应的节点数据结构如图4所示。child[4]分别指向4个子节点;num代表该节点单元的的序号;pt[9][2]用于存储节点内9个离散点在网格中的索引坐标(x,y);vertex_flag[9]用于标识离散点是否被选作三角面片的顶点。在表面优化过程中,所有节点按序号的大小,形成一条链表,parent指向该节点的父节点,prev指向该节点的前驱,next指向该节点的后继。四叉树阵列将四叉树根节点按阵列顺序存储在node类型的二维数组ppp中。

2.2 基于四叉树阵列的铣削仿真过程实现

三轴铣削加工仿真算法的流程如图5所示,加工区域细化是加工仿真中工件模型表示算法核心,主要由函数luminate()的递归调用,函数L()和luminate()的相互调用来完成。函数L()通过离散点的位置确定需要细化的区域,即需进一步细化的四叉树节点。函数Luminate()用于将指定正方形区域细化,生成节点,构造三角面片。为避免裂缝的产生,根据节点内相关离散点所在的位置,继续细化其它正方形区域,直到满足精度为止。四叉树的深度level与阵列划分精度和仿真精度相关,可通过判断节点层次n是否到达四叉树的深度level来判断细分过程是否满足精度要求。L()和luminate()函数中的参数ppp指向四叉树阵列,p指向将细分的正方形区域。luminate()函数开始调用时,p为四叉树的根节点。两函数的执行过程如图6、图7、图8所示。

2.3 工件表面的动态优化

表面优化的目的就是在局部的加工区域细化后,对过于细化的网格进行合并,在一定的精度条件下,用最少的节点单元精确表达加工表面。优化过程将阵列中的每棵树都变成双向链表,从链表的尾节点开始朝根节点方向,对每个节点进行判断或删除操作,实现网格的合并,优化加工表面。

3 建模方法性能分析

毛坯的上表面尺寸为512mm×512mm,工件表面的离散精度为1mm,球头刀的表示误差为0.06mm,采用三轴铣削方式进行粗加工,依次用球头刀、立铣刀进行曲面、平面和孔加工,铣削仿真在一台双核2.11GHz处理器,1.00GB内存,GeForce8500GT显卡的PC机上进行,改变阵列测试本文提出的工件建模方法的性能,仿真结果如图9所示,测试数据如表1所示。

图10是仿真测试的总节点数变化曲线,曲线可划分为AB、BC和CD三段。AB段对应球头刀加工圆弧面的过程。圆弧曲面需要大量的小三角面片来逼近,随着刀步数的增加,节点总量和三角面片总数呈线性趋势。BC段对应平头刀铣平面的过程,加工区域的小三角面片合并为大三角面片,高分辨率节点被清理掉,所以节点增加量很小,节点总数趋于稳定。CD段对应于平头刀孔加工的过程,孔的底面作为平面,由大三角面片表示,孔的边缘由小三角面片表示,节点数量增长呈非线性。

图11的横坐标阵列规模指数N对应于阵列中四叉树总量4N。当阵列的规模较小时,对应的四叉树的层次很高,离散点逐层进行子区域递归细化和访问,耗时较大,降低了帧速率。随着阵列规模的增长,四叉树层次降低,细分操作的耗时减少,帧速率显著提升。而阵列规模过大,仿真耗时反而增加,其原因在于阵列的规模。

4 结论

文章提出了四叉树阵列结构,并给出相应的数据结构,设计出动态的几何建模算法,详细介绍了算法的流程。通过对算法性能对比分析,四叉树阵列结构在仿真效率方面优于单棵四叉树结构。阵列划分存在最优值,仿真效率达到了最高,可同时提高仿真精度和效率,满足了三轴铣削仿真实时性要求。

摘要：为了提高三轴铣削图形仿真的效率,提出了四叉树阵列结构,研究了适用于三轴铣削实时仿真的动态建模方法。该方法集成了单元离散法和四叉树表示工件模型的优点,在整体上工件模型采用单元离散法表示,细节上采用四叉树表示,即每个单元就是一棵四叉树结构体。该建模方法对于给定的精度,根据不同区域几何特征的差异,可自动地调节四叉树表示的层次,既增强了工件模型关键细节特征的表达,又降低了数据量和计算量。通过对比分析,该方法可在保证仿真精度的前提下显著提高仿真效率。

关键词：三轴铣削仿真,四叉树阵列,几何建模,仿真速度,仿真精度

参考文献

[1]Hook T V.Real-time Shaded NC Milling Display[J].Computer Graphic,1986,20(4):15-20.

[2]Sungurtekin U A,VelckerH B G.Graphical simulation and automatic verification of NC machining programation[J].IEEE Transactions on Robotic and Automation,1986(4):156-165.

[3]Chappel L T.The use of vectors to simulate material removed by numerically controlled milling[J].CAD,1983,15(3):156-15.

[4]Navazo,Ayana A D,Brunet P A.Geometric modeler based on the exact octree representation of polyhedra[lJ].Computer Graphics Forum,1986,5(2):91-104.

[5]Hsu P H,Yang W T.Real-time3D simulation of3-axis milling using isometric projection[J].Computer-Aid Design,1993,25(4):215-224.

[6]Liu C L,Esterling D M,Fontdecaba J,Mosel E.Dimensional verification of NC machining profiles using extended quadtrees[J].Computer-Aided Design,1996,28:845-852.

[7]LiuSQ,KongS,ChenYP,NeeAYC.Real-time,dynamiclevel-of-detail management for three-axis NC milling simulation[J].Computer-Aided Design,2006(38):378-391.

四叉树阵列篇2

道路在使用过程中, 由于行车荷载和自然因素的作用, 将使路面逐渐产生各种破损, 有些损害需要及时修补和养护。国际上将图像处理技术应用于路面损坏的自动检测和评价起始于20世纪80年代中期。西方发达国家由于路网管理和路面管理系统发展的需要, 纷纷开展了以路面损坏实时采集设备 (硬件) 和路面损坏图像的计算机图像自动处理系统 (软件) 为主要内容的研究与开发工作。路面数字图像的损害检测和评估发展了这么多年已经做了相当多的研究, 但迄今为止还没有达到能够识别所有路面所有损害类型。但是针对几种主要的损害类型还是有一些识别率较高的方法, 主要的损害可分为:修补、裂缝和龟裂 (包括块裂) 。这几种损害的区别体现在色块和分布状况上。从目前的研究来看, 更多的工作集中在路面损害的检测, 而损害评估方面的研究比较少。

从20世纪80年代开始, 自动路面损害检测评估系统就已经开始出现, 随着计算机技术和图像处理技术的发展, 使得基于数字图像处理的路面监测和评估成为可能, 如澳大利亚交通研究局 (ARRB) 的MCDI系统。后来的计算机辅助半自动损害识别评价系统通过一些图像处理算法进行损害识别, 提高了系统板自动化水平[2]。这些算法的基本目的是从一个二值图像中获取裂缝特征。二值图像获得的方法主要分两类:一类是基于图像边缘检测, 将检测到的边缘设为白色, 其他背景色素设为黑色;另外一类是基于图像分割。在道路损害监测和评估中图像分割方法最常用的是阈值分割, 通过确定一个最佳阈值来得到, 小于阈值的认为是裂缝, 设为白色像素, 大于阈值的认为是背景, 设为黑色像素, 从而提取出裂缝。该方法可以适用于较为明显的裂缝类和龟裂和块裂, 但得到的结果不是很准确, 尤其是对于细裂纹的道路损害, 往往无法得到这样一个阈值来进行分割。

基于边缘检测的方法适合比较明显的条状裂缝, 而基于图像分割的方法, 是针对于大面积损害或者是路面状况理想的情况下的道路损害图像。早期使用不同的边缘检测的方法来对路面损害进行检测和评估, 例如文献[3]利用Sobel算子边缘检测改进了文献[5]提出的最小误差阈值法, 将具有小于一定阈值周长的像素群归结为噪声群, 通过此方法去除噪声, 同时连接离散裂缝段来构造连续的目标像素群;文献[4]采用骨骼化分析算法进行裂缝的检测, 根据形态学图像处理技术得到图像的骨骼, 然后根据图像骨骼间的拓扑和几何关系对裂缝进行检测分类。尽管这些方法在一定程度上解决了一些问题, 但是当路面损害图像不是很理想的情况下, 这些方法的准确性就不是很理想。因此, 研究者将更多的重心放在了基于图像分割的方法上, 特别是基于阈值分割的方法, 而阈值的获得有两个比较经典的方法:Otsu[6]自适应的阈值确定的方法和Kapur[7]最佳熵自动阈值法, 在这两个方法的基础上提出了一些新的求阈值的方法, 如文献[5]提出的最小误差阈值法, 该方法基于贝叶斯误差理论, 在假设理想的目标和背景的灰度分布服从混合正态分布的前提下, 经过合理的处理得到阈值分割表达式取得最小值, 然后根据该值进行阈值分割。

本文提出的基于四叉树分离合并的道路损害评估的方法是基于边缘检测方法, 但该方法不仅适用于裂缝类的道路损害, 同时也适用于龟裂或者块裂类的道路损害。

2 图像处理基础

2.1 基于区域的分割

令R表示整幅图像区域。可以将分割看作将R划分为n个子区域R1, R2, …, Rn的过程:

(a) $\cup_{i = 1}^{n} R_{i} = R$ 。

(b) Ri是一个连通的区域, i=1, 2, …, n。

(d) P (Ri) =TRUE, 对于i=1, 2, …, n。

(e) P (Ri∪Rj) =FALSE, 对于i≠j。

这里, P (Ri) 是定义在集合Ri的点上的逻辑谓词, Ø是空集。

2.2 基于四叉树的区域分离与合并

四叉树分离[1], 令R表示整幅图像区域并选择一个谓词P。如图1所示, 对R进行分割的一种方法是反复将分割得到的结果图像再次分为四个区域, 直到对任何区域Ri, 有P (Ri) =TRUE。这里是从整幅图像开始。如果有P (R) =FALSE, 就将图像分割为四个区域。对任何区域如果P的值是FALSE, 就将这四个区域的每个区域再次分别分为四个区域, 如此不断继续下去。而这种分割的方法用所谓的四叉树形式表示最为方便, 树的根对应于整个图像, 每个节点对应于一个再分为四个后代节点的节点分支。

四叉树合并[1], 将分离的结果合并, 只要求合并邻近区域, 组合的像素满足谓词P, 即仅当P (Rj∪Rk) =TRUE时, 两个邻近区域Rj和Rk才会合并。

2.3 骨骼化

骨骼化[1]是一种将二值图像中的对象简约为一组细骨骼的方法, 这些细骨骼仍保留原始对象形状的重要信息。集合A的骨骼化S (A) 的过程: (1) 如果z是S (A) 的点并且 (D) z是在A内以z为中心的最大圆盘, 则不存在位于A内的能包含 (D) z的更大圆盘 (不一定以z为中心) 。圆盘 (D) z就叫做最大盘。 (2) 圆盘 (D) z在两个或更多的不同位置上与A的边界接触。A的骨骼可以用形态学的腐蚀和开操作表达: $S (A) = \cup_{k = 0}^{Κ} S_{k} (A)$ 其中Sk (A) = (AΘkB) - (AΘkB) °B。

这里B是一个结构元素, (AΘkB) 表示对A的连续k次腐蚀, 第k次是A被腐蚀为空集合前进行的最后一次迭代。图2显示基于集合A的骨骼化的过程。

骨骼化后经常会产生无关的短“毛刺”, 可以通过修剪方法清除 “毛刺”, 这里关于修剪的方法不再细述。

3 基于四叉树分离合并的评估方法

3.1 传统的路面损害评估方法

对于路面损害的评估, 主要针对于以下两种类型:

(1) 线损害主要是裂缝类的损害, 针对于该类损害主要是估计裂缝的长度和宽度, 通常使用的算法[9]步骤如下:

① 对图像平滑去噪;

② 利用Sobel算子或者Canny算子边缘检测;

③ 将得到的边缘图像膨胀;

④ 骨骼化后去处毛刺和孤立点统计得到裂缝的长度, 并根据骨骼化过程中的迭代次数来估计裂缝的宽度。

该方法主要的缺点是, 仅仅使用膨胀的方法不足以将离散的裂缝段连续起来, 特别是长裂缝中的细微裂缝部分往往被当作噪声处理掉;其次由于路面有着高度的纹理化和受到不同强度光照的影响, 所以在图像中就会存在大量的对结果产生影响的噪声, 这些噪声从图4 (e) 可以看出。

(2) 面损害主要是修补龟裂类或者块裂的损害, 针对于该类损害主要是估计损害所覆盖的面积, 通常使用的算法[9]步骤如下:

① 对图像平滑去噪;

② 通过直方图求得图像分割的阈值, 主要包括Otsu[6]自适应的阈值确定的方法和Kapur[7]最佳熵自动阈值法;

③ 根据阈值进行分割, 得到损害的面积。

同样由于噪声的影响, 导致基于图像分割的方法对于高质量路面图像的处理的困难, 如图3 (b) 所示, 虽然图像经过了增强操作, 但是图像底部的阴影还是被错误地估计为损害面积, 实际损害面积只为估计值的40%。

3.2 基于四叉树分离合并的方法

针对传统方法对于线性损害估计所碰到的问题, 本文在此基础上做了进一步的处理, 使用四叉树分离合并的方法之后再进行骨骼化, 而针对使用阈值分割进行面损害估计所碰到的问题, 本文同样使用边缘检测的方法, 这样可以有效地解决传统方法中噪声影响大的问题。本文四叉树分离合并使用8×8区域为最小四叉树区域Ri和谓词P ({Ri|Mmin<mi<Mmax&&Dmin<di<Dmax}) =TRUE对图像进行分离, 符合谓词条件则将该区域设为白色, 否则设为黑色;然后进行合并, 得到合并后的N1个区域R′, 根据每个区域R′i所对应的原始图像的平均灰度和所包含的像素点个数确定该区域是否为噪声点。

$m_{i} = \frac{1}{n} \sum_{j = 1}^{n} s_{j} (s_{j} \in R_{i})$ (1)

$d_{i} = \sqrt{\frac{1}{n} \sum_{j = 1}^{n} (R_{j} - m_{i})^{2}} (s_{j} \in R_{i})$ (2)

(1) 图像预处理

它包括两个过程:图像降噪和图像增强。本文使用维纳滤波对图像采集过程中产生的随机噪声进行处理, 然后组合形态学top-hat变换和bottom-hat变换[1]对图像进行增强操作, 该操作能明显使得阴影的细节得以增强。

(2) 边缘检测

由于路面图像的复杂性和细裂纹的存在, 所以使用Sobel算子进行边缘检测, 这样能保留大量的裂缝的细节, 同时也产生了大量的噪声。

(3) 降噪

由于边缘检测产生的图像中大量的离散边缘既有可能是噪声, 又有可能是龟裂或者块裂的裂纹, 如何将裂纹和噪声区别开来是路面损害系统性能好坏的关键。由于道路损害图像中离散的裂纹相对比较接近, 所以可以通过使用多次膨胀使得一些离散的裂纹连接起来, 然后将膨胀后的结果进行骨骼化, 这样在保留了已有连通裂纹的情况下使得离散的噪声点孤立, 通过设定的阈值和原图像像素灰度值可以将绝大多数的噪声点消除。

(4) 基于四叉树的区域合并与分割

选择所有满足谓词的四叉区域都将用1填充, 并且它们的连通性很容易检测出来, 这样可以达到邻近象限区域的期望合并, 不满足谓词的四叉区域均用0填充, 从而产生一幅分割的图像。这样得到的结果, 除了可以通过 (5) 进行损害的估计之外, 还可以作为掩模来提取原图像中感兴趣的道路损害。

(5) 损害估计

根据不同的路面损害进行评估, 对于裂缝类损害将结果再一次骨骼化后统计白色像素点的个数, 由此可以计算出裂缝的长度, 对于龟裂或块裂类损害, 可以直接通过统计像素点的方法来估计出损害面积。

4 实验结果

利用本文所提出的方法, 对400余幅三大类路面损害图像分别进行了损害评估。

图4 (a) 是裂缝类原始图像;图4 (b) 是原图像经过预处理后的效果, 可以看出裂缝特征得到了明显的增强;图4 (c) 是使用Sobel算子对图4 (b) 进行边缘检测后的效果, 可以看出边检检测产生了一部分噪声;图4 (d) 和图4 (e) 分别是膨胀和骨骼化后的效果, 可以看出膨胀使得离散的边缘连通, 骨骼化虽然去除了部分噪声但是效果并不是很好;将骨骼化后的图像使用四叉树分离和合并算法 (本文中四叉树最小维数是8) 得到图4 (f) , 可以明显看出离散的噪声被去除, 得到的结果非常理想, 为了清楚起见, 图4 (f) 中的裂缝已经加粗。

图5 (a) 是龟裂类原始图像;图5 (b) 是原图像经增强后;图5 (c) 是使用Sobel算子对图5 (b) 进行边缘检测后的效果, 裂纹的大量细节被保留;同样图5 (d) 和图5 (e) 分别是膨胀和骨骼化后的效果;图5 (f) 可以明显看出离散的噪声被去除, 得到的结果非常理想。

表1是对400幅图平均损害估计错误率 (错误率= (|估计面积-实际面积|/实际面积) ×100) 本文方法与传统方法的比较, 从表中可以看出可以看出在对于线损害保持稳定错误率的同时, 对于面损害估计的性能有了显著的提高, 特别是龟裂类的损害。

5 结论与讨论

本文提出了一种基于四叉树分离合并评估道路损害的算法。通过与经典的路面损害评估方法的比较和不同道路损害类型的实验可以看出, 该算法对于裂缝类的道路损害能有效地去除噪声点, 对于龟裂或块裂的道路损害能有效地估计出损害面积。

本文的工作仍有不足, 尤其是对于裂缝类的检测。未来的工作包括将四叉树分离合并后的结果进一步提取特征, 通过有效的分类器自动得到损害的类型, 从而可以达到自动进行检测和评估。

摘要：道路损害的自动评估是计算机视觉研究领域的一个难点, 因为各种道路的颜色、纹理和光照各不相同以及数据采集的时间不同, 所以这些对于评估结果影响特别大。虽然路面损害边缘检测的方法对于光照、纹理等还是相对敏感, 但比图像分割方法受到的影响要小得多, 如果对于原图像进行多次滤波处理, 能有效地增强路面损害, 提高自动评估的精度。在传统的道路损害评估方法的基础上, 提出了四叉树分离和合并的方法, 进行一系列处理后对图像边缘检测、骨骼化和四叉树分离和合并, 然后得到评估的结果。并对不同类型的损害进行了实验, 实验结果表明, 该算法不仅仅能应用于裂缝类的路面损害, 同样能应用于龟裂或块裂类的路面损害, 并且评估的精度相对较高。

关键词：道路损害,边缘检测,骨骼化,四叉树分离合并

参考文献

[1] Rafael C Gonzalez, Richard E Woods, Steven L Eddins.Digital Image Processing Using MATLAB.Pearson/Prentice Hall, 2005.

[2] Pynn J, Wright M, Lldge R.Automatic identification of cracks in road surface[C]//Proceedings of the 7th IEEE International Conference on Image Processing and its Applications.University of Manchester, July 1999.

[3]Li L, Chan P, Rao A, et al.Flexible pavement distress evaluation usingimage analysis[C]//Proceedings of the Second International Confer-ence on Applications of Advanced Technologies in Transportation Engi-neering, 1991.

[4] Cheng H D, Miyojim M.Automatic pavement distress detection system.Journal of Information Sciences, 1998.

[5] Kitter J, Illingworth J.Minimum error thresholding.Pattern Recognition, 1986 (1) .

[6] Otsu N.A Threshold Selection Method from Gray-Level Histogram.IEEE Transaction on Systems, Man and Cybernatics, 1979, 1:62-66.

[7]Kapur J N, Sahoo P K, Wong A K C.A New Method for Gray-LevelPicture Thresholding Using Entropy of the Histogram.Computer Vi-sion, Graphics, and Image Processing, 1985, 29:273-285.

[8]Li Qingquan, Liu Xianglong.Novel Approach to Pavement Image Seg-mentation Based on Neighboring Difference Histogram Method.Imageand Signal Processing, 2008, CISP 08, Congress on.Sanya, 2008.

四叉树阵列篇3

关键词：四叉树复小波,自适应图像,算法,去噪,方向性

0 引言

图像受到污染的原因主要是在传输过程中难免会受到其他未知因素的干扰，结果一般都是会被噪声污染。因为在图像后期处理中必须做去噪处理，最经典的图像去噪方法是以最小二乘估计为基础的，这种算法的缺点是各方向的扩散性太强，虽然也能有效地处理噪点，但是图像保真能力很不理想。

在目前的图形处理中，因为噪声干扰过的图像是一个很大的调整，也是目前图形处理的重要研究课题。而小波的利用就可以很好地解决这一问题，这是因为小波自身的多分辨特性决定的，目前这些技术已经广泛应用于图形去噪处理中，但是缺点也颇多。在小波去噪的发展进程中，基于四叉树复小波的自适应图像去噪是目前图像处理领域的最新技术，也是应用最频繁的技术。小波通过对图形图像的分解，在小波系数上显示主要应对的图像信号高频技术的方法就是四叉树复小波的自适应图像。

通过对受噪声污染的图形的噪点聚类分析图像中的噪点分布，这也对图形的去噪处理影响很大。相对于四叉树复小波相似的小波压缩零树算法在算法上也有很大的提高空间，这也需要先提高四叉树复小波的算法来进一步抑制噪声在图形中的干扰作用。避免在实际操作中因为噪声干扰造成的图像灰度级丢失、清晰度非常不理想的情况。噪声点的聚类分析处理对图形的压缩量很大，例如对于小波压缩零树算法指出，零树算法还有待进一步地发展，算法性能的提高还可望通过抑制噪声来达到在实际应用中。

1 目前图像去噪的发展现状和趋势

图像去噪主要是指通过滤波模型和传统滤波对已知受噪声污染的图像去除受噪部分，整个去噪处理的过程也仅仅是整个图像分析的初级预处理阶段。在隶属于数字图像中的图像恢复的领域，对图像处理具有非凡的意义。

这个图像处理领域的开端可以追溯到上世纪的六十年代，当时的图像处理也是仅仅出于提高图像质量的阶段，如今的图像去噪是深层次深化的产物。当时的图像增强不考虑图像降质这一因素，而今的图像去噪要求轮廓清晰、细节明显，这也是提高图像处理质量的表现。而噪声处理关系到图像的整体质量、边缘检测和特质提取等多部过程的后期处理效果。图像去噪技术的发展是就是要抓住噪声频谱的分部规律和特征的掌控，在去噪技术的发展进程中，开发了各种各有的去噪方法。比如利用均值滤波器去除高斯噪声法、中值滤波器去除脉冲噪声法、矢量中值滤波器法等等，这些方法都是基于相似的小波的滤波器。

如今随着科技的发展，根据噪声的新特点也研究出了具有频谱针对性的去噪方法，如基于四叉树复小波的基于噪声的自适应阈值法，它是根据Mallat经典算法，在方向选择上解决了对平移的依赖，与对一般的复小波的分解和重构的能力很强，可以通过对信号的限制输出来满足重构的条件。基于四叉树复小波的自适应法在更高层的图像去噪处理中除了保留了其他复小波的优点外，还具有完全重构的优势。首先通过对图形的奇偶数进行从长到短的排列变换，再对偶数进行采样分析，在滤波中得到行列的滤波。在Mallat算法的指导下，可以对图形进行低频分解，这就是基于四叉树的重构变换的能力。

2 自适应图形去噪特点

在四叉树复小波中的自适应去噪是通过对冲击滤波器的联合和非线性各向异性扩散滤波器来处理常见的图形去噪处理，图像压缩的性能有严重的影响，图像滤波器通过分析丢失的图像中的细节，在小波的细节变化下，二进制小波极大值与传播特性息息相关。这也决定了四叉树对噪点检测会非常地准确，通过四叉树的遍历对图形中的噪声点的“椒盐噪声点和高斯噪声”的极大值作逐一分析和定位。实践证明这种方法的去噪点效果非常有效，并且能最大化地减少在图片处理中对压缩性能的影响，最大程度地为图像保真。实验也证明了这个结果，通过预处理后的自适应去噪模型能够更直观地展现图像受声污染的轮廓和细节，这也是基于准确的算法快速地对噪点扫描分析实现的。通过与原图像进行对比可以对噪点的位置和状态有一个客观的评价和处理方法。

自适应图形去噪是建立在含噪图像预处理的基础上的去噪方法，通过对边缘检测来获取噪点监测参数，进而构建图像兼容的平滑去噪自适应的模型。这种模型是建立在Bregman基础之上的快速迭代运算方法，在自适应图形去噪实验研究中发现，这种自适应去噪模型在快速去噪的同时保留了图像的细节和纹理结构，所得到的的图像复原结构在视觉效果上有所提高。

综上所述，基于四叉树复小波的自适应去噪法在图像去噪上取得了不错的效果，但是在卫星图像上要求更高。因为在利用四叉树复小波进行图像去噪时，在细节处理上还略显薄弱，在复原工作上也有一定局限性，所以通过对复小波的变换就可以解决以上两大问题。只要在四叉树复小波的变换中能够保证滤波器的完全重构和采样序列能够奇偶对正，就能够减少字去噪处理中的细节问题，这也是图像去噪基于四叉树复小波的自适应的发展趋势。

3 基于四叉树复小波的自适应图形去噪的优点

3.1 有限冗余和高效率的计算

四叉树复小波常常被用于作为频率消耗的分辨和分析，因为其准确性和高效性被应用得非常广泛。通过把信息根据低频和高频进行分离，这是保护图像边缘相信的方法，在通过频率的分析来获得近似独立的系数，这能够为图像去噪创造独立的环境，另外“局部性和光滑性”是其主要的特点。这也使得四叉树复小波代替了传统的金字塔分解方式再与SAR图像的联合增强了其多分辨去噪的能力，这也是其高效率的表现。

有限冗余主要是表现在四叉树小波的变换，通过第一层分解成4个子数后，有限冗余为4:1，接下来每一个步骤都按上一步的4:1的方式分解。这在一定程度上也减少了计算变换的繁琐，与传统的算法相比计算速度更加快，而计算步骤也只是增加三倍而已。

3.2 方向平移不变性

方向平移不变性主要是通过图像的重构中可以看出，还有制定层的细节能够看出其中平移的图像，这就是四叉树复小波在重构中的平移，并且也没有产生混乱和重叠现象。四叉树复小波变换和一般实小波变换图中最能看出其平移不变的特点。通过四叉树在滤波器中的重构来实现其奇偶数的对策，其中偶数相比奇数频率较长，这也是其区分的原则。在复小波的转换中得到实部与虚部，尽管在外观上很难分辨，但根据冲激相应和序列位点可以分辨其属性和方向。

3.3 良好的方向选择

四叉树复小波具有良好的方向性，这主要发生在变换期间。这是因为它在变换的过程中能够区分不同频率的部分，明确各个方向的频率才能够对正负十五度、正负四十五度和正负七十五度六个方向的带子通区分。这也是在获取冲激响应下的四叉树小波频率来区分的，所以说良好的方向判别是其一大优点。这种非线性的去噪原理能够比传统的盲目的方向性更加有去噪的针对性，这表现在小波系数对不同噪声频率的判别和方向选择性，避免了去噪处理中缺少细节带来的处理不完全的现象。

其中信号小波的变换并不是一成不变的，而是根据系数尺度的变化而变化，具体变化规律是递增序列。当信号小波的局部变化太激烈时，这表明了空间出现了奇异点现象。这也就说明了在低频滤波部分应对模糊图像时处理效果会更出色，小波变换分解的尺度越高，图片的清晰度也就越高。在实验中也可以得出，噪点处理性能在尺度的改变上变化非常有限，选定事宜的分解尺寸才能获得最好的性能。

4 结束语

基于四叉树复小波的自适应图像去噪法很好地解决了去噪过程中图像压缩的影响问题，以及避免了图像的灰度级丢失和图形质量问题，也是小波压缩零树算法的革新。不过在自适应图形中的算法性能还有待进一步提高，而通过抑制噪声就可以实现算法性能的提高。这种通过聚类分析来检查图像特殊噪点的方法，能够有效避免常见的椒盐噪声和高斯白噪声。在清除噪声中，保护边缘信息的完整性也非常重要，所以在噪点处理中需要从保护边缘信息开始。在小波局部噪点运算中，增强“硬阈值和软阈值”两种算法的优势，达到优势互补，互相促进。这也是充分利用复小波在图形噪点处理上的优势，以及与图形变换的完美结合。从目前的图像去噪的发展趋势来看，基于四叉树复小波自适应图像去造法具有较大的竞争力，采用四叉树复小波变换和基于子带噪声的自适应阈值方法具有较好的去噪效果。

参考文献

[1]赵美玉.浅析计算机多媒体技术应用与发展趋势.中小企业管理与科技(下旬刊),2012-05-25.

[2]李雨,冯迪.浅析计算机网络通信协议.中小企业管理与科技(上旬刊),2009-01-05.

四叉树阵列篇4

如今,信息隐藏作为保密通信、版权保护等的主要手段,已经得到了广泛的研究与应用,而以图像为载体的基于分形理论的信息隐藏技术更成为研究的热点[1,2,3,4]。

1992年,Jacquin运用局部函数迭代系统理论,提出了一种基于图像子块的全自动的分形图像压缩方法[5],实现了从人工编码到自动编码的转换,大大提高了效率。自此分形编码以新颖的编码思想、高压缩比、解码速度快、分辨率无关性等优点受到学术界的广泛关注[4,5,6],它不仅用于图像压缩,而且还应用在数字水印、人脸识别、信息隐藏等领域中[8,9]。之前,已有很多基于传统分形编码的信息隐藏算法[8,11,12],它们都是在变换域上嵌入隐藏信息,通过对原始载体图像的分形码的分类实现信息嵌入的,而且信息提取必须对载密图像再次进行分形编码,因此信息的提取需要较长的时间。后来Oien和Lepsoy提出的一种特殊的正交分形编码方法,在正交分形编码中,灰度仿射变换中的亮度因子就是值域块的均值,而且这个均值在解码过程中是迭代不变的,大大减少了分形解码的时间。2008年,Pi等人以此提出了一个新的正交分形编码水印算法[8],通过修改分形编码参数将要隐藏的水印嵌入到整幅图像中。该算法具有较强的隐蔽性和鲁棒性,同时大大缩短了整个信息隐藏、提取过程所需要的时间。但基于正交分形编码的信息隐藏算法大都采用平均分割原始载体图像的方法,这种方法的缺点是: 灰度变化明显的区域不能很好地覆盖,而灰度变化不大的区域则不需要划分得很小; 同时原始载体图像为彩色图像时,很多是按照R、G、B三个独立的灰度图像进行单独编码的SFC ( separated fractacoding) 方法,这种方法不能很好利用分量相关性,因此编码时间较长,这也限制了这类算法的实际应用。

考虑以上正交分形信息隐藏算法的不足之处,主要有两点( 1) 等分割载体图像,无法自适应调整划分值域块的大小,非常耗时; ( 2) 在处理彩色载体图像时,很少考虑分量间相关性和拼贴误差,鲁棒性较弱。因此本文在以上算法基础上,提出了一种在彩色图像中利用四叉树分割的正交分形编码来嵌入信息的方法,该方法对彩色载体图像进行四叉树分割,根据图像块的细节复杂程度分割不同大小的值域块,能在几何尺寸上自适应图像内容,并且利用拼贴误差原理,动态改变值域块均值的修改量,兼顾了秘密信息的透明性和载密图像的鲁棒性; 同时考虑现今互联网上的图像大都是彩色图像,使用彩色图像隐藏信息不易引起注意,因此选择彩色图像作为载体图像,利用彩色图像R、G、B三个分量的相关性进行编码,大大缩短了编码时间。实验表明,该信息隐藏算法具有较好的透明性和鲁棒性。同时该算法在某海事船舶船岸数据隐蔽通信中获得了初步应用,应用效果良好。

1 使用四叉树分割的正交分形编码

2008年,Pi等人提出了一个新的正交分形编码水印算法[8],在正交分形编码中,灰度仿射变换中的亮度因子就是待编码子块的均值,而且这个均值在解码过程中是迭代不变的,嵌入到该均值中的秘密信息不会因正交分形解码而消失,而是散布于整个载体图像像素域中。此外,秘密信息的提取只需要计算图像子块的均值,因而秘密信息的提取比其它变换域算法都快。随后,很多学者在Pi等人提出的算法上做了很多改进,并将这种方法应用在了图像隐写中,获得了很好的效果,如考虑HVS特性将值域块分类[9,12],对不同的值域块选择不同的嵌入强度,或者利用拼贴误差的原理[11,12],这些方法都能较好地兼顾秘密信息的不可感知性和鲁棒性,使得基于正交分形的信息隐藏算法更具有实用价值。但这些方法在载体图像进行正交分形编码时,都是将图像平均分割成若干互不重叠大小为2b×2b的值域块R ,如果分割的值域块尺寸过大,那么整个信息隐藏和信息提取过程所需要的时间就越少,但是隐藏的信息量就会很少,如果分割的尺寸过小,所需要的时间很长,也不利于整个信息隐藏过程。

因此可以考虑在图像分割时,根据图像块的特征分割为可变大小的块,这样就能很好地兼顾时间和隐藏量。Y. Fisher于1991年提出图像的四叉树分割方案[6],该方案在图像分割时能根据值域块的拼贴误差自适应地调整值域块的大小。将四叉树分割理论运用到信息隐藏中,可以根据原始载体图像的特征,动态自适应分割图像值域块,同时根据值域块的拼贴误差,调整嵌入秘密信息的强度,兼顾了信息隐藏的时间和隐藏容量,实验表明,这种方法的抗攻击能力( 鲁棒性) 比传统的正交分形信息隐藏算法要强。具体的分割流程如图1所示。

2 彩色图像分量相关性以及拼贴误差

现在,互联网上的图像大都是彩色图像,考虑到信息隐藏的透明性,本文选择彩色图像作为载体图像,通过第1节的编码方法,将秘密图像嵌入到其中,以达到隐蔽通信的目的。而传统的SFC方法[13],未能考虑到彩色图像R、G、B三个分量的相关性,对分量进行分别编码相当费时。本文结合文献[13]中的根据彩色图像R、G、B三个分量的相关性,在对彩色载体图像进行正交分形编码时,首先对亮度分量Y = 0. 301r + 0. 586g + 0. 113b进行编码,然后对三个分量中的对比度因子s以及值域块均值r进行修正,s的修正公式如下:

其中ri是彩色图像红色分量Ir中值域块R的像素值,d'i是Ir中D块经过四邻域平均后与R块等大的定义域块D' 中的像素值,--r和d'分别是R和D' 的平均值( 具体的修正过程在第3节的信息嵌入过程中有详尽的描述) 。在保证图像质量的前提下,加快了正交分形编码的速度。这种算法和SFC编码算法相比,匹配时间缩短约为原来的1 /3,大大缩短了正交分形编码的时间。

很多基于正交分形编码的信息隐藏算法是通过修改载体图像的分形编码参数实现信息嵌入的,具体来说是修改参数中R块均值来嵌入信息的。通过实验发现,R块均值的改变量越大,图像的鲁棒性越强,但是载体图像就会在视觉上降质,从而带来秘密信息透明性的降低,因此需要折中处理[12]。本文将拼贴误差[10,12]运用到均值的修改上,具体说,图像中纹理或边缘区域的拼贴误差大,但是图像中的平滑区域的拼贴误差要小好多,拼贴误差反映了图像的局部特征,如果对于图像的平滑区域也就是拼贴误差小的值域块均值修改量小,反之修改量大,这样既能保证秘密信息的隐蔽性,同时也能带来载体图像鲁棒性的提升。本文首先采用正交分形编码得到分形参数,然后根据拼贴误差将值域块R分成Ci类,不同类中的Ri嵌入强度Δi不同( 式2) ,这样图像的不同局部采用了不同的嵌入强度,从而兼顾秘密信息的透明性和载密图像的鲁棒性。

3 信息嵌入和提取

本文的秘密图像采用灰度图像,然而传统的正交分形算法无法直接运用到灰度图像中。所以,本文采用文献[11]中的方法,通过变换函数,将灰度秘密图像的像素值作为修改参数时的增量,以达到嵌入秘密图像的目的。

设载体图像IN×N,利用正交分形编码嵌入秘密图像时需要修改R块均值r,修改公式如下:

设原始载体图像是2m×2n的彩色图像I,秘密图像为256级灰度图像S。为了增强秘密图像的安全性,同时防止剪切、涂抹等攻击使提取的图像丢失大片连续的区域,这里选择对秘密图像进行Arnold置乱,迭代次数作为密钥key1保存。具体的嵌入过程如下:

( 1) 原始图像I提取亮度分量Y = 0. 301r + 0. 586g +0. 113b,得到一幅灰度图像I' 。

( 2) 设置整个图像I' 为当前值域块Ri,按照图1四叉树的方式进行分割,分割的过程中记录下正交分形编码参数( xi,yi,ai,s,r) 。( 其中( xi,yi) 表示定义域块的位置,ai是8种仿射变换的序号,s表示对比度,r表示当前值域块的均值) 。

( 3) 将原始图像I中红色分量所组成的灰度图Ir中,与值域块R最佳匹配的定义域块D块的坐标和仿射变换序号用I' 中得到的来替代,而R块的平均值用Ir自身的平均值替代,对因子s进行修正,修正公式见式( 2) 。G( 绿色) 分量和B( 蓝色) 分量做相同的处理。最终得到修正后的编码参数 ( xi,yi,ai,sr,rr,sg,rg,sb,rb) 。

( 4) 重复( 2) 、( 3) 直到所有的值域块编码完毕,因为不是等分割载体图像,这里需要记录图像分割情况,作为秘钥key2,供提取信息时使用。

( 5) 按拼贴误差E( R) 对子块集合{ Ri} 进行降序排列,得到子块序列,并把它划分为n类记为Ci,每类的子块个数为:2m + n -2b/ n,每类的嵌入强度为Δi,1≤i≤n。

( 6) 对于子块R∈Ci( 1≤i≤n) ,若对应秘密图像像素值为w,则将分形参数( xi,yi,ai,sr,rr,sg,rg,sb,rb) 中的rr按式( 1)修改得到rr',量化步长满足Δi> Δi+ 1( 1≤i≤n) 。同理,下一个像素值,我们依次处理rg、rb。按照修改均值后的分形码( xi,yi,ai,sr,rr',sg,rg',sb,rb') 进行分形解码迭代,得到含秘密信息的彩色图像。

秘密信息的提取是嵌入的逆过程。具体提取步骤如下:

( 1) 将载密图像按照秘钥key2进行分割,对于每个块Ri,计算三个分量图像的均值ri( 0≤i < 2m + n -2b) 。

( 3) 根据密钥key1,对提取的秘密图像序列W' 进行逆Arnold变换,就得到了秘密图像W。

4 实验结果及分析

本文算法研究及应用背景是某海事船舶管理系统的隐蔽通信子系统,该算法已经在其中获得了初步应用,主要完成隐蔽通信功能,同时为了全面测试算法的有效性,本文做了一系列的实验。

在实验中,原始载体图像采用256×256大小的彩色Ship图,秘密图像为64×64大小的灰度图像,如图2所示。采用第1节的基于四叉树分割的正交分形编码嵌入秘密图像,图像分割的最小分割深度min Dep = 6,最大分割深度max Dep = 7,得到所有R块的正交分形编码参数和E( R) ( 拼贴误差) ,根据E( R)将{ Ri} 分成3类,对应的Δ1= 15,Δ2= 10,Δ3= 6。其中f( w) 变换函数[11]取: f( w) = e( -2. 65 +w/100)。下面对信息隐藏算法两个最重要的指标透明性和鲁棒性分别进行验证,采用PSNR和相似度[12]作为评判的依据,同时将本文算法与Pi算法以及文献[11]中的方法进行对比。

表1给出了本文算法,Pi算法,文献[11]算法嵌入秘密图像后的解码图像与原始图像的R、G、B三个分量的峰值信噪比PSNR。可以看出,当嵌入后的PSNR大于30左右时,人眼很难察觉到图像的降质。这也间接说明了,本文采用四叉树分割的正交分形信息隐藏算法具有较好的透明性( 隐蔽性或不可感知性) 。

图2( c) 给出了在没有收到任何攻击时,从载密图像中提取出的秘密图像,与原始图像相似度为1,说明了本文算法在没受到攻击的情况下能够准确提取出秘密图像。

为了验证本文算法的鲁棒性( 或抗攻击性) ,下面对载密图像分别进行攻击性实验,如: JPEG压缩、加噪、滤波、几何形变等处理。

4. 1 JPEG 压缩

JPEG压缩是图像处理中最常见的操作,对嵌入秘密图像后的载密图像进行JPEG压缩后( 质量因子Q分别为90,80,…,40) ( % ) ,再分别用本文算法进行秘密图像提取实验,结果如表2所示。

无论是从表2的客观数据来看,还是从图3的视觉感受来看,在JPEG压缩质量因子为90、80、70、60、50、40的情况下,相似度都能在75% 以上,说明了算法能够较好地抵抗JPEG压缩,同时和其他算法比较,采用四叉树正交分形编码的隐藏算法能够更有效地抵抗JPEG压缩。

4. 2 图像的加噪、滤波处理

表3和图4给出了对载密图像进行高斯噪声( 0. 02) 、椒盐噪声( 0. 02) 以及均值滤波( 3×3) 攻击后提取出来的秘密图像,相似度分别达到0. 732、0. 935和0. 783,由此可见,本文算法对加噪、滤波有较强的鲁棒性。

4. 3 其他攻击

如表4所示,实验表明: 本文算法具有很好的透明性,而且对加噪、滤波、图像几何形变以及JPEG压缩等具有较强的鲁棒性。

5 结语

本文将四叉树分割理论应用在正交分形信息隐藏算法中,能够根据图像自身特征自适应划分值域块,不仅缩短了秘密信息嵌入过程所需要的时间,而且秘密信息嵌入到载体图像的整个图像域中增强了算法的鲁棒性。在处理彩色图像时,利用R、G、B分量间的相关性,提取亮度分量作为基准,修改三个分量的对比度因子和值域块均值,缩短了正交分形编码的时间。同时在处理秘密图像时,通过变换函数将图像像素值转变成分形编码参数的修改量,弥补了传统正交分形信息隐藏算法只能处理0、1序列或二值图像的不足。通过实验对比,本文算法相对于其他算法透明性好,并对各种攻击有较好的鲁棒性,具有良好的应用价值。

摘要：目前的正交分形信息隐藏算法在进行正交分形编码时都是等分割原始图像,这样无法自适应图像内容且耗时,并且在处理彩色图像时没能考虑分量之间的相关性以及拼贴误差,因此鲁棒性较差。提出一种采用四叉树分割的正交分形信息隐藏算法。该算法能够根据图像特征实现原始图像的四叉树分割,同时考虑彩色图像R、G、B三个分量的相关性,提取亮度分量进行分形编码,并利用拼贴误差特性,动态调整分型参数的修改量来嵌入秘密图像。实验及应用表明,该算法编码时间短、具有很好的透明性以及对JPEG压缩、加噪、滤波、几何形变等具有较好的鲁棒性。

四叉树阵列篇5

一、等面积四叉树全球离散格网数学基础

1. 球冠、球带

对于半径R的球面垂直于直径的平面将其分割成两个部分, 把高度小于或等于R的部分称作球冠。垂直于直径的两平面将其分割分成三个部分, 处于两分割平面之间的部分称作球带[4]。

2. 球冠等积四叉树分割

(1) 分割模式

图1中半径R高度H的球冠a分成四部分常有 (b) 、 (c) 两种形式。称 (b) 模式为极点片状等面积四分模式, 四个格网呈两层排列, 顶层是一个子球冠格网, 底层为处于同一球带上的三个梯形格网;称 (c) 模式为极点瓣状四分模式。若从极点近邻区域应属同一个格网来着眼, (b) 模式比 (c) 模式要好[5]。

(2) 极点片状等积格网四叉树

图1中 (b) 为球冠的一级分割, 规定一级梯形格网分割线为-120°、0°、120°三条经线。对一级子球冠格网, 以H/16的纬线平面及-120°、0°、120°三条经线进行分割, 又被分成四个二级格网;对一级梯形格网以过球带高中点的纬线平面及格网中央经线进行分割, 形成中带底色的12个等面积格网。这样二级格网共有16个。按照这种方法可无限继续进行, 各级格网形成一颗四叉树。

(3) 球带格网的等积四叉树分割

在球冠的二级四叉树分割中, 顶部子球冠格网被进一步被分成一个次级球冠格网与三个同一球带上的格网外, 其余非球冠格网则属同一球带上格网的等积四叉树分割, 其分割方法为每个球带格网的中央经线与过球带高中点的纬圈。

二、等面积四叉树全球离散格网变形分析

格网的几何稳定性是格网模型的基本特性, 对于保持格网的精度有着重要意义, 直接影响到不同分辨率下地理实体的表达和操作的精确性。格网的几何均匀性及其在不同分辨率剖分层次下的稳定性是实践应用中选择格网的一个重要参考指标。

1. 等面积四叉树全球离散格网网边变形递推公式

对于半球的等面积格网即球冠半径及高度均为地球参考球面半径R。每个格网长度应该为该格网所在纬线圈周长除以该格网带的列数。利用公式:纬线圈周长=2πRcosϕ, 其中ϕ为该纬线圈的纬度值。又当带号m不等于等面积格网的级数n+1时, 第m同素格网带的列数。

以一号Cm=3*2n-m。格网带为例, 其中最大边为赤道, 其纬线圈长度为2πR, 随着递归剖分其每个格网带的长度应为2πR/3*2n-m。由于该同素格网带带高不会变即为3R/4, 所以最上边即最短边的纬线圈长度也不会变, 依据纬度定义有sinϕ=34, 可得纬度ϕ=arcsin3/4, 因此该边随着格网的递归剖分其每个格网带的长度应为2πRcosϕ/3*2n-m。

而对于最上边和最下边之间的格网, 由于其纬度会随着网高的不同而有所变化, 所以要先计算出其网高, 进一步推出纬度即可得纬线圈长度。依据公式:网高=带高/行数, 即△hm=△Hm/rm, 当带数不等于等面积格网级数n+1时, 网高△hm=3R/4m*2n-m, 依据纬度定义有ϕ=arcsin3R4m*2n-m, 再依据纬线圈长度除以列数即可。也就是最下边l=2πR/3*2n-m, 最上边l=2πRcosϕ/3*2n-m (ϕ=a r c s i n3/4) , 中间格网l=2πR c o sϕ/3*2n-m (ϕ=arcsin3R/4m*2n-m) 。

2. 网边变形结果

选取西安80坐标系, 其参考椭球体为1975国际椭球体, 参数为a=6378140m, b=6356755.288m, e2=0.006694384999588。因此依据等面积球体半径计算公式R等面积=a (1-1/6e2-17/360e4) , 得R=6371010.222m。表1为上述给出的递推公式求得的边长在不同层次的变化。

3. 网边变形分析

(1) QTM格网的几何变形计算

根据QTM曲面面积和弧距计算公式[6], 得QTM最大边最小边比值 (表2)

(2) QTM几何变形分析

通过对计算结果的分析发现:随着格网的不断细化, 三角形的最大和最小面积的比值与最大和最小边长的比值越来越大, 但是其变化的速度越来越小。

(3) 分析比较

1.随着格网的不断细化, 变形由下向上不断增大, 但都保持在1左右

2.与QTM相比, 格网变形要小的多且没有面积变形 (如图2)

3.同样具有收敛性, 保持了近似均匀的特征

4. 有利于球面实体的层次索引与扩展操作, 是比QTM更好的格网剖分模式

全球离散地理格网是基于球面的一种可以无限细分, 但又不改变形状的地球拟合格网, 当细分到一定程度时, 可以达到模拟地球表面的目的。本文在对全球等面积四叉树离散格网建模方法分析的基础上, 进行了网边变形计算及分析, 得出以下结论:

(1) 全球等面积四叉树离散格网在纬向上采用表现为纬圈到赤道面垂直距离的线量来控制, 减小了格网的变形量。