iccv iccv2013 iccv2013-224 knowledge-graph by maker-knowledge-mining
Source: pdf
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
Reference: text
sentIndex sentText sentNum sentScore
1 Joint optimization for consistent multiple graph matching Junchi Yan∗ Shanghai Jiao Tong University IBM Research - China yan j unchi @ s j tu . [sent-1, score-0.325]
2 cn 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. [sent-7, score-0.405]
3 A more general and challenging problem arises when one aims to find consistent mappings across a number of graphs more than two. [sent-8, score-0.216]
4 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. [sent-9, score-0.837]
5 The problem of graph matching is to establish a consistent mapping between the nodes of two or more graphs. [sent-26, score-0.368]
6 Graph matching is typically and mostly considered under the two-graph scenario, and has been explored in a variety of tasks such as feature tracking, image retrieval, object recognition, and shape matching [9]. [sent-29, score-0.268]
7 For instance, object matching can be regarded as finding consistent correspondences between two sets of features, by maximizing the fitness regarding the unary and edge similarities in two graphs. [sent-30, score-0.173]
8 In this setting, the problem can be formulated as graph matching that aims to find a point-to-point mapping that preserves as much as possible the relationships between nodes. [sent-31, score-0.368]
9 To address the multi11664499 ple graph matching problem, a simple strategy could be applying the state-of-the-art two-graph matching algorithms on each graph pair individually and independently: for instance, given graph Ga, Gb and Gc, firstly one can apply the pair matching solver e. [sent-35, score-1.113]
10 [3, 21] to find the node mapping Xab, Xbc respectively, and then obtain the mapping Xac induced by the intermediate graph Gb. [sent-37, score-0.336]
11 One obvious weakness is the affinity measurement between Ga and Gc is ignored, which might be more accurate than the defined affinity between Ga-Gb and Gb-Gc especially in case Gb is heavily corrupted. [sent-38, score-0.248]
12 On the other hand, applying pair match solver between individual Ga and Gc is likely to generate inconsistent or redundant matching solutions compared with the mapping induced by Xab, Xbc, especially given large number of nodes or significant corruption. [sent-39, score-0.378]
13 Aiming at addressing these challenges, we make the following main contributions in theory and algorithm: 1) We derive the original objective formulation into a new one where the redundant mapping variables are compactly represented by the set of basis mapping variables. [sent-40, score-0.223]
14 This formulation mathematically ensures the mapping constraints and allows for joint pair mappings optimization, mixing the local and the global affinity information. [sent-42, score-0.345]
15 Its robustness against noise and local distortion are indicated in the experiments; 2) Using the derived formulation, we propose an alternating optimization method which allows reusing any of the existing pair matching solvers. [sent-43, score-0.28]
16 Related work A myriad of methods have been proposed for graph matching. [sent-46, score-0.169]
17 Most approaches address the graph matching problem in the context of finding correspondence between a pair of graphs, for which an incomplete list is as follows: [14] formulate graph matching as a constrained integer quadratic programming (IQP) problem with a concave optimization scheme. [sent-47, score-0.711]
18 [20] extended SM to Spectral Matching with Affine Constraint (SMAC) by introducing affine constraints into the spectral decomposition that encodes the one-to-one matching constraints. [sent-51, score-0.163]
19 Recently, [13] showed point matching capable of handling significant affine or similarity transformation can be formulated as an IQP problem which also appeared in graph matching Beyond the second order edge affinity, recent work explore the graph structure by hyper-edges, e. [sent-52, score-0.645]
20 Another research thread in parallel is focusing on learning the affinity matrix (or tensor in the hyper graph case) for graph matching [2, 6, 11] etc. [sent-55, score-0.596]
21 While this paper focuses on the optimization framework, rather than how come from the affinity information (learning or learningfree); or to what extend the affinity information is explored (edge or hyper-edge). [sent-56, score-0.248]
22 One limitation of the aforementioned approaches is that the matching is conducted under a graph pair, rather than an arbitrary number of graphs jointly and consistently. [sent-58, score-0.48]
23 Specifically, [25] synthesizes an ensemble of attributed graphs into the distribution of a random graph and further classify the query graph to a certain category. [sent-62, score-0.557]
24 By using the second order information, [16] extend the first order random graphs (FORGs) [25] to the second-order random graphs (SORGs) for graph clustering and recognition. [sent-63, score-0.523]
25 [1] propose an unsupervised learning method for graphs clustering and median graph building based on a set ofgraphs. [sent-64, score-0.346]
26 These works are all based on graph pair matching as the similarity metric, and share the common weakness that the local matching error taken at initial stages might propagate and lead to bad global results. [sent-65, score-0.518]
27 Compared with the pair matching problem, the multiple graph matching has not been intensively studied by the community, and only a few address this problem using principled optimization. [sent-66, score-0.518]
28 The proof-of-concept (as claimed in the paper by the authors) [24] provide a Bayesian view to extend the matching graph pairs to multiple ones, but no solver is proposed. [sent-67, score-0.345]
29 Using the generalized softassign algorithm, [18] substitute the assignation matrices associated with each graph pair by an assignation hypercube. [sent-68, score-0.351]
30 A more recent state-of-the-art [19] is the extension and improvement of [18]: hypercube is first obtained by pair isomorphism, and then a clean-up step is performed to enforce the mapping consistency. [sent-71, score-0.21]
31 How11665500 ever, none of the previous work has shown how the multiple graph matching formulation can be back transformed into a pair matching problem in its IQP formulation, both algorithmically and mathematically. [sent-73, score-0.554]
32 To our best knowledge, this is the first work on extending the IQP formulation for pair matching to multiple ones. [sent-74, score-0.251]
33 Our novel formulation explores the global affinity and unveil the underlying connection with pair matching. [sent-75, score-0.241]
34 Graph pair matching First we briefly introduce the widely used formulation of pair graph matching. [sent-80, score-0.501]
35 Concretely, given two graphs GL(VL, EL, AL) and GR(VR, ER, AR), where V denotes nodes, E, edges and A, attributes, there is an affinity matrix defined as Mia;jb that measures the affinity with the candidate edge pair (vLi, vjL) vs. [sent-81, score-0.545]
36 And the diagonal term Mia;ia describes the unary affinity of a node match (vLi , vaR). [sent-83, score-0.161]
37 Ap = 1 p ∈ {0, 1} (1) here x is the vectorized permutation matrix, and Ax=1 refers to the one-to-one node mapping constraint for two graphs. [sent-86, score-0.159]
38 Multiple graph matching Given N graphs and the associated affinity matrix Mij , a natural extension for multi-graph matching is: P∗ = ? [sent-89, score-0.738]
39 And λ is the weight for each pair matching score. [sent-108, score-0.215]
40 The above formulation tells that optimizing pij, pjk and xik could not guarantee the consistency between pik and the mapping induced by the chain pij, pjk - see Fig. [sent-109, score-0.234]
41 Even knowing the explicit constraints as will be shown in the rest of this paper, we stillneed new algorithms to solve this problem as it might be different from the conventional pair matching problem. [sent-112, score-0.215]
42 Proposed framework and algorithm Given a graph set with more than two graphs, we are interested in finding their node mapping among the graphs. [sent-115, score-0.271]
43 Directly applying the existing pairwise matching meth- ods will sequentially match the graphs by pair and a local matching mistake between two graphs may propagate along the matching chain to deteriorate the overall performance. [sent-116, score-0.863]
44 Thus we are motivated to design a principled multiple graph matching framework in nature, and furthermore, to explore the possibility of reusing the resource of the off-the-shelf pairwise matching solvers. [sent-117, score-0.46]
45 For clarity reason, the following mathematical derivations will specifically focus on the triple-view graph matching scenario, while it should be noted the formulation can be readily extended to any number of graphs - this will be discussed shortly after the illustration of triple case. [sent-121, score-0.516]
46 Given three graphs Ga, Gb, Gc, let pab, pac, pbc denote the matching correspondences mapping between view pair {Ga, Gb}, {Ga, Gc} and {Gb, Gc}, respectively. [sent-122, score-0.786]
47 In particular, we are interested in how to formulate the triple-view graph matching problem in a unified optimization framework, and preferably, the pairwise matching techniques can be reused. [sent-123, score-0.437]
48 In this way, the correspondences between view b and view c can be determined from the known mapping between pair ab and pair ac: pbc=? [sent-144, score-0.227]
49 In what follows, we show how to obtain pbc when given pab and pac, respectively. [sent-153, score-0.799]
50 Still in the context of four-point graph matching, first define the matrix Q41 as follows: AndQw4e1h=a⎣⎢v ⎡⎢e:01,Q0 4, 01p,0a,b. [sent-155, score-0.169]
51 1 In general, for N node graph, we have: N pbc = ? [sent-175, score-0.366]
52 1 We have shown pbc can be analytically derived from pab and pac. [sent-178, score-0.799]
53 And triple-view matching objective can be written: maxpaTbMabpab + paTcMacpac + pbTcMbcpbc (9) 1When the number of nodes are different in two graphs, one can add dummy nodes or introduce slack variables as done in [7]. [sent-179, score-0.161]
54 Then we address how to formulate pbTcMbcpbc using pab and pac while keeping its IQP formulation. [sent-186, score-0.804]
55 w Neo stheow on heo cwan to re rveperlasece p tbThceM tbecrpmbc inincltuod pincTgbM pbc bpucsb- without changing the property of the objective function 9, which allows for the following reformulation by replacing pcb with pab: N2 paTbMabpab + paTcMacpac + ? [sent-229, score-0.329]
56 pbc are redundant in determining the two mapping relation among three graphs. [sent-238, score-0.424]
57 This also poses the gap for direct applying of the conventional pair matching methods. [sent-239, score-0.243]
58 The above derivation has shown how to replace the redundant variable pbc in Eq. [sent-240, score-0.359]
59 11665522 Algorithm 1 Alternating optimization for graph Ga,Gb,Gc Input: affinity matrix Mab,Mbc, Mac; Output: consistent mappings pab, pbc, pac Initial: k = 0; pa0b = pb0c = = [n12 , . [sent-244, score-0.666]
60 g2 (16) if Δab < ε, Δac < ε: stop end while Calculate pbc by pab and pac using Eq. [sent-251, score-1.133]
61 Alternating optimization algorithm In terms of the proposed framework, we design our optimization algorithm by iterating with respect to pab and pac alternatively, and fixing the other meanwhile. [sent-255, score-0.804]
62 14, one can fix the updated pakc and renew pakb via optimizing: mpakabxpakbT[Mab+i,? [sent-258, score-0.182]
63 Nj=21piakcpajckMbQc(i,j)]pakb (16) By doing so, we update both pakb and pakc in the k-the iteration. [sent-259, score-0.156]
64 16 are both IQP problem, which can be solved by current pair graph matching techniques ‘out-of-the-box’ . [sent-262, score-0.384]
65 Any pair matching solver can be performed for alternating updating. [sent-265, score-0.299]
66 From triple-graph to N-graph Now we address the problem raised in the beginning for how to generalize to any-order of multiple graph matching. [sent-274, score-0.169]
67 Observing the fact from the triple matching model that pbc can be represented by pab and pac. [sent-275, score-0.933]
68 a set of 4 graphs a, b, c, d, the pairwise matching correspondences pbc, pbd, pcd can be represented by Algorithm 2 Alternating optimization for N-graph Input: affinity matrix MG1G2 ,MG2G3 ,. [sent-278, score-0.466]
69 This observation is important to the computational extensibility of our framework in that as the number of graph increases, the total computational overhead grows in a linear proportion due to each of the m 1variables is iteratively updated by turn. [sent-322, score-0.169]
70 And the N-view graph − matching algorithm is summarized in Alg. [sent-324, score-0.303]
71 In summary, we derive a framework for multiple graph matching, where the variables are optimized jointly and the consistency is always satisfied. [sent-326, score-0.196]
72 In each iteration, we cast the objective function into an IQP that can be solved by any pair matching techniques. [sent-327, score-0.215]
73 Protocol on simulation tests In terms of experimental protocol for graph matching, the online available [3, 8] has been recognized as a baseline evaluation. [sent-332, score-0.169]
74 For each trial in all random graph experiments, the same affinity matrix was shared as the input for the testing algorithms. [sent-337, score-0.293]
75 We build three graphs Ga, Gb and Gc with nin inliers, optional nout outliers and the edges with a density controlled by parameter ρ as the same in [3]. [sent-338, score-0.201]
76 For graph Ga, each edge’s attribute diaj is assigned by a random value uniformly sampled from [0,1], and the perturbed graph Gb and Gc are created by adding a Gaussian deformation noise ε sampled from N(0, σ2) to diaj i. [sent-339, score-0.541]
77 = diaj+εC where C is the average of all diaj in graph Ga. [sent-341, score-0.247]
78 /σs2) where ij is the edge between node iand j in one graph and xy is the edge between node x and y in the other graph. [sent-344, score-0.321]
79 4 for both three-graph matching and four-graph, especially the disturbance is significant. [sent-365, score-0.162]
80 In our analysis, this might be due to that as graphs are corrupted, the associated local affinity matrix is misleading and makes the individual matching ppair inaccurate (although being an optimum in score). [sent-366, score-0.466]
81 642130CPMuabi3lr4etG i A G 3 M8 42650 sequencegap (d) Accuracy of pab sequencegap (e) Accuracy of pac sequencegap (f) Accuracy of pbc ScAoBer0 8. [sent-372, score-1.415]
82 30CPMua3bi4lretG i A G3 8GM 42650 sequencegap sequencegap sequencegap (g) Score of pab (h) Score of pac (i) Score of pbc Figure 2: Performance evaluation on CMU hotel sequence dataset with increasing frame gap. [sent-378, score-1.441]
83 Delaunay triangulation is used for graph construction on each raw image as exemplified in the left top sub-graph. [sent-379, score-0.169]
84 GAGM [7] is adopted as the solver for pairwise graph matching. [sent-380, score-0.211]
85 As a result, it jointly optimizes the mapping variables by simultaneously exploring the affinity matrix across pairs, and become less sensitive to the local noise. [sent-382, score-0.216]
86 Due to the space limitation, in this paper we only provide the results using IPFP as the black-box pair matching solver. [sent-384, score-0.215]
87 Individual pair matching is inconsistent: Table 1 shows the counts of the trials when Eq. [sent-385, score-0.256]
88 As the disturbance grows, it becomes more difficult for the individual two-view matching solutions papacir, to satisfy the establishment of Eq. [sent-388, score-0.162]
89 1 ratoiFill ratoiFill Figure 3: Performance evaluation for matching three synthetic graphs by varying deformation, outlier #, and edge density: average and deviation of accuracy and score out of 30 random trials. [sent-533, score-0.419]
90 Row 1: accuracy and score of pab; Row 2: accuracy and score of pac; Row 3: accuracy and score of pab; Row 4: accuracy and score of mean of pab,pac,pbc. [sent-534, score-0.176]
91 Given frame t for the first graph, the other two graphs are selected from frame t 0. [sent-544, score-0.177]
92 5 ∗ gap such that the average sequence gap between two graphs is gap. [sent-546, score-0.233]
93 Conclusion We propose a novel formulation for robust and consistent multiple graph matching. [sent-548, score-0.205]
94 The merits lie in the extension of the conventional pair matching formulation, and seamless reuse of existing pair matching solvers. [sent-549, score-0.43]
95 An integer projected fixed point method for graph matching and map inference. [sent-616, score-0.327]
96 Second-order random graphs for modeling sets of attributed graphs and their application to object learning and recognition. [sent-654, score-0.396]
97 Function-described graphs for modeling objects represented by attributed graphs. [sent-660, score-0.219]
98 1 ratoiFill ratoiFill Figure 4: Performance evaluation for matching four synthetic graphs by varying deformation, outlier #, and edge density: average and deviation of accuracy and score out of 30 random trials. [sent-852, score-0.419]
99 Row 1: accuracy and score of pab; Row 2: accuracy and score of pac; Row 3: accuracy and score of pbc; Row 4: accuracy and score of pad; Row 5: accuracy and score of pbd; Row 6: accuracy and score of pcd; Row 7: accuracy and score of mean of pab,pac,pbc,pbc,pbd,pcd. [sent-853, score-0.308]
100 Feature correspondence via graph matching: Models and global optimization. [sent-901, score-0.169]
wordName wordTfidf (topN-words)
[('pab', 0.47), ('ratoifill', 0.345), ('pac', 0.334), ('pbc', 0.329), ('qni', 0.282), ('graphs', 0.177), ('graph', 0.169), ('matching', 0.134), ('iqp', 0.129), ('affinity', 0.124), ('cubeipfp', 0.11), ('noulteir', 0.11), ('deformaiton', 0.094), ('sequencegap', 0.094), ('shanghai', 0.085), ('pair', 0.081), ('diaj', 0.078), ('pakb', 0.078), ('pakc', 0.078), ('qnipab', 0.078), ('qnipac', 0.078), ('gc', 0.07), ('mapping', 0.065), ('hypercube', 0.064), ('ipfp', 0.064), ('bilretiip', 0.063), ('mbqc', 0.063), ('mulitipfp', 0.063), ('tmbc', 0.063), ('ga', 0.059), ('pij', 0.052), ('jiao', 0.048), ('pad', 0.048), ('gb', 0.047), ('deformation', 0.047), ('cyaua', 0.047), ('multiipfp', 0.047), ('pbtcmbcpbc', 0.047), ('rblietpii', 0.047), ('score', 0.044), ('attributed', 0.042), ('pf', 0.042), ('solver', 0.042), ('alternating', 0.042), ('pjk', 0.042), ('trials', 0.041), ('edge', 0.039), ('mappings', 0.039), ('softassign', 0.039), ('node', 0.037), ('formulation', 0.036), ('transaction', 0.036), ('leordeanu', 0.034), ('tong', 0.033), ('permutation', 0.033), ('labelling', 0.032), ('alqu', 0.031), ('assignation', 0.031), ('gbrpr', 0.031), ('pariipfp', 0.031), ('patbmabpab', 0.031), ('patcmacpac', 0.031), ('pbd', 0.031), ('pcd', 0.031), ('piabpjabpatcmbqc', 0.031), ('pkg', 0.031), ('ppair', 0.031), ('rblietpiifp', 0.031), ('serratosa', 0.031), ('xab', 0.031), ('xbc', 0.031), ('ycauc', 0.031), ('redundant', 0.03), ('ibm', 0.03), ('spectral', 0.029), ('gap', 0.028), ('vli', 0.028), ('disturbance', 0.028), ('gagm', 0.028), ('variables', 0.027), ('fp', 0.027), ('chain', 0.026), ('fix', 0.026), ('inconsistent', 0.026), ('graduated', 0.026), ('hotel', 0.026), ('outlier', 0.025), ('mia', 0.024), ('tuples', 0.024), ('ijprai', 0.024), ('pia', 0.024), ('vectorized', 0.024), ('integer', 0.024), ('density', 0.024), ('reusing', 0.023), ('pik', 0.023), ('iteration', 0.022), ('mac', 0.022), ('delaunay', 0.022), ('tu', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 1.0 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
2 0.20360768 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.17048457 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.16586131 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.087623537 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
Author: Ling Wang, Hichem Sahbi
Abstract: One of the trends of action recognition consists in extracting and comparing mid-level features which encode visual and motion aspects of objects into scenes. However, when scenes contain high-level semantic actions with many interacting parts, these mid-level features are not sufficient to capture high level structures as well as high order causal relationships between moving objects resulting into a clear drop in performances. In this paper, we address this issue and we propose an alternative action recognition method based on a novel graph kernel. In the main contributions of this work, we first describe actions in videos using directed acyclic graphs (DAGs), that naturally encode pairwise interactions between moving object parts, and then we compare these DAGs by analyzing the spectrum of their sub-patterns that capture complex higher order interactions. This extraction and comparison process is computationally tractable, re- sulting from the acyclic property of DAGs, and it also defines a positive semi-definite kernel. When plugging the latter into support vector machines, we obtain an action recognition algorithm that overtakes related work, including graph-based methods, on a standard evaluation dataset.
6 0.085722931 120 iccv-2013-Discriminative Label Propagation for Multi-object Tracking with Sporadic Appearance Features
7 0.071034215 81 iccv-2013-Combining the Right Features for Complex Event Recognition
8 0.067233138 140 iccv-2013-Elastic Net Constraints for Shape Matching
9 0.063372478 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
10 0.058373127 448 iccv-2013-Weakly Supervised Learning of Image Partitioning Using Decision Trees with Structured Split Criteria
11 0.056749769 296 iccv-2013-On the Mean Curvature Flow on Graphs with Applications in Image and Manifold Processing
12 0.055471569 445 iccv-2013-Visual Reranking through Weakly Supervised Multi-graph Learning
13 0.05488544 256 iccv-2013-Locally Affine Sparse-to-Dense Matching for Motion and Occlusion Estimation
14 0.05460522 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
15 0.051380459 105 iccv-2013-DeepFlow: Large Displacement Optical Flow with Deep Matching
16 0.043908771 196 iccv-2013-Hierarchical Data-Driven Descent for Efficient Optimal Deformation Estimation
17 0.043262426 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
18 0.042659838 429 iccv-2013-Tree Shape Priors with Connectivity Constraints Using Convex Relaxation on General Graphs
19 0.041838903 437 iccv-2013-Unsupervised Random Forest Manifold Alignment for Lipreading
20 0.04151731 184 iccv-2013-Global Fusion of Relative Motions for Robust, Accurate and Scalable Structure from Motion
topicId topicWeight
[(0, 0.11), (1, -0.012), (2, -0.02), (3, -0.018), (4, 0.003), (5, 0.051), (6, -0.022), (7, 0.013), (8, 0.076), (9, -0.04), (10, -0.064), (11, 0.027), (12, -0.004), (13, 0.077), (14, 0.104), (15, 0.121), (16, 0.063), (17, 0.001), (18, 0.021), (19, 0.02), (20, -0.017), (21, 0.049), (22, -0.035), (23, 0.009), (24, 0.16), (25, -0.023), (26, -0.093), (27, 0.041), (28, -0.008), (29, 0.014), (30, 0.081), (31, 0.066), (32, 0.076), (33, -0.02), (34, 0.007), (35, 0.049), (36, 0.055), (37, -0.046), (38, -0.059), (39, 0.052), (40, 0.035), (41, -0.016), (42, -0.021), (43, -0.015), (44, -0.004), (45, 0.039), (46, -0.004), (47, -0.002), (48, 0.038), (49, 0.057)]
simIndex simValue paperId paperTitle
same-paper 1 0.97997403 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
2 0.95445973 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.
3 0.9096337 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.
4 0.89445728 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.
5 0.69275546 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.64896971 81 iccv-2013-Combining the Right Features for Complex Event Recognition
7 0.60477668 11 iccv-2013-A Fully Hierarchical Approach for Finding Correspondences in Non-rigid Shapes
8 0.59060109 283 iccv-2013-Multiple Non-rigid Surface Detection and Registration
9 0.58919489 290 iccv-2013-New Graph Structured Sparsity Model for Multi-label Image Annotations
10 0.57161719 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
11 0.54250747 324 iccv-2013-Potts Model, Parametric Maxflow and K-Submodular Functions
12 0.53832459 131 iccv-2013-EVSAC: Accelerating Hypotheses Generation by Modeling Matching Scores with Extreme Value Theory
13 0.53669149 140 iccv-2013-Elastic Net Constraints for Shape Matching
15 0.51530993 205 iccv-2013-Human Re-identification by Matching Compositional Template with Cluster Sampling
16 0.49532375 159 iccv-2013-Fast Neighborhood Graph Search Using Cartesian Concatenation
17 0.48866826 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
18 0.48190051 313 iccv-2013-Person Re-identification by Salience Matching
19 0.47813007 117 iccv-2013-Discovering Details and Scene Structure with Hierarchical Iconoid Shift
20 0.46794724 167 iccv-2013-Finding Causal Interactions in Video Sequences
topicId topicWeight
[(2, 0.095), (7, 0.019), (19, 0.011), (26, 0.043), (31, 0.035), (42, 0.073), (55, 0.368), (64, 0.026), (73, 0.031), (78, 0.016), (89, 0.121), (95, 0.037)]
simIndex simValue paperId paperTitle
same-paper 1 0.67942882 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
2 0.56929296 406 iccv-2013-Style-Aware Mid-level Representation for Discovering Visual Connections in Space and Time
Author: Yong Jae Lee, Alexei A. Efros, Martial Hebert
Abstract: We present a weakly-supervised visual data mining approach that discovers connections between recurring midlevel visual elements in historic (temporal) and geographic (spatial) image collections, and attempts to capture the underlying visual style. In contrast to existing discovery methods that mine for patterns that remain visually consistent throughout the dataset, our goal is to discover visual elements whose appearance changes due to change in time or location; i.e., exhibit consistent stylistic variations across the label space (date or geo-location). To discover these elements, we first identify groups of patches that are stylesensitive. We then incrementally build correspondences to find the same element across the entire dataset. Finally, we train style-aware regressors that model each element’s range of stylistic differences. We apply our approach to date and geo-location prediction and show substantial improvement over several baselines that do not model visual style. We also demonstrate the method’s effectiveness on the related task of fine-grained classification.
3 0.56043959 32 iccv-2013-A Unified Rolling Shutter and Motion Blur Model for 3D Visual Registration
Author: Maxime Meilland, Tom Drummond, Andrew I. Comport
Abstract: Motion blur and rolling shutter deformations both inhibit visual motion registration, whether it be due to a moving sensor or a moving target. Whilst both deformations exist simultaneously, no models have been proposed to handle them together. Furthermore, neither deformation has been consideredpreviously in the context of monocularfullimage 6 degrees of freedom registration or RGB-D structure and motion. As will be shown, rolling shutter deformation is observed when a camera moves faster than a single pixel in parallax between subsequent scan-lines. Blur is a function of the pixel exposure time and the motion vector. In this paper a complete dense 3D registration model will be derived to accountfor both motion blur and rolling shutter deformations simultaneously. Various approaches will be compared with respect to ground truth and live real-time performance will be demonstratedfor complex scenarios where both blur and shutter deformations are dominant.
4 0.5552572 23 iccv-2013-A New Image Quality Metric for Image Auto-denoising
Author: Xiangfei Kong, Kuan Li, Qingxiong Yang, Liu Wenyin, Ming-Hsuan Yang
Abstract: This paper proposes a new non-reference image quality metric that can be adopted by the state-of-the-art image/video denoising algorithms for auto-denoising. The proposed metric is extremely simple and can be implemented in four lines of Matlab code1. The basic assumption employed by the proposed metric is that the noise should be independent of the original image. A direct measurement of this dependence is, however, impractical due to the relatively low accuracy of existing denoising method. The proposed metric thus aims at maximizing the structure similarity between the input noisy image and the estimated image noise around homogeneous regions and the structure similarity between the input noisy image and the denoised image around highly-structured regions, and is computed as the linear correlation coefficient of the two corresponding structure similarity maps. Numerous experimental results demonstrate that the proposed metric not only outperforms the current state-of-the-art non-reference quality metric quantitatively and qualitatively, but also better maintains temporal coherence when used for video denoising. ˜
5 0.55234396 183 iccv-2013-Geometric Registration Based on Distortion Estimation
Author: Wei Zeng, Mayank Goswami, Feng Luo, Xianfeng Gu
Abstract: Surface registration plays a fundamental role in many applications in computer vision and aims at finding a oneto-one correspondence between surfaces. Conformal mapping based surface registration methods conformally map 2D/3D surfaces onto 2D canonical domains and perform the matching on the 2D plane. This registration framework reduces dimensionality, and the result is intrinsic to Riemannian metric and invariant under isometric deformation. However, conformal mapping will be affected by inconsistent boundaries and non-isometric deformations of surfaces. In this work, we quantify the effects of boundary variation and non-isometric deformation to conformal mappings, and give the theoretical upper bounds for the distortions of conformal mappings under these two factors. Besides giving the thorough theoretical proofs of the theorems, we verified them by concrete experiments using 3D human facial scans with dynamic expressions and varying boundaries. Furthermore, we used the distortion estimates for reducing search range in feature matching of surface registration applications. The experimental results are consistent with the theoreticalpredictions and also demonstrate the performance improvements in feature tracking.
6 0.54770082 312 iccv-2013-Perceptual Fidelity Aware Mean Squared Error
7 0.54425871 363 iccv-2013-Rolling Shutter Stereo
8 0.53633666 226 iccv-2013-Joint Subspace Stabilization for Stereoscopic Video
9 0.49544108 144 iccv-2013-Estimating the 3D Layout of Indoor Scenes and Its Clutter from Depth Sensors
10 0.43887565 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
11 0.43629864 173 iccv-2013-Fluttering Pattern Generation Using Modified Legendre Sequence for Coded Exposure Imaging
12 0.43518344 229 iccv-2013-Large-Scale Video Hashing via Structure Learning
13 0.43358877 239 iccv-2013-Learning Hash Codes with Listwise Supervision
14 0.43261009 374 iccv-2013-Salient Region Detection by UFO: Uniqueness, Focusness and Objectness
15 0.43258411 384 iccv-2013-Semi-supervised Robust Dictionary Learning via Efficient l-Norms Minimization
16 0.43211007 322 iccv-2013-Pose Estimation and Segmentation of People in 3D Movies
17 0.43195546 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
18 0.43149665 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
19 0.43143225 25 iccv-2013-A Novel Earth Mover's Distance Methodology for Image Matching with Gaussian Mixture Models
20 0.43107241 83 iccv-2013-Complementary Projection Hashing