作者：
Li, KWu, XDChen, DZSonka, MCarnegie Mellon Univ
Dept Elect & Comp Engn Pittsburgh PA 15213 USA Univ Iowa
Dept Elect & Comp Engn Seamans Ctr Engn Arts & Sci Iowa City IA 52242 USA Univ Iowa
Dept Radiat Oncol Seamans Ctr Engn Arts & Sci Iowa City IA 52242 USA Univ Notre Dame
Dept Comp Sci & Engn Notre Dame IN 46556 USA
Efficient segmentation of globally optimal surfaces representing object boundaries in volumetric data sets is important and challenging in many medical image analysis applications. We have developed an optimal surface...
详细信息
Efficient segmentation of globally optimal surfaces representing object boundaries in volumetric data sets is important and challenging in many medical image analysis applications. We have developed an optimal surface detection method capable of simultaneously detecting multiple interacting surfaces, in which the optimality is controlled by the cost functions designed for individual surfaces and by several geometric constraints defining the surface smoothness and interrelations. The method solves the surface segmentation problem by transforming it into computing a minimum s-t cut in a derived arc-weighted directed graph. The proposed algorithm has a low-order polynomial time complexity and is computationally efficient. It has been extensively validated on more than 300 computer-synthetic volumetric images, 72 CT-scanned data sets of different-sized plexiglas tubes, and tens of medical images spanning various imaging modalities. In all cases, the approach yielded highly accurate results. Our approach can be readily extended to higher-dimensional image segmentation.
In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided int...
详细信息
In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated theoretically to be O(n(7)) and 3n-5, respectively, and the average performance is evaluated based on computer experiments.
Spectral graph partitioning provides a powerful approach to image segmentation. We introduce an alternate idea that finds partitions with a small isoperimetric constant, requiring solution to a linear system rather th...
详细信息
Spectral graph partitioning provides a powerful approach to image segmentation. We introduce an alternate idea that finds partitions with a small isoperimetric constant, requiring solution to a linear system rather than an eigenvector problem. This approach produces the high quality segmentations of spectral methods, but with improved speed and stability.
Combinatorial graph cut algorithms have been successfully applied to a wide range of problems in vision and graphics. This paper focusses on possibly the simplest application of graph-cuts: segmentation of objects in ...
详细信息
Combinatorial graph cut algorithms have been successfully applied to a wide range of problems in vision and graphics. This paper focusses on possibly the simplest application of graph-cuts: segmentation of objects in image data. Despite its simplicity, this application epitomizes the best features of combinatorial graph cuts methods in vision: global optima, practical efficiency, numerical robustness, ability to fuse a wide range of visual cues and constraints, unrestricted topological properties of segments, and applicability to N-D problems. graph cuts based approaches to object extraction have also been shown to have interesting connections with earlier segmentation methods such as snakes, geodesic active contours, and level-sets. The segmentation energies optimized by graph cuts combine boundary regularization with region-based properties in the same fashion as Mumford-Shah style functionals. We present motivation and detailed technical description of the basic combinatorial optimization framework for image segmentation via s/t graph cuts. After the general concept of using binary graph cut algorithms for object segmentation was first proposed and tested in Boykov and Jolly (2001), this idea was widely studied in computer vision and graphics communities. We provide links to a large number of known extensions based on iterative parameter re-estimation and learning, multi-scale or hierarchical approaches, narrow bands, and other techniques for demanding photo, video, and medical applications.
A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing grap...
详细信息
A binary linear programming formulation of the graph edit distance for unweighted, undirected graphs with vertex attributes is derived and applied to a graph recognition problem. A general formulation for editing graphs is used to derive a graph edit distance that is proven to be a metric, provided the cost function for individual edit operations is a metric. Then, a binary linear program is developed for computing this graph edit distance, and polynomial time methods for determining upper and lower bounds on the solution of the binary program are derived by applying solution methods for standard linear programming and the assignment problem. A recognition problem of comparing a sample input graph to a database of known prototype graphs in the context of a chemical information system is presented as an application of the new method. The costs associated with various edit operations are chosen by using a minimum normalized variance criterion applied to pairwise distances between nearest neighbors in the database of prototypes. The new metric is shown to perform quite well in comparison to existing metrics when applied to a database of chemical graphs.
Availability of large-scale experimental data for cell biology is enabling computational methods to systematically model the behaviour of cellular networks. This review surveys the recent advances in the field of grap...
详细信息
Availability of large-scale experimental data for cell biology is enabling computational methods to systematically model the behaviour of cellular networks. This review surveys the recent advances in the field of graph-driven methods for analysing complex cellular networks. The methods are outlined on three levels of increasing complexity, ranging from methods that can characterize global or local structural properties of networks to methods that can detect groups of interconnected nodes, called motifs or clusters, potentially involved in common elementary biological functions. We also briefly summarize recent approaches to data integration and network inference through graph-based formalisms. Finally, we highlight some challenges in the field and offer our personal view of the key future trends and developments in graph-based analysis of large-scale datasets.
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practic...
详细信息
ISBN:
(纸本)3540345973
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in O(m root n) time and gives an additive error of O(root n) for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].
We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter...
详细信息
We consider the problem of partitioning a graph into k components of roughly equal size while minimizing the capacity of the edges between different components of the cut. In particular we require that for a parameter nu >= 1, no component contains more than. nu . n/k of the graph vertices. For k = 2 and nu = 1 this problem is equivalent to the well-known Minimum Bisection problem for which an approximation algorithm with a polylogarithmic approximation guarantee has been presented in [FK]. For arbitrary k and nu >= 2 a bicriteria approximation ratio of O(log n) was obtained by Even et al. [ENRS1] using the spreading metrics technique. We present a bicriteria approximation algorithm that for any constant nu> 1 runs in polynomial time and guarantees an approximation ratio of O(log(1.5) n) ( for a precise statement of the main result see Theorem 6). For nu = 1 and k >= 3 we show that no polynomial time approximation algorithm can guarantee a finite approximation ratio unless P = NP.
作者：
Galeyev, Bulat M.Institute 'Prometei
' Kazan State Technical University Academy of Sciences of Tatarstan K. Marx Str. 10 Kazan 420111 Russia
The article discusses 'The Singing Shamail,' a computer installation created for the Kul Sharif mosque in Kazan, Russia. The installation plays shamails, a form of calligraphy based on sections of the Koran. T...
详细信息
The article discusses 'The Singing Shamail,' a computer installation created for the Kul Sharif mosque in Kazan, Russia. The installation plays shamails, a form of calligraphy based on sections of the Koran. The author discusses how computer systems can use graphic drawings to create music and notes the development of synthesizers that use algorithms to determine sound pitch based on the vertical aspects of an image, while the horizontal axis controls the timing of the musical composition. The author suggests that curves and spirals may incorporated into sound image computer systems.
We prove that for any epsilon > 0 there exists an integer n(epsilon) such that the pathwidth of every cubic (or 3-regular) graph on n > n(epsilon) vertices is at most (1/6 + epsilon)n. Based on this bound we imp...
详细信息
We prove that for any epsilon > 0 there exists an integer n(epsilon) such that the pathwidth of every cubic (or 3-regular) graph on n > n(epsilon) vertices is at most (1/6 + epsilon)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three. (c) 2005 Elsevier B.V. All rights reserved.
暂无评论