**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).**Comparison of Grey-Weighted Distance Measures**

Magnus Gedda*Funding:*TN-faculty, UU*Period:*0601-1005*Abstract:*In several application projects we have discovered the benefit of computing distances weighted by the grey levels traversed, e.g., Project . There are many ways of doing this, and in this project we have made a thorough comparison of the most popular distances calculated that take grey-level information into account; GRAYMAT, Distance On Curved Spaces (DOCS) and the Weighted Distance On Curved Spaces (WDOCS). Already in 2006 we published a theoretical comparison describing the different aspects of the definitions.**Distance Functions and Distance Transforms in Discrete Images**

Robin Strand, Gunilla Borgefors*Partner:*Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Hungary*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 (ns) allows the size of the neighborhood to vary along the paths. In a paper by Strand and Nagy that was presented at the Workshop on Applications of Discrete Geometry and Mathematical Morphology, weighted ns-distances are defined on the honeycomb grid, in which each voxel is a hexagonal prism.**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 2010, a paper by Strand on CMBs and some related concepts was accepted for the discrete geometry for computer imagery (DGCI) conference that will be held in Nancy in 2011.-
**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 some cases, the densest packing is preferred in the spatial domain.In 2010, results on sampling properties of the honeycomb point-lattice and the diamond grid were presented at International Conference on Pattern Recognition, Istanbul, Turkey. In Fig. , the ideal interpolation function on the honeycomb lattice is illustrated.

**Figure:**An isosurface of the ideal interpolation function on the honeycomb lattice is shown together with the Voronoi region of a grid point. -
**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-*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.This theoretically founded project has strong ties with applications. Under 2010, results and knowledge from this project found use in Project where it provided a good object representation for registration and matching tasks, as well as in the project ``Estimation of Linear Shape Deformations and its Medical Applications'' at the University of Szeged, Hungary, where coverage information is utilized for improved estimation of affine deformations of 3D objects. The latter work was presented at the International Conference on Image Processing (ICIP) in September 2010.

In addition, further development of the theoretical framework related to coverage representations was undertaken during 2010. In close collaboration with Project a framework for graph based coverage segmentations was developed. This work is presented in an article in Theoretical Computer Science, appearing in 2011.

**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. An initial goal of this project is to evaluate existing and develop new set distances which are useful in image registration related problems. Of particular interest are properties of monotonicity and continuity.During 2010 we proposed new set distances between crisp sets of points and evaluated their usefulness for rigid body registration of binary images as well as their 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. We extended proposed set distances for crisp sets to distances 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 (see Fig. ). This work is accepted to International Workshop on Combinatorial Image Analysis (IWCIA'2011).

We intend to further extend this work within the framework of mathematical morphology towards more general methods for shape description and analysis. In addition, for the proposed set distances, we intend to perform a distance based classification of biomedical data.

**Figure:**A: Continuous crisp disk, B: Crisp discrete representation of a continuous disk (obtained by Gauss centre point digitization), C: Fuzzy discrete representation of a continuous disk (obtained by coverage digitization), D: Continuous crisp octagon, E: Crisp discrete representation of a continuous octagon, F: Fuzzy discrete representation of a continuous octagon.A B C D E F