DisjointSet.hpp

Aller à la documentation de ce fichier.

/// \file
/// Définition des classes utiles pour le clustering de classes disjointes
#ifndef GUARD_DISJOINTSET_H
#define GUARD_DISJOINTSET_H

#include <vector>

#include "Debug.hpp"
#include "Node.hpp"
#include <map>

using namespace std;

static Channel channelCluster(&cout);
///////////////////////////////////////////////////////////////////////////////
///     Classe de base pour les algorithmes utilisant des ensembles disjoints
///
/// Cette classe implémente la compression de chemin
///////////////////////////////////////////////////////////////////////////////
class DisjointSet_Base{
        /// tableau d'index des parents d'un cluster
        vector<int> parent;
        /// tableau des tailles d'un cluster
        vector<int> size;
        /// map des parents vers les noeuds
        map<int, Node> table;
        /// Itérateur des parents vers les noeuds
        typedef map<int, Node>::iterator table_iter;
protected:
        /// le graphe à clusteriser
        Node graph;
        ///     les noeuds à étudier
        vector<Node> vNode;
        /// le nombre de cluster en cours
        int nbClass;
        /// les arretes du graphe clusterisés
        vector<Edge> edge;
        /// retourn le rang d'un parent
        int getParentRank(int);
public:
        /// Constructeur de l'algorithme
        /// \param Node : le noeud à clusteriser
        DisjointSet_Base(const Node);
        /// Retourne une chaîne de caractères détaillée 
        virtual string toString();
        /// Fusionne 2 noeuds
        Node mergeDisjointSet(Node, Node);
        /// Accomplis effectivement un algorithme de clusteringe
        virtual Node makeDisjointSet() = 0;
        /// Teste l'appartenance au même cluster de 2 points
        bool sameDisjointSet(Node, Node);
        /// Retourne sous forme de graphe un le résultat du clustering
        Node makeNode(string);
        /// Retourne la taille du parent d'un noeud
        int getParentSize(Node);
        /// Retourne le cluster d'un noeud
        Node getParent(Node);
};
///////////////////////////////////////////////////////////////////////////////
///     Kruskal : classe de test
///
/// Implemente l'algorithme de Kruskal pour trouver le MST d'un graphe
///////////////////////////////////////////////////////////////////////////////
class Kruskal : public DisjointSet_Base{
public:
        /// Prend comme argument le graphe dont on veut le MST
        Kruskal(Node);
        /// Implémentation de l'algorithme de Kruskal
        Node makeDisjointSet();
};
///////////////////////////////////////////////////////////////////////////////
///     MInt : classe de l'article
///
/// Implemente l'algorithme de l'article pour segmenter une image
///////////////////////////////////////////////////////////////////////////////
class MInt : public DisjointSet_Base{
        /// Paramètre de l'algorithme
        float tau;
public:
        /// Constructeur
        /// \param le graphe de l'image à segmenter
        /// \param le paramètre de l'algorithme
        /// \param mode bavard
        /// \param fichier de résultat
        MInt(Node, float);
        /// Implémente l'algorithme
        Node makeDisjointSet();
};
///////////////////////////////////////////////////////////////////////////////
///     Segment : résultat de plusieurs test
///
///     Variation de l'algorithme de l'article pour segmenter une image
///////////////////////////////////////////////////////////////////////////////
class Segment : public DisjointSet_Base{
        /// Paramètre de l'algorithme
        float k;
        /// Arrête de poids minimal
        float edgeWeightMin;
        /// Arrête de poids maximal
        float edgeWeightMax;
        /// Différence maximal
        float edgeWeightDelta;
public:
        /// Constructeur
        /// \param Node graphe de l'image à segmenter
        /// \param float paramètre de l'algorithme
        Segment(Node, float);
        /// Implémente l'algorithme
        Node makeDisjointSet();
};
///////////////////////////////////////////////////////////////////////////////
///     Meanshift
///
///     Fusion des régions pour le MeanShift
///////////////////////////////////////////////////////////////////////////////
class MeanShiftFusion : public DisjointSet_Base{
        /// Compteur de fusion
        float radius;
public:
        /// Constructeur
        /// \param le graphe de l'image à segmenter
        MeanShiftFusion(Node, float);
        /// Implémente l'algorithme
        Node makeDisjointSet();
};
///////////////////////////////////////////////////////////////////////////////
///     Elagage d'un graphe
///
///     Fusion des régions plus petites qu'un nombre
///////////////////////////////////////////////////////////////////////////////
class Prune : public DisjointSet_Base{
        /// Compteur de fusion
        int area;
public:
        /// Constructeur
        /// \param Node le graphe de l'image à segmenter
        /// \param int taille minimale
        Prune(Node, int);
        /// Implémente l'algorithme
        Node makeDisjointSet();
};

#endif

---