MRF energy minimization and beyond via dual decomposition

Mechanical cloak via data-driven aperiodic metamaterial design

An invisibility cloak to conceal objects from an outside observer has long been a subject of interest in metamaterial design. While cloaks have been manufactured for optical, thermal, and electric fields, limited progress has been made for mechanical cloaks. Most existing designs rely on mapping-based methods, which have so far been limited to special base cells and a narrow selection of voids with simple shapes. In this study, we develop a fundamentally different approach by exploiting data-driven designs to offer timely, customized solutions to mechanical cloaking that were previously difficult to obtain. Through simulations and experimental validations, we show that excellent cloaking performance can be achieved for various boundary conditions, shapes of voids, base cells, and even multiple voids.

Mechanical cloaks are materials engineered to manipulate the elastic response around objects to make them indistinguishable from their homogeneous surroundings. Typically, methods based on material-parameter transformations are used to design optical, thermal, and electric cloaks. However, they are not applicable in designing mechanical cloaks, since continuum-mechanics equations are not form invariant under general coordinate transformations. As a result, existing design methods for mechanical cloaks have so far been limited to a narrow selection of voids with simple shapes. To address this challenge, we present a systematic, data-driven design approach to create mechanical cloaks composed of aperiodic metamaterials using a large precomputed unit cell database. Our method is flexible to allow the design of cloaks with various boundary conditions, multiple loadings, different shapes and numbers of voids, and different homogeneous surroundings. It enables a concurrent optimization of both topology and properties distribution of the cloak. Compared to conventional fixed-shape solutions, this results in an overall better cloaking performance and offers unparalleled versatility. Experimental measurements on additively manufactured structures further confirm the validity of the proposed approach. Our research illustrates the benefits of data-driven approaches in quickly responding to new design scenarios and resolving the computational challenge associated with multiscale designs of functional structures. It could be generalized to accommodate other applications that require heterogeneous property distribution, such as soft robots and implants design.

Memory Efficient Max Flow for Multi-Label Submodular MRFs

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable X_i is represented by l nodes (where l is the number of labels) arranged in a column. However, this method in general requires 2 l² edges for each pair of neighbouring variables. This makes it inapplicable to realistic problems with many variables and labels, due to excessive memory requirement. In this paper, we introduce a variant of the max-flow algorithm that requires much less storage. Consequently, our algorithm makes it possible to optimally solve multi-label submodular problems involving large numbers of variables and labels on a standard computer.

Efficient Message Passing Methods With Fully Connected Models for Early Vision

Fully connected Markov random fields and conditional random fields have recently been shown to be advantageous in many early vision tasks being formulated as multi-labeling problems, such as stereo matching and image segmentation. The maximum posterior marginal (MPM) inference method in solving fully connected models uses a hybrid framework of mean-field (MF) method and a filtering like approach, and yields excellent results. In this paper, we extend this framework in several aspects. First, we provide an alternative inference method employing fractional belief propagation based method instead of MF. Second, we reformulate the MPM problem into a maximum a posterior (MAP) problem and provide efficient algorithms for solving this. Third, we extend the fully connected model into a multi-resolution approach. Finally, we propose an integral image based approach which makes it possible for efficiently integrating the local linear regression technique into this framework. Comparisons are carried out among different algorithms and different formulations to find the best combination. We demonstrate that the use of our multi-resolution approach with MAP formulation substantially outperforms the ordinary MF-based inference scheme.

A generative vision model that trains with high data efficiency and breaks text-based CAPTCHAs

Learning from a few examples and generalizing to markedly different situations are capabilities of human visual intelligence that are yet to be matched by leading machine learning models. By drawing inspiration from systems neuroscience, we introduce a probabilistic generative model for vision in which message-passing-based inference handles recognition, segmentation, and reasoning in a unified way. The model demonstrates excellent generalization and occlusion-reasoning capabilities and outperforms deep neural networks on a challenging scene text recognition benchmark while being 300-fold more data efficient. In addition, the model fundamentally breaks the defense of modern text-based CAPTCHAs (Completely Automated Public Turing test to tell Computers and Humans Apart) by generatively segmenting characters without CAPTCHA-specific heuristics. Our model emphasizes aspects such as data efficiency and compositionality that may be important in the path toward general artificial intelligence.

Fast Unsupervised Bayesian Image Segmentation With Adaptive Spatial Regularisation

This paper presents a new Bayesian estimation technique for hidden Potts-Markov random fields with unknown regularisation parameters, with application to fast unsupervised K -class image segmentation. The technique is derived by first removing the regularisation parameter from the Bayesian model by marginalisation, followed by a small-variance-asymptotic (SVA) analysis in which the spatial regularisation and the integer-constrained terms of the Potts model are decoupled. The evaluation of this SVA Bayesian estimator is then relaxed into a problem that can be computed efficiently by iteratively solving a convex total-variation denoising problem and a least-squares clustering ( K -means) problem, both of which can be solved straightforwardly, even in high-dimensions, and with parallel computing techniques. This leads to a fast fully unsupervised Bayesian image segmentation methodology in which the strength of the spatial regularisation is adapted automatically to the observed image during the inference procedure, and that can be easily applied in large 2D and 3D scenarios or in applications requiring low computing times. Experimental results on synthetic and real images, as well as extensive comparisons with state-of-the-art algorithms, confirm that the proposed methodology offer extremely fast convergence and produces accurate segmentation results, with the important additional advantage of self-adjusting regularisation parameters.

Organ Location Determination and Contour Sparse Representation for Multiorgan Segmentation

Organ segmentation on computed tomography (CT) images is of great importance in medical diagnoses and treatment. This paper proposes organ location determination and contour sparse representation methods (OLD-CSR) for multiorgan segmentation (liver, kidney, and spleen) on abdomen CT images using an extreme learning machine classifier. First, a location determination method is designed to obtain location information of each organ, which is used for coarse segmentation. Second, for coarse-to-fine segmentation, a contour gradient and rate change based feature point extraction method is proposed. A sparse optimization model is developed for refining the contour feature points. Experimentations with 153 CT images demonstrate the performance advantages of OLD-CSR as compared with related work.

ORGM: Occlusion Relational Graphical Model for Human Pose Estimation

Articulated human pose estimation from monocular image is a challenging problem in computer vision. Occlusion is a main challenge for human pose estimation, which is largely ignored in popular tree structured models. The tree structured model is simple and convenient for exact inference, but short in modeling the occlusion coherence especially in the case of self-occlusion. We propose an occlusion relational graphical model, which is able to model both self-occlusion and occlusion by the other objects simultaneously. The proposed model can encode the interactions between human body parts and objects, and enables it to learn occlusion coherence from data discriminatively. We evaluate our model on several public benchmarks for human pose estimation, including challenging subsets featuring significant occlusion. The experimental results show that our method is superior to the previous state-of-the-arts, and is robust to occlusion for 2D human pose estimation.

Accurate Cervical Cell Segmentation from Overlapping Clumps in Pap Smear Images

Accurate segmentation of cervical cells in Pap smear images is an important step in automatic pre-cancer identification in the uterine cervix. One of the major segmentation challenges is overlapping of cytoplasm, which has not been well-addressed in previous studies. To tackle the overlapping issue, this paper proposes a learning-based method with robust shape priors to segment individual cell in Pap smear images to support automatic monitoring of changes in cells, which is a vital prerequisite of early detection of cervical cancer. We define this splitting problem as a discrete labeling task for multiple cells with a suitable cost function. The labeling results are then fed into our dynamic multi-template deformation model for further boundary refinement. Multi-scale deep convolutional networks are adopted to learn the diverse cell appearance features. We also incorporated high-level shape information to guide segmentation where cell boundary might be weak or lost due to cell overlapping. An evaluation carried out using two different datasets demonstrates the superiority of our proposed method over the state-of-the-art methods in terms of segmentation accuracy.

Postoperative 3D spine reconstruction by navigating partitioning manifolds

PURPOSE

The postoperative evaluation of scoliosis patients undergoing corrective treatment is an important task to assess the strategy of the spinal surgery. Using accurate 3D geometric models of the patient's spine is essential to measure longitudinal changes in the patient's anatomy. On the other hand, reconstructing the spine in 3D from postoperative radiographs is a challenging problem due to the presence of instrumentation (metallic rods and screws) occluding vertebrae on the spine.

METHODS

This paper describes the reconstruction problem by searching for the optimal model within a manifold space of articulated spines learned from a training dataset of pathological cases who underwent surgery. The manifold structure is implemented based on a multilevel manifold ensemble to structure the data, incorporating connections between nodes within a single manifold, in addition to connections between different multilevel manifolds, representing subregions with similar characteristics.

RESULTS

The reconstruction pipeline was evaluated on x-ray datasets from both preoperative patients and patients with spinal surgery. By comparing the method to ground-truth models, a 3D reconstruction accuracy of 2.24 ± 0.90 mm was obtained from 30 postoperative scoliotic patients, while handling patients with highly deformed spines.

CONCLUSIONS

This paper illustrates how this manifold model can accurately identify similar spine models by navigating in the low-dimensional space, as well as computing nonlinear charts within local neighborhoods of the embedded space during the testing phase. This technique allows postoperative follow-ups of spinal surgery using personalized 3D spine models and assess surgical strategies for spinal deformities.

Higher-Order Graph Principles towards Non-Rigid Surface Registration

This paper casts surface registration as the problem of finding a set of discrete correspondences through the minimization of an energy function, which is composed of geometric and appearance matching costs, as well as higher-order deformation priors. Two higher-order graph-based formulations are proposed under different deformation assumptions. The first formulation encodes isometric deformations using conformal geometry in a higher-order graph matching problem, which is solved through dual-decomposition and is able to handle partial matching. Despite the isometry assumption, this approach is able to robustly match sparse feature point sets on surfaces undergoing highly anisometric deformations. Nevertheless, its performance degrades significantly when addressing anisometric registration for a set of densely sampled points. This issue is rigorously addressed subsequently through a novel deformation model that is able to handle arbitrary diffeomorphisms between two surfaces. Such a deformation model is introduced into a higher-order Markov Random Field for dense surface registration, and is inferred using a new parallel and memory efficient algorithm. To deal with the prohibitive search space, we also design an efficient way to select a number of matching candidates for each point of the source surface based on the matching results of a sparse set of points. A series of experiments demonstrate the accuracy and the efficiency of the proposed framework, notably in challenging cases of large and/or anisometric deformations, or surfaces that are partially occluded.

Human Pose Estimation from Monocular Images: A Comprehensive Survey

Human pose estimation refers to the estimation of the location of body parts and how they are connected in an image. Human pose estimation from monocular images has wide applications (e.g., image indexing). Several surveys on human pose estimation can be found in the literature, but they focus on a certain category; for example, model-based approaches or human motion analysis, etc. As far as we know, an overall review of this problem domain has yet to be provided. Furthermore, recent advancements based on deep learning have brought novel algorithms for this problem. In this paper, a comprehensive survey of human pose estimation from monocular images is carried out including milestone works and recent advancements. Based on one standard pipeline for the solution of computer vision problems, this survey splits the problem into several modules: feature extraction and description, human body models, and modeling methods. Problem modeling methods are approached based on two means of categorization in this survey. One way to categorize includes top-down and bottom-up methods, and another way includes generative and discriminative methods. Considering the fact that one direct application of human pose estimation is to provide initialization for automatic video surveillance, there are additional sections for motion-related methods in all modules: motion features, motion models, and motion-based methods. Finally, the paper also collects 26 publicly available data sets for validation and provides error measurement methods that are frequently used.

Simultaneous gene finding in multiple genomes

MOTIVATION

As the tree of life is populated with sequenced genomes ever more densely, the new challenge is the accurate and consistent annotation of entire clades of genomes. We address this problem with a new approach to comparative gene finding that takes a multiple genome alignment of closely related species and simultaneously predicts the location and structure of protein-coding genes in all input genomes, thereby exploiting negative selection and sequence conservation. The model prefers potential gene structures in the different genomes that are in agreement with each other, or-if not-where the exon gains and losses are plausible given the species tree. We formulate the multi-species gene finding problem as a binary labeling problem on a graph. The resulting optimization problem is NP hard, but can be efficiently approximated using a subgradient-based dual decomposition approach.

RESULTS

The proposed method was tested on whole-genome alignments of 12 vertebrate and 12 Drosophila species. The accuracy was evaluated for human, mouse and Drosophila melanogaster and compared to competing methods. Results suggest that our method is well-suited for annotation of (a large number of) genomes of closely related species within a clade, in particular, when RNA-Seq data are available for many of the genomes. The transfer of existing annotations from one genome to another via the genome alignment is more accurate than previous approaches that are based on protein-spliced alignments, when the genomes are at close to medium distances.

AVAILABILITY AND IMPLEMENTATION

The method is implemented in C ++ as part of Augustus and available open source at http://bioinf.uni-greifswald.de/augustus/ CONTACT: stefaniekoenig@ymail.com or mario.stanke@uni-greifswald.deSupplementary information: Supplementary data are available at Bioinformatics online.

Partial Optimality by Pruning for MAP-Inference with General Graphical Models

We consider the energy minimization problem for undirected graphical models, also known as MAP-inference problem for Markov random fields which is NP-hard in general. We propose a novel polynomial time algorithm to obtain a part of its optimal non-relaxed integral solution. Our algorithm is initialized with variables taking integral values in the solution of a convex relaxation of the MAP-inference problem and iteratively prunes those, which do not satisfy our criterion for partial optimality. We show that our pruning strategy is in a certain sense theoretically optimal. Also empirically our method outperforms previous approaches in terms of the number of persistently labelled variables. The method is very general, as it is applicable to models with arbitrary factors of an arbitrary order and can employ any solver for the considered relaxed problem. Our method's runtime is determined by the runtime of the convex relaxation solver for the MAP-inference problem.

Transfer Learning to Infer Social Ties across Heterogeneous Networks

Interpersonal ties are responsible for the structure of social networks and the transmission of information through these networks. Different types of social ties have essentially different influences on people. Awareness of the types of social ties can benefit many applications, such as recommendation and community detection. For example, our close friends tend to move in the same circles that we do, while our classmates may be distributed into different communities. Though a bulk of research has focused on inferring particular types of relationships in a specific social network, few publications systematically study the generalization of the problem of predicting social ties across multiple heterogeneous networks.

In this work, we develop a framework referred to as TranFG for classifying the type of social relationships by learning across heterogeneous networks. The framework incorporates social theories into a factor graph model, which effectively improves the accuracy of predicting the types of social relationships in a target network by borrowing knowledge from a different source network. We also present several active learning strategies to further enhance the inferring performance. To scale up the model to handle really large networks, we design a distributed learning algorithm for the proposed model.

We evaluate the proposed framework (TranFG) on six different networks and compare with several existing methods. TranFG clearly outperforms the existing methods on multiple metrics. For example, by leveraging information from a coauthor network with labeled advisor-advisee relationships, TranFG is able to obtain an F1-score of 90% (8%--28% improvements over alternative methods) for predicting manager-subordinate relationships in an enterprise email network. The proposed model is efficient. It takes only a few minutes to train the proposed transfer model on large networks containing tens of thousands of nodes.

Scale and Rotation Invariant Matching Using Linearly Augmented Trees

We propose a novel linearly augmented tree method for efficient scale and rotation invariant object matching. The proposed method enforces pairwise matching consistency defined on trees, and high-order constraints on all the sites of a template. The pairwise constraints admit arbitrary metrics while the high-order constraints use L1 norms and therefore can be linearized. Such a linearly augmented tree formulation introduces hyperedges and loops into the basic tree structure. But, different from a general loopy graph, its special structure allows us to relax and decompose the optimization into a sequence of tree matching problems that are efficiently solvable by dynamic programming. The proposed method also works on continuous scale and rotation parameters; we can match with a scale up to any large value with the same efficiency. Our experiments on ground truth data and a variety of real images and videos show that the proposed method is efficient, accurate and reliable.

Distribution Matching with the Bhattacharyya Similarity: A Bound Optimization Framework

We present efficient graph cut algorithms for three problems: (1) finding a region in an image, so that the histogram (or distribution) of an image feature within the region most closely matches a given model; (2) co-segmentation of image pairs and (3) interactive image segmentation with a user-provided bounding box. Each algorithm seeks the optimum of a global cost function based on the Bhattacharyya measure, a convenient alternative to other matching measures such as the Kullback-Leibler divergence. Our functionals are not directly amenable to graph cut optimization as they contain non-linear functions of fractional terms, which make the ensuing optimization problems challenging. We first derive a family of parametric bounds of the Bhattacharyya measure by introducing an auxiliary labeling. Then, we show that these bounds are auxiliary functions of the Bhattacharyya measure, a result which allows us to solve each problem efficiently via graph cuts. We show that the proposed optimization procedures converge within very few graph cut iterations. Comprehensive and various experiments, including quantitative and comparative evaluations over two databases, demonstrate the advantages of the proposed algorithms over related works in regard to optimality, computational load, accuracy and flexibility.

Metastatic liver tumour segmentation from discriminant Grassmannian manifolds

The early detection, diagnosis and monitoring of liver cancer progression can be achieved with the precise delineation of metastatic tumours. However, accurate automated segmentation remains challenging due to the presence of noise, inhomogeneity and the high appearance variability of malignant tissue. In this paper, we propose an unsupervised metastatic liver tumour segmentation framework using a machine learning approach based on discriminant Grassmannian manifolds which learns the appearance of tumours with respect to normal tissue. First, the framework learns within-class and between-class similarity distributions from a training set of images to discover the optimal manifold discrimination between normal and pathological tissue in the liver. Second, a conditional optimisation scheme computes non-local pairwise as well as pattern-based clique potentials from the manifold subspace to recognise regions with similar labelings and to incorporate global consistency in the segmentation process. The proposed framework was validated on a clinical database of 43 CT images from patients with metastatic liver cancer. Compared to state-of-the-art methods, our method achieves a better performance on two separate datasets of metastatic liver tumours from different clinical sites, yielding an overall mean Dice similarity coefficient of [Formula: see text] in over 50 tumours with an average volume of 27.3 mm(3).

An efficient conditional random field approach for automatic and interactive neuron segmentation

We present a new graphical-model-based method for automatic and interactive segmentation of neuron structures from electron microscopy (EM) images. For automated reconstruction, our learning based model selects a collection of nodes from a hierarchical merging tree as the proposed segmentation. More specifically, this is achieved by training a conditional random field (CRF) whose underlying graph is the watershed merging tree. The maximum a posteriori (MAP) prediction of the CRF is the output segmentation. Our results are comparable to the results of state-of-the-art methods. Furthermore, both the inference and the training are very efficient as the graph is tree-structured. The problem of neuron segmentation requires extremely high segmentation quality. Therefore, proofreading, namely, interactively correcting mistakes of the automatic method, is a necessary module in the pipeline. Based on our efficient tree-structured inference algorithm, we develop an interactive segmentation framework which only selects locations where the model is uncertain for a user to proofread. The uncertainty is measured by the marginals of the graphical model. Only giving a limited number of choices makes the user interaction very efficient. Based on user corrections, our framework modifies the merging tree and thus improves the segmentation globally.

Generalized Flows for Optimal Inference in Higher Order MRF-MAP

Use of higher order clique potentials in MRF-MAP problems has been limited primarily because of the inefficiencies of the existing algorithmic schemes. We propose a new combinatorial algorithm for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials. The algorithm runs in time O(2(k)n(3)) in the worst case (k is size of clique and n is the number of pixels). A special gadget is introduced to model flows in a higher order clique and a technique for building a flow graph is specified. Based on the primal dual structure of the optimization problem, the notions of the capacity of an edge and a cut are generalized to define a flow problem. We show that in this flow graph, when the clique potentials are submodular, the max flow is equal to the min cut, which also is the optimal solution to the problem. We show experimentally that our algorithm provides significantly better solutions in practice and is hundreds of times faster than solution schemes like Dual Decomposition [1], TRWS [2] and Reduction [3], [4], [5]. The framework represents a significant advance in handling higher order problems making optimal inference practical for medium sized cliques.

A Framework for Efficient Structured Max-Margin Learning of High-Order MRF Models

We present a very general algorithm for structured prediction learning that is able to efficiently handle discrete MRFs/CRFs (including both pairwise and higher-order models) so long as they can admit a decomposition into tractable subproblems. At its core, it relies on a dual decomposition principle that has been recently employed in the task of MRF optimization. By properly combining such an approach with a max-margin learning method, the proposed framework manages to reduce the training of a complex high-order MRF to the parallel training of a series of simple slave MRFs that are much easier to handle. This leads to a very efficient and general learning scheme that relies on solid mathematical principles. We thoroughly analyze its theoretical properties, and also show that it can yield learning algorithms of increasing accuracy since it naturally allows a hierarchy of convex relaxations to be used for loss-augmented MAP-MRF inference within a max-margin learning approach. Furthermore, it can be easily adapted to take advantage of the special structure that may be present in a given class of MRFs. We demonstrate the generality and flexibility of our approach by testing it on a variety of scenarios, including training of pairwise and higher-order MRFs, training by using different types of regularizers and/or different types of dissimilarity loss functions, as well as by learning of appropriate models for a variety of vision tasks (including high-order models for compact pose-invariant shape priors, knowledge-based segmentation, image denoising, stereo matching as well as high-order Potts MRFs).

Submodular Relaxation for Inference in Markov Random Fields

In this paper we address the problem of finding the most probable state of a discrete Markov random field (MRF), also known as the MRF energy minimization problem. The task is known to be NP-hard in general and its practical importance motivates numerous approximate algorithms. We propose a submodular relaxation approach (SMR) based on a Lagrangian relaxation of the initial problem. Unlike the dual decomposition approach of Komodakis et al. [29] SMR does not decompose the graph structure of the initial problem but constructs a submodular energy that is minimized within the Lagrangian relaxation. Our approach is applicable to both pairwise and high-order MRFs and allows to take into account global potentials of certain types. We study theoretical properties of the proposed approach and evaluate it experimentally.

Marginal Consistency: Upper-Bounding Partition Functions over Commutative Semirings

Many inference tasks in pattern recognition and artificial intelligence lead to partition functions in which addition and multiplication are abstract binary operations forming a commutative semiring. By generalizing max-sum diffusion (one of convergent message passing algorithms for approximate MAP inference in graphical models), we propose an iterative algorithm to upper bound such partition functions over commutative semirings. The iteration of the algorithm is remarkably simple: change any two factors of the partition function such that their product remains the same and their overlapping marginals become equal. In many commutative semirings, repeating this iteration for different pairs of factors converges to a fixed point when the overlapping marginals of every pair of factors coincide. We call this state marginal consistency. During that, an upper bound on the partition function monotonically decreases. This abstract algorithm unifies several existing algorithms, including max-sum diffusion and basic constraint propagation (or local consistency) algorithms in constraint programming. We further construct a hierarchy of marginal consistencies of increasingly higher levels and show than any such level can be enforced by adding identity factors of higher arity (order). Finally, we discuss instances of the framework for several semirings, including the distributive lattice and the max-sum and sum-product semirings.

Universality of the Local Marginal Polytope

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

Simultaneous and consistent labeling of longitudinal dynamic developing cortical surfaces in infants

The human cerebral cortex develops extremely dynamically in the first 2years of life. Accurate and consistent parcellation of longitudinal dynamic cortical surfaces during this critical stage is essential to understand the early development of cortical structure and function in both normal and high-risk infant brains. However, directly applying the existing methods developed for the cross-sectional studies often generates longitudinally-inconsistent results, thus leading to inaccurate measurements of the cortex development. In this paper, we propose a new method for accurate, consistent, and simultaneous labeling of longitudinal cortical surfaces in the serial infant brain MR images. The proposed method is explicitly formulated as a minimization problem with an energy function that includes a data fitting term, a spatial smoothness term, and a temporal consistency term. Specifically, inspired by multi-atlas based label fusion, the data fitting term is designed to integrate the contributions from multi-atlas surfaces adaptively, according to the similarities of their local cortical folding with that of the subject cortical surface. The spatial smoothness term is then designed to adaptively encourage label smoothness based on the local cortical folding geometries, i.e., allowing label discontinuity at sulcal bottoms (which often are the boundaries of cytoarchitecturally and functionally distinct regions). The temporal consistency term is to adaptively encourage the label consistency among the temporally-corresponding vertices, based on their similarity of local cortical folding. Finally, the entire energy function is efficiently minimized by a graph cuts method. The proposed method has been applied to the parcellation of longitudinal cortical surfaces of 13 healthy infants, each with 6 serial MRI scans acquired at 0, 3, 6, 9, 12 and 18months of age. Qualitative and quantitative evaluations demonstrated both accuracy and longitudinal consistency of the proposed method. By using our method, for the first time, we reveal several hitherto unseen properties of the dynamic and regionally heterogeneous development of the cortical surface area in the first 18months of life.

Spine segmentation in medical images using manifold embeddings and higher-order MRFs

We introduce a novel approach for segmenting articulated spine shape models from medical images. A nonlinear low-dimensional manifold is created from a training set of mesh models to establish the patterns of global shape variations. Local appearance is captured from neighborhoods in the manifold once the overall representation converges. Inference with respect to the manifold and shape parameters is performed using a higher-order Markov random field (HOMRF). Singleton and pairwise potentials measure the support from the global data and shape coherence in manifold space respectively, while higher-order cliques encode geometrical modes of variation to segment each localized vertebra models. Generic feature functions learned from ground-truth data assigns costs to the higher-order terms. Optimization of the model parameters is achieved using efficient linear programming and duality. The resulting model is geometrically intuitive, captures the statistical distribution of the underlying manifold and respects image support. Clinical experiments demonstrated promising results in terms of spine segmentation. Quantitative comparison to expert identification yields an accuracy of 1.6 ± 0.6 mm for CT imaging and of 2.0 ± 0.8 mm for MR imaging, based on the localization of anatomical landmarks.

Deformable medical image registration: a survey

Deformable image registration is a fundamental task in medical image processing. Among its most important applications, one may cite: 1) multi-modality fusion, where information acquired by different imaging devices or protocols is fused to facilitate diagnosis and treatment planning; 2) longitudinal studies, where temporal structural or anatomical changes are investigated; and 3) population modeling and statistical atlases used to study normal anatomical variability. In this paper, we attempt to give an overview of deformable registration methods, putting emphasis on the most recent advances in the domain. Additional emphasis has been given to techniques applied to medical images. In order to study image registration methods in depth, their main components are identified and studied independently. The most recent techniques are presented in a systematic fashion. The contribution of this paper is to provide an extensive account of registration techniques in a systematic manner.

Optimizing nondecomposable loss functions in structured prediction

We develop an algorithm for structured prediction with nondecomposable performance measures. The algorithm learns parameters of Markov Random Fields (MRFs) and can be applied to multivariate performance measures. Examples include performance measures such as Fβ score (natural language processing), intersection over union (object category segmentation), Precision/Recall at k (search engines), and ROC area (binary classifiers). We attack this optimization problem by approximating the loss function with a piecewise linear function. The loss augmented inference forms a Quadratic Program (QP), which we solve using LP relaxation. We apply this approach to two tasks: object class-specific segmentation and human action retrieval from videos. We show significant improvement over baseline approaches that either use simple loss functions or simple scoring functions on the PASCAL VOC and H3D Segmentation datasets, and a nursing home action recognition dataset.

Predicting future morphological changes of lesions from radiotracer uptake in 18F-FDG-PET images

We introduce a novel computational framework to enable automated identification of texture and shape features of lesions on ¹⁸F-FDG-PET images through a graph-based image segmentation method. The proposed framework predicts future morphological changes of lesions with high accuracy. The presented methodology has several benefits over conventional qualitative and semi-quantitative methods, due to its fully quantitative nature and high accuracy in each step of (i) detection, (ii) segmentation, and (iii) feature extraction. To evaluate our proposed computational framework, thirty patients received 2 ¹⁸F-FDG-PET scans (60 scans total), at two different time points. Metastatic papillary renal cell carcinoma, cerebellar hemongioblastoma, non-small cell lung cancer, neurofibroma, lymphomatoid granulomatosis, lung neoplasm, neuroendocrine tumor, soft tissue thoracic mass, nonnecrotizing granulomatous inflammation, renal cell carcinoma with papillary and cystic features, diffuse large B-cell lymphoma, metastatic alveolar soft part sarcoma, and small cell lung cancer were included in this analysis. The radiotracer accumulation in patients' scans was automatically detected and segmented by the proposed segmentation algorithm. Delineated regions were used to extract shape and textural features, with the proposed adaptive feature extraction framework, as well as standardized uptake values (SUV) of uptake regions, to conduct a broad quantitative analysis. Evaluation of segmentation results indicates that our proposed segmentation algorithm has a mean dice similarity coefficient of 85.75±1.75%. We found that 28 of 68 extracted imaging features were correlated well with SUV_max (p<0.05), and some of the textural features (such as entropy and maximum probability) were superior in predicting morphological changes of radiotracer uptake regions longitudinally, compared to single intensity feature such as SUV_max. We also found that integrating textural features with SUV measurements significantly improves the prediction accuracy of morphological changes (Spearman correlation coefficient = 0.8715, p<2e-16).

Deformable medical image registration: setting the state of the art with discrete methods

This review introduces a novel deformable image registration paradigm that exploits Markov random field formulation and powerful discrete optimization algorithms. We express deformable registration as a minimal cost graph problem, where nodes correspond to the deformation grid, a node's connectivity corresponds to regularization constraints, and labels correspond to 3D deformations. To cope with both iconic and geometric (landmark-based) registration, we introduce two graphical models, one for each subproblem. The two graphs share interconnected variables, leading to a modular, powerful, and flexible formulation that can account for arbitrary image-matching criteria, various local deformation models, and regularization constraints. To cope with the corresponding optimization problem, we adopt two optimization strategies: a computationally efficient one and a tight relaxation alternative. Promising results demonstrate the potential of this approach. Discrete methods are an important new trend in medical image registration, as they provide several improvements over the more traditional continuous methods. This is illustrated with several key examples where the presented framework outperforms existing general-purpose registration methods in terms of both performance and computational complexity. Our methods become of particular interest in applications where computation time is a critical issue, as in intraoperative imaging, or where the huge variation in data demands complex and application-specific matching criteria, as in large-scale multimodal population studies. The proposed registration framework, along with a graphical interface and corresponding publications, is available for download for research purposes (for Windows and Linux platforms) from http://www.mrf-registration.net.