Hello. Another way to segment an image is by looking at it as a 3D surface and exploiting the morphological shape of the surface. Then the interesting idea of the watershed method can be used. If we look again at an image as a 3D surface, it consists of mountain peaks and valleys, or catchment basins. If we were to assume that water starts pouring in from the bottom of the lowest valley, then when this water reaches the peak of the mountain, it will start pouring into the catchment basin next to it. It is that point, the so-called, the watershed line, that we want to detect because it will separate the two objects represented by the valleys. Since the watershed method typically results in over-segmentation, we also describe means to control it. We further describe the three dimensional Cayman's clustering approach and how it applies to the segmentation of medical MRI brain images. So, let's look at the details of these visually, also, interesting approaches. In geography, a watershed is a ridge that divides areas drained by different river systems. A catchment basin is the geographical area draining into a river or a reservoir. The watershed transfer applies these ideas to grayscale images in a way that can be use to solve a variety of image segmentation problems. Watershed segmentation requires that we think of a grayscale image as a topological surface. In other words, the values F, X, Y of an image are interpreted as heights. Let's look for example at this simple image. It's shown here as a grayscale image, and here as a 3D measurement of surface. If we imagine that rain falls on this surface, the water will collect in these four areas shown here, which are called catchment basins. Rain falling exactly on this line, on this watershed line, will collect into these two catchment basins, this and this one, with equal probability. So the watershed transform finds the catchment basins in the ridge of these watershed lines in a grayscale image that will result in the segmentation of the image. As described in the previous slide, according to the watershed transform there are three types of points in an image. Points that belong to a regional minimum, points that belong to a catchment basin of a regional minimum, so these are the points at which, if a drop of water falls, will certainly fall to a single minimum. And then points that belong to ridge lines or watershed lines, and if a drop of water falls onto points belonging on a watershed line, then equally likely will fall to more than one minimum. So the objective of the algorithm is to detect these watershed lines which will result in the segmentation of the image. We want to address the concept behind the watershed transform without getting into any of the fine details. So according to it, given this topography shown here, if we punch a hole here at this local minimum and flood the region with water from below, then water will be rising here until we reach this point. And this point, an additional drop of water, if it's to fall down, it will equally likely go in to this catchment basin or this catchment basin or this valley or the other valley. So in order to prevent this from happening, we built here a dam. And after this is built, we keep going, we keep flooding the area with water until we reach this point, where again an additional drop of water will equally likely go between this valley and this valley. In order to prevent this from happening, will build a second dam here and we keep going until there are no more dams to be built. And this dam here is a watershed line and this is what we are after with the watershed transforms. If you tell me there's watershed lines, then we have separated one object from the next from the next one. So again, this is hopefully the concept that is clear to you, treating a grayscale image as a topographical surface and being able to determine these dividers, these ridges, these watershed lines between different objects that will result in the overall segmentation of the image. We show here the result of applying the watershed algorithm to this image that I showed earlier. And here is the result, we see that the algorithm did a great job in identifying four different regions. And the background region, the fifth one and this here are the watershed lines. It's easier to segment this object. It's more challenging to find this watershed line, but by enlarging, this is a very satisfactory result. We show here the result of the application of the watershed algorithm through this image. It is a magnified microscope image of a slice of the eye of the fruit fly or the so called [FOREIGN]. This is a project we are currently involved in. If one is able to segment successfully the cells shown in this image, one is able to study how cells transition from a stem to a differentiated state. The development of the fly eyes serves as a useful model in understanding this transition. If we apply the watershed algorithm to this image, we obtain this result. Clearly the image is oversegmented because there are a large number of potential minima, many of which may not be relevant. So we need to find ways to control this oversegmentation that results, and this is what we will discuss next. A solution to the oversegmentation problem that was demonstrated in the previous example is to use markers. A marker is a connected component belonging to an image. I would like to have both internal markers, which are inside each object of interest, as well as external markers, which are contained in the background. With respect to the internal markers, some of the properties are that each one corresponds to an object. They are surrounded by points of higher altitude. The points in the region form a connected component. And also, all points in connected components have the same intensity. As far as the property of the external markers goes is that they should partition the image into regions where the regional minima are allowed to locate. These markers bring prior knowledge into the segmentation process and therefore they constrain it. Various methods have be suggested in image processing literature for computing both internal and external markers. They involve linear and nonlinear filtering as well as morphological processing. Which method one chooses depends on the specific nature of the images one deals with as well as with the application account. We'll revisit here the example of applying watershed algorithms towards the segmentation of the image of the eye of the fruit fly. Those microscopy which is magnified. We are going to utilize now markers. We see here the originally marked with internal markers overlayed on it. The other wide parts here. So these internal markers were obtained by thresholding the intensity values of the original image so they represent a bright spot in the image. Obtaining external markers is even harder. Here are the external markers we will be using in this case. They were obtained by applying the original image intensities, not on the gradient image. So these external markers constrain the regions to which the watershed algorithm would be applied. So it would be applied for example, inside this region. So making use of both internal and external markers, we obtain this segmentation result. It's certainly an improved result. It does not suffer from over segmentation and it does a good representative job in delineating the cells in the original image. Another way to perform segmentation is through the use of the K-means clustering algorithm. Clustering means grouping similar data together. So given alphanumeric observations we attempt to classify the data points into K different clusters, and these clusters may represent segments in an image. K stands for the number of clusters and this is a parameter that is input to the algorithm by the user. This algorithm is iterative in nature as we'll see, and is not confined to image segmentation, is a general algorithm for machine learning application. It's actually the same algorithm we encountered in week nine, when we designed the code book for vector quantization. Provide an explanation of the steps that followed towards K-means clustering. These are intuitive steps, as you'll see. And more than that, the steps should look familiar to you, or sound and look familiar, since we followed exactly the same steps back in week nine, when we designed the codebook for vector quantization. So the first problem, is how to assign a class, or a cluster to a given pixel. We see here two clusters a red one and a blue one. And these are representative of big cells so the red class and of the blue class. These are the centroids actually of the classes. So given a new big cell the question is where should this be classified to belong to? The red cluster or the blue cluster? And now so this question, we're going to find the distance of this pixel to both centers, and we are going to compare the distances. This distance here to this distance. As shown graphically here, this is smaller than this distance, and therefore this is going to be classified as a red pixel. The second sub problem we need to address is how to find new centers from known clustering. We show here two clusters, a red one and a blue one and the problem at hand is to find the representative pixel for each of the clusters. The answer is that the representative pixel, let's say the red pixel here is the center of mass of the red pixels. In finding the center of mass, I need to know the probability distribution, the probability density function of the red pixels. We typically don't have that information. And we typically assume that the points are uniformly distributed. In which case, the centroid is simply the average of the red vectors. So this is what we do. We find the new center by taking the average of the red pixels here and the blue pixels here will give us the new blue center. So the game is clustering alternates between the solution of the two sub problems we just described as we'll see also next in the following example. Look us look at the simple example of the application of the K-means clustering algorithm. We're given an image with this white pixels here and we are going to classify them into two classes okay equals two. We initialize the tandem with the these two synthroids of the clusters. We assign the data to the two clusters based on their proximity from the centroids. So this pixels here are closer to this centroid and these are all red pixels. While these pixels are closer to this centroid and given the label blue. We calculate the location of the synthroids, so now this blue synthroid is the average of this blue peak cells while this centroid is the average of these red peak cells. We re-assign data based on the new location of the centroids. We then re-compute the location of the centroids. Reassign data and recompute the new location of the centroids until there is no more change and we have converged. So in summary, the K-means clustering algorithm consists of choosing the number of centroids, k, and then until convergence, we alternate between assigning each training point to its closest centroid and recomputing the centroid location. So the output of the algorithm is that K centroids and of course the label of the pixel to which centroid they belong. As I already mentioned, there are numerous applications of K-means clustering in machine landing applications and design of code books and vector quantization alike. When it comes to image segmentation, they have found applications to processing medical images. We see here in MRI image. We see here the frontal view. The so-called sagital view and the horizontal view of this, of the brain of this person. There are three groups typically with this images. White matter, grey matter, and cerebral spinal fluid or CSF. So we wanna class the voxel cells, these are three dimensional pixels into one of these three categories. Some of the prior knowledge you want to use is that voxels with the same intensity should belong to the same group and also voxels that are next to each other. So we want to use intensity as one feature but also spacial proximity. So we uses a feature vector here. A four dimensional vector. It has the intensity of the voxel. It's a function of three spatial coordinates as well as the three spatial coordinates. In defining distance between two vectors, we use the Euclidian distance. As mentioned in the previous slide, this is the feature vector that can be used in clustering the voxels in an MRI emerging through this three categories gray matter, white matter and CSF. So K equals three for our purposes. We can use weights here alpha and beta based on which the relative importance of the intensity and intensity similarity or proximity of voxel cells is controlled. As far as the distance metric, we could use either the L1 or the L2 north. We will see actually during the last week of classes the impact or the effectiveness of the reason why we should use L1 or LP in general norms versus L2 norms. So I will not say many more things here about it but nevertheless it's an interesting topic of analysis. Typically what's done, in segmenting MRI images, is to start with a large value for K. So, we segment the volume as shown here, into possibly a hundred classes. And then utilize merging algorithms that will merge similar classes and end up at the end with a three desirable classes. We show here a recent result we obtained in our lab, which is a three dimensional k-means clustering application. So we see the human brain, and we see the three different tissues, the grey matter, white matter and CSF. So we see here one slice a time, however, the clustering is a K-means space clustering but in three dimensions. We show here some of the recent results that were obtained by 3D K-means segmentation in our lab. We compare our results with the results obtained by SPM8, which is a public toolbox supported by Matlab. Slide 60 was utilized and was segmented into three regions, gray matter, white matter, and CSF. As mentioned multiple times there is no objective criterion in comparing segmentation results. And the comparison becomes even harder when we deal with medical images, simply because it's the diagnostic quality that we're interested in. Experts actually have looked at these segmentations and carried out their own comparisons. It seems like K-means provides somehow more delicate segmentations than SPM8. Brain image segmentation is a very difficult problem cuz even harder, actually, is that identification of lesions in these brain images. If we are able to identify stroke lesions and also peri-lesions, the regions around the lesion, will assist the medical profession in predicting the recovery of the stroke patient, but also the response of the patient to therapy. We see here an MRI of a healthy brain and an MRI of a brain with damage. These are the lesion regions, or plaque regions. So segmentation is currently typically drawn by hand by the expert, and this is a time consuming process but also a subjective process and therefore not a repeatable process. Therefore there's a great need to overcome the noise present in the images, the existence of weak edges, and the inhomogenity in the data and with an automatic procedure in identifying the lesions and the [INAUDIBLE] lesions, regions for all the purposes that we described. As already mentioned, segmentation techniques can be applied to brain MRI images, and potentially save lives. The segmentation techniques can be used proactively, so that the brain of a healthy individual can be screened to detect abnormalities. But also, after a disease, the same technique can assess the patient's response to therapy. And also can be used to predict the response to drugs and therefore the recovery of the patients. So we see the brain images for two patients here, one and two, and this way we see the very slices of the brain. We see detected in green the lesions in these brain images. We also see a number there which is the value of the Dice Similarity Index. For cases for which the ground proof exist, obtained maybe manually, x represents the ground proof segmentation and why the segmentation provided by our algorithms, or any algorithms for that matter. Then we see that in this index we have the numerator, the cardinality of intersection of the two segmentations, divided by the sum of cardinal this of the individual segmentations. Clearly, x is identical to y. The value of the index is equal to one. So the range of the values is between 0 to 1 and the higher the value of x, the closer to 1, the better the segmentation with respect to the provided ground truth. So the numbers are relatively high and our technology has been compared to other competing techniques and the objective values. They compare very favorably to the competition.
