CSEP 576 Winter 2008: Project 3

Content-Based Retrieval with Regions and Relationships

Progress report due: Sunday, March 2, 2008 11:59pm
Final result due: Sunday, March 16, 2008 11.59pm


Downloads:
1. Images
    Download the images you need: zip, tarred gzip
    Download the image thumbnails: zip, tarred gzip, PowerPoint
2. Report template (doc)
3. Grading guideline (doc)

(The image thumbnails, in jpeg format, should help keep your write-up a manageable size.)

In this assignment, you will 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.
mountain image segmented by color
another mountain image segmented by color

What You Should Do

The main idea is to represent each image (the database images and the query image) by a set of regions obtained from color clustering and their attributes. Then, you are to come up with a distance function between two images in this representation, and use this distance function to find the images that are most similar to a query image.
  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.

Sample Timeline

Extra Credit

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


Progress report

Mid-way through the project you will have to send a short progress report. The report should only be a one paragraph email explaining what you have done, what you plan to do to finish the project on time, and any problems you have encountered.
Send the email progress report to Indri (indria@cs.washington.edu) due Sunday, March 2nd 2008, 11:59pm.

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
Send your written report and source code to Indri (indria@cs.washington.edu)