The Finished Article

Final Version

Title:      Cell Segmentation

Module:  Image Processing - DT021A/4 - Dublin Institute of Technology   

Author:   Safiah Sadeq, Christopher Byrne and James Lowe

Date:       19/04/2018

The final version of the code may be found here. 

Procedure

First an image of a group of cells is read into the program. A denoising filter is used to smooth out the original image to remove areas of noise. A binary mask is created which outlines what is a cell and what is not a cell. With the areas that are a cell having a value of 255 and background having a value of 0. A watershed algorithm is applied using that mask and the original image which outlines the boundary of all the cells in the image. The user is shown the original image with a set of instructions "Left Click to Segment -- Right Click to Return to Original Image". When the user left clicks on a cell the coordinates of the that mouse click is taken. The coordinates are then used in the watershed algorithm mask to fill from those coordinates to the boundary of the cell. This creates a mask that masks everything but the cell that the user selected and the outline of each of the other cells. This mask  is then applied to the original image and will display the cell and the outline of each other cell. The user can right click to return to the original image or left click on a  different cell to segment that cell. The user may also press escape to exit.

Pseudo code 

....... START

....... ( Read in image )

....... ( Display image )

....... ( Filter image using denoising filter )

....... ( Create mask of cells )

....... ( Apply watershed to get borders )

....... ( While escape is not pressed)

   ....... ( If right mouse button pressed down )

....... ( segment the cell selected )

        ....... ( If left mouse button pressed down )

....... ( Display original image )

....... ( If escape is pressed )

....... ( Close while loop )

....... END

Final Results

The final code is made up 4 functions and are described be:

1. Display(displayImage)

Function:

Display - Displays image with border and instructions     

Pseudo code:        

....... ( Create border around the image )

....... ( Place white text on top border )

....... ( Show image with border  )     

Calls:

none

Called by:

Main , Segment()

Input Parameters: 

displayImage Returns:

none

Figure 1. Displayed Image

2. FilterAndMask(img)

Function:

FilterAndMask - Filters image and creates a mask       

Pseudocode:

....... ( Convert image to greyscale )

....... ( Apply denoising filter) 

....... ( Create mask by thresholding )

....... ( Invert mask  )

....... ( Return mask  )

Calls:

none

Called by:

Main  

Input Parameters:

img

Returns:         

binaryInvert

Figure 2. bineryinvert - mask showing what is cell and what is not after the function filterandmask

3. Watershed(mask,img)

Function:
Watershed - Finds the borders of the cells              

Pseudocode:
....... ( Find definite background area (ie. not a cell) )
....... ( Find definite foreground area (ie. is a cell) )
....... ( Find the unknown area (not sure if cell or background)
....... ( label markers for foreground )
....... ( Apply watershed )
....... ( Set the boundary colour to blue )

Calls:
none

Called by:
Main

Input Parameters:
mask, img

Returns:
watershedimg

Figure 3. watershed 

4. Segment (mask,img)

Function:

Segment - Segments cell from background and other cells           

Pseudocode:

....... ( if left mouse button is pressed down: )

     ....... ( Take blue component of watershed image

and apply binary threshold leaving only boundary )

     ....... ( make copy of binary threshold image )

     ....... ( Using the coordinates of the mouse click fill from that area on the boundary mask until                        boundary is reached leaving a mask with cell of interest and boundaries of the other cells.         ....... ( Apply mask to original image )

     ....... ( Display resulting image )

     ....... ( set pixels in mask to 255 so it can be reused )

....... ( if right mouse button is pressed down: )    

     ....... ( Display original image)

Calls:

Display()

Called by:

Main

Input Parameters: 

event , x , y , flags , param , watershedImg , mask

Returns:

none

Figure 5. Mask after floodfill

Figure 6. Image after applying mask to original image

Final Implementation 

The user is greeted with the image below in figure x

Figure 7. UI initial state

When the user selects a particular cell, that cell is then isolated along with the borders of every other cell so the user knows where to click to view another cell. The figures below show a couple of different cells that are selected.  

Figure 8. UI after sell selection 1

Figure 9. UI after sell selection 2

Figure 10. UI after sell selection 1

When the user right clicks on the image after selecting a cell the original image reappears and segmentation can be done again by left clicking on a cell. The user can leave the program by pressing the escape key.

Problems Encountered

Many issues where faced on the road to a working program. The main problems occurred within the thresholding and filtering aspects of the project. This was dealt with mainly by my colleague. The problem was that holes kept on appearing in the cells which where solved by improving thresholding. This issue can be seen in the version 1 blog post.

Similar Images 

My colleague worked on applying different images to the code and changing threshold values and here are the following results:

Figure 11. Similar image test

Figure 12. Similar image segmentation 1

Figure 13. Similar image segmentation 2

Figure 14. Similar image segmentation 3

Version 1 - Segmenting cells

Version 1 - Segmenting cells

This post will look at the segmentation of a cell that has been selected by the user. The code for the following results can be seen here. As this is a group project my task is to implement this aspect of the project. Other members of my group are currently working on creating an efficient filter to accurately remove noise and creating a threshold that will identify the cell from non cells accurately. For this reason I have implemented a vary basic filter that will do the bare minimum so that the user selected segmentation code can be written.

1. Removing noise

The first step is to use a threshold and noise removal. I wont be going into much detail about thresholding and noise removal as a better version is being worked on by other members of the group. The noise removal on this blog is used to allow the segmentation aspect of the project possible. The threshold uses Otsu binarization with the threshold value set to 200 and is applied to the grey-scale cervical image.  The threshold mask can be seen in Figure 1. [1]

Figure 1 - Threshold created of cervical image 

This threshold mask is then used to create a smoother mask with more defined edges using the morphology functions. Figure 2 shows the mask for noise removal.

Figure 2 - Mask after morphology

2. Watershed Algorithm 

The Watershed algorithm has 3 main key components (labels or markers), identifying the foreground, background and unknown areas. These markers are important as it allows the watershed algorithm to achieve its goal while not being over-segmented. The background area is done so by using dilating the mask created after morphology. This is done using the following function.

# Background area

background = cv2.dilate(opening,kernel,iterations=2) [1]

This dilate function takes in the mask and expands the edges of the region of interests. This will result in the following mask output in Figure 3. 

Figure 3 - Background mask 

Finding the foreground does the opposite and shrinks the borders of the mask. This is done using the following functions. The result of which can be seen in Figure 5. 

# Foreground area

dist_transform = cv2.distanceTransform(opening,cv2.DIST_L2,5)

ret, foreground =       cv2.threshold(dist_transform,0.05*dist_transform.max(),255,0) [1]

Figure 5 - Foreground mask

The unknown region is that of which could have a chance of being in either the foreground or the background. It is found by subtracting the two from each other. The areas of which white pixels are in both images are left behind and everything else turns black. The result can be seen in Figure 6.

# Unknown region

foreground = np.uint8(foreground )

unknown = cv2.subtract(background,foreground ) [1]

Figure 6 - Unknown Mask

The next step is to take the foreground mask and use the function cv2.connectedComponents function which computes the connected components labeled image of the Boolean image [2]. This is used to create the marker label using the foreground mask. One is then added to ensure that the background is not 0, but 1. The unknown region is then set to 0 as it could be either in the foreground or the background. The watershed algorithm is then applied to the image which sets the borders of the cells to -1 and everything else from the original image stays at it was. The code for the watershed algorithm can be found below and the resulting image in Figure 7.

# Marker labell
ret, markers = cv2.connectedComponents(foreground)

# Add one to all labels so that sure background is not 0, but 1
markers = markers+1

# Now, mark the region of unknown with zero
markers[unknown==255] = 0 [1]

#Apply watershed algorithm 
markers = cv2.watershed(img,markers)

#Where value = -1 set value to blue
img[markers == -1] = [255,0,0]

Figure 7 - Image after watershed with defined edges

The one problem with this image is the enclaves within the cells (like the way the Vatican is an enclave of Italy) . We don't want this as it will create holes in the final image of the cells. This can be fixed with better filtering to be done by other members of the group. The reason why the edges are blue and not white or black will be shown in the next part.

3. User select

The next step is to use the image created by the watershed algorithm to generate a mask that will allow the user to select the cell of interest. This is done by first splitting the the image from Figure 7 into its individual components B G and R. then using a binary threshold a mask can be created turning everything that's blue to white and everything else will turn black. The code is below with the result in Figure 8. Note that it looks in the image that there are gaps in some sections of the white line. This is not actually the case and it only looks that way when I uploaded it to the blog. They are actually continuous (Take my word for it). 

#Split image colors 

blue, green, red = cv2.split(img)

#Create binary mask of edges 

ret,B = cv2.threshold(blue,254,255,cv2.THRESH_BINARY)

Figure 8. Binary Mask of edges

This is the mask that will be used in conjunction with the original image to allow the user to isolate cells or clumps of cells. The next step is to hand over control to the user. The first step is to display the image and allow the users mouse to have access to the image. In the mouse function it references a function called SEGMENT. This is the function that will be discussed shortly with all the necessary bits and bobs to isolate a particular cell. 

cv2.setMouseCallback('Cervical',SEGMENT)

cv2.namedWindow('Cervical',600)

cv2.imshow('Cervical',img)

For good measure the window size is lowered also as the image is quite large and using the imshow function on its own would have parts of the image cut off the screen. Figure 9 shows what the user will be greeted with when the program runs. No surprises here it is the original image cervical.jpg.

Figure 9 - cervical.jpg will greet the user

The next step is to set up a while loop that will wait for a user input. This is done with the following code

while(1):

    

    if cv2.waitKey(20) & 0xFF == 27:

        break

cv2.destroyAllWindows()

The loop allows for the function SEGMENT to be called. It will also close the window when the escape key is pressed. The Segment function can be seen below. What it does is it waits for the user to left click on a point of the screen. That point that is selected is then stored as an x , y coordinate value. That value if in a cell then takes the mask generated earlier and uses the x,y coordinates to fill from the x,y point out to the boundary around that point creating a new mask with the cell of interest completely white (Figure 10) . This is like using the bucket in Microsoft paint . This Mask is then applied to the image from figure 7 leaving only the cell and the blue boundaries (Figure 11). Then by changing all solid blue and black pixels to white leaves the cell isolated from everything else on a white background (Figure 12). Note: there are some messing around with the borders of the images in this function as this is required to enable  cv2.floodfill.

def SEGMENT(event,x,y,flags,param): 

if event == cv2.EVENT_LBUTTONDOWN: 

h, w = B.shape[:2]

mask = np.zeros((h+2, w+2), np.uint8)

                cv2.floodFill(B, mask, (x,y), 255);

constant = cv2.copyMakeBorder(img,2,2,2,2,                                        cv2.BORDER_CONSTANT,(0,0,0))

img1_bg = cv2.bitwise_and(img,img,mask = B)

img1_bg[np.where((img1_bg == [255,0,0]).all(axis                                                  = 2))] = [255,255,255]

img1_bg[np.where((img1_bg == [0,0,0]).all(axis =                                                    2))] = [255,255,255]

cv2.imshow('Cervical',img1_bg)

Figure 10 - cell mask with cell boundries

Figure 11 - cell after masking 

Figure 12 - Isolated cell

Conclusion and improvements for next version

The segmentation works only on ideal cells. some cells have holes in them due to poor noise removal which needs to be enhanced. If the background is selected the background will show and all the cells are left white. This is also not ideal. The finished design will also crop the image removing the majority of white space. also not to segment out the area where the blue line lies on as it is also part of the cell.

References

[1] Docs.opencv.org. (2018). OpenCV: Image Segmentation with Watershed Algorithm. [online] Available at: https://docs.opencv.org/3.1.0/d3/db4/tutorial_py_watershed.html [Accessed 1 Mar. 2018].

[2] Docs.opencv.org. (2018). OpenCV: Structural Analysis and Shape Descriptors. [online] Available at: https://docs.opencv.org/3.1.0/d3/dc0/group__imgproc__shape.html#gac2718a64ade63475425558aa669a943a [Accessed 1 Mar. 2018].

Project Plan and Research

This is a rough plan before any code is written, it is a plan and we all know in life plans can change. 

The objective of our project is to Isolate (by masking) the cell identified by a user's mouse click in the sample shown on the previous blog entry.This can be broken down into 4 key steps.

1. Load image
2. Identifying cells
3. Watershed Algorithm 
4. Cell selection

1. Load Image

The first step is to load the image that we are wish to work with. for this project we will use cervical.jpg. But going forward we will design the code in a way that will allow other similar images to be used. Loading the image is probably the easiest step of this project as it is required in every image processing task that myself and other members of my team have done to date. This is simply done by using the line:

 I = cv2.imread("cervical.jpg")

The openCV function imread loads an image from the specified file and stores it as an array I . To display I we use the function:

cv2.imshow("image", I) 

This will take the array I and display it in a window.

2. Identifying cells

When the image is displayed in the window the next step is to identify what is a cell and what isn't and show the individual cells. This can be done automatically when the image is displayed or add an extra piece of code so that the user has to prompt the identification of cells. This can be achieved by displaying the image with a prompt that could say "Press I to locate cells" the program waits for the user to enter the letter I and  then the cells will be identified with a colored line around them. But how will the cells be identified?

When something needs to be identified from an image the easiest way is looking at the characteristics of what is being identified with respect to everything else in that image. This could mean a specific color range/shape, then isolating that from everything else in the image. Then the next step is to separate the larger clumps of cells to identify individual cells.     

The cells can be identified by a process called isolation by way of masking. The first step is to identify what is a cell and what isn't. This is done by creating a mask. A mask is a filter that can be used to separate a region of interest from a region of insignificance. Masks are used for edge detection but are also used for a wide range of other applications.

The mask is generated by applying a threshold to the image there are two main thresholding techniques , Simple thresholding and Adaptive thresholding. other thresholding techniques do exist and may be looked into later which include Otsu thresholding. First the image is converted to grey-scale then the threshold is applied. 

Simple thresholding:"If pixel value is greater than a threshold value, it is assigned one value (may be white), else it is assigned another value (may be black) [1]". 

retval, dst=cv.threshold(src, thresh, maxval, type[, dst])

The different types of of simple thresholding are:

• cv.THRESH_BINARY
• cv.THRESH_BINARY_INV
• cv.THRESH_TRUNC
• cv.THRESH_TOZERO
• cv.THRESH_TOZERO_IN

Adaptive thresholding: "In this, the algorithm calculate the threshold for a small regions of the image. So we get different thresholds for different regions of the same image and it gives us better results for images with varying illumination [1]".

dst = cv.adaptiveThreshold( src, maxValue, adaptiveMethod, thresholdType, blockSize, C[, dst]

The different types of of adaptive thresholding are:

• cv.ADAPTIVE_THRESH_MEAN_C : 
• cv.ADAPTIVE_THRESH_GAUSSIAN_C : 

In an ideal world once the appropriate thresholds are set (which could be either simple/adaptive or a mixture of both or by other methods) the mask is a perfect representation of the region of interest. This however is hardly ever the case with real world images. therefore it is likely that the mask will contain some amount of noise. This can be resolved in a couple of different ways by smoothing the image before applying the threshold or using morphological transformations .

Smoothing images can be achieved with convolution and image blurring (average, Gaussian, Median or bilateral filtering) the image. Whereas morphological transformations include such techniques as Erosion, Dilation, Opening, Closing etc of the mask. I feel that the morphological technique of Opening is the most appropriate for this application. "Opening is just another name of erosion followed by dilation. It is useful in removing noise [2]".  By Eroding the image which will reduce the boundaries of foreground object removing small amounts of noise completely and then applying dilation which will increase the boundaries of foreground again in theory should remove a large amount of noise. This can be used in conjunction with some of the convolution techniques could result in a noise free mask.

The mask may then be applied to the image which will show only the region of interest (ie. the cells)  

3. Watershed Algorithm [3]

Next we need to identify individual cells this can be done by applying a watershed algorithm.  Any grey-scale image can be seen as a topographic surface. for those who haven't taken geography in school a topographic surface is a surface with peaks, troughs, hills and valleys. The peaks and hills denotes the high intensity parts of the grey scale  image and the troughs and valleys denote the low intensity parts. The watershed algorithm applies a flood to the topographic surface which will denote the cell boundries.

The idea is to fill isolated valleys with different colored water. The valleys in this case are known as local minima which is the lowest intensity areas of the grey-scale image. The different color water areas are known as labels. applying the watershed starts the flood and as the water rises different color waters will begin to merge. To avoid this from happening barriers are added where the water tries to merge. barriers are continuously put up as the water tries to merge in different areas until the last peak is under water. 

The resulting barriers give the segmentation result. This however tends to give a over-segmented result due to noise and other regularities. This should be minimal in the case of our program as we will have performed a lot of the noise removal in the last step. However as an added step to remove any additional noise OpenCV have implemented an interactive marker-based watershed algorithm. different labels are given for our object. The following labels are given:

• Region which we are sure of being the foreground or object with one color (or intensity)
• Region which we are sure of being the background or or non-object with another colour
• Region which we are not sure of anything is labeled with 0.

The watershed algorithm is then applied. The marker will be updated with the lables that have been given and the boundaries of the objects will have a value of -1.  

The following code is an example of a watershed algorithm identifying the borders of coins

import numpy as np
import cv2
from matplotlib import pyplot as plt

img = cv2.imread('coins.png')
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
ret, thresh = cv2.threshold(gray,0,255,cv2.THRESH_BINARY_INV+cv2.THRESH_OTSU)

# noise removal

kernel = np.ones((3,3),np.uint8)
opening = cv2.morphologyEx(thresh,cv2.MORPH_OPEN,kernel, iterations = 2)

# sure background area
sure_bg = cv2.dilate(opening,kernel,iterations=3)

# Finding sure foreground area
dist_transform = cv2.distanceTransform(opening,cv2.DIST_L2,5)
ret, sure_fg = cv2.threshold(dist_transform,0.7*dist_transform.max(),255,0)

# Finding unknown region
sure_fg = np.uint8(sure_fg)
unknown = cv2.subtract(sure_bg,sure_fg)

# Marker labelling

ret, markers = cv2.connectedComponents(sure_fg)

# Add one to all labels so that sure background is not 0, but 1
markers = markers+1

# Now, mark the region of unknown with zero
markers[unknown==255] = 0

markers = cv2.watershed(img,markers)

img[markers == -1] = [255,0,0]

Original Image

Marker Image after segmentation and Image after watershed algorithm

4. Cell selection

Once each of the cells are clear with their borders defined the next step is to give the user the power to be able to select a cell of interest. When the user selects a cell they wish to examine everything else bar that cell is removed from the window leaving the cell isolated. The cell is then cropped removing all the unnecessary blank space left behind from the cells that were not worthy of being selected.

When the user selects a cell, the pixel location is taken and the pixels RGB value of that location is taken from the marker image after segmentation from the watershed algorithm. This can be done with the line:

if event == cv2.EVENT_LBUTTONDOWN:
                   refPt = [(x, y)]

The first line detects whether the left mouse button has gone down and if so 

Then a thresholding is applied to the marker image leaving everything bar that color. This is then turned into a binary mask that can used on the original image resulting in an image with only the cell that was selected and everything . The cell can then be cropped using the following function that I had used in a previous assignment.

# Crop Image 
p = np.argwhere(thresh1==0) 
p = np.fliplr(p) 
x, y, w, h = cv2.boundingRect(p) 
x = x-10
y = y-10
w = w+20
h = h+20 

c = ROI[y:y+h, x:x+w] 

np.argwhere() - Finds the indices of array elements that are non-zero, grouped by element.

np.fliplr() -Flips array in the left/right direction. Flipa the entries in each row in the left/right direction. Columns are preserved, but appear in a different order than before.

cv2.boundingRect(p) -  Returns x, y, w, h. Lets (x,y) be the top-left coordinate of the rectangle and (w,h) be its width and height.

The cropped image is then to be saved to a file location using the line:

cv2.imwrite('image.png',img)

References

[1 ]Anon, (2018). [online] Available at: https://docs.opencv.org/3.4.0/d7/d4d/tutorial_py_thresholding.htmlaa669a943a [Accessed 12 Apr. 2018].

[2] Docs.opencv.org. (2018). Morphological Transformations — OpenCV 3.0.0-dev documentation. [online] Available at: https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_imgproc/py_morphological_ops/py_morphological_ops.html [Accessed 12 Apr. 2018].

[3] Docs.opencv.org. (2018). OpenCV: Image Segmentation with Watershed Algorithm. [online] Available at: https://docs.opencv.org/3.1.0/d3/db4/tutorial_py_watershed.html [Accessed 12 Apr. 2018].

[4] N. Li, M. Liu and Y. Li, "Image Segmentation Algorithm using Watershed Transform and Level Set Method," 2007 IEEE International Conference on Acoustics, Speech and Signal Processing - ICASSP '07, Honolulu, HI, 2007, pp. I-613-I-616.

[5] Hai Gao, Ping Xue and Weisi Lin, "A new marker-based watershed algorithm," 2004 IEEE International Symposium on Circuits and Systems (IEEE Cat. No.04CH37512), 2004, pp. II-81-4 Vol.2.