Main Page   Compound List   File List   Compound Members   File Members   Related Pages  

MatchCost Class Reference

Object used by GraphManipulator to perform sub-graph matchings according to a parametric similarity model. More...

#include <MatchCost+.hh>

List of all members.

Public Methods

 MatchCost (SubGraph *Graph1, SubGraph *Graph2)
 constructor Allocating memory and creating a Divergence object.

virtual ~MatchCost ()
 destructor desAllocating memory.

void FixCostFuncWeigths (float weightMTinTLDiff, float TL1TL2Div, float flowDiff, float divDiff, float MIDiff, float divMTaMTbCost, float timeDiff, bool meanCalcul)
 This method introduce in the similarity model a given parameter vector. This method fixes also another parameter specific to the matching calculus. More...

void UpdateGraph2 (SubGraph *Graph2)
 Method to update the pointer to a new candidate SubGraph Object.

float InexactMatchCost (int nbMiniBranches, SearchTree *searchTree, float *costs)
 Method to match the reference sub-graph with the candidate sub-graph based on the parametric similarity model. More...


Public Attributes

float factor_weightMTinTLDiff
 parameter weighting the population of each nodes.

float factor_TL1TL2Div
 similarity model parameter weighting the nodes' distribution.

float factor_flowDiff
 similarity model parameter weighting the flow of pixels exchanged between nodes.

float factor_divDiff
 similarity model parameter weighting the change in time of the nodes' distribution.

float factor_MIDiff
 similarity model parameter weighting the intra-node change in time.

float factor_divMTaMTbCost
 similarity model parameter weighting the interaction of the 2 MT classes (only if 2 MT class are consideredper sub-graph).

float factor_timeDiff
 similarity model parameter weighting the time lattice on which the sub-graph is defined.

float meanCalculation
 mean calculation '1' or Kullback-Leibler divergence '0' used in the matching nodes and edges comparisons. More...


Private Methods

void LoadTL1TL2MeanCov (int time, int nodek1, int nodek2)
 method to load a node of the reference graph at time sample (t) and a node of the candidate graph at time sample (t).

void LoadTL1MT2MeanCov (int time, int nodek1, int MTk2)
 method to load one node of the reference graph at time sample (t) and a MT class node related to the candidate graph at time sample (t).

void LoadTL2preMT2MeanCov (int time, int nodek1, int MTk2)
 method to load one node of the candidate graph at time sample (t) and a MT class node related to the candidate graph at time sample (t-1).

void LoadpreTL2MT2MeanCov (int time, int nodek1, int MTk2)
 method to load one nodes of the candidate graph at time sample (t-1) and a MT class node related to the candidate graph at time sample (t).

void LoadpreMT2MT2MeanCov (int time, int preMTk2, int MTk2)
 method to load a MT class node related to the candidate graph at time sample (t-1) and a MT class node related to the candidate graph at time sample (t-1).

void LoadMT1aMT1bMeanCov (int time, int MTk1, int MTk2)
 method to load a MT class node related to the reference graph at time sample (t) and a MT class node related to the reference graph at time sample (t).

void LoadMT2aMT2bMeanCov (int time, int MTk1, int MTk2)
 method to load a MT class node related to the candidate graph at time sample (t) and a MT class node related to the candidate graph at time sample (t).

void LoadTL1preTL1MeanCov (int time, int nodek1, int preNodek1)
 method to load a node of the reference graph at time sample (t) and a node od the the reference graph at time sample (t-1).

void LoadTL2preTL2MeanCov (int time, int nodek2, int preNodek2)
 method to load a node of the candidate graph at time sample (t-1) and a node od the the candidate graph at time sample (t-1).

bool CheckMTCoherentEdge1 (int time, int MTk1, int k, int nodek1)
 method to check if the edge related to a node to match of the reference graph are associated to the same MT class as the other previously matched nodes .

bool CheckMTCoherentEdge2 (int time, int MTk2, int k, int nodek2)
 method to check if the edge related to a node to match of the candidate graph are associated to the same MT class as the other previously matched nodes .


Private Attributes

SubGraphsubGraph1
 reference SubGraph Object for matching.

SubGraphsubGraph2
 candidate SubGraph Object to match with the reference sub-graph.

bool meanCalcul
 mean calculation 'true' or Kullback-Leibler divergence 'false' used in the matching nodes and edges comparison. More...

DivergencedivObject
 divergence objects.

float ** C_A
 Current covariance matrice considered for divergence.

float * M_A
 Current mean vector considered for divergence.

float ** C_B
 Current covariance matrice considered for divergence.

float * M_B
 Current mean vector considered for divergence.


Detailed Description

Object used by GraphManipulator to perform sub-graph matchings according to a parametric similarity model.

Definition at line 28 of file MatchCost+.hh.


Member Function Documentation

void MatchCost::FixCostFuncWeigths float    weightMTinTLDiff,
float    TL1TL2Div,
float    flowDiff,
float    divDiff,
float    MIDiff,
float    divMTaMTbCost,
float    timeDiff,
bool    meanCalcul
[inline]
 

This method introduce in the similarity model a given parameter vector. This method fixes also another parameter specific to the matching calculus.

Parameters:
weightMTinTLDiff  parameter weighting the population of each nodes
TL1TL2Div  parameter weighting the nodes' distribution
flowDiff  parameter weighting the flow of pixels exchanged between nodes
divDiff  parameter weighting the change in time of the nodes' distribution
MIDiff  parameter weighting the intra-node change in time
divMTaMTbCost  parameter weighting the interaction of the 2 MT classes (only if 2 MT class are considered);
timeDiff  parameter weighting the time lattice on which the sub-graph is defined
meanCalcul  mean calculation 'true' or Kullback-Leibler divergence 'flase' used in the matching calculation

Definition at line 113 of file MatchCost+.hh.

float MatchCost::InexactMatchCost int    nbMiniBranches,
SearchTree   searchTree,
float *    costs
[inline]
 

Method to match the reference sub-graph with the candidate sub-graph based on the parametric similarity model.

The idea of this algorithm is to find a collection of elementary transformation wich maps, with a minimal cost, each node and related edges of the reference graph to an existing node or a virtual node of the sub-graph candidate at the same time sample.
The cost assigned to each elementary matching result from the weighted sum of costs related to each graph attributes (population of the node, flow of points, etc...). The weighting is done using the current estimate of the similarity model parameter vector.
Each element of this sum is thus a comparison, by scalar difference or distribution divergence, of the attributes similarities between the couple of nodes (or edges).
When matching with an existing node, this comparison is straight fowards; but when the matching is performed with a virtual node, the virtual node attribute are simply 0 or attribute related to the MT cluster associated to the node. Inddeed, a node represents a TL cluster which is associated to a MT class.
The problem gets complicate when we consider simultaneously 2 MT classes per graph. In this case, at each time sample, the nodes of the 2 MT classes are considered separately one by one. And, as sub-graph nodes related to a given MT class can not be matched with nodes of the candidate sub-graph belonging to 2 different MT classes, the consistencyof the matching must be checked inthis case. This checking is done by the methods 'CheckMTCoherentEdge1(..)' and 'CheckMTCoherentEdge2'. To find the best collection of elementary transformation (mapping function), a SearchTree object is used. This object is a tree constituted of all possible mapping functions:

  • at the beginning a first node of the reference graph is matched with all posssible existing or virtual nodes of the sub-graph candidate present at the same time sample. The collection costs assigned to these elementary tranformations is stored in the first level of the tree.
    NB: note that the mapping of edges are related to nodes. Thus they are considered simultaneously with the node matchings.
  • Then a second node of the reference graph is matched with all posssible existing or virtual nodes of the sub-graph candidate present at the same time sample. This collection of costs assigned to these elementary tranformations is linked to the each element of the collection of costs of the firts level. This collection of collection constitutes the second levels of the tree.
  • the procedure is reiterated for each node of the reference sub-graph until no nodes are left.
    Once the search tree has been built, the best mapping function is the path in the tree associated to a minimal sum of node matching costs. However, because the number of ramification of such a tree is much too high with the combinatorial explosion of solutions, only 'nbMiniBranches' of possible mapping functions (paths in the tree from root to the curent leaves) are preserved after each elementary matching of a new node.

    As we are interested in decomposing each possible mapping function cost in a sum of costs related to a given graph attribute, the cost assigned to the best mapping function is decomposed into several parts related to each attribute contribution. These different cost constribution are stored in the array 'costs'.
    NB: note that the search tree created by this procedure will be used later to update the cost of the mapping function with a new similarity model parameter vector estimate. This update will only by the estimation of the best path in the search tree according to the new parameter vector.
Parameters:
nbMiniBranches  number of possible mapping functions (paths in the tree from root to the curent leaves) preserved after each elementary matching of a new node
searchTree  SearchTree Object resulting form the matching procedure. A number of 'nbMiniBranches' possible mapping functions are stored in it.
costs  collection of costs related to each graph attribute contribution, resulting of the decomposition of the best mapping function costs.

Definition at line 151 of file MatchCost+.hh.


Member Data Documentation

bool MatchCost::meanCalcul [private]
 

mean calculation 'true' or Kullback-Leibler divergence 'false' used in the matching nodes and edges comparison.

We remark that the Kullback-Leibler divergence is not adapted to the actual graph format 2, in which the divergence calculation is replaced by a simple distribution mean difference

Definition at line 67 of file MatchCost+.hh.

float MatchCost::meanCalculation
 

mean calculation '1' or Kullback-Leibler divergence '0' used in the matching nodes and edges comparisons.

We remark that the Kullback-Leibler divergence is not adapted to the actual graph format 2, in which the divergence calculation is replaced by a simple distribution mean difference

Definition at line 54 of file MatchCost+.hh.


The documentation for this class was generated from the following file:
Generated on Thu Feb 17 11:03:19 2005 for Interactive Learning of Sub-Graphs Semantics by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002