线性八叉树的邻域寻找的新算法

来源:用户上传      作者: 廖维猛

　　摘要:提出了一种直接利用三维栅格的编码求其邻域的新算法。这种算法在求相同尺寸邻域时,仅需扫描编码的后几位,而在求不同尺寸邻域时,则直接在已求出的相同尺寸邻域的基础上,利用编码的层次性和大小性寻找此邻域的各级祖先结点和各级子孙结点,且仅需扫描此邻域编码的前几位。
　　关键词:三维栅格 线性八叉树 邻域
　　
　　引言
　　 八叉树只记录叶结点的编码,而不记录中间结点的编码及层次关系,由于它比普通八叉树大大节省了存储空间,且蕴含有层次特性,因此它在实际工作中得到了广泛的应用。邻域实质上是一种拓扑关系,邻域的寻找在一定程度上说,也就是在三维栅格结构中确定物体间的拓扑关系。因此,寻找某一三维栅格的邻域也就成了克服栅格结构中拓扑关系不清晰及栅格矢量数据结构相互转换难点的一种新思路。因此,邻域寻找成为许多学者研究的重点之一。
　　
　　2 几个概念
　　2.1线性八叉树的邻域
　　 它的邻域则分为三种:面相邻的面邻域、边相邻的边邻域、角相邻的角邻域。线性八叉树任一栅格的面邻域有6个,边邻域有12个,角邻域有8个,共26个邻域。
　　2.2边界三维栅格与非边界三维栅格
　　 边界三维栅格是指处于边界上的三维栅格,它们的共同特点是在其各个邻域中总有一个或一个以上的邻域不存在,即这些邻域或是在研究区以外,或是在背景叶结点集中。除了边界三维栅格以外,剩下的都是非边界三维栅格,非边界三维栅格的各个邻域都存在。
　　2.3相同尺寸和不同尺寸邻域
　　 相同尺寸邻域是指待求邻域的尺寸与原三维栅格的尺寸相同。不同尺寸邻域则指待求邻域的尺寸与原三维栅格的尺寸不同,或大或小。
　　2.4对于八叉树编码基准体系的划分
　　 线性八叉树的编码基准体系划分为:北部N8={0,1,4,5}, 南部N8={2,3,6,7},西部W8={0,2,4,6}, 东部E8={1,3,5,7},上部U8={0,1,2,3} 下部D8={4,5,6,7},八叉树的面邻域分为东面、西面、南面、北面、上面、下面邻域;其边邻域可分为东上、东下、西上、西下、南上、南下、北上、北下、东北、西北、东南、西南边邻域;其角邻域分为8个,它们是西北上、西北下、东北上、东北下、东南上、东南下、西南上和西南下角邻域。
　　2.5线性八叉树层次编码特性剖析
　　 线性八叉树的编码有如下特性:(1)方向性。按照八叉树的编码基准,编码大小是按由西向东,由北向南、由上向下的顺序递增。(2)层次性。第n层像元的四进制编码应为:q1q2…qn, qi∈{0,1,2,3,4,5,6,7}, i=1,2,3,…,n在这些编码中,处在第1位的是第1层,第2位是第2层,第n位是第n层(第n次分割), 编码是321像元,因为第一位q1=3按照编码的基准,表示该像元在第1层中的位置为3,同样第2层的位置为2,第3层的位置为1。(3)可压缩性。由编码可知,每一个像元q1,q2,…,qn都需要n个字节来存贮,这显然有点浪费存贮空间,为此可采用位运算法将其转为十进制码以进一步压缩,如对四进制编码为321的像元有(321)4=3×82+2×8+1=209。(4)大小性。显然,编码的位数越多,深度越大,层次越低,像元尺寸越小,编码为2的像元的尺寸分别是编码为30、321像元尺寸的2倍和4倍。
　　
　　3 线性八叉树邻域的确定
　　3.1边界栅格识别
　　 对于任一像元A=O1O2…On,Oi为八进制整数,我们首先判断其是否为边界栅格,若 Oi∈E8或 Oi∈S8或 Oi∈W8或 Oi∈N8或 Oi∈U8或 Oi∈D8, 表示全部,则在面邻域中,其对应的E邻域或S邻域或W邻域或N邻域或U邻域或D邻域将分别不存在。对于边邻域、角邻域存在与否的情况,读者可自行推之。识别出边界栅格后,就知道了哪些邻域不存在,是不用求的。而对于存在的邻域,按下面的方法来求。
　　3.2 相同尺寸面邻域的确定
　　 对于线性八叉树的东、南、西、北面邻域的确定,由于只是在上部或下部内单独运算,上部和下部之间并不发生任何关系,所以可以直接用与线性四叉树相同的求解方法来确定它们。其中,末位qn为0或4、1或5、2或6、3或7的计算方法分别与线性四叉树末位qn为0、1、2、3的计算方法完全相同,只是要注意,若用计算公式计算,则要把上述四叉树公式中的4换成8,因为在八叉树中使用的是八进制编码。但是对于上部和下部发生关系的上下邻域的求解,则要按如下规则来求:
　　 若qn属于上部集合,根据八叉树编码标准体系,可以直接得其下面邻域为A+4,而其上面邻域编码的求解则要经过如下判断:
　　 从编码的末位qn按从右到左的顺序扫描,直到找到第一个不属于上部集合的编码qi(1≤i≤n-1,i为从左到右的码位序号)为止,显然右边的n-i个编码位qj(j=i+1,…,n)都属于上部集合,将它们的值均加4,qi的值减4,而q1,q2,…,qi-1的值不变,此时得到的新编码即为所求邻域的编码(若找不到不属于上部集合的编码,则表明该栅格为上边界栅格,其上邻域不存在)。
　　类似地,若qn属于下部集合,则其上面邻域为A-4,对其下面邻域的求解,也可从编码的末位qn按从右到左的顺序扫描,直到找到第一个不属于下部集合的编码qi(1≤i≤n-1)为止,显然右边的n-i个编码位qj(j=i+1,…,n)都属于下部集合,将它们的值均减4,qi的值加4,其余的不变,如此得到的新编码即为所求邻域的编码。(若找不到不属于下部集合的编码,则表明该栅格为下边界栅格,其下邻域不存在。)
　　3.3相同尺寸边邻域、角邻域的确定
　　 线性八叉树边邻域的情况类似于线性四叉树的角邻域,可采用二维平面矢量合成法,用两次求面邻域的方法来求。其角邻域的确定则较复杂,需用到三维矢量合成法,即一次求边邻域,一次求面邻域,实质上它最终可分解为三次求面邻域:南北面邻域,东西面邻域,上下面邻域。
　　3.4 不同尺寸邻域的确定
　　 我们的方法则是充分利用已求出的相同尺寸邻域来确定它。由于线性八叉树只记录物体叶结点的编码,因此,所求出的相同尺寸邻域的编码(记为B)在线性八叉树的物体叶结点集合中不一定存在。若B存在,则要依据层次编码的层次特性确定B的各级祖先结点或各级子孙结点中的哪一个存在于物体叶结点集中,所存在的祖先结点或子孙结点即为所求的不同尺寸邻域。这是一个搜索比较问题,由于编码的层次特性,各级祖先结点和子孙结点编码的前几位必与B的前几位相同,而且层次越高的祖先结点层数越少。另外由于我们最终要找到的是B在线性四叉树中的最高祖先结点或最大子孙结点,因此应按从高到低的顺序逐层扫描,一旦找到即可停止,以此来加快检测速度。若找不到任何祖先结点和子孙结点,或B本身不存在(或在研究区以外或属于背景叶结点集合),则所求的不同尺寸邻域一定不存在。
　　 由此可见,在我们的方法中,不同尺寸邻域的确定只是一个对已求出的相同尺寸邻域的各级祖先结点或各级子孙结点在八叉树中的存在与否进行检测的问题,关键环节还在于直接、快速地求出相同尺寸的邻域。上面的求编码和检测步骤都是利用层次编码的层次性和大小性而进行的。
　　
　　4结语
　　 分析了线性八叉树编码的特性,并利用它发展了一种新的邻域寻找算法。邻域寻找算法在三维实体分析、边界的确定、三维拓扑关系的确定及连通性判断等方面具有重要的意义。
　　
　　参考文献:
　　[1] 晏明辉.二值图像邻域寻找的一种快速方法.计算机应用与软件,1997(5):32~36.
　　[2] 田文,李仲.计算线性四元树表示的二值图像Euler数的图论方法.计算机学报1989(9): 682~688.

转载注明来源:https://www.xzbu.com/8/view-1064503.htm