Digital Topology

Contents

Topological classification

This work was done in collaboration with professor Gilles Bertrand (Image and Discrete Structures Team, ESIEE, France).

The objective is to classify all points of a 3D digital object according to their topological signification: surface points, curve points, junction points, etc [1]. See figure below for more details.

Different topological types

It comes out that this classification is possible by computing two numbers of connected components.

Different neighborhoods

The principle of the classification is to see what happens when an object point is deleted.

• For the object.
  For that purpose, we consider the 26-connected components of the object in a 26-neighborhood. If the central point belongs to the object, it is obvious that there is only one 26-connected component. When the central point is deleted, ie belongs to the background, we denote this number of 26-connected components by .
  • If is equal to 2, it means that the deletion of the point has cut the object into two parts, ie that locally the object is topologically equivalent to a curve.
  • If is greater than 2, it means that the deletion of the point has cut the object into more than two parts, ie that locally the object is topologically equivalent to a junction between curves.
• For the background.
  For that purpose, we consider the 6-connected components of the background 6-adjacent to the central point in a 18-neighborhood. If the central point belongs to the background (when it is deleted), it is obvious that there is only one such 6-connected component. When the central point is not deleted, ie belongs to the object, we denote this number of 6-connected components by .
  • If is equal to 2, it means that locally the background is divided into two parts, ie that locally the object is topologically equivalent to a surface.
  • If is greater than 2, it means that locally the background is divided into more than two parts, ie that locally the object is topologically equivalent to a junction between surfaces.

Topological classification according to the two numbers and .

Because of the space discretization, some junctions may be thick. This leads to some mis-classifications which can be recovered by using specific methods [1]. See the related publications for details.

Simple points

A side result of the above classification is a new characterisation of simple points in 3D [2]. A simple point is a point whose deletion (in a binary image) does not change the image's topology. Its characterization is very useful for any thinning algorithm. The new characterization is simply

= = 1

Topological numbers in grey valued images

In binary images, object's points are characterized by some non-zero value (typically 1 or 255), while background's points have a null value. Topological numbers in binary images depend on the number of connected components in small neighborhood around the point. Please note that those numbers does not depends on the value of the point itself.

Bertrand, Everat and Couprie have extended the notion of topological numbers to grey valued images [3]. It comes out that one have to define four topological numbers (instead of two).

The trick is to define a binary neighborhood from a grey valued neigborhood by thresholding with the central point's value (the point under examination).

• M is the central point, and I(M) it's value
• P is a neighbor of M, and I(P) it's value

1. Strict threshold
   • The foreground is defined by I(P) > I(M)
   • It comes that the background is defined by I(P) <= I(M)
   It yields the two numbers T++ (corresponding to either T26 or ) and T- (corresponding to either T06 or )
2. Large threshold
   • The foreground is defined by I(P) >= I(M)
   • It comes that the background is defined by I(P) < I(M)
   It yields the two numbers T+ (corresponding to either T26 or ) and T-- (corresponding to either T06 or )

Detailled tables

The number of configurations for each set of values can be found here. It comes out that there are 116 simple point's configurations in 2D (among 2⁸ possible neighborhoods) and 25985144 simple point's configurations in 3D (among 2²⁶ possible neighborhoods).

Skeletonization

Coming soon.

A short bibliography

[1]

G. Malandain, G. Bertrand and N. Ayache Topological segmentation of discrete surfaces. International Journal of Computer Vision, 1993, volume 10, number 2, pages 183-197.

[2]

G. Bertrand and G. Malandain. A New Characterization of three-dimensional Simple Points. Pattern Recognition Letters, February 1994, volume 2, number 15, pages 169-175.

[3]

G. Bertrand, J.-C. Everat and M. Couprie. Image segmentation through operators based upon topology. Journal of Electronic Imaging, 1997, volume 6, number 4, pages 395-405.

[4]

L. Robert, G. Malandain. Fast Binary Image Processing Using Binary Decision Diagrams. Computer Vision and Image Understanding, volume 72, number 1, October 1998, pages 1-9.

Links

• Image and Discrete Structures Team

[Home page] [Publications] [Epidaure team description] [Epidaure team home page] [Epidaure gallery]