MLBio+Laboratory Machine Learning in Biomedical Informatics



Bioinformatics & Data Mining

PrePrint: Practical Ensemble Classification Error Bounds for Different Operating Points

TKDE - Mon, 04/01/2013 - 17:25
Classification algorithms used to support the decisions of human analysts are often used in settings in which zero-one loss is not the appropriate indication of performance. The zero-one loss corresponds to the operating point with equal costs for false alarms and missed detections, and no option for the classifier to leave uncertain test samples unlabeled. A generalization bound for ensemble classification at the standard operating point has been developed based on two interpretable properties of the ensemble: strength and correlation, using the Chebyshev inequality. Such generalization bounds for other operating points have not been developed previously, and are developed in this paper. Significantly, the bounds are empirically shown to have much practical utility in determining optimal parameters for classification with a reject option, classification for ultra-low probability of false alarm, and classification for ultra-low probability of missed detection. Counter to the usual guideline of large strength and small correlation in the ensemble, different guidelines are recommended by the derived bounds in the ultra-low false alarm and missed detection probability regimes.

PrePrint: Crowdsourced Trace Similarity with Smartphones

TKDE - Mon, 04/01/2013 - 17:25
Smartphones are nowadays equipped with a number of sensors, such as WiFi, GPS, accelerometers, etc. This capability allows smartphone users to easily engage in crowdsourced computing services, which contribute to the solution of complex problems in a distributed manner. In this work, we leverage such a computing paradigm to solve efficiently the following problem: comparing a query trace Q against a crowd of traces generated and stored on distributed smartphones. Our proposed framework, coined SmartTrace+, provides an effective solution without disclosing any part of the crowd traces to the query processor. SmartTrace+, relies on an in-situ data storage model and intelligent top-K query processing algorithms that exploit distributed trajectory similarity measures, resilient to spatial and temporal noise, in order to derive the most relevant answers to Q. We evaluate our algorithms on both synthetic and real workloads. We describe our prototype system developed on the Android OS. The solution is deployed over our own SmartLab testbed of 25 smartphones. Our study reveals that computations over SmartTrace+ result in substantial energy conservation; in addition, results can be computed faster than competitive approaches.

PrePrint: Improving Word Similarity by Augmenting PMI with Estimates of Word Polysemy

TKDE - Mon, 04/01/2013 - 17:25
Pointwise mutual information (PMI) is a widely used word similarity measure, but it lacks a clear explanation of how it works. We explore how PMI differs from distributional similarity, and we introduce a novel metric, PMI_max, that augments PMI with information about a word's number of senses. The coefficients of PMI_max are determined empirically by maximizing a utility function based on the performance of automatic thesaurus generation. We show that it outperforms traditional PMI in the application of automatic thesaurus generation and in two word similarity benchmark tasks: human similarity ratings and TOEFL synonym questions. PMI_max achieves a correlation coefficient comparable to the best knowledge-based approaches on the Miller-Charles similarity rating dataset.

PrePrint: Symmetric Fast Marching Schemes for Better Numerical Isotropy

TPAMI - Sun, 03/31/2013 - 18:59
Existing Fast Marching methods solve the Eikonal equation using a continuous (first order) model to estimate the accumulated cost, but a discontinuous (zero order) model for the traveling cost at each grid point. As a result the estimate of the accumulated cost (calculated numerically) at a given point will vary based on the direction of the arriving front, introducing an anisotropy into the discrete algorithm even though the continuous PDE is itself isotropic. To remove this anisotropy, we propose two very different schemes. In the first model we utilize a continuous interpolation of the traveling cost, which is not biased by the direction of the propagating front. In the second model we upsample the traveling cost on a higher resolution grid to overcome the directional bias. We show the significance of removing the directional bias in the computation of the cost in some applications of fast marching method, demonstrating that both methods make the discrete implementation more isotropic in accordance with the underlying continuous PDE. We also compare the accuracy and computation time of our proposed methods with the existing state of the art fast marching techniques to demonstrate the superiority of our method.

PrePrint: Multi-View Face Detection and Registration Requiring Minimal Manual Intervention

TPAMI - Sun, 03/31/2013 - 18:59
Most face recognition systems require faces to be detected and localized a priori. In this paper, an approach to simultaneously detect and localize multiple faces having arbitrary views and different scales is proposed. The main contribution of this paper is the introduction of a face constellation, which enables multi-view face detection and localization. In contrast to other multi-view approaches that require many manually labeled images for training, the proposed face constellation requires only a single reference image of a face containing two manually indicated reference points for initialization. Subsequent training face images from arbitrary views are automatically added to the constellation (registered to the reference image) based on finding the correspondences between distinctive local features. Thus, the key advantage of the proposed scheme is the minimal manual intervention required to train the face constellation. We also propose an approach to identify distinctive correspondence points between pairs of face images in the presence of a large amount of false matches. To detect and localize multiple faces with arbitrary views, we then propose a probabilistic classifier based formulation to evaluate whether a local feature cluster corresponds to a face.

PrePrint: Stereo Seam Carving A Geometrically Consistent Approach

TPAMI - Sun, 03/31/2013 - 18:59
Image retargeting algorithms attempt to adapt the image content to the screen without distorting the important objects in the scene. Existing methods address retargeting of a single image. In this paper we propose a novel method for retargeting a pair of stereo images. Naively retargeting each image independently will distort the geometric structure and hence will impair the perception of the 3D structure of the scene. We show how to extend a single image seam carving to work on a pair of images. Our method minimizes the visual distortion in each of the images as well as the depth distortion. A key property of the proposed method is that it takes into account the visibility relations between pixels in the image pair (occluded and occluding pixels). As a result, our method guarantees, as we formally prove, that the retargeted pair is geometrically consistent with a feasible 3D scene, similar to the original one. Hence, the retargeted stereo pair can be viewed on a stereoscopic display or further processed by any computer vision algorithm. We demonstrate our method on a number of challenging indoor and outdoor stereo images.

PrePrint: Multi-Exemplar Affinity Propagation

TPAMI - Sun, 03/31/2013 - 18:59
Affinity Propagation (AP) clustering algorithm has received much attention in the past few years. AP is appealing because it is efficient, insensitive to initialization, and it produces clusters at a lower error rate than other exemplar-based methods. However, its single-exemplar model becomes inadequate when applied to model multi-subclasses in some situations such as scene analysis and character recognition. To remedy this deficiency, we have extended the single-exemplar model to a multi-exemplar one to create a new Multi-Exemplar Affinity Propagation (MEAP) algorithm. This new model determines automatically the number of exemplars in each cluster associated with a super exemplar to approximate the subclasses in the category. Solving the model is NP-hard and we tackle it with the max-sum belief propagation to produce neighborhood maximum clusters, with no need to specify beforehand the number of clusters, multi-exemplars, and super-exemplars. Also, utilizing the sparsity in the data, we are able to reduce substantially the computational time and storage. Experimental studies have shown MEAP's significant improvements over other algorithms on unsupervised image categorization and the clustering of handwritten digits.

PrePrint: Learning AND-OR Templates for Object Recognition and Detection

TPAMI - Sun, 03/31/2013 - 18:59
This paper presents a framework for unsupervised learning of a hierarchical reconfigurable image template - the AND-OR Template (AOT) for visual objects. The AOT includes: (1) hierarchical composition as ''AND'' nodes, (2) deformation and articulation of parts as geometric "OR" nodes, and (3) multiple ways of composition as structural "OR" nodes. The terminal nodes are hybrid image templates (HIT) \cite{hit} that are fully generative to the pixels. We show that both the structures and parameters of the AOT model can be learned in an unsupervised way from images using an information projection principle. The learning algorithm consists of two steps: i) a recursive block pursuit procedure to learn the hierarchical dictionary of primitives, parts and objects, and ii) a graph compression procedure to minimize model structure for better generalizability. We investigate the factors that influence how well the learning algorithm can identify the underlying AOT. And we propose a number of ways to evaluate the performance of the learned AOTs through both synthesized examples and real world images. Our model advances the state-of-the-art for object detection by improving the accuracy of template matching.

PrePrint: Modeling Natural Images Using Gated MRFs

TPAMI - Sun, 03/31/2013 - 18:59
This paper describes a Markov Random Field for real-valued image modeling that has two sets of latent variables. One set is used to gate the interactions between all pairs of pixels while the second set determines the mean intensities of each pixel. This is a powerful model with a conditional distribution over the input that is Gaussian with both mean and covariance determined by the configuration of latent variables, which is unlike previous models that were restricted to use Gaussians with either a fixed mean or a diagonal covariance matrix. Thanks to the increased flexibility, this gated MRF can generate more realistic samples after training on an unconstrained distribution of high-resolution natural images. Furthermore, the latent variables of the model can be inferred efficiently and can be used as very effective descriptors in recognition tasks. Both generation and discrimination drastically improve as layers of binary latent variables are added to the model, yielding a hierarchical model called a Deep Belief Network.

PrePrint: Efficient Methods for Overlapping Group Lasso

TPAMI - Sun, 03/31/2013 - 18:59
The group Lasso is an extension of the Lasso for feature selection on (predefined) non-overlapping groups of features. The non-overlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation, where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. Our methods and theoretical results are then generalized to tackle the general overlapping group Lasso formulation based on the Lq norm. We further extend our algorithm to solve a non-convex overlapping group Lasso formulation based on the capped norm regularization, which reduces the estimation bias introduced by the convex penalty. Our empirical evaluations using both synthetic and real data demonstrate the efficiency of the proposed algorithm. Results also demonstrate the effectiveness of the non-convex formulation for overlapping group Lasso.

PrePrint: Range Image Registration using a Photometric Metric Under unknown Lighting

TPAMI - Sun, 03/31/2013 - 18:59
Based on the spherical harmonics representation of image formation, we derive a new photometric metric for evaluating the correctness of a given rigid transformation aligning two overlapping range images captured under unknown, distant and general illumination. We estimate the surrounding illumination and albedo values of points of the two range images from the point correspondences induced by the input transformation. We then synthesize the color of both range images using albedo values transferred using the point correspondences to compute the photometric re-projection error. This way allows us to accurately register two range images by finding the transformation that minimizes the photometric re-projection error. We also propose a practical method using the proposed photometric metric to register pairs of range images devoid of salient geometric features, captured under unknown lighting. Our method uses a hypothesize-and-test strategy to search for the transformation that minimizes our photometric metric. Transformation candidates are efficiently generated by employing the spherical representation of each range image. Experimental results using both synthetic and real data demonstrate the usefulness of the proposed metric.

PrePrint: Joint Histogram Based Cost Aggregation for Stereo Matching

TPAMI - Sun, 03/31/2013 - 18:59
This paper presents a novel method for performing efficient cost aggregation in stereo matching. The cost aggregation problem is re-formulated from a perspective of a histogram, giving us a potential to reduce the complexity of the cost aggregation in stereo matching significantly. Different from previous methods which have tried to reduce the complexity in terms of the size of an image and a matching window, our approach focuses on reducing the computational redundancy which exists among the search range, caused by a repeated filtering for all the hypotheses. Moreover, we also reduce the complexity of the window-based filtering through an efficient sampling scheme inside the matching window. The trade-off between accuracy and complexity is extensively investigated by varying the parameters used in the proposed method. Experimental results show that the proposed method provides high-quality disparity maps with a low complexity and outperforms existing local methods. This work also provides new insights into complexity-constrained stereo matching algorithm design.

PrePrint: Higher-Order Partial Least Squares (HOPLS): A Generalized Multi-Linear Regression Method

TPAMI - Sun, 03/31/2013 - 18:59
A new generalized multilinear regression model, termed the Higher-Order Partial Least Squares (HOPLS), is introduced with the aim to predict a tensor (multiway array) <b><u>Y</u></b> from a tensor <b><u>X</u></b> through projecting the data onto the latent space and performing regression on the corresponding latent variables. HOPLS differs substantially from other regression models in that it explains the data by a sum of orthogonal Tucker tensors, while the number of orthogonal loadings serves as a parameter to control model complexity and prevent overfitting. The low dimensional latent space is optimized sequentially via a deflation operation, yielding the best joint subspace approximation for both <b><u>X</u></b> and <b><u>Y</u></b>. Instead of decomposing <b><u>X</u></b> and <b><u>Y</u></b> individually, higher order singular value decomposition on a newly defined generalized cross-covariance tensor is employed to optimize the orthogonal loadings. A systematic comparison on both synthetic data and real-world decoding of 3D movement trajectories from electrocorticogram (ECoG) signals demonstrate the advantages of HOPLS over the existing methods in terms of better predictive ability, suitability to handle small sample sizes, and robustness to noise.

PrePrint: A Branch and Bound Approach to Correspondence and Grouping Problems

TPAMI - Sun, 03/31/2013 - 18:59
Data correspondence/grouping is a fundamental topic in computer vision. Finding feature correspondences is probably the most popular application of this topic and constitutes our main motivation. It is a key ingredient for various tasks including 3D reconstruction and object recognition. Existing feature correspondence methods are based on either local appearance similarity, or global geometric consistency, or a combination of both in some heuristic manner. None of these methods is fully satisfactory, especially with repetitive image textures or mis-matches. In this paper, we present a new algorithm that combines the benefits of both appearance-based and geometry-based methods, and mathematically guarantees a global optimization. Our algorithm accepts the two sets of features as input, and outputs the largest set of feature correspondences verifying both the appearance and geometric constraints. We formulate the problem as a mixed integer program, and solve it efficiently by a series of linear programs via branch-and-bound. We subsequently generalize our framework in the context of data correspondence/grouping under an unknown parametric model and show it can be applied to certain classes of computer vision problems. Our algorithm has been validated successfully on synthesized data and challenging real images.

PrePrint: Hierarchical Object Parsing from Structured Noisy Point Clouds

TPAMI - Sun, 03/31/2013 - 18:59
Object parsing and segmentation from point clouds are challenging tasks because the relevant data is available only as thin structures along object boundaries or other features, and is corrupted by large amounts of noise. To handle this kind of data, flexible shape models are desired that can accurately follow the object boundaries. Popular models such as Active Shape and Active Appearance models lack the necessary flexibility for this task, while recent approaches such as the Recursive Compositional Models make model simplifications in order to obtain computational guarantees. This paper investigates a hierarchical Bayesian model of shape and appearance in a generative setting. The input data is explained by an object parsing layer, which is a deformation of a hidden PCA shape model with Gaussian prior. The paper also introduces a novel efficient inference algorithm that uses informed data-driven proposals to initialize local searches for the hidden variables. Applied to the problem of object parsing from structured point clouds such as edge detection images, the proposed approach obtains state of the art parsing errors on two standard datasets without using any intensity information.

PrePrint: Calibration of Smooth Camera Models

TPAMI - Sun, 03/31/2013 - 18:59
Generic imaging models can be used to represent any camera. Current generic models are discrete and define a mapping between each pixel in the image and a straight line in 3D space. This paper presents a modification of the generic camera model that allows the simplification of the calibration procedure. The only requirement is that the coordinates of the 3D projecting lines are related by functions that vary smoothly across space. Such model is obtained by modifying the general imaging model using radial basis functions to interpolate image coordinates and 3D lines, thereby allowing both an increase in resolution (due to their continuous nature) and a more compact representation. Using this variation of the general imaging model we also develop a calibration procedure. This procedure only requires that a 3D point be matched to each pixel. In addition not all the pixels need to be calibrated. As a result the complexity of the procedure is significantly decreased. Normalization is applied to the coordinates of both image and 3D points which increases the accuracy of the calibration. Results with both synthetic and real data sets show that the model and calibration procedure are easily applicable and provide accurate calibration results.

PrePrint: Clustering Dynamic Textures with the Hierarchical EM Algorithm for Modeling Video

TPAMI - Sun, 03/31/2013 - 18:59
The dynamic texture (DT) is a probabilistic generative model, defined over space and time, that represents a video as the output of a linear dynamical system (LDS). The DT model has been applied to a wide variety of computer vision problems, such as motion segmentation, motion classification, and video registration. In this paper, we derive a new algorithm for clustering DT models that is based on the hierarchical EM algorithm. The proposed clustering algorithm is capable of both clustering DTs and learning novel DT cluster centers that are representative of the cluster members, in a manner that is consistent with the underlying generative probabilistic model of the DT. We also derive an efficient recursive algorithm for sensitivity analysis of the discrete-time Kalman smoothing filter, which is used as the basis for computing expectations in the E-step of the HEM algorithm. Finally, we demonstrate the efficacy of the clustering algorithm on several applications in motion analysis, including hierarchical motion clustering, semantic motion annotation, and learning bag-of-systems codebooks for dynamic texture recognition.

PrePrint: Image-Based Separation of Reflective and Fluorescent Components using Illumination Variant and Invariant Color

TPAMI - Sun, 03/31/2013 - 18:59
Traditionally researchers tend to exclude fluorescence from color appearance algorithms in computer vision and image processing because of its complexity. In reality, fluorescence is a very common phenomenon observed in many objects, from gems and corals, to different kinds of writing paper, and to our clothes. In this paper, we provide detailed theories of fluorescence phenomenon. In particular, we show that the color appearance of fluorescence is unaffected by illumination in which it differs from ordinary reflectance. Moreover, we show that the color appearance of objects with reflective and fluorescent components can be represented as a linear combination of the two components. A linear model allows us to separate the two components using images taken under unknown illuminants using independent component analysis(ICA). The effectiveness of the proposed method is demonstrated using digital images of various fluorescent objects.

PrePrint: Keeping a Pan-Tilt-Zoom Camera Calibrated

TPAMI - Sun, 03/31/2013 - 18:59
Pan-tilt-zoom (PTZ) cameras are pervasive in modern surveillance systems. However, we demonstrate that the (pan, tilt) coordinates reported by PTZ cameras become inaccurate after many hours of operation, endangering tracking and 3D localization algorithms that rely on the accuracy of such values. To solve this problem, we propose a complete model for a pan-tilt-zoom camera that explicitly reflects how focal length and lens distortion vary as a function of zoom scale. We show how the parameters of this model can be quickly and accurately estimated using a series of simple initialization steps followed by a nonlinear optimization. Our method requires only ten images to achieve accurate calibration results. Next, we show how the calibration parameters can be maintained using a one-shot dynamic correction process; this ensures that the camera returns the same field of view every time the user requests a given (pan, tilt, zoom), even after hundreds of hours of operation. The dynamic calibration algorithm is based on matching the current image against a stored feature library created at the time the PTZ camera is mounted. We evaluate the calibration and dynamic correction algorithms on both experimental and real-world datasets, demonstrating the effectiveness of the techniques.

PrePrint: Paired Regions for Shadow Detection and Removal

TPAMI - Sun, 03/31/2013 - 18:59
In this paper, we address the problem of shadow detection and removal from single images of natural scenes. Different from traditional methods that explore pixel or edge information, we employ a region based approach. In addition to considering individual regions separately, we predict relative illumination conditions between segmented regions from their appearances and perform pairwise classification based on such information. Classification results are used to build a graph of segments and graph-cut is used to solve the labeling of shadow and non-shadow regions. Detection results are later refined by image matting, and the shadow free image is recovered by relighting each pixel based on our lighting model. We evaluate our method on the shadow detection dataset in [1]. In addition, we created a new dataset with shadow-free ground truth images, which provides a quantitative basis for evaluating shadow removal. We study the effectiveness of features for both unary and pairwise classification.


Powered by Drupal, an open source content management system