Search

Highlights • Always considered graph edit distance (GED) is a metric if edit functions are a metric. • We discern between GED computed through edit path and graph bijection. • Triangle inequality of edit functions not necessary if GED defined by graph bijection. • Important: usually recognition ratio is maximized in non-metric edit functions. Abstract In the presentation of the graph edit distance in 1983 and other newer bibliography, authors state that it is necessary to apply the distance restrictions (non-negativity, identity of indiscernible elements, symmetry and triangle inequality) to each of the edit functions (insertion, deletion and substitution of nodes and edges) involved in the process of computing the graph edit distance to make the graph edit distance a true distance. Moreover, graph edit distance algorithms presented in the last three decades have been based on mapping the edit path that transforms a graph into the other one into a bijection of the graphs in which some null nodes have been added. In this paper, we show that the triangle inequality does not need to be imposed in each edit function if the graph edit distance is defined through an edit path; however, it is necessary if it is defined as a graph bijection. This is an important finding since the triangle inequality is the only restriction that relates different edit functions and concerns the process of tuning the edit functions given a specific application. Hence, on one hand, it would encourage research to define new algorithms based on the edit path instead of the graph bijection and, on the other hand, use edit functions without the restriction, for instance, that the sum of the costs of insertion and deletion of a pair of nodes has to be larger or equal than the cost of substituting them, which could increase the recognition ratio of a concrete application. [ABSTRACT FROM AUTHOR]

Highlights • Networks and graphs are naturally embedded in Euclidean hyperspheres. • Communicability embedding of networks/graphs reveals clusters in networks. • Nonmetric multidimensional scaling allows visualization of networks in 3D communicability space. • Communicability clusters of papers in a citation network reveal levels of mathematization. • Communicability clusters in a gene-gene network reveal genes that co-participate in cancer and other diseases. Abstract A complex network is a condensed representation of the relational topological framework of a complex system. A main reason for the existence of such networks is the transmission of items through the entities of these complex systems. Here, we consider a communicability function that accounts for the routes through which items flow on networks. Such a function induces a natural embedding of a network in a Euclidean high-dimensional sphere. We use one of the geometric parameters of this embedding, namely the angle between the position vectors of the nodes in the hyperspheres, to extract structural information from networks. First we propose a simple method for visualizing networks by reducing the dimensionality of the communicability space to 3-dimensional spheres. Secondly, we use clustering analysis to cluster the nodes of the networks based on their similarities in terms of their capacity to successfully deliver information through the network. After testing these approaches in benchmark networks and compare them with the most used clustering methods in networks we analyze two real-world examples. In the first, consisting of a citation network, we discover citation groups that reflect the level of mathematics used in their publications. In the second, we discover groups of genes that coparticipate in human diseases, reporting a few genes that coparticipate in cancer and other diseases. Both examples emphasize the potential of the current methodology for the discovery of new patterns in relational data. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to present a new method to compare histograms. The main advantage is that there is an important time-complexity reduction with respect to the methods presented before. This reduction is statistically and analytically demonstrated in the paper. The distances between histograms that we presented are defined on a structure called signature, which is a lossless representation of histograms. Moreover, the type of the elements of the sets that the histograms represent are ordinal, nominal and modulo. We show that the computational cost of these distances is for the ordinal and nominal types and for the modulo one, being the number of non-empty bins of the histograms. The computational cost of the algorithms presented in the literature depends on the number of bins of the histograms. In most of the applications, the obtained histograms are sparse; then considering only the non-empty bins drastically decreases the time consumption of the comparison. The distances and algorithms presented in this paper are experimentally validated on the comparison of images obtained from public databases and positioning of mobile robots through the recognition of indoor scenes (captured in a learning stage). [Copyright &y& Elsevier]

Graph-based image segmentation is popular, because graphs can naturally represent image parts and the relationships between them. Whilst many single-scale approaches exist, significant interest has been shown in segmentation hierarchies, which represent image objects at different scales. However, segmenting arbitrary images automatically remains elusive: segmentation is under-specified, with different users expecting different outcomes. Hierarchical segmentation compounds this, since it is unclear where in the hierarchy objects should appear. Users can easily edit flat segmentations to influence the outcome, but editing hierarchical segmentations is harder: indeed, many existing interactive editing techniques make only small, local hierarchy changes. In this paper, we address this by introducing ‘zipping’ operations for segmentation hierarchies to facilitate user interaction. We use these operations to implement algorithms for non-sibling node merging and parent switching, and perform experiments on both 2D and 3D images to show that these latter algorithms can significantly reduce the interaction burden on the user. [ABSTRACT FROM AUTHOR]

The sample mean is one of the most fundamental concepts in statistics. Properties of the sample mean that are well-defined in Euclidean spaces become unclear in graph spaces. This paper proposes conditions under which the following properties are valid: existence, uniqueness, and consistency of means, the midpoint property, necessary conditions of optimality, and convergence results of mean algorithms. The theoretical results address common misconceptions about the graph mean in graph edit distance spaces, serve as a first step towards a statistical analysis of graph spaces, and result in a theoretically well-founded mean algorithm that outperformed six other mean algorithms with respect to solution quality on different graph datasets representing images and molecules. [ABSTRACT FROM AUTHOR]

Abstract: Finding correspondences between two related feature point sets is a basic task in computer vision and pattern recognition. In this paper, we present a novel method for point pattern matching via spectral graph analysis. In particular, we aim to render the spectral matching algorithm more robust for positional jitter and outlier. A local structural descriptor, namely the spectral context, is proposed to describe the attribute domain of point sets, which is fundamentally different from the previous methods. Furthermore, the approximate distance order is defined and employed as the metric for geometric consistency of neighboring points in this work. By combining these two novel ingredients, we formulate feature point set matching as an optimization problem with one-to-one constraints. The correspondences are then obtained by maximizing the given objective function via the technique of probabilistic relaxation. Comparative experiments conducted on both synthetic and real data demonstrate the effectiveness of the proposed method, especially in the presence of positional jitter and outliers. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a robust tracking algorithm to handle drifting problem. This algorithm consists of two parts: the first part is the G&D part that combines Generative model and Discriminative model for tracking, and the second part is the View-Based model for target appearance that corrects the result of the G&D part if necessary. In G&D part, we use the Maximum Margin Projection (MMP) to construct a graph model to preserve both local geometrical and discriminant structures of the data manifold in low dimensions. Therefore, such discriminative subspace combined with traditional generative subspace can benefit from both models. In addition, we address the problem of learning maximum margin projection under the Spectral Regression (SR) which results in significant savings in computational time. To further solve the drift, an online learned sparsely represented view-based model of the target is complementary to the G&D part. When the result of G&D part is unreliable, the view-based model can rectify the result in order to avoid drifting. Experimental results on several challenging video sequences demonstrate the effectiveness and robustness of our approach. [Copyright &y& Elsevier]

Abstract: Deformable shape detection is an important problem in computer vision and pattern recognition. However, standard detectors are typically limited to locating only a few salient landmarks such as landmarks near edges or areas of high contrast, often conveying insufficient shape information. This paper presents a novel statistical pattern recognition approach to locate a dense set of salient and non-salient landmarks in images of a deformable object. We explore the fact that several object classes exhibit a homogeneous structure such that each landmark position provides some information about the position of the other landmarks. In our model, the relationship between all pairs of landmarks is naturally encoded as a probabilistic graph. Dense landmark detections are then obtained with a new sampling algorithm that, given a set of candidate detections, selects the most likely positions as to maximize the probability of the graph. Our experimental results demonstrate accurate, dense landmark detections within and across different databases. [Copyright &y& Elsevier]

Abstract: The problem of segmenting a foreground object out from its complex background is of great interest in image processing and computer vision. Many interactive segmentation algorithms such as graph cut have been successfully developed. In this paper, we present four technical components to improve graph cut based algorithms, which are combining both color and texture information for graph cut, including structure tensors in the graph cut model, incorporating active contours into the segmentation process, and using a “softbrush” tool to impose soft constraints to refine problematic boundaries. The integration of these components provides an interactive segmentation method that overcomes the difficulties of previous segmentation algorithms in handling images containing textures or low contrast boundaries and producing a smooth and accurate segmentation boundary. Experiments on various images from the Brodatz, Berkeley and MSRC data sets are conducted and the experimental results demonstrate the high effectiveness of the proposed method to a wide range of images. [Copyright &y& Elsevier]

Abstract: Principal curves arising as an essential construct in dimensionality reduction and pattern recognition have recently attracted much attention from theoretical as well as practical perspective. Existing methods usually employ the first principal component of the data as an initial estimate of principal curves. However, they may be ineffective when dealing with complex data with self-intersecting characteristics, high curvature, and significant dispersion. In this paper, a new method based on global structure is proposed to detect the principal graph—a set of principal curves from complex data. First, the global structure of the data, called an initial principal graph, is extracted based on a thinning technique, which captures the approximate topological features of the complex data. In terms of the characteristics of the data, vertex-merge step and the improved fitting-and-smoothing phase are then proposed to control the deviation of the principal graph and improve the process of optimizing the principal graph. Finally, the restructuring step introduced by Kégl is used to rectify imperfections of the principal graph. By using synthetic and real-world data sets, the proposed method is compared with other existing algorithms. Experimental results show the effectiveness of the global structure based method. [Copyright &y& Elsevier]

Abstract: This paper aims to address the problem of shape clustering by discovering the common structure which captures the intrinsic structural information of shapes belonging to the same cluster. It is based on a skeleton graph, named common structure skeleton graph (CSSG), which expresses possible correspondences between nodes of the individual skeletons of the cluster. To construct the CSSG, we derive the correspondences by the optimal subsequence bijection (OSB). To cluster the shape data, we apply an agglomerative clustering scheme, in each iteration, the CSSGs are formed from each cluster and the two closest clusters are merged into one. The proposed agglomerative clustering algorithm has been evaluated on several shape data sets, including three articulated shape data sets, Torsello''s data set, and a gesture data set. In all experiments, our method demonstrates effective performance compared to other algorithms. [Copyright &y& Elsevier]

Abstract: In recent years, semi-supervised clustering (SSC) has aroused considerable interests from the machine learning and data mining communities. In this paper we propose a novel SSC approach with enhanced spectral embedding (ESE), which not only considers the geometric structure information contained in data sets, but also can make use of the given side information such as pairwise constraints. Specially, we first construct a symmetry-favored k-NN graph, which is highly robust to noise and outliers, and can reflect the underlying manifold structures of data sets. Then we learn the enhanced spectral embedding towards an ideal data representation as consistent with the given pairwise constraints as possible. Finally, by using the regularization of spectral embedding we formulate learning the new data representation as a semidefinite-quadratic-linear programming (SQLP) problem, which can be efficiently solved. Experimental results on a variety of synthetic and real-world data sets show that our ESE approach outperforms the state-of-the-art SSC algorithms in terms of speed and quality on both vector-based and graph-based clustering. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a two-dimensional histogram equalization (2DHE) algorithm which utilizes contextual information around each pixel to enhance the contrast of an input image. The algorithm is based on the observation that the contrast in an image can be improved by increasing the grey-level differences between each pixel and its neighbouring pixels. The image equalization is achieved by assuming that for a given image, the modulus of the grey-level differences between pixels and their neighbouring pixels are equally distributed. The well-known global histogram equalization algorithm is a special case of 2DHE when contextual information is not utilized. 2DHE is easy to implement requiring only a small number of simple arithmetic operations and is thus suitable for real-time contrast enhancement applications. Experimental results show that 2DHE produces better or comparable enhanced images than several state-of-the-art algorithms. The only parameter in 2DHE which requires tuning is the size of the spatial neighbourhood support which provides the contextual information for a given dynamic range of the enhanced image. An automated parameter selection algorithm is also presented. The algorithm can be applied to a wide range of image types. [Copyright &y& Elsevier]

Abstract: In this paper, we present a framework for object categorization via sketch graphs that incorporate shape and structure information. In this framework, we integrate the learnable And–Or graph model, a hierarchical structure that combines the reconfigurability of a stochastic context free grammar (SCFG) with the constraints of a Markov random field (MRF). Considering the computation efficiency, we generalize instances from the And–Or graph models and perform a set of sequential tests for cascaded object categorization, rather than directly inferring with the And–Or graph models. We study 33 categories, each consisting of a small data set of 30 instances, and 30 additional templates with varied appearance are generalized from the learned And–Or graph model. These samples better span the appearance space and form an augmented training set of 1980 (60×33) training templates. To perform recognition on a testing image, we use a set of sequential tests to project into different representation spaces to narrow the number of candidate matches in . We use “graphlets” (structural elements), as our local features and model at each stage using histograms of graphlets over categories, histograms of graphlets over object instances, histograms of pairs of graphlets over objects, and shape context. Each test is increasingly computationally expensive, and by the end of the cascade we have a small candidate set remaining to use with our most powerful test, a top-down graph matching algorithm. We apply the proposed approach on the challenging public dataset including 33 object categories, and achieve state-of-the-art performance. [Copyright &y& Elsevier]

Abstract: This paper describes a graph clustering algorithm that aims to minimize the normalized cut criterion and has a model order selection procedure. The performance of the proposed algorithm is comparable to spectral approaches in terms of minimizing normalized cut. However unlike spectral approaches, the proposed algorithm scales to graphs with millions of nodes and edges. The algorithm consists of three components that are processed sequentially: a greedy agglomerative hierarchical clustering procedure, model order selection, and a local refinement. For a graph of n nodes and O(n) edges, the computational complexity of the algorithm is , a major improvement over the complexity of spectral methods. Experiments are performed on real and synthetic networks to demonstrate the scalability of the proposed approach, the effectiveness of the model order selection procedure, and the performance of the proposed algorithm in terms of minimizing the normalized cut metric. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a novel Fast Affinity Propagation clustering approach (FAP). FAP simultaneously considers both local and global structure information contained in datasets, and is a high-quality multilevel graph partitioning method that can implement both vector-based and graph-based clustering. First, a new Fast Sampling algorithm (FS) is proposed to coarsen the input sparse graph and choose a small number of final representative exemplars. Then a density-weighted spectral clustering method is presented to partition those exemplars on the global underlying structure of data manifold. Finally, the cluster assignments of all data points can be achieved through their corresponding representative exemplars. Experimental results on two synthetic datasets and many real-world datasets show that our algorithm outperforms the state-of-the-art original affinity propagation and spectral clustering algorithms in terms of speed, memory usage, and quality on both vector-based and graph-based clustering. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce a novel shape/object retrieval algorithm shortest path propagation (SSP). Given a query object q and a target database object p, we explicitly find the shortest path between them in the distance manifold of the database objects. Then a new distance measure between q and p is learned based on the database objects on the shortest path to replace the original distance measure. The promising results on both MEPG-7 shape dataset and a protein dataset demonstrate that our method can significantly improve the ranking of the object retrieval. [Copyright &y& Elsevier]

Abstract: In this paper we present the Rack algorithm for the detection of optimal non-star-shaped contours in images. It is based on the combination of a user-driven image transformation and dynamic programming. The fundamental idea is to interactively specify and edit the general shape of the desired object by using a rack. This rack is used to model the image as a directed acyclic weighted graph that contains a path corresponding to the expected contour. In this graph, the shortest path with respect to an adequate cost function can be calculated efficiently via dynamic programming. The experimental results indicate the algorithm''s ability of combining an acceptable amount of user interaction with generally good segmentation results. [Copyright &y& Elsevier]

Abstract: Graphs are a powerful and popular representation formalism in pattern recognition. Particularly in the field of document analysis they have found widespread application. From the formal point of view, however, graphs are quite limited in the sense that the majority of mathematical operations needed to build common algorithms, such as classifiers or clustering schemes, are not defined. Consequently, we observe a severe lack of algorithmic procedures that can directly be applied to graphs. There exists recent work, however, aimed at overcoming these limitations. The present paper first provides a review of the use of graph representations in document analysis. Then we discuss a number of novel approaches suitable for making tools from statistical pattern recognition available to graphs. These novel approaches include graph kernels and graph embedding. With several experiments, using different data sets from the field of document analysis, we show that the new methods have great potential to outperform traditional procedures applied to graph representations. [ABSTRACT FROM AUTHOR]

Abstract: The RELIEF algorithm is a popular approach for feature weighting. Many extensions of the RELIEF algorithm are developed, and I-RELIEF is one of the famous extensions. In this paper, I-RELIEF is generalized for supervised distance metric learning to yield a Mahananobis distance function. The proposed approach is justified by showing that the objective function of the generalized I-RELIEF is closely related to the expected leave-one-out nearest-neighbor classification rate. In addition, the relationships among the generalized I-RELIEF, the neighbourhood components analysis, and graph embedding are also pointed out. Experimental results on various data sets all demonstrate the superiority of the proposed approach. [Copyright &y& Elsevier]

Abstract: Data clustering plays an important role in many disciplines, including data mining, machine learning, bioinformatics, pattern recognition, and other fields, where there is a need to learn the inherent grouping structure of data in an unsupervised manner. There are many clustering approaches proposed in the literature with different quality/complexity tradeoffs. Each clustering algorithm works on its domain space with no optimum solution for all datasets of different properties, sizes, structures, and distributions. In this paper, a novel cooperative clustering (CC) model is presented. It involves cooperation among multiple clustering techniques for the goal of increasing the homogeneity of objects within the clusters. The CC model is capable of handling datasets with different properties by developing two data structures, a histogram representation of the pair-wise similarities and a cooperative contingency graph. The two data structures are designed to find the matching sub-clusters between different clusterings and to obtain the final set of clusters through a coherent merging process. The cooperative model is consistent and scalable in terms of the number of adopted clustering approaches. Experimental results show that the cooperative clustering model outperforms the individual clustering algorithms over a number of gene expression and text documents datasets. [Copyright &y& Elsevier]

Abstract: A novel method of recognition of hand postures of Polish Sign Language (PSL) is presented in the paper. The method is based on a syntactic pattern recognition paradigm. A construction of algorithms for generating a structural (graph) description of hand postures that can be analyzed with the graph grammar parsing model has been a main objective of the research. A structural description generated with these algorithms is unique and unambiguous that results in good discriminative properties of the method. [Copyright &y& Elsevier]

Abstract: In recent years, the spectral clustering method has gained attentions because of its superior performance. To the best of our knowledge, the existing spectral clustering algorithms cannot incrementally update the clustering results given a small change of the data set. However, the capability of incrementally updating is essential to some applications such as websphere or blogsphere. Unlike the traditional stream data, these applications require incremental algorithms to handle not only insertion/deletion of data points but also similarity changes between existing points. In this paper, we extend the standard spectral clustering to such evolving data, by introducing the incidence vector/matrix to represent two kinds of dynamics in the same framework and by incrementally updating the eigen-system. Our incremental algorithm, initialized by a standard spectral clustering, continuously and efficiently updates the eigenvalue system and generates instant cluster labels, as the data set is evolving. The algorithm is applied to a blog data set. Compared with recomputation of the solution by the standard spectral clustering, it achieves similar accuracy but with much lower computational cost. It can discover not only the stable blog communities but also the evolution of the individual multi-topic blogs. The core technique of incrementally updating the eigenvalue system is a general algorithm and has a wide range of applications—as well as incremental spectral clustering—where dynamic graphs are involved. This demonstrates the wide applicability of our incremental algorithm. [Copyright &y& Elsevier]

Abstract: In line generalization, results depend very much on the characteristics of the line in question. For this reason it would be useful to obtain an automatic segmentation and enrichment of lines in order to apply to each section the best algorithm and the most appropriate parameter. In this paper, we present a line segmentation methodology based on a sinuosity pattern recognition measured by means of the effective-area as derived from the Visvalingam–Whyatt algorithm. Sections are determined by applying the Douglas–Peucker algorithm to a shape signature of the line: an effective-area/length space representation. An experiment is carried out with a set of 24 road features from a 1:25000 scale map with a recommendation of the value of some parameters and a procedure for the automated search of that defined as natural number of sections. This procedure is based in the search of zones of stability in a graph of the number of sections when applying Douglas–Peucker to the shape signature. The results are positively assessed by an independent group of experts. [Copyright &y& Elsevier]

Abstract: Labeling of connected components in a binary image is one of the most fundamental operations in pattern recognition: labeling is required whenever a computer needs to recognize objects (connected components) in a binary image. This paper presents a fast two-scan algorithm for labeling of connected components in binary images. We propose an efficient procedure for assigning provisional labels to object pixels and checking label equivalence. Our algorithm is very simple in principle, easy to implement, and suitable for hardware and parallel implementation. We show the correctness of our algorithm, analyze its complexity, and compare it with other labeling algorithms. Experimental results demonstrated that our algorithm is superior to conventional labeling algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the applicability of graph cuts to the SFS (shape-from-shading) problem. We propose a new semi-global method for SFS using graph cuts. The new algorithm combines the local method proposed by Lee and Rosenfeld [C.H. Lee, A. Rosenfeld, Improved methods of estimating shape from shading using the light source coordinate system, Artif. Intell. 26 (1985) 125–143] and a global method using an energy minimization technique. By employing a new global energy minimization formulation, the convex/concave ambiguity problem of Lee and Rosenfeld''s method can be resolved efficiently. A new combinatorial optimization technique, the graph cuts method, is used for the minimization of the proposed energy functional. Experimental results on a variety of synthetic and real-world images show that the proposed algorithm reconstructs the 3-D shape of objects very efficiently. [Copyright &y& Elsevier]

• Matching line segments for stereo images can be employed relying only on the geometry constraint. • The association graph constructed with the epipolar constraint is invariant to the projective transformation. • Employing the random walk on the association graph enables ranking the candidate. • The proposed algorithm outperformed the state of the art methods in the experiments, especially in the scenes of the wide baseline, the steep viewpoint change, and the dense line segment. This paper presents a novel method for matching line segments between stereo images. Given the fundamental matrix, the local homography can be over determined with pairwise line segment candidates. We exploit this constraint to initialize the candidate and construct the novel homography graph. Because the constraint between the node is based on the epipolar geometry, the homography graph is invariant to the local projective transformation. We employ the reweighted random walk on the graph to rank the candidate, then, we propose the constrained-greedy algorithm to obtain the reliable match. To the best of our knowledge, this is the first study to embed the epipolar geometry into the graph matching theory for the line segment matching. When evaluated on the 32 image patches, our method outperformed the state of the art methods, especially in the scenes of the wide baseline, steep viewpoint changes and dense line segments. The proposed algorithm is available at https://github.com/weidong-whu/line-match-RRW. [ABSTRACT FROM AUTHOR]