Inexact graph matching for structural pattern recognition

This paper is concerned with the inexact matching of attributed, relational graphs for structural pattern recognition. The matching procedure is based on a state space search utilizing heuristic information. Some experimental results are reported.     

Attributed relational graph matching based on the nested assignment structure

In this paper, we propose a new ARG matching scheme based on the nested assignment structure to assess the similarity between two attributed relational graphs (ARGs). ARGs are represented by nodes and edges containing unary attributes and binary relations between nodes, respectively. The nested assignment structure consists of inner and outer steps. In the inner step, to form a distance matrix, combinatorial differences between every pair of nodes in two ARGs are computed by using an assignment algorithm. Then, in the outer step, a correspondence between nodes in the two ARGs is established by using an assignment algorithm based on the distance matrix. The proposed ARG matching scheme consists of three procedures as follows: first, in the initializing procedure, the nested assignment structure is performed to generate an initial correspondence between nodes in two ARGs. Next, the correspondence is refined by iteratively performing the updating procedure, which also utilizes the nested assignment structure, until the correspondence does not change. Finally, the verifying procedure can be performed in case that some nodes to be matched in the two ARGs are missing. From experimental results, the proposed ARG matching scheme shows superior matching performance and localizes target objects robustly and correctly even in severely noisy and occluded scenes.     

基于非精确图匹配的CAD模型搜索方法

为了弥补现有的三维CAD模型搜索方法难以搜索到不同近似程度的相似模型的缺陷,提出一种基于面属性化邻接图非精确匹配的CAD模型搜索方法.首先提取CAD模型中的B-rep信息将CAD模型转化为面属性化邻接图;然后计算目标模型与被搜索模型的面属性化邻接图之间的顶点相容程度矩阵和边相容程度矩阵,并由此建立2个模型相似程度的度量作为选择不同顶点匹配矩阵M的优化目标函数;在对匹配矩阵M进行连续化松弛后,运用Sinkhorn行列交替规范化方法求解匹配优化问题.实验结果表明,采用该方法能够搜索到不同近似程度的相似模型;并且由于避免了具有NP复杂性的精确图匹配过程,检索效率也能满足实际要求.     

Fingerprint matching using OrientationCodes and PolyLines

Effectively incorporating various features with minutiae in fingerprint matching is a challenging task. This paper presents an algorithm to extract two novel discriminative features that describe three kinds of information: macro orientation patterns, micro ridge representation, and minutiae of fingerprints. These features, namely OrientationCodes and PolyLines, are fixed-length, easy to be measured in similarity, and effective in various stages of fingerprint matching, such as alignment, minutiae pairing, matching score computation, and matching rates fusion. In addition, the scheme of the proposed method has advantages of programming implementation, manipulating fingerprint matching much simpler and smoother at a high level. Experimental results on six data sets of FVC2002 and FVC2004 indicate the proposed algorithm not only achieves remarkably lower EERs, but also consumes significantly less computational times.     

Matching ‘sticks,plates and blobs’ objects using geometric and relational constraints

A recognition scheme using relational and rough geometric information about three-dimensional man-made objects to recognize instances of the objects in single perspectivenormal views of scenes is described. Experiments performed using the matching scheme show that, in most cases, the object in the view can be identified correctly and reasonable estimates can be made of the unknown camera position responsible for generating the given view.The technique is based on the fact that the camera position constrains the appearance of the various parts of the object. The propagation of these constraints from one planar object surface to another through the projection equations is worked out. This constraint propagation guides the matching scheme in the development of the interpretation of the scene. The results provide an estimate of the camera position within 20° of the actual location.     

Symbol recognition in electrical diagrams using probabilistic graph matching

In this paper a method is proposed to recognize symbols in electrical diagrams based on probabilistic matching. The skeletons of the symbols are represented by graphs. After finding the pose of the graph (orientation, translation, scale) by a bounded search for a minimum error transformation, the observed graph is matched to the class models and the likelihood of the match is calculated. Results are given for computer-generated symbols and hand drawn symbols with and without a template. Error rates range from <1% to 8%.     

Planar shape matching based on binary tree shape representation

In this paper we suggest a new way of representing planar two-dimensional shapes and a shape matching method which utilizes the new representation. Through merging of the neighboring boundary runs, a shape can be partitioned into a set of triangles. These triangles are inherently connected according to a binary tree structure. Here we use the binary tree with the triangles as its nodes to represent the shape. This representation is found to be insensitive to shape translation, rotation, scaling and skewing changes due to viewer's location changes (or the object's pose changes). Furthermore, the representation is of multiresolution.

In shape matching we compare the two trees representing two given shapes node by node according to the breadth-first tree traversing sequence. The comparison is done from top of the tree and moving downward, which means that we first compare the lower resolution approximations of the two shapes. If the two approximations are different, the comparison stops. Otherwise, it goes on and compares the finer details of the two shapes. Only when the two shapes are very similar, will the two corresponding trees be compared entirely. Thus, the matching algorithm utilizes the multiresolution characteristic of the tree representation and appears to be very efficient.     

基于面匹配的模型相似性度量方法

为了准确地衡量两个模型的相似程度,提出了一种基于面匹配的模型相似性计算方法.使用面邻接图表示模型的拓扑结构,根据面的组成边数来构造两个模型之间的面匹配矩阵,同时,使用贪心算法来计算模型之间的相似性.在实验中,使用所提方法来度量目标CAD模型和源CAD模型之间的相似程度.实验结果表明,该方法能够有效地衡量模型之间的差异.     

Graph matching using the interference of continuous-time quantum walks

We consider how continuous-time quantum walks can be used for graph matching. We focus in detail on both exact and inexact graph matching, and consider in depth the problem of measuring graph similarity. We commence by constructing an auxiliary graph, in which the two graphs to be matched are co-joined by a layer of indicator vertices (one for each potential correspondence between a pair of vertices). We simulate a continuous-time quantum walk in parallel on the two graphs. The layer of connecting indicator vertices in the auxiliary graph allow quantum interference to take place between the two walks. The interference amplitudes on the indicator vertices are determined by differences in the two walks, and can be used to calculate probabilities for matches between pairs of vertices from the graphs. By applying the Hungarian (Kuhn-Munkres) algorithm to these probabilities, we recover a correspondence mapping between the graphs. To calculate graph similarity, we combine these probabilities with edge-consistency information to give a consistency measure. Based on the consistency measure, we define two graph similarity measures, one of which requires correspondence matches while the second does not. We analyse our approach experimentally using synthetic and real-world graphs. This reveals that our method gives results that are intermediate between the most sophisticated iterative techniques available, and simpler less complex ones.     

基于子区域匹配的稀疏表示跟踪算法

经典稀疏表示目标跟踪算法在处理复杂视频时不免出现跟踪不稳定情况且当目标发生遮挡时易发生漂移现象。针对这一问题,提出一种基于子区域匹配的稀疏表示跟踪算法。首先,将初始目标模板划分为若干子区域,利用LK图像配准算法建立观测模型预测下一帧目标运动状态。然后,对预测的目标模型区域进行同等划分,并在匹配过程中寻找最优子区域。最后,在模板更新过程中引入一种新的模板校正机制,能够有效克服漂移现象。将该算法与多种目标跟踪算法在不同视频序列下进行对比,实验结果表明在目标发生遮挡、运动、光照影响及复杂背景等情况下该算法具有较为理想的跟踪效果,并与经典稀疏表示跟踪算法相比具有较好的跟踪性能。     

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data.     

高效的图模型点模式匹配算法

点模式匹配的概率图模型具有很好的匹配精度,但是计算复杂度较高,当隔离子中包含异常点（outlier）时匹配精度会受到较大的影响。为了提高匹配的速度和精度,提出了一种由粗到精的图模型点模式匹配算法。利用包含特征点的窗口,用标准化互相关方法对特征点进行粗匹配,以减少异常点的数量,提高后续匹配方法的速度和精度。提出了一种新的点模式匹配的概率图模型,这种图模型能综合利用特征点的位置信息和包含特征点的邻域的灰度信息。利用提出的概率图匹配方法对粗匹配所得到的点对进行分段匹配,得到精确的匹配结果。对光学图像和遥感图像的匹配实验显示该方法能显著减少点模式匹配时间,提高匹配的精度。     

A new method for representing and matching shapes of natural objects

A new method for the representation and comparison of irregular two-dimensional shapes is presented. This method uses a polar transformation of the contour points about the geometric centre of the object. The distinctive vertices of the shape are extracted and used as comparative parameters to minimize the difference of contour distance from the centre. Experiments are performed, more than 39 000 comparisons of database shapes, provided by Sebastian et al. (ICCV (2001) 755), are made and the results are compared to those obtained therein. In addition, 450 comparisons of leaf shape are made and leaves of very similar shape are accurately distinguished. The method is shown to be invariant to translation, rotation and scaling and highly accurate in shape distinction. The method shows more tolerance to scale variation than that of Sebastian et al. (ICCV (2001) 755) and is less computationally intense.     

Structural pattern recognition using genetic algorithms

This paper presents a genetic algorithm (GA) based optimization procedure for the solution of structural pattern recognition problem using the attributed relational graph representation and matching technique. In this study, candidate solutions are represented by integer strings and the population is randomly initialized. The GA is employed to generate a monomorphic mapping. As all the mapping constraints are not enforced during the search phase in order to speedup the search, an efficient pose clustering algorithm is used to eliminate spurious matches and to determine the presence of the model in the scene. The performance of the proposed approach to pattern recognition by subgraph isomorphism is demonstrated using line patterns and silhouette images.     

Discrete signal matching using coarse-to-fine wavelet basis functions

In this paper, we propose a matching algorithm to estimate accurate and dense displacements between two signals. The displacements are characterized by a coarse-to-fine wavelet representation, which is a linear combination of hierarchical basis functions developed by Cai and Wang (SIAM Numer. Anal. 33(3) (1996) 937). The coarser-scale basis function has larger support while the finer-scale basis function has smaller support. During the iterative minimization process, the basis functions are utilized as large-to-small windows in selecting global-to-local regions for signal matching. The estimated wavelet coefficients are then used to reconstruct the signal in a coarse-to-fine manner. Two sets of synthetic examples, one with small displacement and the other with large displacements, have been employed to illustrate the advantages of the wavelet-based method. This method has been applied to estimate the dense disparity between stereo images in several real examples and the results demonstrate its effectiveness.     

Classification of hand postures against complex backgrounds using elastic graph matching

A system for person-independent classification of hand postures against complex backgrounds in video images is presented. The system employs elastic graph matching, which has already been successfully applied for object and face recognition. We use the bunch graph technique to model variance in hand posture appearance between different subjects and variance in backgrounds. Our system does not need a separate segmentation stage but closely integrates finding the object boundaries with posture classification.     

扩展哈弗曼前缀编码实现XML数据与关系数据转换

为从企业生产线上XML半结构化数据中抽取富有意义数据,分析了XML半结构化数据和关系数据库中结构化数据特点,以及XML半结构化数据在关系数据库中的存储方法。针对实际应用,提出采用扩展哈弗曼前缀编码方法,对XML文档树进行唯一编码,实现XML文档与关系数据库映射,同时给出最长前缀匹配策略,支持数据查询,以提高查询效率。