Efficient component labeling of images of arbitrary dimensionrepresented by linear bintrees

An algorithm is presented to perform connected-component labeling of images of arbitrary dimension that are represented by a linear bintree. The bintree is a generalization of the quadtree data structure that enables dealing with images of arbitrary dimension. The linear bintree is a pointerless representation. The algorithm uses an active border which is represented by linked lists instead of arrays. This results in a significant reduction in the space requirements, thereby making it feasible to process three- and higher-dimensional images. Analysis of the execution time of the algorithm shows almost linear behavior with respect to the number of leaf nodes in the image, and empirical tests are in agreement. The algorithm can be modified easily to compute a (d-1)-dimensional boundary measure (e.g. perimeter in two dimensions and surface area in three dimensions) with linear performance     

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.     

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

本文讨论了线性四叉树的一种新的构造算法。该算法是在文献[3]的最优四叉树构造算法基础上,进一步减少了构造过程中需插入的结点数及辅助存储空间。它借助于一种新的图象数据结构——数字搜索树作为中间输出结构,因而具有更高的效率。     

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.     

An improved algorithm for gray image representation using non-symmetry and anti-packing model with triangles and rectangles

Although the triangle non-symmetry and anti-packing model (TNAM) representation for gray images is an effective image representation method, there is still much space left for optimization. In this paper, inspired by the optimization idea of the packing problem, we proposed an improved algorithm for gray image representation using the non-symmetry and anti-packing model with triangles and rectangles (NAMTR). By comparing the representation algorithm of the NAMTR with those of the TNAM and the popular linear quadtree, theoretical and experimental results presented in this paper show that the former can greatly reduce the number of sub-patterns or nodes and simultaneously save the data storage much more effectively than the latter, and therefore it is a better method to represent gray images. Representation method of the NAMTR, as envisaged in this paper, shows a very strong promise, and it is valuable for further theoretical research and potential business foreground, such as reducing storage space, increasing transmission speed and improving pattern match efficiency.     

An improved algorithm for gray image representation using non-symmetry and anti-packing model with triangles and rectangles

Although the triangle non-symmetry and anti-packing model (TNAM) representation for gray images is an effective image representation method, there is still much space left for optimization. In this paper, inspired by the optimization idea of the packing problem, we proposed an improved algorithm for gray image representation using the non-symmetry and anti-packing model with triangles and rectangles (NAMTR). By comparing the representation algorithm of the NAMTR with those of the TNAM and the popular linear quadtree, theoretical and experimental results presented in this paper show that the former can greatly reduce the number of sub-patterns or nodes and simultaneously save the data storage much more effectively than the latter, and therefore it is a better method to represent gray images. Representation method of the NAMTR, as envisaged in this paper, shows a very strong promise, and it is valuable for further theoretical research and potential business foreground, such as reducing storage space, increasing transmission speed and improving pattern match efficiency.     

Linear octrees by volume intersection

The paper describes a new algorithm for constructing a 3D approximation of an object from three orthogonal 2D silhouettes. The 2D views are represented as binary arrays and 3D approximation is obtained as a linear octree. The algorithm makes use of volume intersection of three cylinders obtained by sweeping three views in respective directions. The algorithm takes less time than an existing algorithm which makes use of three quadtrees and an octree for 2D and 3D image representation, respectively. Unlike the previous algorithm, the present algorithm does not require any preprocessing stage or condensation. It is Shown that the proposed algorithm is of o(T), where T is the total number of nodes in the resulting octree.     

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.     

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.     

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.     

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.     

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.The support of the National Science Foundation under Grant IRI-88-02457 is gratefully acknowledged.     

Algorithm to expand regions represented by linear quadtrees

An algorithm is presented that changes to ‘black’ those ‘white’ pixels within a specified distance of any ‘black’ pixel in an image represented by a linear quadtree. This function is useful for answering queries in a geographic information system such as ‘Find all wheat fields within five miles of a flood plain.’ The algorithm works by computing the chessboard distance to nearby black pixels for large white nodes, and either leaves them white, changes them to black or repeats the process on each subquadrant, as required. Small white nodes are a priori within the given radius and require no further calculation. Thus only a small percentage of the nodes of the quadtree need extensive processing. The algorithm is easily applied to multicoloured images by treating all nonwhite colours as ‘black’.     

A new region expansion for quadtrees

A one-pass algorithm that performs region expansion in images represented by quadtrees is presented. The algorithm changes to black those white pixels within a specified distance of any black mode in the image. The algorithm yields a significant improvement over previous approaches by reducing both the number of black nodes that must be considered for expansion and the number of nodes that must be inserted as a result of the expansion. The reductions are achieved by introducing the concepts of a merging cluster and a vertex set. Empirical tests show that the execution time of this algorithm generally decreases as the radius of expansion increases, whereas in previous approaches the execution time generally increased with the radius of expansion     

TSNAM彩色图像的格雷码表示

为了提高彩色图像模式的表示效率,借助于三角形和正方形布局问题的思想,将格雷码和位平面分解方法应用到彩色图像的三角形和正方形NAM表示方法（TSNAM）中,提出了一种基于格雷码的TSNAM彩色图像表示方法（GTSNAM）.给出了GTSNAM表示算法的形式化描述,并对其存储结构、总数据量和时空复杂性进行了分析.理论分析和实验结果表明,与最新提出的TSNAM表示方法和经典的线性四元树（LQT）表示方法相比,GTSNAM表示方法具有更少的子模式数(或节点数),能够更有效地减少数据存储空间,因而是一种有效的彩色图像表示方法.     

基于格雷码的NAM彩色图像表示方法

提出了一个重要定理,即所有格雷码(Cray Codc)位面图的复杂性之和小于所有二值位面图的复杂性之和,并将格雷码应用到基于NAM的彩色图像表示方法中,提出了一种基于格雷码的NAM彩色图像表示方法(简称为GNAM表示方法)。给出了GNAM表示算法的形式化描述,并对其存储结构、总数据量和时空复杂性进行了详细的分析。理论分析和实验结果均表明,与无格雷码的NAM表示方法和经典的线性四元树表示方法相比,GNAM表示方法具有更少的子模式数(或节点数),能够更有效地减少数据存储空间,是一种有效的彩色图像表示方法。     

Speeding up construction of PMR quadtree-based spatial indexes

Spatial indexes, such as those based on the quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints, especially when the queries involve spatial joins. In this paper we present a number of techniques for speeding up the construction of quadtree-based spatial indexes, specifically the PMR quadtree, which can index arbitrary spatial data. We assume a quadtree implementation using the “linear quadtree”, a disk-resident representation that stores objects contained in the leaf nodes of the quadtree in a linear index (e.g., a B-tree) ordered based on a space-filling curve. We present two complementary techniques: an improved insertion algorithm and a bulk-loading method. The bulk-loading method can be extended to handle bulk-insertions into an existing PMR quadtree. We make some analytical observations about the I/O cost and CPU cost of our PMR quadtree bulk-loading algorithm, and conduct an extensive empirical study of the techniques presented in the paper. Our techniques are found to yield significant speedup compared to traditional quadtree building methods, even when the size of a main memory buffer is very small compared to the size of the resulting quadtrees. Edited by R. Sacks-Davis. Received: July 10, 2001 / Accepted: March 25, 2002 Published online: September 25, 2002     

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.     

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.     

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.