ECE/CSE 576 Spring 2019 Homework 3: Content-Based Image Retrieval

Date Released: May 6, 2019

Date Due: May 17, 2019 (Friday) 11:59 P.M.

Late Date: May 19, 2019 (Sunday) 11:59 P.M. (Late Policy: 10% off per day)

Webpage and code last updated on May 6 at 1:30 pm.

Required files

Download the zip file here.

The zip file contains 3 folders. The 'Code' folder contains the code files, the 'Database' folder contain the database images (each of size 640 x 480) and the 'Thumbnails' folder contains the thumbnails (each of size 64 x 48) of the database images to be used to display the results. 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. If you want to adjust your application window or text font size for better viewing, refer to the commented lines in the main.cpp file.

(1) 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.
(2) Under 'Projects' tab -> 'Run Settings' (Click 'Run' under 'Build and Run' in the left pane), select the 'Code' folder as the current 'Working directory'.
(3) This homework deals with images in QImage format.

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 RandomSeedImage clustering code is provided in the starter code. You are free to tune its parameters or use a better clustering algorithm from Homework 1. Note: The Clustering() function uses QImage format of the input image and returns an image with each pixel value replaced by the cluster number (not the mean RGB values of the cluster) the pixel belongs to.
    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. Perform some noise cleaning/region merging operations to improve the regions. Don't vary any parameters between images. You can define a threshold in terms of number of pixels in a region and then either ignore regions smaller in size than the threshold or merge them with adjacent (ideally largest) neighboring 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) and use grayscale version of the image):
        1. energy
        2. entropy
        3. contrast
        Note: You have to first create a Gray-level Cooccurrence Matrix (GLCM) for each region and then compute the above features. While creating GLCM with diagonal pairs (d = (1,1)), if the neighboring pixel lies outside the region, ignore that pixel pair. For faster computations and less memory requirement, create 8 x 8 GLCM where 0-31 pixel values are mapped to value 0, 32-63 mapped to value 1 and so on.
      • centroid - mean row and column values of the pixels in the region (no starter code)
      • bounding box or other representation of where the region is - e.g. x and y co-ordinates of the corners, area of the rectangle etc. (no starter code)
    5. Store the attributes in the given data structure (see starter code). Make sure you normalize each feature (easiest is min-max normalization), preferably to the range [0,1], individually before storing them, otherwise different features will have different importance. 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. Don't use L1 and L2 (or any two Lp distances) as 2 different measures, there won't be much difference in the results. If you use one of them, preferably use a weighted version, with different weights for different features based on importance. You can use different weights for different query images, but write them with reasons in your report. You can refer to this article for possible ideas.
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. You can click 'Load database' first and then 'Open Query Image' or vice versa. 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.

The query image will have distance zero (or close to zero since random clustering results in different features for the same image when loaded as query and when loaded as part of the database) 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 functions. 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 check these out with the starter code to see how the buttons function and what to expect from your code. The code takes some 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.

Useful tip: To debug through your feature extraction code, just perform 'Open Query Image'. 'Load database' essentially performs the same operation as 'Open Query Image' but on all 40 images instead of one. So if your code works fine on one, you are good to go. If you want to check your implemented features individually, just comment out the others and use one at a time.

In order to test your system, use the following images as the query image:

Example Query Results for cherry_2 (screenshot of application window; you should submit similar screenshots) (Note: The result is obtained with the starter code + Euclidean distance measure. This is kind of an ideal result where all cherry images are the top retrieved images and similar images are also positioned together. It just worked for cherry images, but you need to get at least 3 images from the same category as the query image among the top 5 retrieved images for every query image. It's better if the 3 images are the top 3, and even better if you get 4 out of 5.)

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: Your code should be well-structured and well-commented. In case you edit any other file, mention the edit in your report at the beginning (you can put in edited code snippets as well). Upload the necessary files 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)