cvpr cvpr2013 cvpr2013-106 knowledge-graph by maker-knowledge-mining
Source: pdf
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.
Reference: text
sentIndex sentText sentNum sentScore
1 This paper proposes deformable graph matching (DGM), an extension of GM for matching graphs subject to global rigid and non-rigid geometric constraints. [sent-5, score-0.366]
2 The key idea of this work is a new factorization of the pair-wise affinity matrix. [sent-6, score-0.34]
3 This factorization decouples the affinity matrix into the local structure of each graph and the pair-wise affinity edges. [sent-7, score-0.65]
4 Besides the ability to incorporate global geometric transformations, this factorization offers three more benefits. [sent-8, score-0.257]
5 First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. [sent-9, score-0.163]
6 Third, it allows to use the path-following optimization algorithm that leads to improved optimization strategies and matching performance. [sent-11, score-0.105]
7 Unlike the linear assignment problem, which can be efficiently solved with the Hungarian algorithm [4], the QAP is known to be NP-hard and exact optimal algorithms using variations of branch-and-bound [22] are only practical for very small graphs (e. [sent-20, score-0.146]
8 DGM simultaneously estimates the correspondence and a smooth non-rigid transformation between nodes. [sent-28, score-0.187]
9 DGM is able to factorize the 20 20 pair-wise affinity matrix as a Kronecker prodfuacctt oorfi iszixe tshmea 2ll0e×r m20at priacire-sw. [sent-29, score-0.239]
10 iTsehe a ffifirsnti ttyw mo groups oaf K mraontreiccekse or fp rsoidze5 16 and 4 10 encode the structure of each of the graphs (i. [sent-30, score-0.108]
11 decades, there are still two main challenges: (1) Many matching problems in computer vision naturally require global constraints among nodes in the graph. [sent-36, score-0.121]
12 For instance, given two sets of coplanar points in two images, the matching between points should be constrained by an affine transformation (under orthographic projection). [sent-37, score-0.18]
13 Sim- ilarly, when matching the deformations of non-rigid objects between two consecutive images that deformation is typically smooth in space and time. [sent-38, score-0.09]
14 Existing GM algorithms do not constrain the nodes of both graphs to a given geometric transformation (e. [sent-39, score-0.29]
15 In order to incorporate global transformations, the key 222999222200 idea of our method is to factorize the pairwise affinity matrix into matrices that preserve the local structure of each graph and matrices that encode the similarity between nodes and edges. [sent-45, score-0.519]
16 This factorization is general and can be applied to both directed and undirected graphs. [sent-46, score-0.397]
17 Using the factorization, we are able to factorize the large 20-by-20 pair-wise affinity matrix into six smaller matrices. [sent-49, score-0.239]
18 Because we have decoupled the local structure for the nodes in each graph, it is easy to add global geometric constraints. [sent-50, score-0.096]
19 Moreover, using this factorization has three additional benefits for GM. [sent-51, score-0.177]
20 First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. [sent-52, score-0.163]
21 Third, it allows the use of path-following optimization algorithms in general GM problems that leads to improved optimization strategies and matching performance. [sent-55, score-0.105]
22 We illustrate the benefits of DGM in synthetic and real matching experiments on standard databases. [sent-56, score-0.126]
23 Graph matching (GM) We denote (see notation1) a graph with n nodes and m directed edges as a 4-tuple G = {P, Q, G, H}. [sent-60, score-0.341]
24 T ∈he R topology of the graph ·is· ,enqco]de ∈d by two node-edge incidence matrices G, H ∈ {0, 1}n×m, where gic e=- hjc = in c1i dife ntchee mctha edge sGta,rHts fr ∈om { 0th,1e} ith node and ends at the jth node. [sent-63, score-0.364]
25 2a illustrates two synthetic graphs, whose edge connection between nodes is encoded by the corresponding matrices shown in Fig. [sent-65, score-0.245]
26 However, the work in [29] is only valid for undirected graphs. [sent-68, score-0.105]
27 Our representation is more general and valid for directed and undirected graphs. [sent-69, score-0.22]
28 Directed graphs typically occur when the features are asymmetrical such as the angle between an edge and the horizontal line. [sent-70, score-0.185]
29 Our model incorporates directed graphs by encoding the starting and ending ×n ×m × × node in G and H respectively. [sent-71, score-0.296]
30 {P2, Q2, G2, H2}, we compute two affinity matrices, Kp ∈ Rn1 ×n2 an}d, Kq e∈ c oRmmp1u ×tem2 t , too measure mthea sriicmesi,larity ∈o fR each node and edge pair respectively. [sent-96, score-0.314]
31 More specifically, κip1i2 = φp(pi11 , pi22 ) measures the similarity between the it1h node of G1 and the it2h node of G2, and n n κct1cqh1ce2dg=e o φfq( Gq1 c1an,qdc2 t2h)e m c2tehaesudrge s o tfh Ge2 s. [sent-97, score-0.102]
32 It is more convenient to encode the node and edge affinities in a global affinity matrix K ∈ Rn1n2 ×n1n2 , whose teileesm iennt a ai sg cloobmaplu aftfeidn aitys fo mlalotwrixs: κi12j12=⎪⎨ ⎪⎧ κ ipqc10 ci,2 ,iogfti1 heci1r 1wh? [sent-100, score-0.329]
33 = j2 1,and Given two g⎩⎪raphs and K, the problem of GM consists in finding the optimal correspondence X between nodes, such that the following score is maximized, mXax Jgm(X) = vec(X)TKvec(X), s. [sent-103, score-0.101]
34 The inequality in the above definition is used for the case when the graphs are of different sizes. [sent-109, score-0.108]
35 However, these methods can only work for a restricted case, where K = K1 ⊗ K2 is composed by two weighted adjacency matrices, K⊗1 K∈ Rn1 ×n1 and K2 ∈ Rn2 ×n2, defined on each graph respectively. [sent-119, score-0.138]
36 (b) The 1st graph’s incidence matrices G1 and H1, where the nonzero elements in each column of G1 and H1 indicate the starting and ending nodes in the corresponding directed edge, respectively. [sent-133, score-0.282]
37 (d) The node affinity matrix Kp and the edge affinity matrix Kq between graphs. [sent-135, score-0.53]
38 (e) The node correspondence matrix X and the edge correspondence matrix Y. [sent-136, score-0.406]
39 For instance, Gold and Rangarajan [11] proposed the graduated assignment algorithm to iteratively solve a series of linear approximations of the cost function using Taylor expansions. [sent-140, score-0.092]
40 Our work is closely related to recent higher-order tensor factorization [5, 9, 26]. [sent-145, score-0.177]
41 In order to make GM invariant to rigid deformations, [5, 9, 26] extended the pairwise matrix K embedded into a tensor that encodes highorder geometrical relations. [sent-147, score-0.098]
42 Therefore, most of high-order GM methods can only work on very sparse graphs with no more than 3-order features. [sent-149, score-0.108]
43 , [2], ∈27 R]) aim to find the correspondence and the geometric transformation between points such that the sum of distances is minimized: Xmi,Tn Jicp(X,T ) =i? [sent-155, score-0.221]
44 X ∈ Π, T ∈ Ψ, (2) where X ∈ {0, 1}n1 ×n2 denotes the correspondence be- twwheeerne points. [sent-160, score-0.101]
45 The optimization over X given the transformation T can be cast as a zliatnieoanr matching problem, wanhsifcohr can o bne efficiently optimized by the Hungarian algorithm (if X is a one-to-one mapping) or the winner-take-all manner (if X is a many-toone mapping). [sent-183, score-0.168]
46 Factorized graph matching This section derives a new factorization of the pair-wise affinity matrix K. [sent-190, score-0.519]
47 As we will see in the following sections, this factorization allows the unification of GM methods, adding geometric constraints to GM and elaborating better optimization strategies. [sent-191, score-0.266]
48 222999222422 To illustrate the intuition behind the factorization, let us consider the synthetic graph shown in Fig. [sent-192, score-0.149]
49 Notice that K ∈ Rn1n2 ×n1n2 is composed by two types of affinities: Kthe ∈nod Re affinity (Kp) on its diagonal and the pairwise edge affinity (Kq) on its off-diagonals. [sent-194, score-0.464]
50 (4) This factorization decouples the graph structure (G1, H1, G2 and H2) from the similarity (Kp and Kq). [sent-205, score-0.286]
51 It is important to notice that our factorization significantly differs from the one proposed in [29] in two aspects: (1) Eq. [sent-206, score-0.177]
52 4 is proposed for more general graphs composed by directed edges while [29] can be only applied for simpler graphs composed by undirected edges; (2) Unlike a joint factorization proposed in [29], Eq. [sent-207, score-0.686]
53 4 separates Kp and Kq in the factorization in two independent terms. [sent-208, score-0.177]
54 1 leads to an equivalent objective function: Jgm(X) = tr ? [sent-217, score-0.099]
55 , (5) where Y = (GT1XG2 ◦ H1TXH2) ∈ {0, 1}m1×m2 is an auxiliary variable that en◦co Hdes the correspondence between edges, i. [sent-221, score-0.101]
56 , yc1c2 = 1 if ct1h edge in G1 is matched to the ct2h edge in G2. [sent-223, score-0.154]
57 2ee i nill Gustrates the node and edge correspondence matrices for the matching defined in Fig. [sent-225, score-0.326]
58 It is worth to point out that it not clear how to derive the relaxations (Jvex (X) and Jcav (X)) and apply the path-following algorithm without the propose factorization of K. [sent-273, score-0.214]
59 Deformable graph matching (DGM) This section describes how to incorporate rigid and nonrigid transformation into the GM framework. [sent-278, score-0.302]
60 Moreover, we illustrate how the factorization can be used into the DGM to derive an improved optimization strategy. [sent-279, score-0.232]
61 Objective function To simplify the discussion and to be consistent with ICP, we compute the node feature of each graph G = I{CPP,, ,Q w, eG c, oHm}p simply as eth fee tnuordee cfo oeardchina gterasp, hP G == {[pP1 , ·Q Q· ,· , p,nH] }∈ iRmdp×lyn. [sent-282, score-0.133]
62 In this case, the edge f−eat pure can be conveniently computed in a matrix form as, Q = P(G − H). [sent-286, score-0.115]
63 × Sni2m ainladr the edge affinity Kq (T ) ∈ Rm1 ×m2 as( Ta )f ∈unc Rtion of the Euclidean distance, i. [sent-289, score-0.24]
64 2 ) where β is chosen to be reasonably large to ensure that the pairwise affinity is greater than zero. [sent-307, score-0.199]
65 In order to make the GM more robust to geometric deformations, DGM aims to find the optimal correspondence X as well as the optimal transformation T such that the global consistency can be tmraanxsifmoirzmedat:i Jdgm(X,T ) mXa,Tx = tr? [sent-312, score-0.221]
66 Due to the non-convex nature of the objective, we optimize DGM by alternatively solving the correspondence (X) and the transformation parameter (T ). [sent-326, score-0.187]
67 eH ioniwtieavliezra, tiohen way of choosing a good initialization is beyond the scope λ λ of this paper and we simply set the initial transformation as an identity one, i. [sent-329, score-0.086]
68 11will alternate between optimizing for the correspondence and the geometric transformation. [sent-335, score-0.173]
69 Optimization for the correspondence: Given the transformation T , DGM is equivalent to a traditional GM problfeomrm. [sent-336, score-0.086]
70 aTtioo fnin Td t,h De GnoMde i correspondence X tr,a we adopt tMhe pathfollowing algorithm by optimizing Eq. [sent-337, score-0.198]
71 Optimization for the geometric transformation: Given the correspondence matrix X, the optimization over the transformation parameter T is similar to ICP. [sent-339, score-0.282]
72 ra Tmhee mtera iTn appears ynolite osninlyt hine tfhacet ntohadtet ahfeftinraitnys fKorpm(Tat )i,o nb upta aralsmo eitne rthTe edge affinity Kq (T ). [sent-341, score-0.24]
73 Experiments This section reports experimental results on three benchmark datasets and compares FGM for Directed graphs (FGM-D) and DGM to several state-of-the-art methods for GM and ICP respectively. [sent-367, score-0.108]
74 In the third experiment we add a known geometrical transformation between graphs and compare it with ICP algorithm on the problem of matching non-rigid shapes. [sent-401, score-0.253]
75 CMU house image dataset The CMU house image dataset consists of 111 frames of a house, each of which has been manually labeled with 30 landmarks. [sent-404, score-0.1]
76 In this experiment, we focused on the simple case, where the edge is undirected and the edge feature is symmetric. [sent-406, score-0.259]
77 In particular, the edge feature qc was com- puted as the pairwise distance between the connected nodes. [sent-407, score-0.19]
78 We compared FGM-D against eight state-of-the-art algorithms: GA [11], SM [14], SMAC [8], IPFP [15] initialized with a uniform correspondence (IPFPU) and spectral matching (IPFP-S), PM [26], RRWM [6] and FGM for Undirected graphs (FGM-U) [29]. [sent-410, score-0.268]
79 This is because FGMU can be considered as a special case of FGM-D when the graph only has undirected edges. [sent-422, score-0.187]
80 Car and motorbike image dataset The car and motorbike image dataset was created in [16]. [sent-425, score-0.157]
81 This dataset consists of 30 pairs of car images and 20 pairs of motorbike images. [sent-426, score-0.094]
82 In this experiment, we consider the most general graph where the edge is directed and the edge feature is asymmetrical. [sent-430, score-0.351]
83 More specifically, each edge was represented by a couple of values, qc = [dc, θc]T, where dc is the pairwise distance between the connected nodes and θc is the angle between the edge and the horizontal line. [sent-431, score-0.304]
84 Thus, for each pair of images, we computed the node affinity as kipj = exp(−|pi − pj |) and the edge affinity as kcq1c2 = exp(−21 |dc1 − dc2 | −21 |θc1 − θc2 |). [sent-432, score-0.477]
85 However, we were unable to directly use FGM-U to match directed graphs. [sent-440, score-0.115]
86 Therefore, we ran FGM-U on an approximated undirected graph, where for each pair of directed edges, we computed its new edge affinity as the average value of the original ones. [sent-441, score-0.483]
87 On the other hand, although FGM-U has a similar path-following strategy, it did not perform well because it is only applicable to undirected edges. [sent-445, score-0.105]
88 Finally, it is important to remind the reader that without the factorization proposed in this work it is not possible to apply the path-following method to general graphs. [sent-446, score-0.177]
89 (a) An example pair of frames with the correspondence generated by our method, where the blue lines indicate incorrect matches. [sent-481, score-0.124]
90 (d) Performance as a function of the outlier number for the motorbike images. [sent-487, score-0.087]
91 Recall that DGM simultaneously computes the correspondence and the rotation. [sent-508, score-0.101]
92 In addition, we tested the performance of our algorithm (FGM-D) only using the path-following algorithm for computing the correspondence but without estimating the transformation. [sent-522, score-0.101]
93 Conclusions This paper proposes DGM, an extension of GM for matching points under a global geometric transformation for directed and undirected graphs. [sent-529, score-0.399]
94 The key idea for DGM is a novel factorization of the pairwise affinity matrix. [sent-530, score-0.376]
95 (c) Results of GM methods, where the green and black lines indicate correct and incorrect correspondence respectively. [sent-552, score-0.101]
96 First, it avoids the expensive (in space and time) computation of the pair- wise affinity matrix. [sent-554, score-0.163]
97 A linear programming approach for the weighted graph matching problem. [sent-566, score-0.141]
98 A spectral technique for correspondence problems using pairwise constraints. [sent-674, score-0.137]
99 An integer projected fixed point method for graph matching and MAP inference. [sent-680, score-0.141]
100 A path following algorithm for the graph matching problem. [sent-775, score-0.141]
wordName wordTfidf (topN-words)
[('dgm', 0.52), ('gm', 0.52), ('icp', 0.204), ('kq', 0.202), ('factorization', 0.177), ('affinity', 0.163), ('jgm', 0.156), ('kp', 0.131), ('directed', 0.115), ('graphs', 0.108), ('undirected', 0.105), ('correspondence', 0.101), ('transformation', 0.086), ('graph', 0.082), ('vec', 0.08), ('edge', 0.077), ('tr', 0.076), ('leordeanu', 0.068), ('motorbike', 0.063), ('nodes', 0.062), ('matching', 0.059), ('jcav', 0.059), ('jvex', 0.059), ('ktpx', 0.059), ('pathfollowing', 0.059), ('cpd', 0.058), ('factorized', 0.056), ('cmu', 0.054), ('qc', 0.052), ('rrwm', 0.052), ('node', 0.051), ('house', 0.05), ('incidence', 0.045), ('permutation', 0.043), ('aantidon', 0.039), ('commonalities', 0.039), ('fgm', 0.039), ('hjc', 0.039), ('jcon', 0.039), ('jicp', 0.039), ('qap', 0.039), ('xve', 0.039), ('matrices', 0.038), ('assignment', 0.038), ('matrix', 0.038), ('factorize', 0.038), ('optimizing', 0.038), ('relaxations', 0.037), ('pairwise', 0.036), ('ucf', 0.036), ('delaunay', 0.036), ('synthetic', 0.035), ('uvt', 0.035), ('affine', 0.035), ('diag', 0.035), ('geometric', 0.034), ('transformations', 0.033), ('connection', 0.033), ('graduated', 0.032), ('gic', 0.032), ('unification', 0.032), ('illustrate', 0.032), ('reveals', 0.032), ('car', 0.031), ('deformations', 0.031), ('adjacency', 0.031), ('outliers', 0.03), ('rotation', 0.029), ('xtx', 0.029), ('concave', 0.027), ('nonrigid', 0.027), ('gold', 0.027), ('decouples', 0.027), ('duchenne', 0.027), ('de', 0.026), ('kij', 0.026), ('torre', 0.025), ('puted', 0.025), ('fish', 0.025), ('instance', 0.025), ('composed', 0.025), ('la', 0.025), ('rigid', 0.024), ('outlier', 0.024), ('optima', 0.024), ('pattern', 0.024), ('incorporate', 0.024), ('edges', 0.023), ('hungarian', 0.023), ('letters', 0.023), ('pair', 0.023), ('zhou', 0.023), ('shapes', 0.023), ('objective', 0.023), ('optimization', 0.023), ('offers', 0.022), ('author', 0.022), ('trapped', 0.022), ('series', 0.022), ('ending', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 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.
2 0.12090076 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.
3 0.120741 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
Author: Jiayi Ma, Ji Zhao, Jinwen Tian, Zhuowen Tu, Alan L. Yuille
Abstract: We present a new point matching algorithm for robust nonrigid registration. The method iteratively recovers the point correspondence and estimates the transformation between two point sets. In the first step of the iteration, feature descriptors such as shape context are used to establish rough correspondence. In the second step, we estimate the transformation using a robust estimator called L2E. This is the main novelty of our approach and it enables us to deal with the noise and outliers which arise in the correspondence step. The transformation is specified in a functional space, more specifically a reproducing kernel Hilbert space. We apply our method to nonrigid sparse image feature correspondence on 2D images and 3D surfaces. Our results quantitatively show that our approach outperforms state-ofthe-art methods, particularly when there are a large number of outliers. Moreover, our method of robustly estimating transformations from correspondences is general and has many other applications.
4 0.077990085 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.
5 0.076682433 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.076170154 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
7 0.076029964 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
8 0.076017313 341 cvpr-2013-Procrustean Normal Distribution for Non-rigid Structure from Motion
9 0.074802861 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
10 0.074320547 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
11 0.071715094 372 cvpr-2013-SLAM++: Simultaneous Localisation and Mapping at the Level of Objects
12 0.071646139 162 cvpr-2013-FasT-Match: Fast Affine Template Matching
13 0.069583908 80 cvpr-2013-Category Modeling from Just a Single Labeling: Use Depth Information to Guide the Learning of 2D Models
14 0.06733074 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
15 0.066704877 46 cvpr-2013-Articulated and Restricted Motion Subspaces and Their Signatures
16 0.065398797 93 cvpr-2013-Constraints as Features
17 0.062270384 366 cvpr-2013-Robust Region Grouping via Internal Patch Statistics
18 0.058261894 301 cvpr-2013-Multi-target Tracking by Rank-1 Tensor Approximation
19 0.057980012 437 cvpr-2013-Towards Fast and Accurate Segmentation
20 0.057769906 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
topicId topicWeight
[(0, 0.133), (1, 0.035), (2, -0.007), (3, 0.021), (4, 0.045), (5, -0.019), (6, 0.0), (7, -0.052), (8, -0.061), (9, -0.019), (10, 0.052), (11, 0.078), (12, -0.076), (13, -0.028), (14, -0.002), (15, -0.088), (16, -0.021), (17, 0.022), (18, 0.054), (19, 0.012), (20, -0.004), (21, 0.0), (22, -0.004), (23, 0.013), (24, 0.082), (25, -0.036), (26, 0.026), (27, -0.033), (28, 0.022), (29, 0.058), (30, -0.005), (31, -0.002), (32, 0.044), (33, -0.08), (34, 0.064), (35, 0.074), (36, 0.023), (37, 0.015), (38, 0.059), (39, -0.031), (40, -0.008), (41, 0.055), (42, -0.001), (43, 0.042), (44, 0.036), (45, -0.049), (46, -0.049), (47, 0.031), (48, -0.042), (49, 0.017)]
simIndex simValue paperId paperTitle
same-paper 1 0.96206051 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.
2 0.8787691 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.
3 0.78408194 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.71561289 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.65554118 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
Author: Peng Wang, Chunhua Shen, Anton van_den_Hengel
Abstract: Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale problems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmentation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs.
6 0.65463072 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
7 0.63824373 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
8 0.63645285 107 cvpr-2013-Deformable Spatial Pyramid Matching for Fast Dense Correspondences
10 0.61712223 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
11 0.61639947 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
12 0.61449593 93 cvpr-2013-Constraints as Features
13 0.59792602 162 cvpr-2013-FasT-Match: Fast Affine Template Matching
14 0.59675711 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
15 0.58760303 190 cvpr-2013-Graph-Based Optimization with Tubularity Markov Tree for 3D Vessel Segmentation
16 0.58105278 110 cvpr-2013-Dense Object Reconstruction with Semantic Priors
17 0.58049947 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
18 0.57652724 361 cvpr-2013-Robust Feature Matching with Alternate Hough and Inverted Hough Transforms
19 0.57571805 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles
20 0.57355195 80 cvpr-2013-Category Modeling from Just a Single Labeling: Use Depth Information to Guide the Learning of 2D Models
topicId topicWeight
[(10, 0.122), (16, 0.027), (26, 0.049), (28, 0.031), (33, 0.258), (36, 0.012), (67, 0.054), (69, 0.033), (87, 0.086), (90, 0.224)]
simIndex simValue paperId paperTitle
1 0.92574912 409 cvpr-2013-Spectral Modeling and Relighting of Reflective-Fluorescent Scenes
Author: Antony Lam, Imari Sato
Abstract: Hyperspectral reflectance data allows for highly accurate spectral relighting under arbitrary illumination, which is invaluable to applications ranging from archiving cultural e-heritage to consumer product design. Past methods for capturing the spectral reflectance of scenes has proven successful in relighting but they all share a common assumption. All the methods do not consider the effects of fluorescence despite fluorescence being found in many everyday objects. In this paper, we describe the very different ways that reflectance and fluorescence interact with illuminants and show the need to explicitly consider fluorescence in the relighting problem. We then propose a robust method based on well established theories of reflectance and fluorescence for imaging each of these components. Finally, we show that we can relight real scenes of reflective-fluorescent surfaces with much higher accuracy in comparison to only considering the reflective component.
same-paper 2 0.8584103 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.82740051 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
Author: Bo Jiang, Chris Ding, Bio Luo, Jin Tang
Abstract: Principal Component Analysis (PCA) is a widely used to learn a low-dimensional representation. In many applications, both vector data X and graph data W are available. Laplacian embedding is widely used for embedding graph data. Wepropose a graph-Laplacian PCA (gLPCA) to learn a low dimensional representation of X that incorporates graph structures encoded in W. This model has several advantages: (1) It is a data representation model. (2) It has a compact closed-form solution and can be efficiently computed. (3) It is capable to remove corruptions. Extensive experiments on 8 datasets show promising results on image reconstruction and significant improvement on clustering and classification.
4 0.80028403 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
Author: Horst Possegger, Sabine Sternig, Thomas Mauthner, Peter M. Roth, Horst Bischof
Abstract: Combining foreground images from multiple views by projecting them onto a common ground-plane has been recently applied within many multi-object tracking approaches. These planar projections introduce severe artifacts and constrain most approaches to objects moving on a common 2D ground-plane. To overcome these limitations, we introduce the concept of an occupancy volume exploiting the full geometry and the objects ’ center of mass and develop an efficient algorithm for 3D object tracking. Individual objects are tracked using the local mass density scores within a particle filter based approach, constrained by a Voronoi partitioning between nearby trackers. Our method benefits from the geometric knowledge given by the occupancy volume to robustly extract features and train classifiers on-demand, when volumetric information becomes unreliable. We evaluate our approach on several challenging real-world scenarios including the public APIDIS dataset. Experimental evaluations demonstrate significant improvements compared to state-of-theart methods, while achieving real-time performance. – –
5 0.80014026 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
Author: Ian Endres, Kevin J. Shih, Johnston Jiaa, Derek Hoiem
Abstract: We propose a method to learn a diverse collection of discriminative parts from object bounding box annotations. Part detectors can be trained and applied individually, which simplifies learning and extension to new features or categories. We apply the parts to object category detection, pooling part detections within bottom-up proposed regions and using a boosted classifier with proposed sigmoid weak learners for scoring. On PASCAL VOC 2010, we evaluate the part detectors ’ ability to discriminate and localize annotated keypoints. Our detection system is competitive with the best-existing systems, outperforming other HOG-based detectors on the more deformable categories.
6 0.79906422 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
7 0.79764479 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
8 0.79739285 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
9 0.79726368 306 cvpr-2013-Non-rigid Structure from Motion with Diffusion Maps Prior
10 0.79662347 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
11 0.79607117 408 cvpr-2013-Spatiotemporal Deformable Part Models for Action Detection
12 0.79591078 143 cvpr-2013-Efficient Large-Scale Structured Learning
13 0.79550338 4 cvpr-2013-3D Visual Proxemics: Recognizing Human Interactions in 3D from a Single Image
14 0.79533619 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
15 0.79521292 414 cvpr-2013-Structure Preserving Object Tracking
16 0.79517817 206 cvpr-2013-Human Pose Estimation Using Body Parts Dependent Joint Regressors
17 0.79507601 14 cvpr-2013-A Joint Model for 2D and 3D Pose Estimation from a Single Image
18 0.79506767 19 cvpr-2013-A Minimum Error Vanishing Point Detection Approach for Uncalibrated Monocular Images of Man-Made Environments
19 0.79441828 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
20 0.7942754 325 cvpr-2013-Part Discovery from Partial Correspondence