Combinatorial Image Analysis

In this paper, we define a new flavour of well-composedness, called Euler well-composedness, in the general setting of regular cell complexes: A regular cell complex is Euler well-composed if the Euler characteristic of the link of each boundary vertex is 1. A cell decomposition of a picture I is a pair of regular cell complexes \(\big (K(I),K(\bar{I})\big )\) such that K(I) (resp. \(K(\bar{I})\)) is a topological and geometrical model representing I (resp. its complementary, \(\bar{I}\)). Then, a cell decomposition of a picture I is self-dual Euler well-composed if both K(I) and \(K(\bar{I})\) are Euler well-composed. We prove in this paper that, first, self-dual Euler well-composedness is equivalent to digital well-composedness in dimension 2 and 3, and second, in dimension 4, self-dual Euler well-composedness implies digital well-composedness, though the converse is not true.

Constructing a discretization of a given set is a major problem in various theoretical and applied disciplines. An offset discretization of a set X is obtained by taking the integer points inside a closed neighborhood of X of a certain radius. In this note we determine a minimum threshold for the offset radius, beyond which the discretization of an arbitrary (possibly disconnected) set is always connected. The results hold for a broad class of disconnected subsets of \(\mathbb {R}^n\), and generalize several previous results.

In this study the Voronoi interpolation is used to interpolate a set of points drawn from a topological space with higher homology groups on its filtration. The technique is based on Voronoi tessellation, which induces a natural dual map to the Delaunay triangulation. Advantage is taken from this fact calculating the persistent homology on it after each iteration to capture the changing topology of the data. The boundary points are identified as critical. The Bottleneck and Wasserstein distance serve as a measure of quality between the original point set and the interpolation. If the norm of two distances exceeds a heuristically determined threshold, the algorithm terminates. We give the theoretical basis for this approach and justify its validity with numerical experiments.

We consider the problem of reconstructing a nanocrystal at atomic resolution from electron microscopy images taken at a few tilt angles. A popular reconstruction approach called discrete tomography confines the atom locations to a coarse spatial grid, which is inspired by the physical a priori knowledge that atoms in a crystalline solid tend to form regular lattices. Although this constraint has proven to be powerful for solving this very under-determined inverse problem in many cases, its key limitation is that, in practice, defects may occur that cause atoms to deviate from regular lattice positions. Here we propose a grid-free discrete tomography algorithm that allows for continuous deviations of the atom locations similar to super-resolution approaches for microscopy. The new formulation allows us to define atomic interaction potentials explicitly, which results in a both meaningful and powerful incorporation of the available physical a priori knowledge about the crystal’s properties. In computational experiments, we compare the proposed grid-free method to established grid-based approaches and show that our approach can indeed recover the atom positions more accurately for common lattice defects.

A frequently investigated problem in various applications of binary image processing is to ensure the topology preservation of image operators, where the concept of simple points plays a key role. The literature primarily focuses on 2D and 3D images that are sampled on the conventional square and cubic grids, respectively. This paper presents some new characterizations of simple points on the body-centered cubic grid.

In this paper, we prove that the two flavours of well-composedness called Continuous Well-Composedness (shortly CWCness), stating that the boundary of the continuous analog of a discrete set is a manifold, and Digital Well-Composedness (shortly DWCness), stating that a discrete set does not contain any critical configuration, are not equivalent in dimension 4. To prove this, we exhibit the example of a configuration of 8 tesseracts (4D cubes) sharing a common corner (vertex), which is DWC but not CWC. This result is surprising since we know that CWCness and DWCness are equivalent in 2D and 3D. To reach our goal, we use local homology.

The study of two-dimensional picture languages has a wide application in image analysis and pattern recognition [5, 7, 13, 17]. There are various models such as grammars, automata, P systems and Petri Nets to generate different picture languages available in the literature [1–4, 6, 8, 10–12, 14, 15, 18]. In this paper we consider Petri Nets generating tetrahedral picture languages. The patterns generated are interesting, new and are applicable in floor design, wall design and tiling. We compare the generative power of these Petri Nets with that of other recent models [9, 16] developed by our group.

The connection between picture languages and restarting automata has been established in Otto (2014). An interesting class of picture languages generated by parallel contextual array grammars was studied with application in image generation and analysis in Subramanian et al. (2008). In this paper, we introduce a variant of two dimensional restarting automata that accepts a subclass of parallel internal contextual array languages. We show that these automata can simulate parallel internal column contextual array grammars in reverse order.

In some cases of tomography, the projection acquisition process has limits, and thus one cannot gain enough projections for an exact reconstruction. In this case, the low number of projections leads to a lack of information, and uncertainty in the reconstructions. In practice this means that the pixel values of the reconstruction are not uniquely determined by the measured data and thus can have variable values. In this paper, we provide a theoretically proven uncertainty measure that can be used for measuring the variability of pixel values in grayscale reconstructions. The uncertainty values are based on linear algebra and measure the slopes of the hyperplane of solutions in the algebraic formulation of tomography. The methods can also be applied for any linear equation system, that satisfy a given set of conditions. Using the uncertainty measure, we also derive upper and lower limits on the possible pixel values in tomographic reconstructions.

An annulus is basically a ring-shaped region between two concentric disks on the same plane. However, it can be defined on any other geometrical shapes, for example, a rectangular annulus is defined as the area between two rectangles with one rectangle enclosing the other. The area of the annulus is the area of the region between the two shapes. An axis-parallel rectangular annulus is an annulus where the sides of the rectangles are parallel to the co-ordinate axes. This paper presents a combinatorial technique to find the largest empty axis-parallel rectangular annulus from a given set of n points and runs in \(O(n\log n)\) time. It uses two balanced binary search trees to store the points and reduces the complexity of the existing algorithm in the literature.

Siromoney et al. introduced Siromoney matrix grammars (1973) which are of sequential-parallel type in the sense that first a horizontal string of nonterminals is derived sequentially by applying the horizontal production rules and then vertical productions are applied in parallel to get the intended two-dimensional picture. In 1999, Radhakrishnan et al. introduced and studied a variant of Siromoney matrix grammars called (X:Y)MG where \(X, Y \in \{Context-Free (CF), Regular(R)\}\). James et al. in 2018 introduced Parallel Contextual Array Insertion Deletion Grammar (PCAIDG) to generate two-dimensional array languages using insertion and deletion operations and parallel contextual mappings. In this paper, we prove that this family of languages generated by PCAIDGs properly includes the family (CF : CF) ML.

This paper addresses the hyperplane fitting problem of discrete points in any dimension (i.e. in \(\mathbb {Z}^d\)). For that purpose, we consider a digital model of hyperplane, namely digital hyperplane, and present a combinatorial approach to find the optimal solution of the fitting problem. This method consists in computing all possible digital hyperplanes from a set \(\mathbf {S}\) of n points, then an exhaustive search enables us to find the optimal hyperplane that best fits \(\mathbf {S}\). The method has, however, a high complexity of \(O(n^d)\), and thus can not be applied for big datasets. To overcome this limitation, we propose another method relying on the Delaunay triangulation of \(\mathbf {S}\). By not generating and verifying all possible digital hyperplanes but only those from the elements of the triangulation, this leads to a lower complexity of \(O(n^{\lceil \frac{d}{2} \rceil + 1})\). Experiments in 2D, 3D and 4D are shown to illustrate the efficiency of the proposed method.

A 2D binary image is well-composed if it does not contain a \(2\times 2\) configuration of two diagonal black and two diagonal white squares. We propose a simple repairing algorithm to construct two well-composed images \(I_4\) and \(I_8\) starting from an image I, and we prove that \(I_4\) and \(I_8\) are homotopy equivalent to I with 4- and 8-adjacency, respectively. This is achieved by passing from the original square grid to another one, rotated by \(\pi /4\), whose pixels correspond to the original pixels and to their vertices. The images \(I_4\) and \(I_8\) are double in size with respect to the image I. Experimental comparisons and applications are also shown.

Computed Tomography (CT) is a widely used x-ray based imaging modality in radiodiagnostics and non-destructive testing. For medical considerations as well as for economical and environmental reasons, it is desirable to reduce the dose of radiation and to optimize energy used for acquiring x-ray projection images. Especially, in case of elongated objects, using a constant energy spectrum radiation may not provide realistic information about the interior of the examined object. In this paper we provide an adaptive tube voltage selection method, which determines the proper amount of radiation energy on-the-fly, during the acquisition, based on projection information. By experiments on software phantom images we show that this adaptive approach can produce CT images of better quality, and in the same time, by consuming less energy.

Annotating a dataset for training a Supervised Machine Learning algorithm is time and annotator’s attention intensive. Our goal was to create a tool that would enable us to create annotations of the dataset with minimal demands on expert’s time. Inspired by applications such as Tinder, we have created an annotation tool for describing microscopic images. A graphical user interface is used to select from a couple of images the one with the higher value of the examined parameter. Two experiments were performed. The first compares the speed of annotation of our application with the commonly used tool for processing microscopic images. In the second experiment, the texture description was compared with the annotations from MicrAnt application and commonly used application. The results showed that the processing time using our application is 3 times lower and the Spearman coefficient increases by 0.05 than using a commonly used application. In an experiment, we have shown that the annotations processed using our application increase the correlation of the studied parameter and texture descriptors compared with manual annotations .

The topic of this paper includes graph cuts based tomography reconstruction methods in binary and multi-gray level cases. A energy-minimization based reconstruction method for binary tomography is introduced. This approach combines the graph cuts and a gradient based method, and applies a shape orientation as an a priori information. The new method is capable for reconstructions in cases of limited projection view availability. Results of experimental evaluation of the considered graph cuts type reconstruction methods for both binary and multi level tomography are presented .

Cluster Pattern Interface (CLUSPI) [6] is an original 2D encoding and a related technology for direct point-and-click interfaces. It allows determining the objects printed on a surface pointed out by the user. The surface is covered by a layer of code composed of tiny dots, which blends with the original surface texture. In practice, however, some of the dots of the code may be damaged or obscured, which creates decoding challenges. In this work we develop theoretical solutions to some of the challenges related to decoding noisy patterns.

Thinning is a frequently used approach to produce all kinds of skeleton-like shape features in a topology-preserving way. It is an iterative object reduction: some border points of binary objects are deleted, and the entire process is repeated until stability is reached. In the conventional implementation of thinning algorithms, we have to investigate the deletability of all border points in each iteration step. In this paper, we introduce the concept of k-attempt thinning (\(k\ge 1\)). In the case of a k-attempt algorithm, if a border point ‘survives’ at least k successive iterations, it is ‘immortal’ (i.e., it belongs to the produced feature). We propose a computationally efficient implementation scheme for k-attempt thinning. It is shown that an existing parallel thinning algorithm is 5-attempt, and the advantage of the new implementation scheme over the conventional one is also illustrated.

One of the most common methods for counterfeiting digital images is copy-move forgery detection (CMFD). It implies that part of the image is copied and pasted to another part of the same image. The purpose of such changes is to hide certain image content, or to duplicate image content. The aim of this paper is to propose a new clustering algorithm for edited images. The image is divided into non-overlapping blocks. New fuzzy metric is used to calculate the distance between the blocks. In this research the metaheuristic method of the variable neighbourhood search (VNS) is used for the classification of the block. The aim of the classification is that the division should be on the changed and unchanged blocks. The results of this research are compared with the latest results from the literature dealing with this problem and it is shown that the proposed algorithm gives better results. Publicly available image databases were used. The proposed algorithm was implemented in the Python programming language.