Department of Information Technology

Discrete Geometry

Images consist of a number of separate points (pixels). Standard geometrical concepts, such as distance and lines must thus be defined discretely. We create and develop such basic definitions. Pixels in two or three dimensions are usually square or cubic, respectively. Theoretically we can prove that there are better shapes and we develop methods for using them.

Image data is inherently discrete since it consists of a finite number of pixels and each pixel has a single intensity or colour value. Therefore, it is very natural to consider a discrete geometry instead of a continuous geometry in image processing. Using the discrete geometry approach, we are developing low-level image processing methods and theory on, for example,

  • Distance functions and transforms - Efficient algorithms for computing the distance between pixels can be obtained by using the discrete geometry framework. Also, the so-obtained distance transforms (where each object pixel is assigned the distance to the closest background pixel) has many good properties. The distance functions and distance transforms methods we develop are often used in applied image processing projects.
  • Skeletonisation - Skeletonisation is a way to reduce dimensionality of digital objects. A skeleton of an object should ideally be topologically correct, centred within the object, thin, and fully reversible. The skeleton is an efficient representation when processing images of thin, elongated structures such as paper fibres and blood vessels.
  • Fuzzy methods - In fuzzy set theory, each element has a degree of membership instead of belonging to only one set. This gives a tool for handling imperfections in images such as noise and artefacts from image acquisition. We use fuzzy methods for, e.g., accurate and precise reconstruction of digitized objects.
  • Alternative image representations - The most commonly used grids for representing images in two and three dimensions are the square and cubic grids. However, it has been demonstrated in many ways that alternative grids are theoretically better than these grids. We develop tools for image processing on alternative, mainly three dimensional, grids.
  • Graph based methods - A field that is closely related to discrete geometry is graph based image processing. A graph in this context is an abstract representation of an image where the pixels are represented by vertices. The graph representation is well suited for interactive image processing methods and we develop, e.g., interactive segmentation methods for medical applications using this approach.
Updated  2015-06-04 16:46:18 by Anneli Folkesson.