Department of Computer Science, University of Maryland, College Park, MD 20742.
IEEE Trans Pattern Anal Mach Intell. 1985 Jan;7(1):94-8. doi: 10.1109/tpami.1985.4767622.
Many standard image processing operations can be implemented using quadtrees as a simple tree traversal where, at each terminal node, a computation is performed involving some of that node's neighbors. Most of this work has involved the use of bottom-up neighbor-finding techniques which search for a nearest common ancestor. Recently, top-down techniques have been proposed which make use of a neighbor vector as the tree is traversed. A simplified version of the top-down method for a quadtree in the context of a general-purpose tree traversal algorithm is presented. It differs, in part, from prior work in its ability to compute diagonally adjacent neighbors rather than just horizontally and vertically adjacent neighbors. It builds a neighbor vector for each node using a minimal amount of information. Analysis of the algorithm shows that its execution time is directly proportional to the number of nodes in the tree. However, it does require some extra storage. Use of the algorithm leads to lower execution time bounds for some common quadtree image processing operations such as connected component labeling.
许多标准的图像处理操作可以使用四叉树作为一种简单的树遍历来实现，其中在每个终端节点处执行涉及该节点的一些邻居的计算。这项工作大多涉及使用自底向上的邻居查找技术来搜索最近的公共祖先。最近，提出了一种自顶向下的技术，该技术在遍历树时使用邻居向量。本文提出了一种简化的自上而下的方法，用于在通用树遍历算法的背景下进行四叉树。它与以前的工作的不同之处在于，它能够计算对角线相邻的邻居，而不仅仅是水平和垂直相邻的邻居。它使用最少的信息量为每个节点构建一个邻居向量。对算法的分析表明，它的执行时间与树中的节点数成正比。但是，它确实需要一些额外的存储空间。该算法的使用导致了一些常见的四叉树图像处理操作（例如连通分量标记）的更低的执行时间限制。
