Fundamenta Informaticae - Volume 125, issue 3-4

Authors: Dulio, P. | Frosini, A. | Rozenberg, G.

Article Type: Other

DOI: 10.3233/FI-2013-860

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. i-xviii, 2013

Authors: Segers, Hilde | Palenstijn, Willem Jan | Batenburg, Kees Joost | Sijbers, Jan

Article Type: Research Article

Abstract: Discrete tomography (DT) is concerned with the tomographic reconstruction of images that consist of only a small number of grey levels. Recently, DART, a practical algorithm was introduced for discrete tomography, which was validated in the domain of X-ray computed and electron tomography. In this paper, DART is introduced for magnetic resonance imaging. Using simulation experiments, it is shown that the proposed MRI-DART algorithm is capable of computing high quality reconstructions from substantially fewer data compared to state-of-the-art MRI reconstruction methods.

DOI: 10.3233/FI-2013-861

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 223-237, 2013

Authors: Batenburg, K. Joost | Fortes, Wagner | Tijdeman, Robert

Article Type: Research Article

Abstract: Discrete tomography deals with tomographic reconstruction of greyscale images for which the set of possible grey levels is discrete and small. Here, we develop a discrete approximate reconstruction algorithm. Our algorithm computes an image that has only grey values belonging to a given finite set. It also guarantees that the difference between the given projections and the projections of the reconstructed discrete image is bounded. The bound, which is computable, is independent of the image size. We present reconstruction experiments for a range of phantom images and a varying number of grey values.

Keywords: Iterative algorithm, Discrete tomography, Image reconstruction

DOI: 10.3233/FI-2013-862

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 239-259, 2013

Authors: Fiorini, Rodolfo A. | Laguteta, Giuseppe

Article Type: Research Article

Abstract: The first impact of Discrete Tomography (DT) applied to nanoscale technology has been to generate enormous quantity of data. Data Footprint Reduction (DFR) is the process of employing one or more techniques to store a given set of data in less storage space. The very best modern lossless compressors use classical probabilistic models only, and are unable to match high end application requirements, like “Arbitrary Bit Depth” (ABD) resolution and “Dynamic Upscale Regeneration” (DUR), with full information conservation. This paper explores, at core level, the basic properties and relationships of $\mathbb{Q}$ Arithmetic to achieve full numeric information conservation …and regeneration, algorithmically. That knowledge shows strong connections to modular group theory and combinatorial optimization. Traditional $\mathbb{Q}$ Arithmetic can be even regarded as a highly sophisticated open logic, powerful and flexible LTR and RTL formal numeric language of languages, with self-defining consistent word and rule, starting from elementary generator and relation. This new awareness can guide the development of successful more convenient algorithm and application. Show more

Keywords: Discrete Tomography, Arithmetic Geometry, Lossless Compression, Data Footprint Reduction, Biomedical Cybernetics, Biomedical Engineering, Public Health, Healthcare

DOI: 10.3233/FI-2013-863

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 261-272, 2013

Authors: Fiorini, Rodolfo A. | Condorelli, Andrea | Laguteta, Giuseppe

Article Type: Research Article

Abstract: In Discrete Tomography (DT) by electron microscopy, 2-D projection images are acquired from various angles, by tilting the sample, generating new challenges associated with the problem of formation, acquisition, compression, transmission, and analysis of enormous quantity of data. Data Footprint Reduction (DFR) is the process of employing one or more techniques to store a given set of data in less storage space. Modern lossless compressors use classical probabilistic models only, and are unable to match high end application requirements like “Arbitrary Bit Depth” (ABD) resolution and information “Dynamic Upscale Regeneration” (DUR). Traditional $\mathbb{Q}$ Arithmetic can be regarded as …a highly sophisticated open logic, powerful and flexible bidirectional (LTR and RTL) formal language of languages, according to brand new “Information Conservation Theory” (ICT). This new awareness can offer competitive approach to guide more convenient algorithm development and application for combinatorial lossless compression, we named “Natural Compression” (NC). To check practical implementation performance, a first raw example is presented, benchmarked to standard, more sophisticate lossless JPEG2000 algorithm, and critically discussed. NC raw overall lossless compression performance compare quite well to standard one, but offering true ABD and DUR at no extra computational cost. Show more

Keywords: Discrete Tomography, Arithmetic Geometry, Lossless Compression, Data Footprint Reduction, Biomedical Cybernetics, Biomedical Engineering, Public Health, Healthcare

DOI: 10.3233/FI-2013-864

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 273-284, 2013

Authors: Petra, Stefania | Schnörr, Christoph | Schröder, Andreas

Article Type: Research Article

Abstract: We analyze representative ill-posed scenarios of tomographic PIV (particle image velocimetry) with a focus on conditions for unique volume reconstruction. Based on sparse random seedings of a region of interest with small particles, the corresponding systems of linear projection equations are probabilistically analyzed in order to determine: (i) the ability of unique reconstruction in terms of the imaging geometry and the critical sparsity parameter, and (ii) sharpness of the transition to non-unique reconstruction with ghost particles when choosing the sparsity parameter improperly. The sparsity parameter directly relates to the seeding density used for PIV in experimental fluids dynamics that is …chosen empirically to date. Our results provide a basic mathematical characterization of the PIV volume reconstruction problem that is an essential prerequisite for any algorithm used to actually compute the reconstruction. Moreover, we connect the sparse volume function reconstruction problem from few tomographic projections to major developments in compressed sensing. Show more

Keywords: compressed sensing, underdetermined nonnegative linear systems, sparsity, large deviation, tail bound, limited angle tomography, TomoPIV

DOI: 10.3233/FI-2013-865

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 285-312, 2013

Authors: Barcucci, Elena | Brocchi, Stefano

Article Type: Research Article

Abstract: Discrete tomography deals with the reconstruction of discrete sets with given projections relative to a limited number of directions, modeling the situation where a material is studied through x-rays and we desire to reconstruct an image representing the scanned object. In many cases it would be interesting to consider the projections to be related to more than one distinguishable type of cell, called atoms or colors, as in the case of a scan involving materials of different densities, as a bone and a muscle. Unfortunately the general n-color problem with n > 1 is NP-complete, but in this paper we …show how several polynomial reconstruction algorithms can be defined by assuming some prior knowledge on the set to be rebuilt. In detail, we study the cases where the union of the colors form a set without switches, a convex polyomino or a convex 8-connected set. We describe some efficient reconstruction algorithms and in a case we give a sufficient condition for uniqueness. Show more

DOI: 10.3233/FI-2013-866

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 313-328, 2013

Authors: Bilotta, Stefano | Rinaldi, Simone | Socci, Samanta

Article Type: Research Article

Abstract: In this paper we consider the class of column-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations (π1 , π2 ). First, using a geometric construction, we prove that for every permutation π there is at least one column-convex permutomino P such that π1 (P) = π or π2 (P) = π. In the second part of the paper, we show how, for any given permutation π, it is possible to define a set of logical implications $\cal{F}(\pi)$ on the points of π, and prove that there exists a column-convex permutomino P such that π1 (P) …= π if and only if $\cal{F}(\pi)$ is satisfiable. This property can be then used to give a characterization of the set of column-convex permutominoes P such that π1 (P) = π. Show more

Keywords: Permutations, Polyominoes, Permutominoes

DOI: 10.3233/FI-2013-867

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 329-342, 2013

Authors: Hantos, Norbert | Balázs, Péter

Article Type: Research Article

Abstract: Reconstruction of binary images from their projections is one of the main tasks in many image processing areas, therefore determining the computational complexity of those problems is essential. The reconstruction complexity is highly dependent on the requirements of the image. In this paper, we will show that the reconstruction is NP-complete if the horizontal and vertical projections and the morphological skeleton of the image are given, and it is supposed that the image is 4-connected.

Keywords: reconstruction from projections, binary tomography, NP-completeness, polyomino, morphological skeleton

DOI: 10.3233/FI-2013-868

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 343-359, 2013

Authors: Fedele, Roberto | Ciani, Antonia | Galantucci, Luca | Bettuzzi, Matteo | Andena, Luca

Article Type: Research Article

Abstract: In this study a robust strategy for 3D-Volume Digital Image Correlation (DIC) is presented, apt to provide accurate kinematic measurements within a loaded sample on the basis of three-dimensional digital images by X-ray computed micro-tomography. In the framework of a Galerkin, finite element discretization of the displacement field, the inverse problem of estimating 3D motion inside the bulk material is solved recursively on a hierarchical family of grids, linked by suitable restriction and prolongation operators. Such structured grids are defined over an image pyramid, which is generated starting from the raw tomographic reconstructions by a reiterated application of average filters …and sub-sampling operators. To achieve robust estimates of the underlying displacement fields, multi-grid cycles are performed ascending and descending along the pyramid in a selected sequence. At each scale, the least-square matching function for DIC is enriched by means of a penalty term in the spirit of Tychonoff regularization, including as a priori information the estimate achieved at the previous grid and transferred to the current scale. For each grid only one Newton iteration can be considered, implying important time savings. Results are presented concerning a laboratory X-ray micro-tomography experiment on a polymeric foam sample, subjected to loading by an apparatus ad-hoc realized. Show more

Keywords: Volume Digital Image Correlation, X-ray micro-tomography, Ill-posed Inverse Problems, Tychonoff regularization, Cellular materials

DOI: 10.3233/FI-2013-869

Citation: Fundamenta Informaticae, vol. 125, no. 3-4, pp. 361-376, 2013