Image Segmentation through Texture Recognition: A Texton Clustering Approach

Julie Letchner, Ruwen Hess, Adit Koolwal
CS223B - Winter, 2002

Our initial motivation was to devise an algorithm that allowed us to segment brain MRI scans into separate regions based upon the "textures" of the different parts of the brain including skin, water, bone, gray matter, and other objects such as tumors, if present. We felt that texture detection was ideal because certain regions of the brain (like the gray matter) do not always have a constant color or intensity in MRI scans, but do have their own unique texture (Fig 1). We hoped to be able to identify these regions with more success than various MRI scan viewing programs that we downloaded. We observed that with several of these programs, we were unable to segment gray matter from skin.

Fig 1. The gray matter of the brain is hard to segment out by using simple grayscale value detection as its values range from very dark to very light.

The above mentioned problem can be classified as a part of the more general problem of image segmentation in computer vision. While humans are already able to detect regions, contours, and textures within in a image, it is desirable to devise algorithms that can do the same in order to compute statistics about these characteristics of images that humans are incapable of computing. Image segmentation techniques generally fall into one of two categories: contour based and region based approaches (1). Contour based approaches such as the Canny Edge Detection algorithm (2) often involve an initial stage of edge detection using Gaussian filters followed by several stages of refinement including thresholding and contour following. While contours can often be detected using local objective functions, regions cannot as they are properties of the entire image while contours are local properties. Several techniques for region detection have been suggested including the Expectation-Maximum algorithm (3) which uses a k-means framework to segment the pixels of an image into one of k different regions using a least squared distance heuristic evaluation function. This algorithm immediately useful for segmenting pixels of an image into regions based upon superficial properties (such as color). For more complicated regions (such as textures) we need a framework in which we take into account both the properties of each pixel p as well as the properties of the pixels surrounding pixel p in order to get a sense of what sort of region p lies in.

In this project we decided to loosely follow the framework presented in (1). This paper discusses the use of textons (which are essentially pixel descriptors) and how they can be applied to texture segmentation algorithms. Using the information we gathered about textons, we experimented with different strategies to come up with our own texture segmenting algorithm. Our strategy can be briefly summed up as follows:

• Calculate a number of filter outputs for each pixel in the image in order to get a robust description of the region surrounding the pixel. The set of filter outputs for each pixel is referred to as that pixel's "texton."

• Perform an initial clustering step, segmenting off pixels into bins based upon the least squared differences between texton values. After the k-means clustering step is complete, assign each pixel a discrete valued number that refers to which "texton group" it was placed in.

• For each pixel, calculate a histogram of how many of its surrounding pixels were placed in each of the texton groups.

• Perform a final k means clustering step, segmenting off pixels into bins based upon the chi squared distances between their histograms. After the k-means clustering step is complete, assign each pixel a discrete valued number that refers to which texture it was placed in.

After observing our results we noted that we were generally successful when the image being processed had textures that were small (ie. textures with patterns that repeated every n pixels, where n was some number less than 20). On images with textures whose patterns repeated over a larger number of pixels, our algorithm found like textures within those larger textures. We also found that our algorithm had trouble dealing with pixels that occurred at the boundaries between textures, often generating textures that formed rings around other valid textures (see RESULTS).

In order to compensate for the shortcomings of our algorithm, we tried to modify our existing algorithm, and, ultimately, we tried other techniques including the normalized cut for contour and texture analysis for image segmentation (see IMPLEMENTATION). While our experimentation did allow for us to handle most of our issues separately, we were unable to come up with an implementation that handled all of our issues at the same time. Still, our base implementation generally worked well within the class of images described above, especially when considering the reduced computational complexity in comparison to other algorithms such as the normalized cut algorithm mentioned above.