iccv iccv2013 iccv2013-214 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 We propose a graph density local estimator (퐷퐿퐸) to measure the quality of matches. [sent-6, score-0.715]
2 The local maximization of 퐷퐿퐸 finds the clusters of nodes as well as eliminates the outliers. [sent-8, score-0.63]
3 The global maximization of 퐷퐿퐸 efficiently refines the matches by exploring a much larger matching space. [sent-9, score-0.917]
4 Our Density Maximization is orthogonal to specific graph matching algorithms. [sent-10, score-0.455]
5 Experimental evaluation demonstrates that it significantly boosts the true matches and enables graph matching to handle both outliers and many-to-many object correspondences. [sent-11, score-1.042]
6 As a result, SFC can be modelled as graph matching in which graph nodes represent features extracted from each image while graph edges represent relationships between features. [sent-15, score-1.134]
7 , RANSAC with rigid transformation assumption), graph matching prol ingqiao . [sent-21, score-0.429]
8 There have been a myriad of algorithms proposed for graph matching [7]. [sent-26, score-0.429]
9 Among recent algorithms, the Integer Quadratic Programming (IQP) has emerged as a de facto formulation of graph matching [2, 8, 14, 15, 23, 19, 11]. [sent-28, score-0.429]
10 Firstly, the combinatorial nature of graph matching makes computation of the full affinity matrix in IQP intractable for large graphs. [sent-33, score-0.545]
11 Secondly, due to the non-negative property of the edge attributes, the objective function of IQP prefers more matches even if they are outliers. [sent-34, score-0.431]
12 Last but not least, IQP assumes that each graph contains only one cluster of nodes. [sent-35, score-0.345]
13 Therefore, graph matching poses three challenges to SFC: (1) its combinatorial nature limits the size of the possible matches; (2) it is sensitive to outliers; (3) it works poorly for many-to-many object correspondences. [sent-37, score-0.531]
14 To address the first challenge, most methods establish the set of candidate matches by using unary descriptors of discriminative features, such as SIFT [18], at a relatively low cost. [sent-38, score-0.441]
15 [5] proposed a progressive framework to update candidate matches based on pair-wise geometric relationships between new matches and the cur33441247 rent graph matching result. [sent-42, score-1.222]
16 However, it tends to introduce many outliers because the current graph matching result might be noisy. [sent-44, score-0.681]
17 Each cluster of matches naturally corresponds to one object pair, and the outliers are filtered out by eliminating the clusters with small sizes or authorities[3]. [sent-52, score-0.645]
18 [17] introduced a graph shift algorithm to detect dense subgraphs with iterative shrinking and expansion. [sent-59, score-0.377]
19 [12] presented a median graph shift which is an extension of the medoid shift based on the concept of the median graph. [sent-61, score-0.467]
20 We first propose a density local estimator (퐷퐿퐸) which is a reliable measure for the quality of matches. [sent-68, score-0.428]
21 [16] who observed that the geometric transformations associated with neighbouring true matches are smoothly varying even for significant displacements. [sent-70, score-0.532]
22 Density Maximization is then modeled as maximization of the 퐷퐿퐸 values both locally and globally. [sent-72, score-0.369]
23 Our global maximization, called Density-Ascent Update (퐷퐴푈), refines the candidate matches by efficiently exploring a much larger matching space. [sent-76, score-0.589]
24 [5] which updates matches in a progressive way, but is more than one order of magnitude faster than [5] while introducing much less outliers. [sent-78, score-0.388]
25 This simple scheme ensures that updating candidate matches is mainly based on the inliers, thus leading to a high precision. [sent-81, score-0.449]
26 Similar to the progression method [5], Density Maximization is orthogonal to specific graph matching algorithms and can be used to improve any of them. [sent-82, score-0.543]
27 Experimental evaluation on extensive natural images demonstrates that Density Maximization significantly boosts the true matches and enables graph matching to handle outliers and many-to-many object correspondences. [sent-83, score-1.042]
28 Compared to the state-of-the-art methods, Density Maximization has the following advantages: (1) It addresses the three challenges of graph matching in a unified framework. [sent-84, score-0.482]
29 The objective of graph matching is to find a mapping between 푉푃 and 푉푄, represented by a binary assignment matrix 푋 ∈ {0, with 푛푃 and 푛a 푄b denoting nthme ennutm mbaetrris xo f푋 no ∈d e{s0 ,i1n} 퐺푃 and 퐺푄 respectively. [sent-92, score-0.493]
30 푋푖,푎 = 1implies that node 푣푖푃 ∈ 푉푃 matches node 푣푎푄 ∈ 푉푄. [sent-93, score-0.697]
31 Let 푥 ∈ {0, denote the column-wise vect∈oriz 푉ed replica 푥o f∈ ∈푋 {,0 t,h1e} integer quadratic programming (IQP) formulates graph matching as 퐴, 1}푛푃×푛푄 1}푛푃푛푄 푥∗ = argm푥ax푥푇푊푥, 푠. [sent-94, score-0.465]
32 A diagonal element 푊푖푎;푖푎 represents a unary similarity of a match (푣푃푖, 푣푎푄), and a non- 푊 × diagonal term 푊푖푎;푗푏 refers to a pairwise similarity of two matches (푣푃푖, 푣푎푄) and (푣푃푗, Every element of 푊 is non-negative. [sent-99, score-0.441]
33 The Graph Matching result contains 283 true matches together with 315 outliers. [sent-103, score-0.429]
34 퐷퐴푆 eliminates most outliers and detects four boosts the number of true matches to 416 and introduces only 63 outliers. [sent-106, score-0.687]
35 True matches are shown with color lines and false matches are shown with black lines. [sent-108, score-0.771]
36 Most graph matching amtreitxho odf ds irmedeuncseiosn nth (e푛 s×iz푛e) of 푊 by using matches at a relatively high unary similarity. [sent-115, score-0.829]
37 This means that IQP prefers including the matches of all the features, even if they might be outliers. [sent-119, score-0.443]
38 This measure is problematic for many-to-many object correspondences because the matches in one object correspondence might clutter those in others. [sent-126, score-0.491]
39 Density Maximization Similar to [2, 4, 14, 18], we construct an association graph 퐺푎푔 = (푉푎푔, 퐸푎푔, 퐴푎푔) based on the affinity matrix 푊. [sent-129, score-0.356]
40 Then the original graph matching problem betwe∈en 퐸 퐸퐺푃 and 퐺푄 becomes node selection problem in the graph 퐺푎푔. [sent-131, score-0.896]
41 Given an image pair, the salient features are firstly extracted from each image and then 푁퐶 candidate matches are readily established using unary descriptors of the features at a relatively low cost. [sent-136, score-0.484]
42 Those matches are taken as the nodes of an initial association graph. [sent-137, score-0.495]
43 Then a reduced set of nodes and their edges are selectively used to construct a new graph which is called valid graph 퐺푉 in this paper. [sent-139, score-0.705]
44 Based on 퐺푉, 퐷퐴푆 finds the clusters of nodes as well as removes the outliers by local maximization of the 퐷퐿퐸 values. [sent-141, score-0.782]
45 퐷퐴푈 produces a updated graph 퐺푈 with 푁퐶 nodes by global maximization of the 퐷퐿퐸 values via exploring a much larger graph called potential graph 퐺푇. [sent-142, score-1.405]
46 This ensures that the updates of matches are mainly based on inliers. [sent-144, score-0.367]
47 1, Density Maximization is 푎푖푎;푗푏 orthogonal to specific graph matching algorithms, and any 33441269 EDL135420 0node2l0cation(w40idth)n 6e0iIOmnulaietgr s80EDL2150 nodel20cation(w40dth)in 60eIOinmulategirs 80 (a) (b) Figure 2. [sent-148, score-0.455]
48 Kernel density estimation for inliers (denoted by red star) and outliers (denoted by black dot). [sent-149, score-0.628]
49 of them can be adopted as the graph matching module in the framework. [sent-152, score-0.429]
50 Density local estimator Recently, graph density has shown its potentials to identify inliers and detect strongly connected node clusters in an association graph. [sent-155, score-1.081]
51 A few attempts to define the graph density include the average kernel density of Liu et al. [sent-156, score-1.017]
52 [4], and the personalized PageRank density of Cho et al. [sent-158, score-0.396]
53 The intuitive of 퐷퐿퐸 is to estimate graph density at one node by using only the nodes within a same object, so that it can avoid the clutter problem introduced by outliers and the nodes in other objects. [sent-162, score-1.29]
54 Fortunately, it has been observed that the geometric transformations associated with neighbouring matches in a same object are smoothly varying even for significant displacements [16]. [sent-164, score-0.467]
55 We adopt the popular kernel density estimation method to compute the graph density locally. [sent-169, score-1.017]
56 We consider node selection as a distribution and use 푥푖 to denote the probability of selecting node 푣푖. [sent-170, score-0.36]
57 T푁h(e 푁 density a)t t 푣푖 eiss 퐷퐿퐸(푖) =∑푗∈Ω(푖)푁푁푥푗퐾(푖,푗)=푗∈∑Ω(푖)푥푗퐾(푖,푗) (3) This is called 퐷퐿퐸 in this paper. [sent-172, score-0.365]
58 The only difference between 퐷퐿퐸 and the classical kernel density estimation lies in Ω. [sent-179, score-0.365]
59 The node selection probability 푥 naturally corresponds to the solutions to (1) since many graph matching methods solve (1) by relaxing the constraints on 푥 such that its elements can take real values in [0,1]. [sent-187, score-0.609]
60 In those methods, 푥 can be viewed as the confidence that the matches are true [14] or as the probability of visits by random walks [2, 13, 4]. [sent-188, score-0.402]
61 For other graph matching methods in which 푥 are integer, we normalize 푥 to obtain a uniform distribution. [sent-190, score-0.429]
62 Therefore 퐷퐿퐸 is orthogonal to specific graph matching algorithms whether 푥 are continuous or not, unlike other methods. [sent-191, score-0.455]
63 1, the aim of 퐷퐴푆 is to produce node clusters and eliminate outliers from valid graph 퐺푉. [sent-195, score-0.717]
64 퐷퐴푆 is a mode-seeking method and the density modes on a graph are defined as follows. [sent-196, score-0.652]
65 The density-ascent 퐷퐴(푖) of node 푣푖 is formulated as 퐷퐴(푖) = arg푗 m∈Ωa(x푖)퐾(푖,푗)Δ퐷퐿퐸(푗) (6) which means the neighbouring node of 푣푖 with the highest expectation of 퐷퐿퐸 increment. [sent-199, score-0.403]
66 Theorem 1 A finite sequence of density-ascent shifts from any node converges to a density mode. [sent-203, score-0.576]
67 Proof Since Ω(푖) ofany node 푣푖 includes itself, the 퐷퐿퐸 values of a sequence of shifts keep strictly increasing until the shifts reach a node whose density-ascent is itself. [sent-204, score-0.422]
68 The final node, therefore, is the density mode, and the length of the sequence is ∣푉푉∣ at most, with ∣푉푉∣ denoting the noufm thbeer s eoqfu neondcees iisn ∣퐺푉푉. [sent-205, score-0.403]
69 The trajectory of nodes sharing a common density mode builds a tree, and leads to a natural cluster. [sent-208, score-0.525]
70 Density Ascent Update Given a clean graph 퐺퐶, the aim of 퐷퐴푈 is to produce a updated graph 퐺푈 with 푁퐶 nodes by maximizing the total 퐷퐿퐸 values. [sent-218, score-0.731]
71 퐺푇 covers most true matches and will be detailed later. [sent-220, score-0.43]
72 since 퐺퐶 ⊂ 퐺푇, this global maximization scheme ensures that 퐷퐴푈⊂ ⊂no 퐺n-decreases the total 퐷퐿퐸 values. [sent-222, score-0.399]
73 By investigating the nodes for true matches in Fig. [sent-229, score-0.533]
74 The potential graph 퐺푇 is constructed using 푍 matches for each feature based on the unary similarity. [sent-238, score-0.687]
75 We test on the image pairs of the intra-class dataset[1] which own large intra-category variations, and find that 퐺푇 covers more than 95% true matches when 푍 = 40. [sent-239, score-0.43]
76 Analysis Using the approximate nearest neighbour (ANN) search, the computational complexity of 퐷퐴푈 is 푂(푘∣푉푉∣ log(푍푛푃)) with ∣푉푉∣ denoting the node n푂u(m푘b∣푉er o∣lfo g퐺(푍푉,푛 푛푃 denoting 푉the node number of graph 퐺푃 (i. [sent-244, score-0.749]
77 The main difference is that 퐷퐴푈 explores the potential graph 퐺푇 while the progression method searches the whole matching space based on 퐺푉. [sent-249, score-0.517]
78 More importantly, either 퐷퐴푈 or 퐷퐴푆 is much faster than most graph matching methods [2, 8, 14, 15, 23, 19, 11], indicating that we can improve graph matching without introducing too much computational cost. [sent-254, score-0.858]
79 This ensures that the updating matches is mainly based on inliers. [sent-256, score-0.408]
80 Experiments In our experiments, the candidate matches are generated using the SIFT descriptor. [sent-260, score-0.378]
81 To measure the similarity between two matches (푣푃푖, 푣푎푄) and (푣푃푗, 푣푏푄), we adopted the symmetric transfer error 푑(푖푎; 푗푏) used in [5, 13, 1, 4]. [sent-261, score-0.374]
82 (a)The result by GP[5] based on the graph matching result in Fig. [sent-275, score-0.483]
83 For fair comparison, we adopt those features and always fix the number of candidate matches 푁퐶 to the same as the number of the given initial matches. [sent-286, score-0.378]
84 Density Maximization vs related work Density Maximization contains novel approaches to both updating matches (i. [sent-295, score-0.378]
85 True matches are shown with green lines and false matches are shown with black lines. [sent-305, score-0.771]
86 For fair comparison, we adopt the same progressive framework as GP, which performs graph matching and updating matches iteratively. [sent-312, score-0.858]
87 True matches are shown with green lines and false matches are shown with black lines. [sent-337, score-0.771]
88 In contrast, our 퐷퐴푆 successfully detects true matches and distinguishes them from outliers. [sent-342, score-0.435]
89 Density Maximization vs Graph Matching In this experiment, we show the improvement of Density Maximization on several state-of-the arts graph matching methods: SM[14], PM[24], BGM[8], IPFP[15] and RRWM[2]. [sent-361, score-0.429]
90 The graph matching methods cannot distinguish inliers from outliers, and fail to separate matches of one object from those of others. [sent-364, score-0.836]
91 (e)The result by our Density Maximization with RRWM as the graph matching module. [sent-370, score-0.456]
92 (f)The result by our Density Maximization with SM as the graph matching module. [sent-371, score-0.456]
93 True matches are shown with color lines and false matches are shown with black lines. [sent-372, score-0.771]
94 Conclusion We introduced a unified framework, called Density Maximization, which effectively resolves the three limitations of conventional graph matching and achieves impressive per- formance improvement. [sent-375, score-0.454]
95 By globally and locally maximizing a novel proposed density estimator, i. [sent-376, score-0.365]
96 , density local estimator, Density Maximization leads to the integration of updating matches, eliminating outliers and cluster detection. [sent-378, score-0.625]
97 We point out that the key to the high performance is twofold: a well-defined local smooth neighbourhood to avoid clutter and an iteration scheme to ensure that updating matches is mainly based on inliers. [sent-379, score-0.494]
98 Median graph shift: A new clustering algorithm for graph domain. [sent-460, score-0.605]
99 An integer projected fixed point method for graph matching and map inference. [sent-477, score-0.465]
100 Feature correspondence via graph matching: Models and global optimization. [sent-527, score-0.342]
wordName wordTfidf (topN-words)
[('maximization', 0.369), ('density', 0.365), ('matches', 0.337), ('graph', 0.287), ('iqp', 0.27), ('acc', 0.191), ('gp', 0.186), ('node', 0.18), ('cho', 0.168), ('outliers', 0.161), ('matching', 0.142), ('nodes', 0.131), ('sae', 0.125), ('clusters', 0.089), ('progression', 0.088), ('ascent', 0.078), ('toys', 0.077), ('ppr', 0.071), ('tdp', 0.071), ('inliers', 0.07), ('prefers', 0.068), ('true', 0.065), ('unary', 0.063), ('estimator', 0.063), ('rrwm', 0.063), ('shift', 0.061), ('sfc', 0.058), ('medoid', 0.058), ('cluster', 0.058), ('ethz', 0.056), ('correspondence', 0.055), ('mser', 0.055), ('neighbourhood', 0.053), ('agglomerative', 0.052), ('progressive', 0.051), ('boosts', 0.05), ('jouili', 0.047), ('exploring', 0.044), ('subgraph', 0.043), ('neighbouring', 0.043), ('firstly', 0.043), ('affinity', 0.042), ('neighbours', 0.042), ('cecs', 0.042), ('updating', 0.041), ('match', 0.041), ('eliminates', 0.041), ('combinatorial', 0.041), ('candidate', 0.041), ('false', 0.038), ('denoting', 0.038), ('might', 0.038), ('symmetric', 0.037), ('precision', 0.036), ('pagerank', 0.036), ('integer', 0.036), ('affine', 0.035), ('clutter', 0.035), ('traversing', 0.035), ('smoothness', 0.035), ('smoothly', 0.034), ('log', 0.034), ('traversal', 0.033), ('nature', 0.033), ('detects', 0.033), ('recall', 0.032), ('graphs', 0.032), ('removes', 0.032), ('black', 0.032), ('pg', 0.031), ('personalized', 0.031), ('shifts', 0.031), ('clustering', 0.031), ('ensures', 0.03), ('linkage', 0.029), ('shrinking', 0.029), ('mode', 0.029), ('challenges', 0.028), ('smooth', 0.028), ('covers', 0.028), ('lots', 0.028), ('aside', 0.028), ('harris', 0.028), ('secondly', 0.027), ('tgh', 0.027), ('iterating', 0.027), ('lines', 0.027), ('association', 0.027), ('result', 0.027), ('geometric', 0.027), ('tends', 0.026), ('clean', 0.026), ('orthogonal', 0.026), ('correspondences', 0.026), ('transformations', 0.026), ('neighbour', 0.026), ('leordeanu', 0.026), ('objective', 0.026), ('unified', 0.025), ('refines', 0.025)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999952 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.
2 0.27269381 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.
3 0.23338036 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.
4 0.19137105 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
Author: Yi Wu, Yoshihisa Ijiri, Ming-Hsuan Yang
Abstract: Detecting and registering nonrigid surfaces are two important research problems for computer vision. Much work has been done with the assumption that there exists only one instance in the image. In this work, we propose an algorithm that detects and registers multiple nonrigid instances of given objects in a cluttered image. Specifically, after we use low level feature points to obtain the initial matches between templates and the input image, a novel high-order affinity graph is constructed to model the consistency of local topology. A hierarchical clustering approach is then used to locate the nonrigid surfaces. To remove the outliers in the cluster, we propose a deterministic annealing approach based on the Thin Plate Spline (TPS) model. The proposed method achieves high accuracy even when the number of outliers is nineteen times larger than the inliers. As the matches may appear sparsely in each instance, we propose a TPS based match growing approach to propagate the matches. Finally, an approach that fuses feature and appearance information is proposed to register each nonrigid surface. Extensive experiments and evaluations demonstrate that the proposed algorithm achieves promis- ing results in detecting and registering multiple non-rigid surfaces in a cluttered scene.
5 0.16586131 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.16296339 81 iccv-2013-Combining the Right Features for Complex Event Recognition
7 0.14693122 12 iccv-2013-A General Dense Image Matching Framework Combining Direct and Feature-Based Costs
8 0.13282779 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
9 0.13211168 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
10 0.1231102 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
11 0.12297975 140 iccv-2013-Elastic Net Constraints for Shape Matching
12 0.12217275 11 iccv-2013-A Fully Hierarchical Approach for Finding Correspondences in Non-rigid Shapes
13 0.12049212 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
14 0.11503514 105 iccv-2013-DeepFlow: Large Displacement Optical Flow with Deep Matching
15 0.10736759 24 iccv-2013-A Non-parametric Bayesian Network Prior of Human Pose
16 0.10481223 256 iccv-2013-Locally Affine Sparse-to-Dense Matching for Motion and Occlusion Estimation
17 0.097844228 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
18 0.087599352 75 iccv-2013-CoDeL: A Human Co-detection and Labeling Framework
19 0.087467313 117 iccv-2013-Discovering Details and Scene Structure with Hierarchical Iconoid Shift
20 0.08375217 205 iccv-2013-Human Re-identification by Matching Compositional Template with Cluster Sampling
topicId topicWeight
[(0, 0.198), (1, -0.021), (2, -0.012), (3, -0.026), (4, 0.031), (5, 0.078), (6, -0.038), (7, 0.023), (8, 0.106), (9, -0.085), (10, -0.091), (11, 0.023), (12, 0.046), (13, 0.115), (14, 0.143), (15, 0.19), (16, 0.098), (17, -0.019), (18, 0.07), (19, 0.03), (20, -0.029), (21, 0.075), (22, -0.026), (23, 0.032), (24, 0.257), (25, -0.075), (26, -0.131), (27, 0.061), (28, -0.035), (29, -0.01), (30, 0.159), (31, 0.055), (32, 0.104), (33, -0.032), (34, -0.007), (35, 0.041), (36, 0.1), (37, -0.064), (38, -0.049), (39, 0.02), (40, 0.003), (41, 0.024), (42, 0.006), (43, -0.031), (44, 0.001), (45, 0.047), (46, -0.008), (47, -0.015), (48, 0.054), (49, 0.042)]
simIndex simValue paperId paperTitle
same-paper 1 0.99127913 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.
2 0.96249622 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
3 0.89994115 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.
4 0.89683348 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.72006392 11 iccv-2013-A Fully Hierarchical Approach for Finding Correspondences in Non-rigid Shapes
Author: Ivan Sipiran, Benjamin Bustos
Abstract: This paper presents a hierarchical method for finding correspondences in non-rigid shapes. We propose a new representation for 3D meshes: the decomposition tree. This structure characterizes the recursive decomposition process of a mesh into regions of interest and keypoints. The internal nodes contain regions of interest (which may be recursively decomposed) and the leaf nodes contain the keypoints to be matched. We also propose a hierarchical matching algorithm that performs in a level-wise manner. The matching process is guided by the similarity between regions in high levels of the tree, until reaching the keypoints stored in the leaves. This allows us to reduce the search space of correspondences, making also the matching process efficient. We evaluate the effectiveness of our approach using the SHREC’2010 robust correspondence benchmark. In addition, we show that our results outperform the state of the art.
6 0.68697304 81 iccv-2013-Combining the Right Features for Complex Event Recognition
7 0.66908509 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
8 0.65974683 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
9 0.64548975 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
10 0.57950205 205 iccv-2013-Human Re-identification by Matching Compositional Template with Cluster Sampling
11 0.57084197 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
12 0.56983459 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
13 0.566679 324 iccv-2013-Potts Model, Parametric Maxflow and K-Submodular Functions
14 0.56142586 140 iccv-2013-Elastic Net Constraints for Shape Matching
15 0.5585925 313 iccv-2013-Person Re-identification by Salience Matching
16 0.5508163 117 iccv-2013-Discovering Details and Scene Structure with Hierarchical Iconoid Shift
17 0.54739052 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
18 0.53372341 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
19 0.53370172 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
20 0.52967739 255 iccv-2013-Local Signal Equalization for Correspondence Matching
topicId topicWeight
[(2, 0.431), (7, 0.019), (26, 0.042), (31, 0.027), (42, 0.083), (64, 0.025), (73, 0.051), (89, 0.211), (95, 0.015)]
simIndex simValue paperId paperTitle
1 0.97720122 13 iccv-2013-A General Two-Step Approach to Learning-Based Hashing
Author: Guosheng Lin, Chunhua Shen, David Suter, Anton van_den_Hengel
Abstract: Most existing approaches to hashing apply a single form of hash function, and an optimization process which is typically deeply coupled to this specific form. This tight coupling restricts the flexibility of the method to respond to the data, and can result in complex optimization problems that are difficult to solve. Here we propose a flexible yet simple framework that is able to accommodate different types of loss functions and hash functions. This framework allows a number of existing approaches to hashing to be placed in context, and simplifies the development of new problemspecific hashing methods. Our framework decomposes the hashing learning problem into two steps: hash bit learning and hash function learning based on the learned bits. The first step can typically be formulated as binary quadratic problems, and the second step can be accomplished by training standard binary classifiers. Both problems have been extensively studied in the literature. Our extensive experiments demonstrate that the proposed framework is effective, flexible and outperforms the state-of-the-art.
2 0.9702723 294 iccv-2013-Offline Mobile Instance Retrieval with a Small Memory Footprint
Author: Jayaguru Panda, Michael S. Brown, C.V. Jawahar
Abstract: Existing mobile image instance retrieval applications assume a network-based usage where image features are sent to a server to query an online visual database. In this scenario, there are no restrictions on the size of the visual database. This paper, however, examines how to perform this same task offline, where the entire visual index must reside on the mobile device itself within a small memory footprint. Such solutions have applications on location recognition and product recognition. Mobile instance retrieval requires a significant reduction in the visual index size. To achieve this, we describe a set of strategies that can reduce the visual index up to 60-80 compared to a scatannd raerddu iens tthaen vceis rueatrli ienvdaelx xim upple tom 6en0t-8at0io ×n found on ddte osk atops or servers. While our proposed reduction steps affect the overall mean Average Precision (mAP), they are able to maintain a good Precision for the top K results (PK). We argue that for such offline application, maintaining a good PK is sufficient. The effectiveness of this approach is demonstrated on several standard databases. A working application designed for a remote historical site is also presented. This application is able to reduce an 50,000 image index structure to 25 MBs while providing a precision of 97% for P10 and 100% for P1.
3 0.94792461 352 iccv-2013-Revisiting Example Dependent Cost-Sensitive Learning with Decision Trees
Author: Oisin Mac Aodha, Gabriel J. Brostow
Abstract: Typical approaches to classification treat class labels as disjoint. For each training example, it is assumed that there is only one class label that correctly describes it, and that all other labels are equally bad. We know however, that good and bad labels are too simplistic in many scenarios, hurting accuracy. In the realm of example dependent costsensitive learning, each label is instead a vector representing a data point’s affinity for each of the classes. At test time, our goal is not to minimize the misclassification rate, but to maximize that affinity. We propose a novel example dependent cost-sensitive impurity measure for decision trees. Our experiments show that this new impurity measure improves test performance while still retaining the fast test times of standard classification trees. We compare our approach to classification trees and other cost-sensitive methods on three computer vision problems, tracking, descriptor matching, and optical flow, and show improvements in all three domains.
4 0.94702411 446 iccv-2013-Visual Semantic Complex Network for Web Images
Author: Shi Qiu, Xiaogang Wang, Xiaoou Tang
Abstract: This paper proposes modeling the complex web image collections with an automatically generated graph structure called visual semantic complex network (VSCN). The nodes on this complex network are clusters of images with both visual and semantic consistency, called semantic concepts. These nodes are connected based on the visual and semantic correlations. Our VSCN with 33, 240 concepts is generated from a collection of 10 million web images. 1 A great deal of valuable information on the structures of the web image collections can be revealed by exploring the VSCN, such as the small-world behavior, concept community, indegree distribution, hubs, and isolated concepts. It not only helps us better understand the web image collections at a macroscopic level, but also has many important practical applications. This paper presents two application examples: content-based image retrieval and image browsing. Experimental results show that the VSCN leads to significant improvement on both the precision of image retrieval (over 200%) and user experience for image browsing.
5 0.93603313 191 iccv-2013-Handling Uncertain Tags in Visual Recognition
Author: Arash Vahdat, Greg Mori
Abstract: Gathering accurate training data for recognizing a set of attributes or tags on images or videos is a challenge. Obtaining labels via manual effort or from weakly-supervised data typically results in noisy training labels. We develop the FlipSVM, a novel algorithm for handling these noisy, structured labels. The FlipSVM models label noise by “flipping ” labels on training examples. We show empirically that the FlipSVM is effective on images-and-attributes and video tagging datasets.
same-paper 6 0.93282908 214 iccv-2013-Improving Graph Matching via Density Maximization
7 0.91939485 244 iccv-2013-Learning View-Invariant Sparse Representations for Cross-View Action Recognition
8 0.90008044 374 iccv-2013-Salient Region Detection by UFO: Uniqueness, Focusness and Objectness
9 0.84732121 239 iccv-2013-Learning Hash Codes with Listwise Supervision
10 0.83475524 322 iccv-2013-Pose Estimation and Segmentation of People in 3D Movies
11 0.83438522 409 iccv-2013-Supervised Binary Hash Code Learning with Jensen Shannon Divergence
12 0.82692009 153 iccv-2013-Face Recognition Using Face Patch Networks
13 0.82664216 83 iccv-2013-Complementary Projection Hashing
14 0.82388657 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
15 0.78452563 313 iccv-2013-Person Re-identification by Salience Matching
16 0.78272659 368 iccv-2013-SYM-FISH: A Symmetry-Aware Flip Invariant Sketch Histogram Shape Descriptor
17 0.78218913 248 iccv-2013-Learning to Rank Using Privileged Information
18 0.76832795 378 iccv-2013-Semantic-Aware Co-indexing for Image Retrieval
19 0.76706856 443 iccv-2013-Video Synopsis by Heterogeneous Multi-source Correlation
20 0.76630008 419 iccv-2013-To Aggregate or Not to aggregate: Selective Match Kernels for Image Search