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 1Structuring 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 2Structuring elements used in determining the SKIZ.1aand1bare 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 elements2aand2bare 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.

- What would the convex hull look like if you used the structuring
element shown in Figure 3? Determine the convex hull of
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.

- Why is finding the approximate convex hull using thickening so slow?
- Can you think of (or find out about) any uses for the SKIZ?
- Use thickening and other morphological operators
(
*e.g.*erosion and opening) to processReduce 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.