nips nips2010 nips2010-234 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: William Brendel, Sinisa Todorovic
Abstract: Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually “meaningful” segments in the ensemble. Knowledge about any specific objects and surfaces present in the image is not available. The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. MWIS is the heaviest subset of mutually non-adjacent nodes of an attributed graph. We construct such a graph from all segments in the ensemble. Then, MWIS selects maximally distinctive segments that together partition the image. A new MWIS algorithm is presented. The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. The algorithm is shown to converge to an optimum. Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results.
Reference: text
sentIndex sentText sentNum sentScore
1 edu Abstract Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually “meaningful” segments in the ensemble. [sent-5, score-0.425]
2 Knowledge about any specific objects and surfaces present in the image is not available. [sent-6, score-0.149]
3 The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. [sent-7, score-0.196]
4 We construct such a graph from all segments in the ensemble. [sent-9, score-0.355]
5 Then, MWIS selects maximally distinctive segments that together partition the image. [sent-10, score-0.291]
6 The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. [sent-12, score-0.137]
7 It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. [sent-13, score-0.132]
8 Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results. [sent-15, score-0.271]
9 1 Introduction This paper presents: (1) a new formulation of image segmentation as the maximum-weight independent set (MWIS) problem; and (2) a new algorithm for solving MWIS. [sent-16, score-0.288]
10 Image segmentation is a fundamental problem, and an area of active research in computer vision and machine learning. [sent-17, score-0.196]
11 It seeks to group image pixels into visually “meaningful” segments, i. [sent-18, score-0.142]
12 , those segments that are occupied by objects and other surfaces occurring in the scene. [sent-20, score-0.374]
13 For example, normalized-cut [1], and dominant set [2] formulate segmentation as a combinatorial optimization problem on a graph representing image pixels. [sent-22, score-0.374]
14 “Meaningful” segments may give rise to modes of the pixels’ probability distribution [3], or minimize the Mumford-Shah energy [4]. [sent-23, score-0.291]
15 Segmentation can also be done by: (i) integrating edge and region detection [5], (ii) learning to detect and close object boundaries [6, 7], and (iii) identifying segments which can be more easily described by their own parts than by other image parts [8, 9, 10]. [sent-24, score-0.412]
16 First, surfaces of real-world objects are typically made of a unique material, and thus their corresponding segments in the image are characterized by unique photometric properties, distinct from those of other regions. [sent-26, score-0.474]
17 To capture this distinctiveness, it seems beneficial to use more expressive, mid-level image features (e. [sent-27, score-0.092]
18 Second, it seems that none of a host of segmentation formulations are able to correctly delineate every object boundary present. [sent-30, score-0.196]
19 However, an ensemble of distinct segmentations is likely to contain a subset of segments that provides accurate spatial support of object occurrences. [sent-31, score-0.459]
20 Based on these two hypotheses, below, we present a new formulation of image segmentation. [sent-32, score-0.092]
21 1 Given an ensemble of segments, extracted from the image by a number of different low-level segmenters, our goal is to select those segments from the ensemble that are distinct, and together partition the image area. [sent-33, score-0.589]
22 Suppose all segments from the ensemble are represented as nodes of a graph, where node weights capture the distinctiveness of corresponding segments, and graph edges connect nodes whose corresponding segments overlap in the image. [sent-34, score-0.945]
23 Then, the selection of maximally distinctive and non-overlapping segments that will partition the image naturally lends itself to the maximum-weight independent set (MWIS) formulation. [sent-35, score-0.383]
24 For example, iterated tabu search [12] and branch-and-price [13] use a trial-and-error, greedy search in the space of possible solutions, with an optimistic complexity estimate of O(n3 ), where n is the number of nodes in the graph. [sent-40, score-0.16]
25 The message passing [14] relaxes MWIS into a linear program (LP), and solves it using loopy belief propagation with no guarantees of convergence for general graphs; the “tightness” of this relaxation holds only for bipartite graphs [15]. [sent-41, score-0.084]
26 Finally, the replicator dynamics [17, 18] converts the original graph into its complement, and solves MWIS as a continuous relaxation of the maximum weight clique (MWC) problem. [sent-44, score-0.235]
27 But in some domains, including ours, important hard constraints captured by edges of the original graph may be lost in this conversion. [sent-45, score-0.095]
28 It goes back and forth between the discrete and continuous domains. [sent-47, score-0.083]
29 Maximization in the discrete domain of the approximation gives ˜ ˜ a candidate discrete solution, x∈{0, 1}n . [sent-55, score-0.155]
30 For non-convex objective functions, our method tends to pass either through or near discrete solutions, and the best discrete one x∗ encountered along the path is returned. [sent-58, score-0.127]
31 Contributions: To the best of our knowledge, this paper presents the first formulation of image segmentation as MWIS. [sent-60, score-0.31]
32 Selecting segments from an ensemble so they cover the entire image and minimize a total energy has been used for supervised object segmentation [19]. [sent-62, score-0.636]
33 They estimate “good” segments by using classifiers of a pre-selected number of object classes. [sent-63, score-0.291]
34 Our segmentation outperforms the state of the art on the benchmark Berkeley segmentation dataset, and our MWIS algorithm runs faster and yields on average more accurate solutions on benchmark datasets than other existing MWIS algorithms. [sent-68, score-0.47]
35 Step 1: The image is segmented using a number of different, off-the-shelf, low-level segmenters, including meanshift [3], Ncuts [1], and gPb-OWT-UCM [7]. [sent-71, score-0.205]
36 Since the right scale at which objects occur in the image is unknown, each of these segmentations is conducted at an exhaustive range of scales. [sent-72, score-0.234]
37 Step 2: The resulting segments are represented as nodes of a graph whose edges connect only those segments that (partially) overlap in the image. [sent-73, score-0.771]
38 A weight is associated with each node capturing the distinctiveness of the corresponding segment from the others. [sent-75, score-0.102]
39 Step 4: The segments selected in the MWIS may not be able to cover the entire image, or may slightly overlap (holes and overlaps are marked red in Fig. [sent-77, score-0.397]
40 The final segmentation is obtained by using standard morphological operators on region boundaries to eliminate these holes and overlaps. [sent-79, score-0.277]
41 the input low-level segmentation is strictly hierarchical, as gPb-OWT-UCM [7]. [sent-81, score-0.232]
42 The same holds if we added the intersections of all input segments to the input ensemble, as in [19], because our MWIS algorithm will continue selecting non-overlapping segments until the entire image is covered. [sent-82, score-0.768]
43 3 formulates image segmentation as MWIS, and describes how to construct the segmentation graph. [sent-86, score-0.507]
44 2 MWIS Formulation and Our Algorithm Consider a graph G = (V, E, ω), where V and E are the sets of nodes and undirected edges, with cardinalities |V |=n and |E|, and ω : V →R+ associates positive weights wi to every node i ∈ V , i=1, . [sent-90, score-0.162]
45 MWIS can be naturally posed as the following integer program (IP): IP: x∗ = argmaxx wT x, s. [sent-97, score-0.079]
46 Consequently, IP can be reformulated as / the following integer quadratic program (IQP): IQP: x∗ = argmaxx [wT x − 1 αxT Ax] 2 s. [sent-101, score-0.102]
47 For example, when ℓ1 norm is used as relaxation, the solution x∗ of (2) can be found using the replicator dynamics in the continuous domain [17]. [sent-112, score-0.142]
48 Usually, the solution found in the continuous domain is binarized to obtain a discrete solution. [sent-114, score-0.135]
49 In this paper, we present a new MWIS algorithm that iteratively seeks a solution directly in the discrete domain. [sent-116, score-0.104]
50 A discrete solution is computed by maximizing the first-order Taylor series approximation 3 of the quadratic objective in (2) around a solution found in the previous iteration. [sent-117, score-0.152]
51 Also, in our notation, 2 ˜ x, x, x∗ ∈ {0, 1}n denote a point, candidate solution, and solution, respectively, in the discrete domain; and y ∈ [0, 1]n denotes a point in the continuous domain. [sent-124, score-0.112]
52 Our algorithm is a fixed-point iteration that solves a sequence of integer programs which are convex approximations of f , around a solution found in the previous iteration. [sent-125, score-0.104]
53 The key intuition is that the approximations are simpler functions than f , and thus facilitate computing the candidate discrete solutions in each iteration. [sent-126, score-0.079]
54 Our algorithm visits a sequence of continuous points {y (1) , . [sent-128, score-0.081]
55 , and finds discrete candidate solutions x ∈ {0, 1}n in their respective neighborhoods, until convergence. [sent-137, score-0.079]
56 ˜ In the second step of iteration t, the algorithm verifies if x can be accepted as a new, valid discrete ˜ solution. [sent-148, score-0.078]
57 3 Formulating Segmentation as MWIS We formulate image segmentation as the MWIS of a graph of image regions obtained from different segmentations. [sent-184, score-0.491]
58 Given a set of all segments, V , extracted from the image by a number of distinct segmenters, we construct a graph, G = (V, E, ω), where V and E are the sets of nodes and undirected edges, and ω : V →R+ assigns positive weights wi to every node i ∈ V , i=1, . [sent-186, score-0.224]
59 Two nodes i and j are adjacent, (i, j) ∈ E, if their respective segments Si and Sj overlap in the image, Si ∩ Sj = ∅. [sent-190, score-0.385]
60 The weights wi should be larger for more “meaningful” segments Si , so that these segments are more likely included in the MWIS of G. [sent-196, score-0.611]
61 Note that this definition is suitable for identifying both: (i) distinct textures in the image, since texture can be defined as a spatial repetition of elementary 2D patterns; and (ii) homogeneous regions with smooth variations of brightness. [sent-198, score-0.152]
62 Specifically, given a dictionary of visual codewords, ¯ and the histogram of occurrence of the codewords in Si , we define wi = |Si |KL(Si , Si ), where KL ¯ denotes the Kullback Leibler divergence, I is the input image, and Si = I\Si . [sent-200, score-0.086]
63 Note that the selected segments will optimally cover the entire image, otherwise any uncovered image areas will be immediately filled out by available segments in V that do not overlap with already selected ones, because this will increase the IQP objective function f . [sent-208, score-0.747]
64 In the case when the input segments do not form a strict hierarchy and intersections of the input segments have not been added to V , we eliminate holes (or “soft” overlaps) between the selected segments by applying the standard morphological operations (e. [sent-209, score-1.068]
65 4 Results This section presents qualitative and quantitative evaluation of our segmentation on 200 images from the benchmark Berkeley segmentation dataset (BSD) [23]. [sent-212, score-0.478]
66 BSD images are challenging for segmentation, because they contain complex layouts of distinct textures (e. [sent-213, score-0.101]
67 We also evaluate the generality and execution time of our MWIS algorithm on a synthetic graph from benchmark OR-Library [24], and the problem sets from [12]. [sent-216, score-0.103]
68 The first type is a hierarchy of segments produced by the gPb-OWT-UCM method of [7]. [sent-218, score-0.34]
69 The second type is a hierarchy of segments produced by the multiscale algorithm of [5]. [sent-221, score-0.37]
70 Meanshift uses three input parameters: feature bandwidth bf , spatial bandwidth bs , and minimum region area Smin . [sent-226, score-0.094]
71 The variant ([3]+[1])+Ours evaluates our hypothesis that reasoning over an ensemble of distinct segmentations improves each individual one. [sent-232, score-0.168]
72 Segmentation of BSD images is used for a comparison with replicator dynamics approach of [17], which transforms the MWIS problem into the maximum weight clique problem, and then relaxes it into a continuous problem, denoted as MWC. [sent-233, score-0.149]
73 4 also shows the best segmentations of [7] and [25], obtained by an exhaustive search for the optimal values of their input parameters. [sent-239, score-0.169]
74 Our approach eliminates the need for hand-picking the optimal input parameters in [7], and yields results that are good even in cases when objects have complex textures (e. [sent-242, score-0.109]
75 Quantitative evaluation: Table 1 presents segmentations of BSD images using our three variants: [7]+Ours, [5]+Ours, and ([3]+[1])+Ours. [sent-247, score-0.124]
76 For [7], we report their best results obtained by an exhaustive search for the optimal value of their input parameter Pb . [sent-253, score-0.092]
77 Input segments are generated by the methods of [7, 5, 3, 1], and then selected by the maximum weight clique formulation (MWC) of [17], or by our algorithm. [sent-269, score-0.325]
78 For [7], we report their best results obtained by an exhaustive search for the optimal value of their input parameter Pb . [sent-270, score-0.092]
79 segments generated by Meanshift, Ncuts, and [5], the performances of [5]+Ours and ([3]+[1])+Ours come very close to those of [7]. [sent-271, score-0.291]
80 1 on two sets of problems beyond image segmentation. [sent-284, score-0.092]
81 As input we use a graph constructed from data from the OR-Library [24], and from the problem sets presented in [12]. [sent-285, score-0.1]
82 Failures, such as the painters’ shoulder, the bird’s lower body part, and the top left fish, occur simply because these regions are not present in the input segmentations. [sent-296, score-0.083]
83 Figure 4: Comparison with the state-of-the-art segmentation algorithms on BSD images. [sent-297, score-0.196]
84 By extracting “meaningful” segments from a segmentation hierarchy produced by [7] we correct the best, manually optimized results of [7]. [sent-301, score-0.536]
85 5 Conclusion To our knowledge, this is the first attempt to formulate image segmentation as MWIS. [sent-302, score-0.288]
86 Our empirical findings suggest that this is a powerful framework that permits good segmentation performance regardless of a particular MWIS algorithm used. [sent-303, score-0.196]
87 We have presented a new fixed point algorithm that efficiently solves MWIS, with complexity O(|E|), on a graph with |E| edges, and proved that the algorithm converges to a maximum. [sent-304, score-0.142]
88 Our MWIS algorithm seeks a solution directly in the discrete domain, instead of resorting to the relaxation, as is common in the literature. [sent-305, score-0.104]
89 Also, we have shown a comparison with the state-of-the-art segmenter [7] on the benchmark Berkeley segmentation dataset. [sent-307, score-0.235]
90 Our selection of “meaningful” regions from a segmentation hierarchy produced by [7] outperforms the manually optimized best results of [7], in terms of Probabilistic Rand Index and Variation of Information. [sent-308, score-0.292]
91 Malik, “Normalized cuts and image segmentation,” IEEE TPAMI, vol. [sent-311, score-0.092]
92 Ahuja, “A transform for multiscale image segmentation by integrated edge and region detection,” IEEE TPAMI, vol. [sent-335, score-0.318]
93 Zisserman, “Segmenting scenes by matching image composites,” in NIPS, 2009. [sent-364, score-0.092]
94 Palubeckis, “Iterated tabu search for the unconstrained binary quadratic optimization problem,” Informatica, vol. [sent-370, score-0.087]
95 Stix, “Approximating the maximum weight clique using replicator dynamics,” IEEE Trans. [sent-408, score-0.091]
96 Sukthankar, “An integer projected fixed point method for graph matching and MAP inference,” in NIPS, 2009. [sent-429, score-0.091]
97 Rangarajan, “A graduated assignment algorithm for graph matching,” IEEE TPAMI, vol. [sent-432, score-0.096]
98 Malik, “A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics,” in ICCV, 2001. [sent-443, score-0.221]
99 Brandt, “Texture segmentation by multiscale aggregation of filter responses and shape elements,” in ICCV, 2003, pp. [sent-454, score-0.226]
100 Hebert, “Toward objective evaluation of image segmentation algorithms,” IEEE TPAMI, vol. [sent-459, score-0.315]
wordName wordTfidf (topN-words)
[('mwis', 0.79), ('segments', 0.291), ('segmentation', 0.196), ('bsd', 0.129), ('iqp', 0.129), ('meanshift', 0.113), ('ay', 0.11), ('image', 0.092), ('si', 0.078), ('segmentations', 0.077), ('aij', 0.076), ('tpami', 0.066), ('ncuts', 0.065), ('segmenters', 0.065), ('graph', 0.064), ('ensemble', 0.057), ('replicator', 0.057), ('argmaxx', 0.052), ('holes', 0.052), ('discrete', 0.05), ('hierarchy', 0.049), ('distinctiveness', 0.048), ('mwc', 0.048), ('nodes', 0.048), ('visits', 0.048), ('sj', 0.047), ('regions', 0.047), ('ax', 0.047), ('overlap', 0.046), ('meaningful', 0.046), ('tabu', 0.042), ('textures', 0.042), ('pb', 0.041), ('ri', 0.04), ('fowlkes', 0.039), ('benchmark', 0.039), ('graphs', 0.037), ('malik', 0.037), ('input', 0.036), ('wt', 0.035), ('clique', 0.034), ('distinct', 0.034), ('exhaustive', 0.034), ('rand', 0.033), ('ip', 0.033), ('continuous', 0.033), ('segment', 0.033), ('bs', 0.032), ('camel', 0.032), ('graduated', 0.032), ('ncut', 0.032), ('overlaps', 0.032), ('objects', 0.031), ('edges', 0.031), ('multiscale', 0.03), ('texture', 0.029), ('candidate', 0.029), ('wi', 0.029), ('boundaries', 0.029), ('converges', 0.029), ('qp', 0.029), ('seeks', 0.028), ('sinisa', 0.028), ('todorovic', 0.028), ('smin', 0.028), ('pelillo', 0.028), ('heaviest', 0.028), ('taylor', 0.028), ('iteration', 0.028), ('marked', 0.028), ('objective', 0.027), ('sh', 0.027), ('integer', 0.027), ('iccv', 0.027), ('domain', 0.026), ('complexity', 0.026), ('bf', 0.026), ('occupied', 0.026), ('surfaces', 0.026), ('solution', 0.026), ('berkeley', 0.025), ('images', 0.025), ('ahuja', 0.024), ('const', 0.024), ('relaxation', 0.024), ('xt', 0.023), ('quadratic', 0.023), ('solves', 0.023), ('formulates', 0.023), ('pixels', 0.022), ('presents', 0.022), ('star', 0.022), ('intersections', 0.022), ('avg', 0.022), ('hebert', 0.022), ('combinatorial', 0.022), ('search', 0.022), ('node', 0.021), ('iff', 0.021), ('occurrence', 0.021)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 234 nips-2010-Segmentation as Maximum-Weight Independent Set
Author: William Brendel, Sinisa Todorovic
Abstract: Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually “meaningful” segments in the ensemble. Knowledge about any specific objects and surfaces present in the image is not available. The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. MWIS is the heaviest subset of mutually non-adjacent nodes of an attributed graph. We construct such a graph from all segments in the ensemble. Then, MWIS selects maximally distinctive segments that together partition the image. A new MWIS algorithm is presented. The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. The algorithm is shown to converge to an optimum. Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results.
2 0.11524326 77 nips-2010-Epitome driven 3-D Diffusion Tensor image segmentation: on extracting specific structures
Author: Kamiya Motwani, Nagesh Adluru, Chris Hinrichs, Andrew Alexander, Vikas Singh
Abstract: We study the problem of segmenting specific white matter structures of interest from Diffusion Tensor (DT-MR) images of the human brain. This is an important requirement in many Neuroimaging studies: for instance, to evaluate whether a brain structure exhibits group level differences as a function of disease in a set of images. Typically, interactive expert guided segmentation has been the method of choice for such applications, but this is tedious for large datasets common today. To address this problem, we endow an image segmentation algorithm with “advice” encoding some global characteristics of the region(s) we want to extract. This is accomplished by constructing (using expert-segmented images) an epitome of a specific region – as a histogram over a bag of ‘words’ (e.g., suitable feature descriptors). Now, given such a representation, the problem reduces to segmenting a new brain image with additional constraints that enforce consistency between the segmented foreground and the pre-specified histogram over features. We present combinatorial approximation algorithms to incorporate such domain specific constraints for Markov Random Field (MRF) segmentation. Making use of recent results on image co-segmentation, we derive effective solution strategies for our problem. We provide an analysis of solution quality, and present promising experimental evidence showing that many structures of interest in Neuroscience can be extracted reliably from 3-D brain image volumes using our algorithm. 1
3 0.071476266 1 nips-2010-(RF)^2 -- Random Forest Random Field
Author: Nadia Payet, Sinisa Todorovic
Abstract: We combine random forest (RF) and conditional random field (CRF) into a new computational framework, called random forest random field (RF)2 . Inference of (RF)2 uses the Swendsen-Wang cut algorithm, characterized by MetropolisHastings jumps. A jump from one state to another depends on the ratio of the proposal distributions, and on the ratio of the posterior distributions of the two states. Prior work typically resorts to a parametric estimation of these four distributions, and then computes their ratio. Our key idea is to instead directly estimate these ratios using RF. RF collects in leaf nodes of each decision tree the class histograms of training examples. We use these class histograms for a nonparametric estimation of the distribution ratios. We derive the theoretical error bounds of a two-class (RF)2 . (RF)2 is applied to a challenging task of multiclass object recognition and segmentation over a random field of input image regions. In our empirical evaluation, we use only the visual information provided by image regions (e.g., color, texture, spatial layout), whereas the competing methods additionally use higher-level cues about the horizon location and 3D layout of surfaces in the scene. Nevertheless, (RF)2 outperforms the state of the art on benchmark datasets, in terms of accuracy and computation time.
4 0.066409811 149 nips-2010-Learning To Count Objects in Images
Author: Victor Lempitsky, Andrew Zisserman
Abstract: We propose a new supervised learning framework for visual object counting tasks, such as estimating the number of cells in a microscopic image or the number of humans in surveillance video frames. We focus on the practically-attractive case when the training images are annotated with dots (one dot per object). Our goal is to accurately estimate the count. However, we evade the hard task of learning to detect and localize individual object instances. Instead, we cast the problem as that of estimating an image density whose integral over any image region gives the count of objects within that region. Learning to infer such density can be formulated as a minimization of a regularized risk quadratic cost function. We introduce a new loss function, which is well-suited for such learning, and at the same time can be computed efficiently via a maximum subarray algorithm. The learning can then be posed as a convex quadratic program solvable with cutting-plane optimization. The proposed framework is very flexible as it can accept any domain-specific visual features. Once trained, our system provides accurate object counts and requires a very small time overhead over the feature extraction step, making it a good candidate for applications involving real-time processing or dealing with huge amount of visual data. 1
5 0.06157032 6 nips-2010-A Discriminative Latent Model of Image Region and Object Tag Correspondence
Author: Yang Wang, Greg Mori
Abstract: We propose a discriminative latent model for annotating images with unaligned object-level textual annotations. Instead of using the bag-of-words image representation currently popular in the computer vision community, our model explicitly captures more intricate relationships underlying visual and textual information. In particular, we model the mapping that translates image regions to annotations. This mapping allows us to relate image regions to their corresponding annotation terms. We also model the overall scene label as latent information. This allows us to cluster test images. Our training data consist of images and their associated annotations. But we do not have access to the ground-truth regionto-annotation mapping or the overall scene label. We develop a novel variant of the latent SVM framework to model them as latent variables. Our experimental results demonstrate the effectiveness of the proposed model compared with other baseline methods.
6 0.061366547 79 nips-2010-Estimating Spatial Layout of Rooms using Volumetric Reasoning about Objects and Surfaces
7 0.060083959 239 nips-2010-Sidestepping Intractable Inference with Structured Ensemble Cascades
8 0.056790713 171 nips-2010-Movement extraction by detecting dynamics switches and repetitions
9 0.054656353 264 nips-2010-Synergies in learning words and their referents
10 0.053597674 141 nips-2010-Layered image motion with explicit occlusions, temporal consistency, and depth ordering
11 0.053011864 255 nips-2010-Static Analysis of Binary Executables Using Structural SVMs
12 0.052245017 129 nips-2010-Inter-time segment information sharing for non-homogeneous dynamic Bayesian networks
13 0.050975565 230 nips-2010-Robust Clustering as Ensembles of Affinity Relations
14 0.050225314 165 nips-2010-MAP estimation in Binary MRFs via Bipartite Multi-cuts
15 0.046703141 162 nips-2010-Link Discovery using Graph Feature Tracking
16 0.046494089 117 nips-2010-Identifying graph-structured activation patterns in networks
17 0.046174206 241 nips-2010-Size Matters: Metric Visual Search Constraints from Monocular Metadata
18 0.045275547 186 nips-2010-Object Bank: A High-Level Image Representation for Scene Classification & Semantic Feature Sparsification
19 0.0450124 63 nips-2010-Distributed Dual Averaging In Networks
20 0.044862609 109 nips-2010-Group Sparse Coding with a Laplacian Scale Mixture Prior
topicId topicWeight
[(0, 0.138), (1, 0.047), (2, -0.045), (3, -0.04), (4, -0.045), (5, -0.079), (6, -0.027), (7, -0.001), (8, 0.052), (9, 0.049), (10, -0.042), (11, -0.025), (12, -0.035), (13, 0.042), (14, -0.029), (15, -0.024), (16, 0.016), (17, -0.077), (18, 0.014), (19, -0.005), (20, 0.032), (21, 0.057), (22, -0.022), (23, 0.057), (24, 0.031), (25, -0.054), (26, -0.01), (27, 0.002), (28, -0.052), (29, 0.024), (30, -0.003), (31, 0.094), (32, -0.016), (33, -0.069), (34, -0.113), (35, -0.067), (36, -0.014), (37, -0.062), (38, 0.087), (39, -0.036), (40, 0.025), (41, -0.01), (42, 0.026), (43, 0.032), (44, -0.077), (45, 0.001), (46, -0.005), (47, 0.004), (48, 0.058), (49, -0.037)]
simIndex simValue paperId paperTitle
same-paper 1 0.91677344 234 nips-2010-Segmentation as Maximum-Weight Independent Set
Author: William Brendel, Sinisa Todorovic
Abstract: Given an ensemble of distinct, low-level segmentations of an image, our goal is to identify visually “meaningful” segments in the ensemble. Knowledge about any specific objects and surfaces present in the image is not available. The selection of image regions occupied by objects is formalized as the maximum-weight independent set (MWIS) problem. MWIS is the heaviest subset of mutually non-adjacent nodes of an attributed graph. We construct such a graph from all segments in the ensemble. Then, MWIS selects maximally distinctive segments that together partition the image. A new MWIS algorithm is presented. The algorithm seeks a solution directly in the discrete domain, instead of relaxing MWIS to a continuous problem, as common in previous work. It iteratively finds a candidate discrete solution of the Taylor series expansion of the original MWIS objective function around the previous solution. The algorithm is shown to converge to an optimum. Our empirical evaluation on the benchmark Berkeley segmentation dataset shows that the new algorithm eliminates the need for hand-picking optimal input parameters of the state-of-the-art segmenters, and outperforms their best, manually optimized results.
2 0.79913652 77 nips-2010-Epitome driven 3-D Diffusion Tensor image segmentation: on extracting specific structures
Author: Kamiya Motwani, Nagesh Adluru, Chris Hinrichs, Andrew Alexander, Vikas Singh
Abstract: We study the problem of segmenting specific white matter structures of interest from Diffusion Tensor (DT-MR) images of the human brain. This is an important requirement in many Neuroimaging studies: for instance, to evaluate whether a brain structure exhibits group level differences as a function of disease in a set of images. Typically, interactive expert guided segmentation has been the method of choice for such applications, but this is tedious for large datasets common today. To address this problem, we endow an image segmentation algorithm with “advice” encoding some global characteristics of the region(s) we want to extract. This is accomplished by constructing (using expert-segmented images) an epitome of a specific region – as a histogram over a bag of ‘words’ (e.g., suitable feature descriptors). Now, given such a representation, the problem reduces to segmenting a new brain image with additional constraints that enforce consistency between the segmented foreground and the pre-specified histogram over features. We present combinatorial approximation algorithms to incorporate such domain specific constraints for Markov Random Field (MRF) segmentation. Making use of recent results on image co-segmentation, we derive effective solution strategies for our problem. We provide an analysis of solution quality, and present promising experimental evidence showing that many structures of interest in Neuroscience can be extracted reliably from 3-D brain image volumes using our algorithm. 1
3 0.70310748 256 nips-2010-Structural epitome: a way to summarize one’s visual experience
Author: Nebojsa Jojic, Alessandro Perina, Vittorio Murino
Abstract: In order to study the properties of total visual input in humans, a single subject wore a camera for two weeks capturing, on average, an image every 20 seconds. The resulting new dataset contains a mix of indoor and outdoor scenes as well as numerous foreground objects. Our first goal is to create a visual summary of the subject’s two weeks of life using unsupervised algorithms that would automatically discover recurrent scenes, familiar faces or common actions. Direct application of existing algorithms, such as panoramic stitching (e.g., Photosynth) or appearance-based clustering models (e.g., the epitome), is impractical due to either the large dataset size or the dramatic variations in the lighting conditions. As a remedy to these problems, we introduce a novel image representation, the ”structural element (stel) epitome,” and an associated efficient learning algorithm. In our model, each image or image patch is characterized by a hidden mapping T which, as in previous epitome models, defines a mapping between the image coordinates and the coordinates in the large ”all-I-have-seen” epitome matrix. The limited epitome real-estate forces the mappings of different images to overlap which indicates image similarity. However, the image similarity no longer depends on direct pixel-to-pixel intensity/color/feature comparisons as in previous epitome models, but on spatial configuration of scene or object parts, as the model is based on the palette-invariant stel models. As a result, stel epitomes capture structure that is invariant to non-structural changes, such as illumination changes, that tend to uniformly affect pixels belonging to a single scene or object part. 1
4 0.62103152 149 nips-2010-Learning To Count Objects in Images
Author: Victor Lempitsky, Andrew Zisserman
Abstract: We propose a new supervised learning framework for visual object counting tasks, such as estimating the number of cells in a microscopic image or the number of humans in surveillance video frames. We focus on the practically-attractive case when the training images are annotated with dots (one dot per object). Our goal is to accurately estimate the count. However, we evade the hard task of learning to detect and localize individual object instances. Instead, we cast the problem as that of estimating an image density whose integral over any image region gives the count of objects within that region. Learning to infer such density can be formulated as a minimization of a regularized risk quadratic cost function. We introduce a new loss function, which is well-suited for such learning, and at the same time can be computed efficiently via a maximum subarray algorithm. The learning can then be posed as a convex quadratic program solvable with cutting-plane optimization. The proposed framework is very flexible as it can accept any domain-specific visual features. Once trained, our system provides accurate object counts and requires a very small time overhead over the feature extraction step, making it a good candidate for applications involving real-time processing or dealing with huge amount of visual data. 1
5 0.57960933 245 nips-2010-Space-Variant Single-Image Blind Deconvolution for Removing Camera Shake
Author: Stefan Harmeling, Hirsch Michael, Bernhard Schölkopf
Abstract: Modelling camera shake as a space-invariant convolution simplifies the problem of removing camera shake, but often insufficiently models actual motion blur such as those due to camera rotation and movements outside the sensor plane or when objects in the scene have different distances to the camera. In an effort to address these limitations, (i) we introduce a taxonomy of camera shakes, (ii) we build on a recently introduced framework for space-variant filtering by Hirsch et al. and a fast algorithm for single image blind deconvolution for space-invariant filters by Cho and Lee to construct a method for blind deconvolution in the case of space-variant blur, and (iii), we present an experimental setup for evaluation that allows us to take images with real camera shake while at the same time recording the spacevariant point spread function corresponding to that blur. Finally, we demonstrate that our method is able to deblur images degraded by spatially-varying blur originating from real camera shake, even without using additionally motion sensor information. 1
6 0.54094124 1 nips-2010-(RF)^2 -- Random Forest Random Field
7 0.50964665 255 nips-2010-Static Analysis of Binary Executables Using Structural SVMs
8 0.46389878 105 nips-2010-Getting lost in space: Large sample analysis of the resistance distance
9 0.4543646 288 nips-2010-Worst-case bounds on the quality of max-product fixed-points
10 0.44819316 204 nips-2010-Penalized Principal Component Regression on Graphs for Analysis of Subnetworks
11 0.44165176 103 nips-2010-Generating more realistic images using gated MRF's
12 0.44059688 241 nips-2010-Size Matters: Metric Visual Search Constraints from Monocular Metadata
13 0.44027433 181 nips-2010-Network Flow Algorithms for Structured Sparsity
14 0.43224159 3 nips-2010-A Bayesian Framework for Figure-Ground Interpretation
15 0.43075117 266 nips-2010-The Maximal Causes of Natural Scenes are Edge Filters
16 0.42645815 224 nips-2010-Regularized estimation of image statistics by Score Matching
17 0.41595227 6 nips-2010-A Discriminative Latent Model of Image Region and Object Tag Correspondence
18 0.41459462 259 nips-2010-Subgraph Detection Using Eigenvector L1 Norms
19 0.41443223 165 nips-2010-MAP estimation in Binary MRFs via Bipartite Multi-cuts
20 0.41027087 79 nips-2010-Estimating Spatial Layout of Rooms using Volumetric Reasoning about Objects and Surfaces
topicId topicWeight
[(13, 0.033), (17, 0.011), (27, 0.047), (30, 0.054), (35, 0.019), (45, 0.208), (50, 0.055), (52, 0.025), (60, 0.035), (77, 0.396), (78, 0.012), (90, 0.02)]
simIndex simValue paperId paperTitle
1 0.98890591 34 nips-2010-Attractor Dynamics with Synaptic Depression
Author: K. Wong, He Wang, Si Wu, Chi Fung
Abstract: Neuronal connection weights exhibit short-term depression (STD). The present study investigates the impact of STD on the dynamics of a continuous attractor neural network (CANN) and its potential roles in neural information processing. We find that the network with STD can generate both static and traveling bumps, and STD enhances the performance of the network in tracking external inputs. In particular, we find that STD endows the network with slow-decaying plateau behaviors, namely, the network being initially stimulated to an active state will decay to silence very slowly in the time scale of STD rather than that of neural signaling. We argue that this provides a mechanism for neural systems to hold short-term memory easily and shut off persistent activities naturally.
2 0.98274374 16 nips-2010-A VLSI Implementation of the Adaptive Exponential Integrate-and-Fire Neuron Model
Author: Sebastian Millner, Andreas Grübl, Karlheinz Meier, Johannes Schemmel, Marc-olivier Schwartz
Abstract: We describe an accelerated hardware neuron being capable of emulating the adaptive exponential integrate-and-fire neuron model. Firing patterns of the membrane stimulated by a step current are analyzed in transistor level simulations and in silicon on a prototype chip. The neuron is destined to be the hardware neuron of a highly integrated wafer-scale system reaching out for new computational paradigms and opening new experimentation possibilities. As the neuron is dedicated as a universal device for neuroscientific experiments, the focus lays on parameterizability and reproduction of the analytical model. 1
3 0.94693899 230 nips-2010-Robust Clustering as Ensembles of Affinity Relations
Author: Hairong Liu, Longin J. Latecki, Shuicheng Yan
Abstract: In this paper, we regard clustering as ensembles of k-ary affinity relations and clusters correspond to subsets of objects with maximal average affinity relations. The average affinity relation of a cluster is relaxed and well approximated by a constrained homogenous function. We present an efficient procedure to solve this optimization problem, and show that the underlying clusters can be robustly revealed by using priors systematically constructed from the data. Our method can automatically select some points to form clusters, leaving other points un-grouped; thus it is inherently robust to large numbers of outliers, which has seriously limited the applicability of classical methods. Our method also provides a unified solution to clustering from k-ary affinity relations with k ≥ 2, that is, it applies to both graph-based and hypergraph-based clustering problems. Both theoretical analysis and experimental results show the superiority of our method over classical solutions to the clustering problem, especially when there exists a large number of outliers.
4 0.93400794 15 nips-2010-A Theory of Multiclass Boosting
Author: Indraneel Mukherjee, Robert E. Schapire
Abstract: Boosting combines weak classifiers to form highly accurate predictors. Although the case of binary classification is well understood, in the multiclass setting, the “correct” requirements on the weak classifier, or the notion of the most efficient boosting algorithms are missing. In this paper, we create a broad and general framework, within which we make precise and identify the optimal requirements on the weak-classifier, as well as design the most effective, in a certain sense, boosting algorithms that assume such requirements. 1
5 0.89187419 142 nips-2010-Learning Bounds for Importance Weighting
Author: Corinna Cortes, Yishay Mansour, Mehryar Mohri
Abstract: This paper presents an analysis of importance weighting for learning from finite samples and gives a series of theoretical and algorithmic results. We point out simple cases where importance weighting can fail, which suggests the need for an analysis of the properties of this technique. We then give both upper and lower bounds for generalization with bounded importance weights and, more significantly, give learning guarantees for the more common case of unbounded importance weights under the weak assumption that the second moment is bounded, a condition related to the R´ nyi divergence of the training and test distributions. e These results are based on a series of novel and general bounds we derive for unbounded loss functions, which are of independent interest. We use these bounds to guide the definition of an alternative reweighting algorithm and report the results of experiments demonstrating its benefits. Finally, we analyze the properties of normalized importance weights which are also commonly used.
same-paper 6 0.85440069 234 nips-2010-Segmentation as Maximum-Weight Independent Set
7 0.78921694 68 nips-2010-Effects of Synaptic Weight Diffusion on Learning in Decision Making Networks
8 0.75344861 10 nips-2010-A Novel Kernel for Learning a Neuron Model from Spike Train Data
10 0.71559411 253 nips-2010-Spike timing-dependent plasticity as dynamic filter
11 0.71551841 200 nips-2010-Over-complete representations on recurrent neural networks can support persistent percepts
12 0.70355517 238 nips-2010-Short-term memory in neuronal networks through dynamical compressed sensing
13 0.70006317 8 nips-2010-A Log-Domain Implementation of the Diffusion Network in Very Large Scale Integration
14 0.69641894 244 nips-2010-Sodium entry efficiency during action potentials: A novel single-parameter family of Hodgkin-Huxley models
15 0.67323476 117 nips-2010-Identifying graph-structured activation patterns in networks
16 0.66646111 127 nips-2010-Inferring Stimulus Selectivity from the Spatial Structure of Neural Network Dynamics
17 0.66192323 31 nips-2010-An analysis on negative curvature induced by singularity in multi-layer neural-network learning
18 0.65850091 30 nips-2010-An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA
19 0.65370536 96 nips-2010-Fractionally Predictive Spiking Neurons
20 0.65293229 182 nips-2010-New Adaptive Algorithms for Online Classification