Mathematical Morphology is the analysis of signals in terms of shape. This simply means that morphology works by changing the shape of objects contained within the signal. Mathematical morphology was developed in the 1970�s by G.Matheron [1] and J.Serra [2]. Morphology has several advantages over other techniques especially when applied to image processing as outlined below:
- Preserves edge information
- Works by using shape-based processing
- Can be designed to be idempotent
- Computationally efficient
Morphology has been used in a wide range of applications. A few of the possible applications are listed below:
- Image enhancement
- Image restoration (i.e. removing scratches from digital film [3,4])
- Edge detection
- Texture analysis
- Noise reduction
There are many more applications that morphology can be applied to. Morphology has been widely researched for use in image and video processing, but with no application to pre-processing for increasing a CODEC�s performance. The rest of this document covers the basic principles behind Morphology, building up from simple 1D binary functions to 3D grey-scale functions.
Binary Morphology
Dilation
Morphology uses �Set Theory� as the foundation for many functions. The simplest functions to implement are �Dilation� and �Erosion�. Dilation in 1D is defined as:
(1)
where A and B are sets in Z. This definition is also known as �Minkowski Addition�. This equation simply means that B is moved over A and the intersection of B reflected and translated with A is found. Usually A will be the signal or image being operated on and B will be the �Structuring Element�. Equation 1 is used to process binary sets of data. Dilation has several interesting properties, which make it useful for image processing. These properties are:
- Translation invariant.
This means that the result of A dilated with B translated is the same as A translated dilated with B as given by:
(2)
- Order invariant.
This simply means that if several dilations are to be done, then the order in which they are done is irrelevant. The result will be the same irrespective:
(3)
- Increasing operator.
This means that if a set, A,is a subset of another set, B, then the dilation of A by C is still a subset of B dilated by C:
(4)
- Scale invariant.
This means that the input and structuring element can be scaled, then dilated and will give the same as scaling the dilated output:
(5)
where r is a scale factor.
These properties can be very useful in image processing and can result in some operations being simplified. Figure 1 shows how dilation works on a 1D binary signal. The structuring element shown in Figure 1 uses the value of the elements immediately to the right and left of the current element (the structuring element in this case looks for ones on the input sequence). Any shape or size-structuring element can be used, where an element with the value of 0 indicates that the corresponding element in set A is not to be used, and a value of 1 indicates that it is to be used. For example, the structuring element shown could be considered to have 0�s on the extreme left and right, as the corresponding inputs would be ignored.
Figure 1: Example of how dilation works
The output is given by (1) and will be set to one unless the input is the inverse of the structuring element. For example, �000� would cause the output to be zero. The output is placed at the origin of the structuring element as shown.
From Figure 1, it can be seen that dilation will completely remove any runs of zeros less than the length of the structuring element (this is only for this type of structuring element though). Longer runs of zeros are shortened at their extremities. Note there is a problem with this technique. That is, what happens at the borders? In general, the structuring element is offset so that it is completely contained within the signal. However, this results in the output containing less data than the input, which is not desirable for image processing where the whole image is to be modified.
Although there are several ways of overcoming this problem, the chosen method is to detect when the structuring element is at the edge, and only use information from the parts of the structuring element that still lay within the signal.
Erosion
The opposite of dilation is known as erosion. This is defined as:
(6)
This definition is also known as �Minkowski Subtraction�. The equation simply says, erosion of A by B is the set of points x such that B translated by x is contained in A. Figure 2 shows how erosion works on a 1D binary signal. This works in exactly the same way as dilation. However (6) essentially says that for the output to be a one, all of the inputs must be the same as the structuring element. Thus, erosion will remove runs of ones that are shorter than the structuring element. Erosion, like dilation also contains properties that are useful for image processing:
- Translation invariant.
This means that the result of A dilated with B translated is the same as A translated dilated with B as given by:
(7)
- Order invariant.
This simply means that if several erosions are to be done, then the order in which they are done is irrelevant. The result will be the same irrespective:
(8)
- Increasing operator.
This means that if a set, A,is a subset of another set, B, then the dilation of A by C is still a subset of B dilated by C:
(9)
- Scale invariant.
This means that the input and structuring element can be scaled, then dilated and will give the same as scaling the dilated output:
(10)
where r is a scale factor.
Figure 2: Example of how erosion works
Opening & Closing
Both dilation and erosion have intresting and useful properties. However, it would be useful to have the properties of both in one function. This can be done in two ways. The first method , �Opening�, is defined as:
(11)
This simply erodes the signal and then dilates the result as shown in Figure 3. As can be seen, the zeros are opened up. Any ones that are shorter than the structuring element are removed, but the rest of the signal is left unchanged. This is a very useful property as it means that if the filter is applied once, no more changes to the signal will result from repeated applications is known as �Idempotent�:
(12)
The opposite of opening, is �Closing� defined by:
(13)
Figure 4 shows how this works. It can be seen that this closes gaps in the signal in the same way as opening opened up gaps. Closing also has the property of being idempotent.
Figure 3: Example of how an opening works
Figure 4: Example of how a closing works
Both of these filters again have interesting properties that would be nice to have in one filter. The opening and closing can be combined to merge these properties. There are two ways of combining these, the first of which is known as an �Open-Close� filter and is defined by:
(14)
The signal is first opened and the result is then closed. The opposite can also be done by closing and then opening. This is called a �Close-Open� filter and is defined by:
(15)
Figure 5 shows how these filters work. It can clearly be seen that both filters remove any runs of ones or zeros that are shorter than the structuring element. The operations, Open-Close and Close-Open are both idempotent.
Figure 5: Example of how OpenClose and CloseOpen work
Extending to grey scale
For morphology to be of use in image processing, it needs to be extended to non-binary signals. There are various ways in which this can be done [3]. The chosen method uses very simple functions, which allow them to be implemented in an efficient way. The following sections describe one method of implementing grey scale morphology.
Grey scale dilation
From Figure 1 it should be clear that this is actually taking the maximum value lying within the structuring element. Hence, dilation can be redefined for grey scale as:
(16)
This works in exactly the same way as before, but just takes the maximum value laying within the 1�s of the structuring element as shown in Figure 6. This method of using the values where the structuring element is 1, is known as a �Flat Structuring Element� (FSE). There is another method [5] that is used in greyscale image processing. Unless stated otherwise, the method described above is used in this report, the following description is included as a reference only.
Figure 6: Example of how a dilation works
As well as having the structuring element to choose the input elements to use, another set is used to allow a value to be added to the values used. This is sometimes written as one set as shown in Figure 7.
(17)
Figure 7: Example of how a variation on standard dilation works
Grey scale Erosion
Like dilation, from (6) and Figure 2 it should be clear that all erosion is actually doing is taking the minimum value from within the structuring element. Thus, erosion can be redefined as:
(18)
Both of these can still be applied to binary signals, but more importantly, they can be applied to real numbers. The rest of the functions, opening, closing and so on remain unchanged, but use the above definition for grey scale.
Extending to two dimensions
Now to be able to use morphology in image processing, the definitions need to be applied in two dimensions (2D). This can be done relatively easily as described below.
2D Dilation
The signal has now become a 2D signal, now called an image and hence the structuring element is changed to become 2D as shown in Figure 8 where the first structuring element shown is known as the Four Nearest Neighbours (4nn). This limits the operations to work only on horizontal and vertical components. To overcome this problem and allow diagonal components to also be used, the Eight Nearest Neighbours (8nn) can be used. Dilation can now be redefined as:
(19)
Figure 8: Extension to 2D
This still works in the same way as before as shown in Figure 9. The structuring element is moved across the image as before. The maximum value inside the structuring element is then set as the output.
Figure 9: Example of how 2D dilation works
2D Erosion
Erosion can also be redefined in exactly the same way, as dilation was to give a new 2D erosion definition:
(20)
This works in the same way as dilation with the exception of erosion takes the minimum instead of the maximum. Again, the other definitions of opening, closing, etc. remain unchanged. To use them in 2D, they must use the above methods for erosion and dilation.
Application to image filtering
These filters can now be applied to images as shown in Figure 10 (this gives a clear illustration of the effect of the filters).
 |
| Input image - Barbara |
 |
| Dilated |
 |
| Eroded |
 |
| opened |
 |
| Closed |
 |
| OpenClose |
 |
| CloseOpen |
| Figure 10: Example of basic morphological operations |
It can be seen from these images exactly what the operations do. Dilation extends the boundary of object by removing low valued regions. Erosion contracts the boundaries by removing high valued regions. Distortions can bee seen in some of these images. The distortion generated not only depends on the filter but also on the image.
Opening will remove high intensity points whilst keeping the rest of the image intact. Closing is doing the opposite of this, removing low valued points whilst keeping the rest of the image intact. Both Open-Close and Close-Open remove both high and low valued points while keeping the rest of the image intact. However, the last two operations do not give the same result due to the order of the erosions and dilations.
Extension to three dimensions
For video processing, it is beneficial to filter spatio-temporally (i.e. in Three Dimensions, 3D). This is done because noise is uncorrelated which means that if a pixel in the current frame is noise, then there is a strong chance that the pixel will be of a different value in other frames. Hence, by using the other frames to process the current frame, the noise can be filtered out.
3D Dilation
As before, dilation can be easily extended to process in 3D as defined by:
(21)
Now the image is 3D (i.e. a sequence) and the structuring element is now 3D as shown in Figure 11. This is applied in the same way as before. The structuring element is placed on the first pixel of the first frame The output is set to the maximum value lying within the structuring element. The structuring element is then moved across the current frame until the entire frame has been processed. Then the next frame is done in exactly the same way. The process is repeated until all the frames have been processed.
3D Erosion
Again, erosion can be redefined in the same way to give:
(22)
The other filters, open, close, etc. are still the same as before, but just use the above definitions for 3D.
Figure 11: Basic principles of 3D morphology
Application to Video pre-processing
These filters can now be applied to video sequences. Visually the results appear almost the same as for the 2D method. Figure 12 illustrates how similar the methods are by showing dilation on an image and on a sequence. However, 3D processing can remove more noise and smooth the images more because of the correlation between frames. This is good for compression as high frequency information is removed. However, this only works well when there is little motion in the sequence (see Figure 13). This can cause �Drop-outs� (a dark spot) and �Spikes� (a bright spot) in the sequence. These methods posses the properties required for pre-processing, but need to be enhanced to overcome this limitation.
 |
| Input Image - Claire, frame 3 |
 |
| 2D dilation of frame 3 |
 |
| 3D dilation of frame 3, using frames 2 and 4 as well |
| Figure 12: Example of the effects of 3D dilation on low motion video |
 |
| Input Image - Stefan, frame 91 |
 |
| 2D dilation of frame 91 |
 |
| 3D dilation of frame 91, using frames 90 and 92 as well |
| Figure 13: Example of the effects of 3D dilation on high motion video |
Granulometry
The filters described so far have interesting properties. However, one of the properties not mentioned so far is that of �Granules�. A granule is an element that falls through a �Sieve� in the same way that small stones fall through a sieve. If a set of structuring elements is used with increasing size, 
with the property that B(t) is B(r) opened for t≥r. This just means that each structuring element is bigger than the previous. Using this, an opening can be defined to use these structuring elements:
(23)
If this satisfies the �semi-group� property (24), then the openings are called a 'Granulometry�. If all ar are translation invariant (7), and scale compatible (10), then it is called �Minkowski Granulometry�.
(24)
1D Grey Scale Granulometry
It is difficult to see from the above definition, exactly what Granulometry does. As stated above, a set of increasing size structuring elements are used as shown in Figure 14.
Figure 14: Example of increasing size structuring elements
The shaded block is the origin (note this could be placed anywhere).
The opening used above is good, but a more useful method would be to use and Open-Close, which will remove both dark and light spots. Thus, using the previous definitions, an Open-Close can be redefined for a sieve as:
(25)
where m is the given size to use. From this it should be clear that the size will determine the data that is removed. For example, if r=2, the corresponding structuring element will remove runs of length 2. However, for a true sieve, this must be done in order. For example, for a target size of 4, the input would first be processed to a size of 1. The result would then be processed to 2 and so on until the target is reached. This is defined as:
(26)
where t is the target size. This can be seen more clearly in Figure 15 and Figure 16. The granules of the system are simply the result subtracted from the input as given by:
(27)
Figure 15: Example of a sieve structure
Figure 16: Example of a sieve up to size 2. Note that the output will depend on the location of the origin within the structuring element and if an OpenClose is used or a CloseOpen. Origins of the structuring elements are shaded.
It should be clear to see that the outputs on Sm, are the low-pass filtered signal whilst the outputs of Gm, are the high-passed signal. Provided no data is thrown away, the original signal can be reconstructed exactly.
2D Grey Scale Granulometry
The previous techniques have proven that morphology is a good for filtering. However, some images show a more noticeable degradation than others. This is due to the fact that the filters described so far all operate on the entire image with no knowledge of the image statistics. This is especially noticeable when sequences with a lot of motion are used. This section describes a filter that will act on the entire image, but that only changes local minimum and maximum points.
The method used is known as �Area Morphology�. This is an extension of 1D grey scale granulometry. For a detailed analysis and theory behind area morphology, the reader is directed to The definition for a grey-scale Area-Opening is given as:
(28)
where Al is the set of subsets which are connected and whose area is greater or equal to l.� This essentially looks at all possible openings that give a certain area-size and uses the maximum found as the result.� The opposite can also be applied, that is to perform an Area-Closing:
(29)
Area sieves
Area morphology can be used to create a 2D and 3D sieves.< The basic sieve structure is used, except that an Area-OpenClose is used. An Area-OpenClose is just an Area-Open followed by an Area-Close (see Figure 17). Figure 18 shows an example of a 2D sieve. This clearly shows how a sieve works and how the granules fall through the sieve.
Figure 17: Example of a 2D sieve structure using area morphology
Figure 18: Example of how a sieve works on images
Application to video
This method can again be applied to images and sequences as shown above and will cope better with motion in sequences, as the growing will actually track objects. It should also be clear that this method could also be described as a sieve. Again provided that no data is thrown away, then the original image can always be reconstructed. However, the idea is to remove parts of the image that the viewer will not notice. Hence there is little point in keeping any data other than the filtered image.
References
[1] G.Matheron, �Random Sets and Integral Geometry�, John Wiley & Sons, ISBN: 0-471-57621-2.
[2] J.Serra, �Image Analysis and Mathematical Morphology�, Academic Press, ISBN: 0-12-637240-3.
[3] J.A.Bangham & S.Marshall, �Image and signal processing with mathematical morphology�, Electronics & communication engineering journal, June 1998, pp117-128.
[4] N.R.Harvey and S.Marshall, �Restoration of archive film material using multi-dimensional soft morphological filters�, In Proceedings of the IEEE-EURASIP Workshop on Nonlinear Signal and Image Processing, pages 811-815, Bogazici University, Istanbul, June 1999
[5] R.C.Gonzalez & R.E.Woods, �Digital Image Processing�, Addison Wesley, ISBN: 0-201-60078-1.