赋权图匹配问题的一种新的松弛模型

图匹配是一个NP难(NP-hard)问题. 基于置换矩阵是非负正交矩阵这一经典结论, 提出赋权图匹配(Weighted graph matching, WGM)的双向松弛障碍规划, 理论上证明新模型的解与原模型的解是一致的. 该规划是一个二元连续规划, 它是正交矩阵上的线性优化问题, 同时也是非负矩阵上的凸二次优化问题. 故设计求解新模型的交替迭代算法, 并证明算法的局部收敛性. 数值实验表明, 在匹配精度方面, 新方法强于线性规划方法和特征值分解方法.     

A Path Following Algorithm for the Graph Matching Problem

We propose a convex-concave programming approach for the labeled weighted graph matching problem. The convex-concave programming formulation is obtained by rewriting the weighted graph matching problem as a least-square problem on the set of permutation matrices and relaxing it to two different optimization problems: a quadratic convex and a quadratic concave optimization problem on the set of doubly stochastic matrices. The concave relaxation has the same global minimum as the initial graph matching problem, but the search for its global minimum is also a hard combinatorial problem. We, therefore, construct an approximation of the concave problem solution by following a solution path of a convex-concave problem obtained by linear interpolation of the convex and concave formulations, starting from the convex relaxation. This method allows to easily integrate the information on graph label similarities into the optimization problem, and therefore, perform labeled weighted graph matching. The algorithm is compared with some of the best performing graph matching methods on four data sets: simulated graphs, QAPLib, retina vessel images, and handwritten Chinese characters. In all cases, the results are competitive with the state of the art.     

Sorting by Short Block-Moves

Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in the study of genome rearrangements and in the design of interconnection networks. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3 -approximation algorithm for this problem is presented. Woven double-strip permutations are defined and a polynomial-time algorithm for this class of permutations is devised that employs graph matching techniques. A linear-time maximum matching algorithm for a special class of grid graphs improves the time complexity of the algorithm for woven double-strip permutations. Received June 1, 1997; revised July 25, 1998.     

图模型匹配:一种新的凹松弛函数及算法

将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向. 它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲, 相对于离散优化,连续优化问题的近似求解将更为容易. 但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵. 最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵, 并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数. 本文提出一种针对于有向无自环图匹配问题的凹松弛函数, 并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.     

Construction of Hamiltonian paths in graphs of permutation polyhedra

The problem of finding an extremum of a linear function over a permutation set is considered. The polyhedron of admissible values of this function over permutations is constructed. The constructed graph is shown to be partially ordered with respect to the transposition of two elements of a permutation. Based on this property, a method is proposed for the construction of a Hamiltonian path in the graph corresponding to the permutation set for n=4.     

Graph Matching by Simplified Convex-Concave Relaxation Procedure

The convex and concave relaxation procedure (CCRP) was recently proposed and exhibited state-of-the-art performance on the graph matching problem. However, CCRP involves explicitly both convex and concave relaxations which typically are difficult to find, and thus greatly limit its practical applications. In this paper we propose a simplified CCRP scheme, which can be proved to realize exactly CCRP, but with a much simpler formulation without needing the concave relaxation in an explicit way, thus significantly simplifying the process of developing CCRP algorithms. The simplified CCRP can be generally applied to any optimizations over the partial permutation matrix, as long as the convex relaxation can be found. Based on two convex relaxations, we obtain two graph matching algorithms defined on adjacency matrix and affinity matrix, respectively. Extensive experimental results witness the simplicity as well as state-of-the-art performance of the two simplified CCRP graph matching algorithms.     

Minimizing total weighted completion time with uncertain data: A stability approach

A single-machine scheduling problem is investigated provided that the input data are uncertain: The processing time of a job can take any real value from the given segment. The criterion is to minimize the total weighted completion time for the n jobs. As a solution concept to such a scheduling problem with an uncertain input data, it is reasonable to consider a minimal dominant set of job permutations containing an optimal permutation for each possible realization of the job processing times. To find an optimal or approximate permutation to be realized, we look for a permutation with the largest stability box being a subset of the stability region. We develop a branch-and-bound algorithm to construct a permutation with the largest volume of a stability box. If several permutations have the same volume of a stability box, we select one of them due to one of two simple heuristics. The efficiency of the constructed permutations (how close they are to a factually optimal permutation) and the efficiency of the developed software (average CPU-time used for an instance) are demonstrated on a wide set of randomly generated instances with 5 ≤ n ≤ 100.     

Partial retrieval of CAD models based on the gradient flows in Lie group

Based on the gradient flows in Lie group, a partial retrieval approach for CAD models is presented in this paper. First, a representation of the face Attributed Relational Graph (ARG) for a CAD model is created from its B-rep model and thus partial retrieval is converted to a subgraph matching problem. Then, an optimization method is adopted to solve the matching problem, where the optimization variable is the vertex mapping and the objective function is the measurement of compatibility between the mapped vertices and between the mapped edges. Different from most previously proposed methods, a homogeneous transformation matrix is introduced to represent the vertex mapping in subgraph matching, whose translational sub-matrix gives the vertex selection in the larger graph and whose orthogonal sub-matrix presents the vertex permutation for the same-sized mapping from the selected vertices to the smaller graph's vertices. Finally, a gradient flow method is developed to search for optimal matching matrix in Special Euclidean group SE(n). Here, a penalty approach is used to handle the constraints on the elements of the matching matrix, which leads its orthogonal part to be a permutation matrix and its translational part to have different integer elements. Experimental results show that it is a promising method to support the partial retrieval of CAD models.     

Sparse stable systems

In the design of decentralized networked systems, it is important to know whether a given network topology can sustain stable dynamics. We consider a basic version of this problem here: given a vector space of sparse real matrices, does it contain a stable (Hurwitz) matrix? Said differently, is a feedback channel (corresponding to a non-zero entry) necessary for stabilization or can it be done without? We provide in this paper a set of necessary conditions and a set of sufficient conditions for the existence of stable matrices in a vector space of sparse matrices. We further prove some properties of the set of sparse matrix spaces that contain Hurwitz matrices. The conditions we exhibit are most easily stated in the language of graph theory, which we thus adopt in this paper.     

Matching hierarchical structures using association graphs

It is well-known that the problem of matching two relational structures can be posed as an equivalent problem of finding a maximal clique in a (derived) “association graph.” However, it is not clear how to apply this approach to computer vision problems where the graphs are hierarchically organized, i.e., are trees, since maximal cliques are not constrained to preserve the partial order. We provide a solution to the problem of matching two trees by constructing the association graph using the graph-theoretic concept of connectivity. We prove that, in the new formulation, there is a one-to-one correspondence between maximal cliques and maximal subtree isomorphisms. This allows us to cast the tree matching problem as an indefinite quadratic program using the Motzkin-Straus theorem, and we use “replicator” dynamical systems developed in theoretical biology to solve it. Such continuous solutions to discrete problems are attractive because they can motivate analog and biological implementations. The framework is also extended to the matching of attributed trees by using weighted association graphs. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees     

Public key cryptosystems based on boolean permutations and their applications

In this paper we propose the use of Boolean permutations to design public key cryptosystems. The security of the cryptosystems is based on the difficulty of inverting Boolean permutations. Using two Boolean permutations for which the inverses are easy to find, one can construct a composite Boolean permutation which is hard to invert. The paper proposes three such Boolean permutation based public key systems. The paper also consider applications of a Boolean permutation based public key system to digital signatures and shared signatures.     

A Lagrangian relaxation network for graph matching

A Lagrangian relaxation network for graph matching is presented. The problem is formulated as follows: given graphs G and g, find a permutation matrix M that brings the two sets of vertices into correspondence. Permutation matrix constraints are formulated in the framework of deterministic annealing. Our approach is in the same spirit as a Lagrangian decomposition approach in that the row and column constraints are satisfied separately with a Lagrange multiplier used to equate the two "solutions". Due to the unavoidable symmetries in graph isomorphism (resulting in multiple global minima), we add a symmetry-breaking self-amplification term in order to obtain a permutation matrix. With the application of a fixpoint preserving algebraic transformation to both the distance measure and self-amplification terms, we obtain a Lagrangian relaxation network. The network performs minimization with respect to the Lagrange parameters and maximization with respect to the permutation matrix variables. Simulation results are shown on 100 node random graphs and for a wide range of connectivities.     

等价关系矩阵的置换合同性质与标准形计算

等价关系在网络分析、图论、模式识别和数据库技术等方面都有许多应用,而任意等价关系矩阵都置换合同于块1-对角矩阵标准形,从置换运算的角度分析置换合同的几条性质,提出基于图的深度优先搜索策略的置换矩阵构造算法：根据等价矩阵关系图搜索路径的性质,将图的深度优先搜索所得顶点路径与初始顶点顺序对比构造置换映射。利用置换分解原理,将置换映射分解成相应的对换乘积,得到最终置换矩阵,完成等价关系矩阵的置换相似判定。为了验证该算法的正确性和效率,设计了一个等价关系矩阵的自动生成算法。实验结果表明,置换矩阵构造算法和等价关系矩阵的自动生成算法简洁且易于理解和实现。     

Object Recognition as Many-to-Many Feature Matching

Object recognition can be formulated as matching image features to model features. When recognition is exemplar-based, feature correspondence is one-to-one. However, segmentation errors, articulation, scale difference, and within-class deformation can yield image and model features which don’t match one-to-one but rather many-to-many. Adopting a graph-based representation of a set of features, we present a matching algorithm that establishes many-to-many correspondences between the nodes of two noisy, vertex-labeled weighted graphs. Our approach reduces the problem of many-to-many matching of weighted graphs to that of many-to-many matching of weighted point sets in a normed vector space. This is accomplished by embedding the initial weighted graphs into a normed vector space with low distortion using a novel embedding technique based on a spherical encoding of graph structure. Many-to-many vector correspondences established by the Earth Mover’s Distance framework are mapped back into many-to-many correspondences between graph nodes. Empirical evaluation of the algorithm on an extensive set of recognition trials, including a comparison with two competing graph matching approaches, demonstrates both the robustness and efficacy of the overall approach.     

A PCA approach for fast retrieval of structural patterns inattributed graphs

An attributed graph (AG) is a useful data structure for representing complex patterns in a wide range of applications such as computer vision, image database retrieval, and other knowledge representation tasks where similar or exact corresponding structural patterns must be found. Existing methods for attributed graph matching (AGM) often suffer from the combinatorial problem whereby the execution cost for finding an exact or similar match is exponentially related to the number of nodes the AG contains. The square matching error of two AGs subject to permutations is approximately relaxed to a square matching error of two AGs subject to orthogonal transformations. Hence, the principal component analysis (PCA) algorithm can be used for the fast computation of the approximate matching error, with a considerably reduced execution complexity. Experiments demonstrate that this method works well and is robust against noise and other simple types of transformations.     

Matching point features under small nonrigid motion

This paper describes a method for matching point features between images of objects that have undergone small nonrigid motion. Feature points are assumed to be available and, given a properly extracted set of feature points, a robust matching is established under the condition that the local nonrigid motion of each point is restricted to a circle of radius δ, where δ is not too large. This is in contrast to other techniques for point matching which assume either rigid motion or nonrigid motion of a known kind. The point matching problem is viewed in terms of weighted bipartite graph matching. In order to account for the possibility that the feature selector can be imprecise, we incorporate a greedy matching strategy with the weighted graph matching algorithm. Our algorithm is robust and insensitive to noise and missing features. The resulting matching can be used with image warping or other techniques for nonrigid motion analysis, image subtraction, etc. We present our experimental results on sequences of mammograms, images of a deformable clay object and satellite cloud images. In the first two cases we provide quantitative comparison with known ground truth.     

Operations on permutations and representation in graph form

Two operations on permutations are defined and some of their properties are illustrated. A particular graph is defined as representation of the permutation set under such operations; this graph consists of strongly connected components only, having at most eight vertices.     

Characterization of Combinatorially Independent Permutation Separability Criteria

The so-called permutation separability criteria are simple operational conditions that are necessary for separability of mixed states of multipartite systems: (1) permute the indices of the density matrix and (2) check if the trace norm of at least one of the resulting operators is greater than one. If it is greater than one then the state is necessarily entangled. A shortcoming of the permutation separability criteria is that many permutations give rise to equivalent separability criteria. Therefore, we introduce a necessary condition for two permutations to yield independent criteria called combinatorial independence. This condition basically means that the map corresponding to one permutation cannot be obtained by concatenating the map corresponding to the second permutation with a norm-preserving map. We characterize completely combina-torially independent criteria, and determine simple permutations that represent all independent criteria. The representatives can be visualized by means of a simple graphical notation. They are composed of three basic operations: partial transpose, and two types of so-called reshufflings. In particular, for a four-partite system all criteria except one are composed of partial transpose and only one type of reshuffling; the exceptional one requires the second type of reshuffling. Furthermore, we show how to obtain efficiently a simple representative for every permutation. This method allows to check easily if two permutations are Combinatorially equivalent or not.     

Analyzing permutation capability of multistage interconnection networks with colored Petri nets

In a multistage interconnection network (MIN) the calculation of the number of permutations of the input terminals into the output terminals is a classic difficult problem. In this paper, we introduce an innovative technique based on Colored Petri Nets (known as CP-nets or CPNs) that will allow us to analyze the permutation capability of arbitrary MINs. We show how to verify whether a MIN is rearrangeable through the state space analysis of the associated CP-net and we measure the permutation capability of non-rearrangeable MINs in terms of the permutations that can be generated. The proposed approach takes advantage of powerful existing software tools, particularly, CPNTools, which is used to explore the occurrence graphs of CP-nets and determine the set of permutations performed by the modeled MINs. This new technique is easy to use and can be efficiently applied to MINs made of cross-bar switches.     

Distributed LQR Design for Identical Dynamically Decoupled Systems

We consider a set of identical decoupled dynamical systems and a control problem where the performance index couples the behavior of the systems. The coupling is described through a communication graph where each system is a node and the control action at each node is only function of its state and the states of its neighbors. A distributed control design method is presented which requires the solution of a single linear quadratic regulator (LQR) problem. The size of the LQR problem is equal to the maximum vertex degree of the communication graph plus one. The design procedure proposed in this paper illustrates how stability of the large-scale system is related to the robustness of local controllers and the spectrum of a matrix representing the desired sparsity pattern of the distributed controller design problem.