Branching Path Following for Graph Matching
Recently, graph matching algorithms utilizing the path following strategy have exhibited state-of-the-art performances. However, the paths computed in these algorithms often contain singular points, which usually hurt the matching performance. To deal wit
- PDF / 4,983,312 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 85 Downloads / 220 Views
Meitu HiScene Lab, HiScene Information Technologies, Shanghai, China [email protected] 2 School of Computer and Information Technology, Beijing Jiaotong University, Beijing, China {cylang,wuj}@bjtu.edu.cn 3 Computer and Information Sciences Department, Temple University, Philadelphia, USA [email protected] Abstract. Recently, graph matching algorithms utilizing the path following strategy have exhibited state-of-the-art performances. However, the paths computed in these algorithms often contain singular points, which usually hurt the matching performance. To deal with this issue, in this paper we propose a novel path following strategy, named branching path following (BPF), which consequently improves graph matching performance. In particular, we first propose a singular point detector by solving an KKT system, and then design a branch switching method to seek for better paths at singular points. Using BPF, a new graph matching algorithm named BPF-G is developed by applying BPF to a recently proposed path following algorithm named GNCCP (Liu &Qiao 2014). For evaluation, we compare BPF-G with several recently proposed graph matching algorithms on a synthetic dataset and four public benchmark datasets. Experimental results show that our approach achieves remarkable improvement in matching accuracy and outperforms other algorithms. Keywords: Graph matching · Path following tion · Singular point · Branch switching
1
·
Numerical continua-
Introduction
Graph matching is a fundamental problem in computer science and closely relates to many computer vision problems including feature registration [1–3], shape matching [4–6], object recognition [7,8], visual tracking [9], activity analysis [10], etc. Despite decades of research effort devoted to graph matching, it remains a challenging problem due to the non-convexity in the objective function and the constraints over the solutions. A typical way is to utilize relaxation to harness the solution searching. Popular algorithms include, but not limited to, three categories: spectral relaxation [11–13], continuous optimization [14–18] and probabilistic modeling [19,20]. Among recently proposed graph matching algorithms, the ones utilizing the path-following strategy have exhibited state-of-the-art performances [15–18]. c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part II, LNCS 9906, pp. 508–523, 2016. DOI: 10.1007/978-3-319-46475-6 32
Branching Path Following for Graph Matching
509
These path following algorithms reformulate graph matching as a convex-concave relaxation procedure (CCRP) problem, which is solved by interpolating between two simpler approximate formulations, and they use the path following strategy to recast iteratively the bistochastic matrix solution in the discrete domain. The path following algorithms can be viewed as special cases of the numerical continuation method (NCM) [21], which computes approximate solutions of parameterized nonlinear equation systems. These algorithms succeed at regular points but may fail at
Data Loading...
