Name
Abstract | ||
|---|---|---|
In this paper, we consider the approximate weighted graph matching problem and introduce stable and informative first and second order compatibility terms suitable for inclusion into the popular integer quadratic program formulation. Our approach relies on a rigorous analysis of stability of spectral signatures based on the graph Laplacian. In the case of the first order term, we derive an objective function that measures both the stability and informativeness of a given spectral signature. By optimizing this objective, we design new spectral node signatures tuned to a specific graph to be matched. We also introduce the pairwise heat kernel distance as a stable second order compatibility term, we justify its plausibility by showing that in a certain limiting case it converges to the classical adjacency matrix-based second order compatibility function. We have tested our approach on a set of synthetic graphs, the widely-used CMU house sequence, and a set of real images. These experiments show the superior performance of our first and second order compatibility terms as compared with the commonly used ones. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/CVPR.2014.296 | CVPR |
Keywords | Field | DocType |
spectral node signatures,graph laplacian,image matching,quadratic programming,informative spectral signatures,pairwise heat kernel distance,spectral signature,cmu house sequence,objective function,weighted graph matching problem,matrix algebra,integer programming,spectral analysis,realistic images,adjacency matrix-based second order compatibility function,second order compatibility term,first order compatibility,graph theory,integer quadratic program formulation,real images,synthetic graphs,stability analysis,upper bound,heating,kernel,optimization | Comparability graph,Spectral graph theory,Computer science,Graph bandwidth,Artificial intelligence,Quadratic programming,Adjacency matrix,Discrete mathematics,Laplacian matrix,Graph energy,Pattern recognition,Algorithm,Matching (graph theory) | Conference |
ISSN | Citations | PageRank |
1063-6919 | 6 | 0.46 |
References | Authors | |
37 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nan Hu | 1 | 59 | 14.04 |
| Raif M. Rustamov | 2 | 251 | 19.58 |
| Leonidas J. Guibas | 3 | 13084 | 1262.73 |