ThinGreyScale is a QGIS plugin. The plugin can be found in the Raster menu and in the Raster toolbar with the name Thin greyscale image to skeleton.
Performs thinning of a greyscale image using a slightly modified version of an algorithm presented by Biagioni and Eriksson [1].
Based on a set of levels, specified by the user, the image is thinned to a skeleton by first thinning the set of pixels that have values higher than or equal to the highest level. Then the next highest level is considered. Here all pixels that have values in the two highest levels are considered, but the thinning is constrained by the skeleton from the highest level. This continues until the lowest level is reached.
The result is a skeleton raster with skeleton pixels that have values corresonding to the level at which they were found. The skeleton raster is saved as GeoTIFF, either at a location specified by the user or in the user’s tempdir (files are not deleted automatically).
It is assumed that the higher the pixel values is, the more “important” is the pixel.
The greyscale skeleton can be vectorised with GRASS r.to.vect by first binarising it (choosing an appropriate threshold), and then thinning it using GRASS r.thin to get a skeleton that is compatible with r.to.vect.
The algorithm was proposed by Biagioni and Eriksson [1], using the notation of Zhang and Suen [2]. We had to slightly modify the original algorithm due to some problems with its behaviour.
The input to the algorithm is a greyscale image and a set of levels, ordered on increasing value. At each level, the thinning is performed on a combination of the skeleton from the higher level and a binary image containing 1’s for all pixels that have values larger then the current level:
Si = Thin(Si+1 + Ti)
Si is the skeleton image for level i, while Ti is the threshold image for level i.
At each level the Thin algorithm runs as follows:
# Skeletonize
# Zhang & Suen 1984: Parallel processing - each pixel
# is considered based on the values from the previous
# step
# Notation and explanations:
#
# Naming of the neighbouring pixels:
# P9 P2 P3
# P8 P1 P4
# P7 P6 P5
#
# B(P1): number of non-zero neighbours of P1
# A(P1): number of (0,>=1) pairs in the ordered set
# P2,P3,...,P9,P2 (avoids removing "nodes"?)
# Step 1:
Repeat until convergence:
# Substep 1:
for all pixels:
set P1 = 0 if all of the following conditions hold:
B(P1) >= 2; # pixels with one or two non-zero neigbours will not be affected
B(P1) <= 6; # pixels with seven or eight non-zero neighbours will not be affected
A(P1) = 1; # "nodes" (where more than two "lines" meet) will not be removed
# P2 x P4 x P6 != 1; # paper original, but does not work
# P4 x P6 x P8 != 1; # paper original, but does not work
P2 x P4 x P6 = 0;
P4 x P6 x P8 = 0;
# Substep 2:
for all pixels:
set P1 = 0 if all of the following conditions hold:
B(P1) >= 2;
B(P1) <= 6;
A(P1) = 1;
# P2 x P4 x P8 != 1; # paper original - does not work
# P2 x P6 x P8 != 1; # paper original - does not work
P2 x P4 x P8 = 0;
P2 x P6 x P8 = 0;
# Step 2:
# deletes completely contained pixels (and some cul-de-sac pixels)
# Could break bridges (if the illustrated situation occurs):
# ******
# **
# ******
for all pixels:
set P1 = 0 if the following condition holds:
B>=7)
The result is not a pure skeleton, as there are some pixels that have more than two 9-neighbours even if they are not “nodes”. The following situation may result (because of the A(P1)=1 condition):
##
####
[1] Biagioni and Eriksson: Map Inference in the Face of Noise and Disparity. SIGSPATIAL GIS, pages 79-88. ACM, 2012.
[2] Zhang & Suen 1984: A fast parallel algorithm for thinning digital patterns. Communications of the ACM, volume 27, issue 3, pages 236-239. ACM, 1984.