Search

Taking advantage of the topological and isotopic properties of binary digital images, we present here anew algorithm for connected component labeling (CLL). A local-to-global treatment of the topologicalinformation within the image, allows us to develop an inherent parallel approach. The time complexityorder for an image of m ×n pixels, under the assumption that a processing element exists for each pixel, is near O (log(m + n )) . Additionally, our method computes both the foreground and background CCL, and allows a straightforward computation of topological features like Adjacency Trees. Experiments show thatour method obtains better performance metrics than other approaches. Our work aims at generating anew class of labeling algorithms: those centered in fully parallel approaches based on computationaltopology, thus allowing a perfect concurrent execution in multiple threads and preventing the use ofcritical sections and atomic instructions. Ministerio de Economía y Competitividad MTM2016-81030-P Ministerio de Economía y Competitividad TEC2012-37868-C04-02

Fractal dimension is a powerful tool employed as a measurement of geometric aspects. In this work we propose a method of topological fractal analysis for 2D binary digital images by using a graph-based topological model of them, called Homological Spanning Forest (HSF, for short). Defined at interpixel level, this set of two trees allows to topologically describe the (black and white) connected component distribution within the image with regards to the relationship “to be surrounded by”. This distribution is condensed into a rooted tree, such that its nodes are connected components determined by some special sub-trees of the previous HSF and the levels of the tree specify the degree of nesting of each connected component. We ask for topological auto-similarity by comparing this topological description of the whole image with a regular rooted tree pattern. Such an analysis can be used to directly quantify some characteristics of biomedical images (e.g. cells samples or clinical images) that are not so noticeable when using geometrical approaches. Ministerio de Economía y Competitividad TEC2016-77785-P Ministerio de Economía y Competitividad MTM2016-81030-P

International audience; Discrete gradient vector fields are combinatorial structures that can be used for accelerating the homology computation of CW complexes, such as simplicial or cubical complexes, by reducing their number of cells. Consequently, they provide a bound for the Betti numbers (the most basic homological information). A discrete gradient vector field can eventually reduce the complex to its minimal form, having as many cells of each dimension as its corresponding Betti number, but this is not guaranteed. Moreover, finding an optimal discrete gradient vector field is an NP-hard problem. We describe here a generalization, which we call Homological Discrete Vector Field (HDVF), which can overcome these limitations by allowing cycles under a certain algebraic condition. In this work we define the HDVF and its associated reduction, we study how to efficiently compute a HDVF, we establish the relation between the HDVF and other concepts in computational homology and we estimate the average complexity of its computation. We also introduce five basic operations for modifying a HDVF, which can also be applied to discrete gradient vector fields.

In this paper we develop a new computational technique called boundary scale-space theory. This tech- nique is based on the topol1 ogical paradigm consisting of representing a geometric subdivided object K using a one-parameter family of geometric objects { Ki }i ≥ 1 all of them having the same number of closed pieces than K. Each piece of Ki ( ∀i ≥ 1) presents the same interior part than the corresponding one in K, and a different boundary part depending on the scale i. Working with coefficients in a field, a scale is installed for the algebraic boundary of each piece and a new invariant for cell complex isomorphisms is given in terms of the Betti numbers of the generated boundary-scale-space cell complexes. Moreover, the so called homology boundary scale-space model of K ( hbss -model for short) is introduced here. Thismodel consists of a hierarchical graph whose nodes are the homology generators of the different bound- ary scale levels and whose edges are specified by homology generators of consecutive boundary scaleindices linked by ( hbss -transition maps) preserving homology classes. Various codes for each connectedsubgraph of an hbss -model are defined, which besides being fast and efficient similarity measures for cel- lular structures, they are as well relevant interpretive tools for the hbss -model. Finally, experimentations mainly aimed at clarifying and understanding the notion of hbss -model, as well as conjecturing about new graph isomorphism invariants (seeing graphs as a 1-dimensional cell complexes), are performed. Ministerio de Economía y Competitividad MTM2016-81030-P Ministerio de Economía y Competitividad TEC2016-77785-P

Segmentations of a digital object based on a connectivity criterion at n-xel or sub-n-xel level are useful tools in image topological analysis and recognition. Working with cell complex analogous of digital objects, an example of this kind of segmentation is that obtained from the combinatorial representation so called Homological Spanning Forest (HSF, for short) which, informally, classifies the cells of the complex as belonging to regions containing the maximal number of cells sharing the same homological (algebraic homology with coefficient in a field) information. We design here a parallel method for computing a HSF (using homology with coefficients in Z/2Z) of a 3D digital object. If this object is included in a 3D image of m1 × m2 × m3 voxels, its theoretical time complexity order is near O(log(m1 + m2 + m3)), under the assumption that a processing element is available for each voxel. A prototype implementation validating our results has been written and several synthetic, random and medical tridimensional images have been used for testing. The experiments allow us to assert that the number of iterations in which the homological information is found varies only to a small extent from the theoretical computational time. Ministerio de Economía y Competitividad MTM2016-81030-P

In this paper we design a new family of relations between (co)homology classes, working with coefficients in a field and starting from an AT-model (Algebraic Topological Model) AT(C) of a finite cell complex C These relations are induced by elementary relations of type “to be in the (co)boundary of” between cells. This high-order connectivity information is embedded into a graph-based representation model, called Second Order AT-Region-Incidence Graph (or AT-RIG) of C. This graph, having as nodes the different homology classes of C, is in turn, computed from two generalized abstract cell complexes, called primal and dual AT-segmentations of C. The respective cells of these two complexes are connected regions (set of cells) of the original cell complex C, which are specified by the integral operator of AT(C). In this work in progress, we successfully use this model (a) in experiments for discriminating topologically different 3D digital objects, having the same Euler characteristic and (b) in designing a parallel algorithm for computing potentially significant (co)homological information of 3D digital objects. Ministerio de Economía y Competitividad MTM2016-81030-P Ministerio de Economía y Competitividad TEC2012-37868-C04-02

In this paper, the concept of homogeneity is defined, from a topological perspective, in order to analyze how uniform is the material composition in 2D electron microscopy images. Topological multiresolution parameters are taken into account to obtain better results than classical techniques. Ministerio de Economía y Competitividad MTM2016-81030-P Ministerio de Economía y Competitividad TEC2012-37868-C04-02

In this paper, we make use of the topological invariants of 2D images for an accelerated training and an improved recognition ability of a deep learning neural network applied to digital image objects. For our test images, we generate the associated simplicial complexes and from them we compute the Betti numbers which for a 2D object are the number of connected components and the number of holes. These information are used for training the network according to the corresponding Betti number. Experiments on the MNIST databases are presented in support of the proposed method. European Union (UE). H2020 INFRAIA- 2016-1-730897

Given a 3D binary digital image I, we define and compute an edge-weighted tree, called Homological Region Tree (or Hom-Tree, for short). It coincides, as unweighted graph, with the classical Region Adjacency Tree of black 6-connected components (CCs) and white 26- connected components of I. In addition, we define the weight of an edge (R, S) as the number of tunnels that the CCs R and S “share”. The Hom-Tree structure is still an isotopic invariant of I. Thus, it provides information about how the different homology groups interact between them, while preserving the duality of black and white CCs. An experimentation with a set of synthetic images showing different shapes and different complexity of connected component nesting is performed for numerically validating the method. Ministerio de Economía y Competitividad MTM2016-81030-P

Connected component labeling (CCL) of binary images is one of the fundamental operations in real time applications. The adjacency tree (AdjT) of the connected components offers a region-based representation where each node represents a region which is surrounded by another region of the opposite color. In this paper, a fully parallel algorithm for computing the CCL and AdjT of a binary digital image is described and implemented, without the need of using any geometric information. The time complexity order for an image of m × n pixels under the assumption that a processing element exists for each pixel is near O(log(m+ n)). Results for a multicore processor show a very good scalability until the so-called memory bandwidth bottleneck is reached. The inherent parallelism of our approach points to the direction that even better results will be obtained in other less classical computing architectures. Ministerio de Economía y Competitividad MTM2016-81030-P Ministerio de Economía y Competitividad TEC2012-37868-C04-02

The paper provides a theorem for the characteriza- tion of numerical stability of spline-type systems. These systems are generated through shifted copies of a given atom over a time lattice. Also, we reformulate the well known Gabor systems via modulated spline-type systems and we apply the corresponding numerical stability to these systems. The numerical stability is tested for consistency against deformations. Austrian Science Fund (FWF) P27516

This is an experimental paper in which we introduce the possibility to analyze and to synthesize 3D medical images by using multivariate Gabor frames with Gaussian windows. Our purpose is to apply a space-variant filter-like operation in the space-frequency domain to correct medical images corrupted by different types of acquisitions errors. The Gabor frames are constructed with Gaussian windows sampled on non-separable lattices for a better packing of the space-frequency plane. An implementable solution for 3D-Gabor frames with non-separable lattice is given and numerical tests on simulated data are presented. Austrian Science Fund (FWF) P27516

An appropriate generalization of the classical notion of abstract cell complex, called primal-dual abstract cell complex (pACC for short) is the combinatorial notion used here for modeling and analyzing the topology of nD digital objects and images. Let D ⊂ I be a set of n-xels (ROI) and I be a n-dimensional digital image.We design a theoretical parallel algorithm for constructing a topologically meaningful asymmetric pACC HSF(D), called Homological Spanning Forest of D (HSF of D, for short) starting from a canonical symmetric pACC associated to I and based on the application of elementary homotopy operations to activate the pACC processing units. From this HSF-graph representation of D, it is possible to derive complete homology and homotopy information of it. The preprocessing procedure of computing HSF(I) is thoroughly discussed. In this way, a significant advance in understanding how the efficient HSF framework for parallel topological computation of 2D digital images developed in [2] can be generalized to higher dimension is made. Ministerio de Economía y Competitividad TEC2016-77785-P Ministerio de Economía y Competitividad MTM2016-81030-P

To prevent the release of large quantities of CO2 into the atmosphere, carbon capture and storage (CCS) represents a potential means of mitigating the contribution of fossil fuel emissions to global warming and ocean acidification. Fluvial saline aquifers are favourite targeted reservoirs for CO2 storage. These reservoirs are very heterogeneous but their heterogeneities were rarely integrated into CO2 reservoir models. Moreover, contrary to petroleum reservoirs, the available dataset is very limited and not supposed to be enriched. This leads to wide uncertainties on reservoir characteristics required for CSS management (injection location, CO2 plume migration, etc.). Stochastic simulations are classical strategies in such under-constrained context. They aim at generating a wide number of models that all fit the available dataset. The generated models serve as support for computing the required reservoir characteristics and their uncertainties. A challenge is to optimize the uncertainty computations by selecting stochastic models that should have a priori very different flow behaviours. Fluid flows depend on the connectivity of reservoir rocks (channel deposits). In this paper, it is proposed to study the variability of the Betti numbers in function of different fluvial architectures. The aim is to quantify the impact of fluvial heterogeneities and their spatial distribution on reservoir rock topology and then on CO2 storage capacities. Representative models of different scenarios of channel stacking and their internal heterogeneities are generated using geostatistical simulation approaches. The Betti numbers are computed on each generated models and statistically analysed to exhibit if fluvial architecture controls reservoir topology.

Given a binary object (2D or 3D), its Betti numbers characterize the number of holes in each dimension. They are obtained algebraically, and even though they are perfectly defined, there is no unique way to display these holes. We propose two geometric measures for the holes, which are uniquely defined and try to compensate the loss of geometric information during the homology computation: the thickness and the breadth. They are obtained by filtering the information of the persistent homology computation of a filtration defined through the signed distance transform of the binary object.

n-dimensional discrete objects can be interpreted as cubical complexes which are suitable for the study of their homology groups in order to understand the original discrete object. The classic approach consists in computing the Normal Smith Form of some matrices associated to the cubical complex. Further approaches deal mainly with a pre-processing of the matrices in order to reduce their size. In this paper we propose a new approach, initially based on discrete Morse theory, which computes some homological information (Betti numbers and representative cycles) without calculating the Normal Smith Form. It works on any dimension, and it can also be applied to any kind of regular cell complex.

In this paper, we follow up on the studies developed by Kovalevsky (Comput Vis Graph Image Process 46:141---161, 1989) and Kenmochi et al. (Comput Vis Image Underst 71:281---293, 1998), which defined a continuous analog for a 4-dimensional digital object. Here, we construct a cell complex that has the same topological information as the original 4-dimensional digital object.

The homology of binary 3{dimensional digital images (digi- tal volumes) provides concise algebraic description of their topology in terms of connected components, tunnels and cavities. Homology gener- ators corresponding to these features are represented by nontrivial 0{ cycles, 1{cycles and 2{cycles, respectively. In the framework of cubical representation of digital volumes with the topology that corresponds to the 26{connectivity between voxels, we introduce a method for algorith- mic computation of a coproduct operation that can be used to decom- pose 2{cycles into products of 1{cycles (possibly trivial). This coproduct provides means of classifying di erent kinds of cavities; in particular, it allows to distinguish certain homotopically non-equivalent spaces that have isomorphic homology. We de ne this coproduct at the level of a cubical complex built directly upon voxels of the digital image, and we construct it by means of the classical Alexander-Whitney map on a sim- plicial subdivision of faces of the voxels., Austrian Science Fund - bolsa P20134-N13, Computational Topology and Applied Mathematics" PAICYT projecto de investigação FQM-296, Andalusian research project" PO6-TIC-02268 Austrian Science, Spanish MEC - projecto MTM2006-03722

International audience; This short paper accompanies an invited lecture on a historical survey of geometric computer vision problems. It presents some early works on image-based 3D modeling, multi-view geometry, and structurefrom- motion, from the last three centuries. Some of these are relatively well known to photogrammetrists and computer vision researchers whereas others seem to have been largely forgotten or overlooked. This paper gives a very brief summary of an ongoing historical study.