CSE 455 Winter '17 Homework 3: Content-Based Image Retrieval

Date Released: Wednesday, February 8, 2017

Date Due: Friday, February 24, 2017 11:59pm

(Late Policy 10% off per day till Sunday, February 26)

Required files

Download here (Updated on February 16 at 4 P.M. Do not replace this with the previous folder, make a new one and work on it.)

Download here (Updated on February 19 at 5:30 P.M.)

The zip file contains 4 folders. The 'Code' folder contains the code files, the 'Database' folder contain the database images in .ppm format (You can use IrfanView to view such images), the 'ImageView' folder contain the same images as in the Database folder but in .jpg format and the 'Thumbnails' folder contains the thumbnails of the database images to be used to display the results. The images in 'ImageView' are just for your viewing, code is written so as to read the .ppm images and display the thumbnail images in the application window after executing the code. For this project, significant parts of mainwindow.cpp and mainwindow.h files have been changed, so you may want to take a look at these apart from the Project3.cpp file which you need to edit. Please read all the comments in Project3.cpp file carefully before you start writing code. After opening the project file in Qt, make sure that 'Projects' tab -> 'Build Settings' -> 'Shadow build' checkbox is unchecked, otherwise the project will not build.

Description

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.

mountain image segmented by color
another mountain image segmented by color

What To 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 connected components and extract the region attributes. Then, come up with a distance function between two images in this representation, and use this distance function to find the images most similar to a query image.

  1. For each image in the database the following procedure should be performed:
    1. Run your K-means color clustering on it to obtain a labeled cluster image. The PixelSeedImage clustering code is provided in the starter code. You are free to tune its parameters or use a better clustering algorithm from Homework 1.
    2. Run connected components on it to obtain a labeled segmentation image. The code for this step is given in the starter code and ideally you don't need to change it.
    3. Possibly perform some noise cleaning/merging operations to improve the regions. Don't vary any parameters between images. You can define a threshold to retain only those regions exceeding a minimum size (number of pixels in the region) so as to avoid spurious regions. No starter code is provided for this step.
    4. For each final region, compute at least the following attributes:
      • size (given in starter code)
      • mean color, in RGB or whatever space you like (RGB space given in starter code)
      • at least the following co-occurrence texture features (no starter code; use spatial relationship d = (1,1)):
        1. energy
        2. entropy
        3. contrast
      • centroid (row, column) (no starter code)
      • bounding box or other representation of where the region is (no starter code)
    5. Store the attributes in the given data structure (see starter code). We'll refer to the feature vector for image I as F(I)
  2. Develop a distance measure that will compute the distance Dist(I1,I2) between F(I1) and F(I2) for any two images I1 and I2. To do this, you need to find a correspondence between the regions of I1 (query image) and the regions of I2. Compute this correspondence greedily. That is, for each region in I1, find its closest match in I2, and so on. The mapping need not be one-to-one. If you like and have time, you can also compute the optimal correspondence. You can do this with an exponential search procedure, since the number of regions will be small. Graph distances are discussed in S&S 11.6.
    Once you have the correspondence (starter code provided but not optimal; you may need to change), the distance between I1 and I2 should be some function of: We would like you to experiment with at least 2 different distance measures and tell us what they were and which one worked best and is used for your final results. Distance measures can vary in what attributes you used and also in the kind of metric you use to compare 2 vectors. Euclidean distance is only one such metric.
Build and compile the project. In the application window, click the 'Load database' button to load the database. This will take each database image as input and extract and store its feature. Then click the 'Open Query Image' button and select the image you want to use as the query from the 'Database' folder. This will load the query image and extract its feature. Finally, click the 'Query database' button. This will compute the distance between the query feature and each of the features of all 40 images in the database, sort the distances in ascending order and display the corresponding database images accordingly. Hopefully, the query image will have distance zero to itself, and similar images will have smaller distances than dissimilar ones. The starter code automatically sorts the distances and displays the thumbnails of the images and the corresponding distances in the desired order. You just need to write the distance function. To use distance function 2, check the box above 'Query database' button in the window. The 'Progress' textbox shows the progress of the steps being executed. You can click the 'Reset' button to start a new application window, erasing the previous one. You can these out with the starter code to see how the buttons function and what to expect from your code. The code takes considerable amount of time to execute, so don't lose patience as long as no error is thrown. Most probably, you will see something coming up in the 'Progress' textbox soon.
In order to test your system, use the following images as the query image:
Example Query Results for boat_2 (screenshot of application window; you should submit similar screenshots) (Note: distances shown are all 0 now since the code is incomplete)

What to turn in

You should turn in the 'Project3.cpp' file and a report in PDF format (with name report.pdf). The report should describe:
  • the attributes you implemented
  • the distance measures you tried, which one works best and why
  • 8 screenshots, one for each of the 8 query images
  • Comments about the results
    • Your code should be well-structured and well-commented. In case you edit any other file, submit that as well, or you can submit the entire 'Code' folder in that case. Upload the necessary files to the homework dropbox HERE. This is a one-person assignment. You may discuss it, but please turn in your own individual work. Plan your work early.

    Evaluation (Total points: 25, Extra credit: 10)