It is often the case in the field of computer vision that the matching of relational structures becomes an important part of solving a given problem. It is often desirable to rephrase vision problems as a graph theoretic one, which is able to be tackled using powerful mathematical methods already developed. Given an image it is often the case that we would like to match the features in an image to features in some given model/s. The matching of such relational structures can often be handled by casting it to the problem of finding a maximal clique in an association graph.
An association graph is an abstract graph that is generated from model features in the original image. The graph is formed by creating nodes from each compatible pair of scene and model features and inserting arcs between nodes if they have equivalent relations expressed as arcs.
This diagram shows an example of a scene and its association graph. The graph represents connections between the linesin the image in an abstract way. Given an image, an arc is established if two conditions are satisfied. The corresponding features in the scene and model are connected within some given error parameter and if the angle between the two segments is within some acceptable range.
A vertex labeled graph consisting of the set of vertices V and the set of edges E is denoted by G(V,E). A clique of graph G is defined as a complete subgraph in G. That is to say, that each point in the subgraph is connected to each other point. The maximal clique in graph G is the clique of G whose cardinality is not smaller than that of any other clique in G.
There are many different algorithms for finding a maximal clique in a graph that work well. The crucial factor is that solutions to the maximal clique problem, reveal information about the image and model. The solutions to the maximal cliques problem reflect the constraints specified in the model.
In the association graph above the maximal clique has 3 nodes - {k,l,m} as each of these nodes is connected to every other one.
The problem of finding a maximal clique in a graph is NP-Complete as there follows a reasonably simple reduction from SAT to the k-clique problem. This means that there is unlikely to be a polynomial time algorithm in the worst case for this problem (unless P=NP). This leads to exponential runtime as the input size increases although smaller models are tractable with modern computing power.
For more information, please see Recognition Approaches for more general approaches to recognition.
Graham Allison, s0199693@sms.ed.ac.uk