CMSC 341 Spring 2009
Project 4

Assigned	Sunday, April 12, 2009
Due	11:59pm, Sunday April 26, 2009
Updates	The definition of similar is two images with the same Average RGB values. Not all images that may be at index Ri,Gj,Bij. The same image shares the name and Average RGB values.
	The table should grow in 3 dimensions when the table needs to expand.
The insert method for the HashTable should take a HashTableObject based upon the string. This change has been reflected in the description.

Objectives

To implement a hash table ADT from scratch
To design a hash function for multiple dimensional data
To create and extend ADTs to serve a particular purpose
To make sound design choices
Optionally, to create an interactive GUI

Overview

In many fields of research there are many applications for categorizing objects based on different measurable data. For instance you may want to categorize people based on height, weight, age, and salary. Each attribute counts as a certain measurable identifier of an object. Images have similar measurable qualities when we consider the color of a pixel and the effect it has on an image. If we look at each image, we relate the colors in a picture to the color of the image. This "average" color of an image can be used to classify images

In this project, you will implement a image classification and retrieval system, using a hash table to store images based on average color to allow a user to view images based on their color classifications. Your base program will execute from the command line and run until all commands have completed. Graphical display and interactive control of the image queries are available extra credit options.

Project Specification

Your project will create the basic infrastructure for an image retrieval system. This system should be able to search for X and return it and any Y images that closely resemble the queried image. You are to write a hash table from scratch implementing all required functionality associated with the hash table. As well as mimicing the following representation of a 3 dimensional data set in a 3 dimensional hash table.

This image sequence shows the path your hash function should move through the 3D hash table based on Red/Blue/Green channels. Based on X,Y,Z produced from your hash function, X corresponds to R, Y corresponds to G, and Z corresponds to B.

Your project must execute the following instructions:

INSERT string - adds the PPM image at the strings location to the hash table printing the number of collisions that have occured
DELETE string - delete the PPM image at the strings location to the hash table printing the number of collisions that have occured
QUERY string - finds the PPM image and all other images which appear similar to that image

Command Line Arguments

file.txt - a file containing commands to execute for the project
x - an integer defining the initial height of the hash table
y - an integer defining the initial width of the hash table
z - an integer defining the initial length of the hash table
-g - a flag that may or may not exist to enable your extra credit gui

The ADTs

The following ADTs must be implemented.

HashTableObject

The hash table object is an entry in your hash table which contains the following information:

filename - an absolute path to a specific ppm image
red - an integer accounting of the average of all pixels in the image red channel
green - an integer accounting of the average of all pixels in the image green channel
blue - an integer accounting of the average of all pixels in the image blue channel
hash(x,y,z) - which produces a 3 dimensional key based on the red/green/blue data stored and the hash table size
init() - calculates the values for red/green/blue

You will need to design a hash function, which takes an image and computes a key based on the average red/green/blue values. This key should be a set of 3 keys (x,y,z) that when used as indexes by the hash table will produce a unique location for this image. Calculating the red/blue/green values will require you to read all the pixels from the PPM image and calculate the average amongst all red/blue/green components per pixel.

HashTable

The hash table is a 3 dimensional hash table. However, it still follows the same principles as a one dimensional hash table. You will need to implement this structure from scratch with the exceptions you may use java's array list and linked list structures. You are to handle collisions with seperate chaining. Your hash table should have methods which accomplish the following:

insert(HashTableObject ) - inserts a HashTableObject created from the image at a string's location. If the table is more than 60% full you will need to rehash your table
remove(HashTableObject ) - removes the image from the hash table based on a string's location.
find( string ) - searchs the hash table for the required image printing out a successful find. This function will also print out a list of images which closely resemble the intended file.
collisions() - returns the number of collisions that have occured in the hash table
rehash() - increases the size of the hash table rehashing every image in the old table

Project Notes, Hints, and Requirements

Your project must adhere to basic good design principles, including (but not limited to) appropriate abstraction and encapsulation, logical control flow, reasonably efficient use of memory, and basic computational efficiency.
You must implement your HashTable class from scratch, with nothing but Object, primitive types, explicitly approved classes, or classes you develop from scratch yourself as a superclass of HashTable or any data elements of HashTable. For the purposes of this assignment, you may use ArrayLists, but other containers and sets are not allowed.
In the interests of reusability, make your HashTable class as general as practical. Specifically, your hash table should be uncoupled from the items stored in it.
The PPM image format follows the same PPM format from project 1.
Project questions will be in your repository as well.

Extra Credit

There are MANY interesting ways to extend your base project. Indicate any items of extra credit that you did in your README file. This will allow the TA to look for that additional functionality when grading your project.

Add a GUI display to your program. Your GUI should allow the user to view image based off finds given a string as well as all images which are closely related. You GUI must also allow users to remove and insert new images based on a string containing the files location and name entered by the user. (MAXIMUM of 10 points)

Submission

You must use CVS to check out your module in the Proj4 repository and to check in your code. That must include an ant build.xml file and javadoc. The grading scripts will issue commands like the following, so be sure that your build.xml supports them:

  ant
  ant doc
  ant -Dargs="arguments go here" run

See the projects page for more information on all of these topics.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.

CMSC 341 Spring 2009 Project 4