Annotating lots of 3D medical images for training segmentation models is time-consuming. The goal of weakly supervised semantic segmentation is to train segmentation models without using any ground truth segmentation masks. Our work addresses the case where only image-level categorical labels, indicating the presence or absence of a particular region of interest (such as tumours or lesions), are available. Most existing methods rely on class activation mapping (CAM). We propose a novel approach, ToNNO, which is based on the Tomographic reconstruction of a Neural Network's Output. Our technique extracts stacks of slices with different angles from the input 3D volume, feeds these slices to a 2D encoder, and applies the inverse Radon transform in order to reconstruct a 3D heatmap of the encoder's predictions. This generic method allows to perform dense prediction tasks on 3D volumes using any 2D image encoder. We apply it to weakly supervised medical image segmentation by training the 2D encoder to output high values for slices containing the regions of interest. We test it on four large scale medical image datasets and outperform 2D CAM methods. We then extend ToNNO by combining tomographic reconstruction with CAM methods, proposing Averaged CAM and Tomographic CAM, which obtain even better results.

Challenges drive the state-of-the-art of automated medical image analysis. The quantity of public training data that they provide can limit the performance of their solutions. Public access to the training methodology for these solutions remains absent. This study implements the Type Three (T3) challenge format, which allows for training solutions on private data and guarantees reusable training methodologies. With T3, challenge organizers train a codebase provided by the participants on sequestered training data. T3 was implemented in the STOIC2021 challenge, with the goal of predicting from a computed tomography (CT) scan whether subjects had a severe COVID-19 infection, defined as intubation or death within one month. STOIC2021 consisted of a Qualification phase, where participants developed challenge solutions using 2000 publicly available CT scans, and a Final phase, where participants submitted their training methodologies with which solutions were trained on CT scans of 9724 subjects. The organizers successfully trained six of the eight Final phase submissions. The submitted codebases for training and running inference were released publicly. The winning solution obtained an area under the receiver operating characteristic curve for discerning between severe and non-severe COVID-19 of 0.815. The Final phase solutions of all finalists improved upon their Qualification phase solutions.

Exploring and identifying a good feature representation to describe high-dimensional datasets is a challenge of prime importance. However, plenty of feature selection techniques and distance metrics exist, which entails an intricacy for identifying the one best suited to the task. This paper provides an algorithm to design high-order distance metrics over a sparse selection of features dedicated to classification. Our approach is based on Conditional Random Field (CRF) energy minimization and Dual Decomposition, which allow efficiency and great flexibility in the considered features. The optimization technique ensures the tractability of high-dimensionality problems using hundreds of features and samples. Our approach is evaluated on synthetic data as well as on Covid-19 patient stratification. Comparisons with state-of-the-art baselines and our proposed method on different classification results prove the learned metric’s relevance.

Precision medicine is a paradigm shift in healthcare relying heavily on genomics data. However, the complexity of biological interactions, the large number of genes as well as the lack of comparisons on the analysis of data, remain a tremendous bottleneck regarding clinical adoption. In this paper, we introduce a novel, automatic and unsupervised framework to discover low-dimensional gene biomarkers. Our method is based on the LP-Stability algorithm, a high dimensional center-based unsupervised clustering algorithm. It offers modularity as concerns metric functions and scalability, while being able to automatically determine the best number of clusters. Our evaluation includes both mathematical and biological criteria to define a quantitative metric. The recovered signature is applied to a variety of biological tasks, including screening of biological pathways and functions, and characterization relevance on tumor types and subtypes. Quantitative comparisons among different distance metrics, commonly used clustering methods and a referential gene signature used in the literature, confirm state of the art performance of our approach. In particular, our signature, based on 27 genes, reports at least 30 times better mathematical significance (average Dunn's Index) and 25% better biological significance (average Enrichment in Protein-Protein Interaction) than those produced by other referential clustering methods. Finally, our signature reports promising results on distinguishing immune inflammatory and immune desert tumors, while reporting a high balanced accuracy of 92% on tumor types classification and averaged balanced accuracy of 68% on tumor subtypes classification, which represents, respectively 7% and 9% higher performance compared to the referential signature.

The Apparent Diffusion Coefficient (ADC) is considered an importantimaging biomarker contributing to the assessment of tissue microstructure and pathophy- siology. It is calculated from Diffusion-Weighted Magnetic Resonance Imaging (DWI) by means of a diffusion model, usually without considering any motion during image acquisition. We propose a method to improve the computation of the ADC by coping jointly with both motion artifacts in whole-body DWI (through group-wise registration) and possible instrumental noise in the diffusion model. The proposed deformable registration method yielded on average the lowest ADC reconstruction error on data with simulated motion and diffusion. Moreover, our approach was applied on whole-body diffusion weighted images obtained with five different b-values from a cohort of 38 patients with histologically confirmed lymphomas of three different types (Hodgkin, diffuse large B-cell lymphoma and follicular lymphoma). Evaluation on the real data showed that ADC-based features, extracted using our joint optimization approach classified lymphomas with an accuracy of approximately 78.6% (yielding a 11% increase in respect to the standard features extracted from unregistered diffusion-weighted images). Furthermore, the correlation between diffusion characteristics and histopathological findings was higher than any other previous approach of ADC computation.

Coronavirus disease 2019 (COVID-19) emerged in 2019 and disseminated around the world rapidly. Computed tomography (CT) imaging has been proven to be an important tool for screening, disease quantification and staging. The latter is of extreme importance for organizational anticipation (availability of intensive care unit beds, patient management planning) as well as to accelerate drug development through rapid, reproducible and quantified assessment of treatment response. Even if currently there are no specific guidelines for the staging of the patients, CT together with some clinical and biological biomarkers are used. In this study, we collected a multi-center cohort and we investigated the use of medical imaging and artificial intelligence for disease quantification, staging and outcome prediction. Our approach relies on automatic deep learning-based disease quantification using an ensemble of architectures, and a data-driven consensus for the staging and outcome prediction of the patients fusing imaging biomarkers with clinical and biological attributes. Highly promising results on multiple external/independent evaluation cohorts as well as comparisons with expert human readers demonstrate the potentials of our approach.

We investigate the use of recent advances in deep learning and propose an end-to-end trainable multi-instance convolutional neural network within a mixture-of-experts formulation that combines information from two types of data-images and clinical attributes-for the diagnosis of lymphocytosis. The convolutional network learns to extract meaningful features from images of blood cells using an embedding level approach and aggregates them. Moreover, the mixture-of-experts model combines information from these images as well as clinical attributes to form an end-to-end trainable pipeline for diagnosis of lymphocytosis. Our results demonstrate that even the convolutional network by itself is able to discover meaningful associations between the images and the diagnosis, indicating the presence of important unexploited information in the images. The mixture-of-experts formulation is shown to be more robust while maintaining performance via. a repeatability study to assess the effect of variability in data acquisition on the predictions. The proposed methods are compared with different methods from literature based both on conventional handcrafted features and machine learning, and on recent deep learning models based on attention mechanisms. Our method reports a balanced accuracy of [Formula: see text] and outperfroms the handcrafted feature-based and attention-based approaches as well that of biologists which scored [Formula: see text], [Formula: see text] and [Formula: see text] respectively. These results give insights on the potentials of the applicability of the proposed method in clinical practice. Our code and datasets can be found at https://github.com/msahasrabudhe/lymphoMIL.

Image registration in multimodal, multitemporal satellite imagery is one of the most important problems in remote sensing and essential for a number of other tasks such as change detection and image fusion. In this paper, inspired by the recent success of deep learning approaches we propose a novel convolutional neural network architecture that couples linear and deformable approaches for accurate alignment of remote sensing imagery. The proposed method is completely unsupervised, ensures smooth displacement fields and provides real time registration on a pair of images. We evaluate the performance of our method using a challenging multitemporal dataset of very high resolution satellite images and compare its performance with a state of the art elastic registration method based on graphical models. Both quantitative and qualitative results prove the high potentials of our method.

In this study, we propose a 3D deep neural network called U-ReSNet, a joint framework that can accurately register and segment medical volumes. The proposed network learns to automatically generate linear and elastic deformation models, trained by minimizing the mean square error and the local cross correlation similarity metrics. In parallel, a coupled architecture is integrated, seeking to provide segmentation maps for anatomies or tissue patterns using an additional decoder part trained with the dice coefficient metric. U-ReSNet is trained in an end to end fashion, while due to this joint optimization the generated network features are more informative leading to promising results compared to other deep learning-based methods existing in the literature. We evaluated the proposed architecture using the publicly available OASIS 3 dataset, measuring the dice coefficient metric for both registration and segmentation tasks. Our promising results indicate the potentials of our method which is composed from a convolutional architecture that is extremely simple and light in terms of parameters.

Deformable registration has been one of the pillars of biomedical image computing. Conventional approaches refer to the definition of a similarity criterion that, once endowed with a deformation model and a smoothness constraint, determines the optimal transformation to align two given images. The definition of this metric function is among the most critical aspects of the registration process. We argue that incorporating semantic information (in the form of anatomical segmentation maps) into the registration process will further improve the accuracy of the results. In this paper, we propose a novel weakly supervised approach to learn domain-specific aggregations of conventional metrics using anatomical segmentations. This combination is learned using latent structured support vector machines. The learned matching criterion is integrated within a metric-free optimization framework based on graphical models, resulting in a multi-metric algorithm endowed with a spatially varying similarity metric function conditioned on the anatomical structures. We provide extensive evaluation on three different datasets of CT and MRI images, showing that learned multi-metric registration outperforms single-metric approaches based on conventional similarity measures.

In this paper, we study a nonconvex continuous relaxation of MAP inference in discrete Markov random fields (MRFs). We show that for arbitrary MRFs, this relaxation is tight, and a discrete stationary point of it can be easily reached by a simple block coordinate descent algorithm. In addition, we study the resolution of this relaxation using popular gradient methods, and further propose a more effective solution using a multilinear decomposition framework based on the alternating direction method of multipliers (ADMM). Experiments on many real-world problems demonstrate that the proposed ADMM significantly outperforms other nonconvex relaxation based methods, and compares favorably with state of the art MRF optimization algorithms in different settings.

Semantic segmentation is currently a mainstream method for addressing several remote sensing applications, achieving recently remarkable performance by employing deep learning techniques. In particular, this is the case for pixel-wise dense classification models in very high resolution remote sensing datasets. In this paper, we exploit the use of a relatively deep architecture based on repetitive downscale-upscale processes that had been previously employed for human pose estimation tasks. By integrating such a model, we are aiming to capture and extract low-level details, such as small objects, object boundaries and edges. Experimental results and quantitative evaluation has been performed on the publicly available ISPRS (WGIII4) benchmark dataset indicating the potential of the proposed approach.

Linear programming relaxations are central to MAP inference in discrete Markov Random Fields. The ability to properly solve the Lagrangian dual is a critical component of such methods. In this paper, we study the benefit of using Newton-type methods to solve the Lagrangian dual of a smooth version of the problem. We investigate their ability to achieve superior convergence behavior and to better handle the ill-conditioned nature of the formulation, as compared to first order methods. We show that it is indeed possible to efficiently apply a trust region Newton method for a broad range of MAP inference problems. In this paper we propose a provably globally efficient framework that includes (i) excellent compromise between computational complexity and precision concerning the Hessian matrix construction, (ii) a damping strategy that aids efficient optimization, (iii) a truncation strategy coupled with a generic pre-conditioner for Conjugate Gradients, (iv) efficient sum-product computation for sparse clique potentials. Results for higher-order Markov Random Fields demonstrate the potential of this approach.

In this paper, we introduce a graph matching method that can account for constraints of arbitrary order, with arbitrary potential functions. Unlike previous decomposition approaches that rely on the graph structures, we introduce a decomposition of the matching constraints. Graph matching is then reformulated as a non-convex non-separable optimization problem that can be split into smaller and much-easier-to-solve subproblems, by means of the alternating direction method of multipliers. The proposed framework is modular, scalable, and can be instantiated into different variants. Two instantiations are studied exploring pairwise and higher-order constraints. Experimental results on widely adopted benchmarks involving synthetic and real examples demonstrate that the proposed solutions outperform existing pairwise graph matching methods, and competitive with the state of the art in higher-order settings.

Automatic and accurate detection of man-made objects, such as buildings, is one of the main problems that the remote sensing community has been focusing on for the last decades. In this paper, we propose a Conditional Random Field (CRF) formulation which is using edge/boundary localization priors towards accurate building detection. These edge priors have been integrated/fused with the classification scores from a deep learning Convolutional Neural Network (CNN) architecture under a single energy formulation. The validation of the developed methodology had been performed on the recently published SpaceNet dataset. Experimental results and quantitative evaluation, based on different accuracy statistics, indicate the great potential of the proposed approach.

Intensity variations can often be described by a physiological or temporal model applied on a voxel-wise basis across a group of images. However the voxel correspondence might be unknown, imposing the need for a group-wise deformable registration coupled with the computation of the model parameters. In this paper we propose a group-wise registration method of medical images that incorporates the temporal dimension (reflecting the change of signal amplitude) of the acquisition process. Consistency on the spatiotemporal physiological model, as well as deformation smoothness, is imposed in order to produce anatomically meaningful representations of the 3D images. The performance of the proposed method is compared to two different group-wise registration approaches; one that penalizes the absolute differences in the intensities and one that penalizes the intensity range among the images on corresponding regions. We chose as an application paradigm the registration of diffusion-weighted magnetic resonance (DW-MR) images for the evaluation of patients with lymphomas. A dataset consisting of 25 patients, each scanned with 3 “b values”, was used to evaluate the method's accuracy. The proposed registration method outperfomed the other two registration approaches, making it a very promising method for highlighting the importance of DWI as an imaging biomarker.

In this paper, a novel generic framework has been designed, developed and validated for addressing simultaneously the tasks of image registration, segmentation and change detection from multisensor, multiresolution, multitemporal satellite image pairs. Our approach models the inter-dependencies of variables through a higher order graph. The proposed formulation is modular with respect to the nature of images (various similarity metrics can be considered), the nature of deformations (arbitrary interpolation strategies), and the nature of segmentation likelihoods (various classification approaches can be employed). Inference of the proposed formulation is achieved through its mapping to an overparametrized pairwise graph which is then optimized using linear programming. Experimental results and the performed quantitative evaluation indicate the high potentials of the developed method.

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.

The automated man-made object detection and building extraction from single satellite images is, still, one of the most challenging tasks for various urban planning and monitoring engineering applications. To this end, in this paper we propose an automated building detection framework from very high resolution remote sensing data based on deep convolutional neural networks. The core of the developed method is based on a supervised classification procedure employing a very large training dataset. An MRF model is then responsible for obtaining the optimal labels regarding the detection of scene buildings. The experimental results and the performed quantitative validation indicate the quite promising potentials of the developed approach.

The papers in this special section address the programs and services supported by graphical models in computer vision. This section explores the main challenges in this framework—modeling novel priors, learning, inference—and presents innovative solutions. The papers cover the aspects of modeling novel priors, inference algorithms and parameter learning methods in the context of higher order graphical 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).

Computational vision and biomedical image have made tremendous progress of the past decade. This is mostly due the development of efficient learning and inference algorithms which allow better, faster and richer modeling of visual perception tasks. Graph-based representations are among the most prominent tools to address such perception through the casting of perception as a graph optimization problem. In this paper, we briefly introduce the interest of such representations, discuss their strength and limitations and present their application to address a variety of problems in computer vision and biomedical image analysis.

Image segmentation is, in general, an ill-posed problem and additional constraints need to be imposed in order to achieve the desired segmentation result. While segmenting organs in medical images, which is the topic of this paper, a significant amount of prior knowledge about the shape, appearance, and location of the organs is available that can be used to constrain the solution space of the segmentation problem. Among the various types of prior information, the incorporation of prior information about shape, in particular, is very challenging. In this paper, we present an explicit shape-constrained MAP-MRF-based contour evolution method for the segmentation of organs in 2-D medical images. Specifically, we represent the segmentation contour explicitly as a chain of control points. We then cast the segmentation problem as a contour evolution problem, wherein the evolution of the contour is performed by iteratively solving a MAP-MRF labeling problem. The evolution of the contour is governed by three types of prior information, namely: (i) appearance prior, (ii) boundary-edgeness prior, and (iii) shape prior, each of which is incorporated as clique potentials into the MAP-MRF problem. We use the master-slave dual decomposition framework to solve the MAP-MRF labeling problem in each iteration. In our experiments, we demonstrate the application of the proposed method to the challenging problem of heart segmentation in non-contrast computed tomography data.

Graph-based methods have become popular in recent years and have successfully addressed tasks like segmentation and deformable registration. Their main strength is optimality of the obtained solution while their main limitation is the lack of precision due to the grid-like representations and the discrete nature of the quantized search space. In this paper we introduce a novel approach for combined segmentation/registration of brain tumors that adapts graph and sampling resolution according to the image content. To this end we estimate the segmentation and registration marginals towards adaptive graph resolution and intelligent definition of the search space. This information is considered in a hierarchical framework where uncertainties are propagated in a natural manner. State of the art results in the joint segmentation/registration of brain images with low-grade gliomas demonstrate the potential of our approach.

We propose a novel approach for dense non-rigid 3D surface registration, which brings together Riemannian geometry and graphical models. To this end, we first introduce a generic deformation model, called Canonical Distortion Coefficients (CDCs), by characterizing the deformation of every point on a surface using the distortions along its two principle directions. This model subsumes the deformation groups commonly used in surface registration such as isometry and conformality, and is able to handle more complex deformations. We also derive its discrete counterpart which can be computed very efficiently in a closed form. Based on these, we introduce a higher-order Markov Random Field (MRF) model which seamlessly integrates our deformation model and a geometry/texture similarity metric. Then we jointly establish the optimal correspondences for all the points via maximum a posteriori (MAP) inference. Moreover, we develop a parallel optimization algorithm to efficiently perform the inference for the proposed higher-order MRF model. The resulting registration algorithm outperforms state-of-the-art methods in both dense non-rigid 3D surface registration and tracking.

The cast shadows in an image provide important information about illumination and geometry. In this paper, we utilize this information in a novel framework in order to jointly recover the illumination environment, a set of geometry parameters, and an estimate of the cast shadows in the scene given a single image and coarse initial 3D geometry. We model the interaction of illumination and geometry in the scene and associate it with image evidence for cast shadows using a higher order Markov Random Field (MRF) illumination model, while we also introduce a method to obtain approximate image evidence for cast shadows. Capturing the interaction between light sources and geometry in the proposed graphical model necessitates higher order cliques and continuous-valued variables, which make inference challenging. Taking advantage of domain knowledge, we provide a two-stage minimization technique for the MRF energy of our model. We evaluate our method in different datasets, both synthetic and real. Our model is robust to rough knowledge of geometry and inaccurate initial shadow estimates, allowing a generic coarse 3D model to represent a whole class of objects for the task of illumination estimation, or the estimation of geometry parameters to refine our initial knowledge of scene geometry, simultaneously with illumination estimation.

In this paper, we use shape grammars (SGs) for facade parsing, which amounts to segmenting 2D building facades into balconies, walls, windows, and doors in an architecturally meaningful manner. The main thrust of our work is the introduction of reinforcement learning (RL) techniques to deal with the computational complexity of the problem. RL provides us with techniques such as Q-learning and state aggregation which we exploit to efficiently solve facade parsing. We initially phrase the 1D parsing problem in terms of a Markov Decision Process, paving the way for the application of RL-based tools. We then develop novel techniques for the 2D shape parsing problem that take into account the specificities of the facade parsing problem. Specifically, we use state aggregation to enforce the symmetry of facade floors and demonstrate how to use RL to exploit bottom-up, image-based guidance during optimization. We provide systematic results on the Paris building dataset and obtain state-of-the-art results in a fraction of the time required by previous methods. We validate our method under diverse imaging conditions and make our software and results available online.

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.

In this paper we propose a novel method for knowledge-based segmentation. Our contribution lies on the introduction of linear sub-spaces constraints within the random-walk segmentation framework. Prior knowledge is obtained through principal component analysis that is then combined with conventional boundary constraints for image segmentation. The approach is validated on a challenging clinical setting that is multicomponent segmentation of the human upper leg skeletal muscle in Magnetic Resonance Imaging, where there is limited visual differentiation support between muscle classes.

In this paper we propose a novel approach for detection, segmentation and characterization of brain tumors. Our method exploits prior knowledge in the form of a sparse graph representing the expected spatial positions of tumor classes. Such information is coupled with image-based classification techniques along with spatial smoothness constraints towards producing a reliable detection map within a unified graphical model formulation. Towards optimal use of prior knowledge, a two layer interconnected graph is considered with one layer corresponding to the low-grade glioma type (characterization) and the second layer to voxel-based decisions of tumor presence. Efficient linear programming both in terms of performance as well as in terms of computational load is considered to recover the lowest potential of the objective function. The outcome of the method refers to both tumor segmentation as well as their characterization. Promising results on substantial data sets demonstrate the extreme potentials of our method.

Co-segmentation is defined as jointly partitioning multiple images depicting the same or similar object, into foreground and background. Our method consists of a multiple-scale multiple-image generative model, which jointly estimates the foreground and background appearance distributions from several images, in a non-supervised manner. In contrast to other co-segmentation methods, our approach does not require the images to have similar foregrounds and different backgrounds to function properly. Region matching is applied to exploit inter-image information by establishing correspondences between the common objects that appear in the scene. Moreover, computing many-to-many associations of regions allow further applications, like recognition of object parts across images. We report results on iCoseg, a challenging dataset that presents extreme variability in camera viewpoint, illumination and object deformations and poses. We also show that our method is robust against large intra-class variability in the MSRC database.

In this paper we address multi-view reconstruction of urban environments using 3D shape grammars. Our formulation expresses the solution to the problem as a shape grammar parse tree where both the tree and the corresponding derivation parameters are unknown. Besides the grammar constraint, the solution is guided by an image support that is twofold. First, we seek for a derivation that induces optimal semantic partitions in the different views. Second, using structure-from-motion, noisy depth maps can be determined towards minimizing their distance from to the ones predicted by any potential solution. We show how the underlying data structure can be efficiently optimized using evolutionary algorithms with automatic parameter selection. To the best of our knowledge, it is the first time that the multi-view 3D procedural modeling problem is tackled. Promising results demonstrate the potentials of the method towards producing a compact representation of urban environments.

International audience

This paper proposes a novel approach to optimally solve volumetric registration problems. The proposed framework exploits parametric dictionaries for sparse volumetric representations, ℓ1dissimilarities and DC (Difference of Convex functions) decomposition. The SAD (sum of absolute differences) criterion is applied to the sparse representation of the reference volume and a DC decomposition of this criterion with respect to the transformation parameters is derived. This permits to employ a cutting plane algorithm for determining the optimal relative transformation parameters of the query volume. It further provides a guarantee for the global optimality of the obtained solution, which–to the best of our knowledge–is not offered by any other existing approach. A numerical validation demonstrates the effectiveness and the large potential of the proposed method.

Analysis of gene expression patterns in brain images obtained from high-throughput in situ hybridization requires accurate and consistent annotations of anatomical regions/subregions. Such annotations are obtained by mapping an anatomical atlas onto the gene expression images through intensity- and/or landmark-based registration methods or deformable model-based segmentation methods. Due to the complex appearance of the gene expression images, these approaches require a pre-processing step to determine landmark correspondences in order to incorporate landmark-based geometric constraints. In this paper, we propose a novel method for landmark-constrained, intensity-based registration without determining landmark correspondences a priori. The proposed method performs dense image registration and identifies the landmark correspondences, simultaneously, using a single higher-order Markov Random Field model. In addition, a machine learning technique is used to improve the discriminating properties of local descriptors for landmark matching by projecting them in a Hamming space of lower dimension. We qualitatively show that our method achieves promising results and also compares well, quantitatively, with the expert's annotations, outperforming previous methods.

In this paper, we propose a novel framework to jointly recover the illumination environment and an estimate of the cast shadows in a scene from a single image, given coarse 3D geometry. We describe a higher-order Markov Random Field (MRF) illumination model, which combines low-level shadow evidence with high-level prior knowledge for the joint estimation of cast shadows and the illumination environment. First, a rough illumination estimate and the structure of the graphical model in the illumination space is determined through a voting procedure. Then, a higher order approach is considered where illumination sources are coupled with the observed image and the latent variables corresponding to the shadow detection. We examine two inference methods in order to effectively minimize the MRF energy of our model. Experimental evaluation shows that our approach is robust to rough knowledge of geometry and reflectance and inaccurate initial shadow estimates. We demonstrate the power of our MRF illumination model on various datasets and show that we can estimate the illumination in images of objects belonging to the same class using the same coarse 3D model to represent all instances of the class.

We address shape grammar parsing for facade segmentation using Reinforcement Learning (RL). Shape parsing entails simultaneously optimizing the geometry and the topology (e.g. number of floors) of the facade, so as to optimize the fit of the predicted shape with the responses of pixel-level 'terminal detectors'. We formulate this problem in terms of a Hierarchical Markov Decision Process, by employing a recursive binary split grammar. This allows us to use RL to efficiently find the optimal parse of a given facade in terms of our shape grammar. Building on the RL paradigm, we exploit state aggregation to speedup computation, and introduce image-driven exploration in RL to accelerate convergence. We achieve state-of-the-art results on facade parsing, with a significant speed-up compared to existing methods, and substantial robustness to initial conditions. We demonstrate that the method can also be applied to interactive segmentation, and to a broad variety of architectural styles.

This paper presents a novel intrinsic 3D surface distance and its use in a complete probabilistic tracking framework for dynamic 3D data. Registering two frames of a deforming 3D shape relies on accurate correspondences between all points across the two frames. In the general case such correspondence search is computationally intractable. Common prior assumptions on the nature of the deformation such as near-rigidity, isometry or learning from a training set, reduce the search space but often at the price of loss of accuracy when it comes to deformations not in the prior assumptions. If we consider the set of all possible 3D surface matchings defined by specifying triplets of correspondences in the uniformization domain, then we introduce a new matching cost between two 3D surfaces. The lowest feature differences across this set of matchings that cause two points to correspond, become the matching cost of that particular correspondence. We show that for surface tracking applications, the matching cost can be efficiently computed in the uniformization domain. This matching cost is then combined with regularization terms that enforce spatial and temporal motion consistencies, into a maximum a posteriori (MAP) problem which we approximate using a Markov Random Field (MRF). Compared to previous 3D surface tracking approaches that either assume isometric deformations or consistent features, our method achieves dense, accurate tracking results, which we demonstrate through a series of dense, anisometric 3D surface tracking experiments.

First order Markov Random Fields (MRFs) have become a predominant tool in Computer Vision over the past decade. Such a success was mostly due to the development of efficient optimization algorithms both in terms of speed as well as in terms of optimality properties. Message passing algorithms are among the most popular methods due to their good performance for a wide range of pairwise potential functions (PPFs). Their main bottleneck is computational complexity. In this paper, we revisit message computation as a distance transformation using a more formal setting than [8] to generalize it to arbitrary PPFs. The method is based on [20] yielding accurate results for a specific class of PPFs and in most other cases a close approximation. The proposed algorithm is parallel and thus enables us to fully take advantage of the computational power of parallel processing architectures. The proposed scheme coupled with an efficient belief propagation algorithm [8] and implemented on a massively parallel coprocessor provides results as accurate as state of the art inference methods, though is in general one order of magnitude faster in terms of speed.

An accurate labeling of a multi-part, complex anatomical structure (e.g., brain) is required in order to compare data across images for spatial analysis. It can be achieved by fitting an object-specific geometric atlas that is constructed using a partitioned, high-resolution deformable mesh and tagging each of its polygons with a region label. Subdivision meshes have been used to construct such an atlas because they can provide a compact representation of a partitioned, multi-resolution, object-specific mesh structure using only a few control points. However, automated fitting of a subdivision mesh-based geometric atlas to an anatomical structure in an image is a difficult problem and has not been sufficiently addressed. In this paper, we propose a novel Markov Random Field-based method for fitting a planar, multi-part subdivision mesh to anatomical data. The optimal fitting of the atlas is obtained by determining the optimal locations of the control points. We also tackle the problem of landmark matching in tandem with atlas fitting by constructing a single graphical model to impose pose-invariant, landmark-based geometric constraints on atlas deformation. The atlas deformation is also governed by additional constraints imposed by the mesh's geometric properties and the object boundary. We demonstrate the potential of the proposed method on the difficult problem of segmenting a mouse brain and its interior regions in gene expression images which exhibit large intensity and shape variability. We obtain promising results when compared with manual annotations and prior methods.

In this paper, we propose a novel one-shot optimization approach to simultaneously determine both the optimal 3D landmark model and the corresponding 2D projections without explicit estimation of the camera viewpoint, which is also able to deal with misdetections as well as partial occlusions. To this end, a 3D shape manifold is built upon fourth-order interactions of landmarks from a training set where pose-invariant statistics are obtained in this space. The 3D-2D consistency is also encoded in such high-order interactions, which eliminate the necessity of viewpoint estimation. Furthermore, the modeling of visibility improves further the performance of the method by handling missing correspondences and occlusions. The inference is addressed through a MAP formulation which is naturally transformed into a higher-order MRF optimization problem and is solved using a dual-decomposition-based method. Promising results on standard face benchmarks demonstrate the potential of our approach.

A novel model-based approach to 3D hand tracking from monocular video is presented. The 3D hand pose, the hand texture, and the illuminant are dynamically estimated through minimization of an objective function. Derived from an inverse problem formulation, the objective function enables explicit use of temporal texture continuity and shading information while handling important self-occlusions and time-varying illumination. The minimization is done efficiently using a quasi-Newton method, for which we provide a rigorous derivation of the objective function gradient. Particular attention is given to terms related to the change of visibility near self-occlusion boundaries that are neglected in existing formulations. To this end, we introduce new occlusion forces and show that using all gradient terms greatly improves the performance of the method. Qualitative and quantitative experimental results demonstrate the potential of the approach.

This paper introduces a new rigorous theoretical framework to address discrete MRF-based optimization in computer vision. Such a framework exploits the powerful technique of Dual Decomposition. It is based on a projected subgradient scheme that attempts to solve an MRF optimization problem by first decomposing it into a set of appropriately chosen subproblems, and then combining their solutions in a principled way. In order to determine the limits of this method, we analyze the conditions that these subproblems have to satisfy and demonstrate the extreme generality and flexibility of such an approach. We thus show that by appropriately choosing what subproblems to use, one can design novel and very powerful MRF optimization algorithms. For instance, in this manner we are able to derive algorithms that: 1) generalize and extend state-of-the-art message-passing methods, 2) optimize very tight LP-relaxations to MRF optimization, and 3) take full advantage of the special structure that may exist in particular MRFs, allowing the use of efficient inference techniques such as, e.g., graph-cut-based methods. Theoretical analysis on the bounds related with the different algorithms derived from our framework and experimental results/comparisons using synthetic and real data for a variety of tasks in computer vision demonstrate the extreme potentials of our approach.

EMPIRE10 (Evaluation of Methods for Pulmonary Image REgistration 2010) is a public platform for fair and meaningful comparison of registration algorithms which are applied to a database of intrapatient thoracic CT image pairs. Evaluation of nonrigid registration techniques is a nontrivial task. This is compounded by the fact that researchers typically test only on their own data, which varies widely. For this reason, reliable assessment and comparison of different registration algorithms has been virtually impossible in the past. In this work we present the results of the launch phase of EMPIRE10, which comprised the comprehensive evaluation and comparison of 20 individual algorithms from leading academic and industrial research groups. All algorithms are applied to the same set of 30 thoracic CT pairs. Algorithm settings and parameters are chosen by researchers expert in the configuration of their own method and the evaluation is independent, using the same criteria for all participants. All results are published on the EMPIRE10 website (http://empire10.isi.uu.nl). The challenge remains ongoing and open to new participants. Full results from 24 algorithms have been published at the time of writing. This paper details the organization of the challenge, the data and evaluation methods and the outcome of the initial launch with 20 algorithms. The gain in knowledge and future work are discussed.

International audience

In this paper we propose a novel approach to the perceptual interpretation of building facades that combines shape grammars, supervised classification and random walks. Procedural modeling is used to model the geometric and the photometric variation of buildings. This is fused with visual classification techniques (randomized forests) that provide a crude probabilistic interpretation of the observation space in order to measure the appropriateness of a procedural generation with respect to the image. A random exploration of the grammar space is used to optimize the sequence of derivation rules towards a semantico-geometric interpretation of the observations. Experiments conducted on complex architecture facades with ground truth validate the approach.

In this paper, we propose a high-order graph matching formulation to address non-rigid surface matching. The singleton terms capture the geometric and appearance similarities (e.g., curvature and texture) while the high-order terms model the intrinsic embedding energy. The novelty of this paper includes: 1. casting 3D surface registration into a graph matching problem that combines both geometric and appearance similarities and intrinsic embedding information, 2. the first implementation of high-order graph matching algorithm that solves a non-convex optimization problem, and 3. an efficient two-stage optimization approach to constrain the search space for dense surface registration. Our method is validated through a series of experiments demonstrating its accuracy and efficiency, notably in challenging cases of large and/or non-isometric deformations, or meshes that are partially occluded.

In this paper, a novel variational framework is introduced toward automatic 3-D building reconstruction from remote-sensing data. We consider a subset of building models that involve the footprint, their elevation, and the roof type. These models, under a certain hierarchical representation, describe the space of solutions and, under a fruitful synergy with an inferential procedure, recover the observed scene's geometry. Such an integrated approach is defined in a variational context, solves segmentation both in optical images and digital elevation maps, and allows multiple competing priors to determine their pose and 3-D geometry from the observed data. The very promising experimental results and the performed quantitative evaluation demonstrate the potentials of our approach.

In this paper, we introduce a reconstruction framework that explicitly accounts for image geometry when defining the spatial interaction between pixels in the filtering process. To this end, image structure is captured using local co-occurrence statistics and is incorporated to the enhancement algorithm in a sequential fashion using the particle filtering technique. In this context, the reconstruction process is modeled using a dynamical system with multiple states and its evolution is guided by the prior density describing the image structure. Towards optimal exploration of the image geometry, an evaluation process of the state of the system is performed at each iteration. The resulting framework explores optimally spatial dependencies between image content towards variable bandwidth image reconstruction. Promising results using additive noise models demonstrate the potentials of such an explicit modeling of the geometry.

In this paper we introduce a new approach to knowledge-based segmentation. Our method consists of a novel representation to model shape variations as well as an efficient inference procedure to fit the model to new data. The considered shape model is similarity-invariant and refers to an incomplete graph that consists of intra and intercluster connections representing the inter-dependencies of control points. The clusters are determined according to the co-dependencies of the deformations of the control points within the training set. The connections between the components of a cluster represent the local structure while the connections between the clusters account for the global structure. The distributions of the normalized distances between the connected control points encode the prior model. During search, this model is used together with a discrete Markov random field (MRF) based segmentation, where the unknown variables are the positions of the control points in the image domain. To encode the image support, a Voronoi decomposition of the domain is considered and regional based statistics are used. The resulting model is computationally efficient, can encode complex statistical models of shape variations and benefits from the image support of the entire spatial domain.

A novel scheme for deformable tracking of curvilinear structures in image sequences is presented. The approach is based on B-spline snakes defined by a set of control points whose optimal configuration is determined through efficient discrete optimization. Each control point is associated with a discrete random variable in a MAP-MRF formulation where a set of labels captures the deformation space. In such a context, generic terms are encoded within this MRF in the form of pairwise potentials. The use of pairwise potentials along with the B-spline representation offers nearly perfect approximation of the continuous domain. Efficient linear programming is considered to recover the approximate optimal solution. The method is successfully applied to the tracking of guide-wires in fluoroscopic X-ray sequences of several hundred frames which requires extremely robust techniques.

In this paper, we introduce a higher-order MRF optimization framework. On the one hand, it is very general; we thus use it to derive a generic optimizer that can be applied to almost any higher-order MRF and that provably optimizes a dual relaxation related to the input MRF problem. On the other hand, it is also extremely flexible and thus can be easily adapted to yield far more powerful algorithms when dealing with subclasses of high-order MRFs. We thus introduce a new powerful class of high-order potentials, which are shown to offer enough expressive power and to be useful for many vision tasks. To address them, we derive, based on the same framework, a novel and extremely efficient message-passing algorithm, which goes beyond the aforementioned generic optimizer and is able to deliver almost optimal solutions of very high quality. Experimental results on vision problems demonstrate the extreme effectiveness of our approach. For instance, we show that in some cases we are even able to compute the global optimum for NP-hard higher-order MRFs in a very efficient manner.

In this paper, we present a kernel-based approach to the clustering of diffusion tensors and fiber tracts. We propose to use a Mercer kernel over the tensor space where both spatial and diffusion information are taken into account. This kernel highlights implicitly the connectivity along fiber tracts. Tensor segmentation is performed using kernel-PCA compounded with a landmark-Isomap embedding and k-means clustering. Based on a soft fiber representation, we extend the tensor kernel to deal with fiber tracts using the multi-instance kernel that reflects not only interactions between points along fiber tracts, but also the interactions between diffusion tensors. This unsupervised method is further extended by way of an atlas-based registration of diffusion-free images, followed by a classification of fibers based on nonlinear kernel Support Vector Machines (SVMs). Promising experimental results of tensor and fiber classification of the human skeletal muscle over a significant set of healthy and diseased subjects demonstrate the potential of our approach.

Illuminant estimation from shadows typically relies on accurate segmentation of the shadows and knowledge of exact 3D geometry, while shadow estimation is difficult in the presence of texture. These can be onerous requirements; in this paper we propose a graphical model to estimate the illumination environment and detect the shadows of a scene with textured surfaces from a single image and only coarse 3D information. We represent the illumination environment as a mixture of von Mises-Fisher distributions. Then, each shadow pixel becomes the combination of samples generated from this illumination environment. We integrate a number of low-level, illumination-invariant 2D cues in a graphical model to detect and estimate cast shadows on textured surfaces. Both 2D cues and approximate 3D reasoning are combined to infer a set of labels that identify the shadows in the image and estimate the positions, shapes and intensities of the light sources. Our results demonstrate that the probabilistic combination of multiple cues, unlike prior approaches, manages to differentiate both hard and soft shadows from the underlying surface texture even when we can only coarsely anticipate the effect of 3D geometry. We also experimentally demonstrate how correct estimation of the sharpness and shape of the light sources improves the augmented reality results.

In this paper, we propose a novel representation of prior knowledge for image segmentation, using diffusion wavelets that can reflect arbitrary continuous interdependencies in shape data. The application of diffusion wavelets has, so far, largely been confined to signal processing. In our approach, and in contrast to state-of-the-art methods, we optimize the coefficients, the number and the position of landmarks, and the object topology - the domain on which the wavelets are defined - during the model learning phase, in a coarse-to-fine manner. The resulting paradigm supports hierarchies both in the model and the search space, can encode complex geometric and photometric dependencies of the structure of interest, and can deal with arbitrary topologies. We report results on two challenging medical data sets, that illustrate the impact of the soft parameterization and the potential of the diffusion operator.

In this paper we introduce a novel approach to single view reconstruction using shape grammars. Our approach consists in modeling architectural styles using a set of basic shapes and a set of parametric rules, corresponding to increasing levels of detail. This approach is able to model elaborate and varying architectural styles, using a tree representation of variable depth and complexity. Towards reconstruction, the parameters of the rules are optimized using image-based and architectural costs. This is done through an efficient MRF formulation based on the shape grammar itself. The resulting framework can produce precise 3D models from single views, can deal with lack of texture and the presence of occlusions and specular reflections, while maintaining the ability to cope with very complex architectural styles. Promising results demonstrate the potential of our approach.

In this paper, we propose a unified graphical-model framework to interpret a scene composed of multiple objects in monocular video sequences. Using a single pairwise Markov random field (MRF), all the observed and hidden variables of interest such as image intensities, pixels' states (associated object's index and relative depth), objects' states (model motion parameters and relative depth) are jointly considered. Particular attention is given to occlusion handling by introducing a rigorous visibility modeling within the MRF formulation. Through minimizing the MRF's energy, we simultaneously segment, track and sort by depth the objects. Promising experimental results demonstrate the potential of this framework and its robustness to image noise, cluttered background, moving camera and background, and even complete occlusions.

In this paper, we introduce a variational framework towards automatic 3D building reconstruction from optical and Lidar data. Multiple 3D competing building priors are considered under a recognition-driven way. These models, under a certain hierarchical representation, describe the space of solutions and under a fruitful synergy with an inferential procedure recover the observed scene's geometry. Our formulation allows the cue with the higher spatial resolution to constrain properly the boundaries detection procedure ensuring, in this way, optimal results in terms of accuracy. Such an integrated approach is defined in a variational context, solves segmentation in both spaces, addresses fusion in a natural manner and allows multiple competing priors to determine the pose and 3D geometry from the observed data. Very promising experimental results demonstrate the potentials of our approach.

Locality information is crucial in datasets where each variable corresponds to a measurement in a manifold (silhouettes, motion trajectories, 2D and 3D images). Although these datasets are typically under-sampled and high-dimensional, they often need to be represented with low-complexity statistical models, which are comprised of only the important probabilistic dependencies in the datasets. Most methods attempt to reduce model complexity by enforcing structure sparseness. However, sparseness cannot describe inherent regularities in the structure. Hence, in this paper we first propose a new class of Gaussian graphical models which, together with sparseness, imposes local constancy through ${\ell}_1$-norm penalization. Second, we propose an efficient algorithm which decomposes the strictly convex maximum likelihood estimation into a sequence of problems with closed form solutions. Through synthetic experiments, we evaluate the closeness of the recovered models to the ground truth. We also test the generalization performance of our method in a wide range of complex real-world datasets and demonstrate that it can capture useful structures such as the rotation and shrinking of a beating heart, motion correlations between body parts during walking and functional interactions of brain regions. Our method outperforms the state-of-the-art structure learning techniques for Gaussian graphical models both for small and large datasets.

Registration and modeling of shapes are two important problems in computer vision and pattern recognition. Despite enormous progress made over the past decade, these problems are still open. In this paper, we advance the state of the art in both directions. First we consider an efficient registration method that aims to recover a one-to-one correspondence between shapes and introduce measures of uncertainties driven from the data which explain the local support of the recovered transformations. To this end, a free form deformation is used to describe the deformation model. The transformation is combined with an objective function defined in the space of implicit functions used to represent shapes. Once the registration parameters have been recovered, we introduce a novel technique for model building and statistical interpretation of the training examples based on a variable bandwidth kernel approach. The support on the kernels varies spatially and is determined according to the uncertainties of the registration process. Such a technique introduces the ability to account for potential registration errors in the model. Hand-written character recognition and knowledge-based object extraction in medical images are examples of applications that demonstrate the potentials of the proposed framework.

In this paper, a novel recognition-driven variational framework, toward multiple building extraction from aerial and satellite images, is introduced. To this end, competing shape priors are considered, and building extraction is addressed through an image segmentation approach that involves the use of a data-driven term constrained from the prior models. The proposed framework extends previous approaches toward the integration of multiple shape priors into the level-set segmentation. In particular, it estimates the number of buildings as well as their pose from the observed data. Therefore, it can address multiple building extraction from a single optical image, a highly demanding task of fundamental importance in various geoscience and remote-sensing applications. Furthermore, it can be easily extended to deal with other remote-sensing data through a simple modification of the image term. Very promising experimental results and the performed qualitative and quantitative evaluation demonstrate the potential of our approach.

Arthroplasty, the implantation of prostheses into joints, is a surgical procedure that is affecting a larger and larger number of patients over time. As a result, it is increasingly important to develop imaging techniques to noninvasively examine joints with prostheses after surgery, both statically and dynamically in 3-D. The static problem is considered here, with the aim to create a 3-D shape model of the bone as well as the prosthesis using a set of 2-D X-rays from various viewpoints. The most important challenge to be addressed is the lack of texture, the most common feature to recover shape from multiple views. In order to overcome this limitation, we reformulate the problem using a novel multiview segmentation approach where an active contours 3-D surface evolution with level-set implementation is used to recover the shape of bones and prostheses in postoperative joints. The recovered shape may then be used to track 3-D motions in dynamic X-ray sequences to obtain kinematic information.

We introduce a new image representation that encompasses both the general layout of groups of quantized local invariant descriptors as well as their relative frequency. A graph of interest points clusters is constructed and we use the matrix of commute times between the different nodes of the graph to obtain a description of their relative arrangement that is robust to large intra class variation. The obtained high dimensional representation is then embedded in a space of lower dimension by exploiting the spectral properties of the graph made of the different images. Classification tasks can be performed in this embedding space. We expose classification and labelling results obtained on three different datasets, including the challenging PASCAL VOC2007 dataset. The performances of our approach compare favorably with the standard bag of features, which is a particular case of our representation.

In this paper, we propose a novel approach to model shape variations. It encodes sparsity, exploits geometric redundancy, and accounts for the different degrees of local variation and image support. In this context we consider a control-point based shape representation. Their sparse distribution is derived based on a shape model metric learned from the training data, and the ambiguity of local appearance with regard to segmentation changes. The resulting sparse model of the object improves reconstruction and search behavior, in particular for data that exhibit a heterogeneous distribution of image information and shape complexity. Furthermore, it goes beyond conventional image-based segmentation approaches since it is able to identify reliable image structures which are then encoded within the model and used to determine the optimal segmentation map. We report promising experimental results comparing our approach with standard models on MRI data of calf muscles - an application where traditional image-based methods fail - and CT data of the left heart ventricle.

In this paper, we propose a novel dynamic discrete framework to address image morphing with application to optical flow estimation. We reformulate the problem using a number of discrete displacements, and therefore the estimation of the morphing parameters becomes a tractable matching criteria independent combinatorial problem which is solved through the FastPD algorithm. In order to overcome the main limitation of discrete approaches (low dimensionality of the label space is unable to capture the continuous nature of the expected solution), we introduce a dynamic behavior in the model where the plausible discrete deformations (displacements) are varying in space (across the domain) and time (different states of the process - successive morphing states) according to the local uncertainty of the obtained solution.

A novel model-based approach to 3D hand tracking from monocular video is presented. The 3D hand pose, the hand texture and the illuminant are dynamically estimated through minimization of an objective function. Derived from an inverse problem formulation, the objective function enables explicit use of texture temporal continuity and shading information, while handling important self-occlusions and time-varying illumination. The minimization is done efficiently using a quasi-Newton method, for which we propose a rigorous derivation of the objective function gradient. Particular attention is given to terms related to the change of visibility near self-occlusion boundaries that are neglected in existing formulations. In doing so we introduce new occlusion forces and show that using all gradient terms greatly improves the performance of the method. Experimental results demonstrate the potential of the formulation.

We propose a shape population metric that reflects the interdependencies between points observed in a set of examples. It provides a notion of topology for shape and appearance models that represents the behavior of individual observations in a metric space, in which distances between points correspond to their joint modeling properties. A Markov chain is learnt using the description lengths of models that describe sub sets of the entire data. The according diffusion map or shape map provides for the metric that reflects the behavior of the training population. With this metric functional clustering, deformation- or motion segmentation, sparse sampling and the treatment of outliers can be dealt with in a unified and transparent manner. We report experimental results on synthetic and real world data and compare the framework with existing specialized approaches.

In this paper we provide an overview of an image representation approach based on the description of layout and appearance properties of groups of features. In each image a graph of quantized features of interest is constructed. The features that are assigned to the same codebook bin are then grouped to produce a collapsed graph; the image content is represented by the matrix of commute times of this collapsed graph. This novel image descriptor can be used to label satellite image databases; we demonstrate the relevance and the efficiency of our approach by addressing classification problems on a dataset of 0.6 m resolution Quick bird images.

A novel center-based clustering algorithm is proposed in this paper. We first formulate clustering as an NP-hard linear integer program and we then use linear programming and the duality theory to derive the solution of this optimization problem. This leads to an efficient and very general algorithm, which works in the dual domain, and can cluster data based on an arbitrary set of distances. Despite its generality, it is independent of initialization (unlike EM-like methods such as K-means), has guaranteed convergence, and can also provide online optimality bounds about the quality of the estimated clustering solutions. To deal with the most critical issue in a center-based clustering algorithm (selection of cluster centers), we also introduce the notion of stability of a cluster center, which is a well defined LP-based quantity that plays a key role to our algorithm's success. Furthermore, we also introduce, what we call, the margins (another key ingredient in our algorithm), which can be roughly thought of as dual counterparts to stabilities and allow us to obtain computationally efficient approximations to the latter. Promising experimental results demonstrate the potentials of our method.

This paper introduces a variational formulation for image denoising based on a quadratic function over kernels of variable bandwidth. These kernels are scale adaptive and reflect spatial and photometric similarities between pixels. The bandwidth of the kernels is observation-dependent towards improving the accuracy of the reconstruction process and is constrained to be locally smooth. We analyze the evolution of the noise model form the RAW space to the RGB one, by propagating it over the image formation process. The experimental results demonstrate that the use of a variable bandwidth approach and an image intensity dependent noise variance ensures better restoration quality.

In this paper, we propose a general framework for fusing bottom-up segmentation with top-down object behavior classification over an image sequence. This approach is beneficial for both tasks, since it enables them to cooperate so that knowledge relevant to each can aid in the resolution of the other, thus enhancing the final result. In particular, classification offers dynamic probabilistic priors to guide segmentation, while segmentation supplies its results to classification, ensuring that they are consistent both with prior knowledge and with new image information. We demonstrate the effectiveness of our framework via a particular implementation for a hand gesture recognition application. The prior models are learned from training data using principal components analysis and they adapt dynamically to the content of new images. Our experimental results illustrate the robustness of our joint approach to segmentation and behavior classification in challenging conditions involving occlusions of the target object before a complex background.

A new efficient MRF optimization algorithm, called Fast-PD, is proposed, which generalizes α-expansion. One of its main advantages is that it offers a substantial speedup over that method, e.g. it can be at least 3-9 times faster than α-expansion. Its efficiency is a result of the fact that Fast-PD exploits information coming not only from the original MRF problem, but also from a dual problem. Furthermore, besides static MRFs, it can also be used for boosting the performance of dynamic MRFs, i.e. MRFs varying over time. On top of that, Fast-PD makes no compromise about the optimality of its solutions: it can compute exactly the same answer as a-expansion, but, unlike that method, it can also guarantee an almost optimal solution for a much wider class of NP-hard MRF problems. Results on static and dynamic MRFs demonstrate the algorithm's efficiency and power. E.g., Fast-PD has been able to compute disparity for stereoscopic sequences in real time, with the resulting disparity coinciding with that of a-expansion.

A new message-passing scheme for MRF optimization is proposed in this paper. This scheme inherits better theoretical properties than all other state-of-the-art message passing methods and in practice performs equally well/outperforms them. It is based on the very powerful technique of Dual Decomposition [1] and leads to an elegant and general framework for understanding/designing message-passing algorithms that can provide new insights into existing techniques. Promising experimental results and comparisons with the state of the art demonstrate the extreme theoretical and practical potentials of our approach.

The endovascular repair of a traumatic rupture of the thoracic aorta - that would otherwise lead to the death of the patient - is performed by delivering a stent-graft into the vessel at the rupture location. The age range of the affected patients is large and the stent-graft will stay in the body for the remaining life. The technique is relatively new, and no experience with regard to long-term effects, and durability exists. To predict long-term complications, such as ruptures or destructive interactions with surrounding tissue during the life of the patient, it is important to understand the - rather intense and constant - movement of the stent- graft during the cardiac cycle. A computed tomography with heart gating (gated CT) acquires sequences that show the region of the stent-graft at different time points. We analyze the motion of stent-grafts with a model based approach. Stent-grafts are represented as sparse sets of axis points extracted from the gated CT, and motion patterns are captured by a minimum description length based group-wise registration of the stent-graft at different time points. No parameterization or a priori definition of the topology is necessary, and highly variable elasticity properties in the data volume can by accounted for by the sparse statistical model, that captures correlations and motion components of the stent-graft. We report results for deformation models and registration accuracy for 5 patients.

Reliable segmentation of the left ventricle is a long sought objective in medical imaging for automatic retrieval of anatomical and pathological measurements and detection of malfunctions. In this paper, we propose a novel model-constrained approach to address this task. The method is based on an implicit representation of the shape model used in a shape registration framework with a Thin Plate Spline transform to retrieve possible deformations. The main innovation of our approach resides in the use of uncertainties defined on the registered shape to augment the training set and improve the robustness of the statistical deformable model. We use ICA to reduce the dimensionality of the space of deformations and provide a good separation of the different deformable parts of the heart. Furthermore the estimation of uncertainties is also introduced in the segmentation process which is addressed in a variational framework where prior knowledge and visual support are considered. The method lead to very promising qualitative and quantitative experimental results in CT.

This paper introduces a new denoising technique that consists in recovering the image using a filtering function adapted to the image content. The definition of such a function relies on the computation of similarity between pixels of a given neighborhood. Our contribution consists in the definition of a new similarity criterion which is more robust to noise. This measure is computed from a dictionary that is adapted to image content. The projection of the image content to this subspace are used then to define a metric between a pixel and the neighborhood ones. Very promising experimental results show the potential of our approach.

Tracking highly deforming structures in space and time arises in numerous applications in computer vision. Static Models are often referred to as linear combinations of a mean model and modes of variation learned from training examples. In Dynamic Modeling, the shape is represented as a function of shapes at previous time steps. In this paper, we introduce a novel technique that uses the spatial and the temporal information on the object deformation. We reformulate tracking as a high order time series prediction mechanism that adapts itself on-line to the newest results. Samples (toward dimensionality reduction) are represented in an orthogonal basis, and are introduced in an auto-regressive model that is determined through an optimization process in appropriate metric spaces. Toward capturing evolving deformations as well as cases that have not been part of the learning stage, a process that updates on-line both the orthogonal basis decomposition and the parameters of the autoregressive model is proposed. Experimental results with a nonstationary dynamic system prove adaptive AR models give better results than both stationary models and models learned over the whole sequence.

In this paper, we propose a novel model-based approach to recover 3D hand pose from 2D images through a compact articulated 3D hand model whose parameters are inferred in a Bayesian manner. To this end, we propose generative models for hand and background pixels leading to a loglikelihood objective function which aims at enclosing hand-like pixels within the silhouette of the projected 3D model while excluding background-like pixels.Segmentation and hand pose estimation are unified through the minimization of a single likelihood function, which is novel and improve overall robustness. We derive the gradient in the hand parameter space of such an area-based objective function, which is new and allows faster convergence rate than gradient free methods. Furthermore, we propose a new constrained variable metric gradient descent to speed up convergence and finally the so called smart particle filter is used to improve robustness through multiple hypotheses and to exploit temporal coherence. Very promising experimental results demonstrate the potentials of our approach. 1

We present a novel, variational and statistical approach for shape registration. Shapes of interest are implicitly embedded in a higher-dimensional space of distance transforms. In this implicit embedding space, registration is formulated in a hierarchical manner: the Mutual Information criterion supports various transformation models and is optimized to perform global registration; then, a B-spline-based Incremental Free Form Deformations (IFFD) model is used to minimize a Sum-of-Squared-Differences (SSD) measure and further recover a dense local nonrigid registration field. The key advantage of such framework is twofold: (1) it naturally deals with shapes of arbitrary dimension (2D, 3D, or higher) and arbitrary topology (multiple parts, closed/open) and (2) it preserves shape topology during local deformation and produces local registration fields that are smooth, continuous, and establish one-to-one correspondences. Its invariance to initial conditions is evaluated through empirical validation, and various hard 2D/3D geometric shape registration examples are used to show its robustness to noise, severe occlusion, and missing parts. We demonstrate the power of the proposed framework using two applications: one for statistical modeling of anatomical structures, another for 3D face scan registration and expression tracking. We also compare the performance of our algorithm with that of several other well-known shape registration algorithms.

Background modeling and subtraction to detect new or moving objects in a scene is an important component of many intelligent video applications. Compared to a single camera, the use of multiple cameras leads to better handling of shadows, specularities and illumination changes due to the utilization of geometric information. Although the result of stereo matching can be used as the feature for detection, it has been shown that the detection process can be made much faster by a simple subtraction of the intensities observed at stereo-generated conjugate pairs in the two views. The methodology however, suffers from false and missed detections due to some geometric considerations. In this paper, we perform a detailed analysis of such errors. Then, we propose a sensor configuration that eliminates false detections. Algorithms are also proposed that effectively eliminate most detection errors due to missed detections, specular reflections and objects being geometrically close to the background. Experiments on several scenes illustrate the utility and enhanced performance of the proposed approach compared to existing techniques.

In this paper, we introduce a new technique for shape modelling in the space of implicit polynomials. Registration consists of recovering an optimal one-to-one transformation of a higher order polynomial along with uncertainties measures that are determined according to the covariance matrix of the correspondences at the zero isosurface. In the modelling phase, these measures are used to weight the importance of the training samples phase according to a variable bandwidth non-parametric density estimation process. The selection of the most appropriate kernels to represent the training set is done through the maximum likelihood criterion. Excellent results for patterns of digits, related with the registration and the modelling aspects of our approach demonstrate the potentials of our method

In this paper, we propose a novel technique to represent and recover optical flow through free form deformations. Such a technique is based on representing the motion field using regular connected grids according to higher order polynomials, a compromise between dense motion estimation and parametric motion models. Optical flow is determined through the deformation of the grid - derived from the optimization of a cost function - and consequently of the underlying image structures towards satisfying the constant brightness constraint. Smoothness conditions are implicitly accounted for through the free form deformation approach. Promising results demonstrate the potentials of our approach.

We describe a stereo rectification method suitable for automatic 3D surveillance. We take advantage of the fact that in a typical urban scene, there is ordinarily a small number of dominant planes. Given two views of the scene, we align a dominant plane in one view with the other. Conjugate epipolar lines between the reference view and plane-aligned image become geometrically identical and can be added to the rectified image pair line by line. Selecting conjugate epipolar lines to cover the whole image is simplified since they are geometrically identical. In addition, the polarities of conjugate epipolar lines are automatically preserved by plane alignment, which simplifies stereo matching.

In this paper, we propose an edge-driven bidirectional geometric flow for boundary extraction. To this end, we combine the geodesic active contour flow and the gradient vector flow external force for snakes. The resulting motion equation is considered within a level set formulation, can deal with topological changes and important shape deformations. An efficient numerical schema is used for the flow implementation that exhibits robust behavior and has fast convergence rate. Promising results on real and synthetic images demonstrate the potentials of the flow.

Background modeling and subtraction is a core component in motion analysis. The central idea behind such module is to create a probabilistic representation of the static scene that is compared with the current input to perform subtraction. Such approach is efficient when the scene to be modeled refers to a static structure with limited perturbation. In this paper, we address the problem of modeling dynamic scenes where the assumption of a static background is not valid. Waving trees, beaches, escalators, natural scenes with rain or snow are examples. Inspired by the work proposed by Doretto et al. (2003), we propose an on-line auto-regressive model to capture and predict the behavior of such scenes. Towards detection of events we introduce a new metric that is based on a state-driven comparison between the prediction and the actual frame. Promising results demonstrate the potentials of the proposed framework.

Knowledge-based segmentation has been explored significantly in medical imaging. Prior anatomical knowledge can be used to define constraints that can improve performance of segmentation algorithms to physically corrupted and incomplete data. In this paper, the objective is to introduce such knowledge-based constraints while preserving the ability of dealing with local deformations. Toward this end, we propose a variational level set framework that can account for global shape consistency as well as for local deformations. In order to improve performance, the problems of segmentation and tracking of the structure of interest are dealt with simultaneously by introducing the notion of time in the process and looking for a solution that satisfies that prior constraints while being consistent along consecutive frames. Promising experimental results in magnetic resonance and ultrasonic cardiac images demonstrate the potentials of our approach.

In this paper, we propose a level set formulation to deal with the segmentation and registration of the left ventricle in Magnetic Resonance (MR) images. Our approach is based on the integration of visual information, anatomical constraints and a flexible shape-driven cardiac model. The visual information is expressed through an intensity-based grouping module. The anatomical constraint accounts for the relative positions of the structures of interest. Global shape consistency is introduced by seeking for the lowest potential of the distance between the solution and the prior model. Registration is obtained using the same criterion where the transformation that aligns the latest segmentation map to either the shape model or to the previous segmentation result (temporal domain) is to be recovered.

There has been an increase in the use of video surveillance and monitoring in public areas to improve safety and security. Change detection and crowding/congestion density estimation are two sub-tasks in a subway monitoring system. We propose a method that decomposes this problem into two steps. The first step consists of a change detection algorithm that distinguishes the background from the foreground. This is done using a discontinuity preserving MRF-based approach where the information from different sources (background subtraction, intensity modeling) is combined with spatial constraints to provide a smooth motion detection map. Then, the obtained change detection map is combined with a geometry module that performs a soft auto-calibration to estimate a measure of congestion of the observed area (platform). Extensive experimental results in a metro station of a metropolitan city demonstrates the performance and the potential of our method.

This paper presents a new variational framework for detecting and tracking multiple moving objects in image sequences. Motion detection is performed using a statistical framework for which the observed interframe difference density function is approximated using a mixture model. This model is composed of two components, namely, the static (background) and the mobile (moving objects) one. Both components are zero-mean and obey Laplacian or Gaussian law. This statistical framework is used to provide the motion detection boundaries. Additionally, the original frame is used to provide the moving object boundaries. Then, the detection and the tracking problem are addressed in a common framework that employs a geodesic active contour objective function. This function is minimized using a gradient descent method. A new approach named Hermes is proposed, which exploits aspects from the well-known front propagation algorithms and compares favorably to them. Very promising experimental results are provided using real video sequences.

This paper addresses the problem of tracking several non-rigid objects over a sequence of frames acquired from a static observer using boundary and region-based information under a coupled geodesic active contour framework. Given the current frame, a statistical analysis is performed on the observed difference frame which provides a measurement that distinguishes between the static and mobile regions in terms of conditional probabilities. An objective function is defined that integrates boundary-based and region-based module by seeking curves that attract the object boundaries and maximize the a posteriori segmentation probability on the interior curve regions with respect to intensity and motion properties. This function is minimized using a gradient descent method. The associated Euler-Lagrange PDE is implemented using a Level-Set approach, where a very fast front propagation algorithm evolves the initial curve towards the final tracking result. Very promising experimental results are provided using real video sequences.

This paper presents a variational method for supervised texture segmentation which is based on ideas coming from the curve propagation theory. We assume that a preferable texture pattern is known (e.g., the pattern that we want to distinguish from the rest of the image). The textured feature space is generated by filtering the input and the preferable pattern image using Gabor filters, and analyzing their responses as multi-component conditional probability density functions. The texture segmentation is obtained by minimizing a Geodesic Active Contour Model objective function where the boundary-based information is expressed via discontinuities on the statistical space associated with the multi-modal textured feature space. This function is minimized using a gradient descent method where the obtained PDE is implemented using a level set approach, that handles naturally the topological changes. Finally a fast method is used for the level set implementation. The performance of our method is demonstrated on a variety of synthetic and real textured images.

The paper presents a novel variational method for supervised texture segmentation. The textured feature space is generated by filtering the given textured images using isotropic and anisotropic filters, and analyzing their responses as multi-component conditional probability density functions. The texture segmentation is obtained by unifying region and boundary based information as an improved Geodesic Active Contour Model. The defined objective function is minimized using a gradient-descent method where a level set approach is used to implement the obtained PDE. According to this PDE, the curve propagation towards the final solution is guided by boundary and region based segmentation forces, and is constrained by a regularity force. The level set implementation is performed using a fast front propagation algorithm where topological changes are naturally handled. The performance of our method is demonstrated on a variety of synthetic and real textured frames.

This paper presents a framework for detecting and tracking moving objects in a sequence of images. Using a statistical approach, where the inter-frame difference is modeled by a mixture of two Laplacian or Gaussian distributions, and an energy minimization based approach, we reformulate the motion detection and tracking problem as a front propagation problem. The Euler-Lagrange equation of the designed energy functional is first derived and the flow minimizing the energy is then obtained. Following the work by Caselles et al. (1995) and Malladi et al. (1995), the contours to be detected and tracked are modeled as geodesic active contours evolving toward the minimum of the designed energy, under the influence of internal and external image dependent forces. Using the level set formulation scheme of Osher and Sethian (1988), complex curves can be detected and tracked and topological changes for the evolving curves are naturally managed. To reduce the computational cost required by a direct implementation, of the formulation scheme of Osher and Sethian (1988), a new approach exploiting aspects from the classical narrow band and fast marching methods is proposed and favorably compared to them. In order to further reduce the CPU time, a multi-scale approach has also been considered. Very promising experimental results are provided using real video sequences.

This paper presents a framework for detecting multiple moving moving objects in a sequence of images. Using a statistical approach, where the inter-frame difference is modeled by a mixture of two Laplacian distributions and a deformable contour-based energy minimization approach, we reformulate the motion detection problem as a front propagation problem. Following the work of geodesic active contours, we transform the moving objects detection problem into an equivalent problem of geodesic computation, which is solved using a level set formulation scheme. To reduce the computational cost required by a direct implementation of the formulation scheme the narrow band technique is used. In order to further reduce the CPU time, a multi-scale approach has also been considered. Very promising experimental results are provided using real video sequences.

In this paper we address an important issue in motion analysis: the detection of moving objects. A statistical approach is adopted in order to formulate the problem. The inter-frame difference is modeled by a mixture of Laplacian distributions, and a Gibbs random field is used for describing the label set. A new method to determine the regularization parameter is proposed, based on a voting technique. Then two different multiscale algorithms are evaluated, and the labeling problem is solved using either ICM (iterated conditional modes) or HCF (highest confidence first) algorithms. Experimental results are provided using synthetic and real video sequences.

Two important problems in motion analysis are addressed in this paper: change detection and moving object location. For the first problem, the inter-frame difference is modelized by a mixture of Laplacian distributions, a Gibbs random field is used for describing the label field, and HCF (highest confidence first) algorithm is used for solving the resulting optimization problem. The solution of the second problem is based on the observation of two successive frames alone. Using the results of change detection an adaptive statistical model for the couple of image intensities is identified. Then the labeling problem is solved using HCF algorithm. Results on real image sequences illustrate the efficiency of the proposed method.