线性四叉树的一种改进最优构造算法.pdfVIP

1992年第1期 计算机辅助设计与图形学学报 ·1· 线性四叉树的一种改进最优构造算法 周洞汝 插 第 (武汉水利电力学院计算机及电子工程系-武汉-鹳O0lf2) (中国科学院计算技术研究所c^D开放实验室，北京，100~0) 擅妻，本文讨论 了线性四又树的一种新的构造算法。试算法是在文献C3)帕最优四又树构 造善法基础上，进一步减少 了构造过程 中需插入的结点数菔辅|助存储空间。它请助于一种新 的圈象数据结构——数字捷索树作为中同精 出结构，目而具有更高的效率。 美■调t线性四叉树，四叉树构造，数字有哪些信誉好的足球投注网站树。 一 、 引 言 四叉树是一种常用的表这二维图象的数据绪梅。它枉敷据压缩、 目标表选及落算辱方面 有着独特的优点而得到广泛的应用(1】。应用四叉树的前提是建立高教的柯遣算法，l；梗【由原 始的二元敷组表示的图象转换为相应 的四叉树。 近年来已有不少文章讨论四叉树的构造算法。较早的如t9e1年Samet在文献 (2)中提 出 的算法。这种算法采用l韵主要是插入及合并策略，即抱图象中的每一象索均插入 出树的适 当位置，然后通过合并成为教大的四叉树的结点。算法的复杂度取决于与象素数成 比倒l的插 入操作数。1987年ShaHer与S8me￡提出了一种最忧四叉树构造算法(|]，这种算法在构造过 程中不再需要台并策略并减少了插入操作，其时闻复杂度只取决于与四叉树结点嫂l 倒的插 入操作数，因而大大提高了效率。 本文是对文献C0)中的最优构造算法的改进 逭种算法进一步减少了插入结点的数量，减 少了中间辅助存储空间，并借助于一种新的图象数据结梅——数字有哪些信誉好的足球投注网站树作为中问结梅，因 而它具有更高的效率。 二、线性四叉树及基本定义 对图I(8)所示的二值图象，可给出下面与本算j击有关的基本定义。 1．图象中_以0标识 的象索为背景色，称为 白象素，以1标识的象素表示 目标 图象 ，称 为 黑象素 每一象素位置可用其坐标 (i，j)表示，并设坐标系的原点在左上带 (图l(a))。 2．对 图1《a)所示正方形图象可划为四个正方形子区，称为四分区。此划分可递 归 地 进行下击。每一四分区称为一个结点。如果 四分区全由白象素梅成则称为 自结点，如果全由 本文于I991年7月收到。一酒寰-I938年生-l961年毕业于华南工学院，教授，目前主要从事计算机图形翠、羲举嚣 据可视化及医学匿象处理等方面的研究工作 黑象素构成则称为黑结点 |如果 四分区中既包含 白象素叉包含黑象素则称为灰结点。对灰结 点要继续划分直至结点全 由黑象素或 白象素构成 (图1(b))。全部黑结点构成 目标图象。 0}0 O o1Dl01 OfO 0 ol010l O}D O 1I】1I a-0 0 】 【】1 O【O0 1lLlII o10 J 】l】I】l 0J0 1 I10l0l O10 1 oIOl0I 图I=值图象及其四叉树表示 3．对于 四分 区表达 的图象可转化为图1(c)所示的四叉树表示 。四叉树阿层次LV(Leve1) 对应 四分 区的划分次数。如 四叉树 的根为0层 ，对应0次划分，以后依次为 1层 、1次划分，… n--1层、n一1次划分等。四叉树的层次反映了四分区的大小。为反映结点的大小，我们定义 一 参数组合 因子GF(GrouP Factor)，对 四叉树第i层的结点，其GF=n—i，结点共含有 4 个‘象素，对应的四分区为i一四分区。 4．四叉树的每一结点可 以用四进制整数编码 。设任一四分区所划分的四个子区的位置码 分别用四进制数表示为；NW 一0，NE-t，SW一2，SE-3，则任一象素的四进制码可表示为I Q-=qn 1q口：…q。 I…q。， 1≤i≤n 式 中q 为第1次划分时的位置码 ，q 一为第i次划分时的位置码，qo为第12次划分 时 的 位置码 。 四叉树第i层