The Experts below are selected from a list of 45099 Experts worldwide ranked by ideXlab platform
Kyoung Mu Lee - One of the best experts on this subject based on the ideXlab platform.
-
ICCV - Discrete Tabu Search for Graph Matching
2015 IEEE International Conference on Computer Vision (ICCV), 2015Co-Authors: Kamil Adamczewski, Yumin Suh, Kyoung Mu LeeAbstract:Graph Matching is a fundamental problem in computer vision. In this paper, we propose a novel Graph Matching algorithm based on tabu search [13]. The proposed method solves Graph Matching problem by casting it into an equivalent weighted maximum clique problem of the corresponding association Graph, which we further penalize through introducing negative weights. Subsequent tabu search optimization allows for overcoming the convention of using positive weights. The method's distinct feature is that it utilizes the history of search to make more strategic decisions while looking for the optimal solution, thus effectively escaping local optima and in practice achieving superior results. The proposed method, unlike the existing algorithms, enables direct optimization in the original discrete space while encouraging rather than artificially enforcing hard one-to-one constraint, thus resulting in better solution. The experiments demonstrate the robustness of the algorithm in a variety of settings, presenting the state-of-the-art results. The code is available at http://cv.snu.ac.kr/research/~DTSGM/.
-
Graph Matching via Sequential Monte Carlo
2012Co-Authors: Yumin Suh, Minsu Cho, Kyoung Mu LeeAbstract:Graph Matching is a powerful tool for computer vision and machine learning. In this paper, a novel approach to Graph Matching is developed based on the sequential Monte Carlo framework. By constructing a sequence of intermediate target distributions, the proposed algorithm sequentially performs a sampling and importance resampling to maximize the Graph Matching objective. Through the sequential sampling procedure, the algorithm effectively collects potential matches under one-to-one Matching constraints to avoid the adverse effect of outliers and deformation. Experimental evaluations on synthetic Graphs and real images demonstrate its higher robustness to deformation and outliers.
-
ECCV (3) - Graph Matching via sequential monte carlo
Computer Vision – ECCV 2012, 2012Co-Authors: Yumin Suh, Minsu Cho, Kyoung Mu LeeAbstract:Graph Matching is a powerful tool for computer vision and machine learning. In this paper, a novel approach to Graph Matching is developed based on the sequential Monte Carlo framework. By constructing a sequence of intermediate target distributions, the proposed algorithm sequentially performs a sampling and importance resampling to maximize the Graph Matching objective. Through the sequential sampling procedure, the algorithm effectively collects potential matches under one-to-one Matching constraints to avoid the adverse effect of outliers and deformation. Experimental evaluations on synthetic Graphs and real images demonstrate its higher robustness to deformation and outliers.
-
Hyper-Graph Matching via reweighted random walks
Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2011Co-Authors: Jungmin Lee, Minsu Cho, Kyoung Mu LeeAbstract:Establishing correspondences between two feature sets is a fundamental issue in computer vision, pattern recognition, and machine learning. This problem can be well formulated as Graph Matching in which nodes represent feature points while edges describe pairwise relations between feature points. Recently, several researches have tried to embed higher-order relations of feature points by hyper-Graph Matching formulations. In this paper, we generalize the previous hyper-Graph Matching formulations to cover relations of features in arbitrary orders, and propose a novel state-of-the-art algorithm by reinterpreting the random walk concept on the hyper-Graph in a probabilistic manner. Adopting personalized jumps with a reweighting scheme, the algorithm effectively reflects the one-to-one Matching constraints during the random walk process. Comparative experiments on synthetic data and real images show that the proposed method clearly outperforms existing algorithms especially in the presence of noise and outliers.
-
Reweighted random walks for Graph Matching
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010Co-Authors: Minsu Cho, Jungmin Lee, Kyoung Mu LeeAbstract:Graph Matching is an essential problem in computer vision and machine learning. In this paper, we introduce a random walk view on the problem and propose a robust Graph Matching algorithm against outliers and deformation. Matching between two Graphs is formulated as node selection on an association Graph whose nodes represent candidate correspondences between the two Graphs. The solution is obtained by simulating random walks with reweighting jumps enforcing the match- ing constraints on the association Graph. Our algorithm achieves noise- robust Graph Matching by iteratively updating and exploiting the con- dences of candidate correspondences. In a practical sense, our work is of particular importance since the real-world Matching problem is made dicult by the presence of noise and outliers. Extensive and comparative experiments demonstrate that it outperforms the state-of-the-art Graph Matching algorithms especially in the presence of outliers and deformation.
Barend J Van Wyk - One of the best experts on this subject based on the ideXlab platform.
-
A LEARNING-BASED FRAMEWORK FOR Graph Matching
International Journal of Pattern Recognition and Artificial Intelligence, 2004Co-Authors: Michael Antonie Van Wyk, Barend J Van WykAbstract:This paper presents a unifying review of a learning-based framework for kernel-based attributed Graph Matching. The framework, which includes as special cases the RKHS Interplator-Based Graph Matching (RIGM) and Interpolator-Based Kronecker Product Graph Matching (IBKPGM) algorithms, incorporates a general approach where no assumption is made about the adjacency structure of the Graphs to be matched. Corresponding pairs of attributed adjacency matrices and attribute vectors of an input and reference Graph are used as the input–output training set of a constrained multi-input multi-output multi-variable mapping to be learned. It is shown that a Reproducing Kernel Hilbert Space (RKHS) based interpolator can be used to infer this mapping. Partially constraining the inferred mapping by the generation of additional consistency input–output training pairs and the use of polynomial feature augmentation lead to improved performance. The proposed learning-based framework avoids the explicit calculation of compatibility values.
-
Kronecker product Graph Matching
Pattern Recognition, 2003Co-Authors: Barend J Van Wyk, Michael Antonie Van WykAbstract:Abstract In this paper the Interpolator-based Kronecker product Graph Matching (IBKPGM) algorithm for performing attributed Graph Matching is presented. The IBKPGM algorithm is based on the Kronecker product Graph Matching (KPGM) formulation. This new formulation incorporates a general approach to a wide class of Graph Matching problems based on attributed Graphs, allowing the structure of the Graphs to be based on multiple sets of attributes. Salient features of the IBKPGM algorithm are that no assumption is made about the adjacency structure of the Graphs to be matched, and that the explicit calculation of compatibility values between all vertices of the reference and input Graphs as well as between all edges of the reference and input Graphs are avoided.
-
SSPR/SPR - Successive Projection Graph Matching
Lecture Notes in Computer Science, 2002Co-Authors: Barend J Van Wyk, Michaël A. Van Wyk, H. E. HanrahanAbstract:The Successive Projection Graph Matching (SPGM) algorithm, capable of performing full- and sub-Graph Matching, is presented in this paper. Projections Onto Convex Sets (POCS) methods have been successfully applied to signal processing applications, image enhancement, neural networks and optics. The SPGM algorithm is unique in the way a constrained cost function is minimized using POCS methodology. Simulation results indicate that the SPGM algorithm compares favorably to other well-known Graph Matching algorithms.
-
A RKHS interpolator-based Graph Matching algorithm
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002Co-Authors: Michael Antonie Van Wyk, Tariq S Durrani, Barend J Van WykAbstract:We present an algorithm for performing attributed Graph Matching. This algorithm is derived from a generalized framework for describing functionally expanded interpolators which is based on the theory of reproducing kernel Hilbert spaces (RKHS). The algorithm incorporates a general approach to a wide class of Graph Matching problems based on attributed Graphs, allowing the structure of the Graphs to be based on multiple sets of attributes. No assumption is made about the adjacency structure of the Graphs to be matched
-
The Approximate Successive Projection Graph Matching algorithm
2002Co-Authors: Barend J Van Wyk, Michael Antonie Van WykAbstract:The Approximate Successive Projection Graph Matching (SPGM-A) algorithm, capable of performing full- and sub-Graph Matching, is presented in this paper. Projections Onto Convex Sets (POCS) methods have been successfully applied to signal processing applications, image enhancement, neural networks and optics. The SPGM-A algorithm is unique in the way a constrained cost function is minimized using an approximate POCS methodology. Simulation results indicate that the SPGM-A algorithm compares favourably with other well-known Graph Matching algorithms.
Bin Luo - One of the best experts on this subject based on the ideXlab platform.
-
binary constraint preserving Graph Matching
Computer Vision and Pattern Recognition, 2017Co-Authors: Bo Jiang, Jin Tang, Chris Ding, Bin LuoAbstract:Graph Matching is a fundamental problem in computer vision and pattern recognition area. In general, it can be formulated as an Integer Quadratic Programming (IQP) problem. Since it is NP-hard, approximate relaxations are required. In this paper, a new Graph Matching method has been proposed. There are three main contributions of the proposed method: (1) we propose a new Graph Matching relaxation model, called Binary Constraint Preserving Graph Matching (BPGM), which aims to incorporate the discrete binary mapping constraints more in Graph Matching relaxation. Our BPGM is motivated by a new observation that the discrete binary constraints in IQP Matching problem can be represented (or encoded) exactly by a l2-norm constraint. (2) An effective projection algorithm has been derived to solve BPGM model. (3) Using BPGM, we propose a path-following strategy to optimize IQP Matching problem and thus obtain a desired discrete solution at convergence. Promising experimental results show the effectiveness of the proposed method.
-
CVPR - Binary Constraint Preserving Graph Matching
2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017Co-Authors: Bo Jiang, Jin Tang, Chris Ding, Bin LuoAbstract:Graph Matching is a fundamental problem in computer vision and pattern recognition area. In general, it can be formulated as an Integer Quadratic Programming (IQP) problem. Since it is NP-hard, approximate relaxations are required. In this paper, a new Graph Matching method has been proposed. There are three main contributions of the proposed method: (1) we propose a new Graph Matching relaxation model, called Binary Constraint Preserving Graph Matching (BPGM), which aims to incorporate the discrete binary mapping constraints more in Graph Matching relaxation. Our BPGM is motivated by a new observation that the discrete binary constraints in IQP Matching problem can be represented (or encoded) exactly by a l2-norm constraint. (2) An effective projection algorithm has been derived to solve BPGM model. (3) Using BPGM, we propose a path-following strategy to optimize IQP Matching problem and thus obtain a desired discrete solution at convergence. Promising experimental results show the effectiveness of the proposed method.
-
Lagrangian relaxation Graph Matching
Pattern Recognition, 2017Co-Authors: Bo Jiang, Jin Tang, Xiaochun Cao, Bin LuoAbstract:Abstract Graph Matching is a fundamental problem in computer vision area. Graph Matching problem that incorporates pair-wise constraints can be formulated as an integer quadratic programming (IQP) problem with affine mapping constraint. Since it is known to be NP-hard, approximate relaxation methods are usually required to find approximate solutions. In this paper, we present a new effective Graph Matching relaxation method, called Lagrangian relaxation Graph Matching (LRGM), which aims to generate a relaxation model by incorporating the affine mapping constraint into the Matching objective optimization. There are three main benefits of the proposed LRGM method: (1) The nonnegative affine mapping constraint encoding one-to-one mapping is naturally incorporated in LRGM relaxation via Lagrangian regularization. (2) By further adding a l 1 -norm constraint, LRGM can generate a sparse solution empirically and thus returns a desired discrete solution for original IQP Matching problem. (3) An effective update algorithm is derived to solve the proposed LRGM model. Theoretically, the converged solution can be proven to be Karush–Kuhn–Tucker (KKT) optimal. Experimental results on both synthetic data and real-world image datasets show the effectiveness and benefits of the proposed LRGM method.
-
A sparse nonnegative matrix factorization technique for Graph Matching problems
Pattern Recognition, 2014Co-Authors: Bo Jiang, Jin Tang, Haifeng Zhao, Bin LuoAbstract:Graph Matching problem that incorporates pairwise constraints can be cast as an Integer Quadratic Programming (IQP). Since it is NP-hard, approximate methods are required. In this paper, a new approximate method based on nonnegative matrix factorization with sparse constraints is presented. Firstly, the Graph Matching is formulated as an optimization problem with nonnegative and sparse constraints, followed by an efficient algorithm to solve this constrained problem. Then, we show the strong relationship between the sparsity of the relaxation solution and its effectiveness for Graph Matching based on our model. A key benefit of our method is that the solution is sparse and thus can approximately impose the one-to-one mapping constraints in the optimization process naturally. Therefore, our method can approximate the original IQP problem more closely than other approximate methods. Extensive and comparative experimental results on both synthetic and real-world data demonstrate the effectiveness of our Graph Matching method. We present a Graph Matching method based on NMF with sparse constraints.Our sparse model can incorporate the mapping constraints approximately.We show the link between the sparsity of the solution and its effectiveness.Experimental results show the effectiveness of our Graph Matching method.
-
GbRPR - Graph Matching with Nonnegative Sparse Model
Graph-Based Representations in Pattern Recognition, 2013Co-Authors: Bo Jiang, Jin Tang, Bin LuoAbstract:Graph Matching is an essential problem in computer vision and pattern recognition. In this paper, we propose a novel Graph Matching method based on non-negative sparse model (NSGM). The main feature for our NSGM is that it can generate sparse solution and thus naturally imposes the discrete mapping constraints approximately in the optimization process. In addition, an efficient algorithm was derived to solve NSGM problem. Promising experimental results on both synthetic and real image Matching tasks show the effectiveness of the proposed Matching method.
Michael Antonie Van Wyk - One of the best experts on this subject based on the ideXlab platform.
-
A LEARNING-BASED FRAMEWORK FOR Graph Matching
International Journal of Pattern Recognition and Artificial Intelligence, 2004Co-Authors: Michael Antonie Van Wyk, Barend J Van WykAbstract:This paper presents a unifying review of a learning-based framework for kernel-based attributed Graph Matching. The framework, which includes as special cases the RKHS Interplator-Based Graph Matching (RIGM) and Interpolator-Based Kronecker Product Graph Matching (IBKPGM) algorithms, incorporates a general approach where no assumption is made about the adjacency structure of the Graphs to be matched. Corresponding pairs of attributed adjacency matrices and attribute vectors of an input and reference Graph are used as the input–output training set of a constrained multi-input multi-output multi-variable mapping to be learned. It is shown that a Reproducing Kernel Hilbert Space (RKHS) based interpolator can be used to infer this mapping. Partially constraining the inferred mapping by the generation of additional consistency input–output training pairs and the use of polynomial feature augmentation lead to improved performance. The proposed learning-based framework avoids the explicit calculation of compatibility values.
-
Kronecker product Graph Matching
Pattern Recognition, 2003Co-Authors: Barend J Van Wyk, Michael Antonie Van WykAbstract:Abstract In this paper the Interpolator-based Kronecker product Graph Matching (IBKPGM) algorithm for performing attributed Graph Matching is presented. The IBKPGM algorithm is based on the Kronecker product Graph Matching (KPGM) formulation. This new formulation incorporates a general approach to a wide class of Graph Matching problems based on attributed Graphs, allowing the structure of the Graphs to be based on multiple sets of attributes. Salient features of the IBKPGM algorithm are that no assumption is made about the adjacency structure of the Graphs to be matched, and that the explicit calculation of compatibility values between all vertices of the reference and input Graphs as well as between all edges of the reference and input Graphs are avoided.
-
A RKHS interpolator-based Graph Matching algorithm
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002Co-Authors: Michael Antonie Van Wyk, Tariq S Durrani, Barend J Van WykAbstract:We present an algorithm for performing attributed Graph Matching. This algorithm is derived from a generalized framework for describing functionally expanded interpolators which is based on the theory of reproducing kernel Hilbert spaces (RKHS). The algorithm incorporates a general approach to a wide class of Graph Matching problems based on attributed Graphs, allowing the structure of the Graphs to be based on multiple sets of attributes. No assumption is made about the adjacency structure of the Graphs to be matched
-
The Approximate Successive Projection Graph Matching algorithm
2002Co-Authors: Barend J Van Wyk, Michael Antonie Van WykAbstract:The Approximate Successive Projection Graph Matching (SPGM-A) algorithm, capable of performing full- and sub-Graph Matching, is presented in this paper. Projections Onto Convex Sets (POCS) methods have been successfully applied to signal processing applications, image enhancement, neural networks and optics. The SPGM-A algorithm is unique in the way a constrained cost function is minimized using an approximate POCS methodology. Simulation results indicate that the SPGM-A algorithm compares favourably with other well-known Graph Matching algorithms.
Bo Jiang - One of the best experts on this subject based on the ideXlab platform.
-
binary constraint preserving Graph Matching
Computer Vision and Pattern Recognition, 2017Co-Authors: Bo Jiang, Jin Tang, Chris Ding, Bin LuoAbstract:Graph Matching is a fundamental problem in computer vision and pattern recognition area. In general, it can be formulated as an Integer Quadratic Programming (IQP) problem. Since it is NP-hard, approximate relaxations are required. In this paper, a new Graph Matching method has been proposed. There are three main contributions of the proposed method: (1) we propose a new Graph Matching relaxation model, called Binary Constraint Preserving Graph Matching (BPGM), which aims to incorporate the discrete binary mapping constraints more in Graph Matching relaxation. Our BPGM is motivated by a new observation that the discrete binary constraints in IQP Matching problem can be represented (or encoded) exactly by a l2-norm constraint. (2) An effective projection algorithm has been derived to solve BPGM model. (3) Using BPGM, we propose a path-following strategy to optimize IQP Matching problem and thus obtain a desired discrete solution at convergence. Promising experimental results show the effectiveness of the proposed method.
-
CVPR - Binary Constraint Preserving Graph Matching
2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017Co-Authors: Bo Jiang, Jin Tang, Chris Ding, Bin LuoAbstract:Graph Matching is a fundamental problem in computer vision and pattern recognition area. In general, it can be formulated as an Integer Quadratic Programming (IQP) problem. Since it is NP-hard, approximate relaxations are required. In this paper, a new Graph Matching method has been proposed. There are three main contributions of the proposed method: (1) we propose a new Graph Matching relaxation model, called Binary Constraint Preserving Graph Matching (BPGM), which aims to incorporate the discrete binary mapping constraints more in Graph Matching relaxation. Our BPGM is motivated by a new observation that the discrete binary constraints in IQP Matching problem can be represented (or encoded) exactly by a l2-norm constraint. (2) An effective projection algorithm has been derived to solve BPGM model. (3) Using BPGM, we propose a path-following strategy to optimize IQP Matching problem and thus obtain a desired discrete solution at convergence. Promising experimental results show the effectiveness of the proposed method.
-
Lagrangian relaxation Graph Matching
Pattern Recognition, 2017Co-Authors: Bo Jiang, Jin Tang, Xiaochun Cao, Bin LuoAbstract:Abstract Graph Matching is a fundamental problem in computer vision area. Graph Matching problem that incorporates pair-wise constraints can be formulated as an integer quadratic programming (IQP) problem with affine mapping constraint. Since it is known to be NP-hard, approximate relaxation methods are usually required to find approximate solutions. In this paper, we present a new effective Graph Matching relaxation method, called Lagrangian relaxation Graph Matching (LRGM), which aims to generate a relaxation model by incorporating the affine mapping constraint into the Matching objective optimization. There are three main benefits of the proposed LRGM method: (1) The nonnegative affine mapping constraint encoding one-to-one mapping is naturally incorporated in LRGM relaxation via Lagrangian regularization. (2) By further adding a l 1 -norm constraint, LRGM can generate a sparse solution empirically and thus returns a desired discrete solution for original IQP Matching problem. (3) An effective update algorithm is derived to solve the proposed LRGM model. Theoretically, the converged solution can be proven to be Karush–Kuhn–Tucker (KKT) optimal. Experimental results on both synthetic data and real-world image datasets show the effectiveness and benefits of the proposed LRGM method.
-
A sparse nonnegative matrix factorization technique for Graph Matching problems
Pattern Recognition, 2014Co-Authors: Bo Jiang, Jin Tang, Haifeng Zhao, Bin LuoAbstract:Graph Matching problem that incorporates pairwise constraints can be cast as an Integer Quadratic Programming (IQP). Since it is NP-hard, approximate methods are required. In this paper, a new approximate method based on nonnegative matrix factorization with sparse constraints is presented. Firstly, the Graph Matching is formulated as an optimization problem with nonnegative and sparse constraints, followed by an efficient algorithm to solve this constrained problem. Then, we show the strong relationship between the sparsity of the relaxation solution and its effectiveness for Graph Matching based on our model. A key benefit of our method is that the solution is sparse and thus can approximately impose the one-to-one mapping constraints in the optimization process naturally. Therefore, our method can approximate the original IQP problem more closely than other approximate methods. Extensive and comparative experimental results on both synthetic and real-world data demonstrate the effectiveness of our Graph Matching method. We present a Graph Matching method based on NMF with sparse constraints.Our sparse model can incorporate the mapping constraints approximately.We show the link between the sparsity of the solution and its effectiveness.Experimental results show the effectiveness of our Graph Matching method.
-
GbRPR - Graph Matching with Nonnegative Sparse Model
Graph-Based Representations in Pattern Recognition, 2013Co-Authors: Bo Jiang, Jin Tang, Bin LuoAbstract:Graph Matching is an essential problem in computer vision and pattern recognition. In this paper, we propose a novel Graph Matching method based on non-negative sparse model (NSGM). The main feature for our NSGM is that it can generate sparse solution and thus naturally imposes the discrete mapping constraints approximately in the optimization process. In addition, an efficient algorithm was derived to solve NSGM problem. Promising experimental results on both synthetic and real image Matching tasks show the effectiveness of the proposed Matching method.
