Thinning is a morphological operation used to remove foreground pixels from binary images. It can be used to to tidy up the output of edge detectors by reducing all lines to single pixel thickness. It works on arbitrary shaped regions too. It erodes away the boundaries of foreground obejects while preserving the extreme ends of lines. Thinning is the dual of Thickening.
The operation uses the extended trinary valued structuring element and can
be expressed in terms of the hit-and-miss transform. The thinning of an image I
by a structuring element J is:
thin(I,J)=I-hit_and_miss(I,J)
where subtraction is defined as X-Y=X&!Y (X and NOT y).
If the foreground and background pixels in the structuring element exactly match foreground and background pixels in the image, then the image pixel result at the origin of the structuring element is set to background; otherwise it is left unchanged. In some cases the operation is applied repeatedly until there is no further change. In other cases it is applied a specified number of times (in which case it is commonly called pruning).
One of the commonest uses of thinning is to reduce the thresholded output of an edge detector to lines of a single pixel thickness, while preserving the full length of those lines (i.e. pixels at the extrem ends of lines should not be changed). A simple algorithm for doing this is:
Consider all pixels on the boundaries of foreground regions (i.e. foreground pixels having at least onebackgroundneighbor). Delete (i.e. set to background) any such pixel that has more than one foreground neighbor, as long as doing so does not disconnect (i.e. split into two) the region containing the pixel. Iterate until convergence.
This effect can be achieved using morphological thinning by iterating until convergence with the two structuring elements below, and all their 90 degree rotations (2*4=8 cases).
|
|
A more general and faster algorithm is to encode the 9 bits of the image under the structuring element into a number in the range 0..511 and use this as an index into a table to get the resulting pixel value. This gives all 8 cases at once.
0000000000000000 0000000000000000 0110000000000000 0001000100000000 0011111111000000 0011111111110000 0011111111111000 0011111111111100 0011100001111100 0011000000111100 0011000000011100 0010000000001100 0010000000001100 0010000000000100 0001110000000000 0000000000000000Before |
0000000000000000 0000000000000000 0110000000000000 0001000000000000 0001000000000000 0001000110000000 0001111001000000 0001000000100000 0001000000010000 0001000000001000 0010000000001000 0010000000001000 0010000000000100 0010000000000100 0001110000000000 0000000000000000After |
Skeletons produced by this method often contain undesirable short spurs resulting from small irregularities in the boundaries if the original object. These spurs can be removed by a process called pruning, which is just another sort of thinning with different structuring elements. They are the four rotations of the following, iterated until no change:
|
|
In the real world yet more complex algorithms are frequently required.