Linear-time border-tracing algorithms for quadtrees

In applications where the quadtree is used as an underlying object representation, a number of basic operations are implemented as a trace along the border of the object's region. A technique is presented that determines a way to shift any given scene (as well as its quadtree), so that the border of all the objects in the scene can be traversed in time proportional to the length of all the borders in the scene (or the number of blocks when the scene is represented as a quadtree). This determination is shown to be performed in time proportional to the length of all the borders in the scene. This allows the direct translation of a number of chain-code algorithms into quadtree algorithms without loss of asymptotic worst-case efficiency. This results in improved worst-case analyses of algorithms that convert chain codes into quadtrees and that perform connected component labeling of images represented as quadtrees.     

Computing geometric properties of images represented by linear quadtrees

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.     

Path-Length distances for quadtrees

A distance measure is defined for a quadtree representation of a binary image. An algorithm is presented that calculates the distance from the center of each black node to the border of the nearest white node. The distance is defined as the path length from the center of the black node, through the center of intervening black nodes, to the white border. The worst-case average execution time is shown to be proportional to the product of the logarithm of the image diameter and the number of blocks in the image.     

Distance transform for images represented by quadtrees

The concept of distance used in binary array representations of images is adapted to a quadtree representation. The chessboard distance metric is shown to be particularly suitable for the quadtree. A chessboard distance transform for a quadtree is defined as the minimum distance in the plane from each BLACK node to the border of a WHiTE node. An algorithm is presented which computes this transform by only examining the BLACK node's adjacent and abutting neighbors and their progeny. However, unlike prior work with quadtrees, computation of the distance transform requires a capability of finding neighbors in the diagonal direction rather than merely in the horizontal and vertical directions. The algorithm's average execution time is proportional to the number of leaf nodes in the quadtree.     

A Constant-Time Algorithm for Finding Neighbors in Quadtrees

Quadtrees and linear quadtrees are well-known hierarchical data structures to represent square images of size 2^{r} times 2^{r}. Finding the neighbors of a specific leaf node is a fundamental operation for many algorithms that manipulate quadtree data structures. In quadtrees, finding neighbors takes O(r) computational time for the worst case, where r is the resolution (or height) of a given quadtree. Schrack [1] proposed a constant-time algorithm for finding equal-sized neighbors in linear quadtrees. His algorithm calculates the location codes of equal-sized neighbors; it says nothing, however, about their existence. To ensure their existence, additional checking of the location codes is needed, which usually takes O(r) computational time. In this paper, a new algorithm to find the neighbors of a given leaf node in a quadtree is proposed which requires just O(1) (i.e., constant) computational time for the worst case. Moreover, the algorithm takes no notice of the existence or nonexistence of neighbors. Thus, no additional checking is needed. The new algorithm will greatly reduce the computational complexities of almost all algorithms based on quadtrees.     

Space and time efficient virtual quadtress

The quadtree has recently become a major data structure in image processing. This correspondence investigates ways in which quadtrees may be efficiently stored as a forest of quadtrees and as a new structure we call a compact quadtree. These new structures are called virtual quadtrees because the basic operations we expect to perform in moving about within a quadtree can also be performed on the new representations. Space and time efficiency are investigated and it is shown these new structures often given an improvement in both.     

Optimal quadtree construction algorithms

An algorithm is presented that builds a quadtree in time proportional to the number of blocks in the image. In particular, this algorithm constructs a linear quadtree from a raster image stored on disk in time proportional to the number of nodes in the output quadtree plus the (relatively minor) amount of time to read the input data. Empirical tests show that for typical 512 × 512 pixel images, the new algorithm results in an order of magnitude or better improvement over traditional algorithms which insert each pixel separately and require a merge routine to form larger nodes. These traditional algorithms have an execution time that is proportional to the number of pixels in the image. Thus, when using the number of insertions into the output quadtree as a metric, our algorithm is optimal to within a constant factor. The algorithm is also adapted to build a pointer-based quadtree, again without a need to merge any nodes.     

Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees

A variant of the plane-sweep paradigm known as topological sweep is adapted to solve geometric problems involving two-dimensional regions when the underlying representation is a region quadtree. The utility of this technique is illustrated by showing how it can be used to extract the boundaries of a map inO(M) space andO(M(M)) time, whereM is the number of quadtree blocks in the map, and(·) is the (extremely slowly growing) inverse of Ackerman's function. The algorithm works for maps that contain multiple regions as well as holes. The algorithm makes use of active objects (in the form of regions) and an active border. It keeps track of the current position in the active border so that at each step no search is necessary. The algorithm represents a considerable improvement over a previous approach whose worst-case execution time is proportional to the product of the number of blocks in the map and the resolution of the quadtree (i.e., the maximum level of decomposition). The algorithm works for many different quadtree representations including those where the quadtree is stored in external storage.M. B. Dillencourt was supported in part by a UCI Faculty Research Grant, and H. Samet was supported in part by the National Science Foundation under Grant IRI-90-17393.     

Boundary matching algorithm for connected component labelling using linear quadtrees

A computationally fast top-down recursive algorithm for connected component labelling using linear quadtrees is presented. The input data structure used is a linear quadtree representing only black leaf nodes. The boundary matching approach used ensures that at most two adjacencies of any black leaf node are considered. Neighbour searching is carried out within restricted subsets of the input quadtree. The time and space complexities of the algorithm are O(Bn) and O(B) respectively for a linear quadtree with B black leaves constructed from a binary array of size 2ⁿ × 2ⁿ. Simulations show the algorithm to be twice as fast as an existing algorithm that uses an identical input data structure. The top-down algorithm presented can also be used to efficiently generate a linear quadtree representing all nodes — ‘grey’, ‘black’ and ‘white’ — in preorder when given an input linear quadtree representing only ‘black’ leaf nodes. The boundary matching algorithm is computationally fast and has low static and dynamic storage costs, making it useful for applications where linear quadtrees are held in main memory.     

On encoding boundaries with quadtrees

The ``line quadtree' data structure hierarchically represents a region and its boundary. Based on the standard quadtree, each node in this structure stores adjacency information as well. While line quadtrees use the same amount of space as standard qaudtrees, they facilitate several region processing algorithms. In particular, we describe efficient algorithms for boundary and superimposing two maps encoded as line quadtrees.     

基于联合最佳基小波包的图像融合方法

基于联合最佳基小波包理论提出了一种新的图像融合方法。该方法首先将所有图像进行小波包分解,得到各自对应的四叉树,将各四叉树节点对应系数平方相加得到一个新的四叉树,利用此平方和四叉树搜索联合最佳基。将待融合图像基于联合最佳基分解,把分解系数加权处理得到融合系数,利用融合系数进行逆变换即得到融合图像。该方法对所有待融合图像的分解都是最佳分解,解决了先前最佳小波包融合方法只能最佳分解一方待融合图像的问题。将该方法与其他主要图像融合方法进行了比较分析,结果表明基于联合最佳小波包基的图像融合方法是非常有效的。     

Multi-colored quadtrees for GIS: Exploiting bit-parallelism for rapid boolean overlay

A number of tesselation based GIS using quadtrees as the underlying data structure have been constructed in recent years. At present there is an almost universal trend towards the representation of a thematic layer as a collection of binary, linear quadtrees, one for each color (value) in the layer. In such a scheme set operations are carried out by taking unions and intersections of binary quadtrees. This paper presents an alternative database scheme where a layer is stored as a single multicolored quadtree, using a bit-list to store values at higher nodes in the tree. This allows the union of any set of values within a layer to be carried out by a single top down traversal of the tree, using parallel bit-masking operations. Experimental evidence is presented to show that these Bit-Mapped Multi-Colored quadtrees lead to faster colour selection and boolean overlay between layers in a GIS. Furthermore, the recent development of One-To-Four and Autumnal quadtrees have meant that it is now possible to exploit the hierarchical structure of regular quadtrees in GIS without paying an associated storage penalty. Experimental results using these developments are presented to show that representing a layer using a Bit-Mapped Multi-Colored quadtree is more space and time efficient for set operations in comparison to the use of a collection of binary quadtrees, one for each value in the layer.     

A top-down quadtree traversal algorithm

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.     

Space and time efficiency of the forest-of-quadtrees representation

A forest of quadtrees is a refinement of a quadtree data structure that is used to represent planar regions. A forest of quadtrees provides space savings over regular quadtrees by concentrating vital information. The paper presents some of the properties of a forest of quadtrees and studies the storage requirements for the case in which a single 2^m × 2^m region is equally likely to occur in any position within a 2ⁿ × 2ⁿ image. Space and time efficiency are investigated for the forest-of-quadtrees representation as compared with the quadtree representation for various cases.     

Computing perimeters of regions in images represented by quadtrees

An algorithm is presented for computing the total perimeter of a region in a binary image represented by a quadtree. The algorithm explores each segment of the boundary of the region once and only once. Analysis of the algorithm shows that its average execution time is proportional to the number of leaf nodes in the quadtree.     

Recent developments in linear quadtree-based geographic information systems

The status of an ongoing research effort to develop a geographic information system based on a variant of the linear quadtree is presented. This system uses quadtree encodings for storing area, point and line features. Recent enhancements to the system are presented in detail. This includes a new hierarchical data structure for storing linear features that represents straight lines exactly and permits updates to be performed in a consistent manner. The memory management system was modified to enable the representation of an image as large as 16 384 × 16 384 pixels. Improvements were also made to some basic area map algorithms which yield significant efficiency speed-ups by reducing node accesses. These include windowing, set operations with unaligned images, a polygon expansion function, and an optimal quadtree building algorithm which has an execution time that is proportional to the number of blocks in the image instead of the number of pixels.     

一种随机化递增的压缩四叉树形数据结构的构建算法

介绍了一种压缩四叉树形数据结构的随机化增量构造算法。首先给出了压缩四叉树的定义,然后描述了算法实现步骤,通过将单位正方形不断分割为更小的正则正方形达到压缩的目的,使用平铺区域和冲突列表,采用随机化递增的算法构建出压缩四叉树,最后分析了算法正确性和运行时间。     

Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape

The problem of path planning for an automaton moving in a two-dimensional scene filled with unknown obstacles is considered. The automaton is presented as a point; obstacles can be of an arbitrary shape, with continuous boundaries and of finite size; no restriction on the size of the scene is imposed. The information available to the automaton is limited to its own current coordinates and those of the target position. Also, when the automaton hits an obstacle, this fact is detected by the automaton's “tactile sensor.” This information is shown to be sufficient for reaching the target or concluding in finite time that the target cannot be reached. A worst-case lower bound on the length of paths generated by any algorithm operating within the framework of the accepted model is developed; the bound is expressed in terms of the perimeters of the obstacles met by the automaton in the scene. Algorithms that guarantee reaching the target (if the target is reachable), and tests for target reachability are presented. The efficiency of the algorithms is studied, and worst-case upper bounds on the length of generated paths are produced.     

Solid modeling of 4-axis wire EDM cut geometry

NC verification has been widely used in milling and turning machining, but the implementation of NC verification for wire electrical discharge machine (wire EDM) has received little attention, made difficult by the characteristics of geometry cut by the thin wire. For an NC verification system, the speed and the accuracy of are two of the most critical issues. In this paper, a novel solid modeling method, which utilizes a dual quadtree structure and a boundary representation, is applied to modeling the parts cut by a wire EDM. In this implementation, two extended quadtrees on the top and bottom surfaces of the stock are first created. Special quadtree nodes are introduced into the dual quadtree structure to model the features associated with the almost coincident surfaces left by a thin wire. The region swept by a wire in each move is generated based on the diameter of the wire, spark gap size and the paths. The overall geometry of the part is represented by a boundary representation which is updated by means of efficient Boolean operations of extended quadtrees. The free-falling objects which may damage the machine tool can be detected. Dimensional inspection and feature detection can be made with the solid model representing the machined part. The system has demonstrated very promising speed and accuracy.     

Worst-case versus average case complexity of ray-shooting

This paper examines worst-case and average-case complexity measures of ray-shooting algorithms in order to find the answer to the question why computer graphics practitioners prefer heuristic methods to extensively studied worst-case optimal algorithms. It demonstrates that ray-shooting requires at least logarithmic time in the worst-case and discusses the strategies how to design such worst-case optimal algorithms. It also examines the lower-bounds of storage complexity of logarithmic-time algorithms and concludes that logarithmic time has very high price in terms of required storage. In order to find average-case measures, a probabilistic model of the scene is established. We conclude that algorithms optimized for the average-case are not only much simpler to implement, but have moderate storage requirement and can even run faster for the majority of problems.