3207638
A topology preserving deformable model using level sets
Active contour and surface models, also known as deformable models, constitute a class of powerful segmentation techniques. Geometric deformable models implemented via level-set methods have advantages over parametric ones due to their intrinsic behavior, parameterization independence, and ease of implementation. However, a long claimed advantage of geometric deformable models, the ability to automatically handle topology changes, turns out to be a liability in applications where the objects to be segmented have a known topology that must be preserved. In this paper, we present a geometric deformable model that preserves topology using the simple point concept from digital topology. This algorithm maintains the other advantages of standard geometric deformable models including sub-pixel accuracy and production of nonintersecting curves (or surfaces). Several experiments on simulated and real data are provided to demonstrate the performance of the proposed algorithm.
18666511
Finding the Brain Cortex Using Fuzzy Segmentation, Isosurfaces, and Deformable Surface Models
A method for finding the cortical surface of the brain from magnetic resonance images using a combination of fuzzy segmentation, isosurface extraction, and a deformable surface is presented. After MR images are acquired and preprocessed to remove extracranial tissue, fuzzy membership functions for gray matter, white matter, and cerebrospinal fluid are computed. An iterative procedure using isosurfaces of filtered white matter membership functions is then used to obtain a topologically correct estimate of the cortical surface. This estimate forms the initialization of a deformable surface, which is then allowed to converge to peaks of the gray matter membership function. We demonstrate the results of each step and show the final parameterized map of the medial layer of the cortex.
3055871
A Topology Preserving Level Set Method for Geometric Deformable Models
Active contour and surface models, also known as deformable models, are powerful image segmentation techniques. Geometric deformable models implemented using level set methods have advantages over parametric models due to their intrinsic behavior, parameterization independence, and ease of implementation. However, a long claimed advantage of geometric deformable models-the ability to automatically handle topology changes-turns out to be a liability in applications where the object to be segmented has a known topology that must be preserved. We present a new class of geometric deformable models designed using a novel topology-preserving level set method, which achieves topology preservation by applying the simple point concept from digital topology. These new models maintain the other advantages of standard geometric deformable models including subpixel accuracy and production of nonintersecting curves or surfaces. Moreover, since the topology-preserving constraint is enforced efficiently through local computations, the resulting algorithm incurs only nominal computational overhead over standard geometric deformable models. Several experiments on simulated and real data are provided to demonstrate the performance of this new deformable model algorithm.
15546541
Reconstruction of the Central Layer of the Human Cerebral Cortex from MR Images
Reconstruction of the human cerebral cortex from MR images is a fundamental step in human brain mapping and in applications such as surgical path planning. In a previous paper, we described a method for obtaining a surface representation of the central layer of the human cerebral cortex using fuzzy segmentation and a deformable surface model. This method, however, suffers from several problems. In this paper, we significantly improve upon the previous method by using a fuzzy segmentation algorithm robust to intensity inhomogeneities, and using a deformable surface model specifically designed for capturing convoluted sulci or gyri. We demonstrate the improvement over the previous method both qualitatively and quantitatively, and show the result of its application to six subjects. We also experimentally validate the convergence of the deformable surface initialization algorithm.
1958666
A 2D moving grid geometric deformable model
Geometric deformable models based on the level set method have become very popular. To overcome an inherent limitation in accuracy while maintaining computational efficiency, adaptive grid techniques using local grid refinement have been developed for use with these models. However, this strategy requires a very complex data structure, yields large numbers of contour points, and is inconsistent with our previously presented topology-preserving geometric deformable model (TGDM). In this paper, we incorporate an alternative adaptive grid technique called the moving grid method into the geometric deformable model framework. We find that it is simpler to implement than grid refinement, requiring no large, complex, hierarchical data structures. It also limits the number of contour vertices in the final contour and supports the incorporation of the topology-preserving constraint of TGDM. After presenting the algorithm, we demonstrate its performance using both simulated and real images.
6175091
Snakes, shapes, and gradient vector flow
Snakes, or active contours, are used extensively in computer vision and image processing applications, particularly to locate object boundaries. Problems associated with initialization and poor convergence to boundary concavities, however, have limited their utility. This paper presents a new external force for active contours, largely solving both problems. This external force, which we call gradient vector flow (GVF), is computed as a diffusion of the gradient vectors of a gray-level or binary edge map derived from the image. It differs fundamentally from traditional snake external forces in that it cannot be written as the negative gradient of a potential function, and the corresponding snake is formulated directly from a force balance condition rather than a variational formulation. Using several two-dimensional (2-D) examples and one three-dimensional (3-D) example, we show that GVF has a large capture range and is able to move snakes into boundary concavities.
33974470
A necessary and sufficient condition for a graph G with diameter 5 to be 2-diameter-stable
Abstract A graph G is called an ( l, d )-graph (with respect to edges), if d ( G − E )⩽ d , for each E ⊂ E ( G ) such that | E |⩽ l − 1. The l -diameter-stable graphs are ( l, d )-graphs with diameter d . These two concepts were first proposed by Hartman and Rubin [1]. A necessary and sufficient condition for a graph G with diameter 2 or 3 to be 2-diameter-stable was given in [1]. A necessary and sufficient condition for a graph G with diameter 4 to be 2-diameter-stable was given in [2]. In this paper similar result was obtained for graphs with diameter 5.
1880898
Energy-aware modeling and scheduling of real-time tasks for dynamic voltage scaling
Dynamic voltage scaling (DVS) is a promising technique for battery-powered systems to conserve energy consumption. Most existing DVS algorithms assume information about task periodicity or a priori knowledge about the task set to be scheduled. This paper presents an analytical model of general tasks for DVS assuming job timing information is known only after a task release. It models the voltage scaling process as a transfer function-based filter system, which facilitates the design of two efficient scaling algorithms. The first is a time-invariant scaling policy based on a voltage scaling function independent of input jobs over time. It is proved to be a generalization of several existing DVS algorithms. A more energy efficient policy is a time-variant scaling algorithm. The algorithm turns out to be a water-filling process of information theory with a low time complexity. It can not only be applied to scheduling based on worst case execution times, but also to online slack distribution when jobs complete earlier. We further establish two relationships between computation capacity and deadline misses. The relationships make it possible to the provisioning of statistical real-time guarantees
40281534
Processing Rate Allocation for Proportional Slowdown Differentiation on Internet Servers
Summary form only given. A proportional differentiation model states that quality of service of different classes of Internet traffic should be kept proportional to their prespecified differentiation parameters, independent of the class loads. The model has been applied in the proportional queueing delay differentiation (FDD) in both network core and network edges. However, in the server side, an important and interesting performance metric is slowdown, the ratio of a request's queueing delay to its service time. Slowdown is important because it is desirable that a request's delay be proportional to its processing requirement. We investigate the problem of processing rate allocation for proportional slowdown differentiation (PSD) on Internet servers. Existing algorithms for FDD provisioning in the network side are not applicable to PSD provisioning in the server side because slowdown is not only dependent on a job's queueing delay but also on its service time, which varies significantly depending on the requested services. We first derive a closed form expression of the expected slowdown in an M/Gp/1 FCFS queue, which is an M/G/l FCFS queue with a typical heavy-tailed service time distribution (bounded Pareto distribution). PSD provisioning is realized by deploying a task server for handling each request class in a FCFS way. We then develop a strategy of processing rate allocation for the task servers for PSD provisioning. Simulation results have showed that the proposed rate allocation strategy can provide predictable and controllable PSD services on the servers.
7866792
Relaxed Implementation of Spectral Methods for Graph Partitioning
This paper presents a fast implementation of the recursive spectral bisection method for p-way partitioning. It is known that recursive bisections for p-way partitioning using optimal strategies at each step may not lead to a good overall solution. The relaxed implementation accelerates the partitioning process by relaxing the accuracy requirement of spectral bisection (SB) method. Considering the solution quality of a SB method on a graph is primarily determined by the accuracy of its Fiedler vector, we propose to set a tight iteration number bound and a loose residual tolerance for Lanczos algorithms to compute the Fiedler vector. The relaxed SB was tested on eight representative meshes from different applications. Experimental results show that the relaxed SB on six meshes produces approximately equivalent quality solutions as the Chaco SB while gaining 10% to 35% improvements in execution time. On the other two meshes, the relaxed SB approaches the Chaco SB in quality as p increases and reduces the execution time by 40% to 70%. Coupled with the Kernighan-Lin local refinement algorithm, the relaxed SB is able to yield high quality solutions in all test cases as p goes beyond 32. Multilevel and spectral quadrisection algorithms benefit from relaxed implementations, as well.
8693838
eQoS: Provisioning of Client-Perceived End-to-End QoS Guarantees in Web Servers
It is important to guarantee client-perceived end-to-end quality of service (QoS) under heavy load conditions. Existing work focuses on network transfer time or server-side request processing time. In this paper, we propose a novel framework, eQoS, to monitor and control client-perceived response time in heavy loaded Web servers. The response time is measured with respect to Web pages that contain multiple embedded objects. Within the framework, we propose an adaptive fuzzy controller, STFC, to allocate server resources. The controller assumes no knowledge of the pageview traffic model. It deals with the effect of process delay in resource allocation by its two-level self-tuning capabilities. We also prove the stability of the STFC. We implement a prototype of eQoS in Linux and conduct comprehensive experiments across wide-range server workload conditions on PlanetLab and simulated networks. Experimental results demonstrate the effectiveness of the framework: it controls the deviation of client-perceived pageview response time to be within 20 percent of a predefined target with both synthetic and real Web traffics. We also compare the STFC with other controllers, including static fuzzy, linear proportional integral (PI), and adaptive PI controllers. Experimental results show that, although the STFC works slightly worse than the static fuzzy controller in the environment where the static fuzzy controller is best tuned, because of its self-tuning capabilities, it has better performance in all other test cases by around 25 percent on average in terms of the deviation from the target response time. In addition, due to its model independence, the STFC outperforms the linear PI and adaptive PI controllers by 50 percent and 75 percent on average, respectively