cvpr cvpr2013 cvpr2013-192 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
Reference: text
sentIndex sentText sentNum sentScore
1 edu Abstract In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. [sent-6, score-0.753]
2 Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. [sent-7, score-1.249]
3 In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. [sent-8, score-0.485]
4 Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. [sent-9, score-0.368]
5 Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. [sent-10, score-0.474]
6 Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods. [sent-11, score-0.856]
7 Introduction The exact and approximate graph matching problem is of great interest in computer vision due to its numerous applications in areas such as 2D and 3D image registration, object recognition and biomedical identification, and object tracking in video sequences. [sent-13, score-0.323]
8 Algorithms that can take advantage of this information to infer the correspondences for the rest of the graph nodes are highly desirable. [sent-16, score-0.476]
9 This problem setup, however, is different from our setting where we only have two graphs with partially known correspondences; in a sense, these known correspondences constitute our “training data”. [sent-18, score-0.279]
10 In this work we provide a method for effectively incor- porating known correspondences into the commonly used integer quadratic program formulation of graph matching. [sent-20, score-0.373]
11 Specifically, our main contribution is to devise a new first order compatibility term between two nodes of different graphs. [sent-21, score-0.431]
12 Our method uses the recently proposed oneparameter family of node signatures called Laplacian Family Signatures (LFS) [11], which provide a feature vector (signature) for each node based solely on the node’s structural position within the graph. [sent-22, score-0.661]
13 Since graph matching is performed using the dissimilarity/distance between these signatures, we derive the distance between the generic signatures. [sent-24, score-0.35]
14 As a result of this manipulation, we find that the entire process of computing and comparing these generic signatures can be encoded into a single proximity matrix. [sent-25, score-0.483]
15 We then introduce an algorithm to learn this proximity matrix from the knowledge of provided correct correspondences. [sent-26, score-0.26]
16 This is done by requiring anchor nodes in one graph to correspond near to their known partners in the other and to be far from non-correspondences, which can be set up as a max-margin problem [28]. [sent-27, score-0.718]
17 First, our max-margin formulation makes an effective use of the scarce training data: even a small number of known correspondences (two anchor correspondences are used in all of our experiments) leads to a large number of constraints on the proximity matrix. [sent-29, score-0.707]
18 Second, our formulation results in learning a proximity matrix that is relatively small (tens 222999000644 by tens in the examples shown) which allows us to reliably learn it without over-fitting. [sent-30, score-0.279]
19 Our goal is to find an approximate matching between these two graphs based solely on their structural properties (e. [sent-36, score-0.364]
20 be the subsets of nodes tNhaatm are k lenotw Un ⊂to V be a nind correspondence; we will refer to these as anchor node sets for G and G? [sent-42, score-0.692]
21 We follow the commonly used integer quadratic program (IQP) formulation for the graph matching problem based on two kinds of compatibility terms. [sent-44, score-0.622]
22 The first order compatibility d(i, a) encodes similarity of a node i ∈ V in graph G tboi a yn do(dei, a ∈ e nVco? [sent-45, score-0.519]
23 de Fro compatibility eds( ii,, j,a, bV) measures ∈the V compatibility of matching the node pair (i, j) to node pair (a, b). [sent-50, score-0.836]
24 Our main goal in this paper is to incorporate the knowl- edge of the anchor correspondences into the first order compatibility term which will be expressed as follows: d(i, a) = cBdB(i, a) + capdap(i, a), where cB and cap are some weights. [sent-51, score-0.654]
25 The first term dB (i, a) is based on our formulation of LFS proximity matrix and is presented in Section 3. [sent-52, score-0.259]
26 The construction of the second term dap(i, a) which involves the heat kernel is explained in Section 3. [sent-54, score-0.449]
27 The matching scheme incorporating both the first order and second order compatibility functions is presented in Section 4. [sent-56, score-0.343]
28 Related Work Our family of signatures are closely related to nodebased signatures on graphs, different forms of which has already been considered, e. [sent-59, score-0.605]
29 al [24] proposed the heat kernel signature (HKS) for application of shape matching in geometry processing. [sent-63, score-0.706]
30 Their signature is based on the simulated heat diffusion process on manifold. [sent-64, score-0.546]
31 Among the pioneering work is Umeyama’s [25] weighted graph matching algorithm from a decomposition of adjacency matrices. [sent-70, score-0.461]
32 [20] used the steady state of the Markov transition matrix to order the nodes and match using edit distances. [sent-74, score-0.304]
33 Later in [21], the same authors proposed to use the leading eigenvector of the adjacency matrix to serialize the graph nodes for matching. [sent-75, score-0.591]
34 al [19] considered using the Fiedler vector together with the proximity to the perimeter of the graph to partition the graph into disconnected components for a hierarchical matching. [sent-77, score-0.533]
35 [4] constructed a reweighed random walk similar to personalized PageRank on the association graph with the addition of an absorbing node, and used the quasi-stationary distribution to find a matching. [sent-80, score-0.246]
36 [6] simulated a quantum walk on the auxiliary graph and used the particle probability of each auxiliary node as the cost of assignment for a bipartite matching. [sent-83, score-0.457]
37 Anchor Based Compatibility In this section we discuss the construction and computation of two kinds of first order compatibility terms that take advantage of known correspondences between anchor nodes. [sent-105, score-0.625]
38 The Laplacian Family Signatures (LFS) for a node u ∈ V iTs a one-parameter family onaft sutrreusct (LurFalS n) fodore descriptors that is defined by φk}|kV= |1 su(t) = ? [sent-126, score-0.208]
39 Special h(t; λk) of different forms will result in the heat kernel signature (HKS) [24] when h(t; λk) = exp(−tλk), the wave kernel signature (WKS) [1] when h(t; λk) = or the wavelet signature if h(t; λk) a)d =mit esx some special behavior as described in [10]. [sent-129, score-0.938]
40 These signatures describe a given node’s structural relationship to its neighborhood. [sent-130, score-0.304]
41 For example, HKS has an interpretation in terms of a simulated heat diffusion process: for each node, this signature captures the amount of heat left at the node at various times (here t) assuming that a unit amount is put on the node initially (t = 0). [sent-131, score-1.189]
42 These signatures are naturally intrinsic, namely if two graphs are isomorphic, then the signatures of corresponding nodes are the same; the signatures are also stable under small perturbations [11]. [sent-132, score-1.272]
43 exp(−(t−lo2gσ2 λk)2), The above discussion suggests using these signatures as node attributes to design first order compatibility terms for if the signatures of two nodes from the two graphs are very different, then these vertices are less likely to be in correspondence. [sent-133, score-1.282]
44 However, such an approach does not take into account the given anchor correspondences, because the form of the function h(t; λk) is explicitly provided beforehand. [sent-134, score-0.336]
45 Assuming tahrabti tLraFryS comparison employs this dot product, the dissimilarity between two nodes u ∈ V, v ∈ V? [sent-148, score-0.238]
46 Namely, we set dB(i, a) = for any two nodes i∈ V, a ∈ V? [sent-253, score-0.207]
47 explicitly, but allows us to learn directly the proximity matrix B which is a small matrix (tens by tens in our experiments). [sent-258, score-0.326]
48 1 Learning the Proximity Matrix Here we explain how to learn the proximity matrix B from the knowledge of anchor nodes. [sent-263, score-0.566]
49 A good proximity matrix B should move closer node pairs that correspond, and move away nodes that are non-matches. [sent-264, score-0.586]
50 In our graph matching setting, Ω(k, j) could be the shortest distance over the graph, or the heat kernel as described in Section 3. [sent-312, score-0.743]
51 2 (we used heat kernel in our experiments as it has been shown to be more robust than the adjacency matrix [11] and, hence, shortest distance). [sent-313, score-0.605]
52 Heat Kernel with Anchor Nodes In this subsection we introduce the second term appear- ing in our first order compatibility measure. [sent-371, score-0.224]
53 This term is based on the heat diffusion process on graph G. [sent-372, score-0.581]
54 Specifically, consider the graph heat kernel kt (u, v), which measures the amount of heat transferred from node u to node v after time t, assuming a unit amount was placed at u in the beginning (t = 0). [sent-373, score-1.299]
55 The heat kernel has the following representation in terms of the eigen-decomposition of the graph Laplacian: kt(u,v) = ? [sent-374, score-0.595]
56 k We use the heat kernel value of anchor nodes at a given node as another first order constraint. [sent-377, score-1.112]
57 Namely, for any node v of graph G define the heat kernel distance to anchor nodes as daHp(v) = ? [sent-378, score-1.287]
58 aHp 222999000977 For two nodes iand a in graphs G and G? [sent-387, score-0.392]
59 ssimilarity between nodes because the anchor nodes U and U? [sent-401, score-0.75]
60 Moreover, the heat kernel is naturally intrinsic (if two graphs are isomorphic, their corresponding heat kernels are the same) and it is stable under small perturbations [11]. [sent-403, score-0.976]
61 Matching Scheme Here we formulate the graph matching as an integer quadratic program (IQP). [sent-405, score-0.427]
62 tshe i ∈lea Vrn \eUd proximity, and let dap(i,a) = order compatibility term is d(i, a) ? [sent-418, score-0.224]
63 Now we need a second order compatibility term, for which we will use the heat kernel as done in [11]. [sent-427, score-0.615]
64 , the pairwise heat kernel dtwisota nnoced eiss di,ejfin ∈ed V as dk (i, j,a, b) = |kt (i, j) − kt? [sent-429, score-0.502]
65 (a, b) | , and this gives a measure of how compatible matching nodes iand a is with matching j and b. [sent-430, score-0.503]
66 As has been discussed in [11], the heat kernel can be thought of as a noise tolerant × approximation of the adjacency matrix, and is stable under small perturbations. [sent-431, score-0.558]
67 Thus, our second order proximity term can be thought as a generalization of the commonly used adjacency-based second order term. [sent-432, score-0.212]
68 Combining all this information, we construct a compatibility matrix W ∈ R(|V |−|U|)(|V? [sent-433, score-0.242]
69 In our experiments, we selected a recently proposed algorithm, reweighed random walk matching (RRWM) [4]. [sent-459, score-0.219]
70 Experiments We tested our approach on three different datasets: 1) synthetically generated random graphs; 2) CMU Hotel sequence for large baseline matching; and 3) pose house sequence from [18] for large rotation angle matching. [sent-463, score-0.225]
71 Synthetic Random Graphs In this section, following the experimental protocol of [4], we synthetically generated random graphs and performed a comparative study. [sent-466, score-0.213]
72 For a pair of graph G1 and G2, they share nin common nodes and and outlier nodes. [sent-467, score-0.382]
73 In the experiment, the number of an- no(1ut) no(2ut) chor nodes |U| = 2. [sent-473, score-0.207]
74 1 (a), it can be seen that with the help of learned proximity matrix B and the term dap(i, a), the matching results are more robust to noise. [sent-476, score-0.407]
75 CMU Hotel Sequence In this experiment, we test our descriptors on the CMU Hotel sequence, which is widely used in performance evaluation of graph matching algorithms as a wide baseline dataset. [sent-484, score-0.323]
76 |U| = 2 nodes were randomly islealrelcyte ads as th Seec atniocnho 5r. [sent-490, score-0.207]
77 As can be seen the matching performance was improved when heat kernel is used in lieu of the adjacency matrix, because the noise tolerance property of the former smoothes out the effect of deformation noise. [sent-496, score-0.706]
78 With the addon effect of proximity matrix B and dap(i, a), furthermore, the matching performance was much improved. [sent-497, score-0.378]
79 2 (b,c) showes an example of the matching between the 20th and the 90th frame of the sequence (yellow lines are correct matches and red lines are wrong matches). [sent-499, score-0.357]
80 In the second part of this experiment, we select to test the influence of the number of anchor nodes on the average matching rate. [sent-501, score-0.691]
81 We intentionally drop off the term dap to reduce the side effect, i. [sent-502, score-0.253]
82 We increase the number of anchor nodes and compare the matching performance in otherwise the same setting. [sent-505, score-0.691]
83 3, with the increase of the number of anchor nodes, the overall matching performance increased. [sent-507, score-0.484]
84 However, the marginal performance gain seems to have a drop-off with the increase of the number of anchor nodes, since the matching rate gap between |U| = 10 and |U| = 5 sisi nmceuc thhe es mmaaltclehri tnhga nra tthea gta abpet bweetwenee e| nU | U =| =5 a 1n0d a| nUd| =U |2 . [sent-508, score-0.484]
85 The house undergoes large pan and tilt angle change (0 4T5h◦e fhooru pan angle eansd l0ar−ge30 p◦a nfo arn tdilt t)il. [sent-513, score-0.378]
86 |U| = 2 nodes were randomly selected as the anchor nodes. [sent-515, score-0.543]
87 lump from left to right represent a tilt angle from 0 to 30◦ with a 5◦ step and within a lump is the pan angle change from left to right for 0 to 45◦ with a 5◦step. [sent-520, score-0.305]
88 It can been seen that extreme pan angles gave poor results while mid range pan angles yield matches with much higher accuracy while matching accuracy was not much influenced by the difference in tilt angles. [sent-521, score-0.434]
89 With the addition of our learned proximity matrix B, the gap between different pan angles decreases and the overall matching accuracy is superior to others. [sent-522, score-0.494]
90 4 (b,c) shows the matching results and the first and last frame of the sequence, which represent the largest pan and tilt angles. [sent-524, score-0.299]
91 Even in this extreme case, it can be seen that our dB + dap + dk matching gives useful results, and is much better than the adjacency matrix based matching. [sent-525, score-0.639]
92 Conclusion In this paper, we have considered the problem of graph matching where some correspondences are known. [sent-529, score-0.417]
93 We have designed a learning algorithm which uses the anchor correspondences as training samples. [sent-530, score-0.43]
94 The matching problem is set up as an IQP, where we use the learned proximity and heat kernel distance to anchor nodes as first order compatibility, and pairwise heat kernel distance difference as a second order compatibility. [sent-531, score-1.714]
95 With a very small number of anchor nodes (|U| = 2 in all of the experiments) we have oabnctahionre dn superior performance as compared teon tthse) swteat he-aovfethe-art techniques based on adjacency matrices. [sent-532, score-0.706]
96 Graph matching using the interference of continuous-time quantum walks. [sent-583, score-0.216]
97 An integer projected fixed point method for graph matching and map inference. [sent-656, score-0.373]
98 Structural graph matching using the em algorithm and singular value decomposition. [sent-684, score-0.323]
99 A concise and provably informative multi-scale signature based on heat diffu- [25] [26] [27] [28] [29] [30] [3 1] sion. [sent-744, score-0.483]
100 A path following algorithm for the graph matching problem. [sent-793, score-0.323]
wordName wordTfidf (topN-words)
[('heat', 0.345), ('anchor', 0.336), ('signatures', 0.273), ('dap', 0.224), ('nodes', 0.207), ('compatibility', 0.195), ('iqp', 0.193), ('graphs', 0.185), ('proximity', 0.183), ('graph', 0.175), ('node', 0.149), ('matching', 0.148), ('adjacency', 0.138), ('signature', 0.138), ('hotel', 0.121), ('lfs', 0.107), ('db', 0.102), ('ja', 0.096), ('correspondences', 0.094), ('pan', 0.091), ('rrwm', 0.086), ('dk', 0.082), ('house', 0.078), ('kernel', 0.075), ('abwia', 0.072), ('dahp', 0.072), ('dkrrwm', 0.072), ('hks', 0.072), ('wiawi', 0.072), ('leordeanu', 0.07), ('nb', 0.07), ('laplacian', 0.069), ('quantum', 0.068), ('kt', 0.061), ('tilt', 0.06), ('cb', 0.059), ('family', 0.059), ('slack', 0.054), ('integer', 0.05), ('edit', 0.05), ('tens', 0.049), ('aubry', 0.048), ('capdap', 0.048), ('cbdb', 0.048), ('emms', 0.048), ('lump', 0.048), ('matrix', 0.047), ('su', 0.046), ('ib', 0.046), ('spectral', 0.045), ('sequence', 0.045), ('matches', 0.044), ('schellewald', 0.043), ('wks', 0.043), ('wyk', 0.043), ('zaslavskiy', 0.043), ('aki', 0.043), ('btr', 0.043), ('berlin', 0.042), ('heidelberg', 0.041), ('graduated', 0.04), ('ipfp', 0.04), ('uk', 0.038), ('reweighed', 0.037), ('mcauley', 0.037), ('isomorphic', 0.037), ('bw', 0.036), ('rk', 0.035), ('namely', 0.035), ('walk', 0.034), ('bi', 0.034), ('cmu', 0.034), ('gold', 0.033), ('qiu', 0.033), ('diffusion', 0.032), ('xia', 0.032), ('lines', 0.031), ('simulated', 0.031), ('structural', 0.031), ('ki', 0.031), ('dissimilarity', 0.031), ('correct', 0.03), ('wave', 0.029), ('angle', 0.029), ('term', 0.029), ('synthetically', 0.028), ('wrong', 0.028), ('quadratic', 0.028), ('generic', 0.027), ('walks', 0.027), ('arxiv', 0.027), ('bb', 0.027), ('program', 0.026), ('pages', 0.026), ('aij', 0.026), ('cour', 0.026), ('perturbations', 0.026), ('superior', 0.025), ('ph', 0.025), ('eigenvector', 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 1.000001 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
2 0.25705382 110 cvpr-2013-Dense Object Reconstruction with Semantic Priors
Author: Sid Yingze Bao, Manmohan Chandraker, Yuanqing Lin, Silvio Savarese
Abstract: We present a dense reconstruction approach that overcomes the drawbacks of traditional multiview stereo by incorporating semantic information in the form of learned category-level shape priors and object detection. Given training data comprised of 3D scans and images of objects from various viewpoints, we learn a prior comprised of a mean shape and a set of weighted anchor points. The former captures the commonality of shapes across the category, while the latter encodes similarities between instances in the form of appearance and spatial consistency. We propose robust algorithms to match anchor points across instances that enable learning a mean shape for the category, even with large shape variations across instances. We model the shape of an object instance as a warped version of the category mean, along with instance-specific details. Given multiple images of an unseen instance, we collate information from 2D object detectors to align the structure from motion point cloud with the mean shape, which is subsequently warped and refined to approach the actual shape. Extensive experiments demonstrate that our model is general enough to learn semantic priors for different object categories, yet powerful enough to reconstruct individual shapes with large variations. Qualitative and quantitative evaluations show that our framework can produce more accurate reconstructions than alternative state-of-the-art multiview stereo systems.
3 0.15156893 107 cvpr-2013-Deformable Spatial Pyramid Matching for Fast Dense Correspondences
Author: Jaechul Kim, Ce Liu, Fei Sha, Kristen Grauman
Abstract: We introduce a fast deformable spatial pyramid (DSP) matching algorithm for computing dense pixel correspondences. Dense matching methods typically enforce both appearance agreement between matched pixels as well as geometric smoothness between neighboring pixels. Whereas the prevailing approaches operate at the pixel level, we propose a pyramid graph model that simultaneously regularizes match consistency at multiple spatial extents—ranging from an entire image, to coarse grid cells, to every single pixel. This novel regularization substantially improves pixel-level matching in the face of challenging image variations, while the “deformable ” aspect of our model overcomes the strict rigidity of traditional spatial pyramids. Results on LabelMe and Caltech show our approach outperforms state-of-the-art methods (SIFT Flow [15] and PatchMatch [2]), both in terms of accuracy and run time.
4 0.13855085 80 cvpr-2013-Category Modeling from Just a Single Labeling: Use Depth Information to Guide the Learning of 2D Models
Author: Quanshi Zhang, Xuan Song, Xiaowei Shao, Ryosuke Shibasaki, Huijing Zhao
Abstract: An object model base that covers a large number of object categories is of great value for many computer vision tasks. As artifacts are usually designed to have various textures, their structure is the primary distinguishing feature between different categories. Thus, how to encode this structural information and how to start the model learning with a minimum of human labeling become two key challenges for the construction of the model base. We design a graphical model that uses object edges to represent object structures, and this paper aims to incrementally learn this category model from one labeled object and a number of casually captured scenes. However, the incremental model learning may be biased due to the limited human labeling. Therefore, we propose a new strategy that uses the depth information in RGBD images to guide the model learning for object detection in ordinary RGB images. In experiments, the proposed method achieves superior performance as good as the supervised methods that require the labeling of all target objects.
5 0.12483762 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
Author: Asad A. Butt, Robert T. Collins
Abstract: We propose a method for global multi-target tracking that can incorporate higher-order track smoothness constraints such as constant velocity. Our problem formulation readily lends itself to path estimation in a trellis graph, but unlike previous methods, each node in our network represents a candidate pair of matching observations between consecutive frames. Extra constraints on binary flow variables in the graph result in a problem that can no longer be solved by min-cost network flow. We therefore propose an iterative solution method that relaxes these extra constraints using Lagrangian relaxation, resulting in a series of problems that ARE solvable by min-cost flow, and that progressively improve towards a high-quality solution to our original optimization problem. We present experimental results showing that our method outperforms the standard network-flow formulation as well as other recent algorithms that attempt to incorporate higher-order smoothness constraints.
6 0.12320176 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
7 0.12090076 106 cvpr-2013-Deformable Graph Matching
8 0.1124096 340 cvpr-2013-Probabilistic Label Trees for Efficient Large Scale Image Classification
9 0.094225086 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
10 0.093524285 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
11 0.087859899 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
12 0.087735519 241 cvpr-2013-Label-Embedding for Attribute-Based Classification
13 0.087495208 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
15 0.084875323 138 cvpr-2013-Efficient 2D-to-3D Correspondence Filtering for Scalable 3D Object Recognition
16 0.083671309 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
17 0.082128413 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
18 0.081856064 180 cvpr-2013-Fully-Connected CRFs with Non-Parametric Pairwise Potential
19 0.080808178 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
20 0.077821493 352 cvpr-2013-Recovering Stereo Pairs from Anaglyphs
topicId topicWeight
[(0, 0.167), (1, 0.025), (2, -0.005), (3, 0.033), (4, 0.062), (5, -0.0), (6, -0.012), (7, -0.046), (8, -0.074), (9, -0.004), (10, 0.05), (11, 0.096), (12, -0.085), (13, -0.01), (14, -0.007), (15, -0.099), (16, -0.058), (17, 0.016), (18, 0.121), (19, -0.023), (20, -0.028), (21, 0.027), (22, -0.016), (23, 0.038), (24, 0.063), (25, -0.07), (26, 0.048), (27, -0.017), (28, -0.02), (29, 0.165), (30, -0.073), (31, -0.072), (32, 0.122), (33, -0.085), (34, 0.132), (35, 0.103), (36, 0.038), (37, -0.012), (38, 0.053), (39, -0.035), (40, -0.034), (41, 0.053), (42, -0.041), (43, -0.003), (44, 0.057), (45, -0.134), (46, -0.032), (47, 0.018), (48, -0.046), (49, -0.054)]
simIndex simValue paperId paperTitle
same-paper 1 0.97326356 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
2 0.85889775 106 cvpr-2013-Deformable Graph Matching
Author: Feng Zhou, Fernando De_la_Torre
Abstract: Graph matching (GM) is a fundamental problem in computer science, and it has been successfully applied to many problems in computer vision. Although widely used, existing GM algorithms cannot incorporate global consistence among nodes, which is a natural constraint in computer vision problems. This paper proposes deformable graph matching (DGM), an extension of GM for matching graphs subject to global rigid and non-rigid geometric constraints. The key idea of this work is a new factorization of the pair-wise affinity matrix. This factorization decouples the affinity matrix into the local structure of each graph and the pair-wise affinity edges. Besides the ability to incorporate global geometric transformations, this factorization offers three more benefits. First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. Second, it provides a unified view of many GM methods and extends the standard iterative closest point algorithm. Third, it allows to use the path-following optimization algorithm that leads to improved optimization strategies and matching performance. Experimental results on synthetic and real databases illustrate how DGM outperforms state-of-the-art algorithms for GM. The code is available at http : / / human s en s ing . c s . cmu .edu / fgm.
3 0.74072748 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu
Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.
4 0.71446085 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
Author: Vittal Premachandran, Ramakrishna Kakarala
Abstract: Propagating similarity information along the data manifold requires careful selection of local neighborhood. Selecting a “good” neighborhood in an unsupervised setting, given an affinity graph, has been a difficult task. The most common way to select a local neighborhood has been to use the k-nearest neighborhood (k-NN) selection criterion. However, it has the tendency to include noisy edges. In this paper, we propose a way to select a robust neighborhood using the consensus of multiple rounds of k-NNs. We explain how using consensus information can give better control over neighborhood selection. We also explain in detail the problems with another recently proposed neighborhood selection criteria, i.e., Dominant Neighbors, and show that our method is immune to those problems. Finally, we show the results from experiments in which we compare our method to other neighborhood selection approaches. The results corroborate our claims that consensus ofk-NNs does indeed help in selecting more robust and stable localities.
5 0.70393062 107 cvpr-2013-Deformable Spatial Pyramid Matching for Fast Dense Correspondences
Author: Jaechul Kim, Ce Liu, Fei Sha, Kristen Grauman
Abstract: We introduce a fast deformable spatial pyramid (DSP) matching algorithm for computing dense pixel correspondences. Dense matching methods typically enforce both appearance agreement between matched pixels as well as geometric smoothness between neighboring pixels. Whereas the prevailing approaches operate at the pixel level, we propose a pyramid graph model that simultaneously regularizes match consistency at multiple spatial extents—ranging from an entire image, to coarse grid cells, to every single pixel. This novel regularization substantially improves pixel-level matching in the face of challenging image variations, while the “deformable ” aspect of our model overcomes the strict rigidity of traditional spatial pyramids. Results on LabelMe and Caltech show our approach outperforms state-of-the-art methods (SIFT Flow [15] and PatchMatch [2]), both in terms of accuracy and run time.
6 0.62678021 190 cvpr-2013-Graph-Based Optimization with Tubularity Markov Tree for 3D Vessel Segmentation
7 0.60255051 194 cvpr-2013-Groupwise Registration via Graph Shrinkage on the Image Manifold
8 0.60105288 350 cvpr-2013-Reconstructing Loopy Curvilinear Structures Using Integer Programming
10 0.59799802 80 cvpr-2013-Category Modeling from Just a Single Labeling: Use Depth Information to Guide the Learning of 2D Models
11 0.58567894 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
12 0.5741865 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
13 0.55532414 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
14 0.55307341 280 cvpr-2013-Maximum Cohesive Grid of Superpixels for Fast Object Localization
15 0.5507257 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
16 0.54957992 340 cvpr-2013-Probabilistic Label Trees for Efficient Large Scale Image Classification
17 0.54205382 224 cvpr-2013-Information Consensus for Distributed Multi-target Tracking
18 0.5393002 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
19 0.53903157 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
20 0.52239656 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
topicId topicWeight
[(10, 0.092), (16, 0.027), (26, 0.035), (28, 0.361), (33, 0.256), (67, 0.042), (69, 0.033), (87, 0.065)]
simIndex simValue paperId paperTitle
same-paper 1 0.78878891 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
2 0.76943499 428 cvpr-2013-The Episolar Constraint: Monocular Shape from Shadow Correspondence
Author: Austin Abrams, Kylia Miskell, Robert Pless
Abstract: Shadows encode a powerful geometric cue: if one pixel casts a shadow onto another, then the two pixels are colinear with the lighting direction. Given many images over many lighting directions, this constraint can be leveraged to recover the depth of a scene from a single viewpoint. For outdoor scenes with solar illumination, we term this the episolar constraint, which provides a convex optimization to solve for the sparse depth of a scene from shadow correspondences, a method to reduce the search space when finding shadow correspondences, and a method to geometrically calibrate a camera using shadow constraints. Our method constructs a dense network of nonlocal constraints which complements recent work on outdoor photometric stereo and cloud based cues for 3D. We demonstrate results across a variety of time-lapse sequences from webcams “in . wu st l. edu (b)(c) the wild.”
3 0.76129174 261 cvpr-2013-Learning by Associating Ambiguously Labeled Images
Author: Zinan Zeng, Shijie Xiao, Kui Jia, Tsung-Han Chan, Shenghua Gao, Dong Xu, Yi Ma
Abstract: We study in this paper the problem of learning classifiers from ambiguously labeled images. For instance, in the collection of new images, each image contains some samples of interest (e.g., human faces), and its associated caption has labels with the true ones included, while the samplelabel association is unknown. The task is to learn classifiers from these ambiguously labeled images and generalize to new images. An essential consideration here is how to make use of the information embedded in the relations between samples and labels, both within each image and across the image set. To this end, we propose a novel framework to address this problem. Our framework is motivated by the observation that samples from the same class repetitively appear in the collection of ambiguously labeled training images, while they are just ambiguously labeled in each image. If we can identify samples of the same class from each image and associate them across the image set, the matrix formed by the samples from the same class would be ideally low-rank. By leveraging such a low-rank assump- tion, we can simultaneously optimize a partial permutation matrix (PPM) for each image, which is formulated in order to exploit all information between samples and labels in a principled way. The obtained PPMs can be readily used to assign labels to samples in training images, and then a standard SVM classifier can be trained and used for unseen data. Experiments on benchmark datasets show the effectiveness of our proposed method.
4 0.74869204 134 cvpr-2013-Discriminative Sub-categorization
Author: Minh Hoai, Andrew Zisserman
Abstract: The objective of this work is to learn sub-categories. Rather than casting this as a problem of unsupervised clustering, we investigate a weakly supervised approach using both positive and negative samples of the category. We make the following contributions: (i) we introduce a new model for discriminative sub-categorization which determines cluster membership for positive samples whilst simultaneously learning a max-margin classifier to separate each cluster from the negative samples; (ii) we show that this model does not suffer from the degenerate cluster problem that afflicts several competing methods (e.g., Latent SVM and Max-Margin Clustering); (iii) we show that the method is able to discover interpretable sub-categories in various datasets. The model is evaluated experimentally over various datasets, and itsperformance advantages over k-means and Latent SVM are demonstrated. We also stress test the model and show its resilience in discovering sub-categories as the parameters are varied.
5 0.74444246 4 cvpr-2013-3D Visual Proxemics: Recognizing Human Interactions in 3D from a Single Image
Author: Ishani Chakraborty, Hui Cheng, Omar Javed
Abstract: We present a unified framework for detecting and classifying people interactions in unconstrained user generated images. 1 Unlike previous approaches that directly map people/face locations in 2D image space into features for classification, we first estimate camera viewpoint and people positions in 3D space and then extract spatial configuration features from explicit 3D people positions. This approach has several advantages. First, it can accurately estimate relative distances and orientations between people in 3D. Second, it encodes spatial arrangements of people into a richer set of shape descriptors than afforded in 2D. Our 3D shape descriptors are invariant to camera pose variations often seen in web images and videos. The proposed approach also estimates camera pose and uses it to capture the intent of the photo. To achieve accurate 3D people layout estimation, we develop an algorithm that robustly fuses semantic constraints about human interpositions into a linear camera model. This enables our model to handle large variations in people size, heights (e.g. age) and poses. An accurate 3D layout also allows us to construct features informed by Proxemics that improves our semantic classification. To characterize the human interaction space, we introduce visual proxemes; a set of prototypical patterns that represent commonly occurring social interactions in events. We train a discriminative classifier that classifies 3D arrangements of people into visual proxemes and quantitatively evaluate the performance on a large, challenging dataset.
6 0.73196542 328 cvpr-2013-Pedestrian Detection with Unsupervised Multi-stage Feature Learning
7 0.7065056 232 cvpr-2013-Joint Geodesic Upsampling of Depth Images
8 0.69607627 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
9 0.65494335 206 cvpr-2013-Human Pose Estimation Using Body Parts Dependent Joint Regressors
10 0.64520407 284 cvpr-2013-Mesh Based Semantic Modelling for Indoor and Outdoor Scenes
11 0.64350587 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
12 0.64159495 19 cvpr-2013-A Minimum Error Vanishing Point Detection Approach for Uncalibrated Monocular Images of Man-Made Environments
14 0.64009905 394 cvpr-2013-Shading-Based Shape Refinement of RGB-D Images
15 0.63723487 432 cvpr-2013-Three-Dimensional Bilateral Symmetry Plane Estimation in the Phase Domain
16 0.636738 303 cvpr-2013-Multi-view Photometric Stereo with Spatially Varying Isotropic Materials
17 0.63655061 54 cvpr-2013-BRDF Slices: Accurate Adaptive Anisotropic Appearance Acquisition
18 0.63636988 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
19 0.63593948 155 cvpr-2013-Exploiting the Power of Stereo Confidences
20 0.63547039 299 cvpr-2013-Multi-source Multi-scale Counting in Extremely Dense Crowd Images