Applications of topology

Fundamental definitions

The methodology used stems from the fields of algebraic topology and mathematical morphology [9][8], especially from the theory of homotopy. The latter deals mostly with paths, their properties as well as the possibility to find topologically equivalent classes of paths. In the simplest case, this leads to the genus or the connectivity number which is in digital images an important property. It will be shown, that the connectivity number is a side product of the transformations and operations described. In Fig.1 an object is sketched with two topological not equivalent paths. This is directly related to a class of objects with holes, here with a genus of 0. The genus is defined as the number of holes minus the number of voids.

In the following we will not fulfill all requirements of mathematical rigorousness. Otherwise this would lead us beyond the scope of this article.

Def. 1

Given a two-dimensional digital image with pixels , the columns, the rows and the range of grey values

Def. 2

Two pixels and are called (8-)neighbored or (4-)neighbored pixels, respectively, if or , respectively.

Def. 3

A path is a sequence of neighbored pixels with a start pixel and an end pixel . A set of pixels, where each pair of pixels is linked by a path completely contained in the set is a (path-)connected set.

Def. 4

A path is called monotone increasing or decreasing path, respectively, if the sequence of neighbored pixels from to is monotone increasing or decreasing in terms of the grey values. This path is directed. A monotone increasing path from to is a monotone decreasing path from to . It can be shown that this definition is an equivalence relation with a partition of the pixels into equivalence classes, the path connected components. In Fig.2 the literal understanding of paths is shown. Additionally possible borders of path connected components are sketched into.

Def. 5

A local maximum (LMX) or minimum (LMN), respectively, is a connected set of pixels with constant maximum or minimum grey value in a certain surrounding.

Def. 6

Every local maximum or minimum, respectively, is related to one upper or lower (path-)connected component UCC or LCC. A connected component is a monotone increasing or decreasing path-connected set of pixels. We do not proof here that each set of connected components is a partition of the image. In Fig.3 a one-dimensional interpretation of these items is illustrated.

Def. 7

From upper connected components a (UCC-)neighborhood relationship can be defined

The local maxima inherit the UCC-neighborhood canonically by and . The LCC-neighborhood can be defined accordingly.

The combination of upper and lower connected components delivers a mixed neighborhood relation between both types of components in the following way: Let be an upper connected component and the set of lower connected components with non-empty intersection with , than

defines a neighborhood between connected components as well as local maxima and (surrounding) local minima and vice versa (see Fig.4).

Def. 8

From the existence of monotone decreasing paths leading from one LMX to a neighbored LMN we can conclude the existence of exactly one point just on half height of the grey value range fom LMN to LMX. This is valid for every existing path, hence we can define all pixels in the upper half height of a path as the upper half height set UHH and the others as lower half height set LHH. This is illustrated in one dimension on the left of Fig.3. The calculation of the UHH and LHH is described with the results of the ricefield transformation in the next section. This partition is independent from absolute grey values and only dependent from the neighborhood of the local maxima and minima.

Image objects and their relations

Using terms as defined in the preceeding section, images can now be understood as sets of objects of the different types like UCC, LCC, LMX or LMN equipped with their neighborhoods. Depending from the actual application these merely mathematically defined terms have to be related to the actual meaning. The simplest example is an image representing a certain height map with the height coded as grey value. The UCC's represent the regions of single mountains limited by the path of lowest locations in the surrounding valleys and LCC's are the regions of the valleys surrounded by the watersheds and crest lines. LMX's represent the summits or peaks and the LMN's the holes.

Of special interest for picture evaluation are relations between objects. They allow the modelling of image content by relations of image objects. These relations can widely differ from local oriented neighborhoods up to those based on the grey value of the objects [6]. Relations are strongly related to the theory of graphs (see Fig.4).

As a first step for further description and structuring of an image the relations defined as neighborhoods in the preceeding section are needed. The relations represented as a graph can be examined and transformed with various methods. Again mathematical morphology is useful in this context [7][12][6].

Structuring and quantification of image objects

Image analysis considered as a hierachical description process delivers at every hierachical level quantitative features of increasing degree of abstraction. This procedure necessitates formal models. The methods described up to now are applicable to every hierachical level, however formulated for the objects of lowest level, the pixels.

Beside several pixel based quantitative features of the connected components like size or mean, their overall number can be used for calculation of a connectivity number. Comparable with the well known Euler number of sets, connectivity of the grey scale image can be defined as .

As far as relations between objects exist well-known methods of graph analysis can be used for further analysis, see [2][14]. At every level, new features can be defined on the base of all other lower-level features

Beside the topological tools described here, other methods, e.g. computational geometry, see [10], to define relations between objects can be used like the well-known Delaunay triangulation or heuristical methods [6]. E.g. the mixed neighborhood between local extrema can be understood as a star graph allowing various algorithmic methods to generate paths between objects or other groups of objects [2]. Defined graphs can either be merged or devided to define new objects with special properties.

Summary of topological applications

An image consists of pixels. Pixels are gathered in different connected components. The latter contain local extrema. Neighborhood relations allow the definition of entities like paths and connected components. New topologies are defined above objects for further more elaborated analysis of the image content on the level of newly defined objects.