TY - JOUR
AB - In this paper we explicitly calculate the analogue of the 't Hooft SU (2) Yang-Mills instantons on Gibbons-Hawking multi-centered gravitational instantons, which come in two parallel families: the multi-Eguchi-Hanson, or Ak ALE gravitational instantons and the multi-Taub-NUT spaces, or Ak ALF gravitational instantons. We calculate their energy and find the reducible ones. Following Kronheimer we also exploit the U(1) invariance of our solutions and study the corresponding explicit singular SU (2) magnetic monopole solutions of the Bogomolny equations on flat ℝ3.
AU - Etesi, Gábor
AU - Tamas Hausel
ID - 1459
IS - 2
JF - Communications in Mathematical Physics
TI - On Yang-Mills instantons over multi-centered gravitational instantons
VL - 235
ER -
TY - CONF
AB - Geodesic active contours and graph cuts are two standard image segmentation techniques. We introduce a new segmentation method combining some of their benefits. Our main intuition is that any cut on a graph embedded in some continuous space can be interpreted as a contour (in 2D) or a surface (in 3D). We show how to build a grid graph and set its edge weights so that the cost of cuts is arbitrarily close to the length (area) of the corresponding contours (surfaces) for any anisotropic Riemannian metric. There are two interesting consequences of this technical result. First, graph cut algorithms can be used to find globally minimum geodesic contours (minimal surfaces in 3D) under arbitrary Riemannian metric for a given set of boundary conditions. Second, we show how to minimize metrication artifacts in existing graph-cut based methods in vision. Theoretically speaking, our work provides an interesting link between several branches of mathematics -differential geometry, integral geometry, and combinatorial optimization. The main technical problem is solved using Cauchy-Crofton formula from integral geometry.
AU - Boykov, Yuri
AU - Vladimir Kolmogorov
ID - 3170
TI - Computing geodesics and minimal surfaces via graph cuts
VL - 1
ER -
TY - CONF
AB - Reconstructing a 3-D scene from more than one camera is a classical problem in computer vision. One of the major sources of difficulty is the fact that not all scene elements are visible from all cameras. In the last few years, two promising approaches have been developed 11,12 that formulate the scene reconstruction problem in terms of energy minimization, and minimize the energy using graph cuts. These energy minimization approaches treat the input images symmetrically, handle visibility constraints correctly, and allow spatial smoothness to be enforced. However, these algorithm propose different problem formulations, and handle a limited class of smoothness terms. One algorithm 11 uses a problem formulation that is restricted to two-camera stereo, and imposes smoothness between a pair of cameras. The other algorithm 12 can handle an arbitrary number of cameras, but imposes smoothness only with respect to a single camera. In this paper we give a more general energy minimization formulation for the problem, which allows a larger class of spatial smoothness constraints. We show that our formulation includes both of the previous approaches as special cases, as well as permitting new energy functions. Experimental results on real data with ground truth are also included.
AU - Vladimir Kolmogorov
AU - Zabih, Ramin
AU - Gortler, Steven
ID - 3171
TI - Generalized multi camera scene reconstruction using graph cuts
VL - 2683
ER -
TY - CONF
AB - We address visual correspondence problems without assuming that scene points have similar intensities in different views. This situation is common, usually due to non-lambertian scenes or to differences between cameras. We use maximization of mutual information, a powerful technique for registering images that requires no a priori model of the relationship between scene intensities in different views. However, it has proven difficult to use mutual information to compute dense visual correspondence. Comparing fixed-size windows via mutual information suffers from the well-known problems of fixed windows, namely poor performance at discontinuities and in low-texture regions. In this paper, we show how to compute visual correspondence using mutual information without suffering from these problems. Using 'a simple approximation, mutual information can be incorporated into the standard energy minimization framework used in early vision. The energy can then be efficiently minimized using graph cuts, which preserve discontinuities and handle low-texture regions. The resulting algorithm combines the accurate disparity maps that come from graph cuts with the tolerance for intensity changes that comes from mutual information.
AU - Kim, Junhwan
AU - Vladimir Kolmogorov
AU - Zabih, Ramin
ID - 3174
TI - Visual correspondence using energy minimization and mutual information
VL - 2
ER -
TY - JOUR
AB - We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.
AU - Krzysztof Pietrzak
ID - 3209
IS - 4
JF - Journal of Computer and System Sciences
TI - On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
VL - 67
ER -