This project deals with the problem of recognizing objects in images. The idea is that you have a model of a known object and want to determine if that object is present in a given image. Both the model and the image are represented as graphs, so the problem reduces to:

- determining if there is a subgraph isomorphism from the object graph to the image graph (for perfect matches), or

- finding the least-error mapping between the two graphs (for similarity matches).

Specifically, as input your will be given two undirected graphs (from a file):

the model graph GM = (VM, EM)

the image graph GD = (VD, ED)

GM represents a structural model of an object that may appear in an image, and GD represents a structural description of the image itself.

PART I

Your program should find all isomorphic copies of GM in GD using a backtracking tree search. When it finds a mapping {(i1,j1),(i2,j2),...,(iN,jN)} that is a valid subgraph isomorphism from VM to VD, it should print the mapping and continue searching for others. If it finds no copies of GM in GD, it should print "NO ISOMORPHISMS FOUND."

PART II

Your Part II program should look for the best (least-error) mapping from VM to VD. The mapping should be one-one, but it won't be onto, since VD has more nodes than VM. It should print the best mapping after the search terminates. (In case of ties, the best mapping is the FIRST of the least-error mappings found.)

Note: This program should be executable on its own, rather than by commenting out code from the program for PART I. Since there is expected to be a large overlap between the two, we strongly encourage sharing utility functions (e.g. for printing out a mapping, etc.).

Details

1. The graphs are undirected, the nodes of each graph are integers between 1 and the total number of nodes. The format of the input file is as follows:

Model Graph Name (character string)

NVM (number of nodes of VM)

NEM (number of edges of EM)

NEM pairs of integers (the edges of EM)

Image Graph Name (character string)

NVD (number of nodes of VD)

NVE (number of edges of ED)

NED pairs of integers (the edges of ED)

Example Input File

M1

3

3

1 2 1 3 2 3

D1

5

5

1 2 1 4 2 3 2 5 3 5

The output of PART I on this small input file would be:

ISOMORPHISM: (1,2)(2,3)(3,5)

ISOMORPHISM: (1,2)(2,5)(3,3)

ISOMORPHISM: (1,3)(2,5)(3,2)

ISOMORPHISM: (1,3)(2,2)(3,5)

ISOMORPHISM: (1,5)(2,2)(3,3)

ISOMORPHISM: (1,5)(2,3)(3,2)

Note that this tiny problem has so many isomorphisms, because the model graph is a tiny and symmetric structure, so there are 6 ways it can be mapped to the image graph. (Try drawing the two graphs.) The test data sets will, in general, not have so many possibilities.

2. You may decide on your own structures for representing the node sets, edge sets, and mappings required for the problem.
Warning: Keep in mind that if you pass a pointer to some list to a function and it changes the list somewhere deep into the recursion, then the list will be changed when it comes back, which is not what you want. So you must be careful what you pass and how you pass it. Also, be careful with memory allocation and deallocation. Careless memory management could cause disaster as the number of recursive calls grows.

3. For Part II, add another function to your program to find the least-error mapping from GM to GD.
(FORWARD ERROR ONLY) This can be done by a branch-and-bound tree search, which has two extra arguments:

map_err (the error of the mapping so far);

bound_err (the error bound of the least-error mapping so far).

For the tiny example above (with 6 isomorphisms), Part II would print out:

LEAST-ERROR MAPPING: (1,2)(2,3)(3,5); ERROR = 0

4. Documentation should include:

A header at the beginning of your code reporting TITLE, AUTHOR, DATE, AND PURPOSE and describing the structures you used to solve the problem.

A short header at the beginning of each function reporting TITLE, PURPOSE, and ARGUMENTS.

A short header at the beginning of each class reporting the TITLE and PURPOSE of the class.

A short paragraph explaining the algorithms you implemented.

Comments throughout the code to explain key sections of code.

5. Input graphs and required tests
The input graphs and their images can be found here.
Note: The same images (pictures) are given for your convenience in both PDF and PS formats.

Test PART I on all four data sets.
Test PART II as follows:

For the test1 data set remove edge (5,9) from GD and run it on the modified set.

For test2 run it as is, so it should find an isomorphism which will have a zero error.

For test3, remove edges (1,2) and (3,4).

For test4, run it as is.

6. Turn-in BOTH the commented program listing AND the output from each of the above tests.

Extra Credit up to 15% can be earned by adding intelligence to the searches and/or trying other search methods and comparing the results. Note, that extra credit only counts if it is in addition to, not instead of the requirements described above. You should fully solve the initial problem before proceeding to any extra credit endeavors.

Good luck!