Automatic visual dictionary generation through Optimum-Path Forest clustering

Image categorization by means of bag of visual words has received increasing attention by the image processing and vision communities in the last years. In these approaches, each image is represented by invariant points of interest which are mapped to a Hilbert Space representing a visual dictionary which aims at comprising the most discriminative features in a set of images. Notwithstanding, the main problem of such approaches is to find a compact and representative dictionary. Finding such representative dictionary automatically with no user intervention is an even more difficult task. In this paper, we propose a method to automatically find such dictionary by employing a recent developed graph-based clustering algorithm called Optimum-Path Forest, which does not make any assumption about the visual dictionary's size and is more efficient and effective than the state-of-the-art techniques used for dictionary generation. © 2012 IEEE.

Automatic visual dictionary generation through optimum-path forest clusteringautomatic visual dictionary generation through optimum-path forest clustering

Image categorization by means of bag of visual words has received increasing attention by the image processing and vision communities in the last years. In these approaches, each image is represented by invariant points of interest which are mapped to a Hilbert Space representing a visual dictionary which aims at comprising the most discriminative features in a set of images. Notwithstanding, the main problem of such approaches is to find a compact and representative dictionary. Finding such representative dictionary automatically with no user intervention is an even more difficult task. In this paper, we propose a method to automatically find such dictionary by employing a recent developed graph-based clustering algorithm called Optimum-Path Forest, which does not make any assumption about the visual dictionary's size and is more efficient and effective than the state-of-the-art techniques used for dictionary generation.

A nature-inspired approach to speed up optimum-path forest clustering and its application to intrusion detection in computer networks

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Collaborative fuzzy clustering algorithms: some refinements and design guidelines

There are some variants of the widely used Fuzzy C-Means (FCM) algorithm that support clustering data distributed across different sites. Those methods have been studied under different names, like collaborative and parallel fuzzy clustering. In this study, we offer some augmentation of the two FCM-based clustering algorithms used to cluster distributed data by arriving at some constructive ways of determining essential parameters of the algorithms (including the number of clusters) and forming a set of systematically structured guidelines such as a selection of the specific algorithm depending on the nature of the data environment and the assumptions being made about the number of clusters. A thorough complexity analysis, including space, time, and communication aspects, is reported. A series of detailed numeric experiments is used to illustrate the main ideas discussed in the study.

Automatic aspect discrimination in data clustering

The attributes describing a data set may often be arranged in meaningful subsets, each of which corresponds to a different aspect of the data. An unsupervised algorithm (SCAD) that simultaneously performs fuzzy clustering and aspects weighting was proposed in the literature. However, SCAD may fail and halt given certain conditions. To fix this problem, its steps are modified and then reordered to reduce the number of parameters required to be set by the user. In this paper we prove that each step of the resulting algorithm, named ASCAD, globally minimizes its cost-function with respect to the argument being optimized. The asymptotic analysis of ASCAD leads to a time complexity which is the same as that of fuzzy c-means. A hard version of the algorithm and a novel validity criterion that considers aspect weights in order to estimate the number of clusters are also described. The proposed method is assessed over several artificial and real data sets.

A clustering method for robust and reliable large scale functional and structural protein sequence annotation

Bioinformatics, in the last few decades, has played a fundamental role to give sense to the huge amount of data produced. Obtained the complete sequence of a genome, the major problem of knowing as much as possible of its coding regions, is crucial. Protein sequence annotation is challenging and, due to the size of the problem, only computational approaches can provide a feasible solution. As it has been recently pointed out by the Critical Assessment of Function Annotations (CAFA), most accurate methods are those based on the transfer-by-homology approach and the most incisive contribution is given by cross-genome comparisons. In the present thesis it is described a non-hierarchical sequence clustering method for protein automatic large-scale annotation, called “The Bologna Annotation Resource Plus” (BAR+). The method is based on an all-against-all alignment of more than 13 millions protein sequences characterized by a very stringent metric. BAR+ can safely transfer functional features (Gene Ontology and Pfam terms) inside clusters by means of a statistical validation, even in the case of multi-domain proteins. Within BAR+ clusters it is also possible to transfer the three dimensional structure (when a template is available). This is possible by the way of cluster-specific HMM profiles that can be used to calculate reliable template-to-target alignments even in the case of distantly related proteins (sequence identity < 30%). Other BAR+ based applications have been developed during my doctorate including the prediction of Magnesium binding sites in human proteins, the ABC transporters superfamily classification and the functional prediction (GO terms) of the CAFA targets. Remarkably, in the CAFA assessment, BAR+ placed among the ten most accurate methods. At present, as a web server for the functional and structural protein sequence annotation, BAR+ is freely available at http://bar.biocomp.unibo.it/bar2.0.

Phylogenetic analysis of Prevotella nigrescens, Prevotella intermedia and Porphyromonas gingivalis clinical strains reveals a clear species clustering

Prevotella nigrescens, Prevotella intermedia and Porphyromonas gingivalis are oral pathogens from the family Bacteroidaceae, regularly isolated from cases of gingivitis and periodontitis. In this study, the phylogenetic variability of these three bacterial species was investigated by means of 16S rRNA (rrs) gene sequence comparisons of a set of epidemiologically and geographically diverse isolates. For each of the three species, the rrs gene sequences of 11 clinical isolates as well as the corresponding type strains was determined. Comparison of all rrs sequences obtained with those of closely related species revealed a clear clustering of species, with only a little intraspecies variability but a clear difference in the rrs gene with respect to the next related taxon. The results indicate that the three species form stable, homogeneous genetic groups, which favours an rrs-based species identification of these oral pathogens. This is especially useful given the 7% sequence divergence between Prevotella intermedia and Prevotella nigrescens, since phenotypic distinction between the two Prevotella species is inconsistent or involves techniques not applicable in routine identification.

Generalized fuzzy clustering for segmentation of multi-spectral magnetic resonance images.

An integrated approach for multi-spectral segmentation of MR images is presented. This method is based on the fuzzy c-means (FCM) and includes bias field correction and contextual constraints over spatial intensity distribution and accounts for the non-spherical cluster's shape in the feature space. The bias field is modeled as a linear combination of smooth polynomial basis functions for fast computation in the clustering iterations. Regularization terms for the neighborhood continuity of intensity are added into the FCM cost functions. To reduce the computational complexity, the contextual regularizations are separated from the clustering iterations. Since the feature space is not isotropic, distance measure adopted in Gustafson-Kessel (G-K) algorithm is used instead of the Euclidean distance, to account for the non-spherical shape of the clusters in the feature space. These algorithms are quantitatively evaluated on MR brain images using the similarity measures.

MRI texture analysis as means for addressing rehydration and milk diffusion of cereals

Cereals microstructure is one of the primary quality attributes of cereals. Cereals rehydration and milk diffusion depends on such microstructure and thus, the crispiness and the texture, which will make it more palatable for the final consumer. Magnetic Resonance Imaging (MRI) is a very powerful topographic tool since acquisition parameter leads to a wide possibility for identifying textures, structures and liquids mobility. It is suited for non-invasive imaging of water and fats. Rehydration and diffusion cereals processes were measured by MRI at different times and using two different kinds of milk, varying their fat level. Several images were obtained. A combination of textural analysis (based on the analysis of histograms) and segmentation methods (in order to understand the rehydration level of each variety of cereals) were performed. According to the rehydration level, no advisable clustering behavior was found. Nevertheless, some differences were noticeable between the coating, the type of milk and the variety of cereals

Improvement for detection of microcalcifications through clustering algorithms and artificial neural networks

A new method for detecting microcalcifications in regions of interest (ROIs) extracted from digitized mammograms is proposed. The top-hat transform is a technique based on mathematical morphology operations and, in this paper, is used to perform contrast enhancement of the mi-crocalcifications. To improve microcalcification detection, a novel image sub-segmentation approach based on the possibilistic fuzzy c-means algorithm is used. From the original ROIs, window-based features, such as the mean and standard deviation, were extracted; these features were used as an input vector in a classifier. The classifier is based on an artificial neural network to identify patterns belonging to microcalcifications and healthy tissue. Our results show that the proposed method is a good alternative for automatically detecting microcalcifications, because this stage is an important part of early breast cancer detection

Image Segmentation Using Ant System-based Clustering Algorithm

Industrial applications of computer vision sometimes require detection of atypical objects that occur as small groups of pixels in digital images. These objects are difficult to single out because they are small and randomly distributed. In this work we propose an image segmentation method using the novel Ant System-based Clustering Algorithm (ASCA). ASCA models the foraging behaviour of ants, which move through the data space searching for high data-density regions, and leave pheromone trails on their path. The pheromone map is used to identify the exact number of clusters, and assign the pixels to these clusters using the pheromone gradient. We applied ASCA to detection of microcalcifications in digital mammograms and compared its performance with state-of-the-art clustering algorithms such as 1D Self-Organizing Map, k-Means, Fuzzy c-Means and Possibilistic Fuzzy c-Means. The main advantage of ASCA is that the number of clusters needs not to be known a priori. The experimental results show that ASCA is more efficient than the other algorithms in detecting small clusters of atypical data.

Identification of pore spaces in 3D CT soil images using a PFCM partitional clustering

Recent advances in non-destructive imaging techniques, such as X-ray computed tomography (CT), make it possible to analyse pore space features from the direct visualisation from soil structures. A quantitative characterisation of the three-dimensional solid-pore architecture is important to understand soil mechanics, as they relate to the control of biological, chemical, and physical processes across scales. This analysis technique therefore offers an opportunity to better interpret soil strata, as new and relevant information can be obtained. In this work, we propose an approach to automatically identify the pore structure of a set of 200-2D images that represent slices of an original 3D CT image of a soil sample, which can be accomplished through non-linear enhancement of the pixel grey levels and an image segmentation based on a PFCM (Possibilistic Fuzzy C-Means) algorithm. Once the solids and pore spaces have been identified, the set of 200-2D images is then used to reconstruct an approximation of the soil sample by projecting only the pore spaces. This reconstruction shows the structure of the soil and its pores, which become more bounded, less bounded, or unbounded with changes in depth. If the soil sample image quality is sufficiently favourable in terms of contrast, noise and sharpness, the pore identification is less complicated, and the PFCM clustering algorithm can be used without additional processing; otherwise, images require pre-processing before using this algorithm. Promising results were obtained with four soil samples, the first of which was used to show the algorithm validity and the additional three were used to demonstrate the robustness of our proposal. The methodology we present here can better detect the solid soil and pore spaces on CT images, enabling the generation of better 2D?3D representations of pore structures from segmented 2D images.

Activity-dependent regulation of synaptic clustering in a hippocampal culture system

Currently, there is a limited understanding of the factors that influence the localization and density of individual synapses in the central nervous system. Here we have studied the effects of activity on synapse formation between hippocampal dentate granule cells and CA3 pyramidal neurons in culture, taking advantage of FM1–43 as a fluorescent marker of synaptic boutons. We observed an early tendency for synapses to group together, quickly followed by the appearance of synaptic clusters on dendritic processes. These events were strongly influenced by N-methyl-d-aspartic acid receptor- and cyclic AMP-dependent signaling. The microstructure and localization of the synaptic clusters resembled that found in hippocampus, at mossy fiber synapses of stratum lucidum. Activity-dependent clustering of synapses represents a means for synaptic targeting that might contribute to synaptic organization in the brain.

Kinase domain of the muscle-specific receptor tyrosine kinase (MuSK) is sufficient for phosphorylation but not clustering of acetylcholine receptors: Required role for the MuSK ectodomain?

Formation of the neuromuscular junction (NMJ) depends upon a nerve-derived protein, agrin, acting by means of a muscle-specific receptor tyrosine kinase, MuSK, as well as a required accessory receptor protein known as MASC. We report that MuSK does not merely play a structural role by demonstrating that MuSK kinase activity is required for inducing acetylcholine receptor (AChR) clustering. We also show that MuSK is necessary, and that MuSK kinase domain activation is sufficient, to mediate a key early event in NMJ formation—phosphorylation of the AChR. However, MuSK kinase domain activation and the resulting AChR phosphorylation are not sufficient for AChR clustering; thus we show that the MuSK ectodomain is also required. These results indicate that AChR phosphorylation is not the sole trigger of the clustering process. Moreover, our results suggest that, unlike the ectodomain of all other receptor tyrosine kinases, the MuSK ectodomain plays a required role in addition to simply mediating ligand binding and receptor dimerization, perhaps by helping to recruit NMJ components to a MuSK-based scaffold.