四叉树分解的图像插值

如何在图像插值的同时较好地保持图像的结构信息一直是图像插值的一个难点,提出了一种基于四叉树分解的图像插值方法,基本思想是：用四叉树分解将原始图像划分为一些像素值相近的子块,当分解区域为1×1,用最邻近插值方法,分解区域为2×2时,用双线性方法插值,其余情况用双立方插值扩充子块,再将扩充后的子块映射到输出图像。实验结果表明该方法能较好地保持图像的边缘,同时具有较高的效率,可以应用到图像、视频及医学图像的放大。     

An exact closed-form formula for d-dimensional quadtree decomposition of arbitrary hyperrectangles

In this paper, we solve the classic problem of computing the average number of decomposed quadtree blocks (quadrants, nodes, or pieces) in quadtree decomposition for an arbitrary hyperrectangle aligned with the axes. We derive a closed-form formula for general cases. The previously known state-of-the-art solution provided a closed-form solution for special cases and utilized these formulas to derive linearly interpolated formulas for general cases individually. However, there is no exact and uniform closed-form formula that fits all cases. Contrary to the top-down counting approach used by most prior solutions, we employ a bottom-up enumeration approach to transform the problem into one that involves the Cartesian product of d multisets of successive 2's powers. Classic combinatorial enumeration techniques are applied to obtain an exact and uniform closed-form formula. The result is of theoretical interest since it is the first exact closed-form formula for arbitrary cases. Practically, it is nice to have a uniform formula for estimating the average number since a simple program can be conveniently constructed taking side lengths as inputs.     

应用迭代四叉树的肝脏MR图像分割

磁共振（Magnetic Resonance,MR）图像的诊断是公认的确认肝脏有无肿瘤等器质性病变的金标准方法,因此肝脏的正确分割对计算机辅助诊断有非常重要的意义。由于脏器组织浸润和个体差异,在肝脏分割实现方法方面有一定难度,目前尚没有通用的医学分割方法。在既有研究的基础上,提出了基于四叉树的迭代分割算法,得到MR图像中肝脏的自动分割结果。实验分割结果表明这种方法的可行性和优势,并为后续的肿瘤提取奠定基础。     

Error-bounded lossy compression of floating-point color buffers using quadtree decomposition

In this paper, we present a new color buffer compression algorithm for floating-point buffers. It can operate in either an approximate (lossy) mode or in an exact (lossless) mode. The approximate mode is error-bounded and the amount of introduced accumulated error is controlled via a few parameters. The core of the algorithm lies in an efficient representation and color space transform, followed by a hierarchical quadtree decomposition, and then hierarchical prediction and Golomb–Rice encoding. We believe this is the first lossy compression algorithm for floating-point buffers, and our results indicate significantly reduced color buffer bandwidths and negligible visible artifacts.     

Iterative quadtree decomposition based automatic selection of the seed point for ultrasound breast tumor images

Based on seed region growing method, lesion segmentation for ultrasound breast tumor images often requires manual selection of the seed point, which is both time-consuming and laborious. To overcome this limit, this paper attempts to explore an automatic method for finding the seed point inside the tumor. Two criteria combining iterative quadtree decomposition (QTD) and the gray characteristics of the lesion are thus designed to locate the seed point. One is to seek the biggest homogenous region and the other is to select the seed region where the seed point is found. Furthermore, this study validates the proposed algorithm through 110 ultrasonic breast tumor images (including 58 malignant tumor images and 52 benign tumor images). According to the needs of the seed region growing algorithm, if the seed point is found inside the tumor, it means the proposed method is correct. Otherwise, it means that the method is a failure. As the quantitative experiment results show, the proposed method in this paper can automatically find the seed point inside the tumor with an accuracy rate of 97.27 %.     

基于四叉树分解与图割的彩色图像快速分割

图割是一种基于图论的组合优化方法,基于图割的GrabCut是一种高效的前景提取算法。然而,GrabCut为达到一定分割精度,在高斯混合模型参数估计过程中多次迭代使用图割,这使得GrabCut在处理海量级图像数据时,耗时往往比较大。通过四叉树分解,可以将图像划分成区域内相似度高的若干分块,以构建精简的网络图,并用块内的RGB均值代替该块内的所有像素点的值进行高斯混合模型参数估计,从而减小问题规模,提高算法效率。实验结果表明了算法的可行性及有效性。     

Dilation algorithm for a linear quadtree

A dilation algorithm for a linear quadtree is presented. This can be used to expand the black regions of a region quadtree by a user-specified amount. The algorithm requires two traversals through the ordered quadtree leaf set, the second traversal being in the opposite direction to the first. No explicit neighbour finding is required. Timings are compared with those obtained using an existing one-pass algorithm. The two-pass algorithm is faster than the one-pass for expansions of typical real images, and this speed increase becomes more pronounced as the expansion and the complexity of the image increase.     

叶结点编码四叉树的邻域寻找算法

针对一类常见而简单的规则中有项或缺项的约束,提出了一种基于事务数据修剪的约束关联规则的快速挖掘算法。该算法先扫描一遍数据库对事务进行水平和纵向的修剪,接着在修剪后的数据集上挖掘频繁项集,形成规则的候选头集、体集和规则项集,最后一次扫描后由最小可信度约束得到所要求的关联规则。实验表明,与按简洁约束采取的一般策略相比,该算法的性能有较明显的提高。设计了一套新的叶子结点编码方式,基于该编码,实现了编码四叉树的邻域寻找。此方法减少了四叉树存储的结点个数,提高了存储效率。同时由于在叶子一级采用位操作实现邻域寻找,使查询效率有所提高。     

一种基于四叉树的TIN的LOD算法

通过在不规则采样点集上构建一个四叉树结构，并联合基于四叉树的LOD算法和基于TIN的三角网简化算法，提出并实现了一种TIN的LOD算法。意在把适用于格网数据的高效方法应用于不规则采样点集，得到地形的一个高效的多分辨率表达。     

Applications of quadtree, octree, and binary tree decomposition techniques to shape analysis and pattern recognition

The binary tree, quadtree, and octree decomposition techniques are widely used in computer graphics and image processing problems. Here, the techniques are reexamined for pattern recognition and shape analysis applications. It has been shown that the quadtree and octree techniques can be used to find the shape hull of a set of points in space while their n-dimensional generalization can be used for divisive hierarchical clustering. Similarly, an n-dimensional binary tree decomposition of feature space can be used for efficient pattern classifier design. Illustrative examples are presented to show the usefulness and efficiency of these hierarchical decomposition techniques.     

A method for solving the n-dimensional convex hull problem

A method is presented for finding all vertices and all hyperplanes containing the faces of a convex polyhedron spanned by a given finite set X in Euclidean space Eⁿ. The present paper indicates how this method can be applied to the investigation of linear separability of two given finite sets X₁ and X₂ in Eⁿ. In the case of linear separability of these sets the proposed method makes it possible to find the separating hyperplane.     

Extended univariate algorithms for n-dimensional global optimization

In recent papers of the author a general class of algorithms was proposed to solve the global optimization problem inn dimensions (n≥1). Here we show that certain types of univariate methods (n=1) can be generalized in a straightforward manner to obtain algorithms for the casen>1. Some numerical test tesults are also reported.     

面向飞行仿真的四叉树多分辨率地形实时优化

为实现大规模复杂地形的实时绘制,提出1种消除四又树多分辨率地形裂缝问题的实时优化方法.该方法将不同分辨率过渡区域的地形进行重新构网,并针对飞行仿真距离地面较高、下视角较大的特点对四又树顶点误差估计和几何光滑过渡算法进行优化,在保证地形准确性的范围内提高计算机实时处理速度.同时,在Vega平台下对某典型飞行训练项目进行仿真并与由LINDSTROM提出的简化公式而制订的解决方案进行比较,结果表明对地形进行优化是1种见效较快的方式.     

Calculating the n-dimensional fast Fourier transform

The one-dimensional fast Fourier transform (FFT) is the most popular tool for calculating the multidimensional Fourier transform. As a rule, to estimate the n-dimensional FFT, a standard method of combining one-dimensional FFTs, the so-called “by rows and columns” algorithm, is used in the literature. For fast calculations, different researchers try to use parallel calculation tools, the most successful of which are searches for the algorithms related to the computing device architecture: cluster, video card, GPU, etc. [1, 2]. The possibility of paralleling another algorithm for FFT calculation, which is an n-dimensional analog of the Cooley-Tukey algorithm [3, 4], is studied in this paper. The focus is on studying the analog of the Cooley-Tukey algorithm because the number of operations applied to calculate the n-dimensional FFT is considerably less than in the conventional algorithm nN ⁿ log₂ N of addition operations and 1/2N ^{n + 1}log₂ N of multiplication operations of addition operations and $\frac{{2^n - 1}} {{2^n }}N^n \log _2 N$ of multiplication operations against: N ^{n + 1}log₂ N of addition operations and 1/2N ^{n + 1}log₂ N of in combining one-dimensional FFTs.     

The immersive visualization probe for exploring n-dimensional spaces

A new tool uses two types of dimensional navigation to display continuous 4D subsets of n-dimensional data. Thanks to the tool's embedded coordinate systems, researchers can better understand a model's underlying physical or mathematical process. Here, we describe a new method for visualizing data structure or models defined in higher-dimensional spaces. This technique is suitable for applications in which a scalar function, defined mathematically or procedurally, depends on n variables or parameters. The function's values essentially describe a set of points in n-dimensional space. To visualize these sets, we fix all but three of the parameters and then sample the resulting 4D set (the three parameters and the function's resulting value) on several discrete grids located on planes in the 3D space. We compose the image by using color to represent the fourth dimension (the function's value) at discrete locations on these grids. Interactive control over the way the parameters are fixed results in a highly dynamic system that researchers can easily use to explore the n-dimensional space's structure.     

Characterization of static bifurcations for n-dimensional flows in the frequency domain

In this paper n-dimensional flows (described by continuous-time system) with static bifurcations are considered with the aim of classification of different elementary bifurcations using the frequency domain formalism. Based on frequency domain approach, we prove some criterions for the saddle-node bifurcation, transcritical bifurcation and pitchfork bifurcation, and give an example to illustrate the efficiency of the result obtained.     

Characterization of static bifurcations for n-dimensional flows in the frequency domain

In this paper n-dimensional flows （described by continuous-time system） with static bifurcations are considered with the aim of classification of different elementary bifurcations using the frequency domain formalism. Based on frequency domain approach, we prove some criterions for the saddle-node bifurcation, transcritical bifurcation and pitchfork bifurcation, and give an example to illustrate the efficiency of the result obtained.     

基于四叉树结构的加权Voronoi图生成算法

针对普通Voronoi图研究的局限性和加权Voronoi算法的低效率问题,提出基于四叉树结构的加权Voronoi图生成方法。核心思想是利用四叉树结构的层次性,获取未膨胀节点的搜索区域和相关生长源,以时间消耗值替代加权距离,并以节点的最短时间消耗值为依据查找归属生长源。推理了基于四叉树结构计算模型的几个基本性质。实验结果表明,本方法能实现生长源的快速膨胀,有效降低时间复杂度,其时间复杂度小于均匀格网结构,可操作性强,具有较好的实用价值。