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.