**Distance Functions and Distance Transforms in Discrete Images**

Robin Strand, Gunilla Borgefors*Partners:*Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Hungary*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 that appeared in Discrete Applied Mathematics in 2009, 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. In another paper, written by Strand and Nagy, also published in 2009 in Discrete Applied Mathematics, the special-case of -dimensional generalizations of the fcc and bcc grids are considered. Strand and Nagy also published results on distance functions in the*diamond*grid in the June-issue of International Journal of Imaging Systems and Technology and at the International Workshop on Combinatorial Image Analysis.**Comparison of Grey-Weighted Distance Measures**

Magnus Gedda*Funding:*UU TN-faculty*Period:*0601-*Abstract:*In several application Projects we have discovered the benefit of computing distances weighted by the grey levels traversed, e.g., Project 12. 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. We are currently investigating the implementational details to form guidelines on which algorithms and datastructures are best suited for different scenarios.-
**Image Processing and Analysis of 3D Images in the Face- and Body-Centered Cubic Grids**

Robin Strand, Gunilla Borgefors

*Partners:*Benedek Nagy, Dept. of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary*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. 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 2009, the Project has focused on properties of sampling and interpolation on these non-Cartesian grids. Numerical experiments on sampling analytic functions have been performed, for example using the 3D Shepp-Logan Phantom in Figure 2. **Skeletonization in 3D Discrete Binary Images**

Robin Strand, Ingela Nyström, Gunilla Borgefors*Partner:*Gabriella Sanniti di Baja, Istituto di Cibernetica, CNR, Pozzuoli, Italy*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 2009, a special invited paper,*On Maximal Balls in Three Volume Grids*written by Borgefors and Strand, was presented at the conference Pattern Recognition and Information Processing, Minsk, Belarus.-
**Spel Coverage Representations**

Joakim Lindblad, Vladimir Curic*Partners:*Nataša Sladoje, Faculty of Engineering, University of Novi Sad, Serbia; 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.A method for precise boundary length estimation from a pixel coverage representation has been developed. Description and evaluation of the method, together with a suggested approach for pixel coverage segmentation based on a double thresholding scheme, is published in IEEE Transactions on Pattern Analysis and Machine Intelligence in February 2009. A coverage segmentation method based on a local statistical model was developed and presented at the International Conference on Image Analysis and Processing (ICIAP) in Sept. 2009. Application of the developed framework, i.e., the combination of coverage segmentation and subsequent high precision feature extraction, was successfully demonstrated on histological images of bone implants. Benefits of precise feature estimation from a fuzzy representation are further confirmed when a method for registration of digital X-ray images of hip implants is improved by utilizing geometric moments of a fuzzy representation. This work was presented at the Scandinavian Conference on Image Analysis (SCIA) in June 2009.

**Set Distances and Their Application in Image Analysis**

Vladimir Curic, Joakim Lindblad, Gunilla Borgefors*Partners:*Nataša Sladoje, Faculty of Engineering, University of Novi Sad, Serbia*Funding:*Graduate School in Mathematics and Computing (FMB)*Period:*0908-*Abstract:*Methods for measuring distances between sets 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 possibly develop new set distances which are useful in image registration problems. We have proposed variations on Sum of Minimal Distances as well as Complement set distances, and are currently exploring, and evaluating their appropriateness for image registration. Of particular interest are properties of monotonicity and continuity.

During 2009 we worked on the application of set distances for registration of 2D binary shapes. See Figure 3. The work was presented at the International Symposium on Image and Signal Processing and Analysis (ISPA2009).

We intend to further extend this work within the framework of mathematical morphology towards more general methods for shape description and analysis.

**Dimensionality-Independent Path Openings**

Cris Luengo*Funding:*S-faculty, SLU*Period:*0904-0907*Abstract:*Path openings and closings are morphological operations with flexible line segments as structuring elements. These line segments have the ability to adapt to local image structures, and can be used to detect lines that are not perfectly straight. They also are a convenient and efficient alternative to straight line segments as structuring elements when the exact orientation of lines in the image is not known. These path operations are defined by an adjacency relation, which typically allows for lines that are approximately horizontal, vertical or diagonal. However, because this definition allows zig-zag lines, diagonal paths can be much shorter than the corresponding horizontal or vertical paths. This undoubtedly causes problems when attempting to use path operations for length measurements.We have extended the definition of path openings and closings to make them dimensionality-independent. This allows us to apply this operation to the 3D images used in many applications at CBA. We have also proposed a way to constrain the path operations to improve their ability to perform length measurements. Both techniques are described in a paper that has been accepted for publication in IEEE Transactions on Image Processing.