Advanced Artificial Intelligence
Programming Assignment 2
Image recognition

Assigned: Nov. 12
Due: Dec. 10

The input file for this assignment contains line drawings of six simple figures, subjected to a random rotation, scaling, and translation, and depicted on a 16X16 pixel array. The six basic drawings are: (1) a square; (2) a 4X6 rectangle; (3) an acute isoceles triangle; (4) an obtuse isoceles triangle; (5) a hexagon; (6) a letter A.

Your assignment is to write a program that reads a series of such inputs, determines which figure is depicted; and writes the corresponding number to standard output. For instance, if your program gets the input shown below, it should identify it as the letter A.

. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . O O . . . .
. . . . . . . . . O O . . . . .
. . . . . . . O O O . . . . . .
. . . . . . O O . O . . . . . .
. . . . . O O . . O . . . . . .
. . . . O O O O O O O O . . . .
. . . . . . . . . . . O O O . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .

Details:

The basic figures are as follows:

The transformation applied is: First, a scaling by a factor randomly chosen between 1.0 and 1.5. Second, a rotation by an angle randomly chosen between 0 and 2 PI. Third, a translation randomly chosen to place the figure in the range from 1 to 16 in both dimensions. Note that the entire figure is always visible in the image; you do not have to worry about cases where it leaks off the edge.

Format of the data file. Figures are separated by three blank lines. Each figure consists of 16 lines of 32 characters each. A line of the figure is a row of the array. A pixel with value 1 is represented ``O ". A pixel with value 0 is represented ``. ''.

Grading the assignment: Partial credit will be given for partial success. If your program is successful on a fraction p of the test examples, then the grade will be computed as (6/5) x (p - 1/6) x 85% + 10% for quality of code + 5% for comments. (Note that one can achieve a success of 1/6 by guessing randomly; hence credit is only given for success rates higher than that.)

Method: You can use any method that works.

Your code is supposed to work for all transformations within the scope specified, not just on the examples in the data file. Beyond that, you need not shoot for any kind of generality. Your methods do not have to generalize to other line drawings, or to larger or smaller images. If you want to write a special routine for each of the six figures, that's fine. If you want to create a hash table with all possible depictions of all the six figures, that's fine. (I'm not recommending either of these, and I don't in fact think the second is possible in practice.)

Extra credit: Get your code to work on some substantially larger class of figures or transformations. (You may want to use a larger image.)