Programming Assignment 1 - Affine Hashing

Due Date

See the assignment turn-in page (last modified on 16 October 2007) for instructions on turning in your assignment.

Background

Given a pair of characters from a Hershey font, the character-recognition problem involves determining whether the pair of characters is the same. If the two characters are from the same font, the determination is fairly simple problem: order the points in each character in some standard way, then compare the ordered list of points.

Character recognition gets a bit harder when some of the points may be missing from the one of the characters. The previous solution has to be extended to determine if one of the point lists (the smaller) is a subset of the other (the larger). We can label the character with the smaller point list the distorted character and the other character the normal character. The distortion occurs relative to the larger character; the distorted character may be a perfectly formed character (A ‘Z’, say), but relative to the other character (an ‘M’, say) it’s distorted. If both characters have the same number of points, we can arbitrarily pick one as the distorted character.

The character recognition problem gets involved when a character, in addition to having missing points, has undergone the rigid-body transformations rotation and scaling (rigid-body transformations are also known as affine transformations). Now the points in the character are completely different from the points in the other character and a simple point-list comparison fails. However, because the transformations were rigid-body, the geometric relations among the unknown points still hold, and that is the key to implementing character recognition.

To solve character recognition with missing and transformed points, both characters should be placed in canonical (or standard) form; this eliminates variations and provides a consistent basis for comparison. The usual canonical form is to pick two points from a character, say the first and last points or the first and second points, and form a line segment S between the two points. Then transform (that is, rotate and scale) the character so that S co-incides with the unit segment on the Y axis.

Given a pair of characters, one of which is normal and the other of which is possibly distorted and possibly different from the normal character, recognition proceeds by putting the distorted character in canonical form and comparing the results to the normal character in canonical form using the approach given for recognizing unknown characters with untranslated but possibly missing points described above.

There is a problem, however: which two points in the normal character should be chosen to form S, the line segment transformed to the unit interval on the Y axis? To find a match between two characters, the same two points for S have to be chosen on each character (this is why it’s important to put the distorted character into canonical form fist). And the points in the characters character can be in any order, so it’s impossible to say, for example, which are the first and last points.

The solution to this problem is to use brute force: examine all possible pairs of points in the normal character. Put the normal character in canonical form using each pair of points, and compare the now possibly canonical character to the distorted canonical character, keeping track of the best match found so far.

This solution, although it works, is expensive: there are O(n²) possible canonical forms for a character where n is the number of points in the character, each of which has to be compared to the canonical distorted character. This is where affine hashing comes in.

In affine hashing, the distorted character points, in canonical form, are stored in one or more hash tables. The points of each possible canonical variant of the normal character are hashed into the same tables; collisions indicate possible matches. After all the points of a canonical version of the normal character are hashed, the number of matching points gives an indication of likelihood that the distorted and normal characters match.

The Problem

Input

void trial(double ** normal, double ** distorted);

which stores into each pointer reference an array describing a letter. Each letter returned is randomly selected from the available letters; your program has the task of determining if the two letters returned by trial() are the same.

The contents of the normal array are a complete and correct description of the points in a letter as given by the font. The contents of the distorted array are also the points in a letter given by the font; however, the points may have undergone any of the following transformations:

1. The points may have been scaled by an arbitrary factor.

2. The points may have been rotated about the origin by an arbitrary angle.

3. Some subset of the points may be missing.

Both arrays returned by trial() have the same format, so only the normal will be described.

• normal[0] is the number of points in the character.

• normal[2*i + 1] is the x coordinate of the ith point for 0 ≤ i < normal[0].

• normal[2*(i + 1)] is the y coordinate of the ith point for 0 ≤ i < normal[0].

Both arrays should be freed by the caller when no longer needed. The program you submit should call trial() exactly once; your program may call it as many times as necessary while you develop and implement your code.

You can find the files letters.h and letters.cc in the /export/home/class/cs-306/a1 assignment directory. These files should not be included in the files you turn-in.

Output

int results(int same_characters)

with a non-zero value if your program has determined that the two characters received from trial() are the same or 0 otherwise. The return value from results() indicates if your program’s determination is correct (a non-zero value) or incorrect (0).

The program you submit should call results() exactly once; your program may call it as many times as necessary while you develop and implement your code.

Testing

double * normal(char c);
double * distorted(char c);

return an array describing the given letter c, ‘A’ ≤ c ≤ ‘Z’. The array has the format given above and should be freed by the caller when no longer needed.

These procedures are for your convenience when developing and testing your code. The program you submit should not call either of these procedures.