Application of Binary Operations 1: Blob Analaysis

Here we go again. Time really flies. We're now down to our 11th activity! It seems like yesterday that I was exploring the syntax and functions used in Scilab. This time, we are more equipped with the knowledge and programming skills to deal with more challenging problems. Our topic this time is blob analysis which integrates all the lessons we have learned from the past. In segmenting an image, we often find the suitable region of interest (ROI) and apply thresholding or color image segmentation. Sometimes, the image that we have an overlap in the graylevel histogram of the ROI and the background[1]. In cases like this, the binarized image has to be further cleaned using morphological operations such as opening or closing to be able to separate the region of interest from the unwanted parts that was segmented. Now, you may be wondering what are opening and closing operations. If you have read my previous blog regarding morphological operations, you must be knowledgeable on erosion and dilation. Opening is often done to preserve foreground regions that are similar to the chosen structuring element[2]. It is done by performing erosion and then followed by dilation. Thus, opening is not as destructive as erosion, and is used if the main goal is to remove unwanted dirt in the segmented image.

The aim is to apply binary operations to be able to analyze blobs of a given cell sample. The sample cell image is shown in the figure below.

Figure 1. Normal cell sample (left) and the image subject to be analyzed (right)

The first task is to separate the cell sample image into a number of 256x256 pixels of subimages, and to get the correct threshold from the its histogram that would separate the image from the background. I generated the histogram for the whole image using Scilab this is shown in the next figure.

Figure 2. Histogram of the Cell Sample and the thresholded image

The image shows a bimodal histogram which dictates that the most number of counts corresponds to the background. From this, we can extract the correct threshold that should be used  if we aim to binarized the image and separate the region of interests (cells) from the gray background. For the whole image, I used 222 as the threshold. I also tried using 215 as the threshold value and compared the results with the first. 

Figure 3. Result of thresholding the image at 222 and 215

Notice that the resulting thresholded images shows some irregular shapes. Thus, we use morphological operations to "clean" the image so that the image left is that of regularly sized circular shapes. I used the opening operation since my aim here is to remove the dirt outside  region of interests. The structuring element that I used is a circle with a radius of 11 units. The result of applying morphological operations and filtering by size is shown in the following image.

Figure 4. Filtered image using Morphological Operation (Opening)

The use of two different threshold affects the resulting image after applying the opening operator significantly. Since we want to determine the average size of each cell and obtain a standard deviation that would give us the best estimates of the normal cell size, I obtained the pixel area of each blob in the image and obtained the histogram of the all the area. This is shown in the following figure.

Figure 5. Histogram of the area computed for each blob in the filtered image

In this histogram, we can obtain the majority pixel area of the blobs. Those that are greater than 600 corresponds to the area of the cells that are overlapping. We can thus exclude these and use filter by size using the correct interval of area. Using the information from the above histogram, I was able to separate those normal cells that are not interconnected. Using these, I calculated the best estimates of their size and obtained the same value for the 222 threshold and 215 threshold. The best estimate, same for both, is 474.03448+- 50.314357 pixels. The picture below are the resulting individual blobs for each threshold used.

Figure 6. Filtered individual blobs using the histogram of the area count

We can now use the best estimate we obtained in separating the abnormally large cancer cells in the next image.

Figure 7. Applying the best estimate for a normal sized cell

Finally, using a larger structuring element and the inspection of the histogram of the area count of all continuous blobs, I was able to separate the abnormally sized cells. The image is shown below:

Figure 8. Abnormally large cells separated from the rest of the normal cells

In this activity, I give myself a grade of 10/10 for all that is required and being able to determine the effect of changing the threshold and radius of structuring element. 

[1] Maricor Soriano. Activity 11 Manual Application of Binary Operations 1: Blob Analaysis

Morphological Operations

I must say that this activity is quite engaging since it actually requires us to draw on hand. Well to give you the gist, we were assigned to predict and observe the output of performing morphological operations to certain images by both hand-drawn and numerically. These two methods are then compared and the result of our imaginations (hand-drawn images) are verified.

Morphological operations are often used as pre or post-processing tool in image processing. It is applied to binary images and are used to either for thinning, filtering or pruning. It is also used to get a representation of the shape of an object  or regions such as boundaries, skeletons, convex hulls and the likes.

The two principal methods of the morphological operation are the erosion and dilation. Erosion basically shrinks the objects into smaller dimensions by eroding some components at the boundaries. Dilation, on the other hand, performs the opposite. It expands the object by filling in holes and connecting the disjoint objects. The extent to which the objects are shrank or expanded are dependent on the structuring element used. Structuring elements can be of any shape.

Mathematically, the dilation of A by B is defined as [1]:

where B is the structuring element. It is illustrated by the following figure:

Figure 1. Dilation of A by B obtained from [1]

Meanwhile, erosion is mathematically defined by the following operator [1]:

where B is again the structuring element. The illustration of erosion is shown in the figure below.

Figure 2. Erosion of A by B obtained from [1]

Notice from figure 1 and 2 that the effect of structuring element to A and B are to elongate and to shrink respectively. Given different figures (A) and structuring elements (B), we are tasked to perform morphological operations erosion and dilation. A picture of my hand-drawn result is shown below:

Figure 3. Hand-drawn result of the morphological operation erosion and dilation

Note that the blank areas (erosion part) corresponds to absence of the object itself. This means that it is possible that the object will be annihilated by the structuring element when performing erosion.

Let's now compare the result of the morphological operation performed using Scilab. The erosion and dilation results for the 5 by 5 square is shown in the following figure where the structuring elements are the blue colored ones.

Figure 4. Inverted result of the morphological operation performed on a 5x5 square and a cross using Scilab

Since in Scilab, the value equal to 1 is white and 0 is black, the result shown in figure 4 is inverted for easier matching to my hand-drawn predictions. Additional results are shown in Figure 5.

Figure 5. Inverted result of the morphological operation applied on a hollow square and a triangle using Scilab

Comparing my hand-drawn predictions to the actual results, we could observe a few mistakes. I apologize for those mistakes, I must have been really in a hurry when I did it. For this activity, I give myself a grade of 10/10 for doing all the required task.

[1] Maricor Soriano. Morphological Operation activity Manual

[2] Morphological Operations on Binary images from http://users.utcluj.ro/~raluca/ip_2013/ipl_07e.pdf

Enhancement in the Frequency Domain

It's been so long since the last time I have posted my results here. I figured out it's rather more difficult to write about a certain topic that is long overdue because the idea and the hype about it is not that  fresh anymore. Anyway, the idea here is to enhance an image using the frequency domain. If we are given an image with unwanted repetitive patterns and we want to remove them, the straightforward thing to do is to create filter masks that will block the unwanted frequencies. The key points behind this are the idea of the convolution theorem, and these are the following [1]:

1. The Fourier Transform of a convolution of two functions in space is just the product of their Fourier transforms. That is, 

2. The convolution of a dirac delta function and a particular function is the replication of that function to the location of the dirac delta. That is,

So to start with, I obtained the fourier transform of an image with two points separated and symmetric about the y-axis and the result is a sinusoid as shown in the following figure.

Figure 1. FT of two dots (one pixel each) separated and symmetrical to the y-axis

Suppose we increase the number of pixels and create a circular pattern of a certain radius r and the Fourier transform is applied, we should get the following result for different radius.

Figure 2. Increasing radius and their corresponding FT

As you increase the radius, the size of the airy pattern formed decreases. The FT of the circle with radius 1 appear almost the same as that of Figure 1, only the shade shows some curvature at the sides. This is because the resulting image is the product of the airy pattern and the sinusoid. The FT of the two dots is just the sinusoid alone. 

As for the FT of the two square symmetric at the center, the FT should be the product of the sinc function and the sinusoid. The increase in the width of the square resulted to the decrease in size of the pattern formed.

Figure 3. Increasing width of the square and their corresponding FT

Meanwhile, the same pattern is observed when the squares are replaced with a gaussian pattern. The effect of the increase in variance is shown in Figure 4. The same with the symmetrical squares and circles, the FT of the two symmetrical gaussian is a combination of the FT of gaussian and a sinusoid. Since the FT of a gaussian is also a gaussian of different form (different parameters), the result shows an image of another gaussian pattern with a sinusoid pattern. The increase in the variance results to the increase in size of the gaussian image, and consequently the decrease in the size of the corresponding FT.

Figure 4. FT of two symmetric gaussian about the center with increasing variance

To evaluate the effect of idea number 2 of the convolution theorem, I created 10 dots placed randomly on an array of zeros. These represents the dirac delta functions. I also created different patterns of stars of different sizes. Then, I took the convolution of the two functions and obtained the following result.

Figure 5. top: pattern convolved with the randomly placed dirac delta and their (bottom) corresponding results

As stated from number 2 above, the pattern was replicated to the locations of all the dirac delta functions. For the case of the last column in Figure 5, the pattern was too big, so the result is an overlapping images of the same pattern.

Now, let's go to the actual application of these concepts. Given an image of the craters of the moon from the NASA Lunar Orbiter, the goal is to remove the horizontal lines observed in the image. 

Figure 5. Image of the crater of the moon 

The only instruction we were given was "Remove the horizontal lines in the image by filtering in the Fourier Domain" so this part of the activity is much more challenging than the rest. The first thought that entered my mind when I saw the horizontal lines in the image is the fourier transform of a number dots symmetrical at the center. 

Figure 6. Enhanced Image of the crater of the moon

Another task is to remove the noise of the following image of a house. 

Figure Subject image

In this image, no pattern can be easily observed. Thus, we have to observe its fourier transform. I created a mask by thresholding the FT of the image and converting it to binary. The result is the following image.

Resulting enhanced image

 I couldn't have done this last part without the help of Eric who guided me in performing these image enhancement. Kudos to Eric for patiently helping me! :)

I give myself a grade of 10/10 in this activity for being able to do all the assigned task.

Color Image Segmentation

Finally! The topic that I have been aching to learn since I started doing  my research problem. Haha. The truth is, I've already tried learning this on my own since the summer of 2013. I had to present meaningful results to my advisers at the time and I found out that color segmentation is one of the topics taught in AP186. I was actually ranting why it has to be taken during the fifth year and not earlier. Well, that of course, is the selfish side of me talking. I knew there was a reason why it had to be taught on our last year.

My research is on the dynamics of granular collapse. The final configurations and the topology of the flow of granular particles are my main concerns. For that reason, I have to find the final position of all the particles resulting from the collapse of a granular column. In order for me to fully visualize and understand their dynamics, I had the grains color-coded and layered into three, both vertically and horizontally. An example of my raw data (compressed) is shown below:

Figure 1. Raw shots from my experiment on granular collapse

As can be observed from the pictures above, the red and yellow grains appear more apparent than the blue ones. My problem lies with the fact that the blue grains camouflage with the background. When I did the experiment, my initial plan was to make the background white or green. However, I have another experiment involving starch (colored white) which uses the same setup, so a white background was not a good option. My other experiment also involve the use of yellow green grains so a green background was not a good option either. I had to settle to black because it was the only color available at the time too.

Anyways, enough with my rants and stories. Let's get back to the main topic of this blog post -- the color segmentation. From the root word alone, segment, defined by the thefreedictionary.com as "to divide or become divided into segments", image segmentation is the partitioning of a digital image into smaller regions and separating a certain region of interest (ROI). There a number of processes in which one can segment an image. The simplest example of this is thresholding method where the desired regions of a certain image is characterized by particular gray-level value. The cut-off graylevel value is then chosen and pixel values not belonging to the corresponding chosen range of graylevel values are considered 0, otherwise, it's 1. Thus, thresholding converts a grayscale image to binary. This process is considered to be the simplest because it's very straightforward to perform especially if the image involve consists of a bimodal histogram wherein the foreground and the background can be easily separated.

If however, we are faced with images that include shading variations (for example: 3D objects), it is best to perform other methods that can separate the pure chromaticity information from brightness. In an RGB image, each pixel has a corresponding value for red, blue and green. If we then let I be equal to the sum of the values R, G, and B, then the normalized chromaticity coordinates are:

(NCC)

Thus, 1 = r +g+b so that the normalized blue coordinate would just be:

We can just therefore represent the chromaticity using two coordinates which are the r and g. We note that the brightness information is stored in the I value. Since we are now dealing with the normalized chromaticity coordinates, we were able to reduce the color information from 3-dimensions (RGB) to 2-dimensions (rgI) where I is just equal to unity. The normalized chromaticity space is shown in the following figure, where the y-axis and the x-axis corresponds to the r and g values, respectively.

Figure 2. Normalized chromaticity space

From the chromaticity space, a red colored pixel is therefore at the lower right corner with values (1, 0), and the value (0,0) corresponds to a pure blue pixel since b = 1-0-0 = 1. One can also notice that the white pixel value appears at the coordinate  (0.33, 0.33), so that the r, g and b, all have the same value.

We now proceed to the discussion of the different methods of segmentation based on color -- parametric and nonparametric. In performing these methods, one begin by choosing and cropping a region of interest  (ROI) from their image. In parametric segmentation, the color histogram of the chosen ROI is normalized to obtain the probability distribution function of the color. This PDF would then serve as the basis in determining if a certain pixel in the image belongs to the region of interest. A joint probability p(r)p(g) for green and red coordinates corresponds to the likelihood of a pixel belonging to the ROI where p(r) is given by the following equation:

In the above equation, we assume a Gaussian distribution independently along r and g values. The mean and standard deviations are therefore calculated first from the chosen ROI for both the red and green values. The same equation is computed for the green values.  This method was performed in the image below and the result is displayed along with it.

Figure 3. A copy of the original image obtained from [2]

Figure 4. Parametric segmentation of the image from figure 3

Since the probability distribution function of the color is dependent on the chosen ROI, it is safe to assume that the precision of the segmentation is dependent on the number of pixels present in the ROI. If say we increase the number of pixels in the ROI, there is a greater chance that a higher variety of shade will be present in the ROI and the standard deviation would be higher. Consequently, the probability of a random pixel to belong to the ROI would also increase. If however, there is uniformity in the chosen ROI even though you increase the number of pixels (that is, if no increase in standard dev), no difference should be observed. This can be best explained by the following results.

Figure 5. Effect of reducing the number of pixels included in the ROI

Notice that the decrease in the ROI resulted to the loss of some of the segmented images that appears when the bigger ROI is used. However, not all part of the concerned sections (red colored paint, bottom image)  are not completely filled as compared to the result bigger ROI. 

Another method of segmenting a colored image is by obtaining the 2D histogram of the region of interest and from it, the pixel is tagged whether or not it belongs to the obtained histogram. The 2D histogram of the red ROI is shown below.

'

Figure 6. 2D histogram of the region of interest

We then employ the method of histogram backprojection wherein a pixel location at the original image is given a certain value corresponding to its histogram value. Supposed a pixel colored blue appears at (0,0), then its corresponding value would be 0 since at (0,0), the 2D histogram is 0. The result of the nonparametric segmentation is shown in the following figure.

Figure 7. Nonparametric segmentation of the image from figure 3

The effect of increasing the number of pixels of an ROI for the nonparametric segmentation is also shown in the next figure. 

Figure 8. Effect of reducing the number of pixels included in the ROI for nonparametric (reduce patch size)

It is intuitive that if we decrease the patch size that we use as ROI, some shades would also be removed from the histogram. This is apparent in Figure 8.

If we now compare the result of the nonparametric to the parametric segmentation, we can easily say that the nonparametric segmentation shows a more accurate result. 

In conclusion, I would like to say that the key in segmentation is to find the right size and area for the ROI. I've learned this because I have used different sizes of ROI in my research. An ROI that is too big would include other unnecessary sections, while a very small ROI would exclude those that are supposed to be included. 

For this activity, I give myself a grade of 12/10 for exploring the parameters that could further affect the result.

[1] Maricor Soriano, Color Image Segmentation Activity Manual
[2] Color Oil paints in opened paint buckets from http://www.flashcoo.com/cartoon/colorful_objects_and_designs/Colorful_oil_paints_Opened_paint_bucket.html on August 10, 2013