Harvey Mudd College
Computer Science 153
Assignment 3
Due Friday, October 13, by midnight

Back to Assignment 3, top-level page

Section 1: Statistical Object Recognition

This section asks you to create an object-recognition system (based on the color distribution of objects) and test it out on the images gathered (and to be gathered) by the group as a whole. (I'll contribute some spam images.)

A color-based object recognition system

In the directory

/cs/cs153/Images/a3/ModeledObjects

parrot1.jpg
parrot2.jpg
vac1.jpg
vac2.jpg
...

<imagename>.info

• The name of the file
  
  
• A one-word name of the dominant object in the image
  
  
• The bounding box of the dominant object, as upperleftx, upperlefty, lowerrightx, lowerrighty, respectively.
  
  
• Other descriptive words about the object or scene
  
  
• Any further comments by the photographer
  
  

parrot1.jpg
parrot
1 1 165 224
outdoor, man-made
by Ross Luengen

fid = fopen('/cs/cs153/Images/a3/ModeledObjects/parrot1.info','r');

filename = fgetl(fid);                  % fgetl gets a line w/o the '\n'
objectType = fgetl(fid);
boundingboxline = fgetl(fid);
bbox = sscanf(boundingboxline,'%d');    % gets a matrix of the values present

fclose(fid);

Generating Histograms You'll need to decide two things to start off: the color space in which you'd like to histogram the objects, and how you want to divide up that color space into bins. You might use RGB, HSV, some combination of the two, or a homemade approach. Once you decide on a colorspace and a strategy for binning it, create and plot at least one histogram of an image using that division of colorspace; include the results (and a brief explanation) here. Keep in mind that you may not want to divide colorspace uniformly along its axes.

Object Models Next, you'll need to decide exactly what will constitute the model of an object. This problem is based around histograms, yes, but there are a variety of ways to use histograms to model, say, a "parrot." The simplest would be to take a single parrot image and use its histogram as the model for parrots in general. Or, you may want to combine the information available from additional images -- for example, by averaging. Alternatively, there may be information you don't want to use in your model of an object: for example, you might considering a more careful hand-segmentation of the objects when creating your object model.

Ultimately, you should have a function or script that will create an object model, given an image/images or, if you prefer, a list of pixels (or several lists of pixels, coming from several images). Include your object-modeling code, along with a brief explanation and description, below:

Model matching The final piece to your system is a means for comparing two object models to determine how similar they are. For this you might use histogram intersection (higher match scores then indicate better matches), perhaps with a scale factor used to eliminate any effect from the image size of the objects matched against. A second approach we considered was a histogram distance function, perhaps using a weighting matrix to allow partial matches among similar colors. In this case, low distance (small match scores) would indicate close matches of models. Again, consider a scale factor to eliminate any dependence on absolute image size.

Still another option is to investigate the Earth-Movers' Distance as a measure of the similarity or differences between two color distributions. This would constitute the extension to assignment 3, if you wanted to pursue it. A link to a C version of the code is at this site. Yossi Rubner's papers (including the one introducing the EMD) are available from here. See the Possible Extensions section for additional suggestions.

Regardless of how you choose to match object models, you will want to try matching several to see how it performs. In addition to the ModeledObjects directory, there is also a sibling UnmodeledObjects directory you may want to use to test histogram comparison. Don't use the UnmodeledObjects, however, to build the object representations, as there needs to be some independent data for use in testing the final system. As you test, you may want to consider a criterion for a "reject class," i.e., a class for objects that do not match any of the 12 modeled ones well.

Putting the pieces together

Once you have a strategy for creating object models and comparing them to each other, create and store models of your 12 (or more) objects in

/cs/cs153/Images/a3/ModeledObjects

/cs/cs153/Images/a3/UnmodeledObjects

1. The name of the image file
2. The name of the object that your system considers the closest match (or "reject")
3. The match score

In addition to these results, comment briefly on the strengths and shortcomings of your object recognition system. Include at least one misclassified image and how the system might be changed to prevent at least that type of misclassification.

Possible Extensions

• Each step of this section would be well served by a tool that visually summarized what was happening or that allowed changing parameters on the fly. For example, an interface could display an image on one side of a window and variable bin definitions with sliders or text fields in the center of that window. Then, with each confirmed update, a new histogram could appear on the right. More simply, a true-color histogram in HSV space, would be nice to have. (You'd need to use the built-in patch command, I believe.
  
  
• As mentioned above, investigating the Earth-movers' distance is a possible extension of this assignment. In fact, that metric allows comparisons among arbitrary distributions, rather than similarly-binned ones (as histogram distance and intersection require).
  
  Because of this, you could automatically histogram images -- for example, with K-means analysis that finds clusters in color space and creates bins around those clusters. This would prevent the problem of having the definition of a histogram bin cut a particular color region in half (as happened with the cyan and blue bins dividing up a single region of Ross's parrot, for example).
  
  
• On a completely different note, you might consider a problem mentioned in the Fourier analysis section of Asignment 2: art identification. Now, rather than using frequency characteristics to distinguish works (or genres) from one another, you could use a color signature. More generally, you might consider defining a measure of "colorfulness" -- perhaps the uniformity (entropy) of a color histogram -- and use that measure to classify works by, say, Mondrian (or Rothko) against those by earlier artists.
  
  
• Another project would be to use color classification of pixels in order to create "photomosaics": an overall image comprised of many very small images. Several nice examples are here. The basic idea would be to choose an image you'd like to mosaic, divide it into a relatively fine grid, find the color distribution of each grid element, and then seek out an image that has that distribution.
  
  
• Rather than seeking individual objects, consider adapting your system to distinguish between outdoor and indoor scenes (the keywords later int he .info files offer this information. Another distinction to pursue might be natural vs. manmade objects. Create a system that classifies input images into one of two categories, based on the color properties of those images.

  For this extension, you may want to use whole-image histograms, rather than the histograms of only the prominant objects in those images.

On to Section 2: OCR and Structural Pattern Matching