TY - CONF AB - We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms. AU - Vladimir Kolmogorov ID - 3204 TI - Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions VL - 6907 ER - TY - CONF AB - In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submod-ular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial problem into sub-problems corresponding to a specific class label while preserving the graph structure of each subproblem. Such decomposition enables us to take into account several types of global constraints in an efficient manner. We study theoretical properties of the proposed approach and demonstrate its applicability on a number of problems. AU - Osokin, Anton AU - Vetrov, Dmitry AU - Vladimir Kolmogorov ID - 3206 TI - Submodular decomposition framework for inference in associative Markov networks with global constraints ER - TY - CONF AB - This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems. AU - Tarlow, Daniel AU - Batra, Druv AU - Kohli, Pushmeet AU - Vladimir Kolmogorov ID - 3205 TI - Dynamic tree block coordinate ascent ER - TY - CONF AB - Cosegmentation is typically defined as the task of jointly segmenting something similar in a given set of images. Existing methods are too generic and so far have not demonstrated competitive results for any specific task. In this paper we overcome this limitation by adding two new aspects to cosegmentation: (1) the "something" has to be an object, and (2) the "similarity" measure is learned. In this way, we are able to achieve excellent results on the recently introduced iCoseg dataset, which contains small sets of images of either the same object instance or similar objects of the same class. The challenge of this dataset lies in the extreme changes in viewpoint, lighting, and object deformations within each set. We are able to considerably outperform several competitors. To achieve this performance, we borrow recent ideas from object recognition: the use of powerful features extracted from a pool of candidate object-like segmentations. We believe that our work will be beneficial to several application areas, such as image retrieval. AU - Vicente, Sara AU - Rother, Carsten AU - Vladimir Kolmogorov ID - 3207 TI - Object cosegmentation ER - TY - CONF AB - The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two limitations: - Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL - large entropy loss and large seed - can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. Second, we study the soundness of the natural expand-then-extract approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S′, and then use the resulting S′ as the seed required by the LHL (or, more generally, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that the expand-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! © 2011 International Association for Cryptologic Research. AU - Barak, Boaz AU - Dodis, Yevgeniy AU - Krawczyk, Hugo AU - Pereira, Olivier AU - Krzysztof Pietrzak AU - Standaert, François-Xavier AU - Yu, Yu ID - 3240 TI - Leftover hash lemma revisited VL - 6841 ER - TY - CONF AB - Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms. AU - Gupta, Ashutosh AU - Popeea, Corneliu AU - Rybalchenko, Andrey ED - Yang, Hongseok ID - 3264 TI - Solving recursion-free Horn clauses over LI+UIF VL - 7078 ER - TY - CONF AB - We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories. The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag [1], followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning. We show that the proposed methodologymatches the current state of the art in the Stanford dataset [2], as well as in VOC2010, where 41.7% accuracy on the test set is achieved. AU - Ion, Adrian AU - Carreira, Joao AU - Sminchisescu, Cristian ID - 3266 T2 - NIPS Proceedings TI - Probabilistic joint image segmentation and labeling VL - 24 ER - TY - JOUR AB - The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods. AU - Sheng, Yu AU - Cutler, Barbara AU - Chen, Chao AU - Nasman, Joshua ID - 3269 IS - 4 JF - Computer Graphics Forum TI - Perceptual global illumination cancellation in complex projection environments VL - 30 ER - TY - JOUR AB - We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field. AU - Chen, Chao AU - Freedman, Daniel ID - 3267 IS - 3 JF - Discrete & Computational Geometry TI - Hardness results for homology localization VL - 45 ER - TY - CHAP AB - Algebraic topology is generally considered one of the purest subfield of mathematics. However, over the last decade two interesting new lines of research have emerged, one focusing on algorithms for algebraic topology, and the other on applications of algebraic topology in engineering and science. Amongst the new areas in which the techniques have been applied are computer vision and image processing. In this paper, we survey the results of these endeavours. Because algebraic topology is an area of mathematics with which most computer vision practitioners have no experience, we review the machinery behind the theories of homology and persistent homology; our review emphasizes intuitive explanations. In terms of applications to computer vision, we focus on four illustrative problems: shape signatures, natural image statistics, image denoising, and segmentation. Our hope is that this review will stimulate interest on the part of computer vision researchers to both use and extend the tools of this new field. AU - Freedman, Daniel AU - Chen, Chao ID - 3268 T2 - Computer Vision TI - Algebraic topology for computer vision ER -