TY - JOUR
AB - The simultaneous multiple volume (SMV) approach in navigator-gated MRI allows the use of the whole motion range or the entire scan time for the reconstruction of final images by simultaneously acquiring different image volumes at different motion states. The motion tolerance range for each volume is kept small, thus SMV substantially increases the scan efficiency of navigator methods while maintaining the effectiveness of motion suppression. This article reports a general implementation of the SMV approach using a multiprocessor scheduling algorithm. Each motion state is regarded as a processor and each volume is regarded as a job. An efficient scheduling that completes all jobs in minimal time is maintained even when the motion pattern changes. Initial experiments demonstrated that SMV significantly increased the scan efficiency of navigatorgated MRI.
AU - Vladimir Kolmogorov
AU - Nguyen, Thành D
AU - Nuval, Anthony
AU - Spincemaille, Pascal
AU - Prince, Martin R
AU - Zabih, Ramin
AU - Wang, Yusu
ID - 3172
IS - 2
JF - Magnetic Resonance in Medicine
TI - Multiprocessor scheduling implementation of the simultaneous multiple volume SMV navigator method
VL - 52
ER -
TY - JOUR
AB - In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.
AU - Vladimir Kolmogorov
AU - Zabih, Ramin
ID - 3173
IS - 2
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - What energy functions can be minimized via graph cuts?
VL - 26
ER -
TY - CONF
AB - Feature space clustering is a popular approach to image segmentation, in which a feature vector of local properties (such as intensity, texture or motion) is computed at each pixel. The feature space is then clustered, and each pixel is labeled with the cluster that contains its feature vector. A major limitation of this approach is that feature space clusters generally lack spatial coherence (i.e., they do not correspond to a compact grouping of pixels). In this paper, we propose a segmentation algorithm that operates simultaneously in feature space and in image space. We define an energy function over both a set of clusters and a labeling of pixels with clusters. In our framework, a pixel is labeled with a single cluster (rather than, for example, a distribution over clusters). Our energy function penalizes clusters that are a poor fit to the data in feature space, and also penalizes clusters whose pixels lack spatial coherence. The energy function can be efficiently minimized using graph cuts. Our algorithm can incorporate both parametric and non-parametric clustering methods. It can be applied to many optimization-based clustering methods, including k-means and k-medians, and can handle models which are very close in feature space. Preliminary results are presented on segmenting real and synthetic images, using both parametric and non-parametric clustering.
AU - Zabih, Ramin
AU - Vladimir Kolmogorov
ID - 3177
TI - Spatially coherent clustering using graph cuts
VL - 2
ER -
TY - JOUR
AB - Minimum cut/maximum flow algorithms on graphs have emerged as an increasingly useful tool for exactor approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push -relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.
AU - Boykov, Yuri
AU - Vladimir Kolmogorov
ID - 3178
IS - 9
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision
VL - 26
ER -
TY - CONF
AB - The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.
AU - Rother, Carsten
AU - Vladimir Kolmogorov
AU - Blake, Andrew
ID - 3179
IS - 3
TI - "GrabCut" - Interactive foreground extraction using iterated graph cuts
VL - 23
ER -
TY - CONF
AB - A new technique for proving the adaptive indistinguishability of two systems, each composed of some component systems, is presented, using only the fact that corresponding component systems are non-adaptively indistinguishable. The main tool is the definition of a special monotone condition for a random system F, relative to another random system G, whose probability of occurring for a given distinguisher D is closely related to the distinguishing advantage ε of D for F and G, namely it is lower and upper bounded by ε and (1+ln1), respectively.
A concrete instantiation of this result shows that the cascade of two random permutations (with the second one inverted) is indistinguishable from a uniform random permutation by adaptive distinguishers which may query the system from both sides, assuming the components’ security only against non-adaptive one-sided distinguishers.
As applications we provide some results in various fields as almost k-wise independent probability spaces, decorrelation theory and computational indistinguishability (i.e., pseudo-randomness).
AU - Maurer, Ueli M
AU - Krzysztof Pietrzak
ID - 3208
TI - Composition of random systems: When two weak make one strong
VL - 2951
ER -
TY - JOUR
AB - The folding and stability of transmembrane proteins is a fundamental and unsolved biological problem. Here, single bacteriorhodopsin molecules were mechanically unfolded from native purple membranes using atomic force microscopy and force spectroscopy. The energy landscape of individual transmembrane α helices and polypeptide loops was mapped by monitoring the pulling speed dependence of the unfolding forces and applying Monte Carlo simulations. Single helices formed independently stable units stabilized by a single potential barrier. Mechanical unfolding of the helices was triggered by 3.9–7.7 Å extension, while natural unfolding rates were of the order of 10−3 s−1. Besides acting as individually stable units, helices associated pairwise, establishing a collective potential barrier. The unfolding pathways of individual proteins reflect distinct pulling speed-dependent unfolding routes in their energy landscapes. These observations support the two-stage model of membrane protein folding in which α helices insert into the membrane as stable units and then assemble into the functional protein.
AU - Harald Janovjak
AU - Struckmeier, Jens
AU - Hubain, Maurice
AU - Kessler, Max
AU - Kedrov, Alexej
AU - Mueller, Daniel J
ID - 3419
IS - 5
JF - Structure
TI - Probing the energy landscape of the membrane protein bacteriorhodopsin
VL - 12
ER -
TY - JOUR
AB - Single-molecule force-spectroscopy was employed to unfold and refold single sodium-proton antiporters (NhaA) of Escherichia coli from membrane patches. Although transmembrane α-helices and extracellular polypeptide loops exhibited sufficient stability to individually establish potential barriers against unfolding, two helices predominantly unfolded pairwise, thereby acting as one structural unit. Many of the potential barriers were detected unfolding NhaA either from the C-terminal or the N-terminal end. It was found that some molecular interactions stabilizing secondary structural elements were directional, while others were not. Additionally, some interactions appeared to occur between the secondary structural elements. After unfolding ten of the 12 helices, the extracted polypeptide was allowed to refold back into the membrane. After five seconds, the refolded polypeptide established all secondary structure elements of the native protein. One helical pair showed a characteristic spring like “snap in” into its folded conformation, while the refolding process of other helices was not detected in particular. Additionally, individual helices required characteristic periods of time to fold. Correlating these results with the primary structure of NhaA allowed us to obtain the first insights into how potential barriers establish and determine the folding kinetics of the secondary structure elements.
AU - Kedrov, Alexej
AU - Ziegler, Christine
AU - Harald Janovjak
AU - Kühlbrandt, Werner
AU - Mueller, Daniel J
ID - 3420
IS - 5
JF - Journal of Molecular Biology
TI - Controlled unfolding and refolding of a single sodium/proton antiporter using atomic force microscopy
VL - 340
ER -
TY - CHAP
AU - Herbert Edelsbrunner
ID - 3574
T2 - Handbook of Discrete and Computational Geometry
TI - Biological applications of computational topology
ER -
TY - CHAP
AB - The Jacobi set of two Morse functions defined on a common - manifold is the set of critical points of the restrictions of one func- tion to the level sets of the other function. Equivalently, it is the set of points where the gradients of the functions are parallel. For a generic pair of Morse functions, the Jacobi set is a smoothly embed- ded 1-manifold. We give a polynomial-time algorithm that com- putes the piecewise linear analog of the Jacobi set for functions specified at the vertices of a triangulation, and we generalize all results to more than two but at most Morse functions.
AU - Herbert Edelsbrunner
AU - Harer, John
ID - 3575
T2 - Foundations of Computational Mathematics
TI - Jacobi sets of multiple Morse functions
VL - 312
ER -