Efficient many-to-many feature matching under the l1 norm

Matching configurations of image features, represented as attributed graphs, to configurations of model features is an important component in many object recognition algorithms. Noisy segmentation of images and imprecise feature detection may lead to graphs that represent visually similar configurations that do not admit an injective matching. In previous work, we presented a framework which computed an explicit many-to-many vertex correspondence between attributed graphs of features configurations. The framework utilized a low distortion embedding function to map the nodes of the graphs into point sets in a vector space. The Earth Movers Distance (EMD) algorithm was then used to match the resulting points, with the computed flows specifying the many-to-many vertex correspondences between the input graphs. In this paper, we will present a distortion-free embedding, which represents input graphs as metric trees and then embeds them isometrically in the geometric space under the l₁ norm. This not only improves the representational power of graphs in the geometric space, it also reduces the complexity of the previous work using recent developments in computing EMD under l₁. Empirical evaluation of the algorithm on a set of recognition trials, including a comparison with previous approaches, demonstrates the effectiveness and robustness of the proposed framework.     

Skeletal Shape Abstraction from Examples

Learning a class prototype from a set of exemplars is an important challenge facing researchers in object categorization. Although the problem is receiving growing interest, most approaches assume a one-to-one correspondence among local features, restricting their ability to learn true abstractions of a shape. In this paper, we present a new technique for learning an abstract shape prototype from a set of exemplars whose features are in many-to-many correspondence. Focusing on the domain of 2D shape, we represent a silhouette as a medial axis graph whose nodes correspond to "parts” defined by medial branches and whose edges connect adjacent parts. Given a pair of medial axis graphs, we establish a many-to-many correspondence between their nodes to find correspondences among articulating parts. Based on these correspondences, we recover the abstracted medial axis graph along with the positional and radial attributes associated with its nodes. We evaluate the abstracted prototypes in the context of a recognition task.     

Region-Based Hierarchical Image Matching

This paper presents an approach to region-based hierarchical image matching, where, given two images, the goal is to identify the largest part in image 1 and its match in image 2 having the maximum similarity measure defined in terms of geometric and photometric properties of regions (e.g., area, boundary shape, and color), as well as region topology (e.g., recursive embedding of regions). To this end, each image is represented by a tree of recursively embedded regions, obtained by a multiscale segmentation algorithm. This allows us to pose image matching as the tree matching problem. To overcome imaging noise, one-to-one, many-to-one, and many-to-many node correspondences are allowed. The trees are first augmented with new nodes generated by merging adjacent sibling nodes, which produces directed acyclic graphs (DAGs). Then, transitive closures of the DAGs are constructed, and the tree matching problem reformulated as finding a bijection between the two transitive closures on DAGs, while preserving the connectivity and ancestor-descendant relationships of the original trees. The proposed approach is validated on real images showing similar objects, captured under different types of noise, including differences in lighting conditions, scales, or viewpoints, amidst limited occlusion and clutter.     

迭代的图变换匹配算法

目的：图像的精确匹配在图像处理与识别中起着重要的作用。为了提高图像的匹配效果,本文提出了一种迭代的图变换匹配算法来实现误匹配关系的去除从而提高图像的匹配精度。方法：该算法首先利用传统的图变换匹配(GTM)算法从初始匹配关系集合中获得较为精确的匹配关系子集,然后,利用已经获得的正确匹配点集与初始匹配点集之间的几何关系对初始匹配进行修正。最后,利用GTM对修正后的匹配关系进一步优化,从而得到更多的精确匹配关系。结果：实验结果显示在不同的图像变换场景下,相比于传统GTM算法,该算法具有较高的查全率。结论：所提算法能够克服传统GTM算法所得正确匹配关系少的缺陷。     

A generative model for graph matching and embedding

This paper shows how to construct a generative model for graph structure through the embedding of the nodes of the graph in a vector space. We commence from a sample of graphs where the correspondences between nodes are unknown ab initio. We also work with graphs where there may be structural differences present, i.e. variations in the number of nodes in each graph and their edge structure. We characterise the graphs using the heat-kernel, and this is obtained by exponentiating the Laplacian eigensystem with time. The idea underpinning the method is to embed the nodes of the graphs into a vector space by performing a Young-Householder decomposition of the heat-kernel into an inner product of node co-ordinate matrices. The co-ordinates of the nodes are determined by the eigenvalues and eigenvectors of the Laplacian matrix, together with a time-parameter which can be used to scale the embedding. Node correspondences are located by applying Scott and Longuet-Higgins algorithm to the embedded nodes. We capture variations in graph structure using the covariance matrix for corresponding embedded point positions. We construct a point-distribution model for the embedded node positions using the eigenvalues and eigenvectors of the covariance matrix. We show how to use this model to both project individual graphs into the eigenspace of the point position covariance matrix and how to fit the model to potentially noisy graphs to reconstruct the Laplacian matrix. We illustrate the utility of the resulting method for shape analysis using data from the Caltech–Oxford and COIL databases.     

Three-Dimensional Reconstruction of Points and Lines with Unknown Correspondence across Images

Three-dimensional reconstruction from a set of images is an important and difficult problem in computer vision. In this paper, we address the problem of determining image feature correspondences while simultaneously reconstructing the corresponding 3D features, given the camera poses of disparate monocular views. First, two new affinity measures are presented that capture the degree to which candidate features from different images consistently represent the projection of the same 3D point or 3D line. An affinity measure for point features in two different views is defined with respect to their distance from a hypothetical projected 3D pseudo-intersection point. Similarly, an affinity measure for 2D image line segments across three views is defined with respect to a 3D pseudo-intersection line. These affinity measures provide a foundation for determining unknown correspondences using weighted bipartite graphs representing candidate point and line matches across different images. As a result of this graph representation, a standard graph-theoretic algorithm can provide an optimal, simultaneous matching and triangulation of points across two views, and lines across three views. Experimental results on synthetic and real data demonstrate the effectiveness of the approach.An erratum to this article can be found at     

Contour-based object detection as dominant set computation

Contour-based object detection can be formulated as a matching problem between model contour parts and image edge fragments. We propose a novel solution by treating this problem as the problem of finding dominant sets in weighted graphs. The nodes of the graph are pairs composed of model contour parts and image edge fragments, and the weights between nodes are based on shape similarity. Because of high consistency between correct correspondences, the correct matching corresponds to a dominant set of the graph. Consequently, when a dominant set is determined, it provides a selection of correct correspondences. As the proposed method is able to get all the dominant sets, we can detect multiple objects in an image in one pass. Moreover, since our approach is purely based on shape, we also determine an optimal scale of target object without a common enumeration of all possible scales. Both theoretic analysis and extensive experimental evaluation illustrate the benefits of our approach.     

Stereo vision correspondence using a multichannel graph matching technique

A multichannel feature-based stereo vision technique is described in this paper where curve segments are used as the feature primitives in the matching process. Curve segments are extracted by tracking the zero-crossings of the left and right images. The generalized Hough transform of each curve and the curve length are used as a local feature vector in representing the distinctive characteristics of the curve segment. The feature vector of each curve segment in the left image is used as a constraint to find an instance of the same curve segment in the right image. The epipolar constraint on the centroids of the curve segment is used to limit the searching space in the right image.

A relational graph is formed from the left image by treating the centroids of the curve segments as the nodes of the graph. The local features of the curve segments are used to represent the local properties of the nodes, and the relationship between the nodes represents the structural properties of the objects in the scene. A similar graph is also formed from the right image curve segments. A graph isomorphism is then formed between the two graphs by using the epipolar constraint on the centroids, the local properties of the nodes, node assignment and the structural relationship (compatibility) between the nodes.     

三维图匹配算法

目的 现有的图匹配算法大多应用于二维图像,对三维图像的特征点匹配存在匹配准确率低和计算速度慢等问题。为解决这些问题,本文将分解图匹配算法扩展应用在了三维图像上。方法 首先将需要匹配的两个三维图像的特征点作为图的节点集;再通过Delaunay三角剖分算法,将三维特征点相连,则相连得到的边就作为图的边集,从而建立有向图;然后,根据三维图像的特征点构建相应的三维有向图及其邻接矩阵;再根据有向图中的节点特征和边特征分别构建节点特征相似矩阵和边特征相似矩阵;最后根据这两个特征矩阵将节点匹配问题转化为求极值问题并求解。结果 实验表明,在手工选取特征点的情况下,本文算法对相同三维图像的特征点匹配有97.56%的平均准确率;对不同三维图像特征点匹配有76.39%的平均准确率;在三维图像有旋转的情况下,有90%以上的平均准确率;在特征点部分缺失的情况下,平均匹配准确率也能达到80%。在通过三维尺度不变特征变换（SIFT）算法得到特征点的情况下,本文算法对9个三维模型的特征点的平均匹配准确率为98.78%。结论 本文提出的基于图论的三维图像特征点匹配算法,经实验结果验证,可以取得较好的匹配效果。     

Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.     

Graph matching based on spectral embedding with missing value

This paper proposes an efficient algorithm for inexact graph matching based on spectral embedding with missing value. We commence by building an association graph model based on initial matching algorithm. Then, by dot product representation of graph with missing value, a new embedding method (co-embedding), where the correspondences between unmatched nodes are treated as missing data in an association graph, is presented. At last, a new graph matching algorithm which alternates between the co-embedding and point pattern matching is proposed. Convictive experimental results on both synthetic and real-world data demonstrate the effectiveness of the proposed graph matching algorithm.     

一种有效的贪婪模式匹配算法

模式匹配问题是意图获得两个模式中所包含个体对象之间的语义匹配和映射,其结果表示源模式的个体对象与目标模式的个体对象之间存在特定的语义关联.它在数据库应用领域起到关键性的作用,例如数据集成、电子商务、数据仓库、XML消息交换等,特别地,它已成为元数据管理的基本问题.然而,模式匹配很大程度上依赖人工的操作,是一个费时费力的过程.模式匹配问题可以归约为一个组合优化问题:多标记图匹配问题.首先,将模式表示为多标记图,将模式匹配转换为多标记图匹配问题.其次,提出多标记图的相似性度量方法,进而提出基于多标记图相似性的模式匹配目标优化函数.最后,在这个目标函数基础上设计实现了一个贪婪匹配算法,其最显著的特点是综合多种可用的标记信息,灵活准确地获得最优的匹配结果.     

基于二分图卷积表示的推荐算法

随着数据驱动智能技术的快速发展,个性化推荐算法及相关应用成为了研究热点.推荐可视为将用户与物品进行匹配的问题,但用户与物品之间存在的语义差距不便于两者之间的直接匹配.现有的许多基于深度学习的推荐算法采用的思路都是将不同空间中的实体映射到统一潜在语义空间,利用其嵌入表示来进行匹配度计算.随着网络表示学习方法的出现,由于用...     

旅游知识图谱特征学习的景点推荐

基于知识图谱的推荐算法在多个领域取得了较好的效果，但仍然存在一些问题，如不能有效提取知识图谱中实体关系标签中的特征，推荐准确率会降低。因而提出将网络嵌入方法（network embedding）用于旅游知识图谱的特征提取，使得特征的提取更加充分。通过对旅游知识图谱中不同标签的属性子图独立建模，利用深度学习模型挖掘游客及景点等图节点语义特征，进而获得融合各个标签语义的游客和景点特征向量，最终通过计算游客和景点相关性生成景点推荐列表。通过在真实旅游知识图谱上的实验，验证了利用网络嵌入方法对知识图谱中数据建模后，可以有效提取节点的深层特征。     

Recognizing hand gestures using the weighted elastic graph matching (WEGM) method

This paper proposes a weighted scheme for elastic graph matching hand posture recognition. Visual features scattered on the elastic graph are assigned corresponding weights according to their relative ability to discriminate between gestures. The weights' values are determined using adaptive boosting. A dictionary representing the variability of each gesture class is expressed in the form of a bunch graph. The positions of the nodes in the bunch graph are determined using three techniques: manually, semi-automatically, and automatically. Experimental results also show that the semi-automatic annotation method is efficient and accurate in terms of three performance measures; assignment cost, accuracy, and transformation error. In terms of the recognition accuracy, our results show that the hierarchical weighting on features has more significant discriminative power than the classic method (uniform weighting). The hierarchical elastic graph matching (WEGM) approach was used to classify a lexicon of ten hand postures, and it was found that the poses were recognized with a recognition accuracy of 97.08% on average. Using the weighted scheme, computing cycles can be decreased by only computing the features for those nodes whose weight is relatively high and ignoring the remaining nodes. It was found that only 30% of the nodes need to be computed to obtain a recognition accuracy of over 90%.     

一种基于改进向量投影距离的知识图谱表示方法

表示学习在知识图谱推理中有着重要的研究价值,将知识库中的实体和关系用连续低维向量进行表示,可实现知识的可计算。基于向量投影距离的知识表示学习模型在面对复杂关系时有较好的知识表达能力,但在处理一对一简单关系时容易受到无关信息的干扰,并且在一对多、多对一和多对多等复杂关系上存在性能提升空间。为此,文中提出了一个基于改进向量投影距离的知识表示学习模型SProjE,该模型引入自适应度量方法,降低了噪声信息的影响。在此基础上,通过进一步优化损失函数来提高复杂关系三元组的损失权重。该模型适用于大规模知识图谱的表示学习任务。最后,在标准知识图谱数据集WN18和FB15K上分析和验证了所提方法的有效性,基于链路预测任务的评测实验结果表明,相较于现有的模型和方法,SProjE在各项性能指标上均取得了明显的进步。     

基于图嵌入与支持向量机的社交网络节点分类方法

针对无属性社交网络的节点分类问题,提出了一种基于图嵌入与支持向量机,利用社交网络中节点之间关系特征,对节点进行分类的方法.首先,通过DeepWalk、LINE等多种图嵌入模型挖掘节点隐含关系特征的同时,将高维的社交网络数据转换为低维embedding向量.其次,提取节点度、聚集系数、PageRank值等特征信息,组合构成节点的特征向量.然后,利用支持向量机构建节点分类预测模型对节点进行分类预测.最后,在三个公开的社交网络数据集上实验,与对比方法相比,提出的方法在社交网络节点分类任务中能取得更好的分类效果.     

一种基于图注意力的双分支社会关系识别方法

从图像中挖掘人物间的社会关系在刑侦、隐私防护等领域有重要的作用。现有的图建模方法通过创建人际关系图或构建知识图谱来学习人物关系,取得了良好的效果。但基于图卷积神经网络（GCN）的方法一定程度上忽略了不同特征对特定关系的不同程度的重要性。针对上述问题,提出了一种基于图注意力的双分支社会关系识别模型（GAT-DBSR）,第一个分支提取人物区域以及图像全局特征作为节点,核心是通过图注意力网络和门控机制去更新这些节点以学习人物关系的特征表示。第二个分支通过卷积神经网络提取场景特征来增强对人物关系的识别。最终对两个分支的特征进行融合并分类得到所有的社会关系。该模型在PISC数据集的细粒度关系识别任务上的mAP达到了74.4%,相比基线模型提高了1.2%。在PIPA数据集上的关系识别准确率也有一定的提升。实验结果表明了该模型具有更优越的效果。     

Efficient and scalable labeled subgraph matching using SGMatch

Graphs are natural candidates for modeling application domains, such as social networks, pattern recognition, citation networks, or protein–protein interactions. One of the most challenging tasks in managing graphs is subgraph matching over data graphs, which attempts to find one-to-one correspondences, called solutions, among the query and data nodes. To compute solutions, most contemporary techniques use backtracking and recursion. An open research question is whether graphs can be matched based on parts and local solutions can be combined to reach a global matching. In this paper, we present an approach based on graph decomposition called SGMatch to match graphs. We represent graphs in smaller units called graphlets and develop a matching technique to leverage this representation. Pruning strategies use a new notion of edge covering called minimum hub cover and metadata, such as statistics and inverted indices, to reduce the number of matching candidates. Our evaluation of SGMatch versus contemporary algorithms, i.e., VF2, GraphQL, QuickSI, GADDI, or SPath, shows that SGMatch substantially improves the performance of current state-of-the-art techniques for larger query graphs with different structures, i.e., cliques, paths or subgraphs.