线性四叉树的邻域寻找的新算法
来源:用户上传
作者: 刘佳慧
摘要:提出了一种直接利用像元的编码求其邻域的新算法。这种算法在求相同尺寸邻域时,仅需扫描编码的后几位,而在求不同尺寸邻域时,则直接在已求出的相同尺寸邻域的基础上,利用编码的层次性和大小性寻找此邻域的各级祖先结点和各级子孙结点,且仅需扫描此邻域编码的前几位。该算法结构简单,易于理解和实现,且寻找速度快、准确。对于部分邻域的寻找,只需一步加减运算即可完成。
关键词:线性四叉树 邻域 边界像元
1 线性四叉树的几个概念
1.1线性四叉树的邻域
邻域分为两种,一种是边相邻的邻域,称为边邻域,又因为在二维图像中任一像元都有四个边邻域,因此又称为四邻域;另一种是角对角的邻域,称为角邻域。将边邻域和角邻域加起来,任一像元上的邻域都有八个,故也称之为八邻域。
1.2边界像元、非边界像元
边界像元是指处于边界上的像元。它们的共同特点是在其各个邻域中总有一个或一个以上的邻域不存在。除了边界像元以外,剩下的都是非边界像元,非边界像元的各个邻域都存在。
1.3 对于四叉树编码基准体系的划分
线性四叉树的编码基准体系划分为如下几个集合:
北部N4={0,1} 南部S4={2,3}西部W4={0,2}东部E4={1,3}
且边邻域分别称之为E邻域、S邻域、W邻域、N邻域,如像元1是像元0的E邻域;角邻域分别称为东南角邻域、东北角邻域、西南角邻域、西北角邻域,如像
元3是像元0的东南角邻域。虽然,上述几个约定看起来较为简单,但它们为后面寻找不同尺寸邻域复杂操作提供了极大的方便,保证了数学上的严密性。
1.4线性四叉树层次编码特性剖析
线性四叉树的编码有如下特性:(1)方向性。按照四叉树的编码基准,编码大小是按由西向东,由北向南的顺序递增。(2)层次性。第n层像元的四进制编码应为:q1q2…qn, qi∈{0,1,2,3}, 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×42+2×4+1=57。(4)大小性。显然,编码的位数越多,深度越大,层次越低,像元尺寸越小,编码为2的像元的尺寸分别是编码为30、321像元尺寸的2倍和4倍。综上所述,由于线性四叉树编码所具有的这些特性为我们寻找邻域提供了一种新的线索和思路,因而我们在这里详细介绍了这些编码所蕴涵的特性。
2 线性四叉树邻域的确定
我们寻找邻域的思路是根据待求栅格的编码直接求出其所有邻域,线性四叉树的编码本身就包含有方向性、层次性、大小性等寻找邻域时所需要的特性,于是如何发掘并将它灵活运用到邻域的寻找上便成了解决问题的关键。
2.1 相同尺寸边邻域的确定
2.1.1非边界像元的相同尺寸邻域的确定
对于任一非边界像元A=q1q2…qn, qn为四进制数,其东西南北四个边邻域可按如下规则确定:若qn=0,则根据编码标准体系,可以直接得其东边邻域为A+1,南边邻域为A+2,其西边邻域和北边邻域的求解则要经过如下判断。对西边邻域,从编码的末位qn按从右到左的顺序扫描,直到找到第一个不属于西部集合的编码qi(1≤i≤n-1,i为从左到右的码位序号,注意在计算机数组中i是从0起算的,下同)为止,显然右边的n-i个编码位qj(j=i+1,…,n)都属于西部集合,将它们的值均加1,qi的值减1,而q1,q2,…,qi-1的值不变,此时得到的新编码即为所求邻域的编码。若找不到不属于西部集合的编码,则表明该栅格为西边界栅格,其西边邻域不存在。类似地,对其北边邻域的求解,也可从编码的末位qn按从右到左的顺序扫描,直到找到第一个不属于北部集合的编码qi(1≤i≤n-1)为止,显然右边的n-i个编码位qj(j=i+1,…,n)都属于北部集合,将它们的值均加2,qi的值减2,其余的不变,如此得到的新编码即为所求邻域的编码。若找不到不属于北部集合的编码,则表明该栅格为北边界栅格,其北边邻域不存在。
同理,若qn=1,2,3也很容易求得。
2.1.2边界像元相同尺寸邻域的确定
在确定边界像元的邻域之前,首先要做的工作是识别出待求像元是否为边界像元,这里的边界像元是指其部分邻域在研究区以外的情况,对于其部分邻域在背景叶结点集合中的情况,则需先求其相同尺寸邻域再判断此邻域是否在线性四叉树中。对于线性四叉树,笔者提出的方法是根据像元编码的所有数字属于N4、S4、W4、E4集合的种类多少来判断,若所属集合数≤2,则为边界像元;若>2则为非边界像元。如西边界像元编码数字全为0与2,东边界像元编码数字全为1与3。识别出边界像元之后,再根据其编码是属于N4、S4、W4、E4中哪一种或两种集合而判断其没有哪个边邻域、角邻域,对于存在的边邻域、角邻域则可仿照非边界像元的方法来求。
2.2相同尺寸角邻域的确定
同样,我们首先需要区分边界像元与非边界像元,不过在这里不再重复,方法同上,要做的是如何快速求出角邻域。一个简单的方法是通过求两次边邻域来确定。如要求西北角邻域,可以先求出西边邻域,再求西边邻域的北边邻域;或者先求北边邻域,然后求其西边邻域。我们把这种方法称为矢量合成法。
上述情况是对非边界像元而言的,对于边界像元的不同之处仅在于缺少某些邻域。上述算法可直接写成程序,实现起来非常简单。
2.3不同尺寸边邻域、角邻域的确定
我们的方法则是充分利用已求出的相同尺寸邻域来确定它。由于线性四叉树只记录物体叶结点的编码,因此,所求出的相同尺寸邻域的编码(记为B)在线性四叉树的物体叶结点集合中不一定存在。若B存在,则要依据层次编码的层次特性确定B的各级祖先结点或各级子孙结点中的哪一个存在于物体叶结点集中,所存在的祖先结点或子孙结点即为所求的不同尺寸邻域。这是一个搜索比较问题,由于编码的层次特性,各级祖先结点和子孙结点编码的前几位必与B的前几位相同,而且层次越高的祖先结点层数越少。另外由于我们最终要找到的是B在线性四叉树中的最高祖先结点或最大子孙结点,因此应按从高到低的顺序逐层扫描,一旦找到即可停止,以此来加快检测速度。若找不到任何祖先结点和子孙结点,或B本身不存在(或在研究区以外或属于背景叶结点集合),则所求的不同尺寸邻域一定不存在。
由此可见,在我们的方法中,不同尺寸邻域的确定只是一个对已求出的相同尺寸邻域的各级祖先结点或各级子孙结点在四叉树中的存在与否进行检测的问题,关键环节还在于直接、快速地求出相同尺寸的邻域。上面的求编码和检测步骤都是利用层次编码的层次性和大小性而进行的。
3结语
分析了线性四叉树编码的特性,并利用它发展了一种新的邻域寻找算法。该算法具有理解容易、实现简单、速度快捷的特点,并用实验进行了证实。相信本文提出的邻域寻找算法在二维图像分析、边界的确定及连通性判断等方面具有重要的意义。
参考文献
[1] 肖乐斌,孟鲁闽.建立八叉树的变长层次编码技术.地理信息世界,1996(2):11~14.
[2] 龚健雅.一种基于自然数的线性四叉树编码.测绘学报,1992,21(2):90~98.
转载注明来源:https://www.xzbu.com/8/view-1064499.htm
