Search

Abstract: This paper proposes a new framework for extracting dense disparity maps from a multispectral stereo rig. The system is constructed with an infrared and a color camera. It is intended to explore novel multispectral stereo matching approaches that will allow further extraction of semantic information. The proposed framework consists of three stages. Firstly, an initial sparse disparity map is generated by using a cost function based on feature matching in a multiresolution scheme. Then, by looking at the color image, a set of planar hypotheses is defined to describe the surfaces on the scene. Finally, the previous stages are combined by reformulating the disparity computation as a global minimization problem. The paper has two main contributions. The first contribution combines mutual information with a shape descriptor based on gradient in a multiresolution scheme. The second contribution, which is based on the Manhattan-world assumption, extracts a dense disparity representation using the graph cut algorithm. Experimental results in outdoor scenarios are provided showing the validity of the proposed framework. [Copyright &y& Elsevier]

Abstract: In this paper a fast algorithm to compute cohomology group generators of cellular decomposition of any orientable open or closed 2-manifold is described. The presented algorithm is a dual version of algorithm to compute homology generators presented by David Eppstein in “Dynamic generators of topologically embedded graphs” and developed by Jeff Erickson and Kim Whittlesey in “Greedy optimal homotopy and homology generators”. Some parts of the paper bases on ideas presented in “Optimal discrete Morse functions for 2-manifolds” by Thomas Lewiner, Helio Lopes and Geovan Tavares. Extension of the algorithm to some non-manifold cases is provided. [Copyright &y& Elsevier]

Highlights • Reducing the graph size by eliminating the nodes based on their degree measure. • Extension to graph edit distance based on node contraction. • Applied the proposed algorithm on letter and AIDS dataset. • Can act as a trade-off between time and accuracy considerations. Abstract Graph matching is the task of computing the similarity between two graphs. It is widely used in graph-based structural pattern recognition. Error-tolerant graph matching is a type of graph matching, in which a similarity between two graphs is computed based on some tolerance value whereas in exact graph matching a strict one-to-one correspondence is required between two graphs. In this paper, we present an approach to error-tolerant graph matching using node contraction where the given graph is transformed into another graph by contracting smaller degree nodes. We use this scheme to extend the notion of graph edit distance, which can be used as a trade-off between execution time and accuracy requirements of various graph matching applications. [ABSTRACT FROM AUTHOR]

Highlights • we use background weight map to provide seeds for manifold ranking. • we extend the traditional manifold ranking to second-order formula. • we establish a third-order smoothness framework to optimize the saliency map. Abstract Graph-based approaches for saliency detection have attracted much attention and been exploited widely in recent years. In this paper, we present a new method to promote the performance of existing manifold ranking algorithms. Initially, we use background weight map to provide seeds for manifold ranking; Next, we extend the traditional manifold ranking to second-order formula and add a weight mask to its fitting term. Finally, for further improvement of the performance, we establish a third-order smoothness framework to optimize the saliency map. In the experiments, we compare two versions (manifold ranking with and without optimization) of our model with seven previous methods and test them on several benchmark datasets. Different kinds of strategies are also adopted for evaluation and the results demonstrate that our method achieves the state-of-the-art. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new fuzzy clustering algorithm for the mode-seeking framework. Given a dataset in R d , we define regions of high density that we call cluster cores. We then consider a random walk on a neighborhood graph built on top of our data points which is designed to be attracted by high density regions. The strength of this attraction is controlled by a temperature parameter β  > 0. The membership of a point to a given cluster is then the probability for the random walk to hit the corresponding cluster core before any other. While many properties of random walks (such as hitting times, commute distances, etc.) have been shown to eventually encode purely local information when the number of data points grows, we show that the regularization introduced by the use of cluster cores solves this issue. Empirically, we show how the choice of β influences the behavior of our algorithm: for small values of β the result is close to hard mode-seeking whereas when β is close to 1 the result is similar to the output of a (fuzzy) spectral clustering. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new distance called the k -max distance that is intended for graphs and images. The length of a path is defined as the sum of the k maximum arc weights along the path. The distance between two nodes is the length of the shortest path between them. We show that the k -max distance is a metric. The algorithm for computing the k -max distance is presented. Certain positive properties of the k -max distance are shown, namely in the context of measuring the distances for image segmentation. The comparison with the geodesic distance, the max-arc distance, the minimum barrier distance, and the random walker technique is carried out in the segmentation of real-life images. [ABSTRACT FROM AUTHOR]

In this paper, we propose and explain the use of anytime algorithms in graph matching (GM). GM methods have been involved in many pattern recognition problems. In such a context, GM methods are part of a more complex retrieval system that imposes time and memory constraints on such methods. Anytime algorithms are well suited for use in such an uncertain environment. An anytime algorithm quickly provides the first solution to the problem, finds a list of improved solutions and eventually converges to the optimal solution instead of providing one and only one solution (i.e., the optimal solution). We describe how to convert a recent depth-first GM method into an anytime one. By constraining the solver, the algorithm creates an anytime heuristic search algorithm that allows a flexible trade-off between the search time and the solution quality. We analyze the properties of the resulting anytime algorithm and consider its performance in terms of the deviation of the provided solution from the optimal or the best one found by a state-of-the-art method. Experiments were carried out on seven different types of graph datasets. Moreover, the adopted algorithm was compared to four approximate error-tolerant GM methods. Results showed that the anytime GM can outperform suboptimal methods by only waiting for a small amount of supplementary time. This conclusion brings into question the usual evidence that claims that it is impossible to use optimal GM methods in real-world applications. [ABSTRACT FROM AUTHOR]

Recently a delta-density based clustering (DDC) algorithm was proposed to cluster data efficiently by fast searching density peaks. In the DDC method, the density and a new-defined criterion delta-distance are utilized. The examples with anomalously large delta-density values are treated as cluster centers, then the remaining are assigned the same cluster label as their neighbor with higher density. However there are two challenges for the DDC algorithm. First, no rules are available to judge density-delta values as “anomalously large” or not. Second, the decision graph might produce the redundant examples with “anomalous large” density-delta values, as we define as the “decision graph fraud” problem. In this paper, an improved and automatic version of the DDC algorithm, named as 3DC clustering, is proposed to overcome those difficulties. The 3DC algorithm is motivated by the divide-and-conquer strategy and the density-reachable concept in the DBSCAN framework. It can automatically find the correct number of clusters in a recursive way. Experiments on artificial and real world data show that the 3DC clustering algorithm has a comparable performance with the supervised-clustering baselines and outperforms the unsupervised DDCs, which utilize the novelty detection strategies to select the “anomalously large” density-delta examples for cluster centers. [ABSTRACT FROM AUTHOR]

Graph-based spectral clustering algorithms involve the analysis of an affinity matrix. The latter defines the pairwise similarity relations among data points. Popular graph partitioning algorithms typically involve a normalization step that reflects itself onto an affinity matrix normalization step in spectral clustering algorithms. In this paper, we show that affinity matrix normalization with constant row/column sum guarantees the invariance of the size-weighted sum of the between- and within-cluster graph association; a property conceptually equivalent to the data variance decomposition exploited by the standard k -means algorithm. From this observation, we demonstrate that the solution of numerous spectral clustering methods can be obtained using the standard graph ratio cut objective function. We have identified in the literature 7 such affinity matrix normalization schemes relevant to spectral clustering. Clustering experiments performed with these 7 normalization schemes on 17 benchmark datasets are presented. As a general rule, it is observed that the appropriate normalization method depends on the dataset. A geometric interpretation in the feature space (FS) of such a normalization scheme for k -way spectral clustering is also presented. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of matching unrooted unordered labeled trees, which refers to the task of evaluating the distance between trees. One of the most famous formalizations of this problem is the computation of the edit distance defined as the minimum-cost sequence of edit operations that transform one tree into another. Unfortunately, this problem has been proved to be NP-complete. In this paper, we propose a new algorithm to measure distance between unrooted unordered labeled trees. This algorithm uses a specific graph coloring to decompose the trees into small components (stars and bistars). Then, it determines a distance between two trees by computing the edit distance between their components. We prove that the proposed distance is a pseudo-metric and we analyze its time complexity. Our experimental evaluations on large synthetic and real world datasets confirm our analytical results and suggest that the distance we propose is accurate and its algorithm is scalable. [Copyright &y& Elsevier]

Abstract: This paper proposes two efficient kernels for comparing acyclic, directed graphs. The first kernel counts the number of common paths and allows for weighing according to path-length and/or according to the vertices contained in each particular path. The second kernel counts the number of paths in common minors of the graphs involved and allows for length- and vertex-weighting too. Both kernels have algorithmic complexity that is cubic in the size of the vertex-set. The performance of the algorithms is concisely demonstrated using synthetic and real data. [Copyright &y& Elsevier]

Abstract: Graph comparison algorithms based on metric space embedding have been proven robust in graph clustering and classification. In this paper we propose graph embedding method exploiting ordered invariants of distance k-graphs, which encode structure of shortest-paths. We study degree histograms of those graphs and use them to construct permutation invariant graph representation called vertex B-matrix. In order to extract more information from structural patterns we also define edge distance k-graphs and associated edge B-matrix. Next, several new graph characteristics obtained by condensing information stored in B-matrices are introduced. We demonstrate that our approach provides stable embedding, which captures relevant graph features. Experiments on classification with satellite photo and mutagenicity benchmark datasets revealed, that new descriptors allow for distinguishing graphs with non trivial structural differences. Moreover, they appear to outperform descriptors based on heat kernel matrix, being at the same time more effective computationally. In the end we test feature selection on B-matrices showing that selecting right B-submatrix can improve classification rate on testing datasets. [Copyright &y& Elsevier]

Abstract: Isometric mapping (Isomap) is a popular nonlinear dimensionality reduction technique which has shown high potential in visualization and classification. However, it appears sensitive to noise or scarcity of observations. This inadequacy may hinder its application for the classification of microarray data, in which the expression levels of thousands of genes in a few normal and tumor sample tissues are measured. In this paper we propose a double-bounded tree-connected variant of Isomap, aimed at being more robust to noise and outliers when used for classification and also computationally more efficient. It differs from the original Isomap in the way the neighborhood graph is generated: in the first stage we apply a double-bounding rule that confines the search to at most k nearest neighbors contained within an ε-radius hypersphere; the resulting subgraphs are then joined by computing a minimum spanning tree among the connected components. We therefore achieve a connected graph without unnaturally inflating the values of k and ε. The computational experiences show that the new method performs significantly better in terms of accuracy with respect to Isomap, k-edge-connected Isomap and the direct application of support vector machines to data in the input space, consistently across seven microarray datasets considered in our tests. [Copyright &y& Elsevier]

Abstract: Combinatorial maps explicitly encode orientations of edges around vertices, and have been used in many fields. In this paper, we address the problem of searching for patterns in model maps by putting forward the concept of symbol graph. A symbol graph will be constructed and stored for each model map in the preprocessing. Furthermore, an algorithm for submap isomorphism is presented based on symbol sequence searching in the symbol graphs. The computational complexity of this algorithm is quadratic in the worst case if we neglect the preprocessing step. [Copyright &y& Elsevier]

Abstract: The increasing growth of data on protein–protein interaction (PPI) networks has boosted research on their comparative analysis. In particular, recent studies proposed models and algorithms for performing network alignment, that is, the comparison of networks across species for discovering conserved functional complexes. In this paper, we present an algorithm for dividing PPI networks, prior to their alignment, into small sub-graphs that are likely to cover conserved complexes. This allows one to perform network alignment in a modular fashion, by acting on pairs of resulting small sub-graphs from different species. The proposed dividing algorithm combines a graph-theoretical property (articulation) with a biological one (orthology). Extensive experiments on various PPI networks are conducted in order to assess how well the sub-graphs generated by this dividing algorithm cover protein functional complexes and whether the proposed pre-processing step can be used for enhancing the performance of network alignment algorithms. Source code of the dividing algorithm is available upon request for academic use. [Copyright &y& Elsevier]

Abstract: Single training image face recognition is one of the main challenges to appearance-based pattern recognition techniques. Many classical dimensionality reduction methods such as LDA have achieved success in face recognition field, but cannot be directly used to the single training image scenario. Recent graph-based semi-supervised dimensionality reduction (SSDR) provides a feasible strategy to deal with such problem. However, most of the existing SSDR algorithms such as semi-supervised discriminant analysis (SDA) are locality-oriented and generally suffer from the following issues: (1) they need a large number of unlabeled training samples to estimate the manifold structure in data, but such extra samples may not be easily obtained in a given face recognition task; (2) they model the local geometry of data by the nearest neighbor criterion which generally fails to obtain sufficient discriminative information due to the high-dimensionality of face image space; (3) they construct the underlying adjacency graph (or data-dependent regularizer) using a fixed neighborhood size for all the sample points without considering the actual data distribution. In this paper, we develop a new graph-based SSDR algorithm called sparsity preserving discriminant analysis (SPDA) to address these problems. More specifically, (1) the graph in SPDA is constructed by sparse representation, and thus the local structure in data is automatically modeled instead of being manually predefined. (2) With the natural discriminative power of sparse representation, SPDA can remarkably improve recognition performance only resorting to very few extra unlabeled samples. (3) A simple ensemble strategy is developed to accelerate graph construction, which results in an efficient ensemble SPDA algorithm. Extensive experiments on both toy and real face data sets are provided to validate the feasibility and effectiveness of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: This paper proposes a novel algorithm that decomposes the 3D shape into meaningful parts based on Poisson equation. The whole algorithm is divided into three steps. Firstly, shape signature is defined with Poisson equation. Secondly, the binary decomposition based on shape signature is recursively performed to get a coarse decomposition result. Finally, the graph-based minimum cut is used to refine the jaggy boundaries in the initial result. The proposed algorithm not only obtains a set of meaningful parts, but also is robust in the case of deformation, rotation and other transformations. Furthermore, it can process large 3D shapes in an efficient way. [Copyright &y& Elsevier]