NICE_SemSeg/semseg/SemSegContextTree.cpp

#include "SemSegContextTree.h"
#include "vislearning/baselib/Globals.h"
#include "vislearning/baselib/ProgressBar.h"
#include "core/basics/StringTools.h"

#include "core/imagedisplay/ImageDisplay.h"

#include "vislearning/cbaselib/CachedExample.h"
#include "vislearning/cbaselib/PascalResults.h"
#include "vislearning/baselib/ColorSpace.h"
#include "segmentation/RSMeanShift.h"
#include "segmentation/RSGraphBased.h"
#include "segmentation/RSSlic.h"
#include "core/basics/numerictools.h"
#include "core/basics/StringTools.h"
#include "core/basics/FileName.h"
#include "vislearning/baselib/ICETools.h"

#include "core/basics/Timer.h"
#include "core/basics/vectorio.h"
#include "core/image/FilterT.h"

#include <omp.h>
#include <iostream>

//#define DEBUG

using namespace OBJREC;
using namespace std;
using namespace NICE;

SemSegContextTree::SemSegContextTree ( const Config *conf, const MultiDataset *md )
    : SemanticSegmentation ( conf, & ( md->getClassNames ( "train" ) ) )
{
  this->conf = conf;
  string section = "SSContextTree";
  lfcw = new LFColorWeijer ( conf );
  firstiteration = true;

  maxSamples = conf->gI ( section, "max_samples", 2000 );

  minFeats = conf->gI ( section, "min_feats", 50 );

  maxDepth = conf->gI ( section, "max_depth", 10 );

  windowSize = conf->gI ( section, "window_size", 16 );

  featsPerSplit = conf->gI ( section, "feats_per_split", 200 );

  useShannonEntropy = conf->gB ( section, "use_shannon_entropy", true );

  nbTrees = conf->gI ( section, "amount_trees", 1 );

  string segmentationtype = conf->gS ( section, "segmentation_type", "slic" );

  useCategorization = conf->gB ( section, "use_categorization", false );

  cndir = conf->gS ( "SSContextTree", "cndir", "" );

  if ( useCategorization && cndir == "" )
  {
    fasthik = new GPHIKClassifier ( conf );
  }
  else
  {
    fasthik = NULL;
  }

  randomTests = conf->gI ( section, "random_tests", 10 );

  saveLoadData = conf->gB ( "debug", "save_load_data", false );
  fileLocation = conf->gS ( "debug", "datafile", "tmp.txt" );

  useRegionFeature = conf->gB ( section, "use_region_feat", false );

  pixelWiseLabeling = false;
  if ( segmentationtype == "meanshift" )
    segmentation = new RSMeanShift ( conf );
  else if ( segmentationtype == "felzenszwalb" )
    segmentation = new RSGraphBased ( conf );
  else if ( segmentationtype == "slic" )
    segmentation = new RSSlic ( conf );
  else if ( segmentationtype == "none" )
  {
    segmentation = NULL;
    pixelWiseLabeling = true;
    useRegionFeature = false;
  }
  else
    throw ( "no valid segmenation_type\n please choose between none, meanshift, slic and felzenszwalb\n" );

  ftypes = conf->gI ( section, "feat_types", 5 );

  string featsec = "Features";

  // feature extraction prototypes
  vector<Operation*> tops;

  if ( conf->gB ( featsec, "minus", true ) )
    tops.push_back ( new Minus() );
  if ( conf->gB ( featsec, "minus_abs", true ) )
    tops.push_back ( new MinusAbs() );
  if ( conf->gB ( featsec, "addition", true ) )
    tops.push_back ( new Addition() );
  if ( conf->gB ( featsec, "only1", true ) )
    tops.push_back ( new Only1() );
  if ( conf->gB ( featsec, "rel_x", true ) )
    tops.push_back ( new RelativeXPosition() );
  if ( conf->gB ( featsec, "rel_y", true ) )
    tops.push_back ( new RelativeYPosition() );
  if ( conf->gB ( featsec, "rel_z", true ) )
    tops.push_back ( new RelativeZPosition() );

  ops.push_back ( tops );

  tops.clear();
  tops.push_back ( new RegionFeat() );
  ops.push_back ( tops );

  tops.clear();
  if ( conf->gB ( featsec, "int", true ) )
    tops.push_back ( new IntegralOps() );
  if ( conf->gB ( featsec, "bi_int_cent", true ) )
    tops.push_back ( new BiIntegralCenteredOps() );
  if ( conf->gB ( featsec, "int_cent", true ) )
    tops.push_back ( new IntegralCenteredOps() );
  if ( conf->gB ( featsec, "haar_horz", true ) )
    tops.push_back ( new HaarHorizontal() );
  if ( conf->gB ( featsec, "haar_vert", true ) )
    tops.push_back ( new HaarVertical() );
  if ( conf->gB ( featsec, "haar_stack", true ) )
    tops.push_back ( new HaarStacked() );
  if ( conf->gB ( featsec, "haar_diagxy", true ) )
    tops.push_back ( new HaarDiagXY() );
  if ( conf->gB ( featsec, "haar_diagxz", true ) )
    tops.push_back ( new HaarDiagXZ() );
  if ( conf->gB ( featsec, "haar_diagyz", true ) )
    tops.push_back ( new HaarDiagYZ() );
  if ( conf->gB ( featsec, "haar3_horz", true ) )
    tops.push_back ( new Haar3Horiz() );
  if ( conf->gB ( featsec, "haar3_vert", true ) )
    tops.push_back ( new Haar3Vert() );
  if ( conf->gB ( featsec, "haar3_stack", true ) )
    tops.push_back ( new Haar3Stack() );

  ops.push_back ( tops );
  ops.push_back ( tops );

  tops.clear();
  if ( conf->gB ( featsec, "minus", true ) )
    tops.push_back ( new Minus() );
  if ( conf->gB ( featsec, "minus_abs", true ) )
    tops.push_back ( new MinusAbs() );
  if ( conf->gB ( featsec, "addition", true ) )
    tops.push_back ( new Addition() );
  if ( conf->gB ( featsec, "only1", true ) )
    tops.push_back ( new Only1() );
  if ( conf->gB ( featsec, "rel_x", true ) )
    tops.push_back ( new RelativeXPosition() );
  if ( conf->gB ( featsec, "rel_y", true ) )
    tops.push_back ( new RelativeYPosition() );
  if ( conf->gB ( featsec, "rel_z", true ) )
    tops.push_back ( new RelativeZPosition() );

  ops.push_back ( tops );

  useGradient = conf->gB ( featsec, "use_gradient", true );

  useWeijer = conf->gB ( featsec, "use_weijer", true );

  useAdditionalLayer = conf->gB ( featsec, "use_additional_layer", false );
  
  useVariance = conf->gB ( featsec, "use_variance", false );

  // geometric features of hoiem
  useHoiemFeatures = conf->gB ( featsec, "use_hoiem_features", false );
  if ( useHoiemFeatures )
  {
    hoiemDirectory = conf->gS ( featsec, "hoiem_directory" );
  }

  opOverview = vector<int> ( NBOPERATIONS, 0 );
  contextOverview = vector<vector<double> > ( maxDepth, vector<double> ( 2, 0.0 ) );

  calcVal.push_back ( new MCImageAccess() );
  calcVal.push_back ( new MCImageAccess() );
  calcVal.push_back ( new MCImageAccess() );
  calcVal.push_back ( new MCImageAccess() );
  calcVal.push_back ( new ClassificationResultAccess() );


  classnames = md->getClassNames ( "train" );

}

SemSegContextTree::~SemSegContextTree()
{
}

double SemSegContextTree::getBestSplit (
    std::vector<NICE::MultiChannelImage3DT<double> > &feats,
    std::vector<NICE::MultiChannelImage3DT<unsigned short int> > &nodeIndices,
    const std::vector<NICE::MultiChannelImageT<int> > &labels,
    int node,
    Operation *&splitop,
    double &splitval,
    const int &tree,
    vector<vector<vector<double> > > &regionProbs )
{
  Timer t;
  t.start();
  int imgCount = 0;

  try
  {
    imgCount = ( int ) feats.size();
  }
  catch ( Exception )
  {
    cerr << "no features computed?" << endl;
  }

  double bestig = -numeric_limits< double >::max();

  splitop = NULL;
  splitval = -1.0;

  set<vector<int> >selFeats;
  map<int, int> e;
  int featcounter = forest[tree][node].featcounter;

  if ( featcounter < minFeats )
  {
    return 0.0;
  }

  vector<double> fraction ( a.size(), 0.0 );

  for ( uint i = 0; i < fraction.size(); i++ )
  {
    if ( forbidden_classes.find ( labelmapback[i] ) != forbidden_classes.end() )
      fraction[i] = 0;
    else
      fraction[i] = ( ( double ) maxSamples ) / ( ( double ) featcounter * a[i] * a.size() );
  }

  featcounter = 0;

  for ( int iCounter = 0; iCounter < imgCount; iCounter++ )
  {
    int xsize = ( int ) nodeIndices[iCounter].width();
    int ysize = ( int ) nodeIndices[iCounter].height();
    int zsize = ( int ) nodeIndices[iCounter].depth();

    for ( int x = 0; x < xsize; x++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int z = 0; z < zsize; z++ )
        {
          if ( nodeIndices[iCounter].get ( x, y, z, tree ) == node )
          {
            int cn = labels[iCounter].get ( x, y, ( uint ) z );
            double randD = ( double ) rand() / ( double ) RAND_MAX;

            if ( labelmap.find ( cn ) == labelmap.end() )
              continue;

            if ( randD < fraction[labelmap[cn]] )
            {
              vector<int> tmp ( 4, 0 );
              tmp[0] = iCounter;
              tmp[1] = x;
              tmp[2] = y;
              tmp[3] = z;
              featcounter++;
              selFeats.insert ( tmp );
              e[cn]++;
            }
          }
        }
      }
    }
  }

  map<int, int>::iterator mapit;

  // global entropy
  double globent = 0.0;

  for ( mapit = e.begin() ; mapit != e.end(); mapit++ )
  {
    double p = ( double ) ( *mapit ).second / ( double ) featcounter;
    globent += p * log2 ( p );
  }

  globent = -globent;

  if ( globent < 0.5 )
  {
    return 0.0;
  }

  // pointers to all selected features
  std::vector<Operation*> featsel;

  for ( int i = 0; i < featsPerSplit; i++ )
  {
    int x1, x2, y1, y2, z1, z2;
    int ft = ( int ) ( ( double ) rand() / ( double ) RAND_MAX * ( double ) ftypes );

    int tmpws = windowSize;

    if ( firstiteration )
      ft = 0;

    if ( channelsPerType[ft].size() == 0 )
    {
      ft = 0;
    }

    if ( ft > 1 )
    {
      //use larger window size for context features
      tmpws *= 3;
    }

    // use region feature only with reasonable pre-segmentation
    if ( ft == 1 && depth < 8 )
    {
      ft = 0;
    }

    /* random window positions */
    double z_ratio = conf->gB ( "SSContextTree", "z_ratio", 1.0 );
    int tmp_z =  ( int ) floor( (tmpws * z_ratio) + 0.5 );
    double y_ratio = conf->gB ( "SSContextTree", "y_ratio", 1.0 );
    int tmp_y =  ( int ) floor( (tmpws * y_ratio) + 0.5 );
    x1 = ( int ) ( rand() % tmpws ) - tmpws / 2 ;
    x2 = ( int ) ( rand() % tmpws ) - tmpws / 2 ;
    y1 = ( int ) ( rand() % tmp_y ) - tmp_y / 2 ;
    y2 = ( int ) ( rand() % tmp_y ) - tmp_y / 2 ;
    z1 = ( int ) ( rand() % tmp_z ) - tmp_z / 2 ;
    z2 = ( int ) ( rand() % tmp_z ) - tmp_z / 2 ;

    if (conf->gB ( "SSContextTree", "z_negative_only", false ))
    {
      z1 = -abs(z1);
      z2 = -abs(z2);
    }
    
    /* random feature maps (channels) */
    int f1, f2;
    f1 = ( int ) ( rand() % channelsPerType[ft].size() );
    if ( (rand() % 2) == 0 )
      f2 = ( int ) ( rand() % channelsPerType[ft].size() );
    else
      f2 = f1;
    f1 = channelsPerType[ft][f1];
    f2 = channelsPerType[ft][f2];
    
    if ( ft == 1 )
    {
      int classes = ( int ) regionProbs[0][0].size();
      f2 = ( int ) ( rand() % classes );
    }
    
    /* random extraction method (operation) */
    int o = ( int ) ( rand() % ops[ft].size() );
    
    Operation *op = ops[ft][o]->clone();
    op->set ( x1, y1, z1, x2, y2, z2, f1, f2, calcVal[ft] );
    op->setFeatType ( ft );

    if ( ft == 3 || ft == 4 )
      op->setContext ( true );
    else
      op->setContext ( false );

    featsel.push_back ( op );
  }

  for ( int f = 0; f < featsPerSplit; f++ )
  {
    double l_bestig = -numeric_limits< double >::max();
    double l_splitval = -1.0;
    vector<double> vals;

    double maxval = -numeric_limits<double>::max();
    double minval = numeric_limits<double>::max();
    for ( set<vector<int> >::const_iterator it = selFeats.begin();
         it != selFeats.end(); it++ )
    {
      Features feat;
      feat.feats = &feats[ ( *it ) [0]];
      feat.nIndices = &nodeIndices[ ( *it ) [0]];
      feat.cTree = tree;
      feat.tree = &forest[tree];

      assert ( forest.size() > ( uint ) tree );
      assert ( forest[tree][0].dist.size() > 0 );

      feat.rProbs = &regionProbs[ ( *it ) [0]];

      double val = featsel[f]->getVal ( feat, ( *it ) [1], ( *it ) [2], ( *it ) [3] );
      if ( !isfinite ( val ) )
      {
        //cerr << "feat " << feat.feats->width() << " " << feat.feats->height() << " " << feat.feats->depth() << endl;
        //cerr << "non finite value " << val << " for " << featsel[f]->writeInfos() <<  endl << (*it) [1] << " " <<  (*it) [2] << " " << (*it) [3] << endl;
        val = 0.0;
      }
      vals.push_back ( val );
      maxval = std::max ( val, maxval );
      minval = std::min ( val, minval );
    }

    if ( minval == maxval )
      continue;

    // split values
    for ( int run = 0 ; run < randomTests; run++ )
    {
      double sval = ( (double) rand() / (double) RAND_MAX*(maxval-minval) ) + minval;

      map<int, int> eL, eR;
      int counterL = 0, counterR = 0;
      int counter2 = 0;

      for ( set<vector<int> >::const_iterator it2 = selFeats.begin();
            it2 != selFeats.end(); it2++, counter2++ )
      {
        int cn = labels[ ( *it2 ) [0]].get ( ( *it2 ) [1], ( *it2 ) [2], ( *it2 ) [3] );
        //cout << "vals[counter2] " << vals[counter2] << " val: " <<  val << endl;

        if ( vals[counter2] < sval )
        {
          //left entropie:
          eL[cn] = eL[cn] + 1;
          counterL++;
        }
        else
        {
          //right entropie:
          eR[cn] = eR[cn] + 1;
          counterR++;
        }
      }

      double leftent = 0.0;
      for ( mapit = eL.begin() ; mapit != eL.end(); mapit++ )
      {
        double p = ( double ) ( *mapit ).second / ( double ) counterL;
        leftent -= p * log2 ( p );
      }

      double rightent = 0.0;
      for ( mapit = eR.begin() ; mapit != eR.end(); mapit++ )
      {
        double p = ( double ) ( *mapit ).second / ( double ) counterR;
        rightent -= p * log2 ( p );
      }

      //cout << "rightent: " << rightent << " leftent: " << leftent << endl;

      double pl = ( double ) counterL / ( double ) ( counterL + counterR );

      //information gain
      double ig = globent - ( 1.0 - pl ) * rightent - pl * leftent;

      //double ig = globent - rightent - leftent;

      if ( useShannonEntropy )
      {
        double esplit = - ( pl * log ( pl ) + ( 1 - pl ) * log ( 1 - pl ) );
        ig = 2 * ig / ( globent + esplit );
      }

      if ( ig > l_bestig )
      {
        l_bestig = ig;
        l_splitval = sval;
      }
    }

    if ( l_bestig > bestig )
    {
      bestig = l_bestig;
      splitop = featsel[f];
      splitval = l_splitval;
    }
  }

#ifdef DEBUG
  //cout << "globent: " << globent <<  " bestig " << bestig << " splitval: " << splitval << endl;
#endif
  return bestig;
}

inline double SemSegContextTree::getMeanProb ( const int &x, const int &y, const int &z, const int &channel, const MultiChannelImage3DT<unsigned short int> &nodeIndices )
{
  double val = 0.0;

  for ( int tree = 0; tree < nbTrees; tree++ )
  {
    val += forest[tree][nodeIndices.get ( x,y,z,tree ) ].dist[channel];
  }

  return val / ( double ) nbTrees;
}

void SemSegContextTree::computeIntegralImage ( const NICE::MultiChannelImage3DT<unsigned short int> &nodeIndices, NICE::MultiChannelImage3DT<double> &integralImage, int firstChannel )
{
  int xsize = integralImage.width();
  int ysize = integralImage.height();
  int zsize = integralImage.depth();

  if ( firstiteration )
  {
#pragma omp parallel for
    for ( int it = 0; it < ( int ) integralMap.size(); it++ )
    {
      int corg = integralMap[it].first;
      int cint = integralMap[it].second;

      for ( int z = 0; z < zsize; z++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int x = 0; x < xsize; x++ )
          {
            integralImage ( x, y, z, cint ) = integralImage ( x, y, z, corg );
          }
        }
      }
      integralImage.calcIntegral ( cint );
    }
  }

  int channels = ( int ) forest[0][0].dist.size();

#pragma omp parallel for
  for ( int c = 0; c < channels; c++ )
  {

    integralImage ( 0, 0, 0, firstChannel + c ) = getMeanProb ( 0, 0, 0, c, nodeIndices );

    //first column
    for ( int y = 1; y < ysize; y++ )
    {
      integralImage ( 0, y, 0, firstChannel + c ) = getMeanProb ( 0, y, 0, c, nodeIndices )
                                            + integralImage ( 0, y - 1, 0, firstChannel + c );
    }

    //first row
    for ( int x = 1; x < xsize; x++ )
    {
      integralImage ( x, 0, 0, firstChannel + c ) = getMeanProb ( x, 0, 0, c, nodeIndices )
                                            + integralImage ( x - 1, 0, 0, firstChannel + c );
    }

    //first stack
    for ( int z = 1; z < zsize; z++ )
    {
      integralImage ( 0, 0, z, firstChannel + c ) = getMeanProb ( 0, 0, z, c, nodeIndices )
                                            + integralImage ( 0, 0, z - 1, firstChannel + c );
    }

    //x-y plane
    for ( int y = 1; y < ysize; y++ )
    {
      for ( int x = 1; x < xsize; x++ )
      {
        integralImage ( x, y, 0, firstChannel + c ) = getMeanProb ( x, y, 0, c, nodeIndices )
                                              + integralImage ( x, y - 1, 0, firstChannel + c )
                                              + integralImage ( x - 1, y, 0, firstChannel + c )
                                              - integralImage ( x - 1, y - 1, 0, firstChannel + c );
      }
    }

    //y-z plane
    for ( int z = 1; z < zsize; z++ )
    {
      for ( int y = 1; y < ysize; y++ )
      {
        integralImage ( 0, y, z, firstChannel + c ) = getMeanProb ( 0, y, z, c, nodeIndices )
                                              + integralImage ( 0, y - 1, z, firstChannel + c )
                                              + integralImage ( 0, y, z - 1, firstChannel + c )
                                              - integralImage ( 0, y - 1, z - 1, firstChannel + c );
      }
    }

    //x-z plane
    for ( int z = 1; z < zsize; z++ )
    {
      for ( int x = 1; x < xsize; x++ )
      {
        integralImage ( x, 0, z, firstChannel + c ) = getMeanProb ( x, 0, z, c, nodeIndices )
                                              + integralImage ( x - 1, 0, z, firstChannel + c )
                                              + integralImage ( x, 0, z - 1, firstChannel + c )
                                              - integralImage ( x - 1, 0, z - 1, firstChannel + c );
      }
    }

    //rest
    for ( int z = 1; z < zsize; z++ )
    {
      for ( int y = 1; y < ysize; y++ )
      {
        for ( int x = 1; x < xsize; x++ )
        {
          integralImage ( x, y, z, firstChannel + c ) = getMeanProb ( x, y, z, c, nodeIndices )
                                                + integralImage ( x - 1, y, z, firstChannel + c )
                                                + integralImage ( x, y - 1, z, firstChannel + c )
                                                + integralImage ( x, y, z - 1, firstChannel + c )
                                                + integralImage ( x - 1, y - 1, z - 1, firstChannel + c )
                                                - integralImage ( x - 1, y - 1, z, firstChannel + c )
                                                - integralImage ( x - 1, y, z - 1, firstChannel + c )
                                                - integralImage ( x, y - 1, z - 1, firstChannel + c );
        }
      }
    }
  }
}

inline double computeWeight ( const int &d, const int &dim )
{
  if (d == 0)
    return 0.0;
  else
    return 1.0 / ( pow ( 2, ( double ) ( dim - d + 1 ) ) );
}

void SemSegContextTree::train ( const MultiDataset *md )
{
  const LabeledSet trainSet = * ( *md ) ["train"];
  const LabeledSet *trainp = &trainSet;
  
  if ( saveLoadData )
  {
    if ( FileMgt::fileExists ( fileLocation ) )
      read ( fileLocation );
    else
    {
      train ( trainp );
      write ( fileLocation );
    }
  }
  else
  {
    train ( trainp );
  }
}

void SemSegContextTree::train ( const LabeledSet * trainp )
{
  int shortsize = numeric_limits<short>::max();

  Timer timer;
  timer.start();
  
  vector<int> zsizeVec;
  getDepthVector ( trainp, zsizeVec );
  bool run_3dseg = conf->gB ( "debug", "run_3dseg", true );

//   ProgressBar pb ( "compute feats" );
//   pb.show();

  //FIXME: memory usage
  vector<MultiChannelImage3DT<double> > allfeats;
  vector<MultiChannelImage3DT<unsigned short int> > nodeIndices;
  vector<MultiChannelImageT<int> > labels;

  vector<SparseVector*> globalCategorFeats;
  vector<map<int,int> > classesPerImage;

  vector<vector<int> > rSize;
  vector<int> amountRegionpI;

  std::string forbidden_classes_s = conf->gS ( "analysis", "forbidden_classes", "" );
  classnames.getSelection ( forbidden_classes_s, forbidden_classes );

  int imgCounter = 0;
  int amountPixels = 0;

  // How many channels of non-integral type do we have?

  if ( imagetype == IMAGETYPE_RGB )
    rawChannels = 3;
  else
    rawChannels = 1;

  if ( useGradient )
    rawChannels *= 2;

  if ( useWeijer )
    rawChannels += 11;

  if ( useHoiemFeatures )
    rawChannels += 8;

  if ( useAdditionalLayer )
    rawChannels += 1;
  
  if ( useVariance )
    rawChannels += 1; 


///////////////////////////// read input data /////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

  int depthCount = 0;
  vector< string > filelist;
  NICE::MultiChannelImageT<uchar> pixelLabels;

  for (LabeledSet::const_iterator it = trainp->begin(); it != trainp->end(); it++)
  {
    for (std::vector<ImageInfo *>::const_iterator jt = it->second.begin();
         jt != it->second.end(); jt++)
    {
      int classno = it->first;
      ImageInfo & info = *(*jt);
      std::string file = info.img();
      filelist.push_back ( file );
      depthCount++;

      const LocalizationResult *locResult = info.localization();

      // getting groundtruth
      NICE::Image pL;
      pL.resize ( locResult->xsize, locResult->ysize );
      pL.set ( 0 );
      locResult->calcLabeledImage ( pL, ( *classNames ).getBackgroundClass() );
      pixelLabels.addChannel ( pL );

      if ( locResult->size() <= 0 )
      {
        fprintf ( stderr, "WARNING: NO ground truth polygons found for %s !\n",
                  file.c_str() );
        continue;
      }

      fprintf ( stderr, "SSContext: Collecting pixel examples from localization info: %s\n", file.c_str() );

      int depthBoundary = 0;
      if ( run_3dseg )
      {
        depthBoundary = zsizeVec[imgCounter];
      }

      if ( depthCount < depthBoundary ) continue;

      // all image slices collected -> make a 3d image
      NICE::MultiChannelImage3DT<double> imgData;
      make3DImage ( filelist, imgData );

      int xsize = imgData.width();
      int ysize = imgData.height();
      int zsize = imgData.depth();
      amountPixels += xsize * ysize * zsize;

      MultiChannelImageT<int> tmpMat ( xsize, ysize, ( uint ) zsize );
      labels.push_back ( tmpMat );

      nodeIndices.push_back ( MultiChannelImage3DT<unsigned short int> ( xsize, ysize, zsize, nbTrees ) );
      nodeIndices[imgCounter].setAll ( 0 );

      //TODO: resize image?!
      MultiChannelImage3DT<double> feats;
      allfeats.push_back ( feats );

      int amountRegions;
      // read image and do some simple transformations
      extractBasicFeatures ( allfeats[imgCounter], imgData, filelist, amountRegions );

      if ( useRegionFeature )
      {
        amountRegionpI.push_back ( amountRegions );
        rSize.push_back ( vector<int> ( amountRegions, 0 ) );
      }

      if ( useCategorization )
      {
        globalCategorFeats.push_back ( new SparseVector() );
        classesPerImage.push_back ( map<int,int>() );
      }

      for ( int x = 0; x < xsize; x++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int z = 0; z < zsize; z++ )
          {
            if ( useRegionFeature )
              rSize[imgCounter][allfeats[imgCounter] ( x, y, z, rawChannels ) ]++;

            if ( run_3dseg )
              classno = pixelLabels ( x, y, ( uint ) z );
            else
              classno = pL.getPixelQuick ( x,y );

            labels[imgCounter].set ( x, y, classno, ( uint ) z );

            if ( forbidden_classes.find ( classno ) != forbidden_classes.end() )
              continue;

            labelcounter[classno]++;

            if ( useCategorization )
              classesPerImage[imgCounter][classno] = 1;
          }
        }
      }

//       pb.update ( trainp->count() );
      filelist.clear();
      pixelLabels.reInit ( 0,0,0 );
      depthCount = 0;
      imgCounter++;
    }
  }
    
//   pb.hide();

  int classes = 0;
  for ( map<int, int>::const_iterator mapit = labelcounter.begin();
        mapit != labelcounter.end(); mapit++ )
  {
    labelmap[mapit->first] = classes;
    labelmapback[classes] = mapit->first;
    classes++;
  }

////////////////////////// channel type configuration /////////////////////////
///////////////////////////////////////////////////////////////////////////////

  // Type 0: gray value channels
  for ( int i = 0; i < rawChannels; i++ )
  {
    channelType.push_back ( 0 );
  }

  // Type 1: region channels
  int shift = 0;
  if ( useRegionFeature )
  {
    channelType.push_back ( 1 );
    shift++;
  }

  // Type 2: gray value integral channels
  integralMap.clear();
  for ( int i = 0; i < rawChannels; i++ )
  {
    channelType.push_back ( 2 );
    integralMap.push_back ( pair<int, int> ( i, i + rawChannels + shift ) );
  }

  // Type 3: label integral channels (context)
  for ( int i = 0; i < classes; i++ )
  {
    channelType.push_back ( 3 );
  }

  // Type 4: label value channels (context) --> INFO: creates bad splits
//  for ( int i = 0; i < classes; i++ )
//  {
//    channelType.push_back ( 4 );
//  }

  // configure to include all possible feature types (just a subset
  // defined by ftypes is actually used)
  // 'amountTypes' sets upper bound for usable feature types
  int amountTypes = 5;
  channelsPerType = vector<vector<int> > ( amountTypes, vector<int>() );

  for ( int i = 0; i < ( int ) channelType.size(); i++ )
  {
    channelsPerType[channelType[i]].push_back ( i );
  }

  for ( int i = 0; i < classes; i++ )
  {
    channelsPerType[channelsPerType.size()-1].push_back ( i );
  }
  ftypes = std::min ( amountTypes, ftypes );

///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////

  vector<vector<vector<double> > > regionProbs;
  if ( useRegionFeature )
  {
    for ( int i = 0; i < imgCounter; i++ )
    {
      regionProbs.push_back ( vector<vector<double> > ( amountRegionpI[i], vector<double> ( classes, 0.0 ) ) );
    }
  }

  //balancing
  a = vector<double> ( classes, 0.0 );
  int featcounter = 0;
  for ( int iCounter = 0; iCounter < imgCounter; iCounter++ )
  {
    int xsize = ( int ) nodeIndices[iCounter].width();
    int ysize = ( int ) nodeIndices[iCounter].height();
    int zsize = ( int ) nodeIndices[iCounter].depth();

    for ( int x = 0; x < xsize; x++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int z = 0; z < zsize; z++ )
        {
          featcounter++;
          int cn = labels[iCounter] ( x, y, ( uint ) z );
          if ( labelmap.find ( cn ) == labelmap.end() )
            continue;
          a[labelmap[cn]] ++;
        }
      }
    }
  }

  for ( int i = 0; i < ( int ) a.size(); i++ )
  {
    a[i] /= ( double ) featcounter;
  }

#ifdef DEBUG
  for ( int i = 0; i < ( int ) a.size(); i++ )
  {
    cout << "a[" << i << "]: " << a[i] << endl;
  }

  cout << "a.size: " << a.size() << endl;

#endif

  depth = 0;
  uniquenumber = 0;

  //initialize random forest
  for ( int t = 0; t < nbTrees; t++ )
  {
    vector<TreeNode> singletree;
    singletree.push_back ( TreeNode() );
    singletree[0].dist = vector<double> ( classes, 0.0 );
    singletree[0].depth = depth;
    singletree[0].featcounter = amountPixels;
    singletree[0].nodeNumber = uniquenumber;
    uniquenumber++;
    forest.push_back ( singletree );
  }

  vector<int> startnode ( nbTrees, 0 );

  bool noNewSplit = false;
  //int baseFeatSize = allfeats[0].size();

  timer.stop();
  cerr << "preprocessing finished in: " << timer.getLastAbsolute() << " seconds" << endl;
  timer.start();

  //////////////////////////// learn the classifier ///////////////////////////
  /////////////////////////////////////////////////////////////////////////////
  while ( !noNewSplit && depth < maxDepth )
  {
    depth++;
#ifdef DEBUG
    cout << "depth: " << depth << endl;
#endif
    noNewSplit = true;
    vector<MultiChannelImage3DT<unsigned short int> > lastNodeIndices = nodeIndices;
    vector<vector<vector<double> > > lastRegionProbs = regionProbs;

    if ( useRegionFeature )
    {
      for ( int i = 0; i < imgCounter; i++ )
      {
        int numRegions = (int) regionProbs[i].size();
        for ( int r = 0; r < numRegions; r++ )
        {
          for ( int c = 0; c < classes; c++ )
          {
            regionProbs[i][r][c] = 0.0;
          }
        }
      }
    }

#ifdef DEBUG
    Timer timerDepth;
    timerDepth.start();
#endif

    double weight = computeWeight ( depth, maxDepth )
                    - computeWeight ( depth - 1, maxDepth );

#pragma omp parallel for
    // for each tree
    for ( int tree = 0; tree < nbTrees; tree++ )
    {
      const int t = ( int ) forest[tree].size();
      const int s = startnode[tree];
      startnode[tree] = t;
      double bestig;

      // for each node
      for ( int node = s; node < t; node++ )
      {
        if ( !forest[tree][node].isleaf && forest[tree][node].left < 0 )
        {
          // find best split
          Operation *splitfeat = NULL;
          double splitval;
          bestig = getBestSplit ( allfeats, lastNodeIndices, labels, node,
                                   splitfeat, splitval, tree, lastRegionProbs );

          forest[tree][node].feat = splitfeat;
          forest[tree][node].decision = splitval;

          // split the node
          if ( splitfeat != NULL )
          {
            noNewSplit = false;
            int left;
#pragma omp critical
            {
              left = forest[tree].size();
              forest[tree].push_back ( TreeNode() );
              forest[tree].push_back ( TreeNode() );
            }
            int right = left + 1;
            forest[tree][node].left = left;
            forest[tree][node].right = right;
            forest[tree][left].init( depth, classes, uniquenumber);
            int leftu = uniquenumber;
            uniquenumber++;
            forest[tree][right].init( depth, classes, uniquenumber);
            int rightu = uniquenumber;
            uniquenumber++;

#pragma omp parallel for
            for ( int i = 0; i < imgCounter; i++ )
            {
              int xsize = nodeIndices[i].width();
              int ysize = nodeIndices[i].height();
              int zsize = nodeIndices[i].depth();

              for ( int x = 0; x < xsize; x++ )
              {
                for ( int y = 0; y < ysize; y++ )
                {
                  for ( int z = 0; z < zsize; z++ )
                  {
                    if ( nodeIndices[i].get ( x, y, z, tree ) == node )
                    {
                      // get feature value
                      Features feat;
                      feat.feats = &allfeats[i];
                      feat.nIndices = &lastNodeIndices[i];
                      feat.cTree = tree;
                      feat.tree = &forest[tree];
                      feat.rProbs = &lastRegionProbs[i];
                      double val = splitfeat->getVal ( feat, x, y, z );

                      if ( !isfinite ( val ) ) val = 0.0;

#pragma omp critical
                      {
                        int curLabel = labels[i] ( x, y, ( uint ) z );
                        // traverse to left child
                        if ( val < splitval )
                        {
                          nodeIndices[i].set ( x, y, z, left, tree );
                          if ( labelmap.find ( curLabel ) != labelmap.end() )
                            forest[tree][left].dist[labelmap[curLabel]]++;
                          forest[tree][left].featcounter++;
                          if ( useCategorization && leftu < shortsize )
                            ( *globalCategorFeats[i] ) [leftu]+=weight;
                        }
                        // traverse to right child
                        else
                        {
                          nodeIndices[i].set ( x, y, z, right, tree );
                          if ( labelmap.find ( curLabel ) != labelmap.end() )
                            forest[tree][right].dist[labelmap[curLabel]]++;
                          forest[tree][right].featcounter++;

                          if ( useCategorization && rightu < shortsize )
                            ( *globalCategorFeats[i] ) [rightu]+=weight;
                        }
                      }
                    }
                  }
                }
              }
            }

            // normalize distributions in child leaves
            double lcounter = 0.0, rcounter = 0.0;
            for ( int c = 0; c < (int)forest[tree][left].dist.size(); c++ )
            {
              if ( forbidden_classes.find ( labelmapback[c] ) != forbidden_classes.end() )
              {
                forest[tree][left].dist[c] = 0;
                forest[tree][right].dist[c] = 0;
              }
              else
              {
                forest[tree][left].dist[c] /= a[c];
                lcounter += forest[tree][left].dist[c];
                forest[tree][right].dist[c] /= a[c];
                rcounter += forest[tree][right].dist[c];
              }
            }

//            assert ( lcounter > 0 && rcounter > 0 );

            if ( lcounter <= 0 || rcounter <= 0 )
            {
              cout << "lcounter : " << lcounter << " rcounter: " << rcounter << endl;
              cout << "splitval: " << splitval << " splittype: " << splitfeat->writeInfos() << endl;
              cout << "bestig: " << bestig << endl;

              for ( int i = 0; i < imgCounter; i++ )
              {
                int xsize = nodeIndices[i].width();
                int ysize = nodeIndices[i].height();
                int zsize = nodeIndices[i].depth();
                int counter = 0;

                for ( int x = 0; x < xsize; x++ )
                {
                  for ( int y = 0; y < ysize; y++ )
                  {
                    for ( int z = 0; z < zsize; z++ )
                    {
                      if ( lastNodeIndices[i].get ( x, y, tree ) == node )
                      {
                        if ( ++counter > 30 )
                          break;

                        Features feat;
                        feat.feats = &allfeats[i];
                        feat.nIndices = &lastNodeIndices[i];
                        feat.cTree = tree;
                        feat.tree = &forest[tree];
                        feat.rProbs = &lastRegionProbs[i];

                        double val = splitfeat->getVal ( feat, x, y, z );
                        if ( !isfinite ( val ) ) val = 0.0;

                        cout << "splitval: " << splitval << " val: " << val << endl;
                      }
                    }
                  }
                }
              }

              assert ( lcounter > 0 && rcounter > 0 );
            }

            for ( int c = 0; c < classes; c++ )
            {
              forest[tree][left].dist[c] /= lcounter;
              forest[tree][right].dist[c] /= rcounter;
            }
          }
          else
          {
            forest[tree][node].isleaf = true;
          }
        }
      }
    }


    if ( useRegionFeature )
    {
      for ( int i = 0; i < imgCounter; i++ )
      {
        int xsize = nodeIndices[i].width();
        int ysize = nodeIndices[i].height();
        int zsize = nodeIndices[i].depth();

#pragma omp parallel for
        // set region probability distribution
        for ( int x = 0; x < xsize; x++ )
        {
          for ( int y = 0; y < ysize; y++ )
          {
            for ( int z = 0; z < zsize; z++ )
            {
              for ( int tree = 0; tree < nbTrees; tree++ )
              {
                int node = nodeIndices[i].get ( x, y, z, tree );
                for ( int c = 0; c < classes; c++ )
                {
                  int r = (int) ( allfeats[i] ( x, y, z, rawChannels ) );
                  regionProbs[i][r][c] += forest[tree][node].dist[c];
                }
              }
            }
          }
        }

        // normalize distribution
        int numRegions = (int) regionProbs[i].size();
        for ( int r = 0; r < numRegions; r++ )
        {
          for ( int c = 0; c < classes; c++ )
          {
            regionProbs[i][r][c] /= ( double ) ( rSize[i][r] );
          }
        }
      }
    }

    //compute integral images
    if ( firstiteration )
    {
      for ( int i = 0; i < imgCounter; i++ )
      {
        allfeats[i].addChannel ( ( int ) ( classes + rawChannels ) );
      }
    }

    for ( int i = 0; i < imgCounter; i++ )
    {
      computeIntegralImage ( nodeIndices[i], allfeats[i], channelType.size() - classes );
    }

    if ( firstiteration )
    {
      firstiteration = false;
    }

#if DEBUG
    timerDepth.stop();
    cout << "time for depth " << depth << ": " << timerDepth.getLastAbsolute() << endl;
#endif

    lastNodeIndices.clear();
    lastRegionProbs.clear();
  }

  timer.stop();
  cerr << "learning finished in: " << timer.getLastAbsolute() << " seconds" << endl;
  timer.start();

  cout << "uniquenumber " << uniquenumber << endl;

  //////////////////////// classification using HIK ///////////////////////////
  /////////////////////////////////////////////////////////////////////////////

  if ( useCategorization && fasthik != NULL )
  {
    uniquenumber = std::min ( shortsize, uniquenumber );
    for ( uint i = 0; i < globalCategorFeats.size(); i++ )
    {
      globalCategorFeats[i]->setDim ( uniquenumber );
      globalCategorFeats[i]->normalize();
    }
    map<int,Vector> ys;

    int cCounter = 0;
    for ( map<int,int>::const_iterator it = labelmap.begin();
          it != labelmap.end(); it++, cCounter++ )
    {
      ys[cCounter] = Vector ( globalCategorFeats.size() );
      for ( int i = 0; i < imgCounter; i++ )
      {
        if ( classesPerImage[i].find ( it->first ) != classesPerImage[i].end() )
        {
          ys[cCounter][i] = 1;
        }
        else
        {
          ys[cCounter][i] = -1;
        }
      }
    }

    fasthik->train ( globalCategorFeats, ys );

  }

#ifdef DEBUG
  for ( int tree = 0; tree < nbTrees; tree++ )
  {
    int t = ( int ) forest[tree].size();

    for ( int i = 0; i < t; i++ )
    {
      printf ( "tree[%i]: left: %i, right: %i", i, forest[tree][i].left, forest[tree][i].right );

      if ( !forest[tree][i].isleaf && forest[tree][i].left != -1 )
      {
        cout <<  ", feat: " << forest[tree][i].feat->writeInfos() << " ";
        opOverview[forest[tree][i].feat->getOps() ]++;
        contextOverview[forest[tree][i].depth][ ( int ) forest[tree][i].feat->getContext() ]++;
      }

      for ( int d = 0; d < ( int ) forest[tree][i].dist.size(); d++ )
      {
        cout << " " << forest[tree][i].dist[d];
      }

      cout << endl;
    }
  }

  std::map<int, int> featTypeCounter;

  for ( int tree = 0; tree < nbTrees; tree++ )
  {
    int t = ( int ) forest[tree].size();

    for ( int i = 0; i < t; i++ )
    {
      if ( !forest[tree][i].isleaf && forest[tree][i].left != -1 )
      {
        featTypeCounter[forest[tree][i].feat->getFeatType() ] += 1;
      }
    }
  }

  cout << "evaluation of featuretypes" << endl;
  for ( map<int, int>::const_iterator it = featTypeCounter.begin(); it != featTypeCounter.end(); it++ )
  {
    cerr << it->first << ": " << it->second << endl;
  }

  for ( uint c = 0; c < ops.size(); c++ )
  {

    for ( int t = 0; t < ( int ) ops[c].size(); t++ )
    {
      cout << ops[c][t]->writeInfos() << ": " << opOverview[ops[c][t]->getOps() ] << endl;
    }
  }

  for ( int d = 0; d < maxDepth; d++ )
  {
    double sum =  contextOverview[d][0] + contextOverview[d][1];
    if ( sum == 0 )
      sum = 1;

    contextOverview[d][0] /= sum;
    contextOverview[d][1] /= sum;

    cout << "depth: " << d << " woContext: " << contextOverview[d][0] << " wContext: " << contextOverview[d][1] << endl;
  }
#endif

  timer.stop();
  cerr << "rest finished in: " << timer.getLastAbsolute() << " seconds" << endl;
  timer.start();
}

void SemSegContextTree::extractBasicFeatures ( NICE::MultiChannelImage3DT<double> &feats, const NICE::MultiChannelImage3DT<double> &imgData, const vector<string> &filelist, int &amountRegions )
{
  int xsize = imgData.width();
  int ysize = imgData.height();
  int zsize = imgData.depth();
  //TODO: resize image?!

  amountRegions = 0;
  feats.reInit ( xsize, ysize, zsize, imgData.channels() );
  feats.setAll ( 0 );

  for ( int z = 0; z < zsize; z++ )
  {
    NICE::MultiChannelImageT<double> feats_tmp;
    feats_tmp.reInit ( xsize, ysize, 3 );
    if ( imagetype == IMAGETYPE_RGB )
    {

      NICE::ColorImage img = imgData.getColor ( z );
      for ( int x = 0; x < xsize; x++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int r = 0; r < 3; r++ )
          {
            feats_tmp.set ( x, y, img.getPixel ( x, y, r ), ( uint ) r );
          }
        }
      }

    }
    else
    {

      NICE::ImageT<double> img = imgData.getChannelT ( z,0 );
      for ( int x = 0; x < xsize; x++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          feats_tmp.set ( x, y, img.getPixel ( x, y ), 0 );
        }
      }

    }

    if ( imagetype == IMAGETYPE_RGB )
      feats_tmp = ColorSpace::rgbtolab ( feats_tmp );

    for ( int x = 0; x < xsize; x++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        if ( imagetype == IMAGETYPE_RGB )
        {
          for ( uint r = 0; r < 3; r++ )
          {
            feats.set ( x, y, z, feats_tmp.get ( x, y, r ), r );
          }
        }
        else
        {
          feats.set ( x, y, z, feats_tmp.get ( x, y, 0 ), 0 );
        }
      }
    }

    // Gradient layers
    if ( useGradient )
    {
      int currentsize = feats_tmp.channels();
      feats_tmp.addChannel ( currentsize );

      for ( int c = 0; c < currentsize; c++ )
      {
        ImageT<double> tmp = feats_tmp[c];
        ImageT<double> tmp2 = feats_tmp[c+currentsize];

        NICE::FilterT<double, double, double>::gradientStrength ( tmp, tmp2 );
      }
    }

    // Weijer color names
    if ( useWeijer )
    {
      if ( imagetype == IMAGETYPE_RGB )
      {
        NICE::ColorImage img = imgData.getColor ( z );
        NICE::MultiChannelImageT<double> cfeats;
        lfcw->getFeats ( img, cfeats );
        feats_tmp.addChannel ( cfeats );
      }
      else
      {
        cerr << "Can't compute weijer features of a grayscale image." << endl;
      }
    }

    // arbitrary additional layer as image
    if ( useAdditionalLayer )
    {
      vector<string> list;
      StringTools::split ( filelist[z], '/', list );
      string layerPath = StringTools::trim ( filelist[z], list.back() ) + "addlayer/" + list.back();
      NICE::Image layer ( layerPath );
      feats_tmp.addChannel ( layer );
    }
    
    // read the geometric cues produced by Hoiem et al.
    if ( useHoiemFeatures )
    {
      // we could also give the following set as a config option
      string hoiemClasses_s = "sky 000 090-045 090-090 090-135 090 090-por 090-sol";
      vector<string> hoiemClasses;
      StringTools::split ( hoiemClasses_s, ' ', hoiemClasses );

      // Now we have to do some fancy regular expressions :)
      // Original image filename: basel_000083.jpg
      // hoiem result: basel_000083_c_sky.png

      // Fancy class of Ferid which supports string handling especially for filenames
      FileName fn ( filelist[z] );
      fn.removeExtension();
      FileName fnBase = fn.extractFileName();

      // counter for the channel index, starts with the current size of the destination multi-channel image
      int currentChannel = feats_tmp.channels();

      // add a channel for each feature in advance
      feats_tmp.addChannel ( hoiemClasses.size() );

      // loop through all geometric categories and add the images
      for ( vector<string>::const_iterator i = hoiemClasses.begin(); i != hoiemClasses.end(); i++, currentChannel++ )
      {
        string hoiemClass = *i;
        FileName fnConfidenceImage ( hoiemDirectory + fnBase.str() + "_c_" + hoiemClass + ".png" );
        if ( ! fnConfidenceImage.fileExists() )
        {
          fthrow ( Exception, "Unable to read the Hoiem geometric confidence image: " << fnConfidenceImage.str() << " (original image is " << filelist[z] << ")" );
        }
        else
        {
          Image confidenceImage ( fnConfidenceImage.str() );
          // check whether the image size is consistent
          if ( confidenceImage.width() != feats_tmp.width() || confidenceImage.height() != feats_tmp.height() )
          {
            fthrow ( Exception, "The size of the geometric confidence image does not match with the original image size: " << fnConfidenceImage.str() );
          }
          ImageT<double> dst = feats_tmp[currentChannel];

          // copy standard image to double image
          for ( uint y = 0 ; y < ( uint ) confidenceImage.height(); y++ )
            for ( uint x = 0 ; x < ( uint ) confidenceImage.width(); x++ )
              feats_tmp ( x, y, currentChannel ) = ( double ) confidenceImage ( x, y );
        }
      }
    }

    uint oldChannels = feats.channels();
    if ( feats.channels() < feats_tmp.channels() )
      feats.addChannel ( feats_tmp.channels()-feats.channels() );

    for ( int x = 0; x < xsize; x++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( uint r = oldChannels; r < ( uint ) feats_tmp.channels(); r++ )
        {
          feats.set ( x, y, z, feats_tmp.get ( x, y, r ), r );
        }
      }
    }
  }

  if ( useRegionFeature )
  {
    //using segmentation
    MultiChannelImageT<int> regions;
    regions.reInit( xsize, ysize, zsize );
    amountRegions = segmentation->segRegions ( imgData, regions, imagetype );

    int cchannel = feats.channels();
    feats.addChannel ( 1 );

    for ( int z = 0; z < ( int ) regions.channels(); z++ )
    {
      for ( int y = 0; y < regions.height(); y++ )
      {
        for ( int x = 0; x < regions.width(); x++ )
        {
          feats.set ( x, y, z, regions ( x, y, ( uint ) z ), cchannel );
        }
      }
    }
  }
  
  // variance maps (textural information)
  if ( useVariance )
  {
    int cchannel = feats.channels();
    if (imagetype == IMAGETYPE_RGB)
    {
      feats.addChannel( 3 );
      for (int c = 0; c < 3; c++)
      {
        feats.calcVariance( c, cchannel+c );
      }
    }
    else
    {
      feats.addChannel( 1 );
      feats.calcVariance( 0, cchannel );
    }
  }

}

void SemSegContextTree::classify (
    const NICE::MultiChannelImage3DT<double> & imgData,
    NICE::MultiChannelImageT<double> & segresult,
    NICE::MultiChannelImage3DT<double> & probabilities,
    const std::vector<std::string> & filelist )
{
  fprintf ( stderr, "ContextTree classification !\n" );

  int xsize = imgData.width();
  int ysize = imgData.height();
  int zsize = imgData.depth();

  ////////////////////////// initialize variables /////////////////////////////
  /////////////////////////////////////////////////////////////////////////////

  firstiteration = true;
  depth = 0;

  // classes occurred during training step
  int classes = labelmapback.size();
  // classes defined in config file
  int numClasses = classNames->numClasses();

  // class probabilities by pixel
  probabilities.reInit ( xsize, ysize, zsize, numClasses );
  probabilities.setAll ( 0 );

  // class probabilities by region
  vector<vector<double> > regionProbs;

  // feature values for each pixel
  MultiChannelImage3DT<double> feats;

  // affiliation: pixel <-> (tree,node)
  MultiChannelImage3DT<unsigned short int> nodeIndices ( xsize, ysize, zsize, nbTrees );
  nodeIndices.setAll ( 0 );

  // for categorization
  SparseVector *globalCategorFeat;
  globalCategorFeat = new SparseVector();

  /////////////////////////// get feature values //////////////////////////////
  /////////////////////////////////////////////////////////////////////////////

  // Basic Features
  int amountRegions;
  extractBasicFeatures ( feats, imgData, filelist, amountRegions );

  vector<int> rSize;
  if ( useRegionFeature )
  {
    regionProbs = vector<vector<double> > ( amountRegions, vector<double> ( classes, 0.0 ) );
    rSize = vector<int> ( amountRegions, 0 );
    for ( int z = 0; z < zsize; z++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int x = 0; x < xsize; x++ )
        {
          rSize[feats ( x, y, z, rawChannels ) ]++;
        }
      }
    }
  }

  ////////////////// traverse image example through trees /////////////////////
  /////////////////////////////////////////////////////////////////////////////

  bool noNewSplit = false;
  for ( int d = 0; d < maxDepth && !noNewSplit; d++ )
  {
    depth++;
    vector<vector<double> > lastRegionProbs = regionProbs;
    MultiChannelImage3DT<unsigned short int> lastNodeIndices = nodeIndices;

    if ( useRegionFeature )
    {
      int numRegions = ( int ) regionProbs.size();
      for ( int r = 0; r < numRegions; r++ )
      {
        for ( int c = 0; c < classes; c++ )
        {
          regionProbs[r][c] = 0.0;
        }
      }
    }

    double weight = computeWeight ( depth, maxDepth )
                    - computeWeight ( depth - 1, maxDepth );

    noNewSplit = true;

    int tree;
#pragma omp parallel for private(tree)
    for ( tree = 0; tree < nbTrees; tree++ )
    {
      for ( int x = 0; x < xsize; x++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int z = 0; z < zsize; z++ )
          {
            int node = nodeIndices.get ( x, y, z, tree );

            if ( forest[tree][node].left > 0 )
            {
              noNewSplit = false;
              Features feat;
              feat.feats = &feats;
              feat.nIndices = &lastNodeIndices;
              feat.cTree = tree;
              feat.tree = &forest[tree];
              feat.rProbs = &lastRegionProbs;

              double val = forest[tree][node].feat->getVal ( feat, x, y, z );
              if ( !isfinite ( val ) ) val = 0.0;

              // traverse to left child
              if ( val < forest[tree][node].decision )
              {
                int left = forest[tree][node].left;
                nodeIndices.set ( x, y, z, left, tree );
#pragma omp critical
                {
                  if ( fasthik != NULL
                       && useCategorization
                       && forest[tree][left].nodeNumber < uniquenumber )
                    ( *globalCategorFeat ) [forest[tree][left].nodeNumber] += weight;
                }
              }
              // traverse to right child
              else
              {
                int right = forest[tree][node].right;
                nodeIndices.set ( x, y, z, right, tree );
#pragma omp critical
                {
                  if ( fasthik != NULL
                       && useCategorization
                       && forest[tree][right].nodeNumber < uniquenumber )
                    ( *globalCategorFeat ) [forest[tree][right].nodeNumber] += weight;
                }
              }
            }
          }
        }
      }
    }

    if ( useRegionFeature )
    {
      int xsize = nodeIndices.width();
      int ysize = nodeIndices.height();
      int zsize = nodeIndices.depth();

#pragma omp parallel for
      for ( int x = 0; x < xsize; x++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int z = 0; z < zsize; z++ )
          {
            for ( int tree = 0; tree < nbTrees; tree++ )
            {
              int node = nodeIndices.get ( x, y, z, tree );
              for ( uint c = 0; c < forest[tree][node].dist.size(); c++ )
              {
                int r = (int) feats ( x, y, z, rawChannels );
                regionProbs[r][c] += forest[tree][node].dist[c];
              }
            }
          }
        }
      }

      int numRegions = (int) regionProbs.size();
      for ( int r = 0; r < numRegions; r++ )
      {
        for ( int c = 0; c < (int) classes; c++ )
        {
          regionProbs[r][c] /= ( double ) ( rSize[r] );
        }
      }
    }

    if ( depth < maxDepth )
    {
      //compute integral images
      if ( firstiteration )
      {
        feats.addChannel ( classes + rawChannels );
      }
      computeIntegralImage ( nodeIndices, feats, channelType.size() - classes );
      if ( firstiteration )
      {
        firstiteration = false;
      }
    }
  }

  vector<int> classesInImg;

  if ( useCategorization )
  {
    if ( cndir != "" )
    {
      for ( int z = 0; z < zsize; z++ )
      {
        vector< string > list;
        StringTools::split ( filelist[z], '/', list );
        string orgname = list.back();

        ifstream infile ( ( cndir + "/" + orgname + ".dat" ).c_str() );
        while ( !infile.eof() && infile.good() )
        {
          int tmp;
          infile >> tmp;
          assert ( tmp >= 0 && tmp < numClasses );
          classesInImg.push_back ( tmp );
        }
      }
    }
    else
    {
      globalCategorFeat->setDim ( uniquenumber );
      globalCategorFeat->normalize();
//       ClassificationResult cr = fasthik->classify ( globalCategorFeat );
      int result;
      SparseVector scores;
      fasthik->classify( globalCategorFeat, result, scores );
      for ( uint i = 0; i < ( uint ) classes; i++ )
      {
        cerr << scores.get(i) << " ";
        if ( scores.get(i) > 0.0/*-0.3*/ )
        {
          classesInImg.push_back ( i );
        }
      }
    }
    cerr << "amount of classes: " << classes << " used classes: " << classesInImg.size() << endl;
  }

  if ( classesInImg.size() == 0 )
  {
    for ( uint i = 0; i < ( uint ) classes; i++ )
    {
      classesInImg.push_back ( i );
    }
  }

  // final labeling step
  if ( pixelWiseLabeling )
  {
    for ( int x = 0; x < xsize; x++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int z = 0; z < zsize; z++ )
        {
          //TODO by nodes instead of pixel?
          double maxProb = - numeric_limits<double>::max();
          int maxClass = 0;

          for ( uint c = 0; c < classesInImg.size(); c++ )
          {
            int i = classesInImg[c];
            double curProb = getMeanProb ( x, y, z, i, nodeIndices );
            probabilities ( x, y, z, labelmapback[i] ) = curProb;

            if ( curProb > maxProb )
            {
              maxProb = curProb;
              maxClass = labelmapback[i];
            }
          }
          assert(maxProb <= 1);

          // copy pixel labeling into segresults (output)
          segresult.set ( x, y, maxClass, ( uint ) z );
        }
      }
    }
#undef VISUALIZE
#ifdef VISUALIZE
    for ( int z = 0; z < zsize; z++ )
    {
      for ( int j = 0 ; j < ( int ) probabilities.channels(); j++ )
      {
        //cout << "class: " << j << endl;//" " << cn.text (j) << endl;

        NICE::Matrix tmp ( probabilities.height(), probabilities.width() );
        double maxval = -numeric_limits<double>::max();
        double minval = numeric_limits<double>::max();


        for ( int y = 0; y < probabilities.height(); y++ )
          for ( int x = 0; x < probabilities.width(); x++ )
          {
            double val = probabilities ( x, y, z, j );
            tmp ( y, x ) = val;
            maxval = std::max ( val, maxval );
            minval = std::min ( val, minval );
          }
        tmp ( 0, 0 ) = 1.0;
        tmp ( 0, 1 ) = 0.0;

        NICE::ColorImage imgrgb ( probabilities.width(), probabilities.height() );
        ICETools::convertToRGB ( tmp, imgrgb );

        cout << "maxval = " << maxval << " minval: " << minval << " for class " << j << endl; //cn.text (j) << endl;

        std::string s;
        std::stringstream out;
        out << "tmpprebmap" << z << "_" << j << ".ppm";
        s = out.str();
        imgrgb.write ( s );
        //showImage(imgrgb, "Ergebnis");
        //getchar();
      }
    }
    cout << "fertsch" << endl;
    getchar();
    cout << "weiter gehtsch" << endl;
#endif
  }
  else
  {
    // labeling by region
    NICE::MultiChannelImageT<int> regions;
    int xsize = feats.width();
    int ysize = feats.height();
    int zsize = feats.depth();
    regions.reInit ( xsize, ysize, zsize );

    if ( useRegionFeature )
    {
      int rchannel = -1;
      for ( uint i = 0; i < channelType.size(); i++ )
      {
        if ( channelType[i] == 1 )
        {
          rchannel = i;
          break;
        }
      }

      assert ( rchannel > -1 );

      for ( int z = 0; z < zsize; z++ )
      {
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int x = 0; x < xsize; x++ )
          {
            regions.set ( x, y, feats ( x, y, z, rchannel ), ( uint ) z );
          }
        }
      }
    }
    else
    {
      amountRegions = segmentation->segRegions ( imgData, regions, imagetype );

#ifdef DEBUG
      for ( unsigned int z = 0; z < ( uint ) zsize; z++ )
      {
        NICE::Matrix regmask;
        NICE::ColorImage colorimg ( xsize, ysize );
        NICE::ColorImage marked ( xsize, ysize );
        regmask.resize ( xsize, ysize );
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int x = 0; x < xsize; x++ )
          {
            regmask ( x,y ) = regions ( x,y,z );
            colorimg.setPixelQuick ( x, y, 0, imgData.get ( x,y,z,0 ) );
            colorimg.setPixelQuick ( x, y, 1, imgData.get ( x,y,z,0 ) );
            colorimg.setPixelQuick ( x, y, 2, imgData.get ( x,y,z,0 ) );
          }
        }
        vector<int> colorvals;
        colorvals.push_back ( 255 );
        colorvals.push_back ( 0 );
        colorvals.push_back ( 0 );
        segmentation->markContours ( colorimg, regmask, colorvals, marked );
        std::vector<string> list;
        StringTools::split ( filelist[z], '/', list );
        string savePath = StringTools::trim ( filelist[z], list.back() ) + "marked/" + list.back();
        marked.write ( savePath );
      }
#endif
    }

    regionProbs.clear();
    regionProbs = vector<vector<double> > ( amountRegions, vector<double> ( classes, 0.0 ) );

    vector<int> bestlabels ( amountRegions, labelmapback[classesInImg[0]] );
    for ( int z = 0; z < zsize; z++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int x = 0; x < xsize; x++ )
        {
          int r = regions ( x, y, ( uint ) z );
          for ( uint i = 0; i < classesInImg.size(); i++ )
          {
            int c = classesInImg[i];
            // get mean voting of all trees
            regionProbs[r][c] += getMeanProb ( x, y, z, c, nodeIndices );
          }
        }
      }
    }

    for ( int r = 0; r < amountRegions; r++ )
    {
      double maxProb = regionProbs[r][classesInImg[0]];
      bestlabels[r] = classesInImg[0];

      for ( int c = 1; c < classes; c++ )
      {
        if ( maxProb < regionProbs[r][c] )
        {
          maxProb = regionProbs[r][c];
          bestlabels[r] = c;
        }
      }

      bestlabels[r] = labelmapback[bestlabels[r]];
    }

    // copy region labeling into segresults (output)
    for ( int z = 0; z < zsize; z++ )
    {
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int x = 0; x < xsize; x++ )
        {
          segresult.set ( x, y, bestlabels[regions ( x,y, ( uint ) z ) ], ( uint ) z );
        }
      }
    }

//#define WRITEREGIONS
#ifdef WRITEREGIONS
    for ( int z = 0; z < zsize; z++ )
    {
      RegionGraph rg;
      NICE::ColorImage img ( xsize,ysize );
      if ( imagetype == IMAGETYPE_RGB )
      {
        img = imgData.getColor ( z );
      }
      else
      {
        NICE::Image gray = imgData.getChannel ( z );
        for ( int y = 0; y < ysize; y++ )
        {
          for ( int x = 0; x < xsize; x++ )
          {
            int val = gray.getPixelQuick ( x,y );
            img.setPixelQuick ( x, y, val, val, val );
          }
        }
      }

      Matrix regions_tmp ( xsize,ysize );
      for ( int y = 0; y < ysize; y++ )
      {
        for ( int x = 0; x < xsize; x++ )
        {
          regions_tmp ( x,y ) = regions ( x,y, ( uint ) z );
        }
      }
      segmentation->getGraphRepresentation ( img, regions_tmp,  rg );
      for ( uint pos = 0; pos < regionProbs.size(); pos++ )
      {
        rg[pos]->setProbs ( regionProbs[pos] );
      }

      std::string s;
      std::stringstream out;
      std::vector< std::string > list;
      StringTools::split ( filelist[z], '/', list );

      out << "rgout/" << list.back() << ".graph";
      string writefile = out.str();
      rg.write ( writefile );
    }
#endif
  }

  delete globalCategorFeat;
  cout << "segmentation finished" << endl;
}

void SemSegContextTree::store ( std::ostream & os, int format ) const
{
  os.precision ( numeric_limits<double>::digits10 + 1 );
  os << nbTrees << endl;
  classnames.store ( os );

  map<int, int>::const_iterator it;

  os << labelmap.size() << endl;
  for ( it = labelmap.begin() ; it != labelmap.end(); it++ )
    os << ( *it ).first << " " << ( *it ).second << endl;

  os << labelmapback.size() << endl;
  for ( it = labelmapback.begin() ; it != labelmapback.end(); it++ )
    os << ( *it ).first << " " << ( *it ).second << endl;

  int trees = forest.size();
  os << trees << endl;

  for ( int t = 0; t < trees; t++ )
  {
    int nodes = forest[t].size();
    os << nodes << endl;
    for ( int n = 0; n < nodes; n++ )
    {
      os << forest[t][n].left << " " << forest[t][n].right << " " << forest[t][n].decision << " " << forest[t][n].isleaf << " " << forest[t][n].depth << " " << forest[t][n].featcounter << " " << forest[t][n].nodeNumber << endl;
      os << forest[t][n].dist << endl;

      if ( forest[t][n].feat == NULL )
        os << -1 << endl;
      else
      {
        os << forest[t][n].feat->getOps() << endl;
        forest[t][n].feat->store ( os );
      }
    }
  }

  os << channelType.size() << endl;
  for ( int i = 0; i < ( int ) channelType.size(); i++ )
  {
    os << channelType[i] << " ";
  }
  os << endl;

  os << integralMap.size() << endl;
  for ( int i = 0; i < ( int ) integralMap.size(); i++ )
  {
    os << integralMap[i].first << " " << integralMap[i].second << endl;
  }

  os << rawChannels << endl;

  os << uniquenumber << endl;
}

void SemSegContextTree::restore ( std::istream & is, int format )
{
  is >> nbTrees;

  classnames.restore ( is );

  int lsize;
  is >> lsize;

  labelmap.clear();
  for ( int l = 0; l < lsize; l++ )
  {
    int first, second;
    is >> first;
    is >> second;
    labelmap[first] = second;
  }

  is >> lsize;
  labelmapback.clear();
  for ( int l = 0; l < lsize; l++ )
  {
    int first, second;
    is >> first;
    is >> second;
    labelmapback[first] = second;
  }

  int trees;
  is >> trees;
  forest.clear();


  for ( int t = 0; t < trees; t++ )
  {
    vector<TreeNode> tmptree;
    forest.push_back ( tmptree );
    int nodes;
    is >> nodes;

    for ( int n = 0; n < nodes; n++ )
    {
      TreeNode tmpnode;
      forest[t].push_back ( tmpnode );
      is >> forest[t][n].left;
      is >> forest[t][n].right;
      is >> forest[t][n].decision;
      is >> forest[t][n].isleaf;
      is >> forest[t][n].depth;
      is >> forest[t][n].featcounter;
      is >> forest[t][n].nodeNumber;

      is >> forest[t][n].dist;

      int feattype;
      is >> feattype;
      assert ( feattype < NBOPERATIONS );
      forest[t][n].feat = NULL;

      if ( feattype >= 0 )
      {
        for ( uint o = 0; o < ops.size(); o++ )
        {
          for ( uint o2 = 0; o2 < ops[o].size(); o2++ )
          {
            if ( forest[t][n].feat == NULL )
            {
              for ( uint c = 0; c < ops[o].size(); c++ )
              {
                if ( ops[o][o2]->getOps() == feattype )
                {
                  forest[t][n].feat = ops[o][o2]->clone();
                  break;
                }
              }
            }
          }
        }

        assert ( forest[t][n].feat != NULL );
        forest[t][n].feat->restore ( is );

      }
    }
  }

  channelType.clear();
  int ctsize;
  is >> ctsize;
  for ( int i = 0; i < ctsize; i++ )
  {
    int tmp;
    is >> tmp;
    channelType.push_back ( tmp );
  }

  integralMap.clear();
  int iMapSize;
  is >> iMapSize;
  for ( int i = 0; i < iMapSize; i++ )
  {
    int first;
    int second;
    is >> first;
    is >> second;
    integralMap.push_back ( pair<int, int> ( first, second ) );
  }

  is >> rawChannels;

  is >> uniquenumber;
}