CSEP 576 Winter 2008: Project 3

mountain image	segmented by color

another mountain image	segmented by color

What You Should Do

1. For each image in the database you will perform the following procedure:
   1. Run your color clustering on it to obtain a labeled cluster image.
   2. Run connected components on it to obtain a labeled segmentation image. Possibly perform some noise cleaning/merging operations to improve the regions. Try not to vary the parameters between the images. There is a connected component program conrgn in the class software page (here). The conrgn program accepts a binary (0s and 1s) image or a labeled image (0 is for background and label 1-255 for other regions in the image) of type PGM as input. It does not accept RGB image for input. The program will output a grayscale PGM file or a color PPM file depending on argument. The program will output at most 255 labels, so if your segmentation produces more regions you may want to create your own output function that outputs a matrix of labels instead. The conrgn output in image is just for debugging (just for show), what you need is the region label at each pixel, so the grayscale output (if there are less than 255 regions) or a matrix output is what you need to then compute the attributes of each region. You can also modify the  conrgn program and calculate the region attributes in the program.
      
   3. For each major region (use a size threshold), compute at least the following attributes
      • size
      • mean color [(R,G,B) or whatever space you like]
      • at least one texture measure. Examples of texture measures include Local Binary Pattern (LBP), co-occurence, edgness per unit area, edge magnitude, or direction histogram.
        
      • centroid (row, column)
      • bounding box or other representation of where the region is
   4. Store the attributes in a data structure that you define and that can be both used in memory and also saved in a file so you don't have to keep rerunning the analysis. We will refer to this structure for an image I as DS(I).

2. Develop a distance measure that will compute the distance DIST(I1,I2) between DS(I1) and DS(I2) for any two images I1 and I2. Ideas for this distance measure can come from Chapter 8, Chapter 11, and your own ideas.
   To do this, you will need to find the best correspondence between regions of I1 and regions of I2 by whatever algorithm you choose. (One simple way is to use a greedy approach that finds for each region in I1, its closest match in I2).
   Then once you have the correspondence, the distance between I1 and I2 can be a function of difference in attributes of corresponding regions, difference in number of regions, and/or any distance measure you choose.
   

3. Create a query system in which you can select a query image Q and compare it to each image I in your database by computing RELDIST(Q,I). Then you order the images in the database according to their distance to the query and return the ordered list (the images and associated distances). A fancy user interface is not required but you can create one for extra credit.

4. Test your system as indicated below.
   • The database has 40 ppm images for the tests.
   • The following images should also be query images.
     1. beach_2
     2. boat_5
     3. cherry_3
     4. crater_3
     5. pond_2
     6. stHelens_2
     7. sunset1_2
     8. sunset2_2
   • Use your distance measure to compare each query image to all 40 database images, recording the distances you get for all 320 tests.

Sample Timeline

• First week: region finding (color clustering, connected components and post-processing)
  
• Second week: Compute region attributes and data structure
  
• Third week: Develop distance measure and query system. 
  
• Fourth week: Finish testing and write it up.

Extra Credit

Here are some ideas for improvements to the basic assignment, any of which will earn some extra credit:

• Add spatial relationship attribute using RAG (region adjacency graph). An example of RAG is in slide 23 of CBIR lecture. Once you have developed the spatial relationship attribute using RAG you should alsodevelop a better algorithm for finding the best correspondence between regions of the query image and those of the database image, using both attributes and relationships.
• Develop a nice GUI for your system.

Progress report

What You Should Turn In in your final report

1. Introduction: describe your system and overall framework
   
2. Describe your region finding algorithm.Give several examples to show your color clustering results and improved regions.
3. List the attributes you selected to describe the regions. Explain why you want to use them.
4. Describe your region correspondence algorithm
   
5. Describe your distance measure a and explain the motivation.
6. A section of the report that gives the results of the tests. For each of the 8 query image, use the THUMBNAILS to show the query and the query results with their distances printed and in ascending order, ie. smallest distance first. Hopefully, the one with smallest distance will be the query image itself, which ought to get a zero when compared to itself, and the one with the largest distance will be quite different.

   The result for a query may look like:

   Query Results for boat_2

   boat_2 d = 0	boat_4 d = 0.05	boat_3 d = 0.07	boat_5 d = 0.07	beach_3 d = 0.12
   beach_2 d = 0.13	beach_4 d = 0.15	crater_2 d = 0.16	boat_1 d = 0.20	...
   ...
   ...
   ...
   ...
   ...
   ...	...	...	...	sunset1_5 d = 0.98

   If you didn't generate the results automatically, you can just give the best 5 and worst 5 images and the distances for all the images. So it may like:

   Best Query Results for boat_2

   Worst Query Results for boat_2

   ...

   ...

   ...

   ...

   1. boat_2 = 0
   2. boat_4 = 0.05
   3. boat_3 = 0.07
   4. boat_5 = 0.07
   5. beach_3 = 0.12
   6. beach_2 = 0.13
   7. beach_4 = 0.15
   8. crater_2 = 0.16
   9. boat_1 = 0.20
   ...
   40. sunset1_5 = 0.98
   

7. Discuss your results (why it retrieves similar/non similar images to the query).
8. Beside the report, your commented code and a readme file to describe how to run your code