Let G = ( g 1 , … , g ℓ ) be a vector of positive integers and set n = ∑ i = 1 ℓ g i . Writing Ch ( a , b ) for the Christoffel word with parameters ( a , b ) , we study the following synchronization problem: choose one conjugate of each word Ch ( g i , n − g i ) so that, at every position 0 , … , n − 1 , exactly one of the chosen words contains the letter 1. This gives a gap-free form of superimposition, motivated by Fraenkel’s conjecture. We encode the choice of conjugates by a shift vector V = ( v 1 , … , v ℓ ) . On the cyclic Cayley graph of Z / n Z , this yields an orbital matrix O ( G , V ) , with entries o i , j = ( v i + j g i ) mod n , and a Christoffel–conjugate matrix C ( G , V ) , which records the columns where a wraparound occurs. The vector V is a synchronizing seed precisely when each column of C ( G , V ) contains exactly one nonzero entry. The main algebraic tool is a vertical invariant: the column sums of O ( G , V ) are constant if and only if this one-wraparound-per-column condition holds. Using this criterion, we give explicit synchronizing seeds for every pair of Christoffel words of common length, for triples in which two generators coincide, for triples with three equal generators, and for the all-distinct family proportional to ( 1,2,4 ) . Finally, we give a geometric interpretation: each synchronized row is the Freeman chain code of a standard 4-connected Réveillès segment, whose parameter μ i is the unique integer in { 1 − n , … , 0 } satisfying μ i ≡ − v i ( mod n ) .

After Learning Evolutionary Retrofitting (AfterLearnER) consists in applying evolutionary optimization to refine fully trained machine learning models by optimizing a set of carefully chosen parameters or hyperparameters of the model, with respect to some actual, exact, and hence possibly non-differentiable error signal, performed on a subset of the standard validation set. The efficiency of AfterLearnER is demonstrated by tackling non-differentiable signals such as threshold-based criteria in depth sensing, the word error rate in speech resynthesis, the number of kills per life at Doom, computational accuracy or BLEU in code translation, image quality in 3D generative adversarial networks (GANs), and user feedback in image generation via latent diffusion models (LDM). This retrofitting can be done after training, or dynamically at inference time by taking into account the user feedback. The advantages of AfterLearnER are its versatility, the possibility to use non-differentiable feedback, including human evaluations (i.e., no gradient is needed), the limited overfitting supported by a theoretical study, and its anytime behavior. Last but not least, AfterLearnER requires only a small amount of feedback, i.e., a few dozen to a few hundred scalars, compared to the tens of thousands needed in most related published works.

Annotating 3D medical images demands expert knowledge and is time-consuming. As a result, semi-supervised learning (SSL) approaches have gained significant interest in 3D medical image segmentation. The significant size differences among various organs in the human body lead to imbalanced class distribution, which is a major challenge in the real-world application of these SSL approaches. To address this issue, we develop a novel Shape Transformation driven by Active Contour (STAC), that enlarges smaller organs to alleviate imbalanced class distribution across different organs. Inspired by curve evolution theory in active contour methods, STAC employs a signed distance function (SDF) as the level set function, to implicitly represent the shape of organs, and deforms voxels in the direction of the steepest descent of SDF (i.e., the normal vector). To ensure that the voxels far from expansion organs remain unchanged, we design an SDF-based weight function to control the degree of deformation for each voxel. We then use STAC as a data-augmentation process during the training stage. Experimental results on two benchmark datasets demonstrate that the proposed method significantly outperforms some state-of-the-art methods. Source code is publicly available at https://github.com/GuGuLL123/STAC.

Providing interpretability of deep-learning models to non-experts, while fundamental for a responsible real-world usage, is challenging. Attribution maps from xAI techniques, such as Integrated Gradients, are a typical example of a visualization technique containing a high level of information, but with difficult interpretation. In this paper, we propose two methods, Maximum Activation Groups Extraction (MAGE) and Multiscale Interpretable Visualization (Ms-IV), to explain the model's decision, enhancing global interpretability. MAGE finds, for a given CNN , combinations of features which, globally, form a semantic meaning, that we call concepts . We group these similar feature patterns by clustering in “concepts”, that we visualize through Ms-IV. This last method is inspired by Occlusion and Sensitivity analysis (incorporating causality) and uses a novel metric, called Class-aware Order Correlation ( CAOC ), to globally evaluate the most important image regions according to the model's decision space. We compare our approach to xAI methods such as LIME and Integrated Gradients. Experimental results evince the Ms-IV higher localization and faithfulness values. Finally, qualitative evaluation of combined MAGE and Ms-IV demonstrates humans' ability to agree, based on the visualization, with the decision of clusters' concepts; and, to detect, among a given set of networks, the existence of bias.

Joint-Embedding Self Supervised Learning (JE-SSL) has seen a rapid development, with the emergence of many method variations but only few principled guidelines that would help practitioners to successfully deploy them. The main reason for that pitfall comes from JE-SSL’s core principle of not employing any input reconstruction therefore lacking visual cues of unsuccessful training. Adding non informative loss values to that, it becomes difficult to deploy SSL on a new dataset for which no labels can help to judge the quality of the learned representation. In this study, we develop a simple unsupervised criterion that is indicative of the quality of the learned JE-SSL representations: their effective rank. Albeit simple and computationally friendly, this method —coined RankMe— allows one to assess the performance of JE-SSL representations, even on different downstream datasets, without requiring any labels. A further benefit of RankMe is that it does not have any training or hyper-parameters to tune. Through thorough empirical experiments involving hundreds of training episodes, we demonstrate how RankMe can be used for hyperparameter selection with nearly no reduction in final performance compared to the current selection method that involve a dataset’s labels. We hope that RankMe will facilitate the deployment of JE-SSL towards domains that do not have the opportunity to rely on labels for representations’ quality assessment.

Recent progress has been made towards learning invariant or equivariant representations with self-supervised learning. While invariant methods are evaluated on large scale datasets, equivariant ones are evaluated in smaller, more controlled, settings. We aim at bridging the gap between the two in order to learn more diverse representations that are suitable for a wide range of tasks. We start by introducing a dataset called 3DIEBench, consisting of renderings from 3D models over 55 classes and more than 2.5 million images where we have full control on the transformations applied to the objects. We further introduce a predictor architecture based on hypernetworks to learn equivariant representations with no possible collapse to invariance. We introduce SIE (Split Invariant-Equivariant) which combines the hypernetwork-based predictor with representations split in two parts, one invariant, the other equivariant, to learn richer representations. We demonstrate significant performance gains over existing methods on equivariance related tasks from both a qualitative and quantitative point of view. We further analyze our introduced predictor and show how it steers the learned latent space. We hope that both our introduced dataset and approach will enable learning richer representations without supervision in more complex scenarios. Code and data are available at https://github.com/garridoq/SIE.

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.

Hyperspectral images (HSIs) consist of rich spatial and spectral information, which can potentially be used for several applications. However, noise, band correlations, and high dimensionality restrict the applicability of such data. This is recently addressed using creative deep learning network architectures, such as ResNet, spectral-spatial residual network (SSRN), and attention-based adaptive spectral-spatial kernel residual networks (A2S2K). However, the last layer, i.e., the classification layer, remains unchanged and is taken to be the softmax classifier. In this article, we propose to use a watershed classifier. Watershed classifier extends the watershed operator from Mathematical Morphology for classification. In its vanilla form, the watershed classifier does not have any trainable parameters. In this article, we propose a novel approach to train deep learning networks to obtain representations suitable for the watershed classifier. The watershed classifier exploits the connectivity patterns, a characteristic of HSI datasets, for better inference. We show that exploiting such characteristics allows the Triplet-Watershed to achieve state-of-art results in supervised and semi-supervised contexts. These results are validated on Indian Pines (IP), University of Pavia (UP), Kennedy Space Center (KSC), and University of Houston (UH) datasets, relying on simple convnet architecture using a quarter of parameters compared to previous state-of-the-art networks. The source code for reproducing the experiments and supplementary material (high-resolution images) is available athttps://github.com/ac20/TripletWatershed_Code.

Component-graphs provide powerful and complex structures for multi-band image processing. We propose a multiband astronomical source detection framework with the component-graphs relying on a new set of component attributes. We propose two modules to differentiate nodes belong to distinct objects and to detect partial object nodes. Experiments demonstrate an improved capacity at detecting faint objects on a multi-band astronomical dataset.

We propose an efficient algorithm that removes unimportant regions from a hierarchical partition tree, while preserving the hierarchical partition structure. Various experiments demonstrate that applying this algorithm on various classification or segmentation problems does indeed improve the results by a large margin. Code is available online at https://github.com/higra/Higra. B. Perret, G. Chierchia, J. Cousty, S.J. F. Guimarães, Y. Kenmochi, L. Najman, Higra: Hierarchical Graph Analysis, SoftwareX, 10, 1--6, ISSN 2019, 2352-7110, 10.1016/j.softx.2019.100335.

Watershed technique from mathematical morphology (MM) is one of the most widely used operators for image segmentation. Recently watersheds are adapted to edge weighted graphs, allowing for wider applicability. However, a few questions remain to be answered - How do the boundaries of the watershed operator behave? Which loss function does the watershed operator optimize? How does watershed operator relate with existing ideas from machine learning. In this letter, a framework is developed, which allows one to answer these questions. This is achieved by generalizing the maximum margin principle to maximum margin partition and proposing a generic solution, morphMedian, resulting in the maximum margin principle. It is then shown that watersheds form a particular class of morphMedian classifiers. Using the ensemble technique, watersheds are also extended to ensemble watersheds. These techniques are compared with relevant methods from the literature and it is shown that watersheds perform better than support vector machines on some datasets, and ensemble watersheds usually outperform random forest classifiers.

Clustering is one of the most important steps in the data processing pipeline. Of all the clustering techniques, perhaps the most widely used technique is K-Means. However, K-Means does not necessarily result in clusters which are spatially connected and hence the technique remains unusable for several remote sensing, geoscience and geographic information science (GISci) data. In this article, we propose an extension of K-Means algorithm which results in spatially connected clusters. We empirically verify that this indeed is true and use the proposed algorithm to obtain most significant group of waterbodies mapped from multispectral image acquired by IRS LISS-III satellite.

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.

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.

Classification of remotely sensed data is an important task for many practical applications. However, it is not always possible to get the ground truth for supervised learning methods. Thus unsupervised methods form a valuable tool in such situations. Such methods are referred to as clustering methods. There exists several strategies for clustering the given data - K-means, density based methods, spectral clustering etc. Recently we proposed a novel method for clustering data - Power Spectral Clustering. In this article we aim to introduce the method in the context of Geoscience and Remote Sensing, apply the method to hyperspectral data and validate its applicability to remotely sensed images.

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.

In this paper, we provide a formal proof of the power watershed framework relying on the $\Gamma$-convergence framework. The main ingredient for the proof is a concept of scale. The proof and the formalism introduced in this paper have the added benefit of clarifying the algorithm and allowing extension of the applicability of the power watershed algorithm to many other types of energy functions. Several examples of applications are provided, including total variation and spectral clustering.

As image processing and analysis techniques improve, an increasing number of procedures in bio-medical analyses can be automated. This brings many benefits, e.g improved speed and accuracy, leading to more reliable diagnoses and follow-up, ultimately improving patients outcome. Many automated procedures in bio-medical imaging are well established and typically consist of detecting and counting various types of cells (e.g. blood cells, abnormal cells in Pap smears, and so on). In this article we propose to automate a different and difficult set of measurements, which is conducted on the cilia of people suffering from a variety of respiratory tract diseases. Cilia are slender, microscopic, hair-like structures or organelles that extend from the surface of nearly all mammalian cells. Motile cilia, such as those found in the lungs and respiratory tract, present a periodic beating motion that keep the airways clear of mucus and dirt. In this paper, we propose a fully automated method that computes various measurements regarding the motion of cilia, taken with high-speed video-microscopy. The advantage of our approach is its capacity to automatically compute robust, adaptive and regionalized measurements, i.e. associated with different regions in the image. We validate the robustness of our approach, and illustrate its performance in comparison to the state-of-the-art.

Angiographic imaging is a crucial domain of medical imaging. In particular, Magnetic Resonance Angiography (MRA) is used for both clinical and research purposes. This article presents the first framework geared toward the design of virtual MRA images from real MRA images. It relies on a pipeline that involves image processing, vascular modeling, computational fluid dynamics and MR image simulation, with several purposes. It aims to provide to the whole scientific community (1) software tools for MRA analysis and blood flow simulation; and (2) data (computational meshes, virtual MRAs with associated ground truth), in an open-source/open-data paradigm. Beyond these purposes, it constitutes a versatile tool for progressing in the understanding of vascular networks, especially in the brain, and the associated imaging technologies. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

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.

Latecki et al. have introduced the notion of well-composed images, i.e., a class of images free from the connectivities paradox of discrete topology. Unfortunately natural and synthetic images are not a priori well-composed, usually leading to topological issues. Making any nD image well-composed is interesting because, afterwards, the classical connectivities of components are equivalent, the component boundaries satisfy the Jordan separation theorem, and so on. In this paper, we propose an algorithm able to make nD images well-composed without any interpolation. We illustrate on text detection the benefits of having strong topological properties.

The non-horizontal cuts of a hierarchy and the floodings of an image are well-established tools for image segmenting and filtering respectively. We present definitions of non-horizontal cuts and of floodings in the same framework of hierarchies of partitions. We show that, given a hierarchy, there is a one-to-one correspondence between the non-horizontal cuts and the floodings. This opens the door to optimal image filtering based on non-horizontal cuts and, conversely, to nonhorizontal cuts obtained by morphological floodings, or more generally by connected filterings.

In this paper, we consider the estimation of a reference shape from a set of different segmentation results using both active contours and information theory. The reference shape is defined as the minimum of a criterion that benefits from both the mutual information and the joint entropy of the input segmentations and is then called a mutual shape. This energy criterion is here justified using similarities between information theory quantities and area measures, and presented in a continuous variational framework. This framework brings out some interesting evaluation measures such as the specificity and sensitivity. In order to solve this shape optimization problem, shape derivatives are computed for each term of the criterion and interpreted as an evolution equation of an active contour. Some synthetical examples allow us to cast the light on the difference between our mutual shape and an average shape. Our framework has been considered for the estimation of a mutual shape for the evaluation of cardiac segmentation methods in MRI.

Many methods based on the morphological notion of shapes (i.e., connected components of level sets) have been proved to be very efficient in shape recognition and shape analysis. The inclusion relationship of the level lines (boundaries of level sets) forms the tree of shapes, a tree-based image representation with a high potential. Numerous applications using this tree representation have been proposed. In this article, we propose an efficient algorithm that extracts a set of disjoint level lines in the image. These selected level lines yield a simplified image with clean contours, which provides an intuitive idea about the main structure of the tree of shapes. Besides, we obtain a saliency map without transition problems around the contours by weighting level lines with their significance. Experimental results demonstrate the efficiency and usefulness of our method.

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.

Among the different methods producing superpixel segmentations of an image, the graph-based approach of Felzenszwalb and Huttenlocher is broadly employed. One of its interesting properties is that the regions are computed in a greedy manner in quasi-linear time by using a minimum spanning tree. The algorithm may be trivially extended to video segmentation by considering a video as a 3D volume, however, this can not be the case for causal segmentation, when subsequent frames are unknown. In a framework exploiting minimum spanning trees all along, we propose an efficient video segmentation approach that computes temporally consistent pixels in a causal manner, filling the need for causal and real time applications.

Many methods relying on the morphological notion of shapes, (i.e., connected components of level sets) have been proved to be very useful for pattern analysis and recognition. Selecting meaningful level lines (boundaries of level sets) yields to simplify images while preserving salient structures. Many image simplification and/or segmentation methods are driven by the optimization of an energy functional, for instance the Mumford-Shah functional. In this article, we propose an efficient shape-based morphological filtering that very quickly compute to a locally (subordinated to the tree of shapes) optimal solution of the piecewise-constant Mumford-Shah functional. Experimental results demonstrate the efficiency, usefulness, and robustness of our method, when applied to image simplification, pre-segmentation, and detection of affine regions with viewpoint changes.

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.

Algorithms based on total variation (TV) minimization are prevalent in image processing. They play a key role in a variety of applications such as image denoising, compressive sensing, and inverse problems in general. In this work, we extend the TV dual framework that includes Chambolle's and Gilboa and Osher's projection algorithms for TV minimization. We use a flexible graph data representation that allows us to generalize the constraint on the projection variable. We show how this new formulation of the TV problem may be solved by means of fast parallel proximal algorithms. In denoising and deblurring examples, the proposed approach is shown not only to perform better than recent TV-based approaches, but also to perform well on arbitrary graphs instead of regular grids. The proposed method consequently applies to a variety of other inverse problems including image fusion and mesh filtering.

In this work, we present a hybrid algorithm to automatically delineate the heart volume in 3D cardiac computed tomography (CT) datasets for the visualization of coronary arteries. Our work eliminates the tedious and time consuming step of manually removing obscuring structures around the heart (ribs, sternum, liver...). It quickly provides a clear and well defined view of the coronaries. So far, works related to heart segmentation have mainly focused on heart cavities delineation, which is not suited for coronaries visualization. In contrast, our algorithm extracts the heart cavities, the myocardium and coronaries as a single object. The proposed approach is based on the fitting of a geometric model of the heart to a set of automatically extracted 3D points lying on the heart shell. A novel two-stage fitting scheme is used to improve the robustness to the outliers. The fitting result is further refined using a Random Walker (RW) segmentation approach. Qualitative analysis of results obtained on a 70 exam database shows the efficiency and the accuracy of our approach.

Image segmentation can be defined as the detection of closed contours surrounding objects of interest. Given a family of closed curves obtained by some means, a difficulty is to extract the relevant ones. A classical approach is to define an energy minimization framework, where interesting contours correspond to local minima of this energy. Active contours, graph cuts or minimum ratio cuts are instances of such approaches. In this article, we propose a novel efficient ratio-cut estimator which is both context-based and can be interpreted as an active contour. As a first example of the effectiveness of our formulation, we consider the tree of shapes, which provides a family of level lines organized in a tree hierarchy through an inclusion relationship. Thanks to the tree structure, the estimator can be computed incrementally in an efficient fashion. Experimental results on synthetic and real images demonstrate the robustness and usefulness of our method.

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.

Algorithms based on the minimization of the Total Variation are prevalent in computer vision. They are used in a variety of applications such as image denoising, compressive sensing and inverse problems in general. In this work, we extend the TV dual framework that includes Chambolle's and Gilboa Osher's projection algorithms for TV minimization in a flexible graph data representation by generalizing the constraint on the projection variable. We show how this new formulation of the TV problem may be solved by means of a fast parallel proximal algorithm, which performs better than the classical TV approach for denoising, and is also applicable to inverse problems such as image deblurring.

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.

Maximum flow (and minimum cut) algorithms have had a strong impact on computer vision. In particular, graph cut algorithms provide a mechanism for the discrete optimization of an energy functional which has been used in a variety of applications such as image segmentation, stereo, image stitching, and texture synthesis. Algorithms based on the classical formulation of max-flow defined on a graph are known to exhibit metrication artifacts in the solution. Therefore, a recent trend has been to instead employ a spatially continuous maximum flow (or the dual min-cut problem) in these same applications to produce solutions with no metrication errors. However, known fast continuous max-flow algorithms have no stopping criteria or have not been proved to converge. In this work, we revisit the continuous max-flow problem and show that the analogous discrete formulation is different from the classical max-flow problem. We then apply an appropriate combinatorial optimization technique to this combinatorial continuous max-flow (CCMF) problem to find a null-divergence solution that exhibits no metrication artifacts and may be solved exactly by a fast, efficient algorithm with provable convergence. Finally, by exhibiting the dual problem of our CCMF formulation, we clarify the fact, already proved by Nozawa in the continuous setting, that the max-flow and the total variation problems are not always equivalent.

Many computer vision applications such as image filtering, segmentation and stereo-vision can be formulated as optimization problems. Whereas in previous decades continuous-domain, iterative procedures were common, recently discrete, convex, globally optimal methods have received a lot of attention. However not all problems in computer vision are convex, for instance L0norm optimization such as seen in compressive sensing. Recently, a novel discrete framework encompassing many known segmentation methods was proposed: power watershed. We are interested to explore the possibilities of this minimizer to solve other problems than segmentation, in particular with respect to unusual norms optimization. In this article we reformulate the problem of anisotropic diffusion as an L0optimization problem, and we show that power watersheds are able to optimize this energy quickly and effectively. This study paves the way for using the power watershed as a useful general-purpose minimizer in many different computer vision contexts.

Most image processing frameworks are not generic enough to provide true reusability of data structures and algorithms. In fact, genericity allows users to write and experiment virtually any method on any compatible input(s). In this paper, we advocate the use of generic programming in the design of image processing software, while preserving performances close to dedicated code. The implementation of our proposal, Milena, a generic and efficient library, illustrates the benefits of our approach.

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.

In this work, we extend a common framework for seeded 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 watersheds 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 power watersheds. Placing the watershed algorithm in this energy minimization framework also opens new possibilities for using unary terms in traditional watershed segmentation and using watersheds to optimize more general models of use in application beyond image segmentation.

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.

The watershed segmentation is a popular tool in image processing. Starting from an initial map, the border thinning transformation produces a map whose minima constitute the catchment basins of the watershed of the initial map. An interesting feature of the transformed map (called border kernel) is to convey not only the watershed partition but also numeric information relative to the initial map. In this paper, we provide the space of all border kernels with a semi lattice and propose morphological operations (relative to this lattice) which allow for merging border kernels and building hierarchies of watersheds based in particular on connected filters.

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.

The choice of a commercial optical character recognition (OCR) engine is important for the process of automatically indexing technical drawings from their title blocks. We would like to benchmark commercial OCR engines with respect to their inclusion in the global digitalisation chain from scanning to understanding the text information contained in a technical drawing document. The crucial (costly) point is the manual correction of OCR recognition errors. By benchmarking, we intend to identify, for our application domain, the causes for OCR errors which are the most costly to correct. For a given OCR engine, we model the correction cost as a function of image characteristics. Thus, our methodology relies on the two following issues: on the one hand, the design of the correction cost, representing the difficulty of correction for a human operator; on the other hand, the classification of image characteristics that may lead to OCR recognition errors. We choose to analyse the behaviour of this correction cost by principal component analysis (PCA), comparing two by two the engines to discover their complementarity. This methodology allows us to obtain a list of domain-dependant problems for OCR engines, classified by importance with respect to the correction cost. This list could then be used to correctly choose the OCR engine, or to enhance the OCR execution, by focusing on the most important problems. While we are confident it could easily be implemented for other document classes, we apply this methodology to the domain of technical drawings, and find that our OCR engines are not adapted to our problem.

This paper presents an application that helps to index archives of technical drawings. Indexing consists of extracting information from the title block in order to ensure document retrieval in a database. The indexing information is usually the drawing number and the title. Today, indexing is mostly done manually. By describing the variability of technical drawing forms, this paper explains why classical automated form recognition methods are hardly applicable to technical drawings. We then present a productive and ergonomic application where specification of the area to index is inter-mixed with the process of recognizing the scanned data, avoiding an a priori analysis which requests a high level of expertise. The recognition relies on the structure of the title block, allowing the approach to deal with the variability of real-world technical drawings.

The watershed is one of the latest segmentation tools developed in mathematical morphology. In order to prevent its oversegmentation, the notion of dynamics of a minimum, based on geodesic reconstruction, has been proposed. In this paper, we extend the notion of dynamics to the contour arcs. This notion acts as a measure of the saliency of the contour. Contrary to the dynamics of minima, our concept reflects the extension and shape of the corresponding object in the image. This representation is also much more natural, because it is expressed in terms of partitions of the plane, i.e., segmentations. A hierarchical segmentation process is then derived, which gives a compact description of the image, containing all the segmentations one can obtain by the notion of dynamics, by means of a simple thresholding. Finally, efficient algorithms for computing the geodesic reconstruction as well as the dynamics of contours are presented.