Mathematical Morphology

Let A and B be subsets of ${\fam11\tenbbb R}^2$. Then the dilation of A by B is the set C defined by

$$C = A \oplus B = \{{\bf x}\in {\fam11\tenbbb R}^2: \exists {\bf a} \in A, \exists \b \in B, {\bf x}= {\bf a}+\b\}$$

where the addition is, of course, the vector addition in that well known vector space ${\fam11\tenbbb R}^2$.

In applications, A and B will be finite sets of pixels. We obviously have that $A \oplus B = B \oplus A$ but we shall tend to choose a particular B and think of it as operating on a lot of different A's. In this case, B is referred to as the structuring element.

Example: If A and B are the sets shown in Fig.2.5, where the origin and axes are as marked, we see that $A \oplus B$ is the `thickened' version shown as C. By making B bigger and approximately disk shaped, we can fatten A quite out of recognition. In this example, each black square is a pixel, and if we think of the corners of the square which is B being at the points $\left(\begin{array} {c} 0 \\ 0 \end{array} \righ... ... \\ 1 \end{array}\right),\left(\begin{array} {c} 1 \\ 1 \end{array} \right)$, every point x of A is expanded to a copy of the unit square stuck onto x at its lower left corner. So A is `blobbified' by B; equally, B has been blobbified by A.

 

Figure 2.5: $A \oplus B = C$

For digital images, the dilation procedure is somewhat simpler; we have the zero which is usually a part of the structuring element, and some points at integer co-ordinates. We simply move the structuring element B and place the zero at a pixel of A, and then fill in all the other pixels of B. Then we repeat for each of the pixels of the original A.

Similarly, it is possible to have an erosion operation, $A \ominus B$ which treats B as a mask with holes in it where the pixels are. Then to get $A \ominus B$, place the origin of B at a pixel of A, and look to see which of the pixels of A can be seen through the holes in B. If there are any holes in B without points of A visible through them, mark the pixel of A visible through the origin of B for deletion. Repeat for each pixel of A, and finally remove all the pixels marked for deletion. Formally:

$$C = A \ominus B = \{{\bf x}\in {\fam11\tenbbb R}^2: \forall \b \in B , {\bf x}+ \b \in A \}$$

Note that I have assumed in my explanation of how erosion is carried out that the origin is in B.

Exercise: What difference does it make if it isn't?

Repeated application of erosion by a suitable structuring element B can be useful for thinning sets. Carried too far, sets can easily be eliminated altogether.

Exercise: Draw a grid of lines, label a horizontal line in the middle somewhere as the X-axis, a suitable vertical line as the Y-axis, and draw pixel dots on the intersections at enough points to pick out a big fat character like the blobbified /2/ of Fig.2.5. This is A. Now take B to be the origin and its 8 nearest neighbours, on a separate grid drawn on transparent film. Do the dilation operation, then the erosion operation on the result. Start again and do it in the opposite order. Do the two operations commute? If the origin is omitted from B, and we use the formal definition, what effect does this have?

Remark There are hardware implementations of many such operations which are extremely fast. See Wojciech Kuczborski's Ph.D. thesis, coming real soon to a store near you, and referenced in the bibliography at this chapter's end. Well, you can write to Wojciech care of The Centre for Intelligent Information Processing Systems (CIIPS) at the University of Western Australia and ask nicely for a copy.

If we blobbify (or dilate) the set of pixels in the image Fig.2.4 by a horizontal bar of pixels, we `stretch' pixels horizontally. This will join up adjacent letters and blur them in a horizontal direction without having any effect vertically. It is childishly simple to write a program which goes over an array of pixels and dilates them horizontally: every time a black pixel is found, the new image has, say, black pixels inserted to the left and right of the location of the given pixel, as well as copying the original pixel. I assume, of course, that we are dealing with black images on a white ground.

Doing this to Fig.2.4, if necessary several times on the result of doing it previously, gives something close to horizontal bands. The page has its text at an angle, so the bands are not very horizontal, but it is now easy to find the spaces between the lines and also to determine the height of the bands that used to be characters. The lines of text can be numbered consecutively from the top and their direction specified.

Of course, there are ways of finding the lines of text which do not require us to apply morphology methods, but the methods will have other uses, and this seemed like a good place to introduce them.

I said it was easy to find the lines, and it is, if you don't mind doing the sort of ghastly hack that occurs naturally to the more depraved kind of programmer. If your aesthetic sensibilities are revolted by this sort of thing, good. There are better ways and we shall come to them in due course.