Activity #8 – Morphological Operations

Previously, in Activity #7, I started talking about morphological operations, where manipulations were done on binary images. Morphology refers to shape and structure, and morphological operations tend to make adjustments on an object’s shape and structure through the use of structure elements. Basically, binary images are those images having only image values of either 0 and 1 (“OFF” or “ON”, 0 or 255 in color space). These images were previously seen in the image thresholding and segmentation activity.

Before I present to you my own work, let us have a little talk on Set Theory, which is a guiding principle behind morphological operations.

I. Set Theory

Since we are working with images, pixel coordinates must be the subject of set theory. The following texts were directly obtained from [1]. If we let A be a set in 2-D image space Z², then the following are operations are considered:

• Element Operator – (∈) indicates if a pixel belongs to the set A (i.e. a ∈ A). If a pixel b does not belong to A, then we write b ∉ A.
• Subset Operator – (⊂) indicates if another 2D set B belongs to A (i.e B ⊂A). If a set C is not a subset of A, then we write C ⊄ A.
• Union of Two Sets – (∪) refers to the set of all elements belonging to either sets A or B (i.e. A ∪ B).
• Intersection of Two Sets – (∩) refers to the set of all elements that are both in A and C only (i.e. A ∩ B).
• Empty Set – Ø indicates a null or zero set.
• Complement of a Set – (A^C) indicates all elements not belonging to set A.
• Difference of Two Sets – (A – B) indicates all elements belonging to A, excluding all elements belonging also to B.
• Reflection of a Set – (Â) indicates all pixels that have coordinates negative of that of A.
• Translation of a Set – (A)_Z indicates a translation by point z = (z₁,z₂) of all elements belonging to A (i.e. a + z, where a ∈ A).

These are some of the basic set operations we can find in set theory. Some of the logic operations we encountered in logic circuits can be represented by these operators. An XOR (exclusive OR) operator can be represented as {c: c ∈ [(A ∪ B) – (A ∩ B)]}, which translates to “the set of all elements c such that c is an element of [(A ∪ B) – (A ∩ B)].” The logical operator [NOT(A)] AND B can also be represented as (B – A) in set operations.

II. Erosion and Dilation

 The first morphological operations that I will demonstrate are the Erosion and Dilation operators. In geology, erosion is the process of removing soil and rock towards from one place to another. The erosion of a set A by a set B is the set of all points z such that B translated by z is contained in A. What happens is that the size of A is reduced by the size of B. This is given by the notation: A ⊖ B = {z| (B)_z  ⊆ A  }. In images, the set B is called a Structuring Element.

Before doing any computational work, let’s try to predict the shapes of different structures when they are eroded by different structuring elements by hand. Here are the shapes:

Figure 1. Drawn structures of a) a 5×5 square, b) a right-triangle, c) a 10×10 hollow square, and d) a cross with length 5 pixels.

Now, here are the structuring elements used to erode the images:

Figure 2. Drawn image of a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The circles indicate the location of the point of origin.

Notice the point of origin indicated in the figures. This will serve as our reference point when we determine whether a pixel in the initial image is a member of the final image or when the image is eroded. Remember that erosion is actually a subset operator, and that pixel membership is important. Usually, the point of origin would not affect the final shape of the image, but the point of origin will indicate how the image is to be eroded. Let’s try erosion for our 5×5 square:

Figure 3. Eroded images of the 5×5 square when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The “x” marks indicate the pixels of the final image and the dashed lines indicate the initial image.

As you can see, the initial images were shrunk down based on the structure elements used. What basically happens is that when a structuring element is found on the initial image, the location of its point of origin will then be included in the eroded image. Although the final shape of the image would not be affected by the location of the origin, the pixel membership would be different  since translation is part of the erosion’s definition. The erosion in (a) is the same as in (e), although the structuring element used is only 2 pixels in (e). It is then good to choose a structuring element that would optimize the digital morphological operations. Let us now move one with the right triangle:

Figure 4. Eroded images of the right triangle when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The “x” marks indicate the pixels of the final image and the dashed lines indicate the initial image.

The same process goes with the right triangle. Now, notice in (d) that the image is totally gone, as there are no “cross” structuring element to be seen inside the right triangle. It is then possible to diminish any image to zero, as long as the structuring element is nowhere to be found in the shape of the image.

Figure 5. Eroded images of the 10×10 hollow square when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The “x” marks indicate the pixels of the final image and the dashed lines indicate the initial image.

The erosion of the hollow square when the structure element is the diagonal is bit tricky. Since we already assumed from the start that the erosion via 2×2 square and diagonal are the same, we would think that it would be the same for this hollow square. Two pixels in the corners are still included, which is a bit tricky to find as they are located in the corners of the initial image. Generally, the erosion of a hollow square would increase the size of the hole.

Figure 6. Eroded images of the 10×10 hollow square when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The “x” marks indicate the pixels of the final image and the dashed lines indicate the initial image.

The erosion of a cross is also straightforward, although the erosion in (e) is also a tad tricky.

Let’s move on with the opposite of erosion, which is Dilation. When we say we want to dilate an image, we then want to enlarge it. Similar to erosion, the dilation of an image will depend on the structure element used. In image set theory, dilation involves all z’s which are translations of a reflected B that when intersected with A is not the empty set, which is defined by the notation [1]: A⊕E = { z | (Ê)_z ∩  A ≠∅ }. To make things easier, let’s demonstrate it using our initial images and structuring elements.

Figure 7. Dilated images of the 5×5 square when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The dots indicate the added pixels and the dashed lines indicate the initial image.

In dilation, we want our final image to include the initial image, while adding pixels based on the structuring element. Think of it as this way: we want each and every pixel in our initial image to be an origin of the structuring element, so whenever they lack the pixels, we add them. This gives a distinction between the dilation in (a) and dilation in (b), in which the pixels that the diagonal structuring element lacks to be a 2×2 square becomes apparent in the dilation.

Figure 8. Dilated images of the right triangle when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The dots indicate the added pixels and the dashed lines indicate the initial image.

The same process goes for the right triangle.

Figure 9. Dilated images of the hollow square when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The dots indicate the added pixels and the dashed lines indicate the initial image.

Generally, in the hollow square, dilation decreases the size of the hole based on the structuring element used.

Figure 10. Dilated images of the cross when the structuring element used is a) a 2×2 square, b) a 2×1 rectangle, c) a 1×2 rectangle, d) a cross with length 3 pixels, and e) a diagonal. The dots indicate the added pixels and the dashed lines indicate the initial image.

Similarly, the dilation process in the cross is straightforward. As can be deduced from my predictions, the erosion is complementary to dilation.

Now, let’s use our dear Scilab to verify my predictions. In Scilab, the Image Processing Design (IPD) toolbox is best for doing these morphological operations, as the functions CreateStructureElement(), which creates the structuring element, ErodeImage(), and DilateImage() does these operations automatically. Here is a sample code for the erosion and dilation of the 5×5 square:

Scilab code for the erosion and dilation of a 5×5 square.

The CreateStructureElement() function hastens the creation and process of dilating and eroding an image. With this code structure, we apply it to all the images we have. I have here a summary of all the erosion parts of the code:

Figure 11. Compilation of all eroded images. Images in the first column (left) are the initial images, and the images in first row (top) are the structuring elements. Their intersection is the eroded image.

To enhance the quality of the image, I used Photoshop to enlarge the image and highlight the pixel areas of the image. This is done because the final images produced by Scilab are very small due to the size of the pixels. All the predictions done for the erosion part were consistent with the simulations.

Figure 12. Compilation of all dilated images. Images in the first column (left) are the initial images, and the images in first row (top) are the structuring elements. Their intersection is the dilated image.

Similar to Figure 11, all simulations for the dilation operator were consistent towards the predictions.

III. Closing, Opening and Top-Hat Operators

In image processing, we are not just limited with eroding and dilating images. One can manipulate structures by combing different morphological operations. Let me first demonstrate the Closing operator.

In the closing operator, one first dilates an initial image then erode it with the same structuring element. It seems intuitive that when we close an image, there’s nothing going to happen to it, since dilation and erosion of the image with the same structuring element would return it to its original image. However, as we have seen in the hollow square dilation in  Figure 9, dilation would decrease the size of the hole. If we increase the size of the structuring element, we would eventually cover the hole. Erosion by the same structuring element then would return the shape into its initial size, without the hole. The closing operator is then best in closing holes in the foreground. Let me demonstrate this using the PCB layout from [2] shown below:

Figure 13. Image of a PCB layout. Image obtained from: http://homepages.inf.ed.ac.uk/rbf/HIPR2/close.htm

If I want to remove the lines from the image while preserving the circles, then I can just use a structuring element that dilates the white part of the board into closing the black lines, and then erodes the image while not ultimately affecting the circles. Moreover, the circles has holes that are white, meaning, if we choose a structuring element that is bigger than the circle, we would eventually diminish them. By using a structuring element that is thicker than the lines, we retain the circles using the closing operator (in Scilab, this is CloseImage()):

Figure 14. Closed image of the PCB.

Although the quality of the circles were affected by the process, the thin lines vanished in the process.

We now move on towards the opposite of the closing operator, which is the opening operator. When opening an image, we erode first the image and then dilate it with the same structuring element. Remember that when we erode images with certain structuring elements, the image could diminish to nothing. The opening operator is then best when we preserve the foreground image that is the same size as the structuring element. This includes removing connections and unwanted patterns in the image. To demonstrate this, I have here a binary image of sticks and circles from [2]:

Figure 15. Binary image of sticks and circles.

Note that the background of the image is black, which is contrary to the PCB layout shown in Fig. 13. If I want to remove the thick sticks from the image, I would then first erode the image by a circular structuring element that is smaller than the circle, and the dilate it with the same structuring element. This diminish the sticks and preserve the shape of the circles. In Scilab, this function is OpenImage().

Figure 15. Opened image of the sticks and circles with a circular structuring element.

The sticks were successfully removed and the circles are retained. Since some of the circles overlapped with the sticks, the shape of some circles are also affected, as some of the elements are retained.

The next operator is the Top-Hat operator. There are two types of top-hat filters: the white top-hat transform, which first opens the image and then subtracts the results from the original image, and the black top-hat transform, which closes the image and then subtracts the results from the original image [3]. In Scilab, the TopHat() function is default to white top-hat transform. This operator is usually used in correcting uneven illuminations in grayscale images. Here is a grayscale image of scattered rice from [3]:

Figure 16. Grayscale image of scattered rice with uneven illumination.

Similar to what is done and outlined in [3] for MATLAB, I used a circular structuring element of size 12, and adjusted the contrast using Photoshop. Here are the results:

Figure 17. Image of the scattered rice after top-hat operator is used (left) and its contrast adjusted image (right).

The illumination in the background has been corrected in the image. This is then useful in most grayscale images, as these image are sensitive to light variations.

IV. Cancer Cell Filtering

With those operations and concepts in mind, let us now apply our knowledge towards one of the most important uses of morphological operations: Cell Filtering. Mammograms, Computerized Tomography (CT scans), and Magnetic Resonance Imaging (MRI) are frequently used to detect tumors, which are cells that are larger than normal cells. By applying basic morphological operations and statistics, one can detect where the abnormal cells are by digital means.

The first part of this basic cancer cell detection is determining the mean area of a normal cell. I have here an image of circles, which we will call normal cells, from [1].

Figure 18. Image of circles or normal cells.

The first thing we have to do is to divide the image into different sub-images (in this case, size 256×256 pixels) in order to obtain samples for the areas of the normal cells. Let us first manipulate a sub-image shown below before we decide on anything with the whole image.

Figure 19. Sub-image of the normal cell image in Fig. 18.

Let us now try doing some operations on this image. First, we have to convert this to a binary image, highlighting the circles. The steps in doing so for a grayscale image is discussed in my previous blog post (Activity #7 – Image Segmentation), so feel free to scan a bit if do not know how to do it. Basically, what happens is that artifacts such as stray white pixels can be observed throughout the image, and we want to remove them. After segmenting it, let’s use the three operators discussed (open, close and top-hat) with circular structuring elements of varying size, and see its effect on the circles.

Figure 20. Initial segmented image (left) with (threshold value = 210) and the resulting image when the closing operator is used with a circular structuring element of size (from left to right) 5, 10 and 13.

Figure 21. Initial segmented image (left) with (threshold value = 210) and the resulting image when the opening operator is used with a circular structuring element of size (from left to right) 5, 10 and 13.

Figure 22. Initial segmented image (left) with (threshold value = 210) and the resulting image when the top-hat operator is used with a circular structuring element of size (from left to right) 5, 10 and 13.

There are two things we want to happen in the segmented image: one is to remove stray intensities, and the other is to preserve the shape of the circles. In the closing operator, the circles become connected due to the dilation part. In the top-hat operator, most parts of the circles become darkened. These two operators does nothing to achieve our goal. Fortunately, the opening operator did the job. It eroded first the stray intensities and connections with the circles, and then preserved the shape and size of the circles. However, notice that by increasing the size of the structuring element, most of the circles become eroded. This is why the initial image is divided into sub-images to increase the sample size of area estimation.

After obtaining a cleaner segmentation, we now access the information about the individual circles. Since each image has circular overlaps, let us first call all the elements with a definite area “Blobs.” The IPD toolbox of Scilab contains the function SearchBlobs(), which will find all of the blobs in a binary image. By doing so, I show here all the blobs in the opened sub-image with a structuring element of radius 10.

Figure 23. Image of all the blobs in the opened sub-image.

Now the image contains all the separated circles and the overlapped circles. These are the individual blobs in the sub-image. But wait just a second, why is there a single image with no blob in it? Could this be an artifact that has never been seen before? (Insert X-Files Theme Here). This anomaly could be attributed to the algorithm used, and I still don’t have an idea about it. But we have to bear this in mind since it will affect our area calculation. The next thing to do is to make a histogram of all the areas of the blobs. To do this, the I use the IPD toolbox function CreateSizeHistogram(), which returns the area values and the frequency in each area. The area is defined as the number of white pixels in each blob. Here is a histogram of the sizes (I did the plotting in Python programming environment because Scilab seems to be bugging for me).

Figure 24. Area histogram of the blobs in the opened sub-image.

As we can see from the histogram, most of the circles have areas between the values 400 to 600 pixels. The higher values are the blobs with overlapped circles, while the lower values indicate blobs that are cut in the sub-image extraction. We do not want those, so we will restrict the area computation in the region stated.

With that in mind, let us now open all the sub-images.

Figure 25. Image of all the sub-images (left) and its opened counter-part (right).

By doing the same procedure as in what is done in the sub-image, we obtain the area histogram of all the sub-images.

Figure 26. Area histogram of all the blobs in all of the sub-images of the normal circles image.

Similar to the histogram in the sub-image, most of the circular area values are in the range of 400 to 600 pixels. We them take out the outlying areas and compute for the mean and standard devation of the remaining areas. By using mean() and stdev() function, the calculated mean and standard deviation values are 485.52632 pixels and 38.180749 pixels, respectively. The maximum and minimum areas that a normal cell could then have would be 523.70706 pixels and  447.34557 pixels. These are important values as we filter out cancer cells.

With those values in mind, we are ready to fight cancer. Here is an image of circles with cancer cells.

Figure 27. Image of the circles with cancer cells (larger circles) from [1].

I show here the histogram of the circles to first have a verification that most of the circles are indeed in the range of the minimum and maximum area we calculated. This is done after segmenting and opening the image.

Figure 28. Area histogram of the circles with cancer cells.

Most of the circles area indeed in the range of areas we have calculated. Let us now move on with cancer cell filtering. My method includes the use of FilterBySize() function of the IPD toolbox. In this function, one has to specify the minimum and maximum areas of the blobs in a blob matrix. The function then returns all the blobs which have sizes in the range of the given values. From the histogram, the outlying bigger circles have accumulated towards 600 to 1200. The higher areas indicate the large accumulation of other cells, which overlapped to produced a much bigger area. This is verified by finding the blobs which have these areas. We don’t want those because they are not classified as cancer cells, so we restrict our cells with those in the 600 to 1200 area values. The filtered cells are shown below.

Figure 29. First filtering of the cancer cell image. Blobs with two circles overlapping are still present.

The first result of the FilterBySize() function is shown above. As you can see, there are still blobs with overlapping circles present. They are counted as blobs whose areas are larger than the normal size. We don’t want them, so we take them out. There are two ways we can do this: first is to detect every single blobs that are not included one-by-one, or by using a morphological operator. The first method is accurate, since we are to judge whether the blob is counted or not. This method is applicable to this image, since the number of blobs has diminished. However, if there still too many blobs in the image that are considered abnormal, this method is tedious. The second one uses an operator, specifically the opening operator. The opening operator diminishes the size of the smaller circles, in which when a circular structuring element that has a size bigger than the normal cells but lesser than the cancer cells is used, the normal cells would be evaporated. Thus, the connected blobs becomes are reduced to zero, while the dilation part of the operator returns the size of the cancer cells. This method is better to use when there are a lot of blobs that are retained in the process, but are not considered cancer cells. Here is the final output when the opening operator is used.

Figure 30. Final filtering of the cancer cell image. Structuring element used for opening Fig. 29 is a circular structuring element of radius 13.

I then mapped the cancer cells with the initial image and labelled the cancer cells.

Figure 31. Cancer cell image with labels on the cancer circles.

We were able to detect and label all of the cancer cells associated with this image. Moreover, the overlapping cells in the first filtering where consisted with the initial image.

This has been one of the most tedious activities I’ve done in our image processing class. Artifacts in codes and algorithms have slowed the task of finishing this activity. However, the result had far better reward than what is given. Cancer cell detection could be as easy as pie nowadays, but the highly advanced mechanisms and technique all started with these basic operations. I have limited the work on binary images, which is by far, the crux of morphological operations. Grayscale images can be done also, with different results regarding the type of operators used. These operators are not limited to only cancer cell detection. Different structuring elements can be combined with these operators to achieve do much bigger and harder results. With this, I gave myself a 12/10 for fully understanding the concepts and doing the whole activity.

Acknowledgements: I would also like to thank Ms. Eloi for the fruitful discussion about this.

References:

1. M. Soriano, “Morphological Operations,” 2014.

2. R. Fisher, et. al., “Morphological Operations,” Hypermedia Image Processing Reference, 2003. Retrieved from: http://homepages.inf.ed.ac.uk/rbf/HIPR2/copyrght.htm

3. MathWorks Documentation on “Top-Hat Filtering (imtophat).” Retrieved from :  http://www.mathworks.com/help/images/ref/imtophat.html