An introduction to thinning and visual aspect preservation

Thinning consists of deleting some points from an object while preserving its topology. In other words, thinning allows to reduce the amount of information in a shape while preserving some of its characteristics (such as the number of pieces, cavities, tunnels, ...). A skeleton is a result of a thinning process that:

• is homotopy equivalent to the original object. In the voxel framework, this is achieved by removing simple points (or simple sets) from the object.
• is centered in the object. This can be done either by using a priority function based on a distance map for points removal, or by removing in parallel layers of simple points.
• is thin (the skeleton has one dimension less than the space where it is embedded in). In the voxel framework, thinness is more difficult to achieve as there is no "universally accepted" definition of thinness (although a consensus exists in 2d, there is none in 3d).
• In addition, in some applications, the skeleton should also contain geometrical information about the object it was computed from (the skeleton should "look like" the original object).

(Click on image to zoom) Two skeletons of a same shape. The skeleton on the left contains all the topological information about the shape, but little geometrical information. The skeleton on the right contains topological and geometrical information about the shape, and gives more information on the original object.
Two skeletons of a same shape. The skeleton on the left contains all the topological information about the shape, but little geometrical information. The skeleton on the right contains topological and geometrical information about the shape, and gives more information on the original object.

Two strategies exist in order to obtain a skeleton "visually close" to the original shape, and both are based on selecting points which should not be removed during thinning:

• a first strategy consists of selecting, before thinning, some points which should not be removed from the object. This is usually achieved by computing a map which assigns to each point of the object a numerical value and perform a threshold of the map. The drawback of this method is that the user needs to give some input to the program (non user-free method).
• another strategy consists of selecting, during thinning, points which should not not be removed, based on their neighborhood's configuration. These methods are usually user-free, but their main drawback is their sensitivity to noise: it is usually necessary to add a pruning step after thinning in order to remove spurious elements from the skeleton (the pruning is a non user-free step).
• (Click on image to zoom)Two skeletons of a same shape. On the left, the skeleton contains spurious elements: this noise makes it difficult to extract information from the skeleton. On the right, the skeleton contains less noise: information extraction will be more easy to perform.
Two skeletons of a same shape. On the left, the skeleton contains spurious elements: this noise makes it difficult to extract information from the skeleton. On the right, the skeleton contains less noise: information extraction will be more easy to perform.

In conclusion, we can say that if one does not want to give any parameter (any clue on the shape) to the thinning algorithm, he or she will obtain a skeleton with spurious elements. Moreover, it is difficult to prove that a thinning algorithm produces a thin result in the voxel framework.

The lambda-medial axis

The lambda-medial axis was originally proposed in the continuous framework by Chazal & Lieutier, who proved its stability to noise and rotation.

The Euclidean medial axis consists of mapping to each point x of an object the radius of the maximal ball centered on x (the point is given the value 0 if it is not a center of maximal ball). The lambda-medial axis consists of mapping to each point x of an object the radius of the smallest point containing E(x), where E(x) is the set of points of the complementary of the object which are the closest to x.

(Click on image to zoom) The radius r is the radius of the maximal ball (in green) centered on m. The points a, b and c are the elements of E(m). In blue, the smallest ball containing E(m). The value of the lambda-medial axis on m is r'.
In red, a point m of a shape. When considering the Euclidean medial axis, the value associated to m is r, the radius of the maximal ball centered on m (yellow). We consider E(m)={a, b, c}, the set of points of the complementary of the object which are the closest to m. When considering the lambda-medial axis, the value associated to m is r', the radius of the smallest ball containing E(m) (in blue).

We adapted, in [ChauCouTa2010], the lambda-medial axis to the discrete framework and studied how it could be used in order to obtain a skeleton "looking like" the original object (more details on thinning were given in [Chaussard_phd]). We also proposed a method for comparing medial axes, and compared the lambda-medial axis with the well-known Euclidean medial axis and with the integer-medial axis (Hesselink & Roerdink). We showed that the lambda-medial axis is more stable to noise and to rotation.

(Click on image to zoom) A skeleton of a shape, computed using a threshold of the lambda-medial axis as inhibitor set (set of points which should be preserved during thinning).
On the left, a shape, and on the right, a skeleton of the shape computed using a threshold of the lambda-medial axis as inhibitor set (set of points which should be preserved during thinning).

The lambda-medial axis is therefore a very good tool for choosing a set of points to preserve during thinning. The source code of this program should be soon available for download on this web site.

The cubical complexes framework

In the cubical complexes framework, a discrete object is not made of voxels, but of cubes, squares, edges and vertices. In this framework, topology is well defined on the whole space, definitions are generally valid in every dimensions and strong links with the continuous framework were established. Practically speaking, using cubical complexes allows to solve easily some hard problems of the voxel framework, such as parallel thinning, decomposition of a skeleton into simple elements, or giving a definition of thinness in every dimension.

We proposed a parallel thinning algorithm [ChauCou2009] in the cubical complexes, and we proved that this algorithm produces thin results. In order to obtain thin skeletons "looking like" the original input, we gave a general scheme for using this algorithm with any medial axis defined in the voxel framework.

We also proposed [Chaussard_phd] in this framework a new user-free thinning (no need of any input from the user) for obtaining skeletons "looking like" the original input and containing very little spurious elements. We compared this method with other user-free thinning algorithms (in the voxel framework), and we showed that our method has, in average, the best visual results and the best stability to noise and rotation. Moreover, we proved that the results of this algorithm are thin.

(Click to play video) Two skeletons of a same shape, computed using our thinning algorithm.
On the left, the original shape, called "Neptune". In the middle, the skeleton of Neptune computed using our algorithm. On the right, the curvilinear skeleton of Neptune computed using our algorithm. Each skeleton is decomposed into elements (surfaces and curves). In both cases, no user input was necessary to compute the skeleton (user-free method).

Thanks to this framework, it is very easy to decompose a skeleton into curves and surfaces. We are currently working on propagation of the skeleton's labels into the original volume: after a skeleton has been decomposed and all its parts have been labeled, we can propagate these labels inside the original object in order to label all its points and obtain a decomposition of the volume. The source code of this program should be soon available for download on this web site.

(Click on image to zoom) Decomposition of an image of polypropylene foam (image acquired by Dominique Bernard, ICMCB).
On the left, a slice from the original data. On the right, a slice of the segmented object. On the right, the decomposition of the segmented object into basic surfaces (based on our thinning method).
(Click on image to zoom) Decomposition of a 3d shape (Neptune).
Results of our decomposition technique on a 3d shape (Neptune). The blue lines represent the frontier between different elements.
Toric spaces and fluid flow simulation

This work was done during the first year of my thesis, and is part of another research theme: there are little connections with the work previously explained. This work is published in [ChauBerCou2010].

When one simulates a fluid flow through the pore space of a material, he or she will realize that the paths followed by the fluid looks like the skeleton of the pore space of the material. The goal of this work was to study how the skeleton of the pore space of a material be used in order to speed up fluid flow simulation calculation.

Our initial idea was to obtain a curvilinear skeleton that could then be easily transformed into a graph where the fluid flow could then be simulated using a max flow algorithm (Ford and Fulkerson, Tarjan and Goldberg, ...). In order to avoid surface patches in the skeleton, it is necessary to remove the grains of the material (pieces of the material which are not connected with the borders of the image). However, the material is considered to be embedded in a toric space: if some fluid leaves the material by one side, it will come back inside the material by the opposite side. In this situation, all the parts of the material which do not wrap around the toric space will also create surface patches in the skeleton: we call these toric grains.

Unlike classical grains, toric grains cannot be characterized in terms of image border. However, we found out a interesting characterization based on topology: an element of the material is not a toric grain iff it contains a loop which cannot be reduced (by continuous deformation) to a single point. We proposed a new definition of loops and continuous deformation adapted to the toric space, and we found an easy way to characterize such loops. Finally, we proposed a linear time algorithm allowing to detect toric grains in an object.

(Click on image to zoom) Detecting and removing toric grains allows to remove, in some cases, surfaces from the skeleton of the pore space.
The skeleton of the pore space of a sample of material is computed. On the left, the skeleton contains a surface (see the red frame). On the right, after removing toric grains, the skeleton does not contain any surface part.