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]

Summary: Image stitching is important for the perception and manipulation of undersea robots. In spite of a well-developed technique, it is still challenging for undersea images because of their inevitable appearance ambiguity caused by the limited light in the undersea environment, and local disturbance caused by moving objects, ocean current, etc. To get a clean and stable background panorama in the undersea environment, this paper proposes an undersea image-stitching method by introducing graph-based registration and blending procedures. Specifically, in the registration procedure, matching the features in each undersea image pair is formulated and solved by graph matching, to incorporate the structural information between features. In the blending procedure, an energy function on the indirect graph Markov random field is proposed, which takes both image consistency and neighboring consistency into consideration. Coincidentally, both graph matching and energy minimization can be mathematically formulated by integer quadratic programming problems with different constraints; the recently proposed graduated nonconvexity and concavity procedure is used to optimize both problems. Experiments on both synthetic images and real-world undersea images witness the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we propose a concavely regularized convex relaxation based graph matching algorithm. The graph matching problem is firstly formulated as a constrained convex quadratic program by relaxing the feasible set from the permutation matrices to doubly stochastic matrices. To gradually push the doubly stochastic matrix back to be a permutation one, an objective function is constructed by adding a simple weighted concave regularization to the convex relaxation. By gradually increasing the weight of the concave term, minimization of the objective function will gradually push the doubly stochastic matrix back to be a permutation one. A concave–convex procedure (CCCP) together with the Frank–Wolfe algorithm is adopted to minimize the objective function. The algorithm can be used on any types of graphs and exhibits a comparable performance as the PATH following algorithm, a state-of-the-art graph matching algorithm but applicable only on undirected graphs. [Copyright &y& Elsevier]

The correspondence between point sets is a fundamental problem in pattern recognition, which is often formulated and solved by graph matching. In this paper, we propose to solve the correspondence problem by a new third order graph matching algorithm. Compared with some previous hyper-graph matching algorithms, the proposed one achieves considerable memory reduction and is applicable to both undirected and directed graphs. Specifically, the correspondence is formulated by the matching between adjacency tensors encoding the third order structural information of each graph, which is then transformed to be a tractable matrix form. Two types of gradient based optimization methods, the graduated nonconvexity and concavity procedure (GNCCP) and graduated assignment (GA) algorithm, are generalized to solve the problem. Comparative experiments with state-of-the-art algorithms on both synthetic and real data witness the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

The path following algorithm was proposed recently to approximately solve the matching problems on undirected graph models and exhibited a state-of-the-art performance on matching accuracy. In this paper, we extend the path following algorithm to the matching problems on directed graph models by proposing a concave relaxation for the problem. Based on the concave and convex relaxations, a series of objective functions are constructed, and the Frank-Wolfe algorithm is then utilized to minimize them. Several experiments on synthetic and real data witness the validity of the extended path following algorithm. [ABSTRACT FROM PUBLISHER]

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]

This paper aims to solve the keypoint correspondence problem in lunar surface images, a typical correspondence task under point ambiguity. Point ambiguity may be caused by repetitive patterns, cluttered scenes, and outliers in the images, which makes the local descriptors less discriminative. In this paper we introduce locally affine-invariance constraints on graphs to tackle the keypoint correspondence problem under point ambiguity. The key idea is that each point can be represented with the affine combination of its neighbors. It is suitable for our problem because it is not only invariant to scale and rotational change, but also more resistant to outliers. Specifically, we introduce the locally affine-invariance constraints into the subgraph matching problem and the common subgraph matching problem. The locally affine-invariance constraint is not directly applicable on common subgraph matching due to its dependency on awareness of selected keypoints. This problem is approximately addressed by solving a series of reliable matching identification and rematching problems. In the experiments, we first apply the proposed method on standard graph matching datasets to evaluate its effectiveness on general correspondence problem under point ambiguity, and second validate the applicability on the lunar surface image dataset. [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]