Morphological Operations

In image processing, there are many morphological operations. Some examples of these operations are union, intersection, complement, difference, reflection, translation, etc. These operations operate under the assumption that the structures or shapes are in binary.

The focus of this activity is the other two types of morphological operations namely: dilation and erosion. The dilation of a shape A with a structuring element B is adding A with a set Z where Z are the translations of a reflected B that when intersected with with A is not the empty set. The erosion of a shape A with a structuring element B is the set of all points Z such that B translated by Z is contained in A.

To show dilation and erosion, I generated four shapes and five structuring elements. The shapes are: a 5×5 square, a triangle (base of 4 and height of 3), a 10×10 hollow square (width of 2) and a plus sign (length of 5 each line). The structuring elements are: 2×2 ones, 2×1 ones, 1×2 ones, cross (3 pixels long, 1 pixel thick) and a diagonal line (2 boxes long). Figure 1-5 shows the four shapes being eroded and dilated (my assumption).

Figure 1. 5×5 square being eroded and dilated by the five structuring elements

Figure 2. Triangle being eroded and dilated by the five structuring elements

Figure 3. A 10×10 hollow square being eroded by the five structuring elements

Figure 4. 10×10 hollow square being dilated by the five structuring elements

Figure 5. Plus sign being eroded and dilated by the five structuring elements

To check if the outputs are correct, I performed the morphological operations in Scilab. Figures 6-9 shows the results of the morphological operations.

Figure 6. (top) Erosion and (bottom) dilation of a 5×5 square in the order same as in Figures 1-5.

Figure 7. (top) Erosion and (bottom) dilation of a triangle in the order same as in Figures 1-5.

Figure 8. (top) Erosion and (bottom) dilation of a 10×10 hollow square in the order same as in Figures 1-5.

Figure 9. (top) Erosion and (bottom) dilation of a plus sign in the order same as in Figures 1-5.

We see that each assumption matched with the Scilab-performed output. But I will not discuss everything in detail anymore because it just follows a certain pattern. To summarize, in eroding, when the structuring element is not found within the shape on a certain pixel, that certain pixel is eroded (zeroed out). In dilating, when the structuring element is not found within the shape on a certain pixel, the shape is expanded following the shape of the structuring element.

After discussing the morphological operations, we now proceed to discussing some applications namely: Open, Close and TopHat. Open operation is an operation in which:

open(shape,element) = dilate(erode(shape,element))

Close operation is an operation in which:

close(shape,element) = erode(dilate(shape,element))

TopHat operation is an operation in which:

tophat(shape,element) = shape – open(shape,element)

To examine these operations, I will also find an application to perform simultaneously. For the application, I am to isolate the “cancer cells” (big circles) from a group of “normal cells” (small circles) as shown in Figure 10.

Figure 10. Group of “cells” composed of “normal cells” and “cancer cells”

To do this, I first have to acquire a separate image to calibrate and get an approximation of the area of “normal cells”. Figure 11 shows the image to perform approximation.

Figure 11. Image of “normal cells” used to approximate its area

I separated Figure 11 into 12 subimages each having a size of 256×256. This is to get more data points and thus leading to a better approximation of the area. After separating into subimages, I will use one to discuss the effect of the three operations discussed earlier (Open, Close, TopHat). Figure 12 shows one of the subimages which will be used. Figure 13 shows the effect of the open operation, Figure 14 shows the effect of the close operation and Figure 15 shows the effect of the tophat operation.

Figure 12. Subimage to be used.

Figure 13. Result after opening the Figure 12.

Figure 14. Result after closing Figure 12.

Figure 15. Result after performing tophat on Figure 12.

Notice that in Figure 12, we see small unwanted white spots. These white spots are clearly not part of the circles. In performing the morphological operations, I used a structuring element in the shape of a circle with a radius of 10. In Figure 13, we see that the unwanted white part have disappeared after opening the image. In Figure 14, the image have been completely distorted and only a few white circles are observable. In Figure 15, the unwanted white sport have not disappeared and to make things worse, the white circles have disappeared and only the outline remains. It is clear what the better option for the operation to be used is here. The properly clean the image, we need to use the open operation.

Going back to isolating the cancer cells, we now have a method to clean the given image in Figure 11. For each subimage, after cleaning with the open operation, we searched for blobs or a group of white pixels enclosed by black pixels. We label each blob and extract their area in terms of number of pixels. We then plot the histogram of the number of blobs based on blob area. The histogram is shown in Figure 16.

Figure 16. Histogram of blob count based on blob area for Figure 11

We see that the histogram is high at values in between 300 pixels and 600 pixels. Areas below that will be too small to be considered as a “normal cell” while values above that will be considered as a clump of cells which will then be rejected because it cannot be of any help in the approximation of the area of a “normal cell”. We then get the mean area and its corresponding standard deviation of those blobs above 300 and below 600 pixels. These values will be used to find the “cancer cells” in Figure 10.

In Figure 10, we perform the same binarization process and clean the image using the same open operation but now with a structuring element in the shape of a circle of radius 13. We then searched the whole image for blobs and labelled each. The histogram for blob count using blob area is then plotted. Figure 17 shows the said histogram.

Figure 17. Histogram of blob count using blob area of Figure 10

After cleaning, only a few circles now remain. We notice that there are peaks less than 600. These peaks will resemble the area of the “normal cells”. A group of peaks are then observed above 800 pixels. This will resemble the area of the “cancer cells” thus when removing those blobs covered by the range (mean – standard deviation) to (mean + standard deviation) which are calculated earlier. Figure 18 shows the resulting image of the isolated “cancer cells”.

Figure 18. Isolated “cancer cells” in black and white

If we compare Figure 18 with Figure 10, we see that they match with the known observed “cancer cells”. This means that this process is effective in isolating shapes based on area.

For my above and beyond study, I will try to find a situation in which the tophat operation is used. I will take an image as shown in Figure 19. It shows a text with something that looks like a spilled ink.

Figure 19. Text with spilled ink. Retrieved from http://www.rnib.org.uk/sites/default/files/unclear_vision_0.jpg

My first step is to take the negative of the image and perform the tophat operation using a square structuring element with a side length of 6. Figure 20 shows the resulting image.

Figure 20. Result after performing tophat operation

We can now see that the color of the ink stain is now starting to merge with the background while the color of the text remain white (due to applying negative). From here, we can completely remove the stain by segmenting by threshold and the result is shown in Figure 21.

Figure 21. Resulting image after thresholding

Although the ink stain is gone, we now observe several unwanted white patches around the letters. To fix this, we return to Figure 20 and apply a limit to thresholding. We create a patch similar to that of Figure 22 and apply lower thresholding to where the patch is white. We apply higher thresholding to the rest. The resulting image will be shown in Figure 23.

Figure 22. Patch used to perform operations

Figure 23. Result after separate thresholding

To further enhance the image, we can use the earlier images (make use of black background) to arrive to a final enhance image shown in Figure 24. The image will then be reinverted to return to black text.

Figure 24. Final enhanced image

Review:

First of all, I would like to thank my classmate Ralph Aguinaldo for sharing ideas with me while figuring out how to perform this activity. I would also like to thank Maam Jing for the guidance and for confirming my results.

Secondly, I would like to say that this activity really exposed the artist (or non-artist) in me. This activity was fun but the above and beyond part really made me think hard. For that, I would like to give myself a grade of 12 for this activity.

References:

[1] http://docs.opencv.org/doc/tutorials/imgproc/opening_closing_hats/opening_closing_hats.html

[2] https://www.cs.auckland.ac.nz/courses/compsci773s1c/lectures/ImageProcessing-html/topic4.htm

Image Segmentation

Image segmentation is an important concept in Imaging. It sets a threshold to the image and binarize the image according to that threshold. Binarization is a process in which the colored image is converted to an image composed only of black and white pixels. For example, let us take the image in Figure 1.

Figure 1. Sample Image for segmentation

This image is composed of black ink (for the text) and light grayish paper (for the background). I want to binarize Figure 1 such that the text will be white and the background will be black. To do that, first I need to plot the histogram of pixel values. I used the function imhist() of Scilab with 256 bins. Figure 2 shows the histogram of pixel values for the image in Figure 1.

Figure 2. Histogram of pixel values for Figure 1

It is observed that there are so many pixels with values greater than 150 as compared to those less than it. In Figure 1, the background is also dominant so the pixels with values greater than 150 are the background pixels. Since I want the background to be black and the text to be white, I let a matrix BW = I < 125 (giving a small allowance to the threshold) with I being the image matrix. This will create a matrix BW with values T or F (True or False) with T be white and F be black. Figure 3 shows the binarized image of Figure 1.

Figure 3. Binarized image of Figure 1 with threshold value of 125

I can use the segmentation concept to isolate a certain color in colored images. Before proceeding to segmenting colored images, I will need to discuss a little bit about colored images. Per pixel in a colored image has a particular color and this color is a combination of the three primary colors: red, green and blue. Colored images will then have a separate channel for each color (R for red, G for green and B for blue). Before segmenting, the three channels of the image have to be converted to normalized chromaticity coordinates or NCC. To do this, I let:

Equations 1-4: Equations to be used to convert to NCC

The terms r (Equation 2) and g (Equation 3) will be the coordinates in the NCC. Note that I did not use the b value (Equation 4) because when I know r and g, I already know b because r + g + b = 1.

Now before calculating anything, I must choose a photo wherein there are many colors involved. I chose a photo of a Korean girl group in one of their music videos where they wear tracksuits of five different colors as seen in Figure 4.

Figure 4. Image to be segmented. Retrieved from Bar Bar Bar music video of Korean Girl Group Crayon Pop

I then choose a region of interest or ROI wherein I want to isolate that certain color. I chose the five different colors simultaneously to perform this activity faster.

Figure 5. a) Yellow b) Pink c) Orange d) Blue e) Red color patches used to segment based on color

I solved for the chromaticity coordinates r and g of each pixel on each color patch. I then took the mean and standard deviation values of r and g for each patch. These values are important to setup the Gaussian distribution for the probability of belongingness for each pixel on the original image. Using the equations 5 and 6 below, I will then solve for the probability of belongingness of each pixel on the original image.

Equations 5-7: Equations to solve for the probability of belongingness

I then solved for the belongingness probability for each pixel with the mean and standard deviation values that I calculated from the patches. Since there are values of P(r,g) that are greater than one, I normalized the probability function to only have values from 0 to 1. As of now, each pixel now has a belongingness probability value. I can use these values to perform the threshold segmentation. I tried different thresholds and Figure 6 shows the results of segmentation.

Figure 6. Segmented image of Figure 4 using the color yellow and with thresholds a) 0.1 b) 0.4 c) 0.7 d) 0.9

It is observed in Figure 6 that as the threshold increases, less white pixels are observed. It is expected because the binarization process is reliant on the value of the probability of belongingness. The higher its probability, the more chances it is to be white on the binarized form.

For the rest of the color patches, I only used a single threshold value of 0.4. Figure 7 shows the rest of the segmented images.

Figure 7. Segmented images of a) pink b) orange c) red d) blue color patches with a threshold of 0.4

The process shown above is called Parametric segmentation since it uses a Gaussian Probability Distribution Function as a threshold basis. There is another method of segmentation and this is called the Non-parametric segmentation. This type of segmentation uses the concept of histogram backprojection wherein the r and g values of the image pixels are compared to a 2D histogram of a certain color patch. The value of the image pixels are then changed depending on the value on the histogram.

To start with non-parametric segmentation, I will give a little discussion on 2D histograms. Given the values of r and g, I can predict the color of that pixel using the normalized chromaticity space like that in Figure 8.

Figure 8. Normalized rg Chromaticity Space

A 2D histogram is formed when the r and g values of each pixel on the original image is calculated. The plot of the NCC space (Figure 8) is divided into bins and be used as basis. Originally, each bin has a value of 0. Each time a pixel’s r and g values correspond to a certain bin, the value of that bin increases by 1. When all the pixels have now been incorporated to the histogram, the histogram is then normalized and binarized using a threshold. When the value of that bin exceeds the set threshold, it will be given a value of 1 (white) and 0 (black) otherwise. The histograms are created using the color patches seen in Figure 5. The histograms generated are shown in Figure 9.

Figure 9. Binarized histograms of the a) yellow b) pink c) orange d) blue e) red color patches

If I compare these histograms with the NCC space in Figure 8, I can see that the white spots are located in the proper color location. After checking, I can proceed to the next step which is histogram backprojection. The pixels of the original image will become white when the histogram values of the corresponding r and g values of the pixels are 1. When the histogram values are zero, the pixel is changed to black. This will then be segmented based on the color of the patch. The resultant image of the non-parametric segmentation is shown in Figure 10. The threshold used for all of the images will be 0.4 (same threshold as that I used in parametric segmentation).

Figure 10. Segmented images with a)pink b) orange c) red d) blue e) yellow color patches and using non-parametric segmentation with a threshold value of 0.4

When comparing the results of the parametric (Figure 7) and non-parametric (Figure 10) segmentation, I noticed that, with the same threshold, parameteric segmentation has a clearer image of the isolated color than non-parametric segmentation. The reason for this is that many information are lost when the histogram is being binarized in the non-parametric segmentation. Also, due to the Gaussian PDF of the parametric segmentation, a large scale of pixels will be involved.

The difference in runtime is in favor of parametric segmentation. This is not what is expected but because of the capability of Scilab to perform parallel computations within matrices, this made the difference. In non-parametric segmentation, a histogram must be setup and values are compared and this caused the delay while in parametric segmentation, values are calculated simultaneously and is just thresholded.

In this activity, I will explore above and beyond by tackling on the topic on choosing color patches. For the color patches shown in Figure 5, they are all of the same saturation (no dark nor light versions of the same hue). One of the reasons why not the whole clothes were segmented above is that they did not reach the threshold. If I do not want to change the threshold, I can  just change the color patch itself. Let us take for example the image of the sky in Figure 11.

Figure 11. Image of the sky

I want to segment the image such that the sky will turn white (while all the rest are black) while having a constant threshold of 0.1. If I pick a patch like that shown in Figure 12, we can expect that most of the sky will be blacked out. The result of this color segmentation is shown in Figure 13.

Figure 12. Color patch selected

Figure 13. Segmented image using the color patch in Figure 12

I notice that only the upper parts are whited out. If I choose another patch like that shown in Figure 14, we can expect another bad segmentation. The resultant image will be shown in Figure 15.

Figure 14. Color patch selected

Figure 15. Segmented image using the color patch in Figure 14

Now the lower parts are white but the higher parts are black. If I change the color patch such that a wide range of color saturation are observed, we can expect much better results. Figure 16 shows the patch with a wide range of saturation and Figure 17 shows the segmented image.

Figure 16. Color patch selected

Figure 17. Segmented image using the patch in Figure 16

This happens because a wide range of color saturation will bring the mean to the real average of all the blue pixels. The standard deviation also increases greatly thus leading to a larger Gaussian PDF. This means that more pixels will then be included even though the threshold is at a strict 0.1. Although it may not be perfect, the point here is to show how choosing the right patch can also be a way to perform better segmentation.

Review:

To think about it, this activity was given only six days to make and I finished the programming part after two days. This means that I went “in the zone” because this activity is so awesome. For this activity, I would congratulate myself for all the effort I put here. Also, I really understood the topic very well. Since it’s alerady October and Christmas is coming fast, I will give my self a Christmas-themed score: 12! Because…