Department of Computer Science, University of Maryland, College Park, MD 20742.
IEEE Trans Pattern Anal Mach Intell. 1985 Feb;7(2):229-40. doi: 10.1109/tpami.1985.4767646.
The region quadtree is a hierarchical data structure that finds use in applications such as image processing, computer graphics, pattern recognition, robotics, and cartography. In order to save space, a number of pointerless quadtree representations (termed linear quadtrees) have been proposed. One representation maintains the nodes in a list ordered according to a preorder traversal of the quadtree. Using such an image representation and a graph definition of a quadtree, a general algorithm to compute geometric image properties such as the perimeter, the Euler number, and the connected components of an image is developed and analyzed. The algorithm differs from the conventional approaches to images represented by quadtrees in that it does not make use of neighbor finding methods that require the location of a nearest common ancestor. Instead, it makes use of a staircase-like data structure to represent the blocks that have been already processed. The worst-case execution time of the algorithm, when used to compute the perimeter, is proportional to the number of leaf nodes in the quadtree, which is optimal. For an image of size 2n × 2n, the perimeter algorithm requires only four arrays of 2n positions each for working storage. This makes it well suited to processing linear quadtrees residing in secondary storage. Implementation experience has confirmed its superiority to existing approaches to computing geometric properties for images represented by quadtrees.
四叉树区域是一种分层数据结构，在图像处理、计算机图形学、模式识别、机器人学和制图学等应用中都有使用。为了节省空间，已经提出了许多无指针的四叉树表示形式（称为线性四叉树）。有一种表示形式按照四叉树的先序遍历将节点保存在一个列表中。使用这种图像表示形式和四叉树的图形定义，开发并分析了一种用于计算图像的几何属性（例如周长、欧拉数和连通分量）的通用算法。该算法与传统的基于四叉树表示的图像方法不同，它不使用需要找到最近公共祖先的邻居查找方法。相反，它使用类似于楼梯的数据结构来表示已经处理过的块。当用于计算周长时，该算法的最坏情况执行时间与四叉树中的叶节点数成正比，这是最优的。对于大小为 2n×2n 的图像，周长算法仅需要四个大小为 2n 的数组用于工作存储。这使其非常适合处理位于辅助存储中的线性四叉树。实现经验证实了它在计算基于四叉树表示的图像的几何属性方面的优越性。
