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

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 explore the possibility of applying the anisotropic generalized Hough transform (AGHT) enhanced with a Gabor based time-frequency filtering (GTF) for the determination of the mandibular canal in digital dental panoramic radiographs. The proposed method is based on template matching us- ing the fact that the shape of the mandibular canal is usually the same, followed by a filtering of the accumulator space in the Gabor domain for a precise detection of the position. The proposed procedure consists of a detailed description of the shape of the canal in its canonical form and on preserving Gabor filtering information for sorting the hierarchy of location candidates after applying anisotropically the ex- traction algorithm. The experimental results show that the proposed procedure is robust to recognition under occlusion and under the presence of additional structures e.g. teeth, projection errors.

In [14], a topologically consistent framework to support parallel topological analysis and recognition for 2 D digital objects was introduced. Based on this theoretical work, we focus on the problem of finding efficient algorithmic solutions for topological interrogation of a 2 D digital object of interest D of a pre-segmented digital image I , using 4-adjacency between pixels of D . In order to maximize the degree of parallelization of the topological processes, we use as many elementary unit processing as pixels the image I has. The mathematical model underlying this framework is an appropriate extension of the classical concept of abstract cell complex: a primal–dual abstract cell complex (pACC for short). This versatile data structure encompasses the notion of Homological Spanning Forest fostered in [14,15]. Starting from a symmetric pACC associated with I , the modus operandi is to construct via combinatorial operations another asymmetric one presenting the maximal number of non-null primal elementary interactions between the cells of D . The fundamental topological tools have been transformed so as to promote an efficient parallel implementation in any parallel-oriented architecture (GPUs, multi-threaded computers, SIMD kernels and so on). A software prototype modeling such a parallel framework is built.

Membrane Computing is a paradigm inspired from biological cellular communication. Membrane computing devices are called P systems. In this paper we calculate some algebraic-topological information of 2D and 3D images in a general and parallel manner using P systems. First, we present a new way to obtain the homology groups of 2D digital images in time logarithmic with respect to the input data involving an improvement with respect to the algorithms development by S. Peltier et al. Second, we obtain an edge-segmentation of 2D and 3D digital images in constant time with respect to the input data.

An alternate method for constructing (Hadamard) cocyclic matrices over a finite group G is described. Provided that a homological model for G is known, the homological reduction method automatically generates a full basis for 2-cocycles over G (including 2-coboundaries). From these data, either an exhaustive or a heuristic search for Hadamard cocyclic matrices is then developed. The knowledge of an explicit basis for 2-cocycles which includes 2-coboundaries is a key point for the designing of the heuristic search. It is worth noting that some Hadamard cocyclic matrices have been obtained over groups G for which the exhaustive searching techniques are not feasible. From the computational-cost point of view, even in the case that the calculation of such a homological model is also included, comparison with other methods in the literature shows that the homological reduction method drastically reduces the required computing time of the operations involved, so that even exhaustive searches succeeded at orders for which previous calculations could not be completed. With aid of an implementation of the method in MATHEMATICA, some examples are discussed, including the case of very well-known groups (finite abelian groups, dihedral groups) for clarity.

This paper offers an algorithmic solution to the problem of obtaining “economical” formulae for some maps in Simplicial Topology, having, in principle, a high computational cost in their evaluation. In particular, maps of this kind are used for defining cohomology operations at the cochain level. As an example, we obtain explicit combinatorial descriptions of Steenrod View the MathML sourcekth powers exclusively in terms of face operators.