Causal inference on networks faces challenges posed in part by violations of standard identification assumptions due to dependencies between treatment units. Although graph geometry fundamentally influences such dependencies, the potential of geometric tools for causal inference on networked treatment units is yet to be unlocked. Moreover, despite significant progress utilizing graph neural networks (GNNs) for causal inference on networks, methods for evaluating their achievable reliability without ground truth are lacking. In this work we establish for the first time a theoretical link between network geometry, the graph Ricci curvature in particular, and causal inference, formalizing the intrinsic challenges that negative curvature poses to estimating causal parameters. The Ricci curvature can then be used to assess the reliability of causal estimates in structured data, as we empirically demonstrate. Informed by this finding, we propose a method using the geometric Ricci flow to reduce causal effect estimation error in networked data, showcasing how this newfound connection between graph geometry and causal inference could improve GNN-based causal inference. Bridging graph geometry and causal inference, this paper opens the door to geometric techniques for improving causal estimation on networks.

Directionally sensitive radiomic features including the histogram of oriented gradient (HOG) have been shown to provide objective and quantitative measures for predicting disease outcomes in multiple cancers. However, radiomic features are sensitive to imaging variabilities including acquisition differences, imaging artifacts and noise, making them impractical for using in the clinic to inform patient care. We treat the problem of extracting robust local directionality features by mapping via optimal transport a given local image patch to an iso-intense patch of its mean. We decompose the transport map into sub-work costs each transporting in different directions. To test our approach, we evaluated the ability of the proposed approach to quantify tumor heterogeneity from magnetic resonance imaging (MRI) scans of brain glioblastoma multiforme, computed tomography (CT) scans of head and neck squamous cell carcinoma as well as longitudinal CT scans in lung cancer patients treated with immunotherapy. By considering the entropy difference of the extracted local directionality within tumor regions, we found that patients with higher entropy in their images, had significantly worse overall survival for all three datasets, which indicates that tumors that have images exhibiting flows in many directions may be more malignant. This may seem to reflect high tumor histologic grade or disorganization. Furthermore, by comparing the changes in entropy longitudinally using two imaging time points, we found patients with reduction in entropy from baseline CT are associated with longer overall survival (hazard ratio = 1.95, 95% confidence interval of 1.4-2.8, p = 1.65e-5). The proposed method provides a robust, training free approach to quantify the local directionality contained in images.

We present a novel approach for volume exploration that is versatile yet effective in isolating semantic structures in both noisy and clean data. Specifically, we describe a hierarchical active contours approach based on Bhattacharyya gradient flow which is easier to control, robust to noise, and can incorporate various types of statistical information to drive an edge-agnostic exploration process. To facilitate a time-bound user-driven volume exploration process that is applicable to a wide variety of data sources, we present an efficient multi-GPU implementation that (1) is approximately 400 times faster than a single thread CPU implementation, (2) allows hierarchical exploration of 2D and 3D images, (3) supports customization through multidimensional attribute spaces, and (4) is applicable to a variety of data sources and semantic structures. The exploration system follows a 2-step process. It first applies active contours to isolate semantically meaningful subsets of the volume. It then applies transfer functions to the isolated regions locally to produce clear and clutter-free visualizations. We show the effectiveness of our approach in isolating and visualizing structures-of-interest without needing any specialized segmentation methods on a variety of data sources, including 3D optical microscopy, multi-channel optical volumes, abdominal and chest CT, micro-CT, MRI, simulation, and synthetic data. We also gathered feedback from a medical trainee regarding the usefulness of our approach and discussion on potential applications in clinical workflows.

BACKGROUND: Compositional systems, represented as parts of some whole, are ubiquitous. They encompass the abundances of proteins in a cell, the distribution of organisms in nature, and the stoichiometry of the most basic chemical reactions. Thus, a central goal is to understand how such processes emerge from the behaviors of their components and their pairwise interactions. Such a study, however, is challenging for two key reasons. Firstly, such systems are complex and depend, often stochastically, on their constituent parts. Secondly, the data lie on a simplex which influences their correlations. RESULTS: To resolve both of these issues, we provide a general and data-driven modeling tool for compositional systems called Compositional Maximum Entropy (CME). By integrating the prior geometric structure of compositions with sample-specific information, CME infers the underlying multivariate relationships between the constituent components. We provide two proofs of principle. First, we measure the relative abundances of different bacteria and infer how they interact. Second, we show that our method outperforms a common alternative for the extraction of gene-gene interactions in triple-negative breast cancer. CONCLUSIONS: CME provides novel and biologically-intuitive insights and is promising as a comprehensive quantitative framework for compositional data.

The remarkable growth of multi-platform genomic profiles has led to the challenge of multiomics data integration. In this study, we present a novel network-based multiomics clustering founded on the Wasserstein distance from optimal mass transport. This distance has many important geometric properties making it a suitable choice for application in machine learning and clustering. Our proposed method of aggregating multiomics and Wasserstein distance clustering (aWCluster) is applied to breast carcinoma as well as bladder carcinoma, colorectal adenocarcinoma, renal carcinoma, lung non-small cell adenocarcinoma, and endometrial carcinoma from The Cancer Genome Atlas project. Subtypes were characterized by the concordant effect of mRNA expression, DNA copy number alteration, and DNA methylation of genes and their neighbors in the interaction network. aWCluster successfully clusters all cancer types into classes with significantly different survival rates. Also, a gene ontology enrichment analysis of significant genes in the low survival subgroup of breast cancer leads to the well-known phenomenon of tumor hypoxia and the transcription factor ETS1 whose expression is induced by hypoxia. We believe aWCluster has the potential to discover novel subtypes and biomarkers by accentuating the genes that have concordant multiomics measurements in their interaction network, which are challenging to find without the network inference or with single omics analysis.

MOTIVATION: Convolutional neural networks (CNNs) have achieved great success in the areas of image processing and computer vision, handling grid-structured inputs and efficiently capturing local dependencies through multiple levels of abstraction. However, a lack of interpretability remains a key barrier to the adoption of deep neural networks, particularly in predictive modeling of disease outcomes. Moreover, because biological array data are generally represented in a non-grid structured format, CNNs cannot be applied directly. RESULTS: To address these issues, we propose a novel method, called PathCNN, that constructs an interpretable CNN model on integrated multi-omics data using a newly defined pathway image. PathCNN showed promising predictive performance in differentiating between long-term survival (LTS) and non-LTS when applied to glioblastoma multiforme (GBM). The adoption of a visualization tool coupled with statistical analysis enabled the identification of plausible pathways associated with survival in GBM. In summary, PathCNN demonstrates that CNNs can be effectively applied to multi-omics data in an interpretable manner, resulting in promising predictive power while identifying key biological correlates of disease. AVAILABILITY AND IMPLEMENTATION: The source code is freely available at: https://github.com/mskspi/PathCNN.

More than half of all cancer patients receive radiotherapy in their treatment process. However, our understanding of abnormal transcriptional responses to radiation remains poor. In this study, we employ an extended definition of Ollivier-Ricci curvature based on LI-Wasserstein distance to investigate genes and biological processes associated with ionizing radiation (IR) and ultraviolet radiation (UV) exposure using a microarray dataset. Gene expression levels were modeled on a gene interaction topology downloaded from the Human Protein Reference Database (HPRD). This was performed for IR, UV, and mock datasets, separately. The difference curvature value between IR and mock graphs (also between UV and mock) for each gene was used as a metric to estimate the extent to which the gene responds to radiation. We found that in comparison of the top 200 genes identified from IR and UV graphs, about 20~30% genes were overlapping. Through gene ontology enrichment analysis, we found that the metabolic-related biological process was highly associated with both IR and UV radiation exposure.

This work presents a deformable point set registration algorithm that seeks an optimal set of radial basis functions to describe the registration. A novel, global optimization approach is introduced composed of simulated annealing with a particle filter based generator function to perform the registration. It is shown how constraints can be incorporated into this framework. A constraint on the deformation is enforced whose role is to ensure physically meaningful fields (i.e., invertible). Further, examples in which landmark constraints serve to guide the registration are shown. Results on 2D and 3D data demonstrate the algorithm's robustness to noise and missing information.

In multiatlas segmentation, one typically registers several atlases to the novel image, and their respective segmented label images are transformed and fused to form the final segmentation. In this work, we provide a new dynamical system perspective for multiatlas segmentation, inspired by the following fact: The transformation that aligns the current atlas to the novel image can be not only computed by direct registration but also inferred from the transformation that aligns the previous atlas to the image together with the transformation between the two atlases. This process is similar to the global positioning system on a vehicle, which gets position by inquiring from the satellite and by employing the previous location and velocity-neither answer in isolation being perfect. To solve this problem, a dynamical system scheme is crucial to combine the two pieces of information; for example, a Kalman filtering scheme is used. Accordingly, in this work, a Kalman multiatlas segmentation is proposed to stabilize the global/affine registration step. The contributions of this work are twofold. First, it provides a new dynamical systematic perspective for standard independent multiatlas registrations, and it is solved by Kalman filtering. Second, with very little extra computation, it can be combined with most existing multiatlas segmentation schemes for better registration/segmentation accuracy.

The left ventricular myocardium plays a key role in the entire circulation system and an automatic delineation of the myocardium is a prerequisite for most of the subsequent functional analysis. In this paper, we present a complete system for an automatic segmentation of the left ventricular myocardium from cardiac computed tomography (CT) images using the shape information from images to be segmented. The system follows a coarse-to-fine strategy by first localizing the left ventricle and then deforming the myocardial surfaces of the left ventricle to refine the segmentation. In particular, the blood pool of a CT image is extracted and represented as a triangulated surface. Then, the left ventricle is localized as a salient component on this surface using geometric and anatomical characteristics. After that, the myocardial surfaces are initialized from the localization result and evolved by applying forces from the image intensities with a constraint based on the initial myocardial surface locations. The proposed framework has been validated on 34-human and 12-pig CT images, and the robustness and accuracy are demonstrated.

In image segmentation, we are often interested in using certain quantities to characterize the object, and perform the classification based on criteria such as mean intensity, gradient magnitude, and responses to certain predefined filters. Unfortunately, in many cases such quantities are not adequate to model complex textured objects. Along a different line of research, the sparse characteristic of natural signals has been recognized and studied in recent years. Therefore, how such sparsity can be utilized, in a non-parametric way, to model the object texture and assist the textural image segmentation process is studied in this paper, and a segmentation scheme based on the sparse representation of the texture information is proposed. More explicitly, the texture is encoded by the dictionaries constructed from the user initialization. Then, an active contour is evolved to optimize the fidelity of the representation provided by the dictionary of the target. In doing so, not only a non-parametric texture modeling technique is provided, but also the sparsity of the representation guarantees the computation efficiency. The experiments are carried out on the publicly available image data sets which contain a large variety of texture images, to analyze the user interaction, performance statistics, and to highlight the algorithm's capability of robustly extracting textured regions from an image.

Computational vision-based flame detection has drawn significant attention in the past decade with camera surveillance systems becoming ubiquitous. Whereas many discriminating features, such as color, shape, texture, etc., have been employed in the literature, this paper proposes a set of motion features based on motion estimators. The key idea consists of exploiting the difference between the turbulent, fast, fire motion, and the structured, rigid motion of other objects. Since classical optical flow methods do not model the characteristics of fire motion (e.g., non-smoothness of motion, non-constancy of intensity), two optical flow methods are specifically designed for the fire detection task: optimal mass transport models fire with dynamic texture, while a data-driven optical flow scheme models saturated flames. Then, characteristic features related to the flow magnitudes and directions are computed from the flow fields to discriminate between fire and non-fire motion. The proposed features are tested on a large video database to demonstrate their practical usefulness. Moreover, a novel evaluation method is proposed by fire simulations that allow for a controlled environment to analyze parameter influences, such as flame saturation, spatial resolution, frame rate, and random noise.

The planning and evaluation of left atrial ablation procedures are commonly based on the segmentation of the left atrium, which is a challenging task due to large anatomical variations. In this paper, we propose an automatic approach for segmenting the left atrium from magnetic resonance imagery. The segmentation problem is formulated as a problem in variational region growing. In particular, the method starts locally by searching for a seed region of the left atrium from an MR slice. A global constraint is imposed by applying a shape prior to the left atrium represented by Zernike moments. The overall growing process is guided by the robust statistics of intensities from the seed region along with the shape prior to capture the entire atrial region. The robustness and accuracy of our approach are demonstrated by experimental results from 64 human MR images.

Segmentation of injured or unusual anatomic structures in medical imagery is a problem that has continued to elude fully automated solutions. In this paper, the goal of easy-to-use and consistent interactive segmentation is transformed into a control synthesis problem. A nominal level set partial differential equation (PDE) is assumed to be given; this open-loop system achieves correct segmentation under ideal conditions, but does not agree with a human expert's ideal boundary for real image data. Perturbing the state and dynamics of a level set PDE via the accumulated user input and an observer-like system leads to desirable closed-loop behavior. The input structure is designed such that a user can stabilize the boundary in some desired state without needing to understand any mathematical parameters. Effectiveness of the technique is illustrated with applications to the challenging segmentations of a patellar tendon in magnetic resonance and a shattered femur in computed tomography.

Extracting anatomical and functional significant structures renders one of the important tasks for both the theoretical study of the medical image analysis, and the clinical and practical community. In the past, much work has been dedicated only to the algorithmic development. Nevertheless, for clinical end users, a well designed algorithm with an interactive software is necessary for an algorithm to be utilized in their daily work. Furthermore, the software would better be open sourced in order to be used and validated by not only the authors but also the entire community. Therefore, the contribution of the present work is twofolds: first, we propose a new robust statistics based conformal metric and the conformal area driven multiple active contour framework, to simultaneously extract multiple targets from MR and CT medical imagery in 3D. Second, an open source graphically interactive 3D segmentation tool based on the aforementioned contour evolution is implemented and is publicly available for end users on multiple platforms. In using this software for the segmentation task, the process is initiated by the user drawn strokes (seeds) in the target region in the image. Then, the local robust statistics are used to describe the object features, and such features are learned adaptively from the seeds under a non-parametric estimation scheme. Subsequently, several active contours evolve simultaneously with their interactions being motivated by the principles of action and reaction-this not only guarantees mutual exclusiveness among the contours, but also no longer relies upon the assumption that the multiple objects fill the entire image domain, which was tacitly or explicitly assumed in many previous works. In doing so, the contours interact and converge to equilibrium at the desired positions of the desired multiple objects. Furthermore, with the aim of not only validating the algorithm and the software, but also demonstrating how the tool is to be used, we provide the reader reproducible experiments that demonstrate the capability of the proposed segmentation tool on several public available data sets.

The registration of a pair of point sets as well as the estimation of their pointwise correspondences is a challenging and important task in computer vision. In this paper, we present a method to estimate the diffeomorphic deformation, together with the pointwise correspondences, between a pair of point sets. Many of the registration problems are iteratively solved by estimating the correspondence, locally optimizing certain cost functionals over the rigid or similarity or affine transformation group, then estimating the correspondence again, and so on. This type of approach, however, is well-known to be susceptible to suboptimal local solutions. In this paper, we first adopt the perspective of treating the registration as a posterior estimation optimization problem and solve it accordingly via a particle-filtering framework. Second, within such a framework, the diffeomorphic registration is performed to correct the nonlinear deformation of the points. In doing so, we provide a solution less susceptible to local minima. We provide the experimental results, which include challenging medical data sets where the two point sets differ by 180 (°) rotation as well as local deformations, to highlight the algorithm's capability of robustly finding the more globally optimal solution for the registration task.

Active contours are very popular tools for video tracking and image segmentation. Parameterized contours are used due to their fast evolution and have become the method of choice in the Sobolev context. Unfortunately, these contours are not easily adaptable to topological changes, and they may sometimes develop undesirable loops, resulting in erroneous results. To solve such topological problems, one needs an algorithm for contour self-crossing detection. We propose a simple methodology via simple techniques from differential topology. The detection is accomplished by inspecting the total net change of a given contour's angle, without point sorting and plane sweeping. We discuss the efficient implementation of the algorithm. We also provide algorithms for locating crossings by angle considerations and by plotting the four-connected lines between the discrete contour points. The proposed algorithms can be added to any parametric active-contour model. We show examples of successful tracking in real-world video sequences by Sobolev active contours and the proposed algorithms and provide ideas for further research.

In this paper, we present a visual pose tracking algorithm based on Monte Carlo sampling of special Euclidean group SE(3) and knowledge of a 3D model. In general, the relative pose of an object in 3D space can be described by sequential transformation matrices at each time step. Thus, the objective of this work is to find a transformation matrix in SE(3) so that the projection of an object transformed by this matrix coincides with an object of interest in the 2D image plane. To do this, first, the set of these transformation matrices is randomly generated via an autoregressive model. Next, 3D trans- formation is performed on a 3D model by these matrices. Finally, a region-based energy model is designed to evaluate the optimality of a transformed model's projection. Experimental results demonstrate the robustness of the proposed method in several tracking scenarios.

Video surveillance systems are often used to detect anomalies: rare events which demand a human response, such as a fire breaking out. Automated detection algorithms enable vastly more video data to be processed than would be possible otherwise. This note presents a video analytics framework for the detection of amorphous and unstructured anomalies such as fire, targets in deep turbulence, or objects behind a smoke-screen. Our approach uses an off-line supervised training phase together with an on-line Bayesian procedure: we form a prior, compute a likelihood function, and then update the posterior estimate. The prior consists of candidate image-regions generated by a weak classifier. Likelihood of a candidate region containing an object of interest at each time step is computed from the photometric observations coupled with an optimal-mass-transport optical-flow field. The posterior is sequentially updated by tracking image regions over time and space using active contours thus extracting samples from a properly aligned batch of images. The general theory is applied to the video-fire-detection problem with excellent detection performance across substantially varying scenarios which are not used for training.

We propose a particle filtering framework for rigid registration of a model image to a time-series of partially observed images. The method incorporates a model-based segmentation technique in order to track the pose dynamics of an underlying observed object with time. An applicable algorithm is derived by employing the proposed framework for registration of a 3D model of an anatomical structure, which was segmented from preoperative images, to consecutive axial 2D slices of a magnetic resonance imaging (MRI) scan, which are acquired intraoperatively over time. The process is fast and robust with respect to image noise and clutter, variations of illumination, and different imaging modalities.

In this work, we present a nonrigid approach to jointly solving the tasks of 2D-3D pose estimation and 2D image segmentation. In general, most frameworks that couple both pose estimation and segmentation assume that one has exact knowledge of the 3D object. However, under nonideal conditions, this assumption may be violated if only a general class to which a given shape belongs is given (e.g., cars, boats, or planes). Thus, we propose to solve the 2D-3D pose estimation and 2D image segmentation via nonlinear manifold learning of 3D embedded shapes for a general class of objects or deformations for which one may not be able to associate a skeleton model. Thus, the novelty of our method is threefold: first, we present and derive a gradient flow for the task of nonrigid pose estimation and segmentation. Second, due to the possible nonlinear structures of one's training set, we evolve the pre-image obtained through kernel PCA for the task of shape analysis. Third, we show that the derivation for shape weights is general. This allows us to use various kernels, as well as other statistical learning methodologies, with only minimal changes needing to be made to the overall shape evolution scheme. In contrast with other techniques, we approach the nonrigid problem, which is an infinite-dimensional task, with a finite-dimensional optimization scheme. More importantly, we do not explicitly need to know the interaction between various shapes such as that needed for skeleton models as this is done implicitly through shape learning. We provide experimental results on several challenging pose estimation and segmentation scenarios.

Visual tracking of arbitrary targets in clutter is important for a wide range of military and civilian applications. We propose a general framework for the tracking of scaled and partially occluded targets, which do not necessarily have prominent features. The algorithm proposed in the present paper utilizes a modified normalized cross-correlation as the likelihood for a particle filter. The algorithm divides the template, selected by the user in the first video frame, into numerous patches. The matching process of these patches by particle filtering allows one to handle the target's occlusions and scaling. Experimental results with fixed rectangular templates show that the method is reliable for videos with nonstationary, noisy, and cluttered background, and provides accurate trajectories in cases of target translation, scaling, and occlusion.

The local conformation of RNA molecules is an important factor in determining their catalytic and binding properties. The analysis of such conformations is particularly difficult due to the large number of degrees of freedom, such as the measured torsion angles per residue and the interatomic distances among interacting residues. In this work, we use a nearest-neighbor search method based on the statistical mechanical Potts model to find clusters in the RNA conformational space. The proposed technique is mostly automatic and may be applied to problems, where there is no prior knowledge on the structure of the data space in contrast to many other clustering techniques. Results are reported for both single residue conformations, where the parameter set of the data space includes four to seven torsional angles, and base pair geometries, where the data space is reduced to two dimensions. Moreover, new results are reported for base stacking geometries. For the first two cases, i.e., single residue conformations and base pair geometries, we get a very good match between the results of the proposed clustering method and the known classifications with only few exceptions. For the case of base stacking geometries, we validate our classification with respect to geometrical constraints and describe the content, and the geometry of the new clusters.

In this paper, we propose an approach for tracking an object of interest based on 3-D range data. We employ particle filtering and active contours to simultaneously estimate the global motion of the object and its local deformations. The proposed algorithm takes advantage of range information to deal with the challenging (but common) situation in which the tracked object disappears from the image domain entirely and reappears later. To cope with this problem, a method based on principle component analysis (PCA) of shape information is proposed. In the proposed method, if the target disappears out of frame, shape similarity energy is used to detect target candidates that match a template shape learned online from previously observed frames. Thus, we require no a priori knowledge of the target's shape. Experimental results show the practical applicability and robustness of the proposed algorithm in realistic tracking scenarios.

Detection of fire and smoke in video is of practical and theoretical interest. In this paper, we propose the use of optimal mass transport (OMT) optical flow as a low-dimensional descriptor of these complex processes. The detection process is posed as a supervised Bayesian classification problem with spatio-temporal neighborhoods of pixels;feature vectors are composed of OMT velocities and R,G,B color channels. The classifier is implemented as a single-hidden-layer neural network. Sample results show probability of pixels belonging to fire or smoke. In particular, the classifier successfully distinguishes between smoke and similarly colored white wall, as well as fire from a similarly colored background.

We present an approach for tracking a moving object based on range information in stereoscopic temporal imagery. Range information is filtered by the proposed dynamic scheme to improve the quality of active contour segmentation, and to better estimate the global motion of the object. Region-based active contours using Bhattacharyya gradient flow is exploited due to its robustness to noise of a cluttered depth map. Such a sensor-fusion approach of an active contour segmentation of the image data with the statistics of a depth map provides a state estimate that is more accurate than what would be possible with either of the two alone. Experimental results demonstrate the applicability of the proposed method on several stereoscopic sequences.

In this paper, we propose a particle filtering approach for the problem of registering two point sets that differ by a rigid body transformation. Typically, registration algorithms compute the transformation parameters by maximizing a metric given an estimate of the correspondence between points across the two sets of interest. This can be viewed as a posterior estimation problem, in which the corresponding distribution can naturally be estimated using a particle filter. In this work, we treat motion as a local variation in pose parameters obtained by running a few iterations of a certain local optimizer. Employing this idea, we introduce stochastic motion dynamics to widen the narrow band of convergence often found in local optimizer approaches for registration. Thus, the novelty of our method is threefold: First, we employ a particle filtering scheme to drive the point set registration process. Second, we present a local optimizer that is motivated by the correlation measure. Third, we increase the robustness of the registration performance by introducing a dynamic model of uncertainty for the transformation parameters. In contrast with other techniques, our approach requires no annealing schedule, which results in a reduction in computational complexity (with respect to particle size) as well as maintains the temporal coherency of the state (no loss of information). Also unlike some alternative approaches for point set registration, we make no geometric assumptions on the two data sets. Experimental results are provided that demonstrate the robustness of the algorithm to initialization, noise, missing structures, and/or differing point densities in each set, on several challenging 2D and 3D registration scenarios.

In this work, we present an approach to jointly segment a rigid object in a two-dimensional (2D) image and estimate its three-dimensional (3D) pose, using the knowledge of a 3D model. We naturally couple the two processes together into a shape optimization problem and minimize a unique energy functional through a variational approach. Our methodology differs from the standard monocular 3D pose estimation algorithms since it does not rely on local image features. Instead, we use global image statistics to drive the pose estimation process. This confers a satisfying level of robustness to noise and initialization for our algorithm and bypasses the need to establish correspondences between image and object features. Moreover, our methodology possesses the typical qualities of region-based active contour techniques with shape priors, such as robustness to occlusions or missing information, without the need to evolve an infinite dimensional curve. Another novelty of the proposed contribution is to use a unique 3D model surface of the object, instead of learning a large collection of 2D shapes to accommodate the diverse aspects that a 3D object can take when imaged by a camera. Experimental results on both synthetic and real images are provided, which highlight the robust performance of the technique in challenging tracking and segmentation applications.

We propose algorithms for tracking the boundary contour of a deforming object from an image sequence, when the nonaffine (local) deformation over consecutive frames is large and there is overlapping clutter, occlusions, low contrast, or outlier imagery. When the object is arbitrarily deforming, each, or at least most, contour points can move independently. Contour deformation then forms an infinite (in practice, very large), dimensional space. Direct application of particle filters (PF) for large dimensional problems is impractically expensive. However, in most real problems, at any given time, most of the contour deformation occurs in a small number of dimensions ("effective basis space") while the residual deformation in the rest of the state space ("residual space") is small. This property enables us to apply the particle filtering with mode tracking (PF-MT) idea that was proposed for such large dimensional problems in recent work. Since most contour deformation is low spatial frequency, we propose to use the space of deformation at a subsampled set of locations as the effective basis space. The resulting algorithm is called deform PF-MT. It requires significant modifications compared to the original PF-MT because the space of contours is a non-Euclidean infinite dimensional space.

Extracting the prostate from magnetic resonance (MR) imagery is a challenging and important task for medical image analysis and surgical planning. We present in this work a unified shape-based framework to extract the prostate from MR prostate imagery. In many cases, shape-based segmentation is a two-part problem. First, one must properly align a set of training shapes such that any variation in shape is not due to pose. Then segmentation can be performed under the constraint of the learnt shape. However, the general registration task of prostate shapes becomes increasingly difficult due to the large variations in pose and shape in the training sets, and is not readily handled through existing techniques. Thus, the contributions of this paper are twofold. We first explicitly address the registration problem by representing the shapes of a training set as point clouds. In doing so, we are able to exploit the more global aspects of registration via a certain particle filtering based scheme. In addition, once the shapes have been registered, a cost functional is designed to incorporate both the local image statistics as well as the learnt shape prior. We provide experimental results, which include several challenging clinical data sets, to highlight the algorithm's capability of robustly handling supine/prone prostate registration and the overall segmentation task.

This work provides a model for tubular structures, and devises an algorithm to automatically extract tubular anatomical structures from medical imagery. Our model fits many anatomical structures in medical imagery, in particular, various fiber bundles in the brain (imaged through diffusion-weighted magnetic resonance (DW-MRI)) such as the cingulum bundle, and blood vessel trees in computed tomography angiograms (CTAs). Extraction of the cingulum bundle is of interest because of possible ties to schizophrenia, and extracting blood vessels is helpful in the diagnosis of cardiovascular diseases. The tubular model we propose has advantages over many existing approaches in literature: fewer degrees-of-freedom over a general deformable surface hence energies defined on such tubes are less sensitive to undesirable local minima, and the tube (in 3-D) can be naturally represented by a 4-D curve (a radius function and centerline), which leads to computationally less costly algorithms and has the advantage that the centerline of the tube is obtained without additional effort. Our model also generalizes to tubular trees, and the extraction algorithm that we design automatically detects and evolves branches of the tree. We demonstrate the performance of our algorithm on 20 datasets of DW-MRI data and 32 datasets of CTA, and quantify the results of our algorithm when expert segmentations are available.

In this paper, we present a novel method for texture mapping of closed surfaces. Our method is based on the technique of optimal mass transport (also known as the "earth-mover's metric"). This is a classical problem that concerns determining the optimal way, in the sense of minimal transportation cost, of moving a pile of soil from one site to another. In our context, the resulting mapping is area preserving and minimizes angle distortion in the optimal mass sense. Indeed, we first begin with an angle-preserving mapping (which may greatly distort area) and then correct it using the mass transport procedure derived via a certain gradient flow. In order to obtain fast convergence to the optimal mapping, we incorporate a multiresolution scheme into our flow. We also use ideas from discrete exterior calculus in our computations.

In this work, we present a non-rigid approach to jointly solve the tasks of 2D-3D pose estimation and 2D image segmentation. In general, most frameworks which couple both pose estimation and segmentation assume that one has the exact knowledge of the 3D object. However, in non-ideal conditions, this assumption may be violated if only a general class to which a given shape belongs to is given (e.g., cars, boats, or planes). Thus, the key contribution in this work is to solve the 2D-3D pose estimation and 2D image segmentation for a general class of objects or deformations for which one may not be able to associate a skeleton model. Moreover, the resulting scheme can be viewed as an extension of the framework presented in, in which we include the knowledge of multiple 3D models rather than assuming the exact knowledge of a single 3D shape prior. We provide experimental results that highlight the algorithm's robustness to noise, clutter, occlusion, and shape recovery on several challenging pose estimation and segmentation scenarios.

In this paper, we propose a particle filtering approach for the problem of registering two point sets that differ by a rigid body transformation. Typically, registration algorithms compute the transformation parameters by maximizing a metric given an estimate of the correspondence between points across the two sets of interest. This can be viewed as a posterior estimation problem, in which the corresponding distribution can naturally be estimated using a particle filter. In this work, we treat motion as a local variation in pose parameters obtained from running a few iterations of the standard Iterative Closest Point (ICP) algorithm. Employing this idea, we introduce stochastic motion dynamics to widen the narrow band of convergence often found in local optimizer functions used to tackle the registration task. Thus, the novelty of our method is twofold: Firstly, we employ a particle filtering scheme to drive the point set registration process. Secondly, we increase the robustness of the registration performance by introducing a dynamic model of uncertainty for the transformation parameters. In contrast with other techniques, our approach requires no annealing schedule, which results in a reduction in computational complexity as well as maintains the temporal coherency of the state (no loss of information). Also, unlike most alternative approaches for point set registration, we make no geometric assumptions on the two data sets. Experimental results are provided that demonstrate the robustness of the algorithm to initialization, noise, missing structures or differing point densities in each sets, on challenging 2D and 3D registration tasks. 1.

In this paper, we describe a region-based active contour technique to perform image segmentation. We propose an energy functional that realizes an explicit trade-off between the (current) image segmentation obtained from a curve and the (implied) segmentation obtained from dynamically thresholding the image. In contrast with standard region-based techniques, the resulting variational approach bypasses the need to fit (a priori chosen) statistical models to the object and the background. Our technique performs segmentation based on geometric considerations of the image and contour, instead of statistical ones. The resulting flow leads to very reasonable segmentations as shown by several illustrative examples.

We propose an approach for non-rigid tracking that represents objects by their set of distribution parameters. Compared to joint histogram representations, a set of parameters such as mixed moments provides a significantly reduced size representation. The discriminating power is comparable to that of the corresponding full high-dimensional histogram yet at far less spatial and computational complexity. The proposed method is robust in the presence of noise and illumination changes, and provides a natural extension to the use of mixture models. Experiments demonstrate that the proposed method outperforms both full color mean-shift and global covariance searches.

We propose a tracking system that is especially well-suited to tracking targets which change drastically in size or appearance. To accomplish this, we employ a fast, two phase template matching algorithm along with a periodic template update method. The template matching step ensures accurate localization while the template update scheme allows the target model to change over time along with the appearance of the target. Furthermore, the algorithm can deliver real-time results even when targets are very large. We demonstrate the proposed method with good results on several sequences showing targets which exhibit large changes in size, shape, and appearance.

Segmentation involves separating an object from the background in a given image. The use of image information alone often leads to poor segmentation results due to the presence of noise, clutter or occlusion. The introduction of shape priors in the geometric active contour (GAC) framework has proved to be an effective way to ameliorate some of these problems. In this work, we propose a novel segmentation method combining image information with prior shape knowledge, using level-sets. Following the work of Leventon et al., we propose to revisit the use of PCA to introduce prior knowledge about shapes in a more robust manner. We utilize kernel PCA (KPCA) and show that this method outperforms linear PCA by allowing only those shapes that are close enough to the training data. In our segmentation framework, shape knowledge and image information are encoded into two energy functionals entirely described in terms of shapes. This consistent description permits to fully take advantage of the Kernel PCA methodology and leads to promising segmentation results. In particular, our shape-driven segmentation technique allows for the simultaneous encoding of multiple types of shapes, and offers a convincing level of robustness with respect to noise, occlusions, or smearing.

In this paper, we propose an image segmentation technique based on augmenting the conformal (or geodesic) active contour framework with directional information. In the isotropic case, the Euclidean metric is locally multiplied by a scalar conformal factor based on image information such that the weighted length of curves lying on points of interest (typically edges) is small. The conformal factor which is chosen depends only upon position and is in this sense isotropic. While directional information has been studied previously for other segmentation frameworks, here we show that if one desires to add directionality in the conformal active contour framework, then one gets a well-defined minimization problem in the case that the factor defines a Finsler metric. Optimal curves may be obtained using the calculus of variations or dynamic programming based schemes. Finally we demonstrate the technique by extracting roads from aerial imagery, blood vessels from medical angiograms, and neural tracts from diffusion-weighted magnetic resonance imagery.

This paper proposes a deterministic observer framework for visual tracking based on non-parametric implicit (level-set) curve descriptions. The observer is continuous-discrete, with continuous-time system dynamics and discrete-time measurements. Its state-space consists of an estimated curve position augmented by additional states (e.g., velocities) associated with every point on the estimated curve. Multiple simulation models are proposed for state prediction. Measurements are performed through standard static segmentation algorithms and optical-flow computations. Special emphasis is given to the geometric formulation of the overall dynamical system. The discrete-time measurements lead to the problem of geometric curve interpolation and the discrete-time filtering of quantities propagated along with the estimated curve. Interpolation and filtering are intimately linked to the correspondence problem between curves. Correspondences are established by a Laplace-equation approach. The proposed scheme is implemented completely implicitly (by Eulerian numerical solutions of transport equations) and thus naturally allows for topological changes and subpixel accuracy on the computational grid.

In this paper, we propose a natural framework that allows any region-based segmentation energy to be re-formulated in a local way. We consider local rather than global image statistics and evolve a contour based on local information. Localized contours are capable of segmenting objects with heterogeneous feature profiles that would be difficult to capture correctly using a standard global method. The presented technique is versatile enough to be used with any global region-based active contour energy and instill in it the benefits of localization. We describe this framework and demonstrate the localization of three well-known energies in order to illustrate how our framework can be applied to any energy. We then compare each localized energy to its global counterpart to show the improvements that can be achieved. Next, an in-depth study of the behaviors of these energies in response to the degree of localization is given. Finally, we show results on challenging images to illustrate the robust and accurate segmentations that are possible with this new class of active contour models.

In this paper, we describe an approach to the problem of simultaneously enhancing image sequences and tracking the objects of interest represented by the latter. The enhancement part of the algorithm is based on Bayesian wavelet denoising, which has been chosen due to its exceptional ability to incorporate diverse a priori information into the process of image recovery. In particular, we demonstrate that, in dynamic settings, useful statistical priors can come both from some reasonable assumptions on the properties of the image to be enhanced as well as from the images that have already been observed before the current scene. Using such priors forms the main contribution of the present paper which is the proposal of the dynamic denoising as a tool for simultaneously enhancing and tracking image sequences. Within the proposed framework, the previous observations of a dynamic scene are employed to enhance its present observation. The mechanism that allows the fusion of the information within successive image frames is Bayesian estimation, while transferring the useful information between the images is governed by a Kalman filter that is used for both prediction and estimation of the dynamics of tracked objects. Therefore, in this methodology, the processes of target tracking and image enhancement "collaborate" in an interlacing manner, rather than being applied separately. The dynamic denoising is demonstrated on several examples of SAR imagery. The results demonstrated in this paper indicate a number of advantages of the proposed dynamic denoising over "static" approaches, in which the tracking images are enhanced independently of each other.

The problem of segmentation of tracking sequences is of central importance in a multitude of applications. In the current paper, a different approach to the problem is discussed. Specifically, the proposed segmentation algorithm is implemented in conjunction with estimation of the dynamic parameters of moving objects represented by the tracking sequence. While the information on objects' motion allows one to transfer some valuable segmentation priors along the tracking sequence, the segmentation allows substantially reducing the complexity of motion estimation, thereby facilitating the computation. Thus, in the proposed methodology, the processes of segmentation and motion estimation work simultaneously, in a sort of "collaborative" manner. The Bayesian estimation framework is used here to perform the segmentation, while Kalman filtering is used to estimate the motion and to convey useful segmentation information along the image sequence. The proposed method is demonstrated on a number of both computed-simulated and real-life examples, and the obtained results indicate its advantages over some alternative approaches.

The ten papers in this special section focus on computer vision for intravascular and intracardiac imaging. The papers are summarized here.

Presented at British Machine Vision Conference 2007, University of Warwick, UK, September 10-13, 2007.

Presented at British Machine Vision Conference 2007, University of Warwick, UK, September 10-13, 2007.

In this paper, we present a novel directional level set segmentation framework employing the theory of Finsler active contours. The framework provides a natural way to perform segmentation of image data in oriented domains. We share examples of this technique on diffusion-weighted magnetic resonance imagery (DW-MRI) for the segmentation of neural fiber bundles and we show examples of texture based segmentation using structure tensors. We also demonstrate that for some applications higher accuracy is achieved by the proposed framework than by level set methods that employ Riemannian metrics. This gain is attributed to the relaxation of the tensor model constraint which is imposed upon the metric in the Riemannian case. 1

Presented at British Machine Vision Conference 2007, University of Warwick, UK, September 10-13, 2007.

Presented at British Machine Vision Conference 2007, University of Warwick, UK, September 10-13, 2007.

This paper proposes a novel method to apply the standard graph cut technique to segmenting multimodal tensor valued images. The Riemannian nature of the tensor space is explicitly taken into account by first mapping the data to a Euclidean space where non-parametric kernel density estimates of the regional distributions may be calculated from user initialized regions. These distributions are then used as regional priors in calculating graph edge weights. Hence this approach utilizes the true variation of the tensor data by respecting its Riemannian structure in calculating distances when forming probability distributions. Further, the non-parametric model generalizes to arbitrary tensor distribution unlike the Gaussian assumption made in previous works. Casting the segmentation problem in a graph cut framework yields a segmentation robust with respect to initialization on the data tested.

In this note, we propose a method to perform segmentation on the tensor manifold, that is, the space of positive definite matrices of given dimension. In this work, we explicitly use the Riemannian structure of the tensor space in designing our algorithm. This structure has already been utilized in several approaches based on active contour models which separate the mean and/or variance inside and outside the evolving contour. We generalize these methods by proposing a new technique for performing segmentation by separating the entire probability distributions of the regions inside and outside the contour using the Bhattacharyya metric. In particular, this allows for segmenting objects with multimodal probability distributions (on the space of tensors). We demonstrate the effectiveness of our algorithm by segmenting various textured images using the structure tensor. A level set based scheme is proposed to implement the curve flow evolution equation.

The standard graph cut technique is a robust method for globally optimal image segmentations. However, because of its global nature, it is prone to capture outlying areas similar to the object of interest. This paper proposes a novel method to constrain the standard graph cut technique for tracking anywhere from one to several objects in regions of interest. For each object, we introduce a pixel penalty based upon distance from a region of interest and so segmentation is biased to remain in this area. Also, we employ a filter predicting the location of the object. The distance penalty is then centered at this location and adoptively scaled based on prediction confidence. This method is capable of tracking multiple interacting objects of different intensity profiles in both gray-scale and color imagery.

In this paper, we describe a method for segmenting fiber bundles from diffusion-weighted magnetic resonance images using a locally-constrained region based approach. From a pre-computed optimal path, the algorithm propagates outward capturing only those voxels which are locally connected to the fiber bundle. Rather than attempting to find large numbers of open curves or single fibers, which individually have questionable meaning, this method segments the full fiber bundle region. The strengths of this approach include its ease-of-use, computational speed, and applicability to a wide range of fiber bundles. In this work, we show results for segmenting the cingulum bundle. Finally, we explain how this approach and extensions thereto overcome a major problem that typical region-based flows experience when attempting to segment neural fiber bundles.

Graph cut image segmentation with intensity information alone is prone to fail for objects with weak edges, in clutter, or under occlusion. Existing methods to incorporate shape are often too restrictive for highly varied shapes, use a single fixed shape which may be prone to misalignment, or are computationally intensive. In this note we show how highly variable nonlinear shape priors learned from training sets can be added to existing iterative graph cut methods for accurate and efficient segmentation of such objects. Using kernel principle component analysis, we demonstrate how a shape projection pre-image can induce an iteratively refined shape prior in a Bayesian manner. Examples of natural imagery show that both single-pass and iterative segmentation fail without such shape information.

Segmentation of medical ultrasound images (e.g., for the purpose of surgical or radiotherapy planning) is known to be a difficult task due to the relatively low resolution and reduced contrast of the images, as well as due to the discontinuity and uncertainty of segmentation boundaries caused by speckle noise. Under such conditions, useful segmentation results seem to be only achievable by means of relatively complex algorithms, which are usually computationally involved and/or require a prior learning. In this paper, a different approach to the problem of segmentation of medical ultrasound images is proposed. In particular, we propose to preprocess the images before they are subjected to a segmentation procedure. The proposed preprocessing modifies the images (without affecting their anatomic contents) so that the resulting images can be effectively segmented by relatively simple and computationally efficient means. The performance of the proposed method is tested in a series of both in silico and in vivo experiments.

Tracking deforming objects involves estimating the global motion of the object and its local deformations as a function of time. Tracking algorithms using Kalman filters or particle filters have been proposed for finite dimensional representations of shape, but these are dependent on the chosen parametrization and cannot handle changes in curve topology. Geometric active contours provide a framework which is parametrization independent and allow for changes in topology. In the present work, we formulate a particle filtering algorithm in the geometric active contour framework that can be used for tracking moving and deforming objects. To the best of our knowledge, this is the first attempt to implement an approximate particle filtering algorithm for tracking on a (theoretically) infinite dimensional state space.

This paper addresses the problem of image segmentation by means of active contours, whose evolution is driven by the gradient flow derived from an energy functional that is based on the Bhattacharyya distance. In particular, given the values of a photometric variable (or of a set thereof), which is to be used for classifying the image pixels, the active contours are designed to converge to the shape that results in maximal discrepancy between the empirical distributions of the photometric variable inside and outside of the contours. The above discrepancy is measured by means of the Bhattacharyya distance that proves to be an extremely useful tool for solving the problem at hand. The proposed methodology can be viewed as a generalization of the segmentation methods, in which active contours maximize the difference between a finite number of empirical moments of the "inside" and "outside" distributions. Furthermore, it is shown that the proposed methodology is very versatile and flexible in the sense that it allows one to easily accommodate a diversity of the image features based on which the segmentation should be performed. As an additional contribution, a method for automatically adjusting the smoothness properties of the empirical distributions is proposed. Such a procedure is crucial in situations when the number of data samples (supporting a certain segmentation class) varies considerably in the course of the evolution of the active contour. In this case, the smoothness properties of the empirical distributions have to be properly adjusted to avoid either over- or underestimation artifacts. Finally, a number of relevant segmentation results are demonstrated and some further research directions are discussed.

The problem of reconstruction of ultrasound images by means of blind deconvolution has long been recognized as one of the central problems in medical ultrasound imaging. In this paper, this problem is addressed via proposing a blind deconvolution method which is innovative in several ways. In particular, the method is based on parametric inverse filtering, whose parameters are optimized using two-stage processing. At the first stage, some partial information on the point spread function is recovered. Subsequently, this information is used to explicitly constrain the spectral shape of the inverse filter. From this perspective, the proposed methodology can be viewed as a "hybridization" of two standard strategies in blind deconvolution, which are based on either concurrent or successive estimation of the point spread function and the image of interest. Moreover, evidence is provided that the "hybrid" approach can outperform the standard ones in a number of important practical cases. Additionally, the present study introduces a different approach to parameterizing the inverse filter. Specifically, we propose to model the inverse transfer function as a member of a principal shift-invariant subspace. It is shown that such a parameterization results in considerably more stable reconstructions as compared to standard parameterization methods. Finally, it is shown how the inverse filters designed in this way can be used to deconvolve the images in a nonblind manner so as to further improve their quality. The usefulness and practicability of all the introduced innovations are proven in a series of both in silico and in vivo experiments. Finally, it is shown that the proposed deconvolutioh algorithms are capable of improving the resolution of ultrasound images by factors of 2.24 or 6.52 (as judged by the autocorrelation criterion) depending on the type of regularization method used.

Tracking deforming objects involves estimating the global motion of the object and its local deformations as functions of time. Tracking algorithms using Kalman filters or particle filters (PFs) have been proposed for tracking such objects, but these have limitations due to the lack of dynamic shape information. In this paper, we propose a novel method based on employing a locally linear embedding in order to incorporate dynamic shape information into the particle filtering framework for tracking highly deformable objects in the presence of noise and clutter. The PF also models image statistics such as mean and variance of the given data which can be useful in obtaining proper separation of object and background.

Image morphing, or image interpolation in the time domain, deals with the metamorphosis of one image into another. In this paper, a new class of image morphing algorithms is proposed based on the theory of optimal mass transport. The L(2) mass moving energy functional is modified by adding an intensity penalizing term, in order to reduce the undesired double exposure effect. It is an intensity-based approach and, thus, is parameter free. The optimal warping function is computed using an iterative gradient descent approach. This proposed morphing method is also extended to doubly connected domains using a harmonic parameterization technique, along with finite-element methods.

This paper presents a novel multiscale shape representation and segmentation algorithm based on the spherical wavelet transform. This work is motivated by the need to compactly and accurately encode variations at multiple scales in the shape representation in order to drive the segmentation and shape analysis of deep brain structures, such as the caudate nucleus or the hippocampus. Our proposed shape representation can be optimized to compactly encode shape variations in a population at the needed scale and spatial locations, enabling the construction of more descriptive, nonglobal, nonuniform shape probability priors to be included in the segmentation and shape analysis framework. In particular, this representation addresses the shortcomings of techniques that learn a global shape prior at a single scale of analysis and cannot represent fine, local variations in a population of shapes in the presence of a limited dataset. Specifically, our technique defines a multiscale parametric model of surfaces belonging to the same population using a compact set of spherical wavelets targeted to that population. We further refine the shape representation by separating into groups wavelet coefficients that describe independent global and/or local biological variations in the population, using spectral graph partitioning. We then learn a prior probability distribution induced over each group to explicitly encode these variations at different scales and spatial locations. Based on this representation, we derive a parametric active surface evolution using the multiscale prior coefficients as parameters for our optimization procedure to naturally include the prior for segmentation. Additionally, the optimization method can be applied in a coarse-to-fine manner. We apply our algorithm to two different brain structures, the caudate nucleus and the hippocampus, of interest in the study of schizophrenia. We show: 1) a reconstruction task of a test set to validate the expressiveness of our multiscale prior and 2) a segmentation task. In the reconstruction task, our results show that for a given training set size, our algorithm significantly improves the approximation of shapes in a testing set over the Point Distribution Model, which tends to oversmooth data. In the segmentation task, our validation shows our algorithm is computationally efficient and outperforms the Active Shape Model algorithm, by capturing finer shape details.

Segmentation involves separating an object from the background. In this work, we propose a novel segmentation method combining image information with prior shape knowledge, within the level-set framework. Following the work of Leventon et al., we revisit the use of principal component analysis (PCA) to introduce prior knowledge about shapes in a more robust manner. To this end, we utilize Kernel PCA and show that this method of learning shapes outperforms linear PCA, by allowing only shapes that are close enough to the training data. In the proposed segmentation algorithm, shape knowledge and image information are encoded into two energy functionals entirely described in terms of shapes. This consistent description allows to fully take advantage of the Kernel PCA methodology and leads to promising segmentation results. In particular, our shape-driven segmentation technique allows for the simultaneous encoding of multiple types of shapes, and offers a convincing level of robustness with respect to noise, clutter, partial occlusions, or smearing.

We propose particle filtering algorithms for tracking on infinite (or large) dimensional state spaces. We consider the general case where state space may not be a vector space, we assume it to be a separable metric space (Polish space). In implementation, any such space is approximated by a finite but large dimensional vector, whose dimension may vary at every time. Monte Carlo sampling from a large dimensional system noise distribution is computationally expensive. Also, the number of particles required for accurate particle filtering increases with the number of independent dimensions of the system noise, making particle filtering even more expensive. But as long as the number of independent system noise dimensions is small, even if the total state space dimension is very large, a particle filtering algorithm can be implemented. In most large dim applications, it is fair to assume that "most of the state change" occurs in a small dimensional basis, which may be fixed or slowly time varying (approximated as piecewise constant). We use this assumption to propose efficient PF algorithms. These are analyzed and extended in N. Vaswani, (2006)

Local conformation is an important determinant of RNA catalysis and binding. The analysis of RNA conformation is particularly difficult due to the large number of degrees of freedom (torsion angles) per residue. Proteins, by comparison, have many fewer degrees of freedom per residue. In this work, we use and extend classical tools from statistics and signal processing to search for clusters in RNA conformational space. Results are reported both for scalar analysis, where each torsion angle is separately studied, and for vectorial analysis, where several angles are simultaneously clustered. Adapting techniques from vector quantization and clustering to the RNA structure, we find torsion angle clusters and RNA conformational motifs. We validate the technique using well-known conformational motifs, showing that the simultaneous study of the total torsion angle space leads to results consistent with known motifs reported in the literature and also to the finding of new ones.

Simple point detection is an important task for several problems in discrete geometry, such as topology preserving thinning in image processing to compute discrete skeletons. In this paper, the approach to simple point detection is based on techniques from cubical homology, a framework ideally suited for problems in image processing. A (d-dimensional) unitary cube (for a d-dimensional digital image) is associated with every discrete picture element, instead of a point in epsilon(d) (the d-dimensional Euclidean space) as has been done previously. A simple point in this setting then refers to the removal of a unitary cube without changing the topology of the cubical complex induced by the digital image. The main result is a characterization of a simple point p (i.e., simple unitary cube) in terms of the homology groups of the (3d - 1) neighborhood of p for arbitrary, finite dimensions

Geometric active contours are formulated in a manner which is parametrization independent. As such, they are amenable to representation as the zero level set of the graph of a higher dimensional function. This representation is able to deal with singularities and changes in topology of the contour. It has been used very successfully in static images for segmentation and registration problems where the contour (represented as an implicit curve) is evolved until it minimizes an image based energy functional. But tracking involves estimating the global motion of the object and its local deformations as a function of time. Some attempts have been made to use geometric active contours for tracking, but most of these minimize the energy at each frame and do not utilize the temporal coherency of the motion or the deformation. On the other hand, tracking algorithms using Kalman filters or particle filters have been proposed for finite dimensional representations of shape. But these are dependent on the chosen parametrization and cannot handle changes in curve topology. In the present work, we formulate a particle filtering algorithm in the geometric active contour framework that can be used for tracking moving and deforming objects.

In supplement to an earlier paper, we present an altered cost functional for the computation of an edge-preserving optical flow that is invariant to rotation. In addition, we explain how the solutions to the resulting non-linear partial differential equations may be computed more efficiently with non-linear multigrid techniques. We prove the rotational invariance of this functional and report computation times on a real image sequence.

We propose an extension of the conformal (or geodesic) active contour framework in which the conformal factor depends not only on the position of the curve but also on the direction of its tangent. We describe several properties for variational curve segmentation schemes that justify the construction of optimal conformal factors (i.e., learning) in strong connection with pattern matching. The determination of optimal curves (i.e., segmentation) can be performed using either the calculus of variations or dynamic programming. The technique is illustrated on a road detection problem for different signal to noise ratios.

In this paper, we present two novel algorithms which produce flattened visualizations of branched physiological surfaces, such as vessels. The first approach is a conformal mapping algorithm based on the minimization of two Dirichlet functionals. From a triangulated representation of vessel surfaces, we show how the algorithm can be implemented using a finite element technique. The second method is an algorithm which adjusts the conformal mapping to produce a flattened representation of the original surface while preserving areas. This approach employs the theory of optimal mass transport. Furthermore, a new way of extracting center lines for vessel fly-throughs is provided.

We present a fast, robust and automatic method for computing central paths through tubular structures for application to virtual endoscopy. The key idea is to utilize a medial surface algorithm, which exploits properties of the average outward flux of the gradient vector field of a Euclidean distance function the boundary of the structure of interest. The algorithm is modified to yield a collection of 3D curves, each of which is locally centered. The approach requires no user interaction, and is virtually parameter free and has low computational complexity. We illustrate the approach on segmented colon and vessel data.

In this paper we will develop a method to determine cross sections of arbitrary two-dimensional tubular structures, which are allowed to branch, by means of a Stokes flow based boundary integral formulation. The measure for the cross sections for a point on the boundary of a given structure will be the path obtained by integrating perpendicularly to the flow lines from one side of the boundary to the other. Special emphasis will be put on the behavior at branching points, the behavior at vortices, and the necessary boundary conditions. The method can be extended to three dimensional problems.

Curvature flows have been extensively considered from a deterministic point of view. They have been shown to be useful for a number of applications including crystal growth, flame propagation, and computer vision. In some previous work G. Ben-Arous et al. (2002), we have described a random particle system, evolving on the discretized unit circle, whose profile converges toward the Gauss-Minkowsky transformation of solutions of curve shortening flows initiated by convex curves. The present note shows that this theory may be implemented as a new way of evolving curves and as a possible alternative to level set methods.

We segment and topologically classify brain vessel data obtained from magnetic resonance angiography (MRA). The segmentation is done adaptively and the classification by means of cubical homology, i.e. the computation of homology groups. In this way the number of connected components; (measured by H/sub 0/), the tunnels (given by H/sub 1/) and the voids (given by H/sub 2/) are determined, resulting in a topological characterization of the blood vessels.

We employ a conformal mapping technique to flatten tubular structures with multi-branches for visualization of MRA and CT volumetric vessel imagery. This may be used for the study of possible vessel pathology or virtual colonoscopy for polyp detection. The method is based on a discrete Laplace-Beltrami operator to flatten a tubular surface onto a planar polygonal region in an angle-preserving manner. A thinned pruned medial surface (or skeleton) is used for the vessel partition.

A new definition of affine invariant erosion of 3D surfaces is introduced. Instead of being based in terms of Euclidean distances, the volumes enclosed between the surface and its chords are used. The resulting erosion is insensitive to noise, and by construction, it is affine invariant. We prove some key properties about this erosion operation, and we propose a simple method to compute the erosion of implicit surfaces. We also discuss how the affine erosion can be used to define 3D affine invariant robust skeletons.

There are a number of tasks in low level vision and image processing that involve computing certain topological characteristics of objects in a given image including connectivity and the number of holes. We combine a new combinatorial topology method to compute the number of connected components and holes of objects in a given image with fast segmentation methods to extract the objects.

We apply a knowledge-based segmentation method developed for still and video images to the problem of tracking missiles and high speed projectiles. Since we are only interested in segmenting a portion of the missile (namely, the nose cone), we use our segmentation procedure as a method of adapting thresholding. The key idea is to utilize a priori knowledge about the objects present in the image, e.g. missile and background, introduced via Bayes' rule. Posterior probabilities obtained in this way are anisotropically smoothed, and the image segmentation is obtained via MAP classifications of the smoothed data. When segmenting sequences of images, the smoothed posterior probabilities of past frames are used as prior distributions in succeeding frames.

An approach for the segmentation of still and video synthetic aperture radar (SAR) images is described. A priori knowledge about the objects present in the image, e.g., target, shadow and background terrain, is introduced via Bayes' rule. Posterior probabilities obtained in this way are then anisotropically smoothed, and the image segmentation is obtained via MAP classifications of the smoothed data. When segmenting sequences of images, the smoothed posterior probabilities of past frames are used to learn the prior distributions in the succeeding frame. We show with examples from public data sets that this method provides an efficient and fast technique for addressing the segmentation of SAR data.

In this paper, we consider a novel three-dimensional (3-D) visualization technique based on surface flattening for virtual colonoscopy. Such visualization methods could be important in virtual colonoscopy because they have the potential for noninvasively determining the presence of polyps and other pathologies. Further, we demonstrate a method that presents a surface scan of the entire colon as a cine, and affords the viewer the opportunity to examine each point on the surface without distortion. We use certain angle-preserving mappings from differential geometry to derive an explicit method for flattening surfaces obtained from 3-D colon computed tomography (CT) imagery. Indeed, we describe a general method based on a discretization of the Laplace-Beltrami operator for flattening a surface into the plane in a conformal manner. From a triangulated surface representation of the colon, we indicate how the procedure may be implemented using a finite element technique, which takes into account special boundary conditions. We also provide simple formulas that may be used in a real-time cine to correct for distortion.

We give an explicit method for mapping any simply connected surface onto the sphere in a manner which preserves angles. This technique relies on certain conformal mappings from differential geometry. Our method provides a new way to automatically assign texture coordinates to complex undulating surfaces. We demonstrate a finite element method that can be used to apply our mapping technique to a triangulated geometric description of a surface.

It is commonly held that skeleton variation due to noise is unmanageable. It is also believed that smoothing, invoked to combat noise, creates no new structures, as in the causality principle for smoothing images. We demonstrate that both views are incorrect. We characterize how smooth points of the skeleton evolve under a general boundary evolution, with the corollary that, when the boundary is smoothed by a geometric heat equation, the skeleton evolves according to a related geometric heat equation. The surprise is that, while certain aspects of the skeleton simplify, as one would expect, others can behave wildly, including the creation of new skeleton branches. Fortunately such sections can be flagged as ligature, or those portions of the skeleton related to shape concavities. Our analysis also includes junctions and an explicit model for boundary noise. Provided a smoothness condition is met, the skeleton can often reduce noise. However when the smoothness condition is violated, the skeleton can change violently, which, we speculate, corresponds to situations in which "parts" are created, e.g., when the handle appears on a rotating cup.

The eikonal equation and variants of it are of significant interest for problems in computer vision and image processing. It is the basis for continuous versions of mathematical morphology, stereo, shape-from-shading and for recent dynamic theories of shape. Its numerical simulation can be delicate, owing to the formation of singularities in the evolving front, and is typically based or, level set methods. However there are more classical approaches rooted in Hamiltonian physics, which have received little consideration in computer vision. In this paper we first introduce a new algorithm for simulating the eikonal equation, which offers a number of computational and conceptual advantages over the earlier methods when it comes to shock tracking. Next, we introduce a very efficient algorithm for shock detection, where the key idea is to measure the net outward flux of a vector field per unit volume, and to detect locations where a conservation of energy principle is violated. We illustrate the approach with several numerical examples including skeletons of complex 2D and 3D shapes.

We earlier introduced an approach to categorical shape description based on the singularities (shocks) of curve evolution equations. The approach relates to many techniques in computer vision, such as Blum's grassfire transform, but since the motivation was abstract it is not clear that it should also relate to human perception. We now report that this shock-based computational model can account for recent psychophysical data collected by Burbeck and Pizer. In these experiments subjects were asked to estimate the local centers of stimuli consisting of rectangles with `wiggles' (sides modulated by sinusoids). Since the experiments were motivated by their `core' model, in which the scale of boundary detail is proportional to object width, we conclude that such properties are also implicit in shock-based shape descriptions. More generally, the results suggest that significance is a structural notion, not an image-based one, and that scale should be defined primarily in terms of relationships between abstract entities, not concrete pixels.

In this paper, using certain conformal mappings from uniformization theory, we give an explicit method for flattening the brain surface in a way which preserves angles. From a triangulated surface representation of the cortex, we indicate how the procedure may be implemented using finite elements. Further, we show how the geometry of the brain surface may be studied using this approach.

We have been developing a theory of generic 2-D shape based on a reaction-diffusion model from mathematical physics. The description of a shape is derived from the singularities of a curve evolution process driven by the reaction (hyperbolic) term. The diffusion (parabolic) term is related to smoothing and shape simplification. However, the unification of the two is problematic, because the slightest amount of diffusion dominates and prevents the formation of generic first-order shocks. The technical issue is whether it is possible to smooth a shape, in any sense, without destroying the shocks. We now report a constructive solution to this problem, by embedding the smoothing term in a global metric against which a purely hyperbolic evolution is performed from the initial curve. This is a new flow for shape, that extends the advantages of the original one. Specific metrics are developed, which lead to a natural hierarchy of shape features, analogous to the simplification one might perceive when viewing an object from increasing distances. We illustrate our new flow with a variety of examples.

A new approach for the segmentation of still and video SAR images is described. A priori knowledge about the objects present in the image, e.g., target, shadow, and background terrain, is introduced via Bayes' rule. Posterior probabilities obtained in this way are then anisotropically smoothed, and the image segmentation is obtained via MAP classifications of the smoothed data. When segmenting sequences of images, the smoothed posterior probabilities of past frames are used to learn the prior distributions in the succeeding frame. We show, via a large number of examples from public data sets, that this method provides an efficient and fast technique for addressing the segmentation of SAR data.

A number of active contour models have been proposed that unify the curve evolution framework with classical energy minimization techniques for segmentation, such as snakes. The essential idea is to evolve a curve (in two dimensions) or a surface (in three dimensions) under constraints from image forces so that it clings to features of interest in an intensity image. The evolution equation has been derived from first principles as the gradient flow that minimizes a modified length functional, tailored to features such as edges. However, because the flow may be slow to converge in practice, a constant (hyperbolic) term is added to keep the curve/surface moving in the desired direction. We derive a modification of this term based on the gradient flow derived from a weighted area functional, with image dependent weighting factor. When combined with the earlier modified length gradient flow, we obtain a partial differential equation (PDE) that offers a number of advantages, as illustrated by several examples of shape segmentation on medical images. In many cases the weighted area flow may be used on its own, with significant computational savings.

Several active contour models have been proposed to unify the curve evolution framework with classical energy minimization techniques for segmentation, such as snakes. The essential idea is to evolve a curve (in 2D) or a surface (in 3D) under constraints from image forces so that it clings to features of interest in an intensity image. Recently the evolution equation has been derived from first principles as the gradient flow that minimizes a modified length functional, tailored to features such as edges. However, because the flow may be slow to converge in practice, a constant (hyperbolic) term is added to keep the curve/surface moving in the desired direction. The authors provide a justification for this term based on the gradient flow derived from a weighted area functional, with image dependent weighting factor. When combined with the earlier modified length gradient flow they obtain a PDE which offers a number of advantages, as illustrated by several examples of shape segmentation on medical images. In many cases the weighted area flow may be used on its own, with significant computational savings.

Several active contour models have been proposed to unify the curve evolution framework with classical energy minimization techniques for segmentation, such as snakes. The essential idea is to evolve a curve (in 2D) or a surface (in 3D) under constraints from image forces so that it clings to features of interest in an intensity image. The evolution equation has been derived from first principles as the gradient flow that minimizes a modified length functional, tailored to features such as edges. However, because the flow may be slow to converge in practice, a constant (hyperbolic) term is added to keep the curve/surface moving in the desired direction. We provide a justification, for this term based on the gradient flow derived from a weighted area functional, with an image dependent weighting factor. When combined with the earlier modified length gradient flow we obtain a partial differential equation (PDE) which offers a number of advantages, as illustrated by several examples of shape segmentation on medical images. In many cases the weighted area flow may be used on its own, with significant computational savings.

In this note, we employ the new geometric active contour models formulated in [25] and [26] for edge detection and segmentation of magnetic resonance imaging (MRI), computed tomography (CT), and ultrasound medical imagery. Our method is based on defining feature-based metrics on a given image which in turn leads to a novel snake paradigm in which the feature of interest may be considered to lie at the bottom of a potential well. Thus, the snake is attracted very quickly and efficiently to the desired feature.

In this paper we undertake a systematic investigation of affine invariant object detection. Edge detection is first presented from the point of view of the affine invariant scale-space obtained by curvature based motion of the image level-sets. In this case, affine invariant edges are obtained as a weighted difference of images at different scales. We then introduce the affine gradient as the simplest possible affine invariant differential function which has the same qualitative behavior as the Euclidean gradient magnitude. These edge detectors are the basis both to extend the affine invariant scale-space to a complete affine flow for image denoising and simplification, and to define affine invariant active contours for object detection and edge integration. The active contours are obtained as a gradient flow in a conformally Euclidean space defined by the image on which the object is to be detected. That is, we show that objects can be segmented in an affine invariant manner by computing a path of minimal weighted affine distance, the weight being given by functions of the affine edge detectors. The geodesic path is computed via an algorithm which allows to simultaneously detect any number of objects independently of the initial curve topology.

A novel approach for the computation of optical flow based on an L (1) type minimization is presented. It is shown that the approach has inherent advantages since it does not smooth the flow-velocity across the edges and hence preserves edge information. A numerical approach based on computation of evolving curves is proposed for computing the optical flow field. Computations are carried out on a number of real image sequences in order to illustrate the theory as well as the numerical approach.

In this paper, we analyze the behavior of the anisotropic diffusion model of Perona and Malik (1990). The main idea is to express the anisotropic diffusion equation as coming from a certain optimization problem, so its behavior can be analyzed based on the shape of the corresponding energy surface. We show that anisotropic diffusion is the steepest descent method for solving an energy minimization problem. It is demonstrated that an anisotropic diffusion is well posed when there exists a unique global minimum for the energy functional and that the ill posedness of a certain anisotropic diffusion is caused by the fact that its energy functional has an infinite number of global minima that are dense in the image space. We give a sufficient condition for an anisotropic diffusion to be well posed and a sufficient and necessary condition for it to be ill posed due to the dense global minima. The mechanism of smoothing and edge enhancement of anisotropic diffusion is illustrated through a particular orthogonal decomposition of the diffusion operator into two parts: one that diffuses tangentially to the edges and therefore acts as an anisotropic smoothing operator, and the other that flows normally to the edges and thus acts as an enhancement operator.

In this paper, we analyze the geometric active contour models discussed previously from a curve evolution point of view and propose some modifications based on gradient flows relative to certain new feature-based Riemannian metrics. This leads to a novel snake paradigm in which the feature of interest may be considered to lie at the bottom of a potential well. Thus the snake is attracted very naturally and efficiently to the desired feature. Moreover, we consider some 3-D active surface models based on these ideas.>

A novel approach for the computation of optical flow based on an L/sup 1/ type minimization is presented. It is shown that the approach has inherent advantages since it does not smooth the flow-velocity across the edges and hence preserves edge information. A numerical approach based on computation of evolving curves is proposed for computing the optical flow field and results of experiments are presented.

This paper describes a class of ill-posed anisotropic diffusion models of the type presented by Perona and Malik (1990). The analysis is based on a previous result that anisotropic diffusion is a steepest descent motion on an energy surface and its behavior is thus determined by the shape of this energy surface. We show that the class of diffusion models are ill-posed because the energy surface is discontinuous at all continuous images, and all step images, which are dense in the space of piecewise images, are global minima of the energy surface.

In this paper, area preserving multi-scale representations of planar curves are described. This allows smoothing without shrinkage at the same time preserving all the scale-space properties. The representations are obtained deforming the curve via geometric heat flows while simultaneously magnifying the plane by a homethety which keeps the enclosed area constant. When the Euclidean geometric heat flow is used, the resulting representation is Euclidean invariant, and similarly it is affine invariant when the affine one is used. The flows are geometrically intrinsic to the curve, and exactly satisfy all the basic requirements of scale-space representations. In the case of the Euclidean heat flow, it is completely local as well. The same approach is used to define length preserving geometric flows. A similarity (scale) invariant geometric heat flow is studied as well in this work.>

In this paper we experiments with geometric algorithms for image smoothing. Examples are given for MRI and ATR data. We emphasize experiments with the affine invariant geometric smoother or affine heat equation, originally developed for binary shape smoothing, and found to be efficient for gray-level images as well. Efficient numerical implementations of these flows give anisotropic diffusion processes which preserve edges.>

Anisotropic diffusion is posed as a process of minimizing an energy function. Its global convergence behavior is determined by the shape of the energy surface, and its local behavior is described by an orthogonal decomposition with the decomposition coefficients being the eigenvalues of the local energy function. A sufficient condition for its convergence to a global minimum is given and is identified to be the same as the condition previously proposed for the well-posedness of 1-D diffusions. Some behavior conjectures are made for anisotropic diffusions not satisfying the sufficient condition. Finally, some well-behaved anisotropic diffusions are proposed and simulation results are shown.>

Some modern techniques are applied from real semialgebraic geometry to the robotic manipulator problem. In particular, using the notion of "metric entropy," the complexity of maneuvering the manipulator from state to state is discussed.