Theory: discrete geometry, volumes and fuzzy methods

1. 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: Graduate School in Mathematics and Computing (FMB); 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, the reversibility is guaranteed. In 2008, one of the chapters in Strand's PhD thesis (see page ) covers CMBs and other related representations.
   Also this year, a book chapter (see pp. ) by Borgefors, Nyström and Sanniti di Baja on distance-based skeletonization in 2D and 3D was published in a book on medial representations in general.

2. Distance functions and distance transforms in discrete images
   Robin Strand, Gunilla Borgefors, Stina Svensson, Filip Malmberg
   Partners: Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Hungary; Nicolas Normand, IRCCyN, École Polytechnique de l´Université de Nantes, France
   Funding: S-faculty, SLU; Graduate School in Mathematics and Computing (FMB)
   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 (ns) allows the size of the neighborhood to vary along the paths. In Thesis 5 (pp. ), weighted ns-distances are defined in a general framework including, e.g., the standard square grid, the face-centered cubic grid, and the body-centered cubic grid. Optimal weights and neighborhood sequences, condition for metricity, and algorithms are presented.
   The weighted ns-distance has been evaluated by comparing it to the traditional weighted distance and distances based on neighborhood sequences. In a distance transform (DT), each picture element in an object is labeled with the distance to the closest element in the background. Thus the shape of the object is ``structured'' in a useful way. Only local operations are used, even if the results are global distances. DTs are very useful tools in many types of image analysis, from simple noise removal to advanced shape recognition. Since the distance defined by using both weights and a neighborhood sequence is defined by a minimal cost-path using only a neighborhood, it is computationally efficient -- also for the case with constrained distance. Moreover, since it uses both weights and neighborhood sequences, the rotational dependency is low.

3. Comparison of gray weighted distance measures
   Magnus Gedda
   Funding: TN-faculty, UU
   Period: 0601-
   Abstract: In several application projects we have discovered the benefit of computing distances weighted by the gray levels traversed, e.g., project 11. There are many ways of doing this, and in this project we have made a thorough comparison of the distances calculated with Gray Weighted Distance Transforms (GWDT) and the Weighted Distance Transforms On Curved Spaces (WDTOCS). In 2006, the work was presented at Discrete Geometry for Computer Imagery (DGCI2006) and published in the conference proceedings. We are currently doing a thorough examination of the performance of the underlying algorithms. See Fig. 2.

   Figure 2: Grey-weighted distance transform. (a) Input image with seed point (green cross) and constraints (red). (b) Weighted distance transform on curved space of input image (a). (c) Iso-distance surface in grey-weighted distance transform of abdominal contrast-enhanced MR angiography image.

   

4. Polar distance transform
   Kristin Norell, Robin Strand, Joakim Lindblad, Stina Svensson
   Partners: The Swedish Timber Measurement Council (VMR), Dept. of Forest Products and Markets, SLU
   Funding: The Swedish Timber Measurement Council (VMR); S-faculty, SLU; Graduate School in Mathematics and Computing (FMB)
   Period: 200702-
   Abstract: Distances and minumum cost paths between pixels can be measured using distance transforms. In this project we focus on images, where circular paths are preferred over straight lines. By introducing the polar distance transform (PDT) we avoid conversion of the image to polar coordinates and associated resampling problems.
   In the PDT each pixel is related to an origin in the image, which is an (approximate) centre of a circular pattern or shape. A path is made up from a sum of local steps, taken in a neighbourhood around each pixel. Different weights are used for steps in the radial and angular direction, respectively. By giving a high cost in the radial direction compared to the angular, the shortest path between two points on the same radius is a segment of a circle.
   A neighbourhood is used in the computation of a local step, both in the PDT and the GWPDT. This gives a hexadeconal (16-sided) pattern instead of the octogonal pattern that would be the case with the neighbourhood. To use the neighbourhood is new to the application of grey weighted distance transforms. Our method can be used also in other grey weighted distance transforms, not only the GWPDT.
   An article on the polar distance transform was published at the Swedish Society for Automated Image Analysis Symposium 2008, and a paper was published at the 19th International Conference on Pattern Recognition 2008 on computations of the PDT by the fast-marching method.
   Distance transforms can be used when computating mathematical morphology. Erosions and dilations are performed by thresholding the distance transform, provided that the distance transform is a metric. In an article published at the 19th International Conference on Pattern Recognition 2008 we showed that the PDT is a metric and used it for morphological operations. In Fig. 3, opening using the PDT is performed to separate circular segments on different radii. The opening removes disturbances between the circular segments (upper part of the image) and separates segments on different radii that are connected (lower part).

   Figure 3: Opening. The origin is in the centre of the image. pixels.

   [Original set]

   [Eroded set]

   [Opened set.]

5. Image processing and analysis of 3D images in the bcc and fcc grids
   Robin Strand, Gunilla Borgefors
   Partners: Christer Kiselman, Dept. of Mathematics, UU; Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary
   Funding: Graduate School in Mathematics and Computing (FMB)
   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 into 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. In the bcc grid, the voxels consist of truncated octahedra, and in the fcc grid, the voxels consist of rhombic dodecahedra. 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 prefered in the frequency domain, resulting in a bcc grid in spatial domain. In some cases, the densest packing is prefered in the spatial domain.
   In the thesis 5, results about acquiring, processing, representing, and visualizing images on point-lattices such as the fcc and bcc grids are presented. The main focus of the thesis is on distance functions and distance transforms defined on point-lattices.

6. Defuzzification of fuzzy segmented objects by feature invariance
   Joakim Lindblad
   Partners: Nataša Sladoje, Tibor Lukic, Faculty of Engineering, University of Novi Sad, Serbia
   Funding: S-faculty, SLU; TN-faculty, UU
   Period: 0301-
   Abstract: This project concerns the development of a method for feature based defuzzification of spatial fuzzy sets. The developed method Defuzzification by Feature Distance Minimization generates crisp shapes from fuzzy shapes by finding a crisp shape at a minimal distance to the fuzzy shape. We define the distance between two fuzzy sets as a distance between their feature-based representations in a chosen feature space. We have found it appropriate for defuzzification to incorporate both local and global features of the two sets. We have studied the use of membership values, gradient, area, perimeter, and centre of gravity in the distance measure. Several existing distance measures can be used to define the distance measure in the feature space. We have so far focused the research on Minkowski type distances measure.
   The optimization part of the defuzzification method was further developed during 2008. A method based on the Spectral Projected Gradient method in combination with concave regularization to solve the minimization problem imposed by defuzzification by feature distance minimization, was developed and evaluated. This work was presented at the DAGM conference in June 2008.

7. Spel coverage representations
   Joakim Lindblad
   Partners: Nataša Sladoje, Vladimir Curic, Faculty of Engineering, University of Novi Sad, Serbia
   Funding: S-faculty, SLU
   Period: 0801-
   Abstract: This project concerns exploration 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.
   During 2008, a method for precise boundary length estimation from a pixel coverage representation was developed. We have shown that the method provides error-free measurements of the length of straight boundary segments in the case of non-quantized pixel values. For quantized pixel values, optimal estimates are derived and we have proven that the estimate converges toward a correct value as the number of gray levels tends toward infinity. A description and evaluation of the method, together with a suggested approach for pixel coverage segmentation, is published in IEEE Transactions on Pattern Analysis and Machine Intelligence in February 2009.