Second- and High-Order Graph Matching for Correspondence Problems
| Autor: | Zhang Ruonan, Wenmin Wang |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Factor-critical graph
Hypergraph Optimization problem Matching (graph theory) Computer science 02 engineering and technology 010501 environmental sciences 01 natural sciences Distance-regular graph Simplex graph law.invention Coxeter graph Graph power law String graph 3-dimensional matching Line graph 0202 electrical engineering electronic engineering information engineering Media Technology Folded cube graph Electrical and Electronic Engineering Graph property Complement graph 0105 earth and related environmental sciences Voltage graph Quartic graph Butterfly graph Graph Petersen graph Bipartite graph Graph (abstract data type) Cubic graph 020201 artificial intelligence & image processing Null graph Graph factorization Algorithm |
| Zdroj: | IEEE Transactions on Circuits and Systems for Video Technology. 28:2978-2992 |
| ISSN: | 1558-2205 1051-8215 |
| Popis: | Correspondence problems are challenging due to the complexity of real-world scenes. One way to solve this problem is to improve the graph matching (GM) process, which is flexible for matching non-rigid objects. GM can be classified into three categories that correspond with the variety of object functions: first-order, second-order, and high-order matching. Graph and hypergraph matching have been proposed separately in previous works. The former is equivalent to the second-order GM, and the latter is equivalent to high-order GM, but we use the terms second- and high-order GM to unify the terminology in this paper. Second- and high-order GM fit well with different types of problems; the key goal for these processes is to find better-optimized algorithms. Because the optimal problems for second- and high-order GM are different, we propose two novel optimized algorithms for them in this paper. (1) For the second-order GM, we first introduce a $K$ -nearest-neighbor-pooling matching method that integrates feature pooling into GM and reduces the complexity. Meanwhile, we evaluate each matching candidate using discriminative weights on its $k$ -nearest neighbors by taking locality as well as sparsity into consideration. (2) High-order GM introduces numerous outliers, because precision is rarely considered in related methods. Therefore, we propose a sub-pattern structure to construct a robust high-order GM method that better integrates geometric information. To narrow the search space and solve the optimization problem, a new prior strategy and a cell-algorithm-based Markov Chain Monte Carlo framework are proposed. In addition, experiments demonstrate the robustness and improvements of these algorithms with respect to matching accuracy compared with other state-of-the-art algorithms. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|