iccv iccv2013 iccv2013-238 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Minsu Cho, Karteek Alahari, Jean Ponce
Abstract: Many tasks in computer vision are formulated as graph matching problems. Despite the NP-hard nature of the problem, fast and accurate approximations have led to significant progress in a wide range of applications. Learning graph models from observed data, however, still remains a challenging issue. This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures.
Reference: text
sentIndex sentText sentNum sentScore
1 It shows significant improvement a graph model from labeled data to provide the best match to over previous approaches for matching. [sent-3, score-0.539]
2 ) Abstract Many tasks in computer vision are formulated as graph matching problems. [sent-5, score-0.687]
3 Learning graph models from observed data, however, still remains a challenging issue. [sent-7, score-0.475]
4 This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. [sent-8, score-0.878]
5 For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. [sent-9, score-0.687]
6 Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures. [sent-10, score-0.447]
7 Introduction Graphs are widely used as a general and powerful representation in a variety of scientific fields, including computer vision, and many problems can be formulated as attributed graph matching. [sent-12, score-0.475]
8 Since graph matching is mathematically expressed as a quadratic assignment problem, which is NPhard, most research has long focused on developing accurate and efficient approximate algorithms [8, 14, 32]. [sent-13, score-0.875]
9 Much progress has been achieved recently in various applications of graph matching, such as shape analysis [27], image matching [12, 30], action recognition [33], and object categorization [3, 13]. [sent-14, score-0.687]
10 For many tasks, however, a natural question arises: How can we obtain a good graph model for a target object to match? [sent-16, score-0.509]
11 Recent studies have revealed that simple graphs with hand-crafted structures and similarity functions, typically used in graph matching, are insufficient to capture the inherent structure underlying the problem at hand. [sent-17, score-0.766]
12 As a consequence, a better optimization of the graph matching objective does not guarantee better correspondence accuracy [5, 6]. [sent-18, score-0.781]
13 Previous learning methods for graph matching tackle this issue by learning a set of parameters in the objective function [5, 21, 26, 30]. [sent-19, score-0.889]
14 Although it is useful to learn such a matching function for two graphs of a certain class, a more apt goal would be to learn a graph model to match, which provides an optimal matching to all instances of the class. [sent-20, score-1.219]
15 Such a learned graph would better model the inherent structure in the target class, thus resulting in better perfor- mance for matching. [sent-21, score-0.622]
16 In this paper, we propose to learn a graph model based on a particular, yet rather general, graph representation with histogram-based attributes for nodes and edges. [sent-22, score-1.342]
17 To this end, we present a generalized formulation for graph matching, which is an extension of previous learning approaches (Sec. [sent-23, score-0.612]
18 We show that all attributes of the graph can be learned in a max-margin framework [3 1] (Sec. [sent-25, score-0.816]
19 The proposed method reconstructs a graph model inherent in a target class, and provides impressive matching performance, as demonstrated in our experiments on synthetic and real datasets (Sec. [sent-27, score-0.842]
20 Here, the learned graph model finds better correspondences than a graph with a learned matching function as well as a hand-crafted graph. [sent-30, score-1.338]
21 In the context of certain graph matching applications, an iterative method that alternates between estimating parameters and punning some of the nodes and edges has been proposed [4, 19]. [sent-34, score-0.794]
22 Our approach differs from these methods in the sense that it learns attributes for all nodes and edges in a max-margin framework, not limited × to global parameters in clique functions or sparse selection of clique functions. [sent-35, score-0.621]
23 Graph matching revisited We begin by reviewing the standard graph matching formulation and elaborate on methods to learn its parameters. [sent-38, score-1.015]
24 Problem formulation The objective of graph matching is to find correspondences between two attributed graphs G = (V, E, A) and dGe? [sent-42, score-0.976]
25 oAf s eodlugetiso,n a nofd graph matching uist desef oinfe tdh as a seusb saentd o efd possible correspondences Y ⊂ V V? [sent-47, score-0.723]
26 W byith y t ∈hi s{ 0n,o1t}ation, graph matching problems can be expressed as finding the assignment vector y∗ that maximizes a score function S(G, G? [sent-55, score-0.876]
27 , y) measures the similarity of graph acottrreib fuutensc,t iaonnd Sis( typically decomposed into a firstorder similarity function sV (ai, a? [sent-71, score-0.657]
28 Thus, the score function of graph matching is defined as: S(G,G? [sent-84, score-0.72]
29 Due to its generality and flexibility, this formulation has been favored in recent graph matching research. [sent-96, score-0.743]
30 (2), an interesting question is what can be learned to improve graph matching. [sent-101, score-0.545]
31 Let π(i) = a denote an assignment of node vi in G to node va? [sent-104, score-0.51]
32 β = 1, it reduces to the conventional graph matching score function of Eq. [sent-120, score-0.72]
33 Despite its apparent simplicity, this formulation covers a wide range of parameter learning approaches proposed for graph matching. [sent-127, score-0.612]
34 While the optimization methods for learning these functions are 26 different, all of them are essentially aimed at learning common weights for all the edge and node similarity functions. [sent-137, score-0.646]
35 However, like previous approaches, it does not learn a graph model underlying the feature map Φ, and requires a reference graph G? [sent-140, score-1.118]
36 at query time, whose attributes cannot be emroednicfeie gdr ainp hth Ge learning phase. [sent-141, score-0.39]
37 Instead of a reference graph used in the previous section, we consider a class-specific model graph G∗ . [sent-146, score-1.058]
38 Let ˆy denote the optimal matching between the model graph G∗ and an input graph G, given by: yˆ(G;G∗,β) = ayr∈gYm(Ga)xS(G∗,G,y;β), (5) where β is a weight vector, Y(G) defines the set of poswsibheler assignment vghetcto vresc foorr, Yth(eG input graph eG s. [sent-148, score-1.759]
39 the I mspoirdeedl graph G∗ and its weights β from labeled examples D = (g? [sent-150, score-0.537]
40 We first separate the graph model G∗ from the joint feature map Φ(G∗ , G, y), so as atop parameterize iot separately. [sent-164, score-0.547]
41 Weateu assume tΦha(Gt th,eG s,iym)-, ilarity functions sV and sE are dot products of two attribute vectors: sV (ai∗ , aa) = ai∗ · aa, sE (ai∗j , aab) = ai∗j · aab, (7) where ai∗ and ai∗j correspond to the node and edge attributes of the model graph respectively. [sent-165, score-1.258]
42 Thus, when the similarity functions are dot products, both the graph model attributes and their weights can be jointly expressed by a single vector. [sent-175, score-1.079]
43 =n1Δ(yi, ˆ y(Gi;w)), (12) where all the graph model attributes and their weights, to be learned, are represented by w. [sent-181, score-0.746]
44 Unlike other learning methods for graph matching [5, 21, 26, 30], this formulation allows us to combine graph learning, and learning a matching function into a coherent structured output framework. [sent-183, score-1.592]
45 Histogram-attributed relational graph In general, any graph representation satisfying the condition of dot product similarity of Eq. [sent-187, score-1.151]
46 However, not all potential representations are effective in representing the data in the context of graph learning and matching performance. [sent-190, score-0.768]
47 In this work, we propose a new histogram-attributed relational graph (HARG), wherein all node and edge attributes are represented by histogram distributions. [sent-191, score-1.149]
48 The similarity value between two attributes in this graph is then computed as their dot product. [sent-192, score-0.914]
49 The histogram attributes in this framework can be composed of a variety of features. [sent-193, score-0.379]
50 The histogram of log-polar bins edge attribute describes the geometric relationship between two interest points as 27 illustrated in Fig. [sent-195, score-0.383]
51 1 Consider an edge eij from node vi (represented by point xi in Fig. [sent-198, score-0.506]
52 The log-distance histogram Lij is constructed on the bins by a discrete Gaussian histogram centered on the bin for ρij : – s. [sent-204, score-0.428]
53 The polar-angle histogram Pij is constructed on it in a similar way, except that a circular Gaussian histogram centered on the bin for θij with respect to the characteristic orientation of vi, is used: Pij (k) = fP(k − m), (14) s. [sent-208, score-0.39]
54 The final histogram composed by concatenating the log-distance Lij, and the polar-angle Pij, histograms is defined as the attribute for edge eij : aij = [Lij ; Pij], which is asymmetric (aij aji). [sent-211, score-0.471]
55 For node attributes ai, describing the local appearance of node vi, we could adopt the histogram of gradient bins such as SIFT [22], HOG [10], and their variants, given their effectiveness. [sent-216, score-0.759]
56 In contrast, our histogram for edge attributes consists of two separate log-distance and polar-angle ones. [sent-225, score-0.5]
57 The polar-angle θij of edge eij is measured from the characteristic orientation of vi, or from the horizontal line through vi (shown as a green line), when there is no such orientation. [sent-232, score-0.385]
58 We observed that our histogrambased similarity function showed better or comparable matching performance than other similarity measures used in [6, 9, 21]. [sent-251, score-0.394]
59 A fully-connected graph is used as the initial graph for learning. [sent-253, score-0.95]
60 For w/o learning, we use a conventional graph matching method with uniform weighting. [sent-255, score-0.719]
61 HARG-SSVM is our graph learning approach proposed in Sec. [sent-263, score-0.556]
62 It should be noted that the methods [5, 21] were originally proposed to learn the weights of a graph matching function for two graphs in the same class. [sent-266, score-0.966]
63 Our approach (HARG-SSVM), on the other hand, learns the graph model as well. [sent-267, score-0.515]
64 (b) We learn angle and distance attributes from these samples. [sent-276, score-0.388]
65 Two examples ofedge attributes are shown on the right, where the upper histogram represents distance and the lower histogram describes angle. [sent-278, score-0.487]
66 The learned attributes (red) not only recover the attributes of the source (blue), but also adjust its weights and variance. [sent-279, score-0.77]
67 Our task is to assign labels to new samples with graph matching. [sent-288, score-0.475]
68 Since there is no unary information in the points, graph matching in this case relies solely on pairwise similarity. [sent-290, score-0.687]
69 From each point set we construct a graph with our histogram-based attributes. [sent-291, score-0.515]
70 Several learning approaches (shown in each row) are evaluated with the stateof-the-art graph matching algorithms (in columns). [sent-293, score-0.768]
71 In contrast, our graph learning approach (HARG-SSVM) does not require such a reference graph, and consistently outperforms all the other learning approaches, including those with the source reference graphs. [sent-297, score-0.949]
72 In other words, ‘source’ corresponds to an ideal reference graph without deformations and noise, i. [sent-327, score-0.583]
73 , a graph formed by red dots on the left image of Fig. [sent-329, score-0.519]
74 We also use different graph matching algorithms to account for dependency on the matching algorithm used. [sent-334, score-0.899]
75 This is because our graph model additionally captures both the variation and the importance in edge attributes as shown in Fig. [sent-337, score-0.867]
76 House/Hotel dataset The CMU House/Hotel sequence is one of the most popular benchmark datasets for graph matching. [sent-343, score-0.475]
77 Here, we learn a graph model using only 3 training images (#0, #50, #100) from the 5 images they used, and match it to all the other test images. [sent-346, score-0.599]
78 Unlike [5, 21], we only rely on the edge attributes without any appearance descriptor. [sent-347, score-0.392]
79 Figure 5 shows the learned graphs and some example results of matching to other frames. [sent-349, score-0.439]
80 In Table 2, we also compared with other learning approaches (SW-SSVM, DW-SSVM) using a reference graph (#0). [sent-351, score-0.664]
81 In this case, a significant number of outliers exists, and thus graph matching becomes challenging. [sent-358, score-0.687]
82 Given a test image, we select kNN features (k = 50) for each node of the model graph based on dot product similarity, and construct 30 Table 2: Matching performance comparison on the CMU House/Hotel sequences. [sent-363, score-0.693]
83 The frame #0 was used as a reference graph in w/o learning, SW-SSVM, and DW-SSVM. [sent-364, score-0.583]
84 Note that while we learn a graph model and match it to all the other images, they learned the parameters for matching, and applied them to match all possible pairs among all the other images. [sent-367, score-0.733]
85 Then, we apply graph matching to find correspondence from the reference to the other images, and refine them by fixing incorrect matches. [sent-394, score-0.849]
86 Table 3 summarizes the results and Figure 4 shows the learned model graphs and their matching results. [sent-397, score-0.439]
87 For each sequence, a graph model is learned using 3 images, and tested on all the other images (108 for House, 98 for Hotel). [sent-400, score-0.545]
88 From left to right, the learned graph and two matching examples are shown. [sent-401, score-0.757]
89 In the graph models, darker lines denote edges with higher weights. [sent-402, score-0.573]
90 It suggests that the detailed attributes learned by our approach enable more accurate matching to other instances in the same class. [sent-406, score-0.596]
91 This experiment demonstrates that our approach successfully handles the practical challenges in matching by constructing a robust graph model. [sent-407, score-0.687]
92 Conclusion We presented a novel graph learning approach with a histogram-based representation and an SSVM framework. [sent-410, score-0.556]
93 In synthetic and real data experiments, we demonstrated that the proposed method effectively learns an inherent model graph from a training set, and provides good generalization to unseen instances for matching. [sent-411, score-0.679]
94 In future work, we plan to explore sparse graph representation for better efficiency. [sent-412, score-0.475]
95 In the graph model, bigger circles represent stronger nodes, and darker lines denote stronger edges. [sent-469, score-0.527]
96 The results show that the learned graph model enables robust matching in spite of deformation and appearance changes. [sent-472, score-0.757]
97 Progressive graph matching: Making a move of graphs via probabilistic voting. [sent-497, score-0.632]
98 An integer projected fixed point method for graph matching and map inference. [sent-578, score-0.727]
99 Feature correspondence via graph matching: Models and global optimization. [sent-641, score-0.529]
100 An eigen decomposition approach to weighted graph matching problems. [sent-652, score-0.687]
wordName wordTfidf (topN-words)
[('graph', 0.475), ('attributes', 0.271), ('matching', 0.212), ('sv', 0.163), ('graphs', 0.157), ('node', 0.141), ('assignment', 0.122), ('edge', 0.121), ('ai', 0.118), ('histogram', 0.108), ('leordeanu', 0.108), ('reference', 0.108), ('vi', 0.106), ('erroraccuracy', 0.099), ('bins', 0.098), ('eij', 0.098), ('source', 0.096), ('lij', 0.093), ('ssvm', 0.093), ('ij', 0.091), ('similarity', 0.091), ('aij', 0.088), ('pij', 0.087), ('learning', 0.081), ('synthetic', 0.078), ('dot', 0.077), ('bin', 0.077), ('se', 0.074), ('va', 0.072), ('parameterize', 0.072), ('learned', 0.07), ('functions', 0.069), ('clique', 0.067), ('esaps', 0.066), ('harg', 0.066), ('logdistance', 0.066), ('pachauri', 0.066), ('rnve', 0.066), ('match', 0.064), ('weights', 0.062), ('ab', 0.061), ('nodes', 0.061), ('characteristic', 0.06), ('learn', 0.06), ('cmu', 0.059), ('bottle', 0.059), ('aab', 0.058), ('angle', 0.057), ('formulation', 0.056), ('duchenne', 0.056), ('attribute', 0.056), ('hotel', 0.054), ('caetano', 0.054), ('correspondence', 0.054), ('darker', 0.052), ('eg', 0.051), ('vectorial', 0.051), ('nci', 0.051), ('aia', 0.048), ('ilarity', 0.048), ('duck', 0.048), ('joachims', 0.047), ('website', 0.047), ('cutting', 0.047), ('normale', 0.047), ('rieure', 0.047), ('edges', 0.046), ('wine', 0.045), ('dots', 0.044), ('house', 0.043), ('inherent', 0.043), ('instances', 0.043), ('fp', 0.043), ('markov', 0.042), ('objective', 0.04), ('learns', 0.04), ('point', 0.04), ('class', 0.039), ('viewed', 0.038), ('hth', 0.038), ('motorbike', 0.038), ('sup', 0.037), ('centered', 0.037), ('gi', 0.037), ('correspondences', 0.036), ('torresani', 0.035), ('loss', 0.035), ('collins', 0.035), ('expressed', 0.034), ('target', 0.034), ('px', 0.034), ('cho', 0.034), ('sample', 0.033), ('relational', 0.033), ('score', 0.033), ('hebert', 0.033), ('uniform', 0.032), ('quadratic', 0.032), ('vj', 0.032), ('fl', 0.032)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000007 238 iccv-2013-Learning Graphs to Match
Author: Minsu Cho, Karteek Alahari, Jean Ponce
Abstract: Many tasks in computer vision are formulated as graph matching problems. Despite the NP-hard nature of the problem, fast and accurate approximations have led to significant progress in a wide range of applications. Learning graph models from observed data, however, still remains a challenging issue. This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures.
2 0.41135874 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
Author: Quanshi Zhang, Xuan Song, Xiaowei Shao, Huijing Zhao, Ryosuke Shibasaki
Abstract: Although graph matching is a fundamental problem in pattern recognition, and has drawn broad interest from many fields, the problem of learning graph matching has not received much attention. In this paper, we redefine the learning ofgraph matching as a model learningproblem. In addition to conventional training of matching parameters, our approach modifies the graph structure and attributes to generate a graphical model. In this way, the model learning is oriented toward both matching and recognition performance, and can proceed in an unsupervised1 fashion. Experiments demonstrate that our approach outperforms conventional methods for learning graph matching.
3 0.27269381 214 iccv-2013-Improving Graph Matching via Density Maximization
Author: Chao Wang, Lei Wang, Lingqiao Liu
Abstract: Graph matching has been widely used in various applications in computer vision due to its powerful performance. However, it poses three challenges to image sparse feature matching: (1) The combinatorial nature limits the size of the possible matches; (2) It is sensitive to outliers because the objective function prefers more matches; (3) It works poorly when handling many-to-many object correspondences, due to its assumption of one single cluster for each graph. In this paper, we address these problems with a unified framework—Density Maximization. We propose a graph density local estimator (퐷퐿퐸) to measure the quality of matches. Density Maximization aims to maximize the 퐷퐿퐸 values both locally and globally. The local maximization of 퐷퐿퐸 finds the clusters of nodes as well as eliminates the outliers. The global maximization of 퐷퐿퐸 efficiently refines the matches by exploring a much larger matching space. Our Density Maximization is orthogonal to specific graph matching algorithms. Experimental evaluation demonstrates that it significantly boosts the true matches and enables graph matching to handle both outliers and many-to-many object correspondences.
4 0.23302142 81 iccv-2013-Combining the Right Features for Complex Event Recognition
Author: Kevin Tang, Bangpeng Yao, Li Fei-Fei, Daphne Koller
Abstract: In this paper, we tackle the problem of combining features extracted from video for complex event recognition. Feature combination is an especially relevant task in video data, as there are many features we can extract, ranging from image features computed from individual frames to video features that take temporal information into account. To combine features effectively, we propose a method that is able to be selective of different subsets of features, as some features or feature combinations may be uninformative for certain classes. We introduce a hierarchical method for combining features based on the AND/OR graph structure, where nodes in the graph represent combinations of different sets of features. Our method automatically learns the structure of the AND/OR graph using score-based structure learning, and we introduce an inference procedure that is able to efficiently compute structure scores. We present promising results and analysis on the difficult and large-scale 2011 TRECVID Multimedia Event Detection dataset [17].
5 0.20360768 224 iccv-2013-Joint Optimization for Consistent Multiple Graph Matching
Author: Junchi Yan, Yu Tian, Hongyuan Zha, Xiaokang Yang, Ya Zhang, Stephen M. Chu
Abstract: The problem of graph matching in general is NP-hard and approaches have been proposed for its suboptimal solution, most focusing on finding the one-to-one node mapping between two graphs. A more general and challenging problem arises when one aims to find consistent mappings across a number of graphs more than two. Conventional graph pair matching methods often result in mapping inconsistency since the mapping between two graphs can either be determined by pair mapping or by an additional anchor graph. To address this issue, a novel formulation is derived which is maximized via alternating optimization. Our method enjoys several advantages: 1) the mappings are jointly optimized rather than sequentially performed by applying pair matching, allowing the global affinity information across graphs can be propagated and explored; 2) the number of concerned variables to optimize is in linear with the number of graphs, being superior to local pair matching resulting in O(n2) variables; 3) the mapping consistency constraints are analytically satisfied during optimization; and 4) off-the-shelf graph pair matching solvers can be reused under the proposed framework in an ‘out-of-thebox’ fashion. Competitive results on both the synthesized data and the real data are reported, by varying the level of deformation, outliers and edge densities. ∗Corresponding author. The work is supported by NSF IIS1116886, NSF IIS-1049694, NSFC 61129001/F010403 and the 111 Project (B07022). Yu Tian Shanghai Jiao Tong University Shanghai, China, 200240 yut ian @ s j tu . edu .cn Xiaokang Yang Shanghai Jiao Tong University Shanghai, China, 200240 xkyang@ s j tu .edu . cn Stephen M. Chu IBM T.J. Waston Research Center Yorktown Heights, NY USA, 10598 s chu @u s . ibm . com
6 0.18779673 31 iccv-2013-A Unified Probabilistic Approach Modeling Relationships between Attributes and Objects
7 0.18592885 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
8 0.18523893 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
9 0.1816199 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
10 0.1791465 52 iccv-2013-Attribute Adaptation for Personalized Image Search
11 0.16868412 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
12 0.1652451 445 iccv-2013-Visual Reranking through Weakly Supervised Multi-graph Learning
13 0.14821677 276 iccv-2013-Multi-attributed Dictionary Learning for Sparse Coding
14 0.14027075 53 iccv-2013-Attribute Dominance: What Pops Out?
15 0.12442306 7 iccv-2013-A Deep Sum-Product Architecture for Robust Facial Attributes Analysis
16 0.12325359 404 iccv-2013-Structured Forests for Fast Edge Detection
17 0.12276065 186 iccv-2013-GrabCut in One Cut
18 0.1202972 429 iccv-2013-Tree Shape Priors with Connectivity Constraints Using Convex Relaxation on General Graphs
19 0.11672729 256 iccv-2013-Locally Affine Sparse-to-Dense Matching for Motion and Occlusion Estimation
20 0.11283969 140 iccv-2013-Elastic Net Constraints for Shape Matching
topicId topicWeight
[(0, 0.296), (1, 0.084), (2, -0.059), (3, -0.109), (4, 0.097), (5, 0.049), (6, -0.09), (7, -0.057), (8, 0.195), (9, -0.034), (10, -0.138), (11, 0.026), (12, 0.03), (13, 0.122), (14, 0.163), (15, 0.18), (16, 0.104), (17, -0.02), (18, 0.017), (19, 0.012), (20, -0.004), (21, 0.065), (22, -0.045), (23, 0.005), (24, 0.249), (25, -0.035), (26, -0.159), (27, 0.018), (28, 0.005), (29, 0.069), (30, 0.167), (31, 0.112), (32, 0.1), (33, -0.004), (34, -0.041), (35, 0.071), (36, 0.072), (37, -0.074), (38, -0.081), (39, 0.048), (40, 0.049), (41, -0.025), (42, -0.023), (43, 0.046), (44, 0.018), (45, 0.087), (46, 0.019), (47, -0.036), (48, 0.035), (49, 0.058)]
simIndex simValue paperId paperTitle
same-paper 1 0.98624611 238 iccv-2013-Learning Graphs to Match
Author: Minsu Cho, Karteek Alahari, Jean Ponce
Abstract: Many tasks in computer vision are formulated as graph matching problems. Despite the NP-hard nature of the problem, fast and accurate approximations have led to significant progress in a wide range of applications. Learning graph models from observed data, however, still remains a challenging issue. This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures.
2 0.97051966 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
Author: Quanshi Zhang, Xuan Song, Xiaowei Shao, Huijing Zhao, Ryosuke Shibasaki
Abstract: Although graph matching is a fundamental problem in pattern recognition, and has drawn broad interest from many fields, the problem of learning graph matching has not received much attention. In this paper, we redefine the learning ofgraph matching as a model learningproblem. In addition to conventional training of matching parameters, our approach modifies the graph structure and attributes to generate a graphical model. In this way, the model learning is oriented toward both matching and recognition performance, and can proceed in an unsupervised1 fashion. Experiments demonstrate that our approach outperforms conventional methods for learning graph matching.
3 0.93868244 224 iccv-2013-Joint Optimization for Consistent Multiple Graph Matching
Author: Junchi Yan, Yu Tian, Hongyuan Zha, Xiaokang Yang, Ya Zhang, Stephen M. Chu
Abstract: The problem of graph matching in general is NP-hard and approaches have been proposed for its suboptimal solution, most focusing on finding the one-to-one node mapping between two graphs. A more general and challenging problem arises when one aims to find consistent mappings across a number of graphs more than two. Conventional graph pair matching methods often result in mapping inconsistency since the mapping between two graphs can either be determined by pair mapping or by an additional anchor graph. To address this issue, a novel formulation is derived which is maximized via alternating optimization. Our method enjoys several advantages: 1) the mappings are jointly optimized rather than sequentially performed by applying pair matching, allowing the global affinity information across graphs can be propagated and explored; 2) the number of concerned variables to optimize is in linear with the number of graphs, being superior to local pair matching resulting in O(n2) variables; 3) the mapping consistency constraints are analytically satisfied during optimization; and 4) off-the-shelf graph pair matching solvers can be reused under the proposed framework in an ‘out-of-thebox’ fashion. Competitive results on both the synthesized data and the real data are reported, by varying the level of deformation, outliers and edge densities. ∗Corresponding author. The work is supported by NSF IIS1116886, NSF IIS-1049694, NSFC 61129001/F010403 and the 111 Project (B07022). Yu Tian Shanghai Jiao Tong University Shanghai, China, 200240 yut ian @ s j tu . edu .cn Xiaokang Yang Shanghai Jiao Tong University Shanghai, China, 200240 xkyang@ s j tu .edu . cn Stephen M. Chu IBM T.J. Waston Research Center Yorktown Heights, NY USA, 10598 s chu @u s . ibm . com
4 0.91850799 214 iccv-2013-Improving Graph Matching via Density Maximization
Author: Chao Wang, Lei Wang, Lingqiao Liu
Abstract: Graph matching has been widely used in various applications in computer vision due to its powerful performance. However, it poses three challenges to image sparse feature matching: (1) The combinatorial nature limits the size of the possible matches; (2) It is sensitive to outliers because the objective function prefers more matches; (3) It works poorly when handling many-to-many object correspondences, due to its assumption of one single cluster for each graph. In this paper, we address these problems with a unified framework—Density Maximization. We propose a graph density local estimator (퐷퐿퐸) to measure the quality of matches. Density Maximization aims to maximize the 퐷퐿퐸 values both locally and globally. The local maximization of 퐷퐿퐸 finds the clusters of nodes as well as eliminates the outliers. The global maximization of 퐷퐿퐸 efficiently refines the matches by exploring a much larger matching space. Our Density Maximization is orthogonal to specific graph matching algorithms. Experimental evaluation demonstrates that it significantly boosts the true matches and enables graph matching to handle both outliers and many-to-many object correspondences.
5 0.73986787 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
Author: K.C. Amit Kumar, Christophe De_Vleeschouwer
Abstract: Given a set of plausible detections, detected at each time instant independently, we investigate how to associate them across time. This is done by propagating labels on a set of graphs that capture how the spatio-temporal and the appearance cues promote the assignment of identical or distinct labels to a pair of nodes. The graph construction is driven by the locally linear embedding (LLE) of either the spatio-temporal or the appearance features associated to the detections. Interestingly, the neighborhood of a node in each appearance graph is defined to include all nodes for which the appearance feature is available (except the ones that coexist at the same time). This allows to connect the nodes that share the same appearance even if they are temporally distant, which gives our framework the uncommon ability to exploit the appearance features that are available only sporadically along the sequence of detections. Once the graphs have been defined, the multi-object tracking is formulated as the problem of finding a label assignment that is consistent with the constraints captured by each of the graphs. This results into a difference of convex program that can be efficiently solved. Experiments are performed on a basketball and several well-known pedestrian datasets in order to validate the effectiveness of the proposed solution.
6 0.72281229 81 iccv-2013-Combining the Right Features for Complex Event Recognition
7 0.68249589 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
8 0.66734982 445 iccv-2013-Visual Reranking through Weakly Supervised Multi-graph Learning
9 0.66223824 11 iccv-2013-A Fully Hierarchical Approach for Finding Correspondences in Non-rigid Shapes
10 0.620628 324 iccv-2013-Potts Model, Parametric Maxflow and K-Submodular Functions
11 0.61492801 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
12 0.61011094 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
13 0.57389104 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
14 0.56611454 205 iccv-2013-Human Re-identification by Matching Compositional Template with Cluster Sampling
15 0.56265986 140 iccv-2013-Elastic Net Constraints for Shape Matching
16 0.55868489 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
17 0.5559175 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
18 0.53375077 194 iccv-2013-Heterogeneous Image Features Integration via Multi-modal Semi-supervised Learning Model
19 0.53043836 313 iccv-2013-Person Re-identification by Salience Matching
20 0.52978432 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
topicId topicWeight
[(2, 0.097), (4, 0.02), (6, 0.011), (7, 0.022), (8, 0.086), (12, 0.011), (26, 0.082), (31, 0.055), (40, 0.011), (42, 0.087), (48, 0.01), (55, 0.01), (64, 0.065), (68, 0.029), (73, 0.04), (78, 0.021), (89, 0.224), (95, 0.031)]
simIndex simValue paperId paperTitle
1 0.95377892 186 iccv-2013-GrabCut in One Cut
Author: Meng Tang, Lena Gorelick, Olga Veksler, Yuri Boykov
Abstract: Among image segmentation algorithms there are two major groups: (a) methods assuming known appearance models and (b) methods estimating appearance models jointly with segmentation. Typically, the first group optimizes appearance log-likelihoods in combination with some spacial regularization. This problem is relatively simple and many methods guarantee globally optimal results. The second group treats model parameters as additional variables transforming simple segmentation energies into highorder NP-hard functionals (Zhu-Yuille, Chan-Vese, GrabCut, etc). It is known that such methods indirectly minimize the appearance overlap between the segments. We propose a new energy term explicitly measuring L1 distance between the object and background appearance models that can be globally maximized in one graph cut. We show that in many applications our simple term makes NP-hard segmentation functionals unnecessary. Our one cut algorithm effectively replaces approximate iterative optimization techniques based on block coordinate descent.
2 0.95123661 3 iccv-2013-3D Sub-query Expansion for Improving Sketch-Based Multi-view Image Retrieval
Author: Yen-Liang Lin, Cheng-Yu Huang, Hao-Jeng Wang, Winston Hsu
Abstract: We propose a 3D sub-query expansion approach for boosting sketch-based multi-view image retrieval. The core idea of our method is to automatically convert two (guided) 2D sketches into an approximated 3D sketch model, and then generate multi-view sketches as expanded sub-queries to improve the retrieval performance. To learn the weights among synthesized views (sub-queries), we present a new multi-query feature to model the similarity between subqueries and dataset images, and formulate it into a convex optimization problem. Our approach shows superior performance compared with the state-of-the-art approach on a public multi-view image dataset. Moreover, we also conduct sensitivity tests to analyze the parameters of our approach based on the gathered user sketches.
3 0.95118237 246 iccv-2013-Learning the Visual Interpretation of Sentences
Author: C. Lawrence Zitnick, Devi Parikh, Lucy Vanderwende
Abstract: Sentences that describe visual scenes contain a wide variety of information pertaining to the presence of objects, their attributes and their spatial relations. In this paper we learn the visual features that correspond to semantic phrases derived from sentences. Specifically, we extract predicate tuples that contain two nouns and a relation. The relation may take several forms, such as a verb, preposition, adjective or their combination. We model a scene using a Conditional Random Field (CRF) formulation where each node corresponds to an object, and the edges to their relations. We determine the potentials of the CRF using the tuples extracted from the sentences. We generate novel scenes depicting the sentences’ visual meaning by sampling from the CRF. The CRF is also used to score a set of scenes for a text-based image retrieval task. Our results show we can generate (retrieve) scenes that convey the desired semantic meaning, even when scenes (queries) are described by multiple sentences. Significant improvement is found over several baseline approaches.
same-paper 4 0.94060141 238 iccv-2013-Learning Graphs to Match
Author: Minsu Cho, Karteek Alahari, Jean Ponce
Abstract: Many tasks in computer vision are formulated as graph matching problems. Despite the NP-hard nature of the problem, fast and accurate approximations have led to significant progress in a wide range of applications. Learning graph models from observed data, however, still remains a challenging issue. This paper presents an effective scheme to parameterize a graph model, and learn its structural attributes for visual object matching. For this, we propose a graph representation with histogram-based attributes, and optimize them to increase the matching accuracy. Experimental evaluations on synthetic and real image datasets demonstrate the effectiveness of our approach, and show significant improvement in matching accuracy over graphs with pre-defined structures.
5 0.93528563 272 iccv-2013-Modifying the Memorability of Face Photographs
Author: Aditya Khosla, Wilma A. Bainbridge, Antonio Torralba, Aude Oliva
Abstract: Contemporary life bombards us with many new images of faces every day, which poses non-trivial constraints on human memory. The vast majority of face photographs are intended to be remembered, either because of personal relevance, commercial interests or because the pictures were deliberately designed to be memorable. Can we make aportrait more memorable or more forgettable automatically? Here, we provide a method to modify the memorability of individual face photographs, while keeping the identity and other facial traits (e.g. age, attractiveness, and emotional magnitude) of the individual fixed. We show that face photographs manipulated to be more memorable (or more forgettable) are indeed more often remembered (or forgotten) in a crowd-sourcing experiment with an accuracy of 74%. Quantifying and modifying the ‘memorability ’ of a face lends itself to many useful applications in computer vision and graphics, such as mnemonic aids for learning, photo editing applications for social networks and tools for designing memorable advertisements.
6 0.93177956 426 iccv-2013-Training Deformable Part Models with Decorrelated Features
7 0.9304949 107 iccv-2013-Deformable Part Descriptors for Fine-Grained Recognition and Attribute Prediction
8 0.92955697 111 iccv-2013-Detecting Dynamic Objects with Multi-view Background Subtraction
9 0.92914748 203 iccv-2013-How Related Exemplars Help Complex Event Detection in Web Videos?
10 0.92833471 361 iccv-2013-Robust Trajectory Clustering for Motion Segmentation
11 0.92714924 265 iccv-2013-Mining Motion Atoms and Phrases for Complex Action Recognition
12 0.9260031 127 iccv-2013-Dynamic Pooling for Complex Event Recognition
13 0.9256655 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
14 0.92561638 396 iccv-2013-Space-Time Robust Representation for Action Recognition
15 0.92530668 95 iccv-2013-Cosegmentation and Cosketch by Unsupervised Learning
16 0.92527032 62 iccv-2013-Bird Part Localization Using Exemplar-Based Models with Enforced Pose and Subcategory Consistency
17 0.92522347 204 iccv-2013-Human Attribute Recognition by Rich Appearance Dictionary
18 0.92496181 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
19 0.92491585 89 iccv-2013-Constructing Adaptive Complex Cells for Robust Visual Tracking
20 0.92489445 439 iccv-2013-Video Co-segmentation for Meaningful Action Extraction