Matt's Webcorner

Computer vision is a field in computer science that focuses on extracting information from images and using this to solve tasks. Two important problems that are fundamental to many computer vision algorithms are image segmentation and image comparison. Image segmentation algorithms take images represented as 2D arrays of colored pixels and divide them up into regions, with the intention that the regions correspond to meaningful objects or parts of the image. Image comparison attempts to compare images (or parts of images) and can be used for answering questions such as classifying an image as a particular type of scene (outdoor vs. indoor) or type of object (human face, car, etc.). A variety of image segmentation algorithms have been proposed, one of the most popular being the watershed transform. This page documents a variant on this algorithm that is similar to an approach used in geometry segmentation called variational shape approximation. The segmentations produced by this algorithm are then run through an image classification algorithm based on graph kernels which compares two images by comparing their segmentation graphs. This is similar to this SIGGRAPH 2011 paper which does the same thing for 3D scenes.

Image Segmentation

The image segmentation algorithm I use generates a segmentation with a pre-specified number of clusters (N). First, N pixels are chosen at random in the image and act as the seeds for the clusters. The clusters are then grown using a priority queue that favors adding pixels whose color is similar to the cluster's seed. Once all pixels are assigned a cluster, new seeds are chosen for each cluster that are more representative of that cluster, and the algorithm iterates until the clusters reach equilbrium (or close enough.) When a small number of regions are used the segmentation approximately captures the overall color structure and style of the images, and when a large number of regions are used the algorithm acts more like a superpixel segmentation. Here we show results on 3 images varying the number of clusters used:

Original	250 Clusters	1000 Clusters	1000 Clusters

The image on the right uses a false coloring to make it easier to see the cluster size. More results can be found here, which show the results of the algorithm using a different number of clusters for a variety of different image categories.

Image Classification

Once an image has been segmented, we can turn it into a graph. There is a node in the graph for each segment in the image. Two nodes are connected by an edge if the two segments represented by those nodes are touching in the image. Once images have been reduced to graphs, we can apply standard graph kernel techniques to compare any two images. The graph kernel just needs a way of comparing two nodes --- in this case, I compare two nodes by comparing the average colors of the two clusters. The interesting computational details of the graph kernels are all described in this CVPR paper. I don't have any more significant results to show, but the code below might serve as a useful reference for anyone who has to implement graph kernels themselves.