- 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.
Figure 2:
A three-dimensional version of the Shepp Logan phantom.
|
|
- 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.
Figure 3:
Examples of test shapes.
|
|
- 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.
