Spring 2000

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 graphs, so the problem reduces to determining if there is a subgraph isomorphism from the object graph to the image graph (for exact matches) and to finding the least-error mapping (for similarity matches).

Your program will input two nondirected 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

Part II

Details

1. The graphs will be undirected, the nodes of each graph will be integers from 1 to the number of nodes. The format of the input file will be 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 for Part I for this small problem 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 2 graphs.) The test data sets will not always 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. Keep in mind that if you pass a pointer to a 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.

3. For Part II, modify 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) and bound_err (the error bound of the least-error mapping so far). Instead of failing and backing up when it encounters an error, it keeps track of how many errors the mapping has in map_err and only backtracks if map_err becomes greater than (or equal to) bound_err. Furthermore, whenever it gets to a leaf-node with a full mapping that has less error than bound_err, it changes bound_err to this new lower value, saves the mapping, and continues the search. It prints out the least-error mapping and its error at the end of the search. One least-error mapping is sufficient.

4. Documentation should include:

A header at the beginning of the code that gives TITLE, AUTHOR, DATE, AND PURPOSE and describes the structures you used to solve the problem.

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

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

Commenting throughout to explain each section of code.

Test graphs and their pictures can be found here. 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 zero error. For test3, remove edges (1,2) and (3,4). For test4, run it as is.

Extra Credit up to 15% can be earned by adding intelligence to the searches and/or trying other search methods and comparing the results.