Theory: discrete geometry, volumes and fuzzy methods

1. Adaptive Mathematical Morphology
   Vladimir Curic, Cris Luengo, Gunilla Borgefors
   Funding: Graduate School in Mathematics and Computing (FMB)
   Period: 1101-
   Abstract: The construction of adaptive structuring elements that adjust their shape and size to the local structures in the image has recently been a popular topic in mathematical morphology. Despite that several methods for the construction of spatially adaptive structuring elements have been proposed, it is still an open problem, both from a theoretical and implementation point of view. An initial goal of this project is to develop a new method for spatially adaptive structuring elements and to further investigate adaptive morphological operators. We have proposed salience adaptive structuring elements that modify their shape and size according to the saliency of the edges in the image. We have examined topological properties of salience adaptive structuring elements and investigated their applicability to image filtering. We intend to further develop new methods for adaptive structuring elements as well as to extend this work towards multi-valued images and sparse image representations. In addition, we plan to study the usefulness of salience adaptive structuring elements in granulometries.

2. Anti-Aliased Euclidean Distance Transform
   Robin Strand
   Partner: Stefan Gustavson, Media and Information Technology, Dept. of Science and Technology, Linköping University
   Funding: TN-faculty, UU
   Period: 0904-
   Abstract: A binary image holds no information on the sub-pixel position of the edge of a sampled object since each sample is considered to be either fully inside or fully outside the object. Therefore, distance values for traditional distance transforms are constrained to values attained in an integer grid. In this project, a model where the intensity values represent the area coverage (the fraction of the pixel that meet the object) is used to approximate the position of the object contour. We assume that the area sampled object is binary and has a smooth contour. When the assumptions are met, we get a distance transform with higher accuracy compared to traditional methods.

3. The Minimum Barrier Distance
   Robin Strand, Filip Malmberg
   Partner: Punam K. Saha, Dept. of Electrical and Computer Engineering and the Dept. of Radiology, University of Iowa, IA, USA
   Funding: TN-faculty, UU
   Period: 1103-
   Abstract: In this project, we introduce a distance function on a fuzzy subset that gives the minimum barrier that has to be passed to go from one point to another. Theoretical properties as well as efficient computational solutions for minimum barrier distance have been developed. An initial application of minimum barrier distance in image segmentation is presented. The experiments show that the minimum barrier distance is robust to noise and blur, and also seed point position, since it captures the total change in membership values across an interface instead of gradient as a measure of slope that is sensitive to noise and blur.

4. Geodesic Computations in Sampled Manifolds
   Anders Brun
   Partners: Ola Nilsson, Dept. of Science and Technology, Linköping University; Martin Reimers, Centre of Mathematics for Applications, University of Oslo, Norway
   Funding: S-faculty, SLU
   Period: 0806-
   Abstract: The estimation of geodesic distances in sampled manifolds and surfaces, such as geometric mesh models in 3-D visualization or abstract sampled manifolds in image analysis, poses a difficult and computationally demanding problem. Despite the many advances in discrete mathematics and distance transforms, and fast marching and numerical methods for the solution of PDEs, the solution of the eikonal equation in a general manifold chart equipped with an arbitrary sampled metric known only in a discrete set of points has only recently beed adressed in 3-D and higher dimensions by researchers. In this project we focus on accurate computations of geodesic distances and related mappings, such as the log map, in 2-D and 3-D. Applications for such methods are found in computer graphics (e.g. camera movement, texture mapping, tensor field visualization) and basic image analysis (e.g. skeletonization, manifold learning, clustering).

5. Digital Distance Functions and Distance Transforms
   Robin Strand, Gunilla Borgefors
   Partner: Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Hungary; Nicols Normand, IRCCyN, University of Nantes, France
   Funding: TN-faculty, UU; S-faculty, SLU
   Period: 9309-
   Abstract: The distance between any two grid points in a grid is defined by a distance function. In this project, weighted distances have been considered for many years. A generalization of the weighted distances is obtained by using both weights and a neighborhood sequence to define the distance function. The neighborhood sequence allows the size of the neighborhood to vary along the paths.

   In 2011, we published two journal papers and two conference papers on this subject. For example, a survey paper on digital distance functions on three-dimensional grids and a paper on neighborhood sequences in a hexagonal grid.

6. Image Processing and Analysis of 3D Images in the Face- and Body-Centered Cubic Grids
   Robin Strand, Gunilla Borgefors
   Partner: Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary
   Funding: TN-faculty, UU; S-faculty, SLU
   Period: 0308-
   Abstract: The main goal of the project is to develop image analysis and processing methods for volume images digitized in non-standard 3D grids. Volume images are usually captured in one of two ways: either the object is sliced (mechanically or optically) and the slices put together into a volume or the image is computed from raw data, e.g., X-ray or magnetic tomography. In both cases, voxels are usually box-shaped, as the within slice resolution is higher than the between slice distance. Before applying image analysis algorithms, the images are usually interpolated to the cubic grid. However, the cubic grid might not be the best choice. In two dimensions, it has been demonstrated in many ways that the hexagonal grid is theoretically better than the square grid. The body-centered cubic (bcc) grid and the face-centered cubic (fcc) grid are the generalizations to 3D of the hexagonal grid. The fcc grid is a densest packing, meaning that the grid points are positioned in an optimally dense arrangement. The fcc and bcc grids are reciprocal, so the Fourier transform on an fcc grid results in a bcc grid. In some situations, the densest packing (fcc grid) is preferred in the frequency domain, resulting in a bcc grid in spatial domain.

   In 2011, mainly papers on distance functions have been published in this project, see Project 37. See also Project 9.

7. Skeletonization in 3D Discrete Binary Images
   Robin Strand, Ingela Nyström, Gunilla Borgefors
   Partner: Gabriella Sanniti di Baja, Istituto di Cibernetica, CNR, Pozzuoli, Italy
   Funding: TN-faculty, UU; S-faculty, SLU
   Period: 9501-
   Abstract: Skeletonization is a way to reduce dimensionality of digital objects. A skeleton should have the following properties: topologically correct, centred within the object, thin, and fully reversible. In general, the skeleton cannot be both thin and fully reversible. We have been working on 3D skeletonization based on distance transforms for the last decade.
   By finding the set of centers of maximal balls (CMBs) and keeping these as anchor-points in the skeletonization process, the reversibility is guaranteed. In 2011, a paper by Strand on CMBs and some related concepts was presented at the international conference on discrete geometry for computer imagery (DGCI) in Nancy.

8. Spel Coverage Representations
   Joakim Lindblad, Vladimir Curic, Filip Malmberg
   Partners: Nataša Sladoje, Faculty of Technical Sciences, University of Novi Sad, Serbia; Attila Tanacs, Csaba Domokos, and Zoltan Kato, Dept. of Computer Science, Szeged University, Hungary
   Funding: S-faculty, SLU; Graduate School in Mathematics and Computing (FMB)
   Period: 0801-1112
   Abstract: This project concerns the study and development of partial pixel/voxel coverage models for image object representation, where spatial image elements (spels) are allowed fractional coverage by the object. The project involves both development of methods for estimation of partial spel coverage (coverage segmentation) as well as development of methods for properly utilizing the information contained in such segmented images (feature extraction). The project builds on previous experience and knowledge from more general fuzzy representations, where the restriction to coverage representations enables derivation of strong theoretical results.

9. Set Distances and their Application in Image Analysis
   Vladimir Curic, Joakim Lindblad, Hamid Sarve, Gunilla Borgefors
   Partner: Nataša Sladoje, Faculty of Technical Sciences, University of Novi Sad, Serbia
   Funding: Graduate School in Mathematics and Computing (FMB)
   Period: 0908-
   Abstract: Methods for measuring distances between sets, which is a measure of how similar the sets are, can be useful for solving various image analysis related problems, such as registration, image retrieval and segmentation evaluation.

   Depending on how the distance measure is defined, it exhibits different properties, such as metricity, monotonicity, continuity, sensitivity to noise, complexity and speed of computation. It is therefore of interest to study and further develop different set distance measures, to be able to select appropriate distances for the different applications. In this project we evaluate existing and develop new set distances which are useful in image registration related problems. Of particular interest are properties of monotonicity and continuity.

   We have proposed a new set distance between crisp sets of points and evaluated its usefulness for rigid body registration of binary images as well as its applicability for the real task of multi-modal 2D-3D registration of 2D histological sections of bone implant with corresponding 3D synchrotron radiation micro computed tomography (SRCT) bone implant volumes. This work is submitted for a journal publication.

   We extended the proposed set distance for crisp sets to a distance between fuzzy sets and observed the improved registration performance when utilizing fuzzy object representations, as compared to using a crisp object representation of the same resolution. Results of this study were presented at the 14th International Workshop on Combinatorial Image Analysis (IWCIA2011).

10. Direct Curvature Calculation of Surfaces in 3D Volumes
    Erik Wernersson, Cris Luengo, Anders Brun, Gunilla Borgefors
    Funding: S-faculty, SLU
    Period: 1009 -
    Abstract: Curvature is known as a useful local descriptor of 2D surfaces, embedded in 3D space with applications ranging from visualisation to segmentation. With this project, we aim to find elegant ways to calculate curvature directly from volumetric data which might be flawed with artifacts and noise. No intermediate surface representations are used to ensure stability. The methods will be useful in the analysis of microCT images of composite materials where curvature can be used as a descriptor of several local properties of wood fibres.

    During 2011, some of the project findings were presented at the 3DIMPVT conference in Hangzhou, China.