The Laplace-Beltrami operator has established itself in the field of non-rigid shape analysis due to its many useful properties such as being invariant under isometric transformation, having a countable eigensystem forming an orthonormal basis, and fully characterizing geodesic distances of the manifold. However, this invariancy only applies under isometric deformations, which leads to a performance breakdown in many real-world applications. In recent years emphasis has been placed upon extracting optimal features using deep learning methods, however spectral signatures play a crucial role and still add value. In this paper we take a step back, revisiting the LBO and proposing a supervised way to learn several operators on a manifold. Depending on the task, by applying these functions, we can train the LBO eigenbasis to be more task-specific. The optimization of the LBO leads to enormous improvements to established descriptors such as the heat kernel signature in various tasks such as retrieval, classification, segmentation, and correspondence, proving the adaptation of the LBO eigenbasis to both global and highly local learning settings.

Over the past few years, artificial intelligence (AI) has emerged as a transformative force in drug discovery and development (DDD), revolutionizing many aspects of the process. This survey provides a comprehensive review of recent advancements in AI applications within early drug discovery and post-market drug assessment. It addresses the identification and prioritization of new therapeutic targets, prediction of drug-target interaction (DTI), design of novel drug-like molecules, and assessment of the clinical efficacy of new medications. By integrating AI technologies, pharmaceutical companies can accelerate the discovery of new treatments, enhance the precision of drug development, and bring more effective therapies to market. This shift represents a significant move towards more efficient and cost-effective methodologies in the DDD landscape.

With the development of deep learning in remote sensing (RS) image change detection (CD), the dependence of CD models on labeled data has become an important problem. To make better use of the comparatively resource-saving unlabeled data, the CD method based on semi-supervised learning (SSL) is worth further study. This article proposes a reliable contrastive learning (RCL) method for semi-supervised RS image CD. First, according to the task characteristics of CD, we design the contrastive loss based on the changed areas to enhance the model’s feature extraction ability for changed objects. Then, to improve the quality of pseudo labels in SSL, we use the uncertainty of unlabeled data to select reliable pseudo labels for model training. Combining these methods, semi-supervised CD models can make full use of unlabeled data. Extensive experiments on three widely used CD datasets demonstrate the effectiveness of the proposed method. The results show that our semi-supervised approach has a better performance than related methods. The code is available athttps://github.com/VCISwang/RC-Change-Detection.

In this article, a novel R-convolution kernel, named the fast quantum walk kernel (FQWK), is proposed for unattributed graphs. In FQWK, the similarity of the neighborhood-pair substructure between two nodes is measured via the superposition amplitude of quantum walks between those nodes. The quantum interference in this kind of local substructures provides more information on the substructures so that FQWK can capture finer-grained local structural features of graphs. In addition, to efficiently compute the transition amplitudes of multistep discrete-time quantum walks, a fast recursive method is designed. Thus, compared with all the existing kernels based on the quantum walk, FQWK has the highest computation speed. Extensive experiments demonstrate that FQWK outperforms state-of-the-art graph kernels in terms of classification accuracy for unattributed graphs. Meanwhile, it can be applied to distinguish a larger family of graphs, including cospectral graphs, regular graphs, and even strong regular graphs, which are not distinguishable by classical walk-based methods.

The target of graph embedding is to embed graphs in vector space such that the embedded feature vectors follow the differences and similarities of the source graphs. In this paper, a novel method named Frequency Filtering Embedding (FFE) is proposed which uses graph Fourier transform and Frequency filtering as a graph Fourier domain operator for graph feature extraction. Frequency filtering amplifies or attenuates selected frequencies using appropriate filter functions. Here, heat, anti-heat, part-sine and identity filter sets are proposed as the filter functions. A generalized version of FFE named GeFFE is also proposed by defining pseudo-Fourier operators. This method can be considered as a general framework for formulating some previously defined invariants in other works by choosing a suitable filter bank and defining suitable pseudo-Fourier operators. This flexibility empowers GeFFE to adapt itself to the properties of each graph dataset unlike the previous spectral embedding methods and leads to superior classification accuracy relative to the others. Utilizing the proposed part-sine filter set, which its members filter different parts of the spectrum in turn, improves the classification accuracy of GeFFE method. Additionally, GeFFE resolves the cospectrality problem entirely in tested datasets.

Finding an optimal assignment between two sets of objects is a fundamental problem arising in many applications, including the matching of 'bag-of-words' representations in natural language processing and computer vision. Solving the assignment problem typically requires cubic time and its pairwise computation is expensive on large datasets. In this paper, we develop an algorithm which can find an optimal assignment in linear time when the cost function between objects is represented by a tree distance. We employ the method to approximate the edit distance between two graphs by matching their vertices in linear time. To this end, we propose two tree distances, the first of which reflects discrete and structural differences between vertices, and the second of which can be used to compare continuous labels. We verify the effectiveness and efficiency of our methods using synthetic and real-world datasets.

In this paper, we develop a variational principle from the von Neumann entropy for directed graph evolution. We minimise the change of entropy over time to investigate how directed networks evolve under the Euler-Lagrange equation. We commence from our recent work in which we show how to compute the approximate von Neumann entropy for a directed graph based on simple in and out degree statistics. To formulate our variational principle we commence by computing the directed graph entropy difference between different time epochs. This is controlled by the ratios of the in-degree and out-degrees at the two nodes forming a directed edge. It also reveals how the entropy change is related to correlations between the changes in-degree ratio and in-degree, and their initial values. We conduct synthetic experiments with three widely studied complex network models, namely Erdos-Renyi random graphs, Watts-Strogatz small-world networks, and Barabasi-Albert scale-free networks, to simulate the in-degree and out-degree distribution. Our model effectively captures the directed structural transitions in the dynamic network models. We also apply the method to the real-world financial networks. These networks reflect stock price correlations on the New York Stock Exchange(NYSE) and can be used to characterise stable and unstable trading periods. Our model not only effectively captures how the directed network structure evolves with time, but also allows us to detect periods of anomalous network behaviour.

Abstract We present intrinsic methods to address the fundamental problem of segmenting a mesh into a specified number of patches with a uniform size and a controllable overlap. Although never addressed in the literature, such a segmentation is useful for a wide range of processing operations where patches represent local regions and overlaps regularize solutions in neighbour patches. Further, we propose a symmetry‐aware distance measure and symmetric modification to furthest‐point sampling, so that our methods can operate on semantically symmetric meshes. We introduce quantitative measures of patch size uniformity and symmetry, and show that our segmentation outperforms state‐of‐the‐art alternatives in experiments on a well‐known dataset. We also use our segmentation in illustrative applications to texture stitching and synthesis where we improve results over state‐of‐the‐art approaches.

We present a novel approach to the computation of dense correspondence maps between shapes in a non-rigid setting. The problem is defined in terms of functional correspondences. We deal with the non-injectivity of the solution of the functional map framework due to the under-determinedness of the original problem. Key to our approach is the injectivity constraint plugged directly into the problem to optimize, achieved casting it as an assignment problem. This leads to an iterative process which yields a high quality bijective map between the shapes. In the experimental section we present both quantitative and qualitative results, showing that the proposed approach is competitive with the current state-of-the-art on quasi-isometric shape matching benchmarks.

In this paper, we use the Maxwell-Boltzmann partition function to compute network entropy. The partition function is used to model the energy level population statistics where the network is in thermodynamic equilibrium with a heat-bath. Here the network Hamiltonian operator defines a set of energy levels occupied by particles in thermal equilibrium. These energy levels are given by the eigenvalues of the normalized Laplacian matrix. In other words, we investigate a thermalised version of the system normally studied in spectral graph theory, where the thermalisation accounts for noise in the system. We provide a systematic study of the entropy resulting from this characterization. Compared to previous work based on using von Neumann network entropy, this thermodynamic quantity is effective in characterizing changes of network structure and distinguishing different types of network models (e.g. Erdős-Rényi random graphs, small world networks, and scale free networks). Numerical experiments on real world data-sets are presented to evaluate the qualitative and quantitative differences in performance.

In this paper, we present a novel method for constructing a generative model to analyze the structure of labeled data. Given a time-series of sample graphs, we aim to learn a so-called “supergraph” that best describes the underlying average connectivity structure presenting in the data. In this time-series the vertex set is fixed and labeled and the set of possible connections between vertices change with time. The supergraph represents these changes with a Gaussian probability distribution for the connection weights on each individual edge. This structure is fitted to the time-series data by minimizing a description length criterion, with the von Neumann entropy controlling the complexity of the fitted model structure and the Gaussian log-likelihood controlling the mean edge weights and variances. We further show this fitting process can be optimized by using a new fixed-point iteration scheme which locates the elements of the optimal weighted adjacency matrix of the supergraph. We show the iteration process is in fact governed by the partial derivative of the von Neumann entropy. In the experiments, the resulting generative model is shown to be an effective tool for analyzing the underlying connectivity structure of time-evolving networks in the financial domain, and in particular locating critical events and distinct time epochs in their evolution.

The success of kernel methods has initiated the design of novel positive semidefinite functions, in particular for structured data. A leading design paradigm for this is the convolution kernel, which decomposes structured objects into their parts and sums over all pairs of parts. Assignment kernels, in contrast, are obtained from an optimal bijection between parts, which can provide a more valid notion of similarity. In general however, optimal assignments yield indefinite functions, which complicates their use in kernel methods. We characterize a class of base kernels used to compare parts that guarantees positive semidefinite optimal assignment kernels. These base kernels give rise to hierarchies from which the optimal assignment kernels are computed in linear time by histogram intersection. We apply these results by developing the Weisfeiler-Lehman optimal assignment kernel for graphs. It provides high classification accuracy on widely-used benchmark data sets improving over the original Weisfeiler-Lehman kernel.

Quantification of symmetries in complex networks is typically done globally in terms of automorphisms. Extending previous methods to locally assess the symmetry of nodes is not straightforward. Here we present a new framework to quantify the symmetries around nodes, which we call connectivity patterns. We develop two topological transformations that allow a concise characterization of the different types of symmetry appearing on networks and apply these concepts to six network models, namely the Erd\H{o}s-R\'enyi, Barab\'asi-Albert, random geometric graph, Waxman, Voronoi and rewired Voronoi. Real-world networks, namely the scientific areas of Wikipedia, the world-wide airport network and the street networks of Oldenburg and San Joaquin, are also analyzed in terms of the proposed symmetry measurements. Several interesting results emerge from this analysis, including the high symmetry exhibited by the Erd\H{o}s-R\'enyi model. Additionally, we found that the proposed measurements present low correlation with other traditional metrics, such as node degree and betweenness centrality. Principal component analysis is used to combine all the results, revealing that the concepts presented here have substantial potential to also characterize networks at a global scale.

As the Internet and 3D modelling tools have led to an increasingly growth in the number of available 3D models, it becomes necessary to have a proper and smaller representation for searching purposes that captures the most important information about shapes. A large number of encoding methods have been proposed in the literature to create shape signatures from local descriptors. Two encoding methods have been receiving most attention from researchers given its informative characteristics: Fisher Vector [9] and Super Vector [36]. We propose to use these encoding methods combined with spectral signatures to represent 3D shapes. Although spectral signatures have many desirable properties to describe 3D shapes, for instance being invariant under rigid transformations and stable against non-rigid transformations, they do not perform so well in recent benchmarks. We propose improvements to the Wave Kernel Signature by analysing its behaviour when combined to different encoding methods for the purpose of shape retrieval and classification. At the end, we show a comparison of our method in two recent benchmarks.

We present an approach to modeling ear-to-ear, high-quality texture from one or more partial views of a face with possibly poor resolution and noise. Our approach is example-based in that we reconstruct texture with patches from a database composed of previously seen faces. A 3D morphable model is used to establish shape correspondence between the observed data across views and training faces. The database is built on the mesh surface by segmenting it into uniform overlapping patches. Texture patches are selected by belief propagation so as to be consistent with neighbors and with observations in an appropriate image formation model. We also develop a variant that is insensitive to light and camera parameters, and incorporate soft symmetry constraints. We obtain textures of higher quality for degraded views as small as 10 pixels wide, than a standard model fitted to non-degraded data. We further show applications to super-resolution where we substantially improve quality compared to a state-of-the-art algorithm, and to texture completion where we fill in missing regions and remove facial clutter in a photorealistic manner.

In this paper we present a method for constructing a generative prototype for a set of graphs by adopting a minimum description length approach. The method is posed in terms of learning a generative supergraph model from which the new samples can be obtained by an appropriate sampling mechanism. We commence by constructing a probability distribution for the occurrence of nodes and edges over the supergraph. We encode the complexity of the supergraph using an approximate Von Neumann entropy. A variant of the EM algorithm is developed to minimize the description length criterion in which the structure of the supergraph and the node correspondences between the sample graphs and the supergraph are treated as missing data. To generate new graphs, we assume that the nodes and edges of graphs arise under independent Bernoulli distributions and sample new graphs according to their node and edge occurrence probabilities. Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm and show the effectiveness of the generative model for the tasks of graph classification, graph clustering and generating new sample graphs.

In this paper, we propose a novel approach to seamless texture stitching on a 3D mesh. The main idea is to blend the sampled images by least-angle selection of gradients in overlapping patches. This is in contrast to previous works which focus on vertex- or face-based strategies with additional heuristics for robustness. Patches are obtained by growing a uniform mesh segmentation via geodesic projections. Blending is achieved by formulating a screened Poisson equation using discrete differential operators. The processing pipeline further includes an optional step of color transformation for calibration and correction. This is applied to a zippered mesh based on range scans and a morphable model fitted to face photographs.

Graph based methods have been successfully used in computer vision for classification and matching. This is due to the fact that shapes can be conveniently represented using graph structures. In this paper we explore the use of a spectral invariant which is based on the wave kernel trace to characterize graphs. The wave kernel is the solution of wave equation defined using the Edge-based Laplacian of a graph. The advantage of using the edge-based Laplacian over its vertex-based counterpart is that it can be used to translate equations from continuous analysis to the discrete graph theoretic domain, that have no meanings if defined using vertex-based Laplacian. To illustrate the utility of the proposed method we apply it to graphs extracted from both three-dimensional shapes and images.

Maximum common sub-graph isomorphism (MCS) is a famous NP-hard problem in graph processing. The problem has found application in many areas where the similarity of graphs is important, for example in scene matching, video indexing, chemical similarity and shape analysis. In this paper, a novel algorithm Qwalk is proposed for approximate MCS, utilizing the discrete-time quantum walk. Based on the new observation that isomorphic neighborhood group matches can be detected quickly and conveniently by the destructive interference of a quantum walk, the new algorithm locates an approximate solution via merging neighborhood groups. Experiments show that Qwalk has better accuracy, universality and robustness compared with the state-of-the-art approximate MCS methods. Meanwhile, Qwalk is a general algorithm to solve the MCS problem approximately while having modest time complexity.

Complex networks are finding increasing use in many scientific fields as a data representation. They are used to describe social networks, power grids, transportation networks, food webs and protein interactions in organisms, for example. A number of network models have been proposed to describe and explain the structure of these networks. In this paper we explore the problem of determining how well these models fit to the data, by using graph descriptors and signatures to define graph similarity and then using a model sampling approach to assess model similarity. We compare well known descriptors such as heat kernel based methods with some new signatures and propose a new method of constructing a global signature. We evaluate the performance of these descriptors on the problem of modelling protein-protein interaction networks.

This paper makes two contributions to the problem of correcting non-Euclidean dissimilarities. Data of this sort arrise when there are negative Eigen values of the dissimilarity matrix, and can therefore not be embedded into a real-valued Euclidean space. Our first contribution is to show how the non-Euclidean artifacts can be rectified. This is achieved by applying Ricci flow to the embedding of the manifold on which the data reside, and performing reprojection of the geodesic distances from tangent spaces centred on local patches of the manifold. Our second contribution is to show how the curvature of the local patches needed in the reprojection, can be estimated from the local point density on the patches. We experiment with the method on the well known Chicken pieces dataset [4].

Structural complexity measures and embedding have both been extensively and separately employed for the problems of graph clustering and classification. In this paper we aim to explore whether entropy component analysis can be used as a means of combining these two fundamental approaches. Specifically we develop a novel method that embeds undirected graphs into a feature space based on the graph entropy distribution. We commence from a recently derived expression for the von Neumann entropy of an undirected graph, which depends on vertex degree statistics. Based on this analysis we identify the local entropy contribution associated with each edge in a graph, and this is related to the reciprocal of the product of the degrees of the two vertices connected by the edge. This suggests a simple entropic characterization of graph structure, based on a two-dimensional histogram in which the bins are indexed by vertex degree and the bin-contents is the total entropy contribution associated with the edges that connect vertices of specific degree. This distribution of entropy with vertex degree can be encoded as a matrix, which captures the structure of the graph in terms of an entropic measure of complexity. The matrix can hence be viewed as a sample of entropy histograms from different graphs. Thus we can extract the entropy components from the sample, and use these to embed populations of graphs into a low dimensional space. We apply this method to the problem of graph classification, and compare the classification results of our new method with some alternative state of the art pattern recognition methods on bioinformatics data.

Many computer vision and pattern recognition problems may be posed as the analysis of a set of dissimilarities between objects. For many types of data, these dissimilarities are not euclidean (i.e., they do not represent the distances between points in a euclidean space), and therefore cannot be isometrically embedded in a euclidean space. Examples include shape-dissimilarities, graph distances and mesh geodesic distances. In this paper, we provide a means of embedding such non-euclidean data onto surfaces of constant curvature. We aim to embed the data on a space whose radius of curvature is determined by the dissimilarity data. The space can be either of positive curvature (spherical) or of negative curvature (hyperbolic). We give an efficient method for solving the spherical and hyperbolic embedding problems on symmetric dissimilarity data. Our approach gives the radius of curvature and a method for approximating the objects as points on a hyperspherical manifold without optimisation. For objects which do not reside exactly on the manifold, we develop a optimisation-based procedure for approximate embedding on a hyperspherical manifold. We use the exponential map between the manifold and its local tangent space to solve the optimisation problem locally in the euclidean tangent space. This process is efficient enough to allow us to embed data sets of several thousand objects. We apply our method to a variety of data including time warping functions, shape similarities, graph similarity and gesture similarity data. In each case the embedding maintains the local structure of the data while placing the points in a metric space.

The aim of this paper is to explore the use of backtrackless walks and prime cycles for characterizing both labeled and unlabeled graphs. The reason for using backtrackless walks and prime cycles is that they avoid tottering, and can increase the discriminative power of the resulting graph representation. However, the use of such methods is limited in practice because of their computational cost. In this paper, we present efficient methods for computing graph kernels, which are based on backtrackless walks in a labeled graph and whose worst case running time is the same as that of kernels based on random walks. For clustering unlabeled graphs, we construct feature vectors using Ihara coefficients, since these coefficients are related to the frequencies of prime cycles in the graph. To efficiently compute the low order coefficients, we present an O(|V|(3)) algorithm which is better than the O(|V|(6)) worst case running time of previously known algorithms. In the experimental evaluation, we apply the proposed method to clustering both labeled and unlabeled graphs. The results show that using backtrackless walks and prime cycles instead of random walks can increase the accuracy of recognition.

The grapheme codebook is a high-performing technique for offline writer identification. This paper considers whether the de facto standards for initial grapheme extraction are optimal for both modern and historical datasets. We examine the construction and representation of the graphemes that comprise the codebook, testing three segmentation methods and two grapheme size normalisation methods on two datasets: a 93-writer IAM dataset, and a 43-writer medieval English dataset. The standard minima-split segmentation is compared to a complementary segmentation method that preserves ligature shapes, as well as the union of both these methods. Classification performance for each method is compared on a range of codebook sizes. We demonstrate that grapheme aspect-ratio is not always a writer-specific feature, and that preserving the character body shape in segmentation is more informative than preserving cursive text ligatures.

The novel contributions of this paper are twofold. First, we demonstrate how to characterize unweighted graphs in a permutation-invariant manner using the polynomial coefficients from the Ihara zeta function, i.e., the Ihara coefficients. Second, we generalize the definition of the Ihara coefficients to edge-weighted graphs. For an unweighted graph, the Ihara zeta function is the reciprocal of a quasi characteristic polynomial of the adjacency matrix of the associated oriented line graph. Since the Ihara zeta function has poles that give rise to infinities, the most convenient numerically stable representation is to work with the coefficients of the quasi characteristic polynomial. Moreover, the polynomial coefficients are invariant to vertex order permutations and also convey information concerning the cycle structure of the graph. To generalize the representation to edge-weighted graphs, we make use of the reduced Bartholdi zeta function. We prove that the computation of the Ihara coefficients for unweighted graphs is a special case of our proposed method for unit edge weights. We also present a spectral analysis of the Ihara coefficients and indicate their advantages over other graph spectral methods. We apply the proposed graph characterization method to capturing graph-class structure and clustering graphs. Experimental results reveal that the Ihara coefficients are more effective than methods based on Laplacian spectra.

Many computer vision and pattern recognition problems may be posed by defining a way of measuring dissimilarities between patterns. For many types of data, these dissimilarities are not Euclidean, and may not be metric. In this paper, we provide a means of embedding such data. We aim to embed the data on a hypersphere whose radius of curvature is determined by the dissimilarity data. The hypersphere can be either of positive curvature (elliptic) or of negative curvature (hyperbolic). We give an efficient method for solving the elliptic and hyperbolic embedding problems on symmetric dissimilarity data. This method gives the radius of curvature and a method for approximating the objects as points on a hyperspherical manifold. We apply our method to a variety of data including shape-similarities, graph-similarity and gesture-similarity data. In each case the embedding maintains the local structure of the data while placing the points in a metric space.

In this paper we present work on automated scribe identification on a new Middle-English manuscript dataset from around the 14th - 15th century. We discuss the image and textual problems encountered in processing historical documents, and demonstrate the effect of accounting for manuscript style on the writer identification rate. The grapheme codebook method is used to achieve a Top-1 classification accuracy of up to 77% with a modification to the distance measure. The performance of the Sparse Multinomial Logistic Regression classifier is compared against five k-nn classifiers. We also consider classification against the principal components and propose a method for visualising the principal component vectors in terms of the original grapheme features.

This paper describes a method for constructing a generative model for sets of graphs. The method is posed in terms of learning a supergraph from which the samples can be obtained by edit operations. We construct a probability distribution for the occurrence of nodes and edges over the supergraph. We use the EM algorithm to learn both the structure of the supergraph and the correspondences between the nodes of the sample graphs and those of the supergraph, which are treated as missing data. In the experimental evaluation of the method, we a) prove that our supergraph learning method can lead to an optimal or suboptimal supergraph, and b) show that our proposed generative model gives good graph classification results.

Similarity based pattern recognition is concerned with the analysis of patterns that are specified in terms of object dissimilarity or proximity rather than ordinal values. For many types of data and measures, these dissimilarities are not Euclidean. This hinders the use of many machine-learning techniques. In this paper, we provide a means of correcting or rectifying the similarities so that the non-Euclidean artifacts are minimized. We consider the data to be embedded as points on a curved manifold and then evolve the manifold so as to increase its flatness. Our work uses the idea of Ricci flow on the constant curvature Riemannian manifold to modify the Gaussian curvatures on the edges of a graph representing the non-Euclidean data. We demonstrate the utility of our method on the standard ``Chicken pieces'' dataset and show that we can transform the non-Euclidean distances into Euclidean space.

We develop a novel method for extracting graph characteristics from edge-weighted graphs, based on an extension of the Ihara zeta function from unweighted to edge-weighted graphs. This is effected by generalizing the determinant form of the Ihara zeta function. We use the set of the reciprocal polynomial coefficients of the resulting Ihara zeta function, i.e. the Ihara coefficients, to construct our characterization. We also present a spectral analysis of the edge-weighted graph Ihara coefficients and indicate their advantages over graph spectral methods. Experimental results reveal that the Ihara coefficients are effective for the purpose of clustering edge-weighted graphs.

MOTIVATION: Throughout evolution, homologous proteins have common regions that stay semi-rigid relative to each other and other parts that vary in a more noticeable way. In order to compare the increasing number of structures in the PDB, flexible geometrical alignments are needed, that are reliable and easy to use. RESULTS: We present a protein structure alignment method whose main feature is the ability to consider different rigid transformations at different sites, allowing for deformations beyond a global rigid transformation. The performance of the method is comparable with that of the best ones from 10 aligners tested, regarding both the quality of the alignments with respect to hand curated ones, and the classification ability. An analysis of some structure pairs from the literature that need to be matched in a flexible fashion are shown. The use of a series of local transformations can be exported to other classifiers, and a future golden protein similarity measure could benefit from it. AVAILABILITY: A public server for the program is available at http://dmi.uib.es/ProtDeform/. SUPPLEMENTARY INFORMATION: All data used, results and examples are available at http://dmi.uib.es/people/jairo/bio/ProtDeform.

Segmenting the speech signals on the basis of time-frequency analysis is the most natural approach. Boundaries are located in places where energy of some frequency subband rapidly changes. Speech segmentation method which bases on discrete wavelet transform, the resulting power spectrum and its derivatives is presented. This information allows to locate the boundaries of phonemes. A statistical classification method was used to check which features are useful. The efficiency of segmentation was verified on a male speaker taken from a corpus of Polish language.

In this paper, we explore experimentally the use of the commute time of the continuous-time quantum walk for graph drawing. For the classical random walk, the commute time has been shown to be robust to errors in edge weight structure and to lead to spectral clustering algorithms with improved performance. We analyse the quantum commute times with reference to their classical counterpart. Specifically, we explore the graph embeddings that preserve commute-time.

In this paper we present a method of combining stereo and shape-from-shading information, taking account of the local reliability of each shape estimate. Local estimates of disparity and orientation are modelled using Gaussian distributions. A Gaussian-Markov random field is used to represent the disparity-map, taking into account interactions between disparity measurements and surface orientation, and the MAP estimate found using belief propagation. Local estimates of the precision of disparities and surface normals are found and used to control the process so that the most accurate data source is used in each region. We assess the performance of our approach using both synthetic and real stereo pairs, and compare against ground truth.

This paper shows how to construct pattern vectors from the Ihara zeta function for the purposes of characterizing graph structures. To avoid the risk of sampling the meaningless infinities at the poles of the Ihara zeta function, we take use of the coefficients of the polynomial of the reciprocal zeta function. The proposed pattern vector is proved to be permutation invariant to the node order of the associated graph. Its components can be computed from a characteristic polynomial derived from the original graph. We apply the proposed scheme to graph clustering.

Generative models are well known in the domain of statistical pattern recognition. Typically, they describe the probability distribution of patterns in a vector space. In contrast, very little work has been done with generative models of graphs because graphs do not have a straight-forward vectorial representation. In this paper we examine the problem of creating generative distributions over sets of graphs. We model the variation in a set of graphs by observing which subgraphs are present in each graph and how these subgraphs are connected. By performing clustering on the subgraphs we can group those with similar structure. Distributions are then defined on the clusters present in each graph, which subgraphs are present in each cluster and the way subgraphs are connected. New graphs can then be generated by sampling from the distributions. We show the utility of our approach on synthetically generated point sets and point sets derived from real-world imagery of articulated objects.

Graph structures have been proved important in high level-vision since they can be used to represent structural and relational arrangements of objects in a scene. One of the problems that arises in the analysis of structural abstractions of object is graph clustering. In this paper, we explore how permutation invariants computed from the trace of the heat kernel can be used to characterize graphs for the purposes of measuring similarity and clustering. We explore three different approaches to characterize the heat kernel trace as a function of time. These are the heat kernel trace moments, heat content invariants and symmetric polynomials with Laplacian eigenvalues as inputs. Experiments on the COIL 100 and Caltech 256 databases reveal that the proposed invariants are effective and outperform the tradition methods.

Binocular stereo has been extensively studied for extracting the shape of a scene. The challenge is in matching features between two images of a scene; this is the correspondence problem. Shape from shading (SfS) is another method of extracting shape. This models the interaction of light with the scene surface(s) for a single image. These two methods are very different; stereo uses surface features to deliver a depth-map, SfS uses shading, albedo and lighting information to infer the differential of the depth-map. In this paper we develop a framework for the integration of both depth and orientation information. Dedicated algorithms are used for initial estimates. A Gaussian-Markov random field then represents the depth-map, Gaussian belief propagation is used to approximate the MAP estimate of the depth-map. Integrating information from both stereo correspondences and surface normals allows fine surface details to be estimated.

The heat-kernel of a graph is computed by exponentiating the Laplacian eigen-system with time. In this paper, we study the heat kernel mapping of the nodes of a graph into a vector-space. Specifically, we investigate whether the resulting point distribution can be used for the purposes of graphclustering. Our characterisation is based on the covariance matrix of the point distribution. We explore the relationship between the covariance matrix and the heat kernel, and demonstrate the eigenvalues of the covariance matrix are found be exponentiating the Laplacian eigenvalues with time. We apply the technique to images from the COIL database, and demonstrate that it leads to well defined graph clusters.

The spectrum of a graph has been widely used in graph theory to characterise the properties of a graph and extract information from its structure. It has been less popular as a representation for pattern matching for two reasons. Firstly, more than one graph may share the same spectrum. It is well known, for example, that very few trees can be uniquely specified by their spectrum. Secondly, the spectrum may change dramatically with a small change structure. In this paper we investigate the extent to which these factors affect graph spectra in practice, and whether they can be mitigated by choosing a particular matrix representation of the graph. There are a wide variety of graph matrix representations from which the spectrum can be extracted. In this paper we analyse the adjacency matrix, combinatorial Laplacian, normalised Laplacian and unsigned Laplacian. We also study the use of the spectrum derived from the heat kernel matrix and path length distribution matrix. We investigate the cospectrality of these matrices over large graph sets and show that the Euclidean distance between spectra tracks the edit distance over a wide range of edit costs, and we analyse the stability of this relationship. We then use the spectra to match and classify the graphs and demonstrate the effect of the graph matrix formulation on error rates.

Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs.

Although graph structures have proved useful in high level vision for object recognition and matching, they can prove computationally cumbersome because of the need to establish reliable correspondences between nodes. Hence, standard pattern recognition techniques can not be easily applied to graphs since feature vectors and not easily contructed. To overcome this problem, in this paper we turn to the spectral matrix. We show how the elements of this matrix can be used to construct symmetric polynomials that are permutation invariants. The co-efficients of these polynomials can be used as graph-features which can be encoded in a vectorial manner. We demonstrate that these vectors can be embedded in a low dimensional space using locally linear embedding, and that the embedding results in well defined graph clusters.

The paper investigates the use of graph-spectral methods for learning the modes of structural variation in sets of graphs. Our approach is as follows. First, we vectorise the adjacency matrices of the graphs. Using a graph-matching method, we establish correspondences between the components of the vectors. Using the correspondences, we cluster the graphs using a Gaussian mixture model. For each cluster we compute the mean and covariance matrix for the vectorised adjacency matrices. We allow the graphs to undergo structural deformation by linearly perturbing the mean adjacency matrix in the direction of the modes of the covariance matrix. We demonstrate the method on sets of corner Delaunay graphs for 3D objects viewed from varying directions.

This paper investigates the use of graph-spectral methods for learning the modes of structural variation in sets of graphs. Our approach is as follows. First, we vectorise the adjacency matrices of the graphs. Using a graph-matching method we establish correspondences between the components of the vectors. Using the correspondences we cluster the graphs using a Gaussian mixture model. For each cluster we compute the mean and covariance matrix for the vectorised adjacency matrices. We allow the graphs to undergo structural deformation by linearly perturbing the mean adjacency matrix in the direction of the modes of the covariance matrix.

This paper develops a maximum a posteriori (MAP) probability estimation framework for shape-from-shading (SFS) from synthetic aperture radar (SAR) images. The aim is to use this method to reconstruct surface topography from a single radar image of relatively complex terrain. Our MAP framework makes explicit how the recovery of local surface orientation depends on the whereabouts of terrain edge features and the available radar reflectance information. To apply the resulting process to real world radar data, we require probabilistic models for the appearance of terrain features and the relationship between the orientation of surface normals and the radar reflectance. We show that the SAR data can be modeled using a Rayleigh-Bessel distribution and use this distribution to develop a maximum likelihood algorithm for detecting and labeling terrain edge features. Moreover, we show how robust statistics can be used to estimate the characteristic parameters of this distribution. We also develop an empirical model for the SAR reflectance function. Using the reflectance model, we perform Lambertian correction so that a conventional SFS algorithm can be applied to the radar data. The initial surface normal direction is constrained to point in the direction of the nearest ridge or ravine feature. Each surface normal must fall within a conical envelope whose axis is in the direction of the radar illuminant. The extent of the envelope depends on the corrected radar reflectance and the variance of the radar signal statistics. We explore various ways of smoothing the field of surface normals using robust statistics. Finally, we show how to reconstruct the terrain surface from the smoothed field of surface normal vectors. The proposed algorithm is applied to various SAR data sets containing relatively complex terrain structure.

Population coding is a coding scheme which is ubiquitous in neural systems, and is also of more general use in coding stimuli, for example in vision problems. A population of responses to a stimulus can be used to represent not only the value of some variable in the environment, but a full probability distribution for that variable. The information is held in a distributed and encoded form, which may in some situations be more robust to noise and failures than conventional representations. Gabor filters are a popular choice for detecting edges in the visual field for several reasons. They are easily tuned for a variety of edge widths and orientations, and are considered a close model of the edge filters in the human visual system. In this paper, we consider population codes of Gabor filters with different orientations. A probabilistic model of Gabor filter responses is presented. Based on the analytically derived orientation tuning function and a parametric mixture model of the filter responses in the presence of local edge structure with single or multiple orientations a probability density function (pdf) of the local orientation in any point (x, y) can be extracted through a parameter estimation procedure. The resulting pdf of the local contour orientation captures not only angular information at edges, corners or T-junctions but also describes the certainty of the measurement which can be characterized in terms of the entropy of the individual mixture components.

In this paper, we analyze the recurrent correlation associative memory (RCAM) model of Chiueh and Goodman (1990, 1991). This is an associative memory in which stored binary memory patterns are recalled via an iterative update rule. The update of the individual pattern-bits is controlled by an excitation function, which takes as its argument the inner product between the stored memory patterns and the input patterns. Our contribution is to analyze the dynamics of pattern recall when the input patterns are corrupted by noise of a relatively unrestricted class. We show how to identify the excitation function which maximizes the separation (the Fisher discriminant) between the uncorrupted realization of the noisy input pattern and the remaining patterns residing in the memory. The excitation function which gives maximum separation is exponential when the input bit-errors follow a binomial distribution. We develop an expression for the expectation value of bit-error probability on the input pattern after one iteration. We show how to identify the excitation function which minimizes the bit-error probability. The relationship between the excitation functions which result from the two different approaches is examined for a binomial distribution of bit-errors. We develop a semiempirical approach to the modeling of the dynamics of the RCAM.

We present a probabilistic population coding model of Gabor filter responses. Based on the analytically derived orientation tuning function and a mixture model of the filter responses in the presence of local edge structures with single or multiple orientations, a probability density function of the local orientation at a given point can be extracted through a parameter estimation procedure. This density captures not only angular information at edges, corners or T-junctions but also describes the certainty of the measurement, which can be characterized in terms of the entropy of the individual mixture components. The method is general as it applies the same algorithm and filter bank for different types of intensity features.

We investigate whether vectors of graph spectral features can be used for the purposes of graph clustering. We commence from the eigenvalues and eigenvectors of the adjacency matrix. Each of the leading eigenmodes represents a cluster of nodes and is mapped to a component of a feature vector. The spectral features used as components of the vectors are the eigenvalues and the shared perimeter length. We explore whether these vectors can be used for the purposes of graph clustering. Here we investigate the use of both central and pairwise clustering methods. On a database of view-graphs, both of the features provide good clusters while the eigenvectors perform better.

The paper describes a probabilistic framework for graph clustering. We commence from a set of pairwise distances between graph structures. From this set of distances, we use a mixture model to characterize the pairwise affinity of the different graphs. We present an EM-like algorithm for clustering the graphs by iteratively updating the elements of the affinity matrix. In the M-step we apply eigendcomposition to the affinity matrix to locate the principal clusters. In the M-step we update the affinity probabilities. We apply the resulting unsupervised clustering algorithm to two practical problems. The first of these involves locating shape-categories using shock trees extracted from 2D silhouettes. The second problem involves finding the view structure of a polyhedral object using the Delaunay triangulation of corner features.

This paper investigates whether meaningful shape categories can be identified in an unsupervised way by clustering shock-trees. We commence by computing weighted and unweighted edit distances between shock-trees extracted from the Hamilton-Jacobi skeleton of 2D binary shapes. Next we use an EM-like algorithm to locate pairwise clusters in the pattern of edit-distances. We show that when the tree edit distance is weighted using the geometry of the skeleton, then the clustering method returns meaningful shape categories.

This paper introduces a Bayesian approach to shape-from-shading ($F$) which is applied to terrain recovery in Synthetic Aperture Radar ($AR) images. The Bayesian model relates the recovery of 3-D shape information to the original 2-D radar intensity and to edges separating different topographic regions. First, we model the image amplitude distribution and the reflection function in $AR images. Using a maximum log-likelihood feature detector derived from the image statistics we identify the ridges and ravines in the terrain image. These topographic features are used to constrain the recovery of suace normals in the shapefrom -shading process. Finally, the suace normals are smoothed using rvbust statistics operators.

We propose a new statistical model for SAR images. According to this model, the SAR image amplitude follows a product of Rayleigh and Bessel functions. We derive the maximum likelihood feature detector for extracting terrain features from synthetic aperture radar (SAR) images. The terrain features are classified as ridges and ravines according to their statistical properties and surrounding neighborhood. These salient features are used as constraints for estimating the SAR terrain surface.

We introduce a new approach for recovering shape-from-shading (SFS) from synthetic aperture radar (SAR) images of the terrain. Three contributions are proposed: 1) we show how the direction of surface normals is constrained by the geometry of the radar reflectivity cone; 2) we show how topographic features can be used as boundary constraints on the recovered surface normals; and 3) the resulting field of surface normals is smoothed using robust statistics.

Population coding has become an essential paradigm in cognitive neuroscience over the past decade and is increasingly studied within the neural network community. We investigate the use of population vector decoding for local edge orientation estimation from a discrete set of Gabor filters. Vectorial combination of the broadly tuned filter outputs yields a resultant population vector, which gives a precise and robust estimate of the local contour orientation. We present results on the accuracy and robustness of orientation measurement.

We analyze the pattern storage capacity of the exponential correlation associative memory (ECAM). We model the performance of the ECAM when presented with corrupted input patterns. Our model leads to an expression for the storage capacity of the ECAM both in terms of the length of the bit-patterns and the probability of bit-corruption in the original input patterns. These storage capacities agree closely with simulation. In addition, our results show that slightly superior performance can be obtained by selecting an optimal value of the exponential constant.

Addresses the problem of how to identify the optimal excitation function for the recurrent correlation associative memory. We present a model of pattern recovery which allows us to measure probability of bit-error. By minimising this measure we are able to numerically locate the excitation function which results in the minimum error of pattern recall. Additionally, we show that minimising a simpler measure of pattern overlap leads to an analytical expression for the excitation function which is exponential. We compare the performance of the numerical and exponential functions. This reveals that the more easily controlled exponential is only slightly poorer in its performance.

Population coding is a coding scheme used in a neural systems and is of general importance. It is ubiquitous in neurological systems. For this reason there is great interest in exploiting population coding in pattern recognition algorithms. A population of neural activities represents not only the value of some variable in the environment, but a full probability distribution for that variable. The information is held in a distributed and encoded form which may in some situations be more robust to noise and failures than conventional representations. Encoding a population code with discrete-valued elements creates inaccuracies in the coded distributions. The result of these errors is the introduction of spurious high-frequency noise in the final distribution. We develop two methods of eliminating these errors and present results comparing the reconstruction accuracy of these techniques.

This paper describes a novel framework for comparing and matching corrupted relational graphs. The paper develops the idea of edit-distance originally introduced for graph-matching by Sanfeliu and Fu (1983). We show how the Levenshtein distance (1966) can be used to model the probability distribution for structural errors in the graph-matching problem. This probability distribution is used to locate matches using MAP label updates. We compare the resulting graph-matching algorithm with that recently reported by Wilson and Hancock. The use of edit-distance offers an elegant alternative to the exhaustive compilation of label dictionaries. Moreover, the method is polynomial rather than exponential in its worst-case complexity. We support our approach with an experimental study on synthetic data and illustrate its effectiveness on an uncalibrated stereo correspondence problem. This demonstrates experimentally that the gain in efficiency is not at the expense of quality of match.

This paper describes work aimed at developing a practical shape-from-shading process for terrain analysis from radar imagery. The paper commences by providing an analysis of the radar reflectance properties of terrain structures. By using ground truth elevation data, we provide an empirical study of the radar reflectance characteristics for large-scale terrain features. The main conclusion of this study are twofold. Firstly, we show that radar has a strong backscatter component. Secondly, we show that the radar noise has a tail which extends to large reflectance values. Based on these observations we develop a semi-empirical shape-from-shading algorithm. We illustrate the effectiveness of the algorithm in extracting surface orientation information from radar images of a mountainous area of terrain in North Wales. 1

This paper describes physically based model for detecting closed edge-contours. According to our model, the magnitude of the Canny edge-gradient represents a raw charge-density. Edge segmentation is realised by considering the damped-motion of charged test-particles in the resulting electric field. The attractor regions of the electric field represent continuous regions that are separated by closed edge-contours. In order to strike a compromise between over and under smoothing the resulting edge-map, we provide a hierarchical algorithm for controlling the dynamics of the region attractors. We illustrate the method on both synthetic and real world data.

This paper describes a novel framework for comparing and matching corrupted relational graphs. The paper develops the idea of edit distance originally used for graph-matching by Sanfeliu and Fu (1983). We show how the normalised edit distance of Marzal and Vidal (1993) can be used to model the probability distribution for structural errors in the graph-matching problem. This probability distribution is used to locate matches using MAP label updates. We compare the resulting graph-matching algorithm with that reported by Wilson and Hancock (1997).

Describes an algorithm for registering retinal angiograms. The idea is to exploit the network structure of the blood vessel patterns to improve the recovery of the affine registration parameters. The framework for our study is provided by the generalised EM algorithm. There are two novel features of the algorithm. Firstly, in the expectation step of the algorithm we update the probabilities of correspondence matching using contextual constraints provided by the network structure of the blood-vessel pattern in the angiograms. The second novel idea is to recover affine transformation parameters by applying the Gustafson fuzzy clustering procedure to the expected log-likelihood function.

Describes a new class of adaptive mesh surface for terrain analysis. The novelty of the contribution resides in the control of the mesh. We use a variance-bias criterion to select the optimal areas for the triangular facets of the mesh. In this way the mesh adapts itself to offer the best tradeoff between increasing the facet area to minimise the noise variance and decreasing the facet area to minimise the bias of the fitted facet parameters. We provide a illustration of the effectiveness of the new mesh control methodology for the case where the faces of the mesh represent planar patches. The piecewise planar mesh is shown to be effective in the modelling of an area of complex terrain structure in Southern England.

The contributions of this article are twofold. First, we develop a new nonquadratic energy function for graph matching. The starting point is a recently reported mixture model that gauges relational consistency using a series of exponential functions of the Hamming distances between graph neighborhoods. We compute the effective neighborhood potentials associated with the mixture model by identifying the single probability function of zero Kullback divergence. This new energy function is simply a weighted sum of graph Hamming distances. The second contribution is to locate matches by graduated assignment. Rather than solving the mean-field saddle-point equations, which are intractable for our nonquadratic energy function, we apply the soft-assign ansatz to the derivatives of our energy function. Here we introduce a novel departure from the standard graduated assignment formulation of graph matching by allowing the connection strengths of the data graph to update themselves. The aim is to provide a means by which the structure of the data graph can be updated so as to rectify structural errors. The method is evaluated experimentally and is shown to outperform its quadratic counterpart.

The main contribution of the paper is to describe a new class of the adaptive mesh. The mesh uses both split and merge operations to adapt itself to the structure of volumetric data-points. The adaptive behaviour is controlled by the variance of the data-point positions about maximum-likelihood quadric patches. The authors show that the density of control points on the mesh is regulated by the curvature of the underlying surface. Finally, they illustrate the effectiveness of the method on both real-world and simulated data-sets.

This paper describes a Bayesian framework for performing relational graph matching by discrete relaxation. Our basic aim is to draw on this framework to provide a comparative evaluation of a number of contrasting approaches to relational matching. Broadly speaking there are two main aspects to this study. Firstly we focus on the issue of how relational inexactness may be quantified. We illustrate that several popular relational distance measures can be recovered as specific limiting cases of the Bayesian consistency measure. The second aspect of our comparison concerns the way in which structural inexactness is controlled. We investigate three different realizations of the matching process which draw on contrasting control models. The main conclusion of our study is that the active process of graph-editing outperforms the alternatives in terms of its ability to effectively control a large population of contaminating clutter.

The aim of this paper is to provide a comparative evaluation of a number of contrasting approaches to relational matching. Unique to this study is the way in which we show how a diverse family of algorithms relate to one-another using a common Bayesian framework. Broadly speaking there are two main aspects to this study. Firstly we focus on the issue of how relational inexactness may be quantified. We illustrate that several popular relational distance measures can be recovered as specific limiting cases of the same Bayesian consistency measure. The second aspect of our comparison concerns the way in which structural inexactness is controlled. We investigate three different realisations of the matching process which draw on contrasting control models. The main conclusion of our study is that the active process of graph-editing outperforms the alternatives in terms of its ability to effectively control a large population of contaminating clutter.

This paper describes a new framework for constructing mean-field energy functions for use in relational matching. The starting point is the Bayesian relational consistency model of Wilson and Hancock (1995). Hitherto, the optimisation of the consistency measure has been effected by the deterministic hill climbing process known as discrete relaxation which is prone to local convergence if local maxima are present. By applying ideas from statistical physics to the configurational matching probabilities we determine the effective potentials of an equivalent Boltzmann distribution. Formally, these potentials are weighted sums of the Hamming distances between matched neighbourhoods in the data graph and their counterparts in the model graph. Adopting a simple softening ansatz we derive mean-field equations for minimising the global graph matching potential. This provides an efficient means of locating the global optima of the Bayesian consistency measure.

The aim of this paper is to explore the sensitivity of relational matching to attribute and structural information. Broadly speaking there are two main aspects to this study. First, we determine the relative importance of attribute and structural information in matching noise corrupted graphs. The second aspect of our analysis concerns the nature of the relational structures used in matching. Here we compare the matching results obtained using four different graph structures, namely the Delaunay graph, the N-nearest neighbour graph, the Gabriel graph and the relative neighbourhood graph. Our results are presented as noise sensitivity curves. The main conclusion of the study is that attributes are essential when the fractional corruption exceeds 20% and that the Delaunay graph has optimal noise robustness.

The paper describes a novel approach to relational matching problems in machine vision. Rather than matching static scene descriptions, the approach adopts an active representation of the data to be matched. This representation is iteratively reconfigured to increase its degree of topological congruency with the model relational structure in a reconstructive matching process. The active reconfiguration of relational structures is controlled by a MAP update process. The final restored graph representation is optimal in the sense that it has maximum a posteriori probability with respect to the available attributes for the objects under match. The benefits of the technique are demonstrated experimentally on the matching of cluttered synthetic aperture radar data to a model in the form of a digital map. The operational limits of the method are established in a simulation study. >

This paper describes a symbolic approach to relational matching. The novelty of the method lies in its Bayesian modelling of relational consistency which leads to a global matching criterion with a unique mathematical structure and robustness to error. Unlike many alternatives in the literature, the method is not limited to the use of binary constraints; it can accommodate N-ary relations of varying order. In consequence of this assumed model, the consistency of match is gauged by a compound exponential function of a higherorder Hamming distance between symbolic relations; there is a single exponential associated with each potential relational mapping. These exponential functions naturally soften the symbolic constraints represented by the relational mappings, This compound exponential structure also bestows a number of tangible benefits over the use of quadratic alternatives. In the first instance, it both renders the method more robust to errors and allows it to operate effectively in a large space of relational mappings. Moreover, this robustness to inconsistency means that the method may be operated without the need for an explicit null matching process. Unmatchable entities are identified by a constraint filtering operation once the relaxation scheme has converged. The utility of the method is illustrated on the matching of hedge structures in SAR images against their cartographic representation in a digital map

Our aim in this paper is to develop the formal basis for hierarchical probabilistic relaxation. The adopted approach is an evidence combining one and relies on the specification of the relaxation process in terms of Bayesian probability distributions. The approach is novel and represents a considerable advance in extending the functionality of relaxation processes. In particular, since many tasks in computer vision are formulated in terms of hierarchies of increasingly abstract image representations, the technique holds out the promise of providing a framework in which constraints from different levels can be brought to bear objectively on the interpretation task.

This paper describes a symbolic approach to relational matching. The novelty of the method lies in its Bayesian modelling of relational consistency through the use of an explicit constraint corruption process. In consequence of this assumed model the consistency of match is gauged by a compound exponential function of a higher-order Hamming distance between symbolic relations, providing a natural mechanism for constraint softening. Unlike many alternatives in the literature, the method is not limited to the use of binary constraints; it can accommodate N-ary relations of varying order.