.网站建设的目标,网站内的新闻怎样做链接,wordpress模板 科技,小程序开发者工具教程四叉树编码
1.四叉树编码定义
四叉树数据结构是一种对栅格数据的压缩编码方法#xff0c;其基本思想是将一幅栅格数据层或图像等分为四部分#xff0c;逐块检查其格网属性值#xff08;或灰度#xff09;#xff1b;如果某个子区的所有格网值都具有相同的值#xff0…四叉树编码
1.四叉树编码定义
四叉树数据结构是一种对栅格数据的压缩编码方法其基本思想是将一幅栅格数据层或图像等分为四部分逐块检查其格网属性值或灰度如果某个子区的所有格网值都具有相同的值则这个子区就不再分割否则还要把这个子区再分割成四个子区这样依次地分割直到每个子块都只含有相同的属性值或灰度值为止可分为自上而下编码和自下而上编码
2.四叉树表示形式
用一倒立树表示这种分割和分割结果如图所示。
根整个区域
高深度、分几级几次分割
叶不能再分割的块
结点或树叉还需分割的块
每个树叉均有4个分叉叫四叉树。 3.四叉树的分类
四叉树分为常规四叉树和线性四叉树
(1 常规四叉树记录这棵树的叶结点外中间结点结点之间的联系用指针联系每个结点需要6个变量父结点指针、四个子结点的指针和本结点的属性值。
指针不仅增加了数据的存储量还增加了操作的复杂性如层次数分割次数由从父结点移到根结点的次数来确定结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以常规四叉树并不广泛用于存储数据主要在数据索引和图幅索引等方面应用
2线性四叉树则只存贮最后叶结点的信息包括叶结点的位置编码/地址码、属性或灰度值线性四叉树地址码通常采用十进制Morton码MD码如图所示
①下图为一个8*8原始栅格数据 ②依据自下而上的编码方式进行莫顿码编码 ③在存储时只存储属性值发生改变位置的莫顿码就是叶节点的属性值 ④如何计算莫顿码如图所示通常是将栅格数据十进制的行列号转成二进制的行列号再将二进制的行号和列号进行错位交叉排列得到二进制的莫顿码再将二进制的莫顿码转成十进制的莫顿码 4.四叉树编码特征
优点
1存贮量小只对叶结点编码节省了大量中间结点的存储地址码隐含着结点的分割路径和分割次数。对于团块图像四叉树表示法占用空间比上述其他方法要少得多四叉树表示法基本上是一种非冗余表示法。
2线性四叉树可直接寻址通过其坐标值直接计算其Morton码而不用建立四叉树(自下而上。
3) 容易执行实现集合相加等组合操作
4四叉树具有可变率或多重分辩率的特点使得它有很好的应用前景适用于处理凝聚性或呈块状分布的空间数据特别适用于处理分布不均匀的块状空间数据但不适用于连续表面如地形或线状地物。
缺点
1四叉树未能直接表示物体间的拓扑关系。
2) 与非树表示法比较四叉树表示法的缺点在于转换的不稳定性或叫滑动变异
例如两个图像的差异仅由于平移就会构成极为不同的四叉树因而很难根据四叉树来判断这两个图像是否全同故不利于做形状分析和模式识别
3) 一个物体的图像在构成四叉树时会被分割到若干个象限中使它失去了内在的相关性。
4矢/栅正反变换还不理想。
5) 建立四叉树耗费机时很多。
6) 四叉树虽可修改但很费事
