Narrow Results

Quadtree data structure, popular in 2-D applications, has not been studied in the context of VLSI embedding. This paper proposes two generic layout strategies for quadtree layout. Layout attributes are derived with primary focus on area-I/O trade-off. We demonstrate a simple layout mixing strategy to obtain improved boundary I/O characteristics. This is followed by development of a recursive layout mixing strategy which yields an order of improvement.

We invented a progressive image transmission scheme that is used for transmitting Chinese calligraphy. The scheme employs the property of simple colors of calligraphy images to design a method of transmitting images phase by phase. Overall, our scheme can achieve the following two goals. One is compressing the image data to reduce the transmission time while the other is gaining less response time by using progressive image transmission. Furthermore, the recovered image still maintains the colors of the seals with high image quality.

The paper describes a technique called ISE for image segmentation using entropy. The relation between the entropy of an image domain and the entropy of its subdomains is explored as a uniformity predicate. Such entropy is obtained from the analysis of the image histogram associating a Gaussian distribution to the maximum frequency of gray levels.

In order to implement the model, we have introduced a well-known technique of Problem Solving. In our model, the most important roles are played by the Evaluation Function (EF) and the Control Strategy. The EF is related to the ratio between the entropy of one region or zone of the picture and the entropy of the entire picture, while the Control Strategy determines the optimal path in the search tree (quadtree) so that the nodes in the optimal path have minimal entropy.

The paper shows some comparisons between ISE and classical edge detection techniques.

Given a binary image of square size, it is desirable to identify the amount of shift of the foreground pixels such that it minimizes the total number of leaves of the region quadtree that represents the image. This problem is called quadtree normalization. For this problem, the best known algorithms have time complexities O(N²logN), where N is the side length of given images (so, N² is the total number of pixels).

In this paper, we show an algorithm that has the optimal complexity O(N²) for some class of images. Our strategy consists of two stages: decomposing the given image into axis-parallel rectangles at first and integrating the contributions of individual rectangles afterwards. To do this, we derive the necessary and sufficient condition on any decomposition scheme, in a conditional form of the well-known Inclusion–Exclusion Principle. It turns out that the generated primitives must be "strictly overlapped" to some extent.

The optimal linear-time complexity can be achieved in the case when the total area of the decomposed rectangles is bounded by O(N²) e.g. for the class of images whose foreground part is drawn with the finite number of rectangles. We only sketch the outline of the first decomposition stage of the new algorithm, but the last integrating stage is described in details.

In this paper, we will introduce some variations of tree adjoining grammars which generate the sets of quadtrees as their languages and investigate their effectiveness to describe the sets of digital images. In those variations, two types of parallel operations, multicomponent and multifoot adjoining, will be introduced. Both of them are quite different parallelisms from ordinary ones (such as Indian parallelism of grammars, or L-systems).

An optimal box-counting algorithm for estimating the fractal dimension of a nonempty set which changes over time is given. This nonstationary environment is characterized by the insertion of new points into the set and in many cases the deletion of some existing points from the set. In this setting, the issue at hand is to update the box-counting result at appropriate time intervals with low computational cost. The proposed algorithm tackles the dynamic box-counting problem by using computational geometry methods. In particular, we use a sequence of compressed Box Quadtrees to store the data points. This storage permits the fast and efficient application of our box-counting approach to compute what we call the "dynamic fractal dimension". For a nonempty set of points in the d-dimensional space ℝ^d (for constant d ≥ 1), the time complexity of the proposed algorithm is shown to be O(n log n) while the space complexity is O(n), where n is the number of considered points. In addition, we show that the time complexity of an insertion, or a deletion is O(log n), and that the above time and space complexity is optimal. Experimental results of the proposed approach illustrated on the well-known and widely studied Hénon map are presented.

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R²) or the skip octree (for point data in R^d, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined “box”-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

We describe efficient PRAM algorithms for constructing unbalanced quadtrees, balanced quadtrees, and quadtree-based finite element meshes. Our algorithms take time O(log n) for point set input and O(log n log k) time for planar straight-line graphs, using O(n+k/log n) processors, where n measures input size and k output size.

In this paper, we have studied the problem of finding the neighbors of a node in a quadtree. We have proposed a variation in the quadtree representation which has helped in finding the neighbors efficiently. We have presented algorithms for construction and maintenance of our quadtree.

A special regularization method based on higher-order partial differential equations is presented. Instead of using the fundamental solution of the original partial differential operator with source points located outside of the domain, the original second-order partial differential equation is approximated by a higher-order one, the fundamental solution of which is continuous at the origin. This allows the use of the method of fundamental solutions (MFS) for the approximate problem. Due to the continuity of the modified operator, the source points and the boundary collocation points are allowed to coincide, which makes the solution process simpler. This regularization technique is generalized to various problems and combined with the extremely efficient quadtree-based multigrid methods. Approximation theorems and numerical experiences are also presented.

In many extended versions of the finite element method (FEM) the mesh does not conform to the physical domain. Therefore, discontinuity of variables is expected when some elements are cut by the boundary. Thus, the integrands are not continuous over the whole integration domain. Apparently, none of the well developed integration schemes such as Gauss quadrature can be used readily. This paper investigates several modifications of the Gauss quadrature to capture the discontinuity within an element and to perform a more precise integration. The extended method used here is the finite cell method (FCM), an extension of a high-order approximation space with the aim of simple meshing. Several examples are included to evaluate different modifications.

There remain outstanding challenges for improving accuracy of multi-feature information for head-pose and gaze estimation. The proposed framework employs discriminative analysis for head-pose and gaze estimation using kernel discriminative multiple canonical correlation analysis (K-DMCCA). The feature extraction component of the framework includes spatial indexing, statistical and geometrical elements. Head-pose and gaze estimation is constructed by feature aggregation and transforming features into a higher dimensional space using K-DMCCA for accurate estimation. The two main contributions are: Enhancing fusion performance through the use of kernel-based DMCCA, and by introducing an improved iris region descriptor based on quadtree. The overall approach is also inclusive of statistical and geometrical indexing that are calibration free (does not require any subsequent adjustment). We validate the robustness of the proposed framework across a wide variety of datasets, which consist of different modalities (RGB and Depth), constraints (wide range of head-poses, not only frontal), quality (accurately labelled for validation), occlusion (due to glasses, hair bang, facial hair) and illumination. Our method achieved an accurate head-pose and gaze estimation of 4.8^∘ using Cave, 4.6^∘ using MPII, 5.1^∘ using ACS, 5.9^∘ using EYEDIAP, 4.3^∘ using OSLO and 4.6^∘ using UULM datasets.