Thinning

Common Names: Thinning

Brief Description

Thinning is a morphological operation that is used to remove selected foreground pixels from binary images, somewhat like erosion or opening. It can be used for several applications, but is particularly useful for skeletonization. In this mode it is commonly used to tidy up the output of edge detectors by reducing all lines to single pixel thickness. Thinning is normally only applied to binary images, and produces another binary image as output.
The thinning operation is related to the hit-and-miss transform, and so it is helpful to have an understanding of that operator before reading on.

How It Works

Like other morphological operators, the behaviour of the thinning operation is determined by a structuring element. The binary structuring elements used for thinning are of the extended type described under the hit-and-miss transform (i.e. they can contain both ones and zeros).
The thinning operation is related to the hit-and-miss transform and can be expressed quite simply in terms of it. The thinning of an image I by a structuring element J is:

where the subtraction is a logical subtraction defined by

.
In everyday terms, the thinning operation is calculated by translating the origin of the structuring element to each possible pixel position in the image, and at each such position comparing it with the underlying image pixels. If the foreground and background pixels in the structuring element exactly match foreground and background pixels in the image, then the image pixel underneath the origin of the structuring element is set to background (zero). Otherwise it is left unchanged. Note that the structuring element must always have a one or a blank at its origin if it is to have any effect.
The choice of structuring element determines under what situations a foreground pixel will be set to background, and hence it determines the application for the thinning operation.
We have described the effects of a single pass of a thinning operation over the image. In fact, the operator is normally applied repeatedly until it causes no further changes to the image (i.e. until convergence). Alternatively, in some applications, e.g. pruning, the operations may only be applied for a limited number of iterations.
Thinning is the dual of thickening, i.e. thickening the foreground is equivalent to thinning the background.

Guidelines for Use

One of the most common uses of thinning is to reduce the thresholded output of an edge detector such as the Sobel operator, to lines of a single pixel thickness, while preserving the full length of those lines (i.e. pixels at the extreme ends of lines should not be affected). A simple algorithm for doing this is the following:

Consider all pixels on the boundaries of foreground regions (i.e. foreground points that have at least one background neighbour). Delete any such point that has more than one foreground neighbour, as long as doing so does not locally disconnect (i.e. split into two) the region containing that pixel. Iterate until convergence.

This procedure erodes away the boundaries of foreground objects as much as possible, but does not affect pixels at the ends of lines.
This effect can be achieved using morphological thinning by iterating until convergence with the structuring elements shown in Figure 1, and all their 90° rotations (4×2 = 8 structuring elements in total).
In fact what we are doing here is determining the octagonal skeleton of a binary shape --- the set of points that lie at the centers of octagons that fit entirely inside the shape, and which touch the boundary of the shape at at least two points. See the section on skeletonization for more details on skeletons and on other ways of computing it. Note that this skeletonization method is guaranteed to produce a connected skeleton.

Figure 1 Structuring elements for skeletonization by morphological thinning. At each iteration, the image is first thinned by the left hand structuring element, and then by the right hand one, and then with the remaining six 90° rotations of the two elements. The process is repeated in cyclic fashion until none of the thinnings produces any further change. As usual, the origin of the structuring element is at the center.

Figure 2 shows the result of this thinning operation on a simple binary image.

Figure 2 Example skeletonization by morphological thinning of a simple binary shape, using the above structuring elements. Note that the resulting skeleton is connected.

Note that skeletons produced by this method often contain undesirable short spurs produced by small irregularities in the boundary of the original object. These spurs can be removed by a process called pruning, which is in fact just another sort of thinning. The structuring element for this operation is shown in Figure 3, along with some other common structuring elements.

Figure 3 Some applications of thinning. 1 simply finds the boundary of a binary object, i.e. it deletes any foreground points that don't have at least one neighbouring background point. Note that the detected boundary is 4-connected. 2 does the same thing but produces an 8-connected boundary. 3a and 3b are used for pruning. At each thinning iteration, each element must be used in each of its four 90° rotations. Pruning is normally carried out for only a limited number of iterations to remove short spurs, since pruning until convergence will actually remove all pixels except those that form closed loops.

Note that many implementations of thinning have a particular structuring element `hardwired' into them (usually the skeletonization structuring elements), and so the user does not need to be concerned about selecting one.

is the result of applying the Sobel operator to

. Note that the detected boundaries of the object are several pixels thick.
We first threshold the image at a greylevel value of 60 producing

in order to obtain a binary image.
Then, iterating the thinning algorithm until convergence, we get

. The detected lines have all been reduced to a single pixel width. Note however that there are still one or two `spurs' present, which can be removed using pruning.

is the result of pruning (using thinning) for five iterations. The spurs are now almost entirely gone.
Thinning is often used in combination with other morphological operators for extracting a simple representation of regions. A common example is the automated recognition of hand-written characters. In this case, morphological operators are used as pre-processing to obtain the shape of the characters which then can be used for the recognition. We illustrate a simple example using

, which shows a Japanese character. Note that this and the following images were zoomed by a factor of 4 for a better display. Hence, a 4×4 pixel square here corresponds to 1 pixel during the processing. Since we want to work on binary images, we start off by thresholding the image at a value of 180, obtaining

. A simple way to obtain the skeleton of the character is to thin the image with the masks shown in Figure 4 until convergence. The result is shown in

.
The character is now reduced to a single pixel wide line. However, the line is broken at some locations, which might cause problems during the recognition process. To improve the situation we can first dilate the image to connect the lines before thinning it. Dilating the image twice with a 3×3 square mask yields

, then the result of the thinning is

. The corresponding images for three dilations are

and

. Although the line is now connected the process also had negative effects on the skeleton: we obtain spurs on the end points of the lines and the skeleton changes its shape at high curvature locations. Therefore, we try to prune the spurs by thinning the image using the masks shown in Figure 4.

Figure 4 Shows the masks used in the character recognition example. 1 shows the mask used in combination with thinning to obtain the skeleton. 2 was used in combination with thinning to prune the skeleton and with the hit-and-miss operator to find the end points of the skeleton. Each mask was used in each of its 45° rotations.

Pruning the thinned image which was obtained after 2 dilations yields

using two iterations for each orientation of the mask. For the example obtained after 3 dilations we get

using 4 iterations of pruning. The spurs have now disappeared, however, the pruning has also suppressed pixels at the end of correct lines. If we want to restore these parts of the image, we can combine the dilation operator with a logical AND operator. First, we need to know the end points of the skeleton so that we know where to start the dilation. We find these by applying a hit-and-miss operator using the mask shown in Figure 4. The end points of the latter of the two pruned images are shown in

. Now, we dilate this image using a 3×3 mask. ANDing it with the thinned, but not pruned image prevents the dilation from spreading out in all direction, hence it limits the dilation along the original character. This process is known as conditional dilation. After repeating this procedure 5 times, we obtain

. Although one of the parasitic branches disappeared, the ones appearing close to the end of the lines remain.
Our final step is to OR this image with the pruning output thus obtaining

. This simple example illustrates that we can successfully apply a variety of morphological operators to obtain information about the shape of a character. However, in a real world application, more sophisticated algorithms and masks would be necessary to get good results.
Thinning more complicated images often produces less spectacular results.
For instance

is the output from the Sobel operator applied to

is the same image thresholded at a greylevel value of 200.
And

is the effect of skeletonization by thinning. The result is a lot less clear than before. Compare this with the results obtained using the Canny operator.

Exercises

What is the difference of a thinned line obtained from the slightly different skeleton masks in Figure 1 and Figure 4 ?
The conditional dilation in the character recognition example `followed' the original character not only towards the initial end of the line but also backwards. Hence it also might restore unwanted spurs which were located in this direction. Can you think of a way to avoid that using a second condition?
Can you think of any situation in the character recognition example, in which the pruning mask shown in Figure 4 might cause problems ?
Find the boundaries of using morphological edge detection. First threshold the image, then apply thinning using the mask shown in Figure 3. Compare the result with which was obtain using the Sobel operator and morphological post-processing (see above).
Compare and contrast the effect of the Canny operator with the combined effect of Sobel operator plus thinning and pruning.
If an edge detector has produced long lines in its output that are approximately x pixels thick, what is the longest length spurious spur (prune) that you could expect to see after thinning to a single pixel thickness? Test your estimate out on some real images.
Hence, approximately how many iterations of pruning should be applied to remove spurious spurs from lines that were thinned down from a thickness of x pixels?

References

R. Gonzalez and R. Woods Digital Image Processing, Addison-Wesley Publishing Company, 1992, pp 518 - 548.
E. Davies Machine Vision: Theory, Algorithms and Practicalities Academic Press, 1990, pp 149 - 161.
R. Haralick and L. Shapiro Computer and Robot Vision, Vol 1, Addison-Wesley Publishing Company, 1992, Chap 5, pp 168-173.
A. Jain Fundamentals of Digital Image Processing, Prentice-Hall, 1989, Chap 9.
D. Vernon Machine Vision, Prentice-Hall, 1991, Chap 4.

Removal of Thin Connectors Using Morphological Operations:

One way to deal with the potential misclassification is to separate thin connections between similar structures, then use connectivity to isolate major structures with similar responses.
Background on Mathematical Morphology
Image morphology provides a way to incorporate neighborhood and distance information into algorithms (see [Serra 1982.] [Haralick, Sternberg and Zhuang 1987.] for detailed treatment of morphological operators). The basic idea in mathematical morphology is to convolve an image with a given mask (known as the structuring element), and to binarize the result of the convolution using a given function. Choice of convolution mask and binarization function depend on the particular morphological operator being used.
Binary morphology has been used in several segmentation systems, and we provide here functional descriptions of morphological elements as applicable in our work.

Erosion: An erosion operation on an image I containing labels 0 and 1, with a structuring element S, changes the value of pixel i in I from 1 to 0, if the result of convolving S with I, centered at i, is less than some predetermined value. We have set this value to be the area of S, which is basically the number of pixels that are 1 in the structuring element itself. The structuring element (also known as the erosion kernel) determines the details of how a particular erosion thins boundaries.
Dilation Dual to erosion, a dilation operation on an image I containing labels 0 and 1, with a structuring element S, changes the value of pixel i in I from 0 to 1, if the result of convolving S with I, centered at i, is more than some predetermined value. We have set this value to be zero. The structuring element (also known as the dilation kernel) determines the details of how a particular dilation grows boundaries in an image.
Conditional Dilation A conditional dilation is a dilation operation with the added condition that only pixels that are 1 in a second binary image, , (the image on which the dilation is conditioned), will be turned changed to 1 by the dilation process. It is equivalent to masking the results of the dilation by the image.
Opening An opening operation consists of an erosion followed by a dilation with the same structuring element.
Closing A closing operation consists of a dilation followed by an erosion with the same structuring element.

As an example, Figure 6 shows (from top to bottom) a binarized MR cross section, erosion of the MR image with a circular structuring element of radius 3, conditional dilation of the largest connected component in the eroded image with a circular structuring element of radius 4. Since the dilation is conditioned on the original image, no boundaries are expanded in this process.

Figure 6: Examples of Erosion and Dilation on a Binary Brain Image
Mathematical Morphology in Context of Our Method
This step uses morphological operations (in 3D) to incorporate neighborhood information into the tissue-labeled image obtained from EM Segmentation. The strategy is to use morphological operators to ``shave off'' the misclassified nerve fibers and muscles connecting the brain tissue to the cranium, and then use connectivity to find the largest connected component of white and grey matter in the image. Similar methods have been used by others (e.g. [Hohne and Hanson 1992.]). Specifically, the sequence of operations performed is as follows:

Perform an erosion operation on the input with a spherical (in real space which implies elliptical in image space due to the anisotropy of the voxels) structuring element with radius corresponding to the thickness of the connectors between brain and the cranium (determined empirically, and held constant over scans), so that it eliminates connections from the brain to any misclassified non-brain structure.
Find the largest 3D connected component with tissue labels corresponding to the brain.
Dilate the brain component obtained in the previous step by a structuring element slightly larger in size to the one used in the erosion, conditioned on the brain labels in the input image. Since the dilation is conditioned on the original image, no boundaries are expanded in this process. This corresponds approximately to restoring the boundaries of the brain component that were distorted in the erosion step.

The result of this stage is an improved segmentation of the tissue types, which incorporates topological information into the results of the pure intensity classification. Figure 7 illustrates the results of this step on the first of our two example scans, and is representative of the case in which the EM segmentation step combined with the morphology step achieves an isolation of the brain.
Occasionally (in about 10 of the over 100 scans we have segmented), due to the variation in the size of the connecting elements from the brain tissue to the cranium, the empirically determined radius of the erosion kernel does not adequately model the width of the connectors between the brain and non-brain structures, and therefore the brain tissue is not isolated at the end of this step. This case is illustrated in the results of the morphological operations on our second example (Figure 8). Such scenarios are currently detected by manual inspection, and lead to the use of the third step of our algorithm which uses manually initialized deformable models to annihilate connections between the brain and spurious structures. More automatic methods for detecting these cases are currently under development.

Figure7: Top to Bottom, Left to Right: EM Segmentation from Figure 5, Binarized Image, Eroded Image, Largest Connected Component in Eroded Image, Dilated Connected Component, Conditionally Dilated Connected Component.

Figure8: Top to Bottom, Left to Right: EM Segmentation from Figure 4, Binarized Image, Eroded Image, Largest Connected Component in Eroded Image, Dilated Connected Component, Conditionally Dilated Connected Component. Note that the slice shown here is a cross-section of a full 3D data which happens not to show the connectors between brain and non-brain structures.