The cross-modal person re-identification task aims to match visible and infrared images of the same individual.The main challenges in this field arise from significant modality differences between individuals and the ...The cross-modal person re-identification task aims to match visible and infrared images of the same individual.The main challenges in this field arise from significant modality differences between individuals and the lack of high-quality cross-modal correspondence methods.Existing approaches often attempt to establish modality correspondence by extracting shared features across different modalities.However,these methods tend to focus on local information extraction and fail to fully leverage the global identity information in the cross-modal features,resulting in limited correspondence accuracy and suboptimal matching performance.To address this issue,we propose a quadratic graph matching method designed to overcome the challenges posed by modality differences through precise cross-modal relationship alignment.This method transforms the cross-modal correspondence problem into a graph matching task and minimizes the matching cost using a center search mechanism.Building on this approach,we further design a block reasoning module to uncover latent relationships between person identities and optimize the modality correspondence results.The block strategy not only improves the efficiency of updating gallery images but also enhances matching accuracy while reducing computational load.Experimental results demonstrate that our proposed method outperforms the state-of-the-art methods on the SYSU-MM01,RegDB,and RGBNT201 datasets,achieving excellent matching accuracy and robustness,thereby validating its effectiveness in cross-modal person re-identification.展开更多
To enhance network security,this study employs a deep graph matching model for vulnerability similarity detection.The model utilizes a Word Embedding layer to vectorize data words,an Image Embedding layer to vectorize...To enhance network security,this study employs a deep graph matching model for vulnerability similarity detection.The model utilizes a Word Embedding layer to vectorize data words,an Image Embedding layer to vectorize data graphs,and an LSTM layer to extract the associations between word and graph vectors.A Dropout layer is applied to randomly deactivate neurons in the LSTM layer,while a Softmax layer maps the LSTM analysis results.Finally,a fully connected layer outputs the detection results with a dimension of 1.Experimental results demonstrate that the AUC of the deep graph matching vulnerability similarity detection model is 0.9721,indicating good stability.The similarity scores for vulnerabilities such as memory leaks,buffer overflows,and targeted attacks are close to 1,showing significant similarity.In contrast,the similarity scores for vulnerabilities like out-of-bounds memory access and logical design flaws are less than 0.4,indicating good similarity detection performance.The model’s evaluation metrics are all above 97%,with high detection accuracy,which is beneficial for improving network security.展开更多
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 ma...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.展开更多
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 amon...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.展开更多
Inexact graph matching algorithms have proved to be useful in many applications,such as character recognition,shape analysis,and image analysis. Inexact graph matching is,however,inherently an NP-hard problem with exp...Inexact graph matching algorithms have proved to be useful in many applications,such as character recognition,shape analysis,and image analysis. Inexact graph matching is,however,inherently an NP-hard problem with exponential computational complexity. Much of the previous research has focused on solving this problem using heuristics or estimations. Unfortunately,many of these techniques do not guarantee that an optimal solution will be found. It is the aim of the proposed algorithm to reduce the complexity of the inexact graph matching process,while still producing an optimal solution for a known application. This is achieved by greatly simplifying each individual matching process,and compensating for lost robustness by producing a hierarchy of matching processes. The creation of each matching process in the hierarchy is driven by an application-specific criterion that operates at the subgraph scale. To our knowledge,this problem has never before been approached in this manner. Results show that the proposed algorithm is faster than two existing methods based on graph edit operations.The proposed algorithm produces accurate results in terms of matching graphs,and shows promise for the application of shape matching. The proposed algorithm can easily be extended to produce a sub-optimal solution if required.展开更多
For the problem of track correlation failure under the influence of sensor system deviation in wireless sensor networks,a new track correlation method which is based on relative positional relation chart matching is p...For the problem of track correlation failure under the influence of sensor system deviation in wireless sensor networks,a new track correlation method which is based on relative positional relation chart matching is proposed.This method approximately simulates the track correlation determination process using artificial data,and integrally matches the relative position relation between multiple targets in the common measuring space of various sensors in order to fulfill the purpose of multi-target track correlation.The simulation results show that this method has high correlation accuracy and robustness.展开更多
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 qu...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.展开更多
Let G be a graph with n（G） vertices and m（G） be its matching number.The nullity of G,denoted by η（G）,is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then...Let G be a graph with n（G） vertices and m（G） be its matching number.The nullity of G,denoted by η（G）,is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then η（G） = n（G）-2m（G）.Guo et al.[Jiming GUO,Weigen YAN,Yeongnan YEH.On the nullity and the matching number of unicyclic graphs.Linear Alg.Appl.,2009,431：1293 1301]proved that if G is a unicyclic graph,then η（G）equals n（G）-2m（G）-1,n（G）-2m（G）,or n（G）-2m（G） ＋2.In this paper,we prove that if G is a bicyclic graph,then η（G） equals n（G）-2m（G）,n（G）-2m（G）±1,n（G）-2m（G）±2or n（G）-2m（G） ＋ 4.We also give a characterization of these six types of bicyclic graphs corresponding to each nullity.展开更多
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 decis...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.展开更多
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...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.展开更多
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.
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 δ&...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 δ (sK<sub>1</sub> ∪ t<sub>1</sub>C<sub>9</sub> ∪ t<sub>2</sub>C<sub>15</sub>), which is a generation of the results of in <a href="#ref1">[1].展开更多
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 under...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.展开更多
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 ab...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.展开更多
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 gr...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.展开更多
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...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 optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canoni...The optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large 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 ...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 .展开更多
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 inc...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.展开更多
文摘The cross-modal person re-identification task aims to match visible and infrared images of the same individual.The main challenges in this field arise from significant modality differences between individuals and the lack of high-quality cross-modal correspondence methods.Existing approaches often attempt to establish modality correspondence by extracting shared features across different modalities.However,these methods tend to focus on local information extraction and fail to fully leverage the global identity information in the cross-modal features,resulting in limited correspondence accuracy and suboptimal matching performance.To address this issue,we propose a quadratic graph matching method designed to overcome the challenges posed by modality differences through precise cross-modal relationship alignment.This method transforms the cross-modal correspondence problem into a graph matching task and minimizes the matching cost using a center search mechanism.Building on this approach,we further design a block reasoning module to uncover latent relationships between person identities and optimize the modality correspondence results.The block strategy not only improves the efficiency of updating gallery images but also enhances matching accuracy while reducing computational load.Experimental results demonstrate that our proposed method outperforms the state-of-the-art methods on the SYSU-MM01,RegDB,and RGBNT201 datasets,achieving excellent matching accuracy and robustness,thereby validating its effectiveness in cross-modal person re-identification.
基金Special Project Funded by Tsinghua University Press:“Engineering Drawing and CAD”Course Construction and Textbook Development。
文摘To enhance network security,this study employs a deep graph matching model for vulnerability similarity detection.The model utilizes a Word Embedding layer to vectorize data words,an Image Embedding layer to vectorize data graphs,and an LSTM layer to extract the associations between word and graph vectors.A Dropout layer is applied to randomly deactivate neurons in the LSTM layer,while a Softmax layer maps the LSTM analysis results.Finally,a fully connected layer outputs the detection results with a dimension of 1.Experimental results demonstrate that the AUC of the deep graph matching vulnerability similarity detection model is 0.9721,indicating good stability.The similarity scores for vulnerabilities such as memory leaks,buffer overflows,and targeted attacks are close to 1,showing significant similarity.In contrast,the similarity scores for vulnerabilities like out-of-bounds memory access and logical design flaws are less than 0.4,indicating good similarity detection performance.The model’s evaluation metrics are all above 97%,with high detection accuracy,which is beneficial for improving network security.
文摘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.
文摘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.
文摘Inexact graph matching algorithms have proved to be useful in many applications,such as character recognition,shape analysis,and image analysis. Inexact graph matching is,however,inherently an NP-hard problem with exponential computational complexity. Much of the previous research has focused on solving this problem using heuristics or estimations. Unfortunately,many of these techniques do not guarantee that an optimal solution will be found. It is the aim of the proposed algorithm to reduce the complexity of the inexact graph matching process,while still producing an optimal solution for a known application. This is achieved by greatly simplifying each individual matching process,and compensating for lost robustness by producing a hierarchy of matching processes. The creation of each matching process in the hierarchy is driven by an application-specific criterion that operates at the subgraph scale. To our knowledge,this problem has never before been approached in this manner. Results show that the proposed algorithm is faster than two existing methods based on graph edit operations.The proposed algorithm produces accurate results in terms of matching graphs,and shows promise for the application of shape matching. The proposed algorithm can easily be extended to produce a sub-optimal solution if required.
基金Supported by the National Basic Research Program of China (973 Program) (2006CB303000)
文摘For the problem of track correlation failure under the influence of sensor system deviation in wireless sensor networks,a new track correlation method which is based on relative positional relation chart matching is proposed.This method approximately simulates the track correlation determination process using artificial data,and integrally matches the relative position relation between multiple targets in the common measuring space of various sensors in order to fulfill the purpose of multi-target track correlation.The simulation results show that this method has high correlation accuracy and robustness.
文摘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.
基金Supported by the National Natural Science Foundation of China(Grant Nos.1133100311471077)
文摘Let G be a graph with n（G） vertices and m（G） be its matching number.The nullity of G,denoted by η（G）,is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then η（G） = n（G）-2m（G）.Guo et al.[Jiming GUO,Weigen YAN,Yeongnan YEH.On the nullity and the matching number of unicyclic graphs.Linear Alg.Appl.,2009,431：1293 1301]proved that if G is a unicyclic graph,then η（G）equals n（G）-2m（G）-1,n（G）-2m（G）,or n（G）-2m（G） ＋2.In this paper,we prove that if G is a bicyclic graph,then η（G） equals n（G）-2m（G）,n（G）-2m（G）±1,n（G）-2m（G）±2or n（G）-2m（G） ＋ 4.We also give a characterization of these six types of bicyclic graphs corresponding to each nullity.
文摘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.
文摘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.
文摘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.
文摘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 δ (sK<sub>1</sub> ∪ t<sub>1</sub>C<sub>9</sub> ∪ t<sub>2</sub>C<sub>15</sub>), which is a generation of the results of in <a href="#ref1">[1].
文摘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.
文摘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.
文摘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.
基金Sponsored by"985"Second Procession Construction of Ministry of Education(3040012040101)
文摘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 optimal semi-matching problem is one relaxing form of the maximum cardinality matching problems in bipartite graphs, and finds its applications in load balancing. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate Boolean functions efficiently. OBDD-based symbolic algorithms appear to give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic OBDD formulation and algorithm for the optimal semi-matching problem in bipartite graphs. The symbolic algorithm is initialized by heuristic searching initial matching and then iterates through generating residual network, building layered network, backward traversing node-disjoint augmenting paths, and updating semi-matching. It does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Our simulations show that symbolic algorithm has better performance, especially on dense and large 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 .
文摘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.
