CSE 590 TU: Image Understanding

Autumn 2002

CSE 590 TU: Homework Set 3

Content-Based Retrieval with Regions and Relationships

Software and Images
Download the software you need
Download the modified connected components code: conrgn2.c or ConnectComponent.java
Download the images you need: zip, tarred gzip
Download the image thumbnails: zip, tarred gzip, PowerPoint

(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, their attributes, and their simple spatial relationships.
  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. This requires a modified connected components algorithm that can handle all the cluster labels, not just 0s and 1s. Possibly perform some noise cleaning/merging operations to improve the regions. (Something that you can do the same for all of them.)
    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]
      • a few texture attributes (for example, those from the midterm are easiest)
      • centroid (row, column)

      • bounding box or other representation of where the region is
      • RAG (region adjacency graph). This should probably be represented as a set of adjacency lists, one for each node (region) in the graph.
    4. For each pair of (major) adjacent regions in the RAG, find and record the following possible relationships: inside, above_adjacency, below_adjacency, left_adjacency, right_adjacency, other_adjacency (if none of the others are satisfied by whatever requirements you impose to define them).
    5. Store the attributes and relationships 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 RELDIST(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. Basically, you will need to find the best correspondence between regions of I1 and regions of I2 by whatever algorithm you choose. (Keep it simple; a greedy approach is OK for basic assignment.) Then once you have the correspondence, you can develop the error in terms of region attributes of corresponding regions, missing or extra regions, and relationship errors.
  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 for the basic assignment.
  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:

What You Should Turn In

  1. A report that describes your system, including the exact motivation for and definition of your distance measure.
  2. 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 best 5 and worst 5 images returned 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.
  3. A concluding section of the report that discusses your results.
  4. Your commented code

Remember that you should put headers on all your routines with the following information: