nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Combinatorial Image Analysis

19th International Workshop, IWCIA 2018, Porto, Portugal, November 22–24, 2018, Proceedings

herausgegeben von: Reneta P. Barneva, Prof. Dr. Valentin E. Brimkov, Dr. João Manuel R.S. Tavares

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 19th International Workshop on Combinatorial Image Analysis, IWCIA 2018, held in Porto, Portugal, in November 2018.
The 18 revised full papers presented were carefully reviewed and selected from 32 submissions. The papers are grouped into two sections. The first one includes nine papers devoted to theoretical foundations of combinatorial image analysis, including digital geometry and topology, array grammars, tilings and patterns, discrete geometry in non-rectangular grids, and other technical tools for image analysis. The second part includes nine papers presenting application-driven research on topics such as discrete tomography, image segmentation, texture analysis, and medical imaging.

Inhaltsverzeichnis

Frontmatter

Theoretical Contributions

Frontmatter

On Gaps in Digital Objects

Abstract

Different formulae were proposed in the literature for the number of gaps in digital objects. We give several new formulae for the number of 0-gaps in 2D, based on the known connection between the number of 0-gaps and the Euler characteristic of 2D digital objects. We also present two new, short and intuitive proofs of one of the two known equivalent formulae for the number of \((n-2)\)-gaps in nD digital objects.

Lidija Čomić

Fixpoints of Iterated Reductions with Equivalent Deletion Rules

Abstract

A reduction transforms a binary picture only by deleting some black points to white ones. Sequential reductions traverse the black points of a picture, and focus on the actually visited point for possible deletion, while parallel reductions delete all ‘deletable’ black points simultaneously. Two reductions are called equivalent if they produce the same result for each input picture. A deletion rule is said to be equivalent if it provides a pair of equivalent sequential and parallel reductions. Thinning and shrinking algorithms iterate reductions until no points are deleted. If a black point is not deleted in an iteration step, it is taken into consideration again in the next step. This work examine fixpoints of iterated reductions with equivalent deletion rules, i.e., ‘survival’ points whose rechecking is not needed in the remaining iterations.

Kálmán Palágyi, Gábor Németh

Parallel Contextual Array Insertion Deletion Grammar

Abstract

We introduce a new grammar, called parallel contextual array insertion deletion grammar and show that it has a strictly higher generative power than a system generating recognizable 2D-picture language and Siromoney context-sensitive matrix grammar.

D. G. Thomas, S. James Immanuel, Atulya K. Nagar, Robinson Thamburaj

Chain Code P System for Generation of Approximation Patterns of Sierpiński Curve

Abstract

A sequence of approximating geometric patterns that define in the limit, the Sierpiński space filling curve is considered and the problem of generation of the infinite set of these patterns is investigated. A P system model in the bio-inspired area of membrane computing is constructed to generate the language of chain code kind of words that describe the approximating geometric patterns of Sierpiński curve.

A. Dharani, R. Stella Maragatham, Atulya K. Nagar, K. G. Subramanian

Digitized Rotations of Closest Neighborhood on the Triangular Grid

Abstract

Rigid motions on the plane play an important role in image processing and in image manipulation. They have many properties including the bijectivity and the isometry. On the other hand, digitized rigid motions may fail to satisfy this injectivity or surjectivity properties. Pluta et al. investigated digitized rigid motions locally on the square grid and the hexagonal grid by using neighborhood motion maps. In this paper we show digitized rigid rotations of a pixel and its closest neighbors on the triangular grid. In particular, different rotation centers are considered with respect to the corresponding main pixel, e.g. edge midpoints and corner points. Angles of all bijective and non-bijective rotations are proven for rotations described above.

Aydın Avkan, Benedek Nagy, Müge Saadetoğlu

Binary Tomography on Triangular Grid Involving Hexagonal Grid Approach

Abstract

In this paper, we consider the binary tomography reconstruction problem of images on the triangular grid. The reconstruction process is based on three natural directions of projections, defined by the lane directions of the triangular grid (they are analogous to row and column directions on the square grid). The recently proposed shifted projection approach is applied, which allows that the number of delta and nabla shape triangular pixels in each lane to be exactly determined. The structure of the set of the same type pixels coincides with the structure of the hexagonal grid. The proposed new reconstruction process solve separately the task for the delta and nabla shape pixels on two hexagonal grids. Experimental results on a number of test images is presented and analyzed. The new method shows advantage in both aspects, quality of the reconstructions and running times.

Benedek Nagy, Tibor Lukić

Sphere Construction on the FCC Grid Interpreted as Layered Hexagonal Grids in 3D

Abstract

In this paper, we propose an algorithm to build discrete spherical shell having integer center and real-valued inner and outer radii on the face-centered cubic (FCC) grid. We address the problem by mapping it to a 2D scenario and building the shell layer by layer on hexagonal grids with additive manufacturing in mind. The layered hexagonal grids get shifted according to need as we move from one layer to another and forms the FCC grid in 3D. However, we restrict our computation strictly to 2D in order to utilize symmetry and simplicity.

Girish Koshti, Ranita Biswas, Gaëlle Largeteau-Skapin, Rita Zrour, Eric Andres, Partha Bhowmick

Quadrangular Mesh Generation Using Centroidal Voronoi Tessellation on Voxelized Surface

Abstract

We propose an efficient algorithm for isotropic tessellation on a voxelized surface. Owing to execution in the voxel space, the algorithm is easily compliant to parallel computation. We show how an input triangle mesh can readily be restructured to an isotropic quadrangular mesh after a post-processing on the tessellated surface. We also show how different regions of the quad mesh can be decimated to finer quads in an adaptive manner based on digital planarity. Necessary theoretical analysis and experimental results have been provided to adjudge its merit.

Ashutosh Soni, Partha Bhowmick

When Can -norm Objective Functions Be Minimized via Graph Cuts?

Abstract

Techniques based on minimal graph cuts have become a standard tool for solving combinatorial optimization problems arising in image processing and computer vision applications. These techniques can be used to minimize objective functions written as the sum of a set of unary and pairwise terms, provided that the objective function is submodular. This can be interpreted as minimizing the \(l_1\)-norm of the vector containing all pairwise and unary terms. By raising each term to a power p, the same technique can also be used to minimize the \(l_p\)-norm of the vector. Unfortunately, the submodularity of an \(l_1\)-norm objective function does not guarantee the submodularity of the corresponding \(l_p\)-norm objective function. The contribution of this paper is to provide useful conditions under which an \(l_p\)-norm objective function is submodular for all \(p\ge 1\), thereby identifying a large class of \(l_p\)-norm objective functions that can be minimized via minimal graph cuts.

Filip Malmberg, Robin Strand

From Theory to Practice

Frontmatter

Detection of Osteoarthritis by Gap and Shape Analysis of Knee-Bone X-ray

Abstract

Osteoarthritis in knee-joints of humans can be diagnosed by analyzing an X-ray image of the bone. The changes in the shape of the concerned bones (tibia and femur), and the variation in joint-gap, provide markers of such a bone disease. In this paper, digital-geometric techniques are deployed to analyze the X-ray image for identifying the change in shape and alignment of knee-bones, if any. The gap between the two sections of a knee-joint is checked for uniformity over the entire length. The shape of bone can also be correlated to the presence of osteophytes, if any. For automated diagnosis of osteoarthritis, the given X-ray image is analyzed to detect the presence of any abnormality in the bone-contour or gap. We use the concept of chain code and relaxed digital straight-line segments (RDSS) in our analysis.

Sabyasachi Mukherjee, Oishila Bandyopadhyay, Arindam Biswas, Bhargab B. Bhattacharya

Registration of CT with PET: A Comparison of Intensity-Based Approaches

Abstract

The integration of functional imaging modality provided by Positron Emission Tomography (PET) and associated anatomical imaging modality provided by Computed Tomography (CT) has become an essential procedure both in the evaluation of different types of malignancy and in radiotherapy planning. The alignment of these two exams is thus of great importance. In this research work, three registration approaches (1) intensity-based registration, (2) rigid translation followed by intensity-based registration and (3) coarse registration followed by fine-tuning were evaluated and compared. To characterize the performance of these methods, 161 real volume scans from patients involved in Hodgkin Lymphoma staging were used: CT volumes used for radiotherapy planning were registered with PET volumes before any treatment. Registration results achieved 78%, 60%, and 91% of accuracy for methods (1), (2) and (3), respectively. Registration methods validation was extended to a corresponding landmarks points distance calculation. Methods (1), (2) and (3) achieved a median improvement registration rate of 66% mm, 51% mm and 70% mm, respectively. The accuracy of the proposed methods was further confirmed by extending our experiments to other multimodal datasets and in a monomodal dataset with different acquisition conditions.

Gisèle Pereira, Inês Domingues, Pedro Martins, Pedro H. Abreu, Hugo Duarte, João Santos

Iterative High Resolution Tomography from Combined High-Low Resolution Sinogram Pairs

Abstract

In some cases of tomography we can only gain high resolution projections of the object with only partial coverage, whereas only a small part of the object – a given Region of Interest (ROI) – is fully covered by high resolution projections. In such cases the structures outside the region of interest cause artefacts to appear in the reconstructed image and degrade the image quality of the tomogram. We proposed three new iterative approaches for the accurate reconstruction of the ROI by combining a high resolution set of projections, with low resolution full field of view projections and prior information. We also evaluate our methods reconstructing software phantoms, and compare their performance to other methods in the literature.

László Varga, Rajmund Mokso

A Multi-channel DART Algorithm

Abstract

Tomography deals with the reconstruction of objects from their projections, acquired along a range of angles. Discrete tomography is concerned with objects that consist of a small number of materials, which makes it possible to compute accurate reconstructions from highly limited projection data. For cases where the allowed intensity values in the reconstruction are known a priori, the discrete algebraic reconstruction technique (DART) has shown to yield accurate reconstructions from few projections. However, a key limitation is that the benefit of DART diminishes as the number of different materials increases. Many tomographic imaging techniques can simultaneously record tomographic data at multiple channels, each corresponding to a different weighting of the materials in the object. Whenever projection data from more than one channel is available, this additional information can potentially be exploited by the reconstruction algorithm. In this paper we present Multi-Channel DART (MC-DART), which deals effectively with multi-channel data. This class of algorithms is a generalization of DART to multiple channels and combines the information for each separate channel-reconstruction in a multi-channel segmentation step. We demonstrate that in a range of simulation experiments, MC-DART is capable of producing more accurate reconstructions compared to single-channel DART.

Mathé Zeegers, Felix Lucka, Kees Joost Batenburg

Evaluation of Chaos Game Representation for Comparison of DNA Sequences

Abstract

Chaos Game Representation (CGR) of DNA sequences has been used for visual representation as well as alignment-free comparisons. CGR is considered to be of great value as the images obtained from parts of a genome present the same structure as those obtained for the whole genome. However, the robustness of the CGR method to compare DNA sequences obtained in a variety of scenarios is not yet fully demonstrated. This paper addresses this issue by presenting a method to evaluate the potential of CGR to distinguish various classes in a DNA dataset. Two indices are proposed for this purpose - a rejection rate (\(\alpha \)) and an overlapping rate (\(\beta \)). The method was applied to 4 datasets, with between 31 to 400 classes each. Nearly 430 million pairs of DNA sequences were compared using the CGR.

André R. S. Marcal

Image-Based Object Spoofing Detection

Abstract

Using 2D images in authentication systems raises the question of spoof attacks: is it possible to deceive an authentication system using fake models possessing identical visual properties of the genuine one? In this work, an anti-spoofing method approach for a wine anti-counterfeiting system is presented. The proposed method relies in two different color spaces: CIE L*u*v* and \(YC_rC_b\), to distinguish between a genuine instance and a spoof attack. To evaluate the proposed strategy, two databases were used: a private database, with photos/2D attacks of cork stoppers, created for this work; and the public Replay-Attack database that is used for face spoofing detection methods testing. The results on the private database show that the anti-spoofing approach is able to distinguish with high accuracy a real photo from an attack. Regarding the public database, the results were obtained with existing methods, as the best HTER results using a single frame approach.

Valter Costa, Armando Sousa, Ana Reis

Improvement of Measurement Accuracy of Optical 3D Scanners by Discrete Systematic Error Estimation

Abstract

A new methodology is introduced which enables the improvement of measurement accuracy of optical 3D scanners. This improvement is based on geometric compensation of the systematic measurement error over the measurement volume. Possible sources for systematic measurement errors are introduced and discussed. Estimation of the systematic error is performed by determination of length measurement error of a ballbar in different positions in the measurement volume. Description of the systematic error may be done using polynomials or sampling points in an equidistant volumetric grid. Simulations as well as experimental measurements using real data were performed in order to evaluate the new methodology. The results show that a reduction of the systematic error to about half of the original error is possible. The method is discussed, and potential improvements are given as prospective future work.

Christian Bräuer-Burchardt, Peter Kühmstedt, Gunther Notni

Defect Detection in Textiles with Co-occurrence Matrix as a Texture Model Description

Abstract

Automatized inspection at textile production lines becomes very important. However, there is still a need to design methods which meet not only demands concerning accuracy of defect detection, but also ones related to the processing time. In this work, a novel approach for defect model definition is presented. It is derived from the idea of co-occurrence matrix. Due to scale incorporation and binarization of the model content it proved to be a very powerful descriptor of the novelties. Moreover, it also satisfies the requirements of short processing time. The defect mask achieved with the introduced method was compared visually to other popular solutions and show a very high accuracy and quality of defect description. The processing time is real-time as the response for a 1MP (megapixel) image is reached within tens of milliseconds.

Karolina Nurzynska, Michał Czardybon

Multiscale Graph-Cut for 3D Segmentation of Compact Objects

Abstract

The article is a step forward towards improving image segmentation using a popular method called Graph-Cut. We focus on optimizing the algorithm for processing data, in which the target object occupies only a small portion of the total volume. We propose a two-step procedure. At the first step, the location of the object is determined roughly. At the second step, Graph-Cut segmentation is performed with a special multi-scale chart structure. Two different graph construction methods are suggested. The calculation time of both variants is compared with the original Graph-Cut method. The msgc_lo2hi method has been shown to provide a statistically significant time reduction of the computational costs.

Miroslav Jirik, Vladimir Lukes, Milos Zelezny, Vaclav Liska

Backmatter

Titel: Combinatorial Image Analysis
herausgegeben von: Reneta P. Barneva
Prof. Dr. Valentin E. Brimkov
Dr. João Manuel R.S. Tavares
Verlag: Springer International Publishing
Electronic ISBN: 978-3-030-05288-1
Print ISBN: 978-3-030-05287-4
DOI: https://doi.org/10.1007/978-3-030-05288-1