Feature Matching via Topology-Aware Graph Interaction Model

Feature matching plays a key role in computer vision. However, due to the limitations of the descriptors, the putative matches are inevitably contaminated by massive outliers.This paper attempts to tackle the outlier filtering problem from two aspects. First, a robust and efficient graph interaction model,is proposed, with the assumption that matches are correlated with each other rather than independently distributed. To this end, we construct a graph based on the local relationships of matches and formulate the outlier filtering task as a binary labeling energy minimization problem, where the pairwise term encodes the interaction between matches. We further show that this formulation can be solved globally by graph cut algorithm. Our new formulation always improves the performance of previous localitybased method without noticeable deterioration in processing time,adding a few milliseconds. Second, to construct a better graph structure, a robust and geometrically meaningful topology-aware relationship is developed to capture the topology relationship between matches. The two components in sum lead to topology interaction matching(TIM), an effective and efficient method for outlier filtering. Extensive experiments on several large and diverse datasets for multiple vision tasks including general feature matching, as well as relative pose estimation, homography and fundamental matrix estimation, loop-closure detection, and multi-modal image matching, demonstrate that our TIM is more competitive than current state-of-the-art methods, in terms of generality, efficiency, and effectiveness. The source code is publicly available at http://github.com/YifanLu2000/TIM.

Perfect 1-k Matchings of Bipartite Graphs

Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.

Matching spatial relation graphs using a constrained partial permutation strategy

A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n 2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.

A Study on Short Text Matching Method Based on KS-BERT Algorithm

To improve the accuracy of short text matching,a short text matching method with knowledge and structure enhancement for BERT(KS-BERT)was proposed in this study.This method first introduced external knowledge to the input text,and then sent the expanded text to both the context encoder BERT and the structure encoder GAT to capture the contextual relationship features and structural features of the input text.Finally,the match was determined based on the fusion result of the two features.Experiment results based on the public datasets BQ_corpus and LCQMC showed that KS-BERT outperforms advanced models such as ERNIE 2.0.This Study showed that knowledge enhancement and structure enhancement are two effective ways to improve BERT in short text matching.In BQ_corpus,ACC was improved by 0.2%and 0.3%,respectively,while in LCQMC,ACC was improved by 0.4%and 0.9%,respectively.

A Novel Symbolic Algorithm for Maximum Weighted Matching in Bipartite Graphs

The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.

Subgraph Matching Using Graph Neural Network

Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph may contain many subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the target graph along with its characteristics. The simulation results show that GNN is capable of identifying a target sub-graph in a graph.

Multi-scale Graph-matching Based Kernel for Character Recognition from Natural Scenes

认出从自然景色图象提取的字符由于 intraclass 变化的高度是相当挑战性的。在这份报纸，我们为景色特性识别建议一个多尺度的匹配图的基于的核。以便捕获人物的内在地特殊的结构，每幅图象被与多尺度的图象格子联系的几张图代表。当也越过邻近的节点保存空间一致性时，二幅图象的类似被匹配二张图(图象) 因此定义为最佳精力，它在图为每个节点发现最好的火柴。计算类似是合适的为支持向量机器(SVM ) 构造一个核。与多尺度的格子匹配图获得的多重核被联合以便最后的核是更柔韧的。挑战性的 Chars74k 和 ICDAR03-CH 数据集上的试验性的结果证明建议方法比现状方法更好表现。

ENTIRE CHROMATIC NUMBER AND Δ-MATCHING OF OUTERPLANE GRAPHS

Let G be an outerplane graph with maximum degree A and the entire chromatic number Xvef（G）. This paper proves that if △ ≥6, then △＋ 1≤Xvef（G）≤△＋ 2, and Xvef （G） = △＋ 1 if and only if G has a matching M consisting of some inner edges which covers all its vertices of maximum degree.

Efficient Stereo Matching Scheme Based on Graph Cuts

A new stereo matching scheme from image pairs based on graph cuts is given,which can solve the problem of large color differences as the result of fusing matching results of graph cuts from different color spaces.This scheme builds normalized histogram and reference histogram from matching results,and uses clustering algorithm to process the two histograms.Region histogram statistical method is adopted to retrieve depth data to achieve final matching results.Regular stereo matching library is used to verify this scheme,and experiments reported in this paper support availability of this method for automatic image processing.This scheme renounces the step of manual selection for adaptive color space and can obtain stable matching results.The whole procedure can be executed automatically and improve the integration level of image analysis process.

The Matching Uniqueness of A Graphs

In the paper, We discussed the matching uniqueness of graphs with degree sequence . The necessary and sufficient conditions for and its complement are matching unique are given.

The Number of Matching Equivalent for the Union Graph of Vertices and Cycles

For two graphs G and H, if G and H have the same matching polynomial, then G and H are said to be matching equivalent. We denote by δ (G), the number of the matching equivalent graphs of G. In this paper, we give δ (sK1 ∪ t1C9 ∪ t2C15), which is a generation of the results of in [1].

K-Means Graph Database Clustering and Matching for Fingerprint Recognition

The graph can contain huge amount of data. It is heavily used for pattern recognition and matching tasks like symbol recognition, information retrieval, data mining etc. In all these applications, the objects or underlying data are represented in the form of graph and graph based matching is performed. The conventional algorithms of graph matching have higher complexity. This is because the most of the applications have large number of sub graphs and the matching of these sub graphs becomes computationally expensive. In this paper, we propose a graph based novel algorithm for fingerprint recognition. In our work we perform graph based clustering which reduces the computational complexity heavily. In our algorithm, we exploit structural features of the fingerprint for K-means clustering of the database. The proposed algorithm is evaluated using realtime fingerprint database and the simulation results show that our algorithm outperforms the existing algorithm for the same task.

Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies

In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let wi?be a non-isolated vertex of graph Gi?where i=1, 2, …, k. We use Gu(k)?(respectively, Hv(k)) to denote the graph which is the coalescence of G (respectively, H) and G1, G2,…, Gk?by identifying the vertices u (respectively, v) and w1, w2,…, wk. In this paper, we first present a new technique of directly comparing the matching energies of Gu(k)?and Hv(k), which can tackle some quasi-order incomparable problems. As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all n≥211.

Exact Graph Pattern Matching:Applications,Progress and Prospects

Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.

Rainbow Matchings in Properly Colored Bipartite Graphs

Let G be a properly colored bipartite graph. A rainbow matching of G is such a matching in which no two edges have the same color. Let G be a properly colored bipartite graph with bipartition (X,Y) and . We show that if , then G has a rainbow coloring of size at least .

Induced Matching-Extendability of Halin Graphs

Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).

Graph Based Filtering and Matching for Symbol Recognition

Pattern recognition is a task of searching particular patterns or features in the given input. The data mining, computer networks, genetic engineering, chemical structure analysis, web services etc. are few rapidly growing applications where pattern recognition has been used. Graphs are very powerful model applied in various areas of computer science and engineering. This paper proposes a graph based algorithm for performing the graphical symbol recognition. In the proposed approach, a graph based filtering prior to the matching is performed which significantly reduces the computational complexity. The proposed algorithm is evaluated using a large number of input drawings and the simulation results show that the proposed algorithm outperforms the existing algorithms.

Solving the Maximum Matching Problem on Bipartite Star123-Free Graphs in Linear Time

The bipartite Star123-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star123-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star123, P7-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.

Image Matching Using Mutual k-Nearest Neighbor Graph

Though weighted voting matching is one of most successful image matching methods, each candidate correspondence receives voting score from all other candidates, which can not apparently distinguish correct matches and incorrect matches using voting scores. In this paper, a new image matching method based on mutual k-nearest neighbor (k-nn) graph is proposed. Firstly, the mutual k-nn graph is constructed according to similarity between candidate correspondences.Then, each candidate only receives voting score from its mutual k nearest neighbors. Finally, based on voting scores, the matching correspondences are computed by a greedy ranking technique. Experimental results demonstrate the effectiveness of the proposed method.

An Incremental Graph Pattern Matching Based Dynamic Cold-Start Recommendation Method

In order to give accurate recommendations for cold-start user, researchers use social network to find similar users. These efforts assume that cold-start user’s social relationships are static. However social relationships of cold-start user may change as time pass by. In order to give accurate and timely in manner recommendations for cold-start user, it is need to update social relationship continuously. In this paper, we proposed an incremental graph pattern matching based dynamic cold-start recommendation method (IGPMDCR), which updates similar users for cold-start user based on topology of social network, and gives recommendations based on the latest similar users’ records. The experimental results show that, IGPMDCR could give accurate and timely in manner recommendations for cold-start user.