Search

Real-world scene understanding requires recognizing object categories in novel visual scenes. This paper describes a composition system that automatically learns structured, hierarchical object representations in an unsupervised manner without requiring manual segmentation or manual object localization. A central concept for learning object models in the challenging, general case of unconstrained scenes, large intraclass variations, large numbers of categories, and lacking supervision information is to exploit the compositional nature of our (visual) world. The compositional nature of visual objects significantly limits their representation complexity and renders learning of structured object models statistically and computationally tractable. We propose a robust descriptor for local image parts and show how characteristic compositions of parts can be learned that are based on an unspecific part vocabulary shared between all categories. Moreover, a Bayesian network is presented that comprises all the compositional constituents together with scene context and object shape. Object recognition is then formulated as a statistical inference problem in this probabilistic model.

In neuroanatomy, automatic geometry extraction of neurons from electron microscopy images is becoming one of the main limiting factors in getting new insights into the functional structure of the brain. We propose a novel framework for tracing neuronal processes over serial sections for 3d reconstructions. The automatic processing pipeline combines the probabilistic output of a random forest classifier with geometrical consistency constraints which take the geometry of whole sections into account. Our experiments demonstrate significant improvement over grouping by Euclidean distance, reducing the split and merge error per object by a factor of two.

Comprehensive characterization of a proteome is a fundamental goal in proteomics. To achieve saturation coverage of a proteome or specific subproteome via tandem mass spectrometric identification of tryptic protein sample digests, proteomics data sets are growing dramatically in size and heterogeneity. The trend toward very large integrated data sets poses so far unsolved challenges to control the uncertainty of protein identifications going beyond well established confidence measures for peptide-spectrum matches. We present MAYU, a novel strategy that reliably estimates false discovery rates for protein identifications in large scale data sets. We validated and applied MAYU using various large proteomics data sets. The data show that the size of the data set has an important and previously underestimated impact on the reliability of protein identifications. We particularly found that protein false discovery rates are significantly elevated compared with those of peptide-spectrum matches. The function provided by MAYU is critical to control the quality of proteome data repositories and thereby to enhance any study relying on these data sources. The MAYU software is available as standalone software and also integrated into the Trans-Proteomic Pipeline.

Motivation: Liquid chromatography tandem mass spectrometry (LC-MS/MS) is the predominant method to comprehensively characterize complex protein mixtures such as samples from prefractionated or complete proteomes. In order to maximize proteome coverage for the studied sample, i.e. identify as many traceable proteins as possible, LC-MS/MS experiments are typically repeated extensively and the results combined. Proteome coverage prediction is the task of estimating the number of peptide discoveries of future LC-MS/MS experiments. Proteome coverage prediction is important to enhance the design of efficient proteomics studies. To date, there does not exist any method to reliably estimate the increase of proteome coverage at an early stage., Results: We propose an extended infinite Markov model DiriSim to extrapolate the progression of proteome coverage based on a small number of already performed LC-MS/MS experiments. The method explicitly accounts for the uncertainty of peptide identifications. We tested DiriSim on a set of 37 LC-MS/MS experiments of a complete proteome sample and demonstrated that DiriSim correctly predicts the coverage progression already from a small subset of experiments. The predicted progression enabled us to specify maximal coverage for the test sample. We demonstrated that quality requirements on the final proteome map impose an upper bound on the number of useful experiment repetitions and limit the achievable proteome coverage.

Purpose: To evaluate molecular and immunohistochemical markers to develop a molecular grading of urothelial bladder cancer and to test these markers in voided urine samples., Experimental Design: 255 consecutive biopsies from primary bladder cancer patients were evaluated on a tissue microarray. The clinical parameters gender, age, adjacent carcinoma in situ, and multifocality were collected. UroVysion fluorescence in situ hybridization (FISH) was done. Expression of cytokeratin 20, MIB1, and TP53 was analyzed by immunohistochemistry. Fibroblast growth factor receptor 3 (FGFR3) status was studied by SNaPshot mutation detection. Results were correlated with clinical outcome by Cox regression analysis. To assess the predictive power of different predictor subsets to detect high grade and tumor invasion, logistic regression models were learned. Additionally, voided urine samples of 119 patients were investigated. After cytologic examination, urine samples were matched with their biopsies and analyzed for loss of heterozygosity (LOH), FGFR3 mutation, polysomy, and p16 deletion using UroVysion FISH. Receiver operator characteristic curves for various predictor subsets were plotted., Results: In biopsies, high grade and solid growth pattern were independent prognostic factors for overall survival. A model consisting of UroVysion FISH and FGFR3 status (FISH + FGFR3) predicted high grade significantly better compared with a recently proposed molecular grade (MIB1 + FGFR3). In voided urine, the combination of cytology with LOH analysis (CYTO + LOH) reached the highest diagnostic accuracy for the detection of bladder cancer cells and performed better than cytology alone (sensitivity of 88.2% and specificity of 97.1%)., Conclusions: The combination of cytology with LOH analysis could reduce unpleasant cystoscopies for bladder cancer patients.

Objective: Differential quantification of proteins by liquid chromatography/mass spectrometry requires the alignment of a retention time axis. The alignment automatically corrects for time changes in the liquid chromatography unit when repeating two experiments., Methods: In this paper we will show an extension of non-negative canonical correlation analysis. We introduce an adaptive scale space estimation that adapts the complexity of a monotone regression function to the density of measurements across the retention time. Furthermore, a global model selection of the scale is replaced by a local one, where we estimate the scale for each individual time axis, instead of a global parameter that holds for all time axes., Results: We show in experiments that we got a 13% gain. The performance gain is measured in the number of proteins that are detected to differ significantly in abundance for two different biological samples., Conclusion: We conclude that the adaptive scale estimation and the local model selection can outperform the global model selection which yields a more effective selection of differentially abundant proteins.

It is estimated that in 2010 more than 220 million people will be affected by type 2 diabetes mellitus (T2DM). Early evidence indicates that specific markers for alpha and beta cells in pancreatic islets of Langerhans can be used for early T2DM diagnosis. Currently, the analysis of such histological tissues is manually performed by trained pathologists using a light microscope. To objectify classification results and to reduce the processing time of histological tissues, an automated computational pathology framework for segmentation of pancreatic islets from histopathological fluorescence images is proposed. Due to high variability in the staining intensities for alpha and beta cells, classical medical imaging approaches fail in this scenario. The main contribution of this paper consists of a novel graph-based segmentation approach based on cell nuclei detection with randomized tree ensembles. The algorithm is trained via a cross validation scheme on a ground truth set of islet images manually segmented by 4 expert pathologists. Test errors obtained from the cross validation procedure demonstrate that the graph-based computational pathology analysis proposed is performing competitively to the expert pathologists while outperforming a baseline morphological approach.

Renal cell carcinoma (RCC) can be diagnosed by histological tissue analysis where exact counts of cancerous cell nuclei are required. We propose a completely automated image analysis pipeline to predict the survival of RCC patients based on the analysis of immunohistochemical staining of MIB-1 on tissue microarrays. A random forest classifier detects cell nuclei of cancerous cells and predicts their staining. The classifier training is achieved by expert annotations of 2300 nuclei gathered from tissues of 9 different RCC patients. The application to a test set of 133 patients clearly demonstrates that our computational pathology analysis matches the prognostic performance of expert pathologists.

We present and evaluate a strategy for the mass spectrometric identification of proteins from organisms for which no genome sequence information is available that incorporates cross-species information from sequenced organisms. The presented method combines spectrum quality scoring, de novo sequencing and error tolerant BLAST searches and is designed to decrease input data complexity. Spectral quality scoring reduces the number of investigated mass spectra without a loss of information. Stringent quality-based selection and the combination of different de novo sequencing methods substantially increase the catalog of significant peptide alignments. The de novo sequences passing a reliability filter are subsequently submitted to error tolerant BLAST searches and MS-BLAST hits are validated by a sampling technique. With the described workflow, we identified up to 20% more groups of homologous proteins in proteome analyses with organisms whose genome is not sequenced than by state-of-the-art database searches in an Arabidopsis thaliana database. We consider the novel data analysis workflow an excellent screening method to identify those proteins that evade detection in proteomics experiments as a result of database constraints.

Motivation: Tandem mass spectrometry allows for high-throughput identification of complex protein samples. Searching tandem mass spectra against sequence databases is the main analysis method nowadays. Since many peptide variations are possible, including them in the search space seems only logical. However, the search space usually grows exponentially with the number of independent variations and may therefore overwhelm computational resources., Results: We provide fast, cache-efficient search algorithms to screen large peptide search spaces including non-tryptic peptides, whole genomes, dozens of posttranslational modifications, unannotated point mutations and even unannotated splice sites. All these search spaces can be screened simultaneously. By optimizing the cache usage, we achieve a calculation speed that closely approaches the limits of the hardware. At the same time, we control the size of the overall search space by limiting the combinations of variations that can co-occur on the same peptide. Using a hypergeometric scoring scheme, we applied these algorithms to a dataset of 1 420 632 spectra. We were able to identify a considerable number of peptide variations within a modest amount of computing time on standard desktop computers.

Automated segmentation of images has been considered an important intermediate processing task to extract semantic meaning from pixels. We propose an integrated approach for image segmentation based on a generative clustering model combined with coarse shape information and robust parameter estimation. The sensitivity of segmentation solutions to image variations is measured by image resampling. Shape information is included in the inference process to guide ambiguous groupings of color and texture features. Shape and similarity-based grouping information is combined into a semantic likelihood map in the framework of Bayesian statistics. Experimental evidence shows that semantically meaningful segments are inferred even when image data alone gives rise to ambiguous segmentations.

Background: Quantitative analysis of differential protein expressions requires to align temporal elution measurements from liquid chromatography coupled to mass spectrometry (LC/MS). We propose multiple Canonical Correlation Analysis (mCCA) as a method to align the non-linearly distorted time scales of repeated LC/MS experiments in a robust way., Results: Multiple canonical correlation analysis is able to map several time series to a consensus time scale. The alignment function is learned in a supervised fashion. We compare our approach with previously published methods for aligning mass spectrometry data on a large proteomics dataset. The proposed method significantly increases the number of proteins that are identified as being differentially expressed in different biological samples., Conclusion: Jointly aligning multiple liquid chromatography/mass spectrometry samples by mCCA substantially increases the detection rate of potential bio-markers which significantly improves the interpretability of LC/MS data.

Motivation: Mass spectrometry (MS) combined with high-performance liquid chromatography (LC) has received considerable attention for high-throughput analysis of proteomes. Isotopic labeling techniques such as ICAT [5,6] have been successfully applied to derive differential quantitative information for two protein samples, however at the price of significantly increased complexity of the experimental setup. To overcome these limitations, we consider a label-free setting where correspondences between elements of two samples have to be established prior to the comparative analysis. The alignment between samples is achieved by nonlinear robust ridge regression. The correspondence estimates are guided in a semi-supervised fashion by prior information which is derived from sequenced tandem mass spectra., Results: The semi-supervised method for finding correspondences was successfully applied to aligning highly complex protein samples, even if they exhibit large variations due to different biological conditions. A large-scale experiment clearly demonstrates that the proposed method bridges the gap between statistical data analysis and label-free quantitative differential proteomics., Availability: The software will be available on the website http://people.inf.ethz.ch/befische/proteomics.

De novo sequencing of peptides poses one of the most challenging tasks in data analysis for proteome research. In this paper, a generative hidden Markov model (HMM) of mass spectra for de novo peptide sequencing which constitutes a novel view on how to solve this problem in a Bayesian framework is proposed. Further extensions of the model structure to a graphical model and a factorial HMM to substantially improve the peptide identification results are demonstrated. Inference with the graphical model for de novo peptide sequencing estimates posterior probabilities for amino acids rather than scores for single symbols in the sequence. Our model outperforms state-of-the-art methods for de novo peptide sequencing on a large test set of spectra.

A network of leaky integrate-and-fire (IAF) neurons is proposed to segment gray-scale images. The network architecture with local competition between neurons that encode segment assignments of image blocks is motivated by a histogram clustering approach to image segmentation. Lateral excitatory connections between neighboring image sites yield a local smoothing of segments. The mean firing rate of class membership neurons encodes the image segmentation. A weight modification scheme is proposed that estimates segment-specific prototypical histograms. The robustness properties of the network implementation make it amenable to an analog VLSI realization. Results on synthetic and real-world images demonstrate the effectiveness of the architecture.

Data clustering describes a set of frequently employed techniques in exploratory data analysis to extract "natural" group structure in data. Such groupings need to be validated to separate the signal in the data from spurious structure. In this context, finding an appropriate number of clusters is a particularly important model selection question. We introduce a measure of cluster stability to assess the validity of a cluster model. This stability measure quantifies the reproducibility of clustering solutions on a second sample, and it can be interpreted as a classification risk with regard to class labels produced by a clustering algorithm. The preferred number of clusters is determined by minimizing this classification risk as a function of the number of clusters. Convincing results are achieved on simulated as well as gene expression data sets. Comparisons to other methods demonstrate the competitive performance of our method and its suitability as a general validation tool for clustering solutions in real-world problems.

This paper introduces a novel adaptive image segmentation algorithm which represents images by polygonal segments. The algorithm is based on an intuitive generative model for pixel intensities and its associated cost function which can be effectively optimized by a hierarchical triangulation algorithm. A triangular mesh is iteratively refined and reorganized to extract a compact description of the essential image structure. After analyzing fundamental convexity properties of our cost function, we adapt an information-theoretic bound to assess the statistical significance of a given triangulation step. The bound effectively defines a stopping criterion to limit the number of triangles in the mesh, thereby avoiding undesirable overfitting phenomena. It also facilitates the development of a multiscale variant of the triangulation algorithm, which substantially improves its computational demands. The algorithm has various applications in contextual classification, remote sensing, and visual object recognition. It is particularly suitable for the segmentation of noisy imagery.

Image quantization and digital halftoning, two fundamental image processing problems, are generally performed sequentially and, in most cases, independent of each other. Color reduction with a pixel-wise defined distortion measure and the halftoning process with its local averaging neighborhood typically optimize different quality criteria or, frequently, follow a heuristic approach without reference to any quantitative quality measure. In this paper, we propose a new model to simultaneously quantize and halftone color images. The method is based on a rigorous cost-function approach which optimizes a quality criterion derived from a simplified model of human perception. It incorporates spatial and contextual information into the quantization and thus overcomes the artificial separation of quantization and halftoning. Optimization is performed by an efficient multiscale procedure which substantially alleviates the computational burden. The quality criterion and the optimization algorithms are evaluated on a representative set of artificial and real-world images showing a significant image quality improvement compared to standard color reduction approaches. Applying the developed cost function, we also suggest a new distortion measure for evaluating the overall quality of color reduction schemes.

Vision extracts useful information from images. Reconstructing the three-dimensional structure of our environment and recognizing the objects that populate it are among the most important functions of our visual system. Computer vision researchers study the computational principles of vision and aim at designing algorithms that reproduce these functions. Vision is difficult: the same scene may give rise to very different images depending on illumination and viewpoint. Typically, an astronomical number of hypotheses exist that in principle have to be analyzed to infer a correct scene description. Moreover, image information might be extracted at different levels of spatial and logical resolution dependent on the image processing task. Knowledge of the world allows the visual system to limit the amount of ambiguity and to greatly simplify visual computations. We discuss how simple properties of the world are captured by the Gestalt rules of grouping, how the visual system may learn and organize models of objects for recognition, and how one may control the complexity of the description that the visual system computes.