Page d'accueil Description du projet Project Description (english)

Correspondence Graphs

Fast Access

Comments

  1. Objectives

    2. This small graph library solves a very common problem in robotics: the data association between observed data, and some reference in memory. Let's take an example: assume that we have a robot equipped with a camera and moving in a building. To localise this robot, we implement some door detection capability. One doors have been detected, they have to be identified, i.e. we have to find which doors are visible. Because all the doors look similar, we have to identify our doors together, or as a set. This is what a correspondence graph solves.

  2. Example

    3. Let's assume that the environment is represented by the following schematic:

    Environment :

    So, we have, in memory, a map of the position of all the 21 doors.

    Global map:

    Let's assume now that the robot is represented by a disc R, oriented toward the arrow. The red doors are the one visibles from this position of the robot.

    Visible doors:

    Once the door position detected (in the robot frame), we get a local map, as illustrated below:

    Local map :

    The problem is to identify the doors visible in the local map.

  3. Principle

    4. Using a correspondence graph provides a reliable solution to this identification problem. In such a graph, nodes are potential data associations (a node represent the association of "Door 1 -- Door IV"). Then we add an edge between two nodes of the graph if they are consistent with one another. For instance, the distance between Door 14 and Door 6 is the same as between Door I and door IV in the local map. Nodes (14,I) and (6,IV) are consistent, hence we add an edge between them.

    Once the edges added to the graph, we look for a subset of nodes, with maximal size, such that all the nodes in this subset are consistent with each others. This subset is called a complete graph or a clique: all its nodes are connected to each others.

    Problem: The search for a maximal subset of noded (or a maximal clique) is a NP-complete problem (i.e. very very hard to solve) in the general case. Nevertheless, if our consistency criterion is sufficiently discriminative, the resulting graph is sufficiently simple to allow for finding a maximal clique in a time compatible with a real-time implementation.

    The objective of this library is to implement a graph representation and an algorithm that search for a maximal clique. This algorithm is inspired from the indications found on the web site: The Algorithm Design Manual.

    Note: This algorithm is not at all memory efficient. So, when possible, it is recommended to make a pre-selection of potentially visible landmarks (Doors) knowing a initial guess of the robot position. This will reduce the size of the graph, and the amount of memory required to process it.

  4. Search for a maximum clique

    5. The search is done in two stages: First we search a maximal clique (i.e. local maximum), then we search if we can find a clique bigger. At each step, we reject any nodes whose degree is not compatible with being part of the maximum clique. The resulting algorithm is:

    In this algorithm, the tricky bit is the line marked with (***). This is where we have to enumerate all possible cliques and test them. This is very expansive in a very dense graph and if the maximal clique is not maximum.

Demonstration

File "graph"

Running "make test" build a graph from the file "graph": 
8
5	1	3	4	5	7
3	0	6	2
2	1	6
4	0	4	5	7
4	0	3	5	7
4	0	3	4	7
2	1	2
4	0	3	4	5
The format is given below: 
<Number of nodes>
<Node 0>
<Node 1>
...
<Node n-1>
Where each node is defined by a line such as: 
<Number of neighbours> <adjacent 0> <adjacent 1> ...
The graph we use here is:

Results

Results Comments 
Printing
#Vertices : 8
0 : 5 connection :  1  3  4  5  7 
1 : 3 connection :  0  2  6 
2 : 2 connection :  1  6 
3 : 4 connection :  0  4  5  7 
4 : 4 connection :  0  3  5  7 
5 : 4 connection :  0  3  4  7 
6 : 2 connection :  1  2 
7 : 4 connection :  0  3  4  5 
Converting
 .  X  .  X  X  X  .  X 
 X  .  X  .  .  .  X  . 
 .  X  .  .  .  .  X  . 
 X  .  .  .  X  X  .  X 
 X  .  .  X  .  X  .  X 
 X  .  .  X  X  .  .  X 
 .  X  X  .  .  .  .  . 
 X  .  .  X  X  X  .  . 
Highest degree : 5
Maximal clique
{ 0  3  4  5  7 }
Maximum clique
{ 0  3  4  5  7 }



Graph display







Display of the graph using
an adjacency matrix







Maximal degree : 5 --> Node 0

The search for a maximal clique
gives immediatly THE maximum
clique.

Result visualisation

Sources

  1. TAR.GZ archive

    2. As all the sources on my web page, this archive should work "as-is". 
    > tar zxf matchGraph.tgz
> cd matchGraph
> make
> make test

  2. Files