Thickening is a morphological operation that is used to grow selected regions of foreground pixels in binary images, somewhat like dilation or closing. It has several applications, including determining the approximate convex hull of a shape, and determining the skeleton by zone of influence. Thickening is normally only applied to binary images, and it produces another binary image as output.
The thickening operation is related to the hit-and-miss transform, and so it is helpful to have an understanding of that operator before reading on.
Like other morphological operators, the behavior of the thickening operation is determined by a structuring element. The binary structuring elements used for thickening are of the extended type described under the hit-and-miss transform (i.e. they can contain both ones and zeros).
The thickening operation is related to the hit-and-miss transform and can be expressed quite simply in terms of it. The thickening of an image I by a structuring element J is:
Thus the thickened image consists of the original image plus any additional foreground pixels switched on by the hit-and-miss transform.
In everyday terms, the thickening 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 foreground (one). Otherwise it is left unchanged. Note that the structuring element must always have a zero or a blank at its origin if it is to have any effect.
The choice of structuring element determines under what situations a background pixel will be set to foreground, and hence it determines the application for the thickening operation.
We have described the effects of a single pass of a thickening 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, the operations may only be applied for a limited number of iterations.
Thickening is the dual of thinning, i.e. thinning the foreground is equivalent to thickening the background. In fact, in most cases thickening is performed by thinning the background.
We will illustrate thickening with two applications, determining the convex hull, and finding the skeleton by zone of influence or SKIZ.
The convex hull of a binary shape can be
visualized quite easily by imagining stretching an elastic band around
the shape. The elastic band will follow the convex contours of the
shape, but will `bridge' the concave contours. The resulting shape
will have no concavities and contains the original shape. Where an
image contains multiple disconnected shapes, the convex hull algorithm
will determine the convex hull of each shape, but will not connect
disconnected shapes, unless their convex hulls happen to overlap (e.g.
two interlocked `U'-shapes).
An approximate convex hull can be computed using thickening with the structuring elements shown in Figure 1. The convex hull computed using this method is actually a `45° convex hull' approximation, in which the boundaries of the convex hull must have orientations that are multiples of 45°. Note that this computation can be very slow.
Figure 1 Structuring elements for determining the convex hull using thickening. During each iteration of the thickening, each element should be used in turn, and then in each of their 90° rotations, giving 8 effective structuring elements in total. The thickening is continued until no further changes occur, at which point the convex hull is complete.
The image
is an image containing a number of cross-shaped binary objects.
Applying the 45° convex hull algorithm described above results in
This process took a considerable amount of time --- over 100 thickening passes with each of the eight structuring elements!
Another application of
thickening is to determine the skeleton by zone of influence, or
SKIZ. The SKIZ is a skeletal structure that divides an image into
regions, each of which contains just one of the distinct objects in
the image. The boundaries are drawn such that all points within a
particular boundary are closer to the binary object contained within
that boundary than to any other. As with normal
skeletons, various possible distance
metrics can be used. The SKIZ is also sometimes called the
Voronoi diagram.
One method of calculating the SKIZ is to first determine the skeleton of the background, and then prune this until convergence to remove all branches except those forming closed loops, or those intersecting the image boundary. Both of these concepts are described (applied to foreground objects) under thinning. Since thickening is the dual of thinning, we can accomplish the same thing using thickening. The structuring elements used in the two processes are shown in Figure 2.
Figure 2 Structuring elements used in determining the SKIZ. 1a and 1b are used to perform the skeletonization of the background. Note that these elements are just the duals of the corresponding skeletonization by thinning elements. On each thickening iteration, each element is used in turn, and in each of its 90° rotations. Thickening is continued until convergence. When this is finished, structuring elements 2a and 2b are used in similar fashion to prune the skeleton until convergence and leave behind the SKIZ.
We illustrate the SKIZ using the same starting image as for the convex hull.
shows the image after the skeleton of the background has been found.
is the same image after pruning until convergence. This is the SKIZ of the original image.
Since the SKIZ considers each foreground pixel as an object to which it assigns a zone of influence, it is rather sensitive to noise. If we, for example, add some `salt noise' to the above image, we obtain
The SKIZ of that image is given by
Now, we not only have a zone of influence for each of the crosses, but also for each of the noise points.
Since thickening is the dual to thinning, it can be applied for the same range of tasks as thinning. Which operator is used depends on the polarity of the image, i.e. if the object is represented in black and the background is white, the thickening operator thins the object.
You can interactively experiment with this operator by clicking here.
using this structuring element and compare it with the result obtained with the structuring element shown in Figure 1.
Figure 3 Alternative structuring element to determine convex hull. This structuring element is used together with its 90° rotations.
Reduce all lines to a single pixel width and try to obtain their maximum length.
R. Gonzalez and R. Woods Digital Image Processing, Addison-Wesley Publishing Company, 1992, pp 518 - 548.
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.
Specific information about this operator may be found here.
More general advice about the local HIPR installation is available in the Local Information introductory section.
©2003 R. Fisher, S. Perkins,
A. Walker and E. Wolfart.
