线性四叉树邻域寻找新算法.docVIP

线性四叉树邻域寻找新算法 　　摘要:提出了一种直接利用像元的编码求其邻域的新算法。这种算法在求相同尺寸邻域时,仅需扫描编码的后几位,而在求不同尺寸邻域时,则直接在已求出的相同尺寸邻域的基础上,利用编码的层次性和大小性寻找此邻域的各级祖先结点和各级子孙结点,且仅需扫描此邻域编码的前几位。该算法结构简单,易于理解和实现,且寻找速度快、准确。对于部分邻域的寻找,只需一步加减运算即可完成。 　　关键词:线性四叉树 邻域 边界像元 　　 　　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边界像元相同尺寸邻域的确定 　　 在确定边界像元的邻域之前,首先要做的工作是识别出待求像元是否为边界像元,这里的边界像元是指其部分邻域在研究区以外的情况,对于其部分邻域在背景叶结点集合中的情况,则需先求其相同尺寸邻域再判断此邻域是否