线性四叉树和线性八叉树邻域寻找的一种新算法

肖乐斌

(中国科学院地理信息产业发展中心，北京，100101)

龚建华

(香港中文大学地理系，地球信息科学联合实验室，香港)

谢传节

(中国科学院地理所资源与环境国家重点实验室，北京，100101)

A NEW ALGORITHM FOR SEARCHING NEIGHBORS IN THE LINEAR QUADTREE AND OCTREE

Xiao Lebin

Center for GIS Industry Development, Chinese Academy of Sciences,Beijing, 100101

Gong Jianhua

Department of Geography & Joint Laboratory for Geoinformation Science，
The Chinese University of Hong Kong，Shatin, New Territories, Hong Kong

Xie Chuanjie

State Key Lab of Resource and Environment,
Inst of Geography, Chinese Academy of Sciences, Beijing, 100101

Abstract In this paper, based on the analyses of algorithms for searching neighbor pixels in linear quadtrees and neighbor octants in linear octrees and deeply studying on the characters of codes in linear quadtrees or octrees, such as direction, hierarchy, compressibility and size difference characters, a new searching algorithm is presented, which is directly in light of the code number and doesn’t use the comparison method described in fore researchers’ algorithms any more. For the searching of same size neighbors of a code, only a few rear digits of the code need to be checked. For the searching of different size neighbors of a code, based on the acquired same size neighbor code, only a few fore digits of the code need to be checked in light of the hierarchy and size difference character of codes in linear quadtrees and octrees. Because of its simple structure, this algorithm is easy to understand for readers and realize on computers, with a character of consuming time less. For the searching of a part of neighbors, only one time adding or subtracting operation is enough. The experiment results verify that the new algorithm is correct, simple and less consuming time.

Key words linear quadtrees linear octrees neighbors

摘要 本文在对目前线性四叉树、八叉树邻域寻找算法进行分析的基础上,通过分析这两种数据结构编码的特性（方向性、层次性、可压缩性及大小性），提出了一种直接利用象元和3D栅格的编码求其邻域的新算法。这种算法在求相同尺寸邻域时，仅需扫描编码的后几位，而在求不同尺寸邻域时，则直接在已求出的相同尺寸邻域的基础上，利用编码的层次性和大小性寻找此邻域的各级祖先结点和各级子孙结点，且仅需扫描此邻域编码的前几位。该算法结构简单，易于理解和实现，且寻找速度快、准确。对于部分邻域的寻找，只需一步加减运算即可完成。最后用实验证明了本方法的正确性。

关键词 线性四叉树 线性八叉树 邻域

1 引言

线性四叉树与八叉树都是只记录叶结点的编码,而不记录中间结点的编码及层次关系,由于它比普通四叉树、八叉树大大节省了存储空间，且蕴含有层次特性，因此它在实际工作中得到了广泛的应用。邻域的确定在二维图象分析、三维实体分析、边界的确定及连通性判断等方面具有重要的意义。另外，邻域实质上是一种拓扑关系,邻域的寻找在一定程度上说,也就是在2D或3D栅格结构中确定物体间的拓扑关系。因此,寻找某一像元、某一3D栅格的邻域也就成了克服栅格结构中拓扑关系不清晰及栅格矢量数据结构相互转换难点的一种新思路。因此,邻域寻找成为许多学者研究的重点之一。

Samet等提出的邻域寻找方法是基于指针四叉树镜面反射的思想，首先通过逐层上升寻找到共同祖先，然后以此为转折点逐层下降到满足条件的邻接象元。显然，这种方法的麻烦之处在于求任一邻域时总要通过最小公共祖先来进行，这就显得不够直接，耗时较多，不适合线性四叉树(H.Samet,1982)。虽然他在1989年又提出了在指针八叉树和线性八叉树中寻找各种邻域的算法，但其主要思想仍然是利用逐层上升和作者自定义的反射函数寻找最近公共祖先和邻域(H.Samet,1989)。文献[3]通过分析和充分利用线性四叉树编码的位置特征,提出了一种较为简单、快捷且容易推广到八邻域寻找领域的一种新算法,但笔者认为,该方法主要是通过比较判断法来确定某一象元是否是一待求象元的邻域,这样的思路导致了为寻找某一象元的邻域，在最坏情况下必须对整个图象进行遍历。对于一幅n×n维图象,为确定一象元的邻域就可能需要进行n2(n2-1)次判断,显然这种方法的效率仍然较低,对于线性八叉树就需要更多的机时和空间了。张田文等在其提出的四值逻辑编码的基础上提出了一种较为有效的寻找算法(张田文,李仲,1989),但该算法是根据按阶异步映射原理，先计算出各个可能的邻接象元，再按照一定的条件判断这些象元是否为其邻接象元。这种方法用的仍是比较判断法，只是将比较判断的范围缩小了。文献[5]是在Peano编码[5][6] 的基础上，利用一系列迭代公式直接求出相同尺寸和大尺寸邻域的，虽然没有再用比较判断法，但其算法较为复杂。我们认为，文献[5]中N模式Peano码的层次关系、大小关系并不清晰和直观，不便于理解和编程实现。针对上述各种方法的种种不足之处，笔者作了认真的思考, 结合前期做的工作, 依据层次编码[7]的特性提出了一种更为快速简单的新算法。该方法根据待求栅格的编码直接求出其所有邻域，算法结构简单，易于理解，耗时少。文献[5]对每一个邻域（东西南北上下邻域）都要进行迭代计算，我们只需计算部分邻域，且计算时仅扫描后几位，对另一部分只需一步加减运算即可完成。另外，在求大尺寸邻域时，我们是在已求出的相同尺寸邻域的基础上，充分利用层次编码中所蕴涵的层次性与大小性，直接检查可能包含此邻域的大尺寸编码在四叉树和八叉树中是否存在，而不需要象文献[5]那样在求大尺寸邻域时再一次进行迭代计算后来检查。求小尺寸邻域的情况与此类似。
2 线性四叉树和线性八叉树的几个概念和约定

2.1 几个概念

2.11 线性四叉树的邻域

邻域分为两种,一种是边相邻的邻域,称为边邻域,又因为在二维图象中任一象元都有四个边邻域,因此又称为四邻域,另一种是角对角的邻域,称为角邻域。将边邻域和角邻域加起来,任一象元上的邻域都有八个,故也称之为八邻域。如图1所示：



图1中象元21的北边邻域为03,东边邻域为3,其西南角邻域为22。

2.12 线性八叉树的邻域

它的邻域则分为三种:面相邻的面邻域、边相邻的边邻域、角相邻的角邻域,如图4(b)所示:333为337的面邻域, 330 为333的边邻域,330为337的角邻域。

线性八叉树任一栅格的面邻域有6个,边邻域有12个，角邻域有8个,共26个邻域。

2.13 边界象元、3D栅格与非边界象元、3D栅格

边界象元是指处于边界上的象元，如图4(a)中象元022、100、133、233等都是边界象元，它们的共同特点是在其各个邻域中总有一个或一个以上的邻域不存在，即这些邻域或是在研究区以外，或是在背景叶结点集中。如022象元的西边邻域、100象元的北边邻域不存在（在研究区以外）。除了边界象元以外，剩下的都是非边界象元，非边界象元的各个邻域都存在。边界3D栅格与非边界3D栅格的定义与此类似。

2.14 相同尺寸和不同尺寸邻域

相同尺寸邻域是指待求邻域的尺寸与原象元、3D栅格的尺寸相同，不同尺寸邻域则指待求邻域的尺寸与原象元、3D栅格的尺寸不同，或大或小。例如，图1中象元03是象元21的相同尺寸北边邻域，象元3则是象元21的不同尺寸（或说大尺寸）邻域，图4(b)中3D栅格310、311都是3D栅格13的小尺寸南面邻域。

2.2 几个简单约定

为了后面论述方便,笔者在这里先作几个简单约定：

2.21 对于四叉树编码基准体系的划分



图2 线性四叉树和线性八叉树的编码基准

Fig.2 the encoding standard in the linear quadtree and octree

如图2(a)所示,线性四叉树的编码基准体系划分为如下几个集合：

北部N4={0,1}, 南部S4={2,3},

西部S4={0,2}, 东部E4={1,3}

且边邻域分别称之为E邻域,S邻域,W邻域,N邻域,例如象元1是象元0的E邻域,角邻域分别称为东南角邻域,东北角邻域,西南角邻域,西北角邻域,例如象元3是象元0的东南角邻域。

2.22 对于八叉树编码基准体系的划分

如图2(b)所示,线性八叉树的编码基准体系划分为:

北部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}

类似于四叉树,八叉树的面邻域分为东面、西面、南面、北面、上面、下面邻域,例如栅格2的下面邻域是6;其边邻域可分为东上,东下、西上、西下、南上、南下、北上、北下、东北、西北、东南、西南边邻域,例如栅格7的西北边邻域为栅格4,西上邻域为栅格2,其角邻域分为8个,它们是西北上、西北下、东北上、东北下、东南上、东南下、西南上和西南下角邻域,例如栅格6的东北上邻域为栅格1。

虽然,上述几个约定看起来较为简单,但它们为后面寻找不同尺寸邻域、边界栅格等复杂操作提供了极大的方便,保证了数学上的严密性。

3 线性四叉树和线性八叉树层次编码特性剖析

3.1线性四叉树和线性八叉树的层次编码

如图3所示,对包围物体的区域进行二值分割,设分割次数为3,则得到3层,

其编码如图3(c)所示：







图3 对包围物体的最小矩形区域的线性四叉树编码

Fig.3 the linear quadtree encoding for the smallest rectangle containing the object

由图可见,线性四叉树的编码有如下特性：

方向性 按照图3(a)中的编码基准,编码大小总是按由西向东,由北向南的顺序递增的。

层次性 第n层象元的四进制编码应为

q1q2...qn,qiÎ{0,1,2,3},i=1,2,3...,nÎ{0,1,2,3},i=1,2,3...,n

在这些编码中,处在第1位的是第1层,第2位是第2层,第n位是第n层(第n次分割),如图3(c)中的321象元,因为第一位q1=3按照图3(a)的参考基准,表示该象元在第1层中的位置为3,同样第2层的位置为2,第3层的位置为1。

(3)可压缩性 由编码可知,每一个象元q1,q2,...,qn都需要n个字节来存贮,这显然有点浪费存贮空间,为此可采用位运算法将其转为十进制码以进一步压缩,如对四进制编码为321的象元有:

(321)4=3*42+2*4+1=57

(4)大小性 对于四进制码和十进制码之间的相互转换，文献[8]作了详细的论述。

显然,编码的位数越多,深度越大,层次越低,象元尺寸越小,如图3(c)中编码为2的象元的尺寸分别是编码为30的象元尺寸、编码为321象元尺寸的2倍和4倍。上述情况可完全扩展到线性八叉树。

八叉树的层次编码与此类似，对于其特性,笔者在文献[7]中已作了较为详尽的论述,这里不再赘述。

综上所述,由于线性四叉树、线性八叉树编码所具有的这些特性为我们寻找邻域提供了一种新的线索和思路,因而我们在这里详细介绍了这些编码所蕴涵的特性。

4 线性四叉树邻域的确定

前面说过,我们寻找邻域的思路是根据待求栅格的编码直接求出其所有邻域,而不是如文献[3]通过判断的方式来确定邻域。正如前面指出的那样,线性四叉树的编码本身就包含有方向性、层次性、大小性等寻找邻域时所需要的特性,于是如何发掘并将它灵活运用到邻域的寻找上便成了解决问题的关键。

4.1相同尺寸边邻域的确定

4.1.1非边界象元的相同尺寸邻域的确定

让我们先看一幅经过过3次分割得到的一幅大小为23*23的图象,如图4(a)所示。

对于任一非边界象元A=q1q2...qn, qn为四进制数,其东西南北四个边邻域可按如下规则确





图4 分割次数为3的线性四叉树和线性八叉编码

Fig.4 the encoding in the linear quadtree and octree with 3 times subdividings

定:

若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的值不变，此时得到的新编码即为所求邻域的编码。(若找不到不属于西部集合的编码，则表明该栅格为西边界栅格，其西边邻域不存在。) 该栅格与其邻域编码的差值也可计算如下：

， l为整型变量，下同。

类似地，对其北边邻域的求解，也可从编码的末位qn按从右到左的顺序扫描，直到找到第一个不属于北部集合的编码qi(1≤i≤n-1)为止，显然右边的n-i个编码位qj(j=i+1,...,n)都属于北部集合，将它们的值均加2，qi的值减2，其余的不变，如此得到的新编码即为所求邻域的编码。(若找不到不属于北部集合的编码，则表明该栅格为北边界栅格，其北边邻域不存在。) 也可用如下计算式直接求得：



同理，若 qn =1, 则西边邻域为A-1,南边邻域为A+2，其东边邻域为



其北边邻域则为



若 qn =2, 则北边邻域为A-2,东边邻域A+1,南边邻域为



西边邻域为



若 qn =3, 则西边邻域为A-1,北边邻域A-2,南边邻域为



东边邻域为



由上可见,上述邻域确定算法非常简单,仅需先对编码的后几位扫描即可实现,而且有的邻域只需一步加减运算即可求出。这种算法充分利用了线性四叉树层次编码的方向性。

4.1.2边界象元相同尺寸邻域的确定

在确定边界象元的邻域之前,我们首先要做的工作是识别出待求象元是否为边界象元（这里的边界象元是指其部分邻域在研究区以外的情况，对于其部分邻域在背景叶结点集合中的情况，则需先求其相同尺寸邻域再判断此邻域是否在线性四叉树中。后面线性八叉树的边界栅格与此类似）。对于线性四叉树,笔者提出的方法是根据象元编码的所有数字属于N4、S4、W4、E4集合的种类多少来判断,若所属集合数≤2,则为边界象元;若＞2则为非边界象元。如西边界象元编码数字全为0与2,东边界象元编码数字全为1与3。

识别出边界象元之后,再根据其编码是属于N4、S4、W4、E4中哪一种或两种集合而判断其没有哪个边邻域、角邻域,对于存在的边邻域、角邻域则可仿照非边界象元的方法来求。如边界象元101,其邻域情况为:

北边邻域不存在,西边邻域为100,东边邻域为110,南边邻域为103，

西北角、东北角邻域不存在,西南角邻域为102,东南角邻域为103。

4.2 相同尺寸角邻域的确定

同样,我们首先需要区分边界象元与非边界象元,不过在这里我们不再重复,方法同上,我们要做的是如何快速求出角邻域。一个简单的方法是通过求两次边邻域来确定。如要求西北角邻域，我们可以先求出西边邻域，再求西边邻域的北边邻域，或者先求北边邻域然后求其西边邻域。我们把这种方法称为矢量合成法，如图5 (a)所示。



图5 线性四叉树和线性八叉树邻域寻找的矢量合成法

Fig.5 the vector operation method for the neighbor searching in the linear quadtree and octree

上述情况是对非边界象元而言的,对于边界象元的不同之处仅在于缺少某些邻域。上述算法可直接写成程序,实现起来非常简单,这里不再列出程序流程图。

4.3 不同尺寸边邻域、角邻域的确定

文献[3]是通过比较小象元比大象元多出的后面几位编码是否满足一定条件来判断的, 文献[5]则要再一次进行迭代运算求出大尺寸邻域的编码，然后判断此编码是否在四叉树中。我们的方法则是充分利用已求出的相同尺寸邻域来确定它。由于线性四叉树只记录物体叶结点的编码,因此,所求出的相同尺寸邻域的编码（记为B）在线性四叉树的物体叶结点集合中不一定存在。若B存在, 则要依据层次编码的层次特性确定B的各级祖先结点或各级子孙结点中的哪一个存在于物体叶结点集中,所存在的祖先结点或子孙结点即为所求的不同尺寸邻域。这是一个搜索比较问题，由于编码的层次特性，各级祖先结点和子孙结点编码的前几位必与B的前几位相同，而且层次越高的祖先结点层数越少，另外由于我们最终要找到的是B在线性四叉树中的最高祖先结点或最大子孙结点，因此我们应按从高到低的顺序逐层扫描，一旦找到即可停止，以此来加快检测速度。若找不到任何祖先结点和子孙结点，或B本身不存在（或在研究区以外或属于背景叶结点集合），则所求的不同尺寸邻域一定不存在。

由此可见，在我们的方法中，不同尺寸邻域的确定只是一个对已求出的相同尺寸邻域的各级祖先结点或各级子孙结点在四叉树中的存在与否进行检测的问题，关键环节还在于直接、快速地求出相同尺寸的邻域。上面的求编码和检测步骤都是利用层次编码的层次性和大小性而进行的。

5 线性八叉树邻域的确定

至此为止,我们已经全面论述了线性四叉树边角邻域的确定方法,线性八叉树的邻域确定方法与之类似。虽然它在编码方面是线性四叉树编码向3D方面的直接扩展,但在确定邻域上要比2D四叉树复杂很多。我们在这里只阐述八叉树邻域确定方法的关键部分,对于二者的相同之处只作略微提示。

5.1边界栅格识别

如图5(b)所示,对于任一象元A=o1o2...on, oi为八进制整数,我们首先判断其是否为边界栅格,若

" oiÎ E8 或 " oiÎ S8 或 " oiÎ W8

" oiÎ N8 或 " oiÎ U8 或 " oiÎ D8 ， " 表示全部


 
 

则在面邻域中,其对应的E邻域或S邻域或W邻域或N邻域或U邻域或D邻域将分别不存在。对于边邻域、角邻域存在与否的情况,读者可自行推之。

识别出边界栅格后,我们就知道了哪些邻域不存在,是不用求的。而对于存在的邻域,我们按下面节5.2中的方法来求。

5.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的值不变，此时得到的新编码即为所求邻域的编码。(若找不到不属于上部集合的编码，则表明该栅格为上边界栅格，其上邻域不存在。) 其与邻域编码的差值也可计算如下：

， l为整型变量，下同。

差值的正负号要根据其方向性而定,这里因求的是上面邻域，因此应给以负号。

类似地，若qn属于下部集合,则其上面邻域为A-4，对其下面邻域的求解，也可从编码的末位qn按从右到左的顺序扫描，直到找到第一个不属于下部集合的编码qi(1≤i≤n-1)为止，显然右边的n-i个编码位qj(j=i+1,...,n)都属于下部集合，将它们的值均减4, qi的值加4，其余的不变，如此得到的新编码即为所求邻域的编码。(若找不到不属于下部集合的编码，则表明该栅格为下边界栅格，其下邻域不存在。) 也可用如下计算式直接求得：



下面给几个例子,

(1) U8、D8结合部处的栅格732

与下邻域编码之差为732-736 = -4，与上邻域编码之差为:

(732)8-(376)8=(400)8-(44)8=4*82-(4*8+4)

若进一步分割得(7322)8，其与上邻域编码之差为:

8 - (3766)8 = (4000)8 - (444)8 = 4*83 - (4*82+4*8+4)
其与下邻域之差为(3722)8 - (3726)8 = -4

(2) 非U8、D8结合部的栅格372

与上邻域之差为(372)8 - (336)8 = (40)8 - (4)8，与下邻域之差为(372)8 - (376)8 = -4

若进一步分割得(3722)8, 其与上邻域之差为:

(3722)8 - (3366)8 = (722)8 - (366)8 = (400)8 - (44)8,

其与下邻域之差为(3722)8 - (3726)8 = -4

值得注意的是,上述编码均为八进制数,读者不要与十进制数混淆。

5.3 相同尺寸边邻域、角邻域的确定

线性八叉树边邻域的情况类似于线性四叉树的角邻域,可采用2D平面矢量合成法,用两次求面邻域的方法来求,如图5(b)所示。其角邻域的确定则较复杂,需用到3D矢量合成法,即一次求边邻域, 一次求面邻域，实质上它最终可分解为三次求面邻域：南北面邻域,东西面邻域，上下面邻域，如图5(c)所示。

5.4 不同尺寸邻域的确定

确定方法完全同于线性四叉树的方法。

6 实验

我们在微机windows NT4.0环境下用Visual C++4.2进行了实验，得到线性八叉树邻域

寻找的结果如表一、表二所示。

由表可见，对于任一栅格，我们都可以直接快速地求出其邻域，限于篇幅，这里只列出部分栅格的邻域寻找结果。表中-1表示该邻域不存在。

表一 经过三次分割得到的线性八叉树邻域确定

Tab.1 the result of searching neighbors in the linear octree with 3 times subdividings

编码 邻域
北面邻域
南面邻域
西面邻域
东面邻域
上面邻域
下面邻域

000
-1
002
-1
001
-1
004

323
321
-1
322
332
-1
327

366
364
-1
277
367
362
722

562
560
740
473
563
526
566

...
...
...
...
...
...
...

716
714
734
707
717
712
752


表二 经过五次分割得到的线性八叉树邻域确定

Tab.2 the result of searching neighbors in the linear octree with 5 times subdividings

编码 邻域
北面邻域
南面邻域
西面邻域
东面邻域
上面邻域
下面邻域

03534
03516
03536
03525
03535
03530
03570

10377
10375
12155
10376
11266
10373
10733

36606
36604
36624
27717
36607
36602
36642

67226
67224
-1
66337
67227
67222
67262

...
...
...
...
...
...
...

73313
73311
73331
73312
-1
37757
73317


7 结论

本文较完整地分析了线性四叉树和线性八叉树编码的特性(层次性、方向性、大小性及可压缩性),并利用它发展了一种新的邻域寻找算法。与前人的方法相比,该算法具有理解容易、实现简单、速度快捷的特点,并用实验进行了证实。相信本文提出的邻域寻找算法在二维图象分析、三维实体分析、边界的确定、三维拓扑关系的确定及连通性判断等方面具有重要的意义。

参 考 文 献

1 H. Samet, Neghbor finding technqnes for image represented by quadtrees, Computer

Graphics and Image Processing,,1982,18(3):37~57

2 H. Samet, Neighbor finding in images represented by octrees ,Computer

Vision ,Graphics, and Image Processing,1989,46,367~386

3 刘钦,晏明辉,二值图象邻域寻找的一种快速方法,计算机应用与软件,1997,5:32~36

4 张田文,李仲 ,计算线性四元树表示的二值图象Euler数的图论方法,计算机学

报,1989,9:682~688

5 Rongxing Li and Changshi Xu, An algorithm for searching boundary octants in 3D

geological subsurface modeling, Geographic Information Sciences, 1995 ,1(1):23~33

6 Gargantini, I., Linear octrees for fast processing of three dimensional objects,

Computer Graphics and Image Processing, 1982,20:365~374

7 肖乐斌,孟鲁闽,建立八叉树的变长层次编码技术,地理信息世界,1996,2:11~14

8 龚健雅,一种基于自然数的线性四叉树编码,测绘学报,1992,21(2):90~98