Using spanning graphs for efficient image registration.

We provide a detailed analysis of the use of minimal spanning graphs as an alignment method for registering multimodal images. This yields an efficient graph theoretic algorithm that, for the first time, jointly estimates both an alignment measure and a viable descent direction with respect to a parameterized class of spatial transformations. We also show how prior information about the interimage modality relationship from prealigned image pairs can be incorporated into the graph-based algorithm. A comparison of the graph theoretic alignment measure is provided with more traditional measures based on plug-in entropy estimators. This highlights previously unrecognized similarities between these two registration methods. Our analysis gives additional insight into the tradeoffs the graph-based algorithm is making and how these will manifest themselves in the registration algorithm's performance.     

Geodesic entropic graphs for dimension and entropy estimation in manifold learning

In the manifold learning problem, one seeks to discover a smooth low dimensional surface, i.e., a manifold embedded in a higher dimensional linear vector space, based on a set of measured sample points on the surface. In this paper, we consider the closely related problem of estimating the manifold's intrinsic dimension and the intrinsic entropy of the sample points. Specifically, we view the sample points as realizations of an unknown multivariate density supported on an unknown smooth manifold. We introduce a novel geometric approach based on entropic graph methods. Although the theory presented applies to this general class of graphs, we focus on the geodesic-minimal-spanning-tree (GMST) to obtaining asymptotically consistent estimates of the manifold dimension and the Re/spl acute/nyi /spl alpha/-entropy of the sample density on the manifold. The GMST approach is striking in its simplicity and does not require reconstruction of the manifold or estimation of the multivariate density of the samples. The GMST method simply constructs a minimal spanning tree (MST) sequence using a geodesic edge matrix and uses the overall lengths of the MSTs to simultaneously estimate manifold dimension and entropy. We illustrate the GMST approach on standard synthetic manifolds as well as on real data sets consisting of images of faces.     

Applications of numbered undirected graphs

Numbered undirected graphs are becoming an increasingly useful family of mathematical models for a broad range of applications. They have found usage in various coding theory problems, including the design of good radar-type codes, synch-set codes and convolutional codes with optimal autocorrelation properties. They facilitate the optimal nonstandard encodings of integers. They have also been applied to determining ambiguities in X-ray crystallographic analysis, to design of a communication network addressing system, to determination of optimal circuit layouts, and to problems in additive number theory. An attempt has been made to systematically present all of these diverse applications in a unifying framework and to indicate the existence of additional applications and to suggest directions for additional research.     

Generalized entropic uncertainty principle on fractional Fourier transform

The entropic uncertainty principle is an element in information theory and plays an important role in signal processing. Based on the relations between the original function and the definition of the fractional Fourier transform (FRFT), two novel entropic uncertainty principles in FRFT domains, in which one is Shannon entropy uncertainty principle and the other is Rényi entropy uncertainty principle, are derived, which are associated with the FRFT parameters. In addition, the extended Rényi entropy uncertainty principle for multiple functions and discrete entropy uncertainty principle are explored as well. These inequalities disclose the relations between the bounds and the transform parameters and sampling periods.     

A class of robust entropic functionals for image restoration

This paper considers the concept of robust estimation in regularized image restoration. Robust functionals are employed for the representation of both the noise and the signal statistics. Such functionals allow the efficient suppression of a wide variety of noise processes and permit the reconstruction of sharper edges than their quadratic counterparts. A new class of robust entropic functionals is introduced, which operates only on the high-frequency content of the signal and reflects sharp deviations in the signal distribution. This class of functionals can also incorporate prior structural information regarding the original image, in a way similar to the maximum information principle. The convergence properties of robust iterative algorithms are studied for continuously and noncontinuously differentiable functionals. The definition of the robust approach is completed by introducing a method for the optimal selection of the regularization parameter. This method utilizes the structure of robust estimators that lack analytic specification. The properties of robust algorithms are demonstrated through restoration examples in different noise environments.     

Generating function for spanning trees

A generating function that facilitates the counting and listing of the spanning trees in many classes of graphs is presented, with examples of its application.     

Marked graphs and hamiltonian graphs

In this paper we present an algorithm using a sign incidence matrix to enumerate all the subsets of places of a marked graph which are both siphon and trap, whose input transitions equal the output transitions and where both of them equal the set of all transitions. An iterative procedure to find a set of places in a marked graph whose removal ensures the resulting marked graph does not have a subset of places which are both siphon and trap, is given. This iterative procedure employs a siphon-trap matrix. As an application, using the algorithm given earlier, we have obtained all Hamiltonian circuits of a given directed graph. We have also found the minimal feedback edge set of a given directed graph. A characterization for Hamiltonian graphs is obtained in terms of siphons and traps.     

Marked graphs and Euler graphs

In this paper an algorithm to find all the subsets of places of a marked graph which are both siphon and trap using sign incidence matrix is proposed. We introduce a new matrix called the siphon-trap matrix for marked graphs. An interesting relation between sign incidence matrix and siphon-trap matrix is established. It is proved that the token count remains the same under any firing for the set of places which are both siphon and trap. As an application an elegant characterization for Euler graphs is obtained.     

Efficient algorithm for common spanning tree problem

Enumerating the spanning trees common to a pair of graphs is a problem which arises in symbolic circuit analysis. The algorithm presented here is between 350% and 26000% faster than the best algorithm previously published, and hence the computer analysis of circuits of a reasonable size is now feasible.     

Prism-based pulse shaper for octave spanning spectra

We demonstrate a prism-based pulse shaping setup that enables the shaping of ultrashort pulses with octave-spanning spectra. In contrast to gratings prisms allow for a high throughput and large bandwidths. The second-order dispersion of the prism material is precompensated by a fused silica prism sequence while higher dispersion orders are compensated by the pulse shaper. This flexible tool for dispersion compensation enables us to generate the shortest pulses ever achieved directly from an oscillator. The resulting pulse is almost transform-limited and shows a clean temporal profile with very low background. We assess the performance and limitations of the setup both experimentally and by theoretical analysis.     

RRED indices: reduced reference entropic differencing for image quality assessment

We study the problem of automatic "reduced-reference" image quality assessment (QA) algorithms from the point of view of image information change. Such changes are measured between the reference- and natural-image approximations of the distorted image. Algorithms that measure differences between the entropies of wavelet coefficients of reference and distorted images, as perceived by humans, are designed. The algorithms differ in the data on which the entropy difference is calculated and on the amount of information from the reference that is required for quality computation, ranging from almost full information to almost no information from the reference. A special case of these is algorithms that require just a single number from the reference for QA. The algorithms are shown to correlate very well with subjective quality scores, as demonstrated on the Laboratory for Image and Video Engineering Image Quality Assessment Database and the Tampere Image Database. Performance degradation, as the amount of information is reduced, is also studied.     

Improved algorithm for the construction of minimal spanning trees

An improved algorithm for the construction of minimal spanning trees is proposed which is particularly suitable for use with data sets containing repeated elements. The algorithm may be applied to cluster-detection and pattern-segmentation problems, such as arise in automatic speech recognition.     

Improved implementation of search technique to find spanning trees

The authors have developed a set of algorithms to find the spanning trees, the minimal paths and minimal cutsets of a graph, starting from the incidence matrix of the graph [1,3]. All the above algorithms employ a unique tracing process based on search techniques. The above algorithms have a number of salient features. The arithmetic and logic operations are very simple, which makes it possible to design small desk top calculators capable of handling reasonably large and complex graphs. The major constraint of these equipments is the memory capacity vis à vis their capability of handling larger graphs. The authors designed a microprocessor based system [2] to find spanning trees. The end results were available in the form of code numbers of branches appearing in a spanning tree, which had to be noted down, every time a tree was generated. In the new system the end results are in a more compact form, i.e. the vectors (see definition), one vector for one tree. The user can easily note down the vectors and decode them later to obtain the branches of a tree. In the new system the user can reallocate the available working memory space to suit the problem. The memory requirement in the new approach is also less.     

Solving minimum spanning tree problem with DNA computing

Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.     

Two-dimensional phase unwrapping using a minimum spanning treealgorithm

Phase unwrapping refers to the determination of phase from modulo 2pi data, some of which may not be reliable. In 2D, this is equivalent to confining the support of the phase function to one or more arbitrarily shaped regions. A phase unwrapping algorithm is presented which works for 2D data known only within a set of nonconnected regions with possibly nonconvex boundaries. The algorithm includes the following steps: segmentation to identify connectivity, phase unwrapping within each segment using a Taylor series expansion, phase unwrapping between disconnected segments along an optimum path, and filling of phase information voids. The optimum path for intersegment unwrapping is determined by a minimum spanning tree algorithm. Although the algorithm is applicable to any 2D data, the main application addressed is magnetic resonance imaging (MRI) where phase maps are useful.     

Generalised star graphs

Generalised star graphs are defined, and a general formula is given for the number of (spanning) trees in the incomplete graphs resulting from the deletion of such subgraphs from a complete graph. Multigraph variations of the star are indicated.     

Quantum factor graphs

The natural Hilbert Space of quantum particles can implement maximum-likelihood (ML) decoding of classical information. The “Quantum Product Algorithm” (QPA) is computed on a Factor Graph, where function nodes are unitary matrix operations followed by appropriate quantum measurement. QPA is like the Sum-Product Algorithm (SPA), but without summary, giving optimal decode with exponentially finer detail than achievable using SPA. Graph cycles have no effect on QPA performance. QPA must be repeated a number of times before successful and the ML codeword is obtained only after repeated quantum “experiments”. ML amplification improves decoding accuracy, and Distributed QPA facilitates successful evolution.