Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows the use of higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.
The graph resp. hypergraph matching problem is known to be NP-hard except for special cases where polynomial-time algorithms exist for planar graphs @cite_33 . In order to make the problem computationally tractable, a myriad of approximate algorithms have been proposed over the last three decades aiming at an acceptable trade-off between the complexity of the algorithm and matching accuracy. They can be categorized from different perspectives and we refer to @cite_26 @cite_10 for an extensive review. In this section, we review only those approximate algorithms that use Lawler's formulations for both graph and hypergraph matching as they are closely related to our work. In particular, the graph matching problem can be formulated as a quadratic assignment problem (QAP) @math while the hypergraph matching problem is formulated as a higher-order assignment problem (HAP) @math In these formulations, @math and @math refer to the affinity matrix and affinity tensor respectively, and @math is some matching constraint set depending on specific applications. Also, depending on whether the problem is graph matching or hypergraph matching, the corresponding algorithms will be called second-order methods or higher-order methods.
@cite_26 @cite_10 @cite_33
2109294083 2046021036
A recent paper posed the question: "Graph Matching: What are we really talking about?". Far from providing a definite answer to that question, in this paper we will try to characterize the role that graphs play within the Pattern Recognition field. To this aim two taxonomies are presented and discussed. The first includes almost all the graph matching algorithms proposed from the late seventies, and describes the different classes of algorithms. The second taxonomy considers the types of common applications of graph-based techniques in the Pattern Recognition and Machine Vision field. The isomorphism problem for graphs G 1 and G 2 is to determine if there exists a one-to-one mapping of the vertices of G 1 onto the vertices of G 2 such that two vertices of G 1 are adjacent if and only if their images in G 2 are adjacent. In addition to determining the existence of such an isomorphism, it is useful to be able to produce an isomorphism-inducing mapping in the case where one exists. The isomorphism problem for triconnected planar graphs is particularly simple since a triconnected planar graph has a unique embedding on a sphere [6]. Weinberg [5] exploited this fact in developing an algorithm for testing isomorphism of triconnected planar graphs in O(|V| 2 ) time where V is the set consisting of the vertices of both graphs. The result has been extended to arbitrary planar graphs and improved to O(|V|log|V|) steps by Hopcroft and Tarjan [2,3]. In this paper, the time bound for planar graph isomorphism is improved to O(|V|). In addition to determining the isomorphism of two planar graphs, the algorithm can be easily extended to partition a set of planar graphs into equivalence classes of isomorphic graphs in time linear in the total number of vertices in all graphs in the set. A random access model of computation (see Cook [1]) is assumed. Although the proposed algorithm has a linear asymptotic growth rate, at the present stage of development it appears to be inefficient on account of a rather large constant. This paper is intended only to establish the existence of a linear algorithm which subsequent work might make truly efficient.