OTCYMIST: Otsu-Canny minimal spanning tree for born-digital images

Text segmentation and localization algorithms are proposed for the born-digital image dataset. Binarization and edge detection are separately carried out on the three colour planes of the image. Connected components (CC's) obtained from the binarized image are thresholded based on their area and aspect ratio. CC's which contain sufficient edge pixels are retained. A novel approach is presented, where the text components are represented as nodes of a graph. Nodes correspond to the centroids of the individual CC's. Long edges are broken from the minimum spanning tree of the graph. Pair wise height ratio is also used to remove likely non-text components. A new minimum spanning tree is created from the remaining nodes. Horizontal grouping is performed on the CC's to generate bounding boxes of text strings. Overlapping bounding boxes are removed using an overlap area threshold. Non-overlapping and minimally overlapping bounding boxes are used for text segmentation. Vertical splitting is applied to generate bounding boxes at the word level. The proposed method is applied on all the images of the test dataset and values of precision, recall and H-mean are obtained using different approaches.

A divisive scheme for constructing minimal spanning trees in coordinate space

An algorithm to generate a minimal spanning tree is presented when the nodes with their coordinates in some m-dimensional Euclidean space and the corresponding metric are given. This algorithm is tested on manually generated data sets. The worst case time complexity of this algorithm is O(n log2n) for a collection of n data samples.

Dense active appearance models using a bounded diameter minimum spanning tree

We present a method for producing dense Active Appearance Models (AAMs), suitable for video-realistic synthesis. To this end we estimate a joint alignment of all training images using a set of pairwise registrations and ensure that these pairwise registrations are only calculated between similar images. This is achieved by defining a graph on the image set whose edge weights correspond to registration errors and computing a bounded diameter minimum spanning tree (BDMST). Dense optical flow is used to compute pairwise registration and we introduce a flow refinement method to align small scale texture. Once registration between training images has been established we propose a method to add vertices to the AAM in a way that minimises error between the observed flow fields and a flow field interpolated between the AAM mesh points. We demonstrate a significant improvement in model compactness using the proposed method and show it dealing with cases that are problematic for current state-of-the-art approaches.

A knowledge-based evolution strategy for the multi-objective minimum spanning tree problem

A fast Knowledge-based Evolution Strategy, KES, for the multi-objective minimum spanning tree, is presented. The proposed algorithm is validated, for the bi-objective case, with an exhaustive search for small problems (4-10 nodes), and compared with a deterministic algorithm, EPDA and NSGA-II for larger problems (up to 100 nodes) using benchmark hard instances. Experimental results show that KES finds the true Pareto fronts for small instances of the problem and calculates good approximation Pareto sets for larger instances tested. It is shown that the fronts calculated by YES are superior to NSGA-II fronts and almost as good as those established by EPDA. KES is designed to be scalable to multi-objective problems and fast due to its small complexity.

A hybridised evolutionary algorithm for multi-criterion minimum spanning tree problems

A hybridised and Knowledge-based Evolutionary Algorithm (KEA) is applied to the multi-criterion minimum spanning tree problems. Hybridisation is used across its three phases. In the first phase a deterministic single objective optimization algorithm finds the extreme points of the Pareto front. In the second phase a K-best approach finds the first neighbours of the extreme points, which serve as an elitist parent population to an evolutionary algorithm in the third phase. A knowledge-based mutation operator is applied in each generation to reproduce individuals that are at least as good as the unique parent. The advantages of KEA over previous algorithms include its speed (making it applicable to large real-world problems), its scalability to more than two criteria, and its ability to find both the supported and unsupported optimal solutions.

Spanning Tree Approach On The Snow Cleaning Problem

Snow cleaning is one of the important tasks in the winter time in Sweden. Every year government spends huge amount money for snow cleaning purpose. In this thesis we generate a shortest road network of the city and put the depots in different place of the city for snow cleaning. We generate shortest road network using minimum spanning tree algorithm and find the depots position using greedy heuristic. When snow is falling, vehicles start work from the depots and clean the snow all the road network of the city. We generate two types of model. Models are economic model and efficient model. Economic model provide good economical solution of the problem and it use less number of vehicles. Efficient model generate good efficient solution and it take less amount of time to clean the entire road network.

Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Multi-model fitting based on minimum spanning tree

This paper presents a novel approach to the computation of primitive geometrical structures, where no prior knowledge about the visual scene is available and a high level of noise is expected. We based our work on the grouping principles of proximity and similarity, of points and preliminary models. The former was realized using Minimum Spanning Trees (MST), on which we apply a stable alignment and goodness of fit criteria. As for the latter, we used spectral clustering of preliminary models. The algorithm can be generalized to various model fitting settings, without tuning of run parameters. Experiments demonstrate the significant improvement in the localization accuracy of models in plane, homography and motion segmentation examples. The efficiency of the algorithm is not dependent on fine tuning of run parameters like most others in the field.

Structure-potential relationship and nature of disorder in liquids and glassy solids

A method based on the minimal-spanning tree is extended to a collection of points in three dimensions. Two parameters, the average edge length and its standard deviation characterize the disorder. The structural phase diagram for a monatomic system of particles and the characteristic values for the uniform random distribution of points have been obtained. The method is applied to hard spheres and Lennard-Jones systems. These systems occupy distinct regions in the structural phase diagram. The structure of the Lennard-Jones system approaches that of the defective close-packed arrangements at low temperatures whereas in the liquid regime, it deviates from the close-packed configuration.

Dependence of diffusivity on density and solute diameter in liquid phase: A molecular dynamics study of Lennard-Jones system

Investigations into the variation of self-diffusivity with solute radius, density, and degree of disorder of the host medium is explored. The system consists of a binary mixture of a relatively smaller sized solute, whose size is varied and a larger sized solvent interacting via Lennard-Jones potential. Calculations have been performed at three different reduced densities of 0.7, 0.8, and 0.933. These simulations show that diffusivity exhibits a maximum for some intermediate size of the solute when the solute diameter is varied. The maximum is found at the same size of the solute at all densities which is at variance with the prediction of the levitation effect. In order to understand this anomaly, additional simulations were carried out in which the degree of disorder has been varied while keeping the density constant. The results show that the diffusivity maximum gradually disappears with increase in disorder. Disorder has been characterized by means of the minimal spanning tree. Simulations have also been carried out in which the degree of disorder is constant and only the density is altered. The results from these simulations show that the maximum in diffusivity now shifts to larger distances with decrease in density. This is in agreement with the changes in void and neck distribution with density of the host medium. These results are in excellent agreement with the predictions of the levitation effect. They suggest that the effect of disorder is to shift the maximum in diffusivity towards smaller solute radius while that of the decrease in density is to shift it towards larger solute radius. Thus, in real systems where the degree of disorder is lower at higher density and vice versa, the effect due to density and disorder have opposing influences. These are confirmed by the changes seen in the velocity autocorrelation function, self part of the intermediate scattering function and activation energy. (C) 2012 American Institute of Physics. http://dx.doi.org/10.1063/1.3701619]

长白山地区曲尾藓属植物生态分化的排序研究

The relationships of eight moss species of Dicranum in 31 sites in main ecological systems in the Changbai Mountain with environmental factors were studied by canonical correspondence analysis (CCA). The results showed that altitude, soil sand percentage, water percentage, acidity and canopy density were important environmental factors influencing the distribution of the species of Dicranum . The relationships between Dicranum elongatum Schleich. ex Schwaegr ., D.groenlandicum Brid. and altitude,between D.japonicum Mitt., D.scoparium Hedw. and canopy density,between D.polysetum Sw., D. undulatum Schrad. ex Brid. and soil acidity and water percentage,were positively correlative. The niche overlaps among the eight species of Dicranum were calculated. The minimal spanning tree of the eight species on the two-dimensional scatter plot were also drawn based on their niche overlaps, which clearly revealed the ecological similarities of eight species.

Rozproszone algorytmy aproksymacyjne dla grafów dyskowych

Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej

Evaluation of ERIC-PCR as Genotyping Method for Corynebacterium pseudotuberculosis Isolates

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)