Chris McDonald
CS641 Midterm Question B
            
            A Review of Spatial Color Indexing Using Rotation, 
              Translation and Scale Invariant Anglograms*

Introduction
	The problem of similarity-based image matching is a complex one, and a 
substantial area of open research.  A user has a sample image, and wishes to retreive 
other images in the database that are similar to it.  But how should the notion of similiarity be defined?  Many approaches have been proposed and tried, and the fall into several general categories:
  
  - Annotation Methods - these methods require human intervention to annotate the 
images with textual data.  This text data is then referenced when searching the data.  The obvious disadvantage here is the amount of work required to create and maintain effective annotations on a large database of images.  	
  - Histogram Methods - these methods compile a histogram of the color content of the
image.  If 2 images have similar color histograms, they are considered similar.  The color histogram of an image is a fairly weak measure of its content, however.  For example, a picture of a beige computer and a picture of a person in a beige dress have little in common, yet will have a similar color histogram.  In a large database you are bound to get collisions of this sort, where very dissimilar images will be evaluated as highly similar.  
  - Feature/Object Methods - These methods attempt to extract features or objects from 
the image.   Features and objects the appear to be similar in size, shape and orientation
in 2 different images suggest the images are similar.  
  - Transformation Methods - These methods define similarity by how inexpensive it is to
transform one image into the other.  This is a very powerful idea, but how to put it into 
practice in a straightforward and efficient way is still unclear. 
  - Spatial Color Methods - These methods partition the scene into regions, and then by
evaluating the color content of the regions and their spatial relationships, attempt to build a similarity model. 

The authors propose a new spatial color-based similarity heuristic, based on a data 
structure they call an anglogram.  This is similar to a histogram, except that it counts how many angles of a given degree range fall in each bin, instead of color values of a given color range.  Details of how this anglogram is constructed and why it is a useful device for determining image similarity follow.

Method Overview
	First, the image is decomposed into a number of mxn pixel sub-regions.  For
each sub-region, an average hue, saturation and intensity rating is determined.  Next
a Delauny triangulation of all sets of regions with the same hue, saturation or intensity
is performed.  Each region is treated a a vertex at the region center.  Then we consider,
for each hue, saturation and intensity value, the set of vertices that have that value.  We
find the Voronoi diagram of that set of vertices, and then take the dual of that graph to
get the Delauny triangluation.  The details of constructing the Voronoi Diagram are 
described in the paper and aren't worth going into here.  The reasons for constructing a Delauny triangulation are described in analysis below.

The angles formed by these Delauny triangulations are placed into bins by degree size -
18 bins, each of width 10 degrees.  This creates an anglogram, a vector that holds the number of angles in the image of each size category for each hue, saturation and intensity value.  These anglograms are stored with each image in the database.

Similarity is determined by intersection.  Each anglogram in the sample image is 
compared to each anglogram in the candidate image.  The ratio of number of matching 
angles to total angles is the degree of similarity.  For example, if for hue 1, the sample 
image has 5 angles of 0-9 degrees, and the candidate image has 3 angles of 0-9 
degrees, there is an 80% match in that bin.  The various values can also be weighted.  
Hue might be given a stronger weight than intensity or saturation, since the eye is more 
sensitive to color hue than to saturation or intensity.

Analysis
	The Delauny triangulation has the useful property that its angles are invariant 
under any uniform rotation, scaling or translation of its vertices.  This is the crucial 
property of the anglogram, a property which feature/object based methods and other 
spatial color methods lack.  For example, a picture of airplane flying level 50' away and a picture of an airplane flying up at 45 degrees 500' away would look very different to a 
method that is comparing the size and orientation of features, or one that relies on
matching overlapping regions of color.  The anglogram handles this quite nicely.  Since 
the relative angles of the various color regions of the airplane will still be the same, it will 
have a similar Delauny triangluation, and hence a similar anglogram.  

This conclusion is borne out fairly well by the experimental results presented in the paper.   The authors compared their technique to two other spatial color-based methods, using 2 different databases - one of  2008 outdoor images, and one of 1380 earth and space science images.  The authors defined the effeciency of retrieval as the number of images similar to the test image retrieved over the total number of images retrieved.  What images are considered similar are defined a priori for a given test image.  

The first method compared against is the Color-WISE system, developed at Wayne State University.  This system divides the image into fixed-size blocks, much like the anglogram system, then indexes each block by its dominant hue and saturation values.  

The second method compared against is the color autocorrelogram approach.  A 
correlegram of an image is a table indexed by color pairs <i,j> and a distance k.  The 
entry at a given position is the probability of a pixel of color i being k distance from a pixel of color j.  An autocorrelegram only considers pairs where i and j are the same color, greatly reducingthe size of the table.  

The image query for the outdoor image database was a pyramid.  The image query for
the space image database was a rocket launch.   The anglogram did much better than
the other two methods on the space image query - generally 20-30 percent better than 
Color-WISE and 10-20 percent better than the correlogram.  Looking at the results 
provided in the paper, the reason is obvious - the database contains a number of images of the rocket launch from further away, with the rocket higher in the sky or with the rocket at a different angle.  Since the anglogram is invariant to these transformations, it recognizes these images as similar more easily than the other methods.   The pyramid query, on the other hand, was more or less even.  The anglogram performed slightly better in some cases, but generally the same as the other two methods.  Again the reason is fairly apparent from the results.  The database contained a wide array of images, most having nothing to do with pyramids, and in those that did, they pyramid was generally fullframe and upright, just as in the query image.  The anglogram provides no particular advantage in this case.

Conclusions
	The anglogram provides a useful addition to the field of similarity-based image retrieval.  It captures new information (the angles between areas of the same color in an image) and uses that information to capture similarties not easily recognized by other techniques - the rotation, scaling and translation of objects in the image.  

It is not, of course, the ultimate solution to the image retrieval problem.  First of all, it is 
still vulnerable to false positives.  For example, the pyramid image retrives a man in loose, brown-colored clothing.  Because his loose clothing makes a vaguely triangular shape, he is considered similar to the pyramid.  Similarly, a rectangular monument viewed corner- on appears to have a triangular shape due to the perspective effect, hence i is returned as similar.  Also, the anglogram only contains 2-dimensional angle information, and hence can only recognize rotations in the image plane.  This works out well in the sample images, since both the pyramid and the rocket are basically symmetrical about their vertical axis - viewed from any side they appear the same.  But the anglograms would not be helpful in recognizing a car viewed from the front as similar to the same car viewed from the side - its anglogram will be distinct.  This problem can't really be solved without 3D information about the scene captured in the image, but it is worth keeping in mind.

Nevertheless, anglograms have already shown experimental success, and have the 
potential to be a useful tool in image database systems.