nips nips2011 nips2011-119 knowledge-graph by maker-knowledge-mining

119 nips-2011-Higher-Order Correlation Clustering for Image Segmentation

Source: pdf

Author: Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo

Abstract: For many of the state-of-the-art computer vision algorithms, image segmentation is an important preprocessing step. As such, several image segmentation algorithms have been proposed, however, with certain reservation due to high computational load and many hand-tuning parameters. Correlation clustering, a graphpartitioning algorithm often used in natural language processing and document clustering, has the potential to perform better than previously proposed image segmentation algorithms. We improve the basic correlation clustering formulation by taking into account higher-order cluster relationships. This improves clustering in the presence of local boundary ambiguities. We ﬁrst apply the pairwise correlation clustering to image segmentation over a pairwise superpixel graph and then develop higher-order correlation clustering over a hypergraph that considers higher-order relations among superpixels. Fast inference is possible by linear programming relaxation, and also effective parameter learning framework by structured support vector machine is possible. Experimental results on various datasets show that the proposed higher-order correlation clustering outperforms other state-of-the-art image segmentation algorithms.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 kr Abstract For many of the state-of-the-art computer vision algorithms, image segmentation is an important preprocessing step. [sent-10, score-0.503]

2 As such, several image segmentation algorithms have been proposed, however, with certain reservation due to high computational load and many hand-tuning parameters. [sent-11, score-0.503]

3 Correlation clustering, a graphpartitioning algorithm often used in natural language processing and document clustering, has the potential to perform better than previously proposed image segmentation algorithms. [sent-12, score-0.534]

4 We improve the basic correlation clustering formulation by taking into account higher-order cluster relationships. [sent-13, score-0.459]

5 This improves clustering in the presence of local boundary ambiguities. [sent-14, score-0.26]

6 We ﬁrst apply the pairwise correlation clustering to image segmentation over a pairwise superpixel graph and then develop higher-order correlation clustering over a hypergraph that considers higher-order relations among superpixels. [sent-15, score-2.435]

7 Experimental results on various datasets show that the proposed higher-order correlation clustering outperforms other state-of-the-art image segmentation algorithms. [sent-17, score-0.993]

8 1 Introduction Image segmentation, a partitioning of an image into disjoint regions such that each region is homogeneous, is an important preprocessing step for many of the state-of-the-art algorithms for high-level image/scene understanding for three reasons. [sent-18, score-0.371]

9 Image segmentation algorithms can be categorized into either non-graph-based or graph-based algorithms. [sent-22, score-0.358]

10 In comparison to non-graph-based segmentations, graph-based segmentations have been shown to produce consistent segmentations by adaptively balancing local 1 judgements of similarity [7]. [sent-24, score-0.234]

11 However, in contrast to the min-cuts and normalized cuts which are node-labeling algorithms, the FH algorithm beneﬁts from the edge-labeling in that it leads to faster inference and does not require a pre-speciﬁed number of segmentations in each image [7]. [sent-26, score-0.345]

12 Correlation clustering is a graph-partitioning algorithm [8] that simultaneously maximizes intracluster similarity and inter-cluster dissimilarity by solving the global objective (discriminant) function. [sent-27, score-0.226]

13 In comparison with the previous image segmentation algorithms, correlation clustering is a graph-based, global-objective, and edge-labeling algorithm and therefore, has the potential to perform better for image segmentation. [sent-28, score-1.107]

14 Furthermore, correlation clustering leads to the linear discriminant function which allows for approximate polynomial-time inference by linear programming (LP) and large margin training based on structured support vector machine (S-SVM) [9]. [sent-29, score-0.706]

15 A framework that uses S-SVM for training the parameters in correlation clustering has been considered previously by Finley et al. [sent-30, score-0.499]

16 Taskar derived a max-margin formulation for learning the edge scores for correlation clustering [11]. [sent-32, score-0.57]

17 Even though the previous (pairwise) correlation clustering can consider global aspects of an image using the discriminatively-trained discriminant function, it is restricted in resolving the segment boundary ambiguities caused by neighboring pairwise relations presented by the pairwise graph. [sent-35, score-1.291]

18 Therefore, to capture long-range dependencies of distant nodes in a global context, this paper proposes a novel higher-order correlation clustering to incorporate higher-order relations. [sent-36, score-0.499]

19 We ﬁrst apply the pairwise correlation clustering to image segmentation over a pairwise superpixel graph and then develop higher-order correlation clustering over a hypergraph that considers higher-order relations among superpixels. [sent-37, score-2.435]

20 The proposed higher-order correlation clustering is deﬁned over a hypergraph in which an edge can connect to two or more nodes [12]. [sent-38, score-0.937]

21 Hypergraphs have been previously used to lift certain limitations of conventional pairwise graphs [13, 14, 15]. [sent-39, score-0.214]

22 However, previously proposed hypergraphs for image segmentation are restricted to partitioning based on the generalization of normalized cut framework, which suffer from a number of problems. [sent-40, score-0.635]

23 A number of algorithms to approximate the inference process have been introduced based on the coarsening algorithm [14] and the hypergraph Laplacian matrices [13]; these are heuristic approaches and therefore are sub-optimal. [sent-42, score-0.335]

24 Second, incorporating a supervised learning algorithm for parameter estimation under the spectral hypergraph partitioning framework is difﬁcult. [sent-43, score-0.41]

25 Almost all previous hypergraph-based image segmentation algorithms are restricted to use only color variances as region features. [sent-47, score-0.576]

26 The proposed higher-order correlation clustering overcomes all of these problems due to the generalization of the pairwise correlation clustering and enables to take advantages of using a hypergraph. [sent-48, score-1.163]

27 The proposed higher-order correlation clustering algorithm uses as its input a hypergraph and leads to a linear discriminant function. [sent-49, score-0.882]

28 For fast inference, the LP relaxation is used to approximately solve the higher-order correlation clustering problem, and for supervised training of the parameter vector by S-SVM, we apply a decomposable structured loss function to handle unbalanced classes. [sent-51, score-0.656]

29 Experimental results on various datasets show that the proposed higher-order correlation clustering outperforms other state-of-the-art image segmentation algorithms. [sent-53, score-0.993]

30 Section 2 presents the higher-order correlation clustering for image segmentation. [sent-55, score-0.604]

31 Section 3 describes large margin training for supervised image segmentation based on the S-SVM and the cutting plane algorithm. [sent-56, score-0.727]

32 2 i k yik k yijk j yij y jk j (a) yj k (b) Figure 1: Illustrations of a part of (a) the pairwise graph (b) and the triplet graph built on superpixels. [sent-58, score-0.439]

33 The proposed correlation clustering merges superpixels into disjoint homogeneous regions over a superpixel graph. [sent-60, score-1.105]

34 1 Pairwise correlation clustering over pairwise superpixel graph Deﬁne a pairwise undirected graph G = (V, E) where a node corresponds to a superpixel and a link between adjacent superpixels corresponds to an edge (see Figure 1. [sent-62, score-1.757]

35 A binary label yjk for an edge (j, k) ∈ E between nodes j and k is deﬁned such that { 1, if nodes j and k belong to the same region, yjk = (1) 0, otherwise. [sent-64, score-0.406]

36 Note that the discriminant function F (x, y; w) is assumed to be linear in both the parameter vector w and the joint feature map Φ(x, y), and ϕjk (x) is a pairwise feature vector which reﬂects the correspondence between the jth and the kth ˆ superpixels. [sent-66, score-0.386]

37 An image segmentation is to infer the edge label, y, over the pairwise superpixel graph G by maximizing F such that ˆ y = argmax F (x, y; w) (3) y∈Y E where Y is the set of {0, 1} that corresponds to a valid segmentation, the so called multicut polytope. [sent-67, score-1.086]

38 When producing the segmentation results based on the approximated LP solutions, we take the ﬂoor of a fractionally-predicted label of each edge independently for simply obtaining valid integer solutions that may be sub-optimal. [sent-70, score-0.506]

39 Therefore, to incorporate higher-order relations, we develop higher-order correlation clustering by generalizing the correlation clustering over a hypergraph. [sent-72, score-0.918]

40 2 Higher-order correlation clustering over hypergraph The proposed higher-order correlation clustering is deﬁned over a hypergraph in which an edge called hyperedge can connect to two or more nodes. [sent-74, score-1.83]

41 (b), one 3 (a) (b) (c) (d) Figure 2: Example of segmentation result by pairwise correlation clustering. [sent-76, score-0.805]

42 can introduce binary labels for each adjacent vertices forming a triplet such that yijk = 1 if all vertices in the triplet ({i, j, k}) are in the same cluster; otherwise, yijk = 0. [sent-81, score-0.245]

43 Deﬁne a hypergraph HG ∪ (V, E) where V is a set of nodes (superpixels) and E is a set of hyperedges (subsets of V) such = that e∈E = V. [sent-82, score-0.443]

44 Therefore, the hyperedge set E can be divided into two disjoint subsets: pairwise edge set Ep = {e ∈ E | |e| = 2} and higher∪ order edge set Eh = {e ∈ E | |e| > 2} such that Ep Eh = E. [sent-86, score-0.647]

45 Note that in the proposed hypergraph for higher-order correlation clustering all hyperedges containing just two nodes (∀ep ∈ Ep ) are linked between adjacent superpixels. [sent-87, score-0.97]

46 The pairwise superpixel graph is a special hypergraph where all hyperedges contain just two (neighboring) superpixels: Ep = E. [sent-88, score-0.844]

47 A binary label ye for a hyperedge e ∈ E is deﬁned such that { 1, if all nodes in e belong to the same region, (4) ye = 0, otherwise. [sent-89, score-0.361]

48 Note that the proposed discriminant function for higher-order correlation clustering is decomposed into two terms by assigning different parameter vectors to the pairwise edge set Ep and T T the higher-order edge set Eh such that w = [wp , wh ]T . [sent-91, score-1.062]

49 Thus, in addition to the pairwise similarity between neighboring superpixels, the proposed higher-order correlation clustering considers a broad homogeneous region reﬂecting higher-order relations among superpixels. [sent-92, score-0.936]

50 Now the problem is how to build our hypergraph from a given image. [sent-93, score-0.296]

51 We obtain unsupervised multiple partitionings by merging not pixels but superpixels with different image quantizations using the ultrametric contour maps [19]. [sent-95, score-0.528]

52 These higher-order inequalities can be formulated as yeh ≤ yep , ∀ep ∈ Ep |ep ⊂ eh , ∑ (1 − yeh ) ≤ (1 − yep ). [sent-107, score-0.862]

53 (7) ep ∈Ep |ep ⊂eh Indeed, the LP relaxation to approximately solve (6) is formulated as ∑ ∑ argmax ⟨wp , ϕep (x)⟩yep + ⟨wh , ϕeh (x)⟩yeh y s. [sent-108, score-0.258]

54 ep ∈Ep ∀ e ∈ E(= Ep ∪ (8) eh ∈Eh Eh ), ye ∈ [0, 1], ∀ ep ∈ Ep , cycle inequalities, odd-wheel inequalities [18], ∀ eh ∈ Eh , higher-order inequalities (7). [sent-110, score-1.143]

55 Note that the proposed higher-order correlation clustering follows the concept of soft constraints: superpixels within a hyperedge are encouraged to merge if a hyperedge is highly homogeneous. [sent-111, score-1.114]

56 The pairwise feature vector ϕep (x) reﬂects the correspondence between neighboring superpixels, and the higher-order feature vector ϕeh (x) characterizes a more complex relations among superpixels in a broader region to measure homogeneity. [sent-115, score-0.733]

57 5 • Texture difference ϕt : The 64 texture distances (absolute differences, χ2 -distances, earth mover’s distances) between two adjacent superpixels using 15 Leung-Malik (LM) ﬁlter banks [19]. [sent-121, score-0.335]

58 • Joint visual word posterior ϕv : The 100-dimensional vector holding the joint visual word posteriors for a pair of neighboring superpixels using 10 visual words and the 400-dimensional vector holding the joint posteriors based on 20 visual words [21]. [sent-124, score-0.415]

59 eh e eh • Variance ϕva : The 14 color variances and 30 texture variances among superpixels in a hyperedge. [sent-127, score-0.86]

60 The 100-dimensional template matching feature vector is composed of the matching scores between a region deﬁned by a hyperedge and templates using the Gaussian RBF kernel. [sent-130, score-0.289]

61 3 Structural learning The proposed discriminant function is deﬁned over the superpixel graph, and therefore, the groundtruth segmentation needs to be transformed to the ground-truth edge labels in the superpixel graph. [sent-132, score-0.98]

62 For this, we ﬁrst assign a single dominant segment label to each superpixel by majority voting over the superpixel’s constituent pixels and then obtain the ground-truth edge labels. [sent-133, score-0.324]

63 Given N training samples {xn , yn }N where yn is the ground-truth edge labels n=1 for the nth training image, the S-SVM [9] optimizes w by minimizing a quadratic objective function subject to a set of linear margin constraints: min w,ξ s. [sent-135, score-0.379]

64 The cutting plane algorithm [9, 18] with LP relaxation for loss-augmented inference is used to solve the optimization problem of S-SVM, since fast convergence and high robustness of the cutting plane algorithm in handling a large number of margin constraints are well-known [22, 23]. [sent-140, score-0.342]

65 A loss function is usually a non-negative function, and a loss function that is decomposable is preferred, since it enables the loss-augmented inference in the cutting plane algorithm to be performed efﬁciently. [sent-141, score-0.233]

66 The most popular loss function that is decomposable is the Hamming distance which is equivalent to the number of mismatches between yn and y at the edge level in this correlation clustering. [sent-142, score-0.457]

67 Unfortunately, in the proposed correlation clustering for image segmentation, the number of edges which are labeled as 1 is considerably higher than that of edges which are labeled as 0. [sent-143, score-0.693]

68 This unbalance makes other learning methods such as the perceptron algorithm inappropriate, since it leads to the clustering of the whole image as one segment. [sent-144, score-0.407]

69 3 gPb- oiem H 20 25 30 35 Average number of regions 40 Corr - luster - airwise C P 20 25 30 35 Average number of regions 40 Corr - luster - igher C H Figure 4: Obtained evaluation measures from segmentation results on the SBD. [sent-155, score-0.698]

70 Therefore, we use the following loss function: ) ) ∑( ∑( n n n n ∆(yn , y)= Rp yep +yep − (Rp + 1)yep yep +D Rh yeh +yeh − (Rh + 1)yeh yeh (10) ep ∈Ep eh ∈Eh where D is the relative weight of the loss at higher-order edge level to that of the loss at pairwise edge level. [sent-157, score-1.567]

71 In addition, Rp and Rh control the relative importance between the incorrect merging of the superpixels and the incorrect separation of the superpixels by imposing different weights to the false negative and the false positive. [sent-158, score-0.536]

72 4 Experiments To evaluate segmentations obtained by various algorithms against the ground-truth segmentation, we conducted image segmentations on three benchmark datasets: Stanford background dataset [24] (SBD), Berkeley segmentation dataset (BSDS) [25], MSRC dataset [26]. [sent-160, score-0.737]

73 For image segmentation based on correlation clustering, we initially obtain baseline superpixels (438 superpixels per image on average) by the gPb contour detector and the oriented watershed transform [19] and then construct a hypergraph. [sent-161, score-1.448]

74 Note that the relaxed solutions in loss-augmented inference are used during training, while in testing, our simple rounding method is used to produce valid segmentation results. [sent-163, score-0.397]

75 Rounding is only necessary in case we obtain fractional solutions from LP-relaxed correlation clustering. [sent-164, score-0.233]

76 We compared the proposed pairwise/higher-order correlation clustering to the following state-of-theart image segmentation algorithms: multiscale NCut [27], gPb-owt-ucm [19], and gPb-Hoiem [20] that grouped the same superpixels based on pairwise same-label likelihoods. [sent-165, score-1.504]

77 The pairwise samelabel likelihoods were independently learnt from the training data with the same 611-dimensional pairwise feature vector. [sent-166, score-0.506]

78 We consider four performance measures: probabilistic Rand index (PRI) [28], variation of information (VOI) [29], segmentation covering (SCO) [19], and boundary displacement error (BDE) [30]. [sent-167, score-0.392]

79 As the predicted segmentation is close to the ground-truth segmentation, the PRI and SCO are increased while the VOI and BDE are decreased. [sent-168, score-0.358]

80 Figure 4 shows the obtained four measures from segmentation results according to the average number of regions. [sent-172, score-0.358]

81 Irrespective of the measure, the proposed higher-order correlation clustering (Corr-Cluster-Higher) performed better than other algorithms including the pairwise correlation clustering (Corr-Cluster-Pairwise). [sent-179, score-1.163]

82 The proposed higher-order correlation clustering yielded the best segmentation results. [sent-181, score-0.848]

83 Regarding the runtime of our algorithm, we observed that for test-time inference it took on average around 15 seconds (graph construction and feature extraction: 14s, LP: 1s) per image on a 2. [sent-225, score-0.222]

84 Note that other segmentation algorithms such as the multiscale NCut and the gPb-owt-ucm took on average a few minutes per image. [sent-227, score-0.387]

85 2 Berkeley segmentation dataset and MSRC dataset The BSDS contains 300 natural images split into the 200 training images and 100 test images. [sent-229, score-0.398]

86 Since each image is segmented by multiple human subjects, we deﬁned a single probabilistic (real-valued) ground-truth segmentation of each image for training in the proposed correlation clustering. [sent-230, score-0.952]

87 On average, all segmentation algorithms were set to produce 30 disjoint regions per image on the BSDS and 15 disjoint regions per image on the MSRC dataset. [sent-234, score-0.876]

88 As shown in Table 1, the proposed higher-order correlation clustering gave the best results on both datasets. [sent-235, score-0.49]

89 5 Conclusion This paper proposed the higher-order correlation clustering over a hypergraph to merge superpixels into homogeneous regions. [sent-237, score-1.111]

90 The LP relaxation was used to approximately solve the higher-order correlation clustering over a hypergraph where a rich feature vector was deﬁned based on several visual cues involving higher-order relations among superpixels. [sent-238, score-0.953]

91 The S-SVM was used for supervised training of parameters in correlation clustering, and the cutting plane algorithm with LP-relaxed inference was applied to solve the optimization problem of S-SVM. [sent-239, score-0.452]

92 Experimental results showed that the proposed higher-order correlation clustering outperformed other image segmentation algorithms on various datasets. [sent-240, score-0.993]

93 Wu, “An efﬁcient k-means clustering algorithm: Analysis and implementation,” PAMI, vol. [sent-250, score-0.226]

94 Malik, “Blobworld: image segmentation using expectationmaximization and its application to image querying,” PAMI, vol. [sent-262, score-0.648]

95 Joachims, “Supervised clustering with support vector machines,” in ICML, 2005. [sent-295, score-0.226]

96 Yilmaz, “Image segmentation as learning on hypergraphs,” in Proc. [sent-304, score-0.358]

97 Laget, “A multilevel spectral hypergraph partitioning approach for color image segmentation,” in Proc. [sent-314, score-0.524]

98 Shi, “Spectral segmentation with multiscale graph decomposition,” in CVPR, 2005. [sent-368, score-0.438]

99 Rand, “Objective criteria for the evaluation of clustering methods,” Journal of the American Statistical Association, vol. [sent-371, score-0.226]

100 Lee, “Learning full pairwise afﬁnities for spectral segmentation,” in CVPR, 2010. [sent-389, score-0.258]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('segmentation', 0.358), ('hypergraph', 0.296), ('eh', 0.296), ('superpixels', 0.268), ('correlation', 0.233), ('clustering', 0.226), ('ep', 0.217), ('pairwise', 0.214), ('hyperedge', 0.178), ('superpixel', 0.176), ('image', 0.145), ('yep', 0.142), ('yeh', 0.125), ('bsds', 0.124), ('segmentations', 0.117), ('edge', 0.111), ('hyperedges', 0.107), ('discriminant', 0.096), ('msrc', 0.094), ('bde', 0.089), ('sco', 0.089), ('yjk', 0.089), ('regions', 0.081), ('voi', 0.078), ('pri', 0.078), ('region', 0.073), ('luster', 0.071), ('lp', 0.068), ('relations', 0.063), ('hypergraphs', 0.062), ('cutting', 0.062), ('korea', 0.057), ('homogeneous', 0.057), ('rh', 0.057), ('yn', 0.056), ('partitionings', 0.053), ('yijk', 0.053), ('ye', 0.053), ('graph', 0.051), ('layer', 0.051), ('malik', 0.051), ('plane', 0.047), ('spectral', 0.044), ('cuts', 0.044), ('margin', 0.044), ('relaxation', 0.041), ('nodes', 0.04), ('wh', 0.04), ('training', 0.04), ('partitioning', 0.039), ('inference', 0.039), ('neighboring', 0.039), ('fh', 0.038), ('feature', 0.038), ('pami', 0.038), ('label', 0.037), ('adjacent', 0.037), ('wp', 0.037), ('finley', 0.037), ('estrada', 0.036), ('homw', 0.036), ('jepson', 0.036), ('kaist', 0.036), ('ncut', 0.036), ('oiem', 0.036), ('rital', 0.036), ('sbd', 0.036), ('simw', 0.036), ('unbalance', 0.036), ('triplet', 0.035), ('jk', 0.035), ('rp', 0.034), ('boundary', 0.034), ('disjoint', 0.033), ('labels', 0.032), ('inequalities', 0.032), ('shi', 0.032), ('multicut', 0.031), ('daejeon', 0.031), ('mover', 0.031), ('quantizations', 0.031), ('contour', 0.031), ('proposed', 0.031), ('supervised', 0.031), ('distances', 0.03), ('coherent', 0.029), ('multiscale', 0.029), ('edges', 0.029), ('layers', 0.029), ('decomposable', 0.029), ('cues', 0.029), ('segments', 0.029), ('structured', 0.028), ('taskar', 0.028), ('yellow', 0.028), ('loss', 0.028), ('cour', 0.027), ('ambiguities', 0.027), ('visual', 0.027), ('joachims', 0.026)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000004 119 nips-2011-Higher-Order Correlation Clustering for Image Segmentation

Author: Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo

2 0.23132057 227 nips-2011-Pylon Model for Semantic Segmentation

Author: Victor Lempitsky, Andrea Vedaldi, Andrew Zisserman

Abstract: Graph cut optimization is one of the standard workhorses of image segmentation since for binary random ﬁeld representations of the image, it gives globally optimal results and there are efﬁcient polynomial time implementations. Often, the random ﬁeld is applied over a ﬂat partitioning of the image into non-intersecting elements, such as pixels or super-pixels. In the paper we show that if, instead of a ﬂat partitioning, the image is represented by a hierarchical segmentation tree, then the resulting energy combining unary and boundary terms can still be optimized using graph cut (with all the corresponding beneﬁts of global optimality and efﬁciency). As a result of such inference, the image gets partitioned into a set of segments that may come from different layers of the tree. We apply this formulation, which we call the pylon model, to the task of semantic segmentation where the goal is to separate an image into areas belonging to different semantic classes. The experiments highlight the advantage of inference on a segmentation tree (over a ﬂat partitioning) and demonstrate that the optimization in the pylon model is able to ﬂexibly choose the level of segmentation across the image. Overall, the proposed system has superior segmentation accuracy on several datasets (Graz-02, Stanford background) compared to previously suggested approaches. 1

3 0.17791952 155 nips-2011-Learning to Agglomerate Superpixel Hierarchies

Author: Viren Jain, Srinivas C. Turaga, K Briggman, Moritz N. Helmstaedter, Winfried Denk, H. S. Seung

Abstract: An agglomerative clustering algorithm merges the most similar pair of clusters at every iteration. The function that evaluates similarity is traditionally handdesigned, but there has been recent interest in supervised or semisupervised settings in which ground-truth clustered data is available for training. Here we show how to train a similarity function by regarding it as the action-value function of a reinforcement learning problem. We apply this general method to segment images by clustering superpixels, an application that we call Learning to Agglomerate Superpixel Hierarchies (LASH). When applied to a challenging dataset of brain images from serial electron microscopy, LASH dramatically improved segmentation accuracy when clustering supervoxels generated by state of the boundary detection algorithms. The naive strategy of directly training only supervoxel similarities and applying single linkage clustering produced less improvement. 1

4 0.17784233 223 nips-2011-Probabilistic Joint Image Segmentation and Labeling

Author: Adrian Ion, Joao Carreira, Cristian Sminchisescu

Abstract: We present a joint image segmentation and labeling model (JSL) which, given a bag of ﬁgure-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 ﬁrst 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 conﬁgurations that a not-yet-competent model rates probable during learning. We show that the proposed methodology matches 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.

5 0.16682515 76 nips-2011-Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials

Author: Philipp Krähenbühl, Vladlen Koltun

Abstract: Most state-of-the-art techniques for multi-class image segmentation and labeling use conditional random ﬁelds deﬁned over pixels or image regions. While regionlevel models often feature dense pairwise connectivity, pixel-level models are considerably larger and have only permitted sparse graph structures. In this paper, we consider fully connected CRF models deﬁned on the complete set of pixels in an image. The resulting graphs have billions of edges, making traditional inference algorithms impractical. Our main contribution is a highly efﬁcient approximate inference algorithm for fully connected CRF models in which the pairwise edge potentials are deﬁned by a linear combination of Gaussian kernels. Our experiments demonstrate that dense connectivity at the pixel level substantially improves segmentation and labeling accuracy. 1

6 0.16443048 266 nips-2011-Spatial distance dependent Chinese restaurant processes for image segmentation

7 0.15320548 54 nips-2011-Co-regularized Multi-view Spectral Clustering

8 0.11716174 186 nips-2011-Noise Thresholds for Spectral Clustering

9 0.10379728 198 nips-2011-On U-processes and clustering performance

10 0.097031206 247 nips-2011-Semantic Labeling of 3D Point Clouds for Indoor Scenes

11 0.093392506 180 nips-2011-Multiple Instance Filtering

12 0.08291664 1 nips-2011-$\theta$-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding

13 0.082576118 22 nips-2011-Active Ranking using Pairwise Comparisons

14 0.080973074 244 nips-2011-Selecting Receptive Fields in Deep Networks

15 0.076099277 70 nips-2011-Dimensionality Reduction Using the Sparse Linear Model

16 0.072585493 127 nips-2011-Image Parsing with Stochastic Scene Grammar

17 0.070326328 165 nips-2011-Matrix Completion for Multi-label Image Classification

18 0.068423122 114 nips-2011-Hierarchical Multitask Structured Output Learning for Large-scale Sequence Segmentation

19 0.065106042 96 nips-2011-Fast and Balanced: Efficient Label Tree Learning for Large Scale Object Recognition

20 0.062414337 141 nips-2011-Large-Scale Category Structure Aware Image Categorization

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.185), (1, 0.119), (2, -0.13), (3, 0.12), (4, 0.047), (5, 0.004), (6, -0.124), (7, -0.004), (8, 0.12), (9, -0.008), (10, 0.083), (11, 0.162), (12, 0.156), (13, -0.246), (14, -0.164), (15, 0.012), (16, 0.047), (17, -0.145), (18, 0.007), (19, -0.066), (20, -0.084), (21, -0.038), (22, -0.001), (23, -0.029), (24, -0.055), (25, -0.013), (26, -0.007), (27, -0.09), (28, -0.006), (29, -0.058), (30, 0.026), (31, -0.16), (32, 0.011), (33, -0.035), (34, -0.023), (35, 0.035), (36, 0.078), (37, 0.006), (38, 0.071), (39, -0.005), (40, 0.012), (41, 0.018), (42, 0.074), (43, -0.014), (44, -0.063), (45, -0.064), (46, 0.047), (47, -0.0), (48, -0.025), (49, 0.025)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.96980047 119 nips-2011-Higher-Order Correlation Clustering for Image Segmentation

Author: Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo

2 0.80254662 227 nips-2011-Pylon Model for Semantic Segmentation

Author: Victor Lempitsky, Andrea Vedaldi, Andrew Zisserman

3 0.76286799 223 nips-2011-Probabilistic Joint Image Segmentation and Labeling

Author: Adrian Ion, Joao Carreira, Cristian Sminchisescu

4 0.76142675 76 nips-2011-Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials

Author: Philipp Krähenbühl, Vladlen Koltun

5 0.76132047 155 nips-2011-Learning to Agglomerate Superpixel Hierarchies

Author: Viren Jain, Srinivas C. Turaga, K Briggman, Moritz N. Helmstaedter, Winfried Denk, H. S. Seung

6 0.70688611 266 nips-2011-Spatial distance dependent Chinese restaurant processes for image segmentation

7 0.50429726 54 nips-2011-Co-regularized Multi-view Spectral Clustering

8 0.48438367 247 nips-2011-Semantic Labeling of 3D Point Clouds for Indoor Scenes

9 0.47388849 235 nips-2011-Recovering Intrinsic Images with a Global Sparsity Prior on Reflectance

10 0.41584763 186 nips-2011-Noise Thresholds for Spectral Clustering

11 0.3993617 255 nips-2011-Simultaneous Sampling and Multi-Structure Fitting with Adaptive Reversible Jump MCMC

12 0.38977686 198 nips-2011-On U-processes and clustering performance

13 0.36851642 47 nips-2011-Beyond Spectral Clustering - Tight Relaxations of Balanced Graph Cuts

14 0.36737654 216 nips-2011-Portmanteau Vocabularies for Multi-Cue Image Representation

15 0.35902438 125 nips-2011-Identifying Alzheimer's Disease-Related Brain Regions from Multi-Modality Neuroimaging Data using Sparse Composite Linear Discrimination Analysis

16 0.35036901 67 nips-2011-Data Skeletonization via Reeb Graphs

17 0.34541106 181 nips-2011-Multiple Instance Learning on Structured Data

18 0.33976007 167 nips-2011-Maximum Covariance Unfolding : Manifold Learning for Bimodal Data

19 0.33847713 277 nips-2011-Submodular Multi-Label Learning

20 0.33520669 127 nips-2011-Image Parsing with Stochastic Scene Grammar

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.029), (4, 0.034), (20, 0.476), (26, 0.019), (31, 0.061), (33, 0.026), (43, 0.042), (45, 0.074), (57, 0.034), (60, 0.012), (65, 0.014), (74, 0.041), (99, 0.042)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.89361769 290 nips-2011-Transfer Learning by Borrowing Examples for Multiclass Object Detection

Author: Joseph J. Lim, Antonio Torralba, Ruslan Salakhutdinov

Abstract: Despite the recent trend of increasingly large datasets for object detection, there still exist many classes with few training examples. To overcome this lack of training data for certain classes, we propose a novel way of augmenting the training data for each class by borrowing and transforming examples from other classes. Our model learns which training instances from other classes to borrow and how to transform the borrowed examples so that they become more similar to instances from the target class. Our experimental results demonstrate that our new object detector, with borrowed and transformed examples, improves upon the current state-of-the-art detector on the challenging SUN09 object detection dataset. 1

2 0.88629669 275 nips-2011-Structured Learning for Cell Tracking

Author: Xinghua Lou, Fred A. Hamprecht

Abstract: We study the problem of learning to track a large quantity of homogeneous objects such as cell tracking in cell culture study and developmental biology. Reliable cell tracking in time-lapse microscopic image sequences is important for modern biomedical research. Existing cell tracking methods are usually kept simple and use only a small number of features to allow for manual parameter tweaking or grid search. We propose a structured learning approach that allows to learn optimum parameters automatically from a training set. This allows for the use of a richer set of features which in turn affords improved tracking compared to recently reported methods on two public benchmark sequences. 1

same-paper 3 0.88574469 119 nips-2011-Higher-Order Correlation Clustering for Image Segmentation

Author: Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, Chang D. Yoo

4 0.88029528 305 nips-2011-k-NN Regression Adapts to Local Intrinsic Dimension

Author: Samory Kpotufe

Abstract: Many nonparametric regressors were recently shown to converge at rates that depend only on the intrinsic dimension of data. These regressors thus escape the curse of dimension when high-dimensional data has low intrinsic dimension (e.g. a manifold). We show that k-NN regression is also adaptive to intrinsic dimension. In particular our rates are local to a query x and depend only on the way masses of balls centered at x vary with radius. Furthermore, we show a simple way to choose k = k(x) locally at any x so as to nearly achieve the minimax rate at x in terms of the unknown intrinsic dimension in the vicinity of x. We also establish that the minimax rate does not depend on a particular choice of metric space or distribution, but rather that this minimax rate holds for any metric space and doubling measure. 1

5 0.78269994 260 nips-2011-Sparse Features for PCA-Like Linear Regression

Author: Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail

Abstract: Principal Components Analysis (PCA) is often used as a feature extraction procedure. Given a matrix X ∈ Rn×d , whose rows represent n data points with respect to d features, the top k right singular vectors of X (the so-called eigenfeatures), are arbitrary linear combinations of all available features. The eigenfeatures are very useful in data analysis, including the regularization of linear regression. Enforcing sparsity on the eigenfeatures, i.e., forcing them to be linear combinations of only a small number of actual features (as opposed to all available features), can promote better generalization error and improve the interpretability of the eigenfeatures. We present deterministic and randomized algorithms that construct such sparse eigenfeatures while provably achieving in-sample performance comparable to regularized linear regression. Our algorithms are relatively simple and practically efﬁcient, and we demonstrate their performance on several data sets.

6 0.5432412 223 nips-2011-Probabilistic Joint Image Segmentation and Labeling

7 0.51401317 154 nips-2011-Learning person-object interactions for action recognition in still images

8 0.50733781 227 nips-2011-Pylon Model for Semantic Segmentation

9 0.49006158 303 nips-2011-Video Annotation and Tracking with Active Learning

10 0.4744522 1 nips-2011-$\theta$-MRF: Capturing Spatial and Semantic Structure in the Parameters for Scene Understanding

11 0.46120885 59 nips-2011-Composite Multiclass Losses

12 0.46054861 208 nips-2011-Optimistic Optimization of a Deterministic Function without the Knowledge of its Smoothness

13 0.46037698 166 nips-2011-Maximal Cliques that Satisfy Hard Constraints with Application to Deformable Object Model Learning

14 0.45796472 247 nips-2011-Semantic Labeling of 3D Point Clouds for Indoor Scenes

15 0.45773661 263 nips-2011-Sparse Manifold Clustering and Embedding

16 0.45717332 304 nips-2011-Why The Brain Separates Face Recognition From Object Recognition

17 0.45298034 266 nips-2011-Spatial distance dependent Chinese restaurant processes for image segmentation

18 0.45101002 76 nips-2011-Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials

19 0.45059016 180 nips-2011-Multiple Instance Filtering

20 0.43978673 25 nips-2011-Adaptive Hedge