Search

Feature correspondence lays the foundation for many computer vision and image processing tasks, which can be well formulated and solved by graph matching. Because of the high complexity, approximate methods are necessary for graph matching, and the continuous relaxation provides an efficient approximate scheme. But there are still many problems to be settled, such as the highly nonconvex objective function, the ignorance of the combinatorial nature of graph matching in the optimization process, and few attention to the outlier problem. Focusing on these problems, this paper introduces a continuation method directly targeting at the combinatorial optimization problem associated with graph matching. Specifically, first a regularization function incorporating the original objective function and the discrete constraints is proposed. Then a continuation method based on Gaussian smoothing is applied to it, in which the closed forms of relevant functions with respect to the outlier distribution are deduced. Experiments on both synthetic data and real world images validate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Graph matching is a fundamental problem in theoretical computer science and artificial intelligence, and lays the foundation for many computer vision and machine learning tasks. Approximate algorithms are necessary for graph matching due to its NP-complete nature. Inspired by the usage in network-related tasks, random walk is generalized to graph matching as a type of approximate algorithm. However, it may be inappropriate for the previous random walk-based graph matching algorithms to utilize continuous techniques without considering the discrete property. In this paper, we propose a novel random walk-based graph matching algorithm by incorporating both continuous and discrete constraints in the optimization process. Specifically, after interpreting graph matching by random walk, the continuous constraints are directly embedded in the random walk constraint in each iteration. Further, both the assignment matrix (vector) and the pairwise similarity measure between graphs are iteratively updated according the discrete constraints, which automatically leads the continuous solution to the discrete domain. Comparisons on both synthetic and real-world data demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Point correspondence problem is an important problem in pattern recognition and computer vision, which can be solved by graph matching. Recently, high order graph matching methods have attracted much attention due to their robustness to geometric transformations. Since high order graph matching usually suffers from high complexity, we previously proposed an adjacency tensor based algorithm, which effectively reduced the complexity of high order graph matching, especially high storage complexity. However, this method can only be applied to equal sized hypergraphs, and it cannot be directly extended to hypergraphs with outliers which are common in real world tasks. Aiming at this problem, in this paper we propose a third order subgraph matching method by extending our previous method to deal with partial point correspondence problem with outliers. Specifically, first a novel objective function focusing on the outlier problem is proposed, by encoding the attributes in a hypergraph with an adjacency tensor, and representing vertex assignments with a partial permutation matrix. Then the objective function is transformed and relaxed to a tractable matrix form and solved by a gradient based optimization algorithm. Consequently, the proposed algorithm can not only tackle the outlier vertices in the hypergraphs, but also involve the same low computational and storage complexities with our previous algorithm. Both synthetic data and real image comparisons with the state-of-the-art methods validate the effectiveness of the proposed method. • An adjacency tensor based sub-hypergraph matching algorithm is proposed. • It involves the lower computational and storage complexities than affinity tensor based high order algorithms. • Both synthetic data and real image comparisons with the state-of-the-art methods validate its effectiveness. [ABSTRACT FROM AUTHOR]

LibCoopt is an open-source matlab code library which provides a general and convenient tool to approximately solve the combinatorial optimization problems on the set of partial permutation matrices, which are frequently encountered in computer vision, bioinformatics, social analysis, etc. To use the library, the user needs only to give the objective function and its gradient function associated with the problem. Two typical problems, the subgraph matching problem and the quadratic assignment problem, are employed to illustrate how to use the library and also its flexibility on different types of problems. [ABSTRACT FROM AUTHOR]

Image stitching has long been studied in computer vision and has been applied to many fields. However, when the input images contain moving objects and meanwhile are noisy or partially contaminated, it remains a challenge to get a satisfactory clean panorama. In this paper, we propose to tackle both the challenges, i.e., denoising and stitching, by proposing a new energy function in a unified way. Such an energy model is however non-submodule, making the widely used optimization algorithms, such as graph cuts, hard to be used directly. We then generalize the recently proposed Graduated Non-Convexity and Concavity Procedure (GNCCP) to approximately minimize the energy. Comparative experiments validate the efficacy of the proposed energy function on both image denoising and stitching. Besides, the results also show the validity of the generalized-GNCCP on minimizing non-submodule function. [ABSTRACT FROM AUTHOR]

Graph matching is a fundamental problem in pattern recognition and computer vision. In this paper we introduce a novel graph matching algorithm to find the specified number of best vertex assignments between two labeled weighted graphs. The problem is first explicitly formulated as the minimization of a quadratic objective function and then solved by an optimization algorithm based on the recently proposed graduated nonconvexity and concavity procedure (GNCCP). Simulations on both synthetic data and real world images witness the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Feature correspondence lays the foundation for many tasks in computer vision and pattern recognition. In this paper the directed structural model is utilized to represent the feature set, and the correspondence problem is then formulated as the structural model matching. Compared with the undirected structural model, the proposed directed model provides more discriminating ability and invariance against rotation and scale transformations. Finally, the recently proposed convex–concave relaxation procedure (CCRP) is generalized to approximately solve the problem. Extensive experiments on synthetic and real data witness the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Graph matching is a fundamental problem in image processing and computer vision tasks, which can be used to solve the feature correspondence problem. Most graph matching tasks have been proved to be NP-Complete problems which are generally solved by approximate algorithms based on the continuous relaxation scheme. Targeting at these problems, this paper proposes a novel graph matching algorithm based on the alternating direction method of multipliers (ADMM) which typically decomposes a difficult problem into relatively simpler subproblems. Specifically, the matching constraints are decomposed into four continuous constraints and the assignment vector is decomposed into different vectors according to the constraints. Then the transformed objective function is iteratively optimized under the framework of ADMM. The proposed method achieves the state of the art performance, while maintaining a comparable computational complexity. And a discrete solution can be directly obtained without the projection process. Experimental results on both synthetic points and real images demonstrate the effectiveness of the proposed method by comparing it with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

• A graph matching method based on fast normalized cut and multiplicative update mapping is proposed. • The discrete constraint is incorporated into the optimization step and the multiplicative update algorithm is utilized in the mapping process. • Both synthetic points and real-world images comparisons with the state-of-the-art methods validate the effectiveness of the proposed method. Point correspondence is a fundamental problem in pattern recognition and computer vision, which can be tackled by graph matching. Since graph matching is basically an NP-complete problem, some approximate methods are proposed to solve it. Continuous relaxation offers an effective approximate method for graph matching problem. However, the discrete constraint is not taken into consideration in the optimization step. In this paper, a fast normalized cut based graph matching method is proposed, where the discrete constraint is introduced into the optimization step. Specifically, first a semidefinite positive affinity matrix based form objective function is constructed by introducing a regularization term which is related to the discrete constraint. Then the fast normalized cut algorithm is utilized to find the continuous solution. Last, the discrete solution of graph matching is obtained by a multiplicative update algorithm. Experiments on both synthetic points and real-world images validate the effectiveness of the proposed method by comparing it with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]