Speeding up the EM algorithm for mixture model-based segmentation of magnetic resonance images

Mixture models implemented via the expectation-maximization (EM) algorithm are being increasingly used in a wide range of problems in pattern recognition such as image segmentation. However, the EM algorithm requires considerable computational time in its application to huge data sets such as a three-dimensional magnetic resonance (MR) image of over 10 million voxels. Recently, it was shown that a sparse, incremental version of the EM algorithm could improve its rate of convergence. In this paper, we show how this modified EM algorithm can be speeded up further by adopting a multiresolution kd-tree structure in performing the E-step. The proposed algorithm outperforms some other variants of the EM algorithm for segmenting MR images of the human brain. (C) 2004 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

Dynamic load balancing in parallel KD-tree k-means

One among the most influential and popular data mining methods is the k-Means algorithm for cluster analysis. Techniques for improving the efficiency of k-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting geometrical constraints and an efficient data structure, notably a multidimensional binary search tree (KD-Tree). These techniques allow to reduce the number of distance computations the algorithm performs at each iteration. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient k-Means variants in parallel computing environments. In this work, we provide a parallel formulation of the KD-Tree based k-Means algorithm for distributed memory systems and address its load balancing issue. Three solutions have been developed and tested. Two approaches are based on a static partitioning of the data set and a third solution incorporates a dynamic load balancing policy.

Operações booleanas entre objetos delimitados por surfels usando constrained BSP-trees

As áreas de visualização e modelagem baseados em pontos têm sido pesquisadas ativamente na computação gráfica. Pontos com atributos (por exemplo, normais) são geralmente chamados de surfels e existem vários algoritmos para a manipulação e visualização eficiente deles. Um ponto chave para a eficiência de muitos métodos é o uso de estruturas de particionamento do espaço. Geralmente octrees e KD-trees, por utilizarem cortes alinhados com os eixos são preferidas em vez das BSP-trees, mais genéricas. Neste trabalho, apresenta-se uma estrutura chamada Constrained BSP-tree (CBSP-tree), que pode ser vista como uma estrutura intermediárias entre KD-trees e BSP-trees. A CBSP-tree se caracteriza por permitir cortes arbitrários desde que seja satisfeito um critério de validade dos cortes. Esse critério pode ser redefinido de acordo com a aplicação. Isso permite uma aproximação melhor de regões curvas. Apresentam-se algoritmos para construir CBSP-trees, valendo-se da flexibilidade que a estrutura oferece, e para realizar operações booleanas usando uma nova classificação de interior/exterior.

Scalability of efficient parallel K-Means

Clustering is defined as the grouping of similar items in a set, and is an important process within the field of data mining. As the amount of data for various applications continues to increase, in terms of its size and dimensionality, it is necessary to have efficient clustering methods. A popular clustering algorithm is K-Means, which adopts a greedy approach to produce a set of K-clusters with associated centres of mass, and uses a squared error distortion measure to determine convergence. Methods for improving the efficiency of K-Means have been largely explored in two main directions. The amount of computation can be significantly reduced by adopting a more efficient data structure, notably a multi-dimensional binary search tree (KD-Tree) to store either centroids or data points. A second direction is parallel processing, where data and computation loads are distributed over many processing nodes. However, little work has been done to provide a parallel formulation of the efficient sequential techniques based on KD-Trees. Such approaches are expected to have an irregular distribution of computation load and can suffer from load imbalance. This issue has so far limited the adoption of these efficient K-Means techniques in parallel computational environments. In this work, we provide a parallel formulation for the KD-Tree based K-Means algorithm and address its load balancing issues.

Space partitioning for scalable K-means

K-Means is a popular clustering algorithm which adopts an iterative refinement procedure to determine data partitions and to compute their associated centres of mass, called centroids. The straightforward implementation of the algorithm is often referred to as `brute force' since it computes a proximity measure from each data point to each centroid at every iteration of the K-Means process. Efficient implementations of the K-Means algorithm have been predominantly based on multi-dimensional binary search trees (KD-Trees). A combination of an efficient data structure and geometrical constraints allow to reduce the number of distance computations required at each iteration. In this work we present a general space partitioning approach for improving the efficiency and the scalability of the K-Means algorithm. We propose to adopt approximate hierarchical clustering methods to generate binary space partitioning trees in contrast to KD-Trees. In the experimental analysis, we have tested the performance of the proposed Binary Space Partitioning K-Means (BSP-KM) when a divisive clustering algorithm is used. We have carried out extensive experimental tests to compare the proposed approach to the one based on KD-Trees (KD-KM) in a wide range of the parameters space. BSP-KM is more scalable than KDKM, while keeping the deterministic nature of the `brute force' algorithm. In particular, the proposed space partitioning approach has shown to overcome the well-known limitation of KD-Trees in high-dimensional spaces and can also be adopted to improve the efficiency of other algorithms in which KD-Trees have been used.

Fiedler trees for multiscale surface analysis

In this work we introduce a new hierarchical surface decomposition method for multiscale analysis of surface meshes. In contrast to other multiresolution methods, our approach relies on spectral properties of the surface to build a binary hierarchical decomposition. Namely, we utilize the first nontrivial eigenfunction of the Laplace-Beltrami operator to recursively decompose the surface. For this reason we coin our surface decomposition the Fiedler tree. Using the Fiedler tree ensures a number of attractive properties, including: mesh-independent decomposition, well-formed and nearly equi-areal surface patches, and noise robustness. We show how the evenly distributed patches can be exploited for generating multiresolution high quality uniform meshes. Additionally, our decomposition permits a natural means for carrying out wavelet methods, resulting in an intuitive method for producing feature-sensitive meshes at multiple scales. Published by Elsevier Ltd.

Efficient update and retrieval of objects in a multiresolution geospatial database

Many emerging applications benefit from the extraction of geospatial data specified at different resolutions for viewing purposes. Data must also be topologically accurate and up-to-date as it often represents real-world changing phenomena. Current multiresolution schemes use complex opaque data types, which limit the capacity for in-database object manipulation. By using z-values and B+trees to support multiresolution retrieval, objects are fragmented in such a way that updates to objects or object parts are executed using standard SQL (Structured Query Language) statements as opposed to procedural functions. Our approach is compared to a current model, using complex data types indexed under a 3D (three-dimensional) R-tree, and shows better performance for retrieval over realistic window sizes and data loads. Updates with the R-tree are slower and preclude the feasibility of its use in time-critical applications whereas, predictably, projecting the issue to a one-dimensional index allows constant updates using z-values to be implemented more efficiently.

WOOD DENSITY VARIATION AND TREE RING DEMARCATION IN Gmelina arborea TREES USING X-RAY DENSITOMETRY

Due to its relationship with other properties, wood density is the main wood quality parameter. Modern, accurate methods - such as X-ray densitometry - are applied to determine the spatial distribution of density in wood sections and to evaluate wood quality. The objectives of this study were to determinate the influence of growing conditions on wood density variation and tree ring demarcation of gmelina trees from fast growing plantations in Costa Rica. The wood density was determined by X-ray densitometry method. Wood samples were cut from gmelina trees and were exposed to low X-rays. The radiographic films were developed and scanned using a 256 gray scale with 1000 dpi resolution and the wood density was determined by CRAD and CERD software. The results showed tree-ring boundaries were distinctly delimited in trees growing in site with rainfall lower than 25 10 mm/year. It was demonstrated that tree age, climatic conditions and management of plantation affects wood density and its variability. The specific effect of variables on wood density was quantified by for multiple regression method. It was determined that tree year explained 25.8% of the total variation of density and 19.9% were caused by climatic condition where the tree growing. Wood density was less affected by the intensity of forest management with 5.9% of total variation.

Variation in the wood anatomical structure of Gmelina arborea (Verbenaceae) trees at different ecological conditions in Costa Rica

The tree Gmelina arborea has been widely introduced in Costa Rica for commercial purposes. This new conditions for melina cause variations on anatomy in secondary xylem of the trees growing in plantations. The objective of the present research was to determine the variation in the anatomy of xylem caused by the ecological conduction variation. Dimensions of fiber, axial parenchyma percentage of cross sections, parameters of vessels and the ray were measured. The results showed that some anatomical characteristics remained stable despite variations of ecological conditions, especially radial parenchyma and anatomical features which were less affected by the altitude. On the other hand, the vessels, axial parenchyma and fiber were less stable because they were affected significantly by the longitude, latitude, altitude and precipitation. Latitude significantly affected vessel percentage, length and diameter of the fiber and lumen. Longitude affected vessel percentage and fiber diameter. Altitude had a significant correlation with the amount of cells at my height. Annual average precipitation affected vessel percentage and diameter, not only of the fiber, but also of the lumen. These results suggest that the new growth conditions of G. arborea trees in Costa Rica have produced an anatomic adaptation.

INFLUENCE OF ALTITUDE, AGE AND DIAMETER ON YIELD AND ALPHA-BISABOLOL CONTENT OF CANDEIA TREES (Eremanthus erythropappus)

The heartwood of candeia tree is a source of essential oil rich in alpha-bisabolol, a substance widely used in the cosmetic and pharmaceutical industry. Bearing in mind the economic importance of alpha-bisabolol, this work aimed to evaluate the influence of tree age on the yield and content of alpha-bisabolol present in essential oil from candeia, considering two distinct reliefs and three diameter classes, in Aiuruoca region, south Minas Gerais state. The two distinct reliefs correspond respectively to one section of the stand growing at 1,000m of altitude (Area 1) and another section growing at 1,100m of altitude (Area 2). In each section, 15 trees were felled from among 3 different diameter classes. Discs were removed from the base of each tree to estimate their age by doing growth ring count. Soil samples were taken and Subjected to physical and chemical analysis. The logs were reduced into chips and random samples were taken for distillation to extract essential oil. The method used was steam distillation at a pressure of 2 kgf/cm(2)/2.5 h. The chemical analysis was performed in a gas chromatograph (GC) based on the alpha-bisabolol standard reference. The yield of essential oil from trees in Area I was higher than that from trees in Area 2, with the same pattern of influence for older trees. In Area 2, the alpha-bisabolol content was higher in younger trees. No differences were found between the relevant parameters in relation to diameter classes.

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

The Lobel-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars

Loebl, Komlos, and Sos conjectured that if at least half the vertices of a graph G have degree at least some k is an element of N, then every tree with at most k edges is a subgraph of G. We prove the conjecture for all trees of diameter at most 5 and for a class of caterpillars. Our result implies a bound on the Ramsey number r( T, T') of trees T, T' from the above classes.

BORON UPTAKE AND DISTRIBUTION IN FIELD GROWN CITRUS TREES

In low fertility tropical soils, boron (B) deficiency impairs fruit production. However, little information is available on the efficiency of nutrient application and use by trees. Therefore, this work verified the effects of soil and foliar applications of boron in a commercial citrus orchard. An experiment was conducted with fertigated 4-year-old `Valencia` sweet orange trees on `Swingle` citrumelo rootstock. Boron (isotopically-enriched 10B) was supplied to trees once or twice in the growing season, either dripped in the soil or sprayed on the leaves. Trees were sampled at different periods and separated into different parts for total B contents and 10B/11B isotope ratios analyses. Soil B applied via fertigation was more efficient than foliar application for the organs grown after the B fertilization. Recovery of labeled B by fruits was 21% for fertigation and 7% for foliar application. Residual effects of nutrient application in the grove were observed in the year after labeled fertilizer application, which greater proportions derived from the soil supply.