GraphCutter.h

Go to the documentation of this file.

/********************************************************************
**                Image Component Library (ICL)                    **
**                                                                 **
** Copyright (C) 2006-2013 CITEC, University of Bielefeld          **
**                         Neuroinformatics Group                  **
** Website: www.iclcv.org and                                      **
**          http://opensource.cit-ec.de/projects/icl               **
**                                                                 **
** File   : ICLMath/src/ICLMath/GraphCutter.h                      **
** Module : ICLMath                                                **
** Authors: Andre Ueckermann                                       **
**                                                                 **
**                                                                 **
** GNU LESSER GENERAL PUBLIC LICENSE                               **
** This file may be used under the terms of the GNU Lesser General **
** Public License version 3.0 as published by the                  **
**                                                                 **
** Free Software Foundation and appearing in the file LICENSE.LGPL **
** included in the packaging of this file.  Please review the      **
** following information to ensure the license requirements will   **
** be met: http://www.gnu.org/licenses/lgpl-3.0.txt                **
**                                                                 **
** The development of this software was supported by the           **
** Excellence Cluster EXC 277 Cognitive Interaction Technology.    **
** The Excellence Cluster EXC 277 is a grant of the Deutsche       **
** Forschungsgemeinschaft (DFG) in the context of the German       **
** Excellence Initiative.                                          **
**                                                                 **
********************************************************************/

#pragma once

#include <ICLMath/DynMatrix.h>
#include <ICLUtils/Point.h>

namespace icl{
  namespace math{


          class ICLMath_API GraphCutter{

          public:

        typedef struct{
          std::vector<int> subset;
          int parent;
          std::vector<int> children;
          float cost;
        }CutNode;


        static float minCut(DynMatrix<float> &adjacencyMatrix, std::vector<int> &subset1, std::vector<int> &subset2);


        static std::vector<std::vector<int> > thresholdCut(DynMatrix<float> &adjacencyMatrix, float threshold);


        static std::vector<std::vector<int> > thresholdCut(DynMatrix<bool> &adjacencyMatrix, float threshold);


        static std::vector<CutNode> hierarchicalCut(DynMatrix<float> &adjacencyMatrix);


        static std::vector<CutNode> hierarchicalCut(DynMatrix<bool> &adjacencyMatrix);


        static math::DynMatrix<float> calculateProbabilityMatrix(math::DynMatrix<bool> &initialMatrix, bool symmetry=true);


        static std::vector<std::vector<int> > findUnconnectedSubgraphs(DynMatrix<float> &adjacencyMatrix);


              static DynMatrix<float> createSubMatrix(DynMatrix<float> &adjacencyMatrix, std::vector<int> &subgraph);


              static void mergeMatrix(DynMatrix<bool> &dst, DynMatrix<bool> &src);


              static void weightMatrix(DynMatrix<float> &dst, DynMatrix<bool> &featureMatrix, float weight);

      private:
        static std::vector<float> capforest(std::vector<utils::Point> &edgeList, std::vector<float> &edgeCosts, int subsetsSize);

        static float initialLambda(DynMatrix<float> &adjacencyMatrix, int &lambda_id);

        static void createEdgeList(DynMatrix<float> &adjacencyMatrix, std::vector<utils::Point> &edgeList, std::vector<float> &edgeCosts);

        static std::vector<std::vector<int> > createInitialNodes(DynMatrix<float> &adjacencyMatrix);

        static float merge(std::vector<utils::Point> &edgeList, std::vector<float> &edgeCosts, std::vector<float> &q,
                                           std::vector<std::vector<int> > &subsets, float lambda_score, int j, int &lambda_id);
    };

  } // namespace math
}