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 -
TY - CONF
AB - Luby and Rackoff showed how to construct a (super-)pseudo-random permutation {0,1}2n→ {0,1}2n from some number r of pseudo-random functions {0,1}n → {0,1}n. Their construction, motivated by DES, consists of a cascade of r Feistel permutations. A Feistel permutation 1for a pseudo-random function f is defined as (L, R) → (R,L ⊕ f (R)), where L and R are the left and right part of the input and ⊕ denotes bitwise XOR or, in this paper, any other group operation on {0,1}n. The only non-trivial step of the security proof consists of proving that the cascade of r Feistel permutations with independent uniform random functions {0,1}n → {0,1}n, denoted Ψ2nr is indistinguishable from a uniform random permutation {0,1}2n → {0,1}2n by any computationally unbounded adaptive distinguisher making at most O(2cn) combined chosen plaintext/ciphertext queries for any c < α, where a is a security parameter. Luby and Rackoff proved α = 1/2 for r = 4. A natural problem, proposed by Pieprzyk is to improve on α for larger r. The best known result, α = 3/4 for r = 6, is due to Patarin. In this paper we prove a = 1 -O(1/r), i.e., the trivial upper bound α = 1 can be approached. The proof uses some new techniques that can be of independent interest.
AU - Maurer, Ueli M
AU - Krzysztof Pietrzak
ID - 3210
TI - The security of many round Luby Rackoff pseudo random permutations
VL - 2656
ER -