The C-elegans nematode is a free living roundworm that was chosen for this project due to the availability of images and ground truth as well as for its relation to cancer studies. The goal of this portion of the project was to correctly identify the position and number of these organisms in an image such as in Figure 3. The output of the algorithm is an Nx4 matrix consisting of the x and y coordinates of the top left corners of each bounding box as well as the height and width of the box for use in testing accuracy using our ground truth. The output is then [x,y,w,h]. The algorithm uses edge and external contour detection as its basis, but there were various attempts on the problem before edge detection was considered as a final solution.

First, we used a clustering algorithm called K-means to analyze the image. Unfortunately, the organisms, due to the nature of the background, tended to blend into the page, more so on some images than others such as in Figure 4.

From this we understood that this would not be a simple thresholding problem. We then thought to attempt background subtraction. Unfortunately, the background has a more than subtle shift between images, which means using a median based subtraction would not work. Due to this we thought to use a different type of background subtraction. Assuming one knows what the background looks like, it is possible to simply subtract the original image from the background. The question then becomes, where do we get the background image from. The idea was to blur the image enough that the background is still in tact while removing the organisms from the image. We used cv2.pyrmeanshift for this purpose. The equation is the original minus the background plus some intensity value. The result was less than satisfactory as shown in Figure 5, mainly due to the noise involved during the change in gradient within the image.

Finally, edge detection was tested. It seemed to accurately remove the background while maintaining a sense of the cell. In computer vision, if a few pixels that represent the whole can be obtained, It is possible for an effective algorithm to be developed. As such, we continued with the process. Canny edge detection was used for our needs as shown in figure 6.

The next problem was the removal of the only thing in the image outside of the organisms, the image border between the completely black area on the corners and the rest of the inner area. The answer to this problem required some backtracking. Thankfully, the dark corners were actually fairly black and thus easily separable from the rest of the image using some thresholding. From there, we used an 8 connected component algorithm to located the areas outside of the border, dilated them so that they would hang over the edge of the border line and replaced the area in the canny image with the dilated area, which was turned black to match the rest of the binary canny image. We then replaced a few rows and columns at the top, right, left, and bottom with black since the borders there were not removed during this process, which can be seen in Figure 7.

The next step was to filter out the leftover noise that did not pertain to the cells in question. The assumption made was that if there was a collection of pixels under a certain amount, it would be considered noise. For this problem, we first used a closing morphology algorithm on the image which filled in most of the holes since the edge image was highly disconnected. From there, we used another connected components algorithm to identify all of the pixel clusters in the image greater than 10, iterated through them, and replaced the bounding box of each cluster under 400 pixels with a completely eroded version of the original. This process is shown in Figure 8.

Next, since the cells still weren’t completely connected, we had to come up with a solution other than a simple connected components algorithm to separate cells while making sure we didn’t break up individual cells. Dilation would work to fill in holes, but it would also connect cells that were not touching originally. The same issue comes up in using closing morphology. We thought to use snakes; however since deformable contours was deprecated in OpenCV for python, we did not want to chance making an ineffective algorithm. Thus we sought other solutions similar in nature. We had the thought to connect nearby external contours but thought that this might already be implemented online. It turns out that someone on the stack exchange had implemented this in response to another question. The algorithm detects all external contours, which means that it does not save any contours that are within contours. It then goes on to compare each contour’s point to all of the other points in the image, and if it is within a certain vicinity, then it adds it to a contour array. Finally, the OpenCV draw contours function is evoked for a visual as shown below in Figure 9.

The contours are used to determine Cell number and to compute the bounding boxes. For each contour, if there are at least 200 pixels within the canny image in that location, then we consider that 1 cell. If there are more than 350 pixels, then we divide the number of pixels in that contour area by 350 and round up. We use a mask of the contour area over the canny edge image to accomplish this process as shown in figure 10.

The bounding boxes are simply the top, left, bottom, and right-most locations on each contour. The final output is shown in Figure 11.

The goal of the image analysis of the U2OS cancer cell dataset, like the example shown in Figure 12, was to return the number of cells in each image and the size and location of each cell. The output is an Nx4 matrix where N is the number of cells and each row contains [x,y,w,h] where x and y is the coordinates of the top left corner of a patch containing the cell and w and h are the width and height of the patch respectively. The script uses an iterative process that uses different parameters and methods with each pass and tries to increase the accuracy of segmentation without over segmenting. The function is built such that each pass can segment a patch into multiple cells, but if a single cell is over segmented, future passes will not return the whole cell. This is why it is important for each pass to err on the side of under segmenting and work in that direction towards the ground truth without ever going over.

The first method that is used is a simple connected components blob detection method. This was an obvious choice because it is easy to implement and most of the cells are separated by black. The image was first smoothed using a Gaussian filter and then a simple intensity threshold was taken to remove the background. A built in connected components function from the scipy ndimage library was used. This method quickly and easily separated and returned each cell that was not connected to any other cells and any cells that were touching were returned together as one cell. In figure 13(a) a low threshold was used to separate the cells from the background. Because of the smoothing, cells that were touching or were close together were not separated. Cells that were far from other cells were easily segmented. In figure 13(b) a higher threshold was used. All cells were successfully separated, but the threshold was too high and some cells were not even seen while almost all the cells lost their edges and their sizes were returned to be much smaller than they actually were. No threshold was perfect and to solve this problem I used an iterative process. I made several passes using the connected components algorithm using increasingly high thresholds. I started with the threshold in 13(a) and ended with the threshold used in 13(b). After the first pass, each box was treated as its own image and passed individually back through the function and thresholded with a higher value. If the algorithm detected only 1 cell at the new threshold it did nothing and assumed that the previous pass was more accurate. If it detected more than 1 cell it created new bounding boxes for each cell. Figure 13(c) shows that this method successfully segmented all cells in the image without missing any or returning sizes that were too small.

The second method we employed was a circle detect method. Some images had cells that were touching or overlapping and the connected components method would never separate those cells. The theory was that overlapping cells would vote in hough space for different ellipse centers and the cells could be segmented by that method. Figure 14 shows some examples of the success and failures of the circle detection method. Segmentations done by this method are yellow while segmentations done by other methods are in orange. Figure 14(a) and (b) show two overlapping cells that could not be segmented with the connected components method but were successfully segmented with the circle detection method. Figure 14(c) and (d) show a fairly successful example of the method in action on an entire image. The method successfully separated groups of overlapping cells that could not be separated with the connected components method. In the top left corner of 14(d) all the cells were successfully separated and the boxes were pretty tightly bound to the cells. In the top right corner the cells were successfully separated, but the bounding box on the upper cell is a little large. The center group was segmented reasonably well, but one cell was missed and the bounding boxes were a bit large on others. The lower left group was poorly operated on. Half of the cells were missed entirely in that group. Overall, figure 14(d) shows a pretty successful application of the circle detection method. The accuracy of the segmentation was superior when added to the connected components method shown in (c). Figure 13(e) shows a failure case of the circle detection method. The top left yellow boxes were improperly placed around an unusually shaped cell. The yellow boxes just below that were placed around a cell with unfortunate intensity variations that the method detected as several ellipses. The center yellow boxes were placed around a cell that had a slight notch in the center. Each side of the notched ellipse voted for circles.

The circle detection method worked in some cases but not in others. The major difficulty was choosing parameters and what worked on one image did not work on others. This method could improve accuracy in a single image after carefully choosing the parameters, but it would decrease the accuracy in many other images. Some reasons this method failed was irregularly shaped cells, difficulty in removing noise in all images with the same parameters and opposite sides of an ellipse voting for two circles. At the end, parameters were chosen such that the circle detection method was applied extremely conservatively and it did not increase the accuracy of cell separation by a large margin when applied to the whole dataset with uniform parameters.

Figure 15 (a) and (b): display the final result of the U2OS detection algorithm implementation.

Results and Experiments:

Experimentation and metrics setup (The following are applicable to both the approaches):

          a. Classifier performance- To measure the performance of the classifier on the test images, precision, accuracy, recall and balanced F-score were calculated. These were done by comparing the correct labels in the ground truth image against the labels predicted by the SVM for both the classes using false positives, false negatives, true positives and true negatives. Sklearn’s metrics modules was used for this purpose.

          b. Detector performance- To measure the performance of the detector, a detection was considered a true positive if it’s IOU (intersection over union) with respect to the ground truth bounding box was above 0.5. Precision was calculated as the ratio of number of true positives over the predicted bounding boxes. Recall was computed as the ratio of true positives to the actual number of bounding boxes in the ground truth.

          c. Cell count- To measure the cell-count performance, the mean RMS cell-count error was computed using the predicted cell-count and the ground truth cell-count.

Approach 1:

          A. Detector performance

Figure 16 Displays the C.elegans detector performance.

Figure 17 Displays the Human U2OS detector performance.

Figure 18 Displays the average performance.

Figure 19 A chart displaying the precision, recall, f1-score, and support vector score of the classifier.

Class 1 / C.elegans: RMS cell count error: 3.22672662398 cells

Class 2 / Human U2OS: RMS cell count error: 4.86483983978 cells

System: RMS cell count error: 3.72418651754 cells

Some example result images:

Figure 20 Displays the C.elegans detector output after an image is correctly classified as C.elegans

Figure 21 Displays the Human U2OS detector output after an image is correctly classified as Human U2OS

Figure 22a An example of the final output after going through the C-Elegans detector algorithm. Figure 22b is an example of the final output after going through the Human U2OS detector algorithm.

Approach 2:

Detector performance:

Figure 23 Displays the results with classification.

Figure 24 Displays the results without classification.

Classifier performance:

Figure 25 A chart displaying the SVM performance on C. Elegans.

Figure 26 A chart displaying the SVM performance on Human U2OS.

Cell count performance:

Mean RMS error - RMS cell count error: 4.79583152331 cells

Some sample outputs:

Red boxes indicate successfully classified C.elegans crops, and green boxes indicate successfully classified Human U2OS crops. Figure 27a is an image displaying the SVM score or positive probability of classifying each respective C. Elegans cell. Figure 27b is an image displaying the SVM score or positive probability of classifying each respective Human U2OS cell.

Figures 28a and 28b display the final output of approach 2.

Figure 29 displays a chart comparing the two approaches.

Challenges faced:

           1. The dataset procurement was a challenging issue since we were not able to get images along with ground truth which was a much needed requirement to measure the performance of our models accurately. The datasets we eventually worked on had limited images which could have led to over-fitting.

          2. During SIFT feature extraction, multiple cell crops gave zero key-points and descriptors, indicating there weren’t much features that could be extracted. This was affecting our performance. As an alternative, we resized all the patches to a pre-determined minimum dimension. That too didn’t seem to work. So finally, when SIFT detector could not detect any key-point, we treated the entire patch as a key-point. If there weren’t much gradients in the patch, the histogram returned would be a series of zeros or else some miniscule non-zero values in the bins. But this helped to detect similar patches in test image and improve the performance.

          3. For approach 2, our sliding window approach turned out computationally expensive to run. As an alternative we came up with a basic, generic cell detection method.

Conclusions:

We successfully implemented two cell classifiers with decent performance in terms of precision, recall and mean RMS cell count error. The first approach used class-specific cell detection algorithms whereas the second approach followed a generic cell detection approach. On comparing the two approaches, we realized that the second approach performed better and is applicable even if not much is known about the given cell phenotype (e.g shape, texture etc). It can be easily extended to other datasets whereas the first approach is far more fine-tuned and dataset-specific. The overall performance of the second model was better in terms of precision (0.6980) and recall (0.5305) as against first model’s precision (0.6512) and recall (0.4971).

Dataset-based detector modules can be useful too as seen in the case of the Human U2OS detector in approach 1 which gave a precision and recall of approximately 0.9020 and 0.8187 respectively. Also the mean RMS error in cell counting was lower in approach 1, due to the high specificity and tuning of the algorithms.

Approach 2 indicated that classification helped in pruning a lot of false positives from the detector module, giving a 51.74% improvement in mean precision value (increasing it from 0.46 to 0.698). The recall dropped; however, this was intuitive.

A drawback in our system could be the high dependence on illumination. This is because SIFT is not invariant to illumination changes. We counteracted this to some extent by pre-processing the input images. We would have tested with more datasets of same cell-types, however such highly specific demand in dataset procurement could not have been met.

Random selected examples of inputs and outputs: