Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder.

MOTIVATION: Single-cell RNA sequencing (scRNA-seq) allows studying the development of cells in unprecedented detail. Given that many cellular differentiation processes are hierarchical, their scRNA-seq data are expected to be approximately tree-shaped in gene expression space. Inference and representation of this tree structure in two dimensions is highly desirable for biological interpretation and exploratory analysis. RESULTS: Our two contributions are an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data, and a visualization method respecting the tree structure. We extract the tree structure by means of a density-based maximum spanning tree on a vector quantization of the data and show that it captures biological information well. We then introduce density-tree biased autoencoder (DTAE), a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space. We compare to other dimension reduction methods and demonstrate the success of our method both qualitatively and quantitatively on real and toy data. AVAILABILITY AND IMPLEMENTATION: Our implementation relying on PyTorch and Higra is available at github.com/hci-unihd/DTAE. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Myocardial Perfusion Simulation for Coronary Artery Disease: A Coupled Patient-Specific Multiscale Model.

Patient-specific models of blood flow are being used clinically to diagnose and plan treatment for coronary artery disease. A remaining challenge is bridging scales from flow in arteries to the micro-circulation supplying the myocardium. Previously proposed models are descriptive rather than predictive and have not been applied to human data. The goal here is to develop a multiscale patient-specific model enabling blood flow simulation from large coronary arteries to myocardial tissue. Patient vasculatures are segmented from coronary computed tomography angiography data and extended from the image-based model down to the arteriole level using a space-filling forest of synthetic trees. Blood flow is modeled by coupling a 1D model of the coronary arteries to a single-compartment Darcy myocardium model. Simulated results on five patients with non-obstructive coronary artery disease compare overall well to [[Formula: see text]O][Formula: see text]O PET exam data for both resting and hyperemic conditions. Results on a patient with severe obstructive disease link coronary artery narrowing with impaired myocardial blood flow, demonstrating the model's ability to predict myocardial regions with perfusion deficit. This is the first report of a computational model for simulating blood flow from the epicardial coronary arteries to the left ventricle myocardium applied to and validated on human data.

Generation of Patient-Specific Cardiac Vascular Networks: A Hybrid Image-Based and Synthetic Geometric Model.

OBJECTIVE: In this paper, we propose an algorithm for the generation of a patient-specific cardiac vascular network starting from segmented epicardial vessels down to the arterioles. METHOD: We extend a tree generation method based on satisfaction of functional principles, named constrained constructive optimization, to account for multiple, competing vascular trees. The algorithm simulates angiogenesis under vascular volume minimization with flow-related and geometrical constraints adapting the simultaneous tree growths to patient priors. The generated trees fill the entire left ventricle myocardium up to the arterioles. RESULTS: From actual vascular tree models segmented from CT images, we generated networks with 6000 terminal segments for six patients. These networks contain between 33 and 62 synthetic trees. All vascular models match morphometry properties previously described. CONCLUSION AND SIGNIFICANCE: Image-based models derived from CT angiography are being used clinically to simulate blood flow in the coronary arteries of individual patients to aid in the diagnosis of disease and planning treatments. However, image resolution limits vessel segmentation to larger epicardial arteries. The generated model can be used to simulate the blood flow and derived quantities from the aorta into the myocardium. This is an important step for diagnosis and treatment planning of coronary artery disease.

Some Properties of Interpolations Using Mathematical Morphology.

The problem of interpolation of images is defined as - given two images at time t = 0 and t = T, one must find the series of images for the intermediate time. This problem is not well posed, in the sense that without further constraints, there are many possible solutions. The solution is thus usually dictated by the choice of the constraints/assumptions, which in turn relies on the domain of application. In this article we follow the approach of obtaining a solution to the interpolation problem using the operators from Mathematical Morphology (MM). These operators have an advantage of preserving structures since the operators are defined on sets. In this work we explore the solutions obtained using MM, and provide several results along with proofs which corroborates the validity of the assumptions, provide links among existing methods and intuition about them. We also summarize few possible extensions and prospective problems of current interest.

Curvilinear Structure Analysis by Ranking the Orientation Responses of Path Operators.

The analysis of thin curvilinear objects in 3D images is a complex and challenging task. In this article, we introduce a new, non-linear operator, called RORPO (Ranking the Orientation Responses of Path Operators). Inspired by the multidirectional paradigm currently used in linear filtering for thin structure analysis, RORPO is built upon the notion of path operator from mathematical morphology. This operator, unlike most operators commonly used for 3D curvilinear structure analysis, is discrete, non-linear and non-local. From this new operator, two main curvilinear structure characteristics can be estimated: an intensity feature, that can be assimilated to a quantitative measure of curvilinearity; and a directional feature, providing a quantitative measure of the structure's orientation. We provide a full description of the structural and algorithmic details for computing these two features from RORPO, and we discuss computational issues. We experimentally assess RORPO by comparison with three of the most popular curvilinear structure analysis filters, namely Frangi Vesselness, Optimally Oriented Flux, and Hybrid Diffusion with Continuous Switch. In particular, we show that our method provides up to 8 percent more true positive and 50 percent less false positives than the next best method, on synthetic and real 3D images.

Scale-space for empty catheter segmentation in PCI fluoroscopic images.

PURPOSE: In this article, we present a method for empty guiding catheter segmentation in fluoroscopic X-ray images. The guiding catheter, being a commonly visible landmark, its segmentation is an important and a difficult brick for Percutaneous Coronary Intervention (PCI) procedure modeling. METHODS: In number of clinical situations, the catheter is empty and appears as a low contrasted structure with two parallel and partially disconnected edges. To segment it, we work on the level-set scale-space of image, the min tree, to extract curve blobs. We then propose a novel structural scale-space, a hierarchy built on these curve blobs. The deep connected component, i.e. the cluster of curve blobs on this hierarchy, that maximizes the likelihood to be an empty catheter is retained as final segmentation. RESULTS: We evaluate the performance of the algorithm on a database of 1250 fluoroscopic images from 6 patients. As a result, we obtain very good qualitative and quantitative segmentation performance, with mean precision and recall of 80.48 and 63.04% respectively. CONCLUSIONS: We develop a novel structural scale-space to segment a structured object, the empty catheter, in challenging situations where the information content is very sparse in the images. Fully-automatic empty catheter segmentation in X-ray fluoroscopic images is an important and preliminary step in PCI procedure modeling, as it aids in tagging the arrival and removal location of other interventional tools.

Hierarchical Segmentation Using Tree-Based Shape Spaces.

Current trends in image segmentation are to compute a hierarchy of image segmentations from fine to coarse. A classical approach to obtain a single meaningful image partition from a given hierarchy is to cut it in an optimal way, following the seminal approach of the scale-set theory. While interesting in many cases, the resulting segmentation, being a non-horizontal cut, is limited by the structure of the hierarchy. In this paper, we propose a novel approach that acts by transforming an input hierarchy into a new saliency map. It relies on the notion of shape space: a graph representation of a set of regions extracted from the image. Each region is characterized with an attribute describing it. We weigh the boundaries of a subset of meaningful regions (local minima) in the shape space by extinction values based on the attribute. This extinction-based saliency map represents a new hierarchy of segmentations highlighting regions having some specific characteristics. Each threshold of this map represents a segmentation which is generally different from any cut of the original hierarchy. This new approach thus enlarges the set of possible partition results that can be extracted from a given hierarchy. Qualitative and quantitative illustrations demonstrate the usefulness of the proposed method.

Connected Filtering on Tree-Based Shape-Spaces.

Connected filters are well-known for their good contour preservation property. A popular implementation strategy relies on tree-based image representations: for example, one can compute an attribute characterizing the connected component represented by each node of the tree and keep only the nodes for which the attribute is sufficiently high. This operation can be seen as a thresholding of the tree, seen as a graph whose nodes are weighted by the attribute. Rather than being satisfied with a mere thresholding, we propose to expand on this idea, and to apply connected filters on this latest graph. Consequently, the filtering is performed not in the space of the image, but in the space of shapes built from the image. Such a processing of shape-space filtering is a generalization of the existing tree-based connected operators. Indeed, the framework includes the classical existing connected operators by attributes. It also allows us to propose a class of novel connected operators from the leveling family, based on non-increasing attributes. Finally, we also propose a new class of connected operators that we call morphological shapings. Some illustrations and quantitative evaluations demonstrate the usefulness and robustness of the proposed shape-space filters.

Improved Estimation of Cardiac Function Parameters Using a Combination of Independent Automated Segmentation Results in Cardiovascular Magnetic Resonance Imaging.

This work aimed at combining different segmentation approaches to produce a robust and accurate segmentation result. Three to five segmentation results of the left ventricle were combined using the STAPLE algorithm and the reliability of the resulting segmentation was evaluated in comparison with the result of each individual segmentation method. This comparison was performed using a supervised approach based on a reference method. Then, we used an unsupervised statistical evaluation, the extended Regression Without Truth (eRWT) that ranks different methods according to their accuracy in estimating a specific biomarker in a population. The segmentation accuracy was evaluated by estimating six cardiac function parameters resulting from the left ventricle contour delineation using a public cardiac cine MRI database. Eight different segmentation methods, including three expert delineations and five automated methods, were considered, and sixteen combinations of the automated methods using STAPLE were investigated. The supervised and unsupervised evaluations demonstrated that in most cases, STAPLE results provided better estimates than individual automated segmentation methods. Overall, combining different automated segmentation methods improved the reliability of the segmentation result compared to that obtained using an individual method and could achieve the accuracy of an expert.

Tree-based Morse regions: a topological approach to local feature detection.

This paper introduces a topological approach to local invariant feature detection motivated by Morse theory. We use the critical points of the graph of the intensity image, revealing directly the topology information as initial interest points. Critical points are selected from what we call a tree-based shape-space. In particular, they are selected from both the connected components of the upper level sets of the image (the Max-tree) and those of the lower level sets (the Min-tree). They correspond to specific nodes on those two trees: 1) to the leaves (extrema) and 2) to the nodes having bifurcation (saddle points). We then associate to each critical point the largest region that contains it and is topologically equivalent in its tree. We call such largest regions the tree-based Morse regions (TBMRs). The TBMR can be seen as a variant of maximally stable extremal region (MSER), which are contrasted regions. Contrarily to MSER, TBMR relies only on topological information and thus fully inherit the invariance properties of the space of shapes (e.g., invariance to affine contrast changes and covariance to continuous transformations). In particular, TBMR extracts the regions independently of the contrast, which makes it truly contrast invariant. Furthermore, it is quasi-parameter free. TBMR extraction is fast, having the same complexity as MSER. Experimentally, TBMR achieves a repeatability on par with state-of-the-art methods, but obtains a significantly higher number of features. Both the accuracy and robustness of TBMR are demonstrated by applications to image registration and 3D reconstruction.

Learning hierarchical features for scene labeling.

Scene labeling consists of labeling each pixel in an image with the category of the object it belongs to. We propose a method that uses a multiscale convolutional network trained from raw pixels to extract dense feature vectors that encode regions of multiple sizes centered on each pixel. The method alleviates the need for engineered features, and produces a powerful representation that captures texture, shape, and contextual information. We report results using multiple postprocessing methods to produce the final labeling. Among those, we propose a technique to automatically retrieve, from a pool of segmentation components, an optimal set of components that best explain the scene; these components are arbitrary, for example, they can be taken from a segmentation tree or from any family of oversegmentations. The system yields record accuracies on the SIFT Flow dataset (33 classes) and the Barcelona dataset (170 classes) and near-record accuracy on Stanford background dataset (eight classes), while being an order of magnitude faster than competing approaches, producing a $(320\times 240)$ image labeling in less than a second, including feature extraction.

Nonsupervised ranking of different segmentation approaches: application to the estimation of the left ventricular ejection fraction from cardiac cine MRI sequences.

A statistical methodology is proposed to rank several estimation methods of a relevant clinical parameter when no gold standard is available. Based on a regression without truth method, the proposed approach was applied to rank eight methods without using any a priori information regarding the reliability of each method and its degree of automation. It was only based on a prior concerning the statistical distribution of the parameter of interest in the database. The ranking of the methods relies on figures of merit derived from the regression and computed using a bootstrap process. The methodology was applied to the estimation of the left ventricular ejection fraction derived from cardiac magnetic resonance images segmented using eight approaches with different degrees of automation: three segmentations were entirely manually performed and the others were variously automated. The ranking of methods was consistent with the expected performance of the estimation methods: the most accurate estimates of the ejection fraction were obtained using manual segmentations. The robustness of the ranking was demonstrated when at least three methods were compared. These results suggest that the proposed statistical approach might be helpful to assess the performance of estimation methods on clinical data for which no gold standard is available.

Curvilinear structure enhancement with the polygonal path image--application to guide-wire segmentation in X-ray fluoroscopy.

Curvilinear structures are common in medical imaging, which typically require dedicated processing techniques. We present a new structure to process these, that we call the polygonal path image, denoted (see text for symbol). We derive from (see text for symbol) some curvilinear structure enhancement and analysis algorithms. We show that (see text for symbol) has some interesting properties: it generalizes several concepts found in other methods; it makes it possible to control the smoothness and length of the structures under study; and it can be computed efficiently. We estimate quantitatively its performance in the context of interventional cardiology for the detection of guide-wires in Xray images. We show that (see text for symbol) is particularly well suited for this task where it appears to outperform previous state of the art techniques.

A comprehensive study of stent visualization enhancement in X-ray images by image processing means.

In this work we propose a comprehensive study of Digital Stent Enhancement (DSE), from the analysis of the requirements to the validation of the proposed solution. First, we derive the stent visualization requirements in the context of the clinical application and workflow. Then, we propose a DSE algorithm combining automatic detection, tracking, registration and contrast enhancement. The most original parts of our solution: landmark segmentation and non-linear image registration are detailed. Finally, we validate the algorithm on a large number of synthetic and clinical cases. Performance is characterized in terms of automation, image quality and execution time. This work is, to the best of our knowledge, the first comprehensive article on DSE, covering problem statement, proposed solution, and validation strategies.

Power Watershed: A Unifying Graph-Based Optimization Framework.

In this work, we extend a common framework for graph-based image segmentation that includes the graph cuts, random walker, and shortest path optimization algorithms. Viewing an image as a weighted graph, these algorithms can be expressed by means of a common energy function with differing choices of a parameter q acting as an exponent on the differences between neighboring nodes. Introducing a new parameter p that fixes a power for the edge weights allows us to also include the optimal spanning forest algorithm for watershed in this same framework. We then propose a new family of segmentation algorithms that fixes p to produce an optimal spanning forest but varies the power q beyond the usual watershed algorithm, which we term the power watershed. In particular, when q=2, the power watershed leads to a multilabel, scale and contrast invariant, unique global optimum obtained in practice in quasi-linear time. Placing the watershed algorithm in this energy minimization framework also opens new possibilities for using unary terms in traditional watershed segmentation and using watershed to optimize more general models of use in applications beyond image segmentation.

Comparison of different segmentation approaches without using gold standard. Application to the estimation of the left ventricle ejection fraction from cardiac cine MRI sequences.

A statistical method is proposed to compare several estimates of a relevant clinical parameter when no gold standard is available. The method is illustrated by considering the left ventricle ejection fraction derived from cardiac magnetic resonance images and computed using seven approaches with different degrees of automation. The proposed method did not use any a priori regarding with the reliability of each method and its degree of automation. The results showed that the most accurate estimates of the ejection fraction were obtained using manual segmentations, followed by the semiautomatic methods, while the methods with the least user input yielded the least accurate ejection fraction estimates. These results were consistent with the expected performance of the estimation methods, suggesting that the proposed statistical approach might be helpful to assess the performance of estimation methods on clinical data for which no gold standard is available.

Watershed cuts: thinnings, shortest path forests, and topological watersheds.

We recently introduced watershed cuts, a notion of watershed in edge-weighted graphs. In this paper, our main contribution is a thinning paradigm from which we derive three algorithmic watershed cut strategies: The first one is well suited to parallel implementations, the second one leads to a flexible linear-time sequential implementation, whereas the third one links the watershed cuts and the popular flooding algorithms. We state that watershed cuts preserve a notion of contrast, called connection value, on which several morphological region merging methods are (implicitly) based. We also establish the links and differences between watershed cuts, minimum spanning forests, shortest path forests, and topological watersheds. Finally, we present illustrations of the proposed framework to the segmentation of artwork surfaces and diffusion tensor images.

Watershed cuts: minimum spanning forests and the drop of water principle.

We study the watersheds in edge-weighted graphs. We define the watershed cuts following the intuitive idea of drops of water flowing on a topographic surface. We first establish the consistency of these watersheds: They can be equivalently defined by their "catchment basins" (through a steepest descent property) or by the "dividing lines" separating these catchment basins (through the drop of water principle). Then, we prove, through an equivalence theorem, their optimality in terms of minimum spanning forests. Afterward, we introduce a linear-time algorithm to compute them. To the best of our knowledge, similar properties are not verified in other frameworks and the proposed algorithm is the most efficient existing algorithm, both in theory and in practice. Finally, the defined concepts are illustrated in image segmentation, leading to the conclusion that the proposed approach improves, on the tested images, the quality of watershed-based segmentations.

Building the component tree in quasi-linear time.

The level sets of a map are the sets of points with level above a given threshold. The connected components of the level sets, thanks to the inclusion relation, can be organized in a tree structure, that is called the component tree. This tree, under several variations, has been used in numerous applications. Various algorithms have been proposed in the literature for computing the component tree. The fastest ones (considering the worst-case complexity) have been proven to run in O(n ln(n)). In this paper, we propose a simple to implement quasi-linear algorithm for computing the component tree on symmetric graphs, based on Tarjan's union-find procedure. We also propose an algorithm that computes the n most significant lobes of a map.