To see, or not to see

CSE 576 Project Three – Spring, 2006
by
Leith Caldwell

The challenge

The goal of this project was to develop a content-based image retrieval system that retrieves database images based on the similarity between their regions and those of a query image, using both region attributes and spatial relationships.

The how

K-means clustering.

K-means clustering.

The first step in developing this system was to draw out the various attributes from the provided database of images. This first involved using a color clustering algorithm to determine the initial components of the image. K-means clustering was used with an color-histogram derived seed initialization somewhat similar to mean shift.

From the labelled segmentation image, the next step was to reduce noise. In order to do this, a median filter with a 5 × 5 pixel window size was used. The aim of this was to remove as many of the small, connected regions as possible. While some small regions still remain, hundreds are removed through this filtering prcoess.

After the color-segmented images have been cleaned up, a connected components algorithm was run over these noise-reduced images. This provided a labelled image which was segmented by connected components. These components were also thresholded to being at least 200 pixels in size. For each of the major components selected by the connected components algorithm, the following attributes were recorded:

Post-median filtering.

Post-median filtering.

For each pair of major regions in the connected components image, the adjacency relationships of being relatively left, right, above, below or 'other' (for inside/outside) were recorded in the RAG in order to determine the spatial relationships. These spatial relationships were computed by determining a simple bounding box overlap measurement and storing a binary 'yes' or 'no' as to whether or not they overlap. I used these relationships because they were the simplest ones; there are 28 different cases over how bounding boxes can be positioned relative to each other and this enabled a reduction in the number of test cases.

In order for any content-based image retrieval system to be effective, it needs to work both in memory and through persistent files. The system thus handles reading and writing of the specific attributes, respectively from and to a specifc text file format.

From there the query and database-generating system was written in order to facilitate the operation and testing of the system, initially with a dummy distance measure in place.

'Major' regions (more than 200 pixels).

'Major' regions (more than 200 pixels).

Relative distance

With the framework in place, the dummy distance measure was supplanted by my own initial relative distance measure. My approach was simple: for each attribute of each component in the query image, record the error difference for every component in the current database image. When all the attributes and components have been processed, use a weighted comparison of each of the attributes in order to find the best corresponding component in the database image for each component in the query image. When all components have a corresponding match, use an aggregate function (in this case a simple sum) in order to provide a total error score. My distance measure favored color and texture as the main component weights, as these provide the best representation of the region's content. The Region Adjacency Graph and the size of the each region would provide the next most important attributes, since they describe the location and relative importance of the component in the image. Next would come the bounding box and the centroid as lightly weighted attributes. Since the location of the component may change heavily (as in a panning image sequence) in an image but still have similar content, I do not believe these play an important role in determining the relative distance.

The approximate percentage weights would be: Color (~27%); Texture (~27%); Size (~16%); RAG (~16%); Bounding box (~10%); and Centroid (~4%);

The challenges I came across were:

The result

After all that, I have a system which has some issues with memory leaks and particular image files; the bounding box and region adjacency graphs have not been factored into the relative distance measure at this stage of implementation. To that end, the image 'boat_5' has been omitted from the following query results and 'boat_2' has been used as a replacement query image. Some other tests have been omitted due to inexplicable errors in the programming that have yet to be resolved.

Unfortunately there was not enough time available to perform any experimental analyses of various weight measures and the effects on the resulting datasets.

These are the results of the test results, in order of increasing error:

beach_2

beach_2  
beach_2   beach_4   crater_3   beach_3   stHelens_3   crater_2   cherry_3   stHelens_2   cherry_1   boat_3   boat_2   crater_5   sunset2_5   stHelens_4   boat_4   cherry_2   crater_4   beach_5   stHelens_5   crater_1   sunset2_4   cherry_4   sunset2_3   pond_2   boat_1   beach_1   cherry_5   pond_3   stHelens_1   sunset2_1   pond_1   pond_5   pond_4   sunset1_2   sunset2_2   sunset1_3   sunset1_1   sunset1_5   sunset1_4  

boat_2

boat_2  
boat_2   cherry_1   stHelens_3   boat_3   cherry_3   stHelens_2   boat_4   sunset2_5   cherry_2   crater_3   crater_5   beach_4   beach_2   crater_2   sunset2_4   beach_5   stHelens_5   crater_4   sunset2_1   crater_1   sunset2_3   beach_3   cherry_4   stHelens_4   pond_3   pond_2   pond_1   beach_1   boat_1   cherry_5   stHelens_1   pond_5   pond_4   sunset1_3   sunset2_2   sunset1_2   sunset1_1   sunset1_5   sunset1_4  

cherry_3

cherry_3  
cherry_3   stHelens_3   stHelens_2   cherry_1   boat_3   cherry_2   boat_2   crater_3   crater_5   boat_4   beach_4   stHelens_5   beach_2   beach_3   cherry_4   beach_5   crater_4   crater_2   sunset2_5   crater_1   stHelens_4   boat_1   cherry_5   stHelens_1   sunset2_4   sunset2_3   beach_1   pond_3   sunset2_1   pond_2   pond_1   pond_5   pond_4   sunset1_3   sunset2_2   sunset1_2   sunset1_1   sunset1_5   sunset1_4  

crater_3

crater_3  
crater_3   crater_2   beach_4   beach_2   beach_3   crater_5   crater_4   stHelens_3   stHelens_2   crater_1   boat_1   stHelens_5   cherry_3   cherry_2   boat_3   beach_5   cherry_1   boat_4   cherry_4   stHelens_4   stHelens_1   boat_2   cherry_5   sunset2_5   beach_1   pond_2   pond_3   sunset2_3   sunset2_1   pond_1   sunset2_4   pond_5   pond_4   sunset1_3   sunset1_2   sunset2_2   sunset1_1   sunset1_5   sunset1_4  

stHelens_2

stHelens_2  
stHelens_2   stHelens_3   boat_3   cherry_3   cherry_2   stHelens_5   crater_5   cherry_1   crater_3   beach_5   crater_1   stHelens_4   crater_4   beach_4   crater_2   cherry_4   beach_3   beach_2   boat_4   boat_2   boat_1   sunset2_5   stHelens_1   sunset2_1   sunset2_3   cherry_5   pond_3   beach_1   pond_2   sunset2_4   pond_1   pond_5   pond_4   sunset1_3   sunset2_2   sunset1_2   sunset1_1   sunset1_5   sunset1_4  

sunset2_2

sunset2_2  
sunset2_2   sunset2_3   boat_2   stHelens_3   stHelens_2   cherry_1   boat_3   cherry_3   sunset2_4   beach_2   sunset2_5   beach_4   pond_2   beach_5   sunset2_1   beach_3   crater_3   stHelens_4   beach_1   pond_3   cherry_2   boat_4   boat_1   crater_2   crater_5   cherry_5   crater_1   pond_1   cherry_4   crater_4   stHelens_5   stHelens_1   pond_5   sunset1_2   pond_4   sunset1_1   sunset1_3   sunset1_5   sunset1_4  

Further development

While there are always more extensions one can add into any project, in this case there are a number of things that could be done in order to improve the end result:

Acknowledgements

Thanks to Lillie Kittredge for helping me try to understand what on earth I'm doing and for telling me to relax when I really needed to relax. Thanks also to both Lillie again and Linda Shapiro for being so understanding about the issues I have had during the development of this project.