Parallel Computation of the Topology of Level Sets

This paper introduces two efficient algorithms that compute the Contour Tree of a three-dimensional scalar field F and its augmented version with the Betti numbers of each isosurface. The Contour Tree is a fundamental data structure in scientific visualization that is used to pre-process the domain mesh to allow optimal computation of isosurfaces with minimal overhead storage. The Contour Tree can also be used to build user interfaces reporting the complete topological characterization of a scalar field, as shown in Figure~\ref{fig:top}. Data exploration time is reduced since the user understands the evolution of level set components with changing isovalue. The Augmented Contour Tree provides even more accurate information segmenting the range space of the scalar field into regions of invariant topology. The exploration time for a single isosurface is also improved since its genus is known in advance. Our first new algorithm augments any given Contour Tree with the Betti numbers of all possible corresponding isocontours in linear time with the size of the tree. Moreover, we show how to extend the scheme introduced in [3] with the Betti number computation without increasing its complexity. Thus, we improve on the time complexity in our previous approach from O(m log m) to O(n log n + m), where m is the number of cells and n is the number of vertices in the domain of F. Our second contribution is a new divide-and-conquer algorithm that computes the Augmented Contour Tree with improved efficiency. The approach computes the output Contour Tree by merging two intermediate Contour Trees and is independent of the interpolant. In this way we confine any knowledge regarding a specific interpolant to an independent function that computes the tree for a single cell. We have implemented this function for the trilinear interpolant and plan to replace it with higher-order interpolants when needed. The time complexity is O(n + t log n), where t is the number of critical points of F. For the first time we can compute the Contour Tree in linear time in many practical cases where t = O(n ^1–ε). We report the running times for a parallel implementation, showing good scalability with the number of processors.     

基于图割和水平集的肾脏医学图像分割

肾脏医学图像分割是医学图像分析和非侵入式计算机辅助诊断系统中的关键步骤。从CT、MRI图像中分割出肾脏及肾皮质,计算其体积和皮质厚度等信息,有助于评估肾脏的功能,从而制定相应的治疗方案。根据肾脏序列图像相邻切片之间结构灰度分布的相似性,提出了一种基于图割和水平集方法的自动肾脏及肾皮质分割方法。选取皮质区域具有足够对比度和清晰度的切片为初始参考图像,使用霍夫森林算法检测肾脏区域,对前景、背景进行均值聚类以估计其灰度分布,获取图割模型能量函数,分割出肾脏整体;通过形态学处理得到相邻切片肾脏的分割候选区域,重复上述分割。以此初步分割结果作为水平集方法的初始轮廓,进一步分割得到三维的肾脏整体和肾皮质区域。实验结果表明,基于图割和水平集的肾脏分割方法能够比较准确地分割出肾脏及肾皮质。     

Topology design of three-dimensional continuum structures using isosurfaces

Isolines Topology Design (ITD) is an iterative algorithm for the topological design of two-dimensional continuum structures using isolines. This paper presents an extension to this algorithm for topology design of three-dimensional continuum structures. The topology and the shape of the design depend on an iterative algorithm, which continually adds and removes material depending on the shape and distribution of the contour isosurfaces for the required structural behaviour. In this study the von Mises stress was investigated. Several examples are presented to show the effectiveness of the algorithm, which produces final designs with very detailed surfaces without the need for interpretation. The results demonstrate how the ITD algorithm can produce realistic designs by using the design criteria contour isosurface.     

Level sets and the representation theorem for intuitionistic fuzzy sets

We discuss the concept of a level set of a fuzzy set and the related ideas of the representation theorem and Zadeh’s extension principle. We then describe the extension of these ideas to the case of interval valued fuzzy sets (IVFS). We then recall the formal equivalence between IVFS and intuitionistic fuzzy sets (IFS). This equivalence allows us to naturally extend the concepts of level sets, representation theorem and extension principle from the domain of IVFS to the domain of IFS. What is important to note here is that in the case of these non-standard fuzzy sets, interval valued and intuitionistic, the number of distinct level sets can be greater then the number of distinct membership grades of the fuzzy set being represented. This is a result of the fact that the distinct level sets are generated by the power set of the membership grades. In particular, the minimum of each subset of membership grades provides a level set. In the case of the standard fuzzy sets the minimum of a subset of membership grades results in one of the elements in the subset. In the case of the non-standard fuzzy sets, the membership grades are not linearly ordered and hence taking the minimum of a subset of these can result in a value that was not one of the members of the subset.

基于GPU的大规模拓扑优化问题并行计算方法

针对进行大规模拓扑优化问题计算量庞大且计算效率低的问题,设计并实现了一种基于图形处理器(GPU)的并行拓扑优化方法.采用双向渐进结构拓扑优化(BESO)为基础优化算法,采用一种基于节点计算的共轭梯度求解方法用于有限元方程组求解.通过对原串行算法的研究,并结合GPU的计算特点,实现了迭代过程全流程的并行计算.上述方法的程序设计和编写采用统一计算架构(CUDA),提出了基于单元和基于节点的两种并行策略.编写程序时充分使用CUDA自带的各种数学运算库,保证了程序的稳定性和易用性.数值算例证明,并行计算方法稳定并且高效,在优化结果一致的前提下,采用GTX580显卡可以取得巨大的计算加速比.     

基于模糊粗糙集的粒度计算

粒度计算是一种新的智能计算的理论和方法,目前受到很多学者的关注。但是,具体可行的粒表示模型和不同粒的推理方法研究相对较少。本文将模糊粗糙集纳入粒度计算这种新的理论框架,对于处理复杂信息系统,求解复杂问题无疑具有重要的意义。首先利用笛卡尔积,构建了模糊关系下的信息粒;然后给出不同粒度下模糊粗糙算子的表示方法,进而形成一个分层递阶结构;最后考虑了对于模糊信息系统粒度粗细的选择问题,并给出一个实例,从而为粒度计算提供一个具体而实用的框架。     

Parallel Algorithms for Maximal Acyclic Sets

Given a graph G=(V,E), the well-known spanning forest problem of G can be viewed as the problem of finding a maximal subset F of edges in G such that the subgraph induced by F is acyclic. Although this problem has well-known efficient NC algorithms, its vertex counterpart, the problem of finding a maximal subset U of vertices in G such that the subgraph induced by U is acyclic, has not been shown to be in NC (or even in RNC) and is not believed to be parallelizable in general. In this paper we present NC algorithms for solving the latter problem for two special cases. First, we show that, for a planar graph with n vertices, the problem can be solved in time with O(n) processors on an EREW PRAM. Second, we show that the problem is solvable in NC if the input graph G has only vertex-induced paths of length polylogarithmic in the number of vertices of G. As a consequence of this result, we show that certain natural extensions of the well-studied maximal independent set problem remain solvable in NC. Moreover, we show that, for a constant-degree graph with n vertices, the problem can be solved in time with O(n ² ) processors on an EREW PRAM. Received July 3, 1995; revised April 1, 1996.     

Topology optimization of shell structures using adaptive inner-front (AIF) level set method

A new topology optimization using adaptive inner-front level set method is presented. In the conventional level set-based topology optimization, the optimum topology strongly depends on the initial level set due to the incapability of inner-front creation during the optimization process. In the present work, in this regard, an algorithm for inner-front creation is proposed in which the sizes, the positions, and the number of new inner-fronts during the optimization process can be globally and consistently identified. In the algorithm, the criterion of inner-front creation for compliance minimization problems of linear elastic structures is chosen as the strain energy density along with volumetric constraint. To facilitate the inner-front creation process, the inner-front creation map is constructed and used to define new level set function. In the implementation of inner-front creation algorithm, to suppress the numerical oscillation of solutions due to the sharp edges in the level set function, domain regularization is carried out by solving the edge smoothing partial differential equation (smoothing PDE). To update the level set function during the optimization process, the least-squares finite element method (LSFEM) is adopted. Through the LSFEM, a symmetric positive definite system matrix is constructed, and non-diffused and non-oscillatory solution for the hyperbolic PDE such as level set equation can be obtained. As applications, three-dimensional topology optimization of shell structures is treated. From the numerical examples, it is shown that the present method brings in much needed flexibility in topologies during the level set-based topology optimization process.     

直觉模糊数决策粗糙集

决策粗糙集模型的代价函数不包含模糊概念,不能够细腻地描述包含模糊信息的决策。针对上述不足,首先将模型中精确值的代价函数拓展为直觉模糊数,构建直觉模糊数决策粗糙集模型。然后,通过分析基于直觉模糊数下、上理想的决策预期代价函数,形成保守、激进、可变的决策策略和相应的决策规则,并分析其相关数学性质。最后,通过对战略目标防空部署策略的风险分析来说明模型的具体应用过程。     

Level sets and the extension principle for interval valued fuzzy sets and its application to uncertainty measures

We describe the representation of a fuzzy subset in terms of its crisp level sets. We then generalize these level sets to the case of interval valued fuzzy sets and provide for a representation of an interval valued fuzzy set in terms of crisp level sets. We note that in this representation while the level sets are crisp the memberships are still intervals. Once having this representation we turn to its role in the extension principle and particularly to the extension of measures of uncertainty of interval valued fuzzy sets. Two types of extension of uncertainty measures are investigated. The first, based on the level set representation, leads to extensions whose values for the measure of uncertainty are themselves fuzzy sets. The second, based on the use of integrals, results in extensions whose value for the uncertainty of an interval valued fuzzy sets is an interval.     

基于元信息的粗糙集规则并行挖掘方法

1.引言在当前的信息化时代,为从大量积累的历史数据中获取有用的知识,使得数据挖掘已成为研究热点。Pawlak教授提出粗糙集合理论,经过众多学者的研究和完善,已成为数据挖掘的重要手段。在大数据环境下,数据挖掘方法的速度将直接影响整个数据挖掘系统的性能,如何有效地提高数据挖掘方法的速度,是迫切需要解决的问题。与此同时,计算机网络存在大量的运算资源,充分利用这些资源是提高数据挖掘方法速度的有效途径。为此,本文提出     

面向大规模数据的快速并行聚类划分算法研究

随着聚类分析中处理数据量的急剧增加,面对大规模数据,传统K-Means聚类算法面临着巨大挑战。为了提高传统K-Means聚类算法的效率,针对已有基于MPI的并行K-Means聚类算法和基于Hadoop的分布式K-Means云聚类算法,从聚心初始化和通信模式等入手,提出了改进思路和具体实现。实验结果表明,所提算法能大大减少通信量和计算量,具有较高的执行效率。研究结果可以为以后设计更好的大规模数据快速并行聚类划分算法提供研究依据。     

基于双水平集的图像分割模型

针对水平集模型对于具有细长拓扑部分的目标和弱边界目标进行分割时存在的问题,提出了双水平集方法.在新的方法中通过两条水平集之间的相互吸引来加速解的收敛,同时提出了一种快速有符号距离函数生成方法,提高了计算效率.传统的水平集通常利用图像边界信息来构造速度函数进行求解,但在待分割目标具有很强噪音或具有弱边界时往往得不到真实解,对此,提出了一种新的基于区域信息的速度构造方法.将双水平集模型应用到合成图像与左心室MR图像的分割实验,结果表明该方法具有较好的分割效果和较高的分割效率.     

关于Vague集的模糊熵

由于Vague集是Zadeh's模糊集的一个扩展,为计算Vague集的模糊熵,有学者提出将Vague集转化为模糊集,然后借用模糊集有关熵的计算方法来讨论它们。该文首先给出反例说明Li's(2003)的方法在某些情况下和基于模糊集的Vague集模糊熵定义不一致。在指出Vague集的模糊性主要来自未知信息和不确定性信息的基础上,提出了一个基于非模糊集的Vague集模糊熵公理化定义,给出了该类模糊熵的计算公式,最后通过定理证明了它确实同时考虑到了影响Vague集模糊熵的两个因素。     

多电平变换器拓扑结构的发展与现状

本文介绍了多电平变换器拓扑结构的发展和现状,以及实现多电平变换器的基本电路,包括二极管箝位型、飞跨电容型、级联型、通用型、直流源级联型、变压器级联型等,列出了它们的基本电路拓扑图,同时对拓扑图进行了简单的分析,总结了各种拓扑结构的特点。最后,对多电平变换器的发展方向提出了看法。     

基于水平集的医学图像分割改进算法

医学影像分割是图像分割中的难点,具有重要的应用价值。针对医学影像的特点和图像分割算法的性能差异,提出了一种水平集医学图像分割改进算法。首先通过曲线演化仿真,得出水平集算法核心-速度函数;其次选定速度函数实现对图像的粗略分割,将灰度值较大的区域设置成灰度值较小的值,通过仿真演化准确找到图像中目标区域;最后利用选定的速度函数通过初始算法,经过一定次数的迭代操作后实现了医学影像的准确分割。实验结果表明:该算法可以精确地找到肿瘤所在区域,具有较好的分割性能和一定的鲁棒性。
     

水平集曲线演化快速提取足迹轮廓

提出空间多分辨分析方法,通过分析图像行列方向能量投影的分布,将图像划分为大小不均匀的子块,根据图像的总体结构特征和局部细节特征自适应地调整子块大小,并以各子块的灰度均值作为新图像基元像素的灰度值,实现图像压缩.水平集曲线演化方法在压缩图像上进行,使得被处理的数据量大大减少,从而缩短了轮廓提取的时间,提高了算法的实用性.与边缘检测方法或直接水平集曲线演化方法相比较表明,该方法能够以较少的运算量获取较高的足迹轮廓提取准确度.     

Computation of the topology of real algebraic space curves

An algorithm for computing the topology of a real algebraic space curve , implicitly defined as the intersection of two surfaces, is presented. Given , the algorithm generates a space graph which is topologically equivalent to the real variety on the Euclidean space. The algorithm is based on the computation of the graphs of at most two projections of . For this purpose, we introduce the notion of space general position for space curves, we show that any curve under the above conditions can always be linearly transformed to be in general position, and we present effective methods for checking whether space general position has been reached.     

正态模糊集合——Fuzzy集理论的新拓展

直觉模糊集（intuitionistic fuzzy sets）、区间值模糊集（interval-valued fuzzy sets）以及Vague集对普通fuzzy集的扩展是给出了隶属度的上下限,把隶属度从[0,1]区间中的一个单值推广到了[0,1]的子区间。但是该子区间犹如一个黑洞,隶属度在其内部的分布情况我们无从知晓,即这个子区间中的每一个值是等可能地作为元素的隶属度还是区间中的某些值较另外的值有更大的可能性呢？为了清晰的刻画出元素的隶属度在[0,1]区间中的分布情况,本文通过对投票模型的分析及正态分布理论,提出了一种新的模糊集合——正态模糊集合,同时对正态模糊集合的交、并、补等基本运算性质进行了讨论,文章最后对正态模糊集与fuzzy集、直觉模糊集的相互关系也作出了详细阐述。正态模糊集合是模糊集合理论的进一步推广,为我们处理模糊信息提供了一种全新的思想方法。