SuperPixel.H

/*!@file Gist/test-SuperPixel.C testing SuperPixel segmentation algorithm */
// //////////////////////////////////////////////////////////////////// //
// The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2001 by the //
// University of Southern California (USC) and the iLab at USC.         //
// See http://iLab.usc.edu for information about this project.          //
// //////////////////////////////////////////////////////////////////// //
// Major portions of the iLab Neuromorphic Vision Toolkit are protected //
// under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
// in Visual Environments, and Applications'' by Christof Koch and      //
// Laurent Itti, California Institute of Technology, 2001 (patent       //
// pending; application number 09/912,225 filed July 23, 2001; see      //
// http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
// //////////////////////////////////////////////////////////////////// //
// This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
//                                                                      //
// The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
// redistribute it and/or modify it under the terms of the GNU General  //
// Public License as published by the Free Software Foundation; either  //
// version 2 of the License, or (at your option) any later version.     //
//                                                                      //
// The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
// that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
// implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
// PURPOSE.  See the GNU General Public License for more details.       //
//                                                                      //
// You should have received a copy of the GNU General Public License    //
// along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
// to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
// Boston, MA 02111-1307 USA.                                           //
// //////////////////////////////////////////////////////////////////// //
//
// Primary maintainer for this file: Christian Siagian <siagian@usc.edu>
// $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/Gist/SuperPixel.H $
// $Id: SuperPixel.H 14762 2011-05-03 01:13:16Z siagian $
//
//////////////////////////////////////////////////////////////////////////
//
// Implementation of the segmentation algorithm described in:
//
// Efficient Graph-Based Image Segmentation
// Pedro F. Felzenszwalb and Daniel P. Huttenlocher
// International Journal of Computer Vision, 59(2) September 2004.
// Copyright (C) 2006 Pedro Felzenszwalb

#ifndef SUPERPIXEL_SEGMENT_IMAGE
#define SUPERPIXEL_SEGMENT_IMAGE

#include <cstdlib>

#include "Image/Image.H"
#include "Image/Pixels.H"
#include "Raster/Raster.H"
#include "Image/MathOps.H"
#include "Image/ColorOps.H"

#include "Gist/SuperPixel_filter.H"
#include "Gist/SuperPixel_segment_graph.H"

#include "Util/Timer.H"

// random color
PixRGB<byte> random_rgb(){ 
  PixRGB<byte> c((byte)random(),
                 (byte)random(),
                 (byte)random());
  return c;
}

// dissimilarity measure between pixels
static inline float 
diff(Image<float> r, Image<float> g, Image<float> b,
     int x1, int y1, int x2, int y2) 
{
  return sqrt(pow(r.getVal(x1, y1) - r.getVal(x2, y2), 2.0) +
              pow(g.getVal(x1, y1) - g.getVal(x2, y2), 2.0) +
              pow(b.getVal(x1, y1) - b.getVal(x2, y2), 2.0));
}
// dissimilarity measure between pixels
static inline float 
diff(std::vector<Image<float> > channels,
     int x1, int y1, int x2, int y2) 
{
  float difference = 0.0;
  std::vector<Image<float> >::iterator 
    it = channels.begin(), 
    stop = channels.end();
  for (;it!=stop; ++it) 
    {
      Image<float> ch = *it;
      difference+= pow(ch.getVal(x1, y1) - ch.getVal(x2, y2), 2.0) ;
    }
  
  return sqrt(difference);
}



//! Segment an image using Super Pixel Segmentation.
/*!
 * Returns an integer image where the value at each pixel denotes the
 * group it belongs to.  Additionally, if a groups vector is supplied,
 * it will be filled with vectors of points belonging to each group.
 *
 * \param im image to segment.
 * \param sigma to smooth the image.
 * \param c constant for treshold function.
 * \param min_size minimum component size (enforced by post-processing stage).
 * \param num_ccs number of connected components in the segmentation.
 * \param channels :instead use default RGB channels, it takes all channels as graph base 
 *
 */

// ######################################################################
Image<int> SuperPixelSegment
(Image<PixRGB<byte> > im, 
 float sigma, float c, int min_size, int &num_ccs, 
 std::vector<std::vector<Point2D<int> > > *groups , 
 std::vector<Image<float> > channels )
{
  //smooth out each channel
  std::vector<Image<float> > smooth_channels;
  std::vector<Image<float> >::iterator 
    it = channels.begin(), 
    stop = channels.end();
  for (;it!=stop; ++it) {
          Image<float> ch = *it;
          Image<float> smooth_temp = smooth(ch, sigma);
          smooth_channels.push_back(smooth_temp);
  }
 
  int width  = im.getWidth();
  int height = im.getHeight();

  // build graph
  edge *edges = new edge[width*height*4];
  int num = 0;
  for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
      if (x < width-1) {
        edges[num].a = y * width + x;
        edges[num].b = y * width + (x+1);
        edges[num].w = diff(smooth_channels, x, y, x+1, y);
        num++;
      }

      if (y < height-1) {
        edges[num].a = y * width + x;
        edges[num].b = (y+1) * width + x;
        edges[num].w = diff(smooth_channels, x, y, x, y+1);
        num++;
      }

      if ((x < width-1) && (y < height-1)) {
        edges[num].a = y * width + x;
        edges[num].b = (y+1) * width + (x+1);
        edges[num].w = diff(smooth_channels, x, y, x+1, y+1);
        num++;
      }

      if ((x < width-1) && (y > 0)) {
        edges[num].a = y * width + x;
        edges[num].b = (y-1) * width + (x+1);
        edges[num].w = diff(smooth_channels, x, y, x+1, y-1);
        num++;
      }
    }
  }

  // segment
  universe *u = segment_graph(width*height, num, edges, c);

  // post process small components
  for (int i = 0; i < num; i++) {
    int a = u->find(edges[i].a);
    int b = u->find(edges[i].b);
    if ((a != b) && ((u->size(a) < min_size) || (u->size(b) < min_size)))
      u->join(a, b);
  }
  delete [] edges;
  num_ccs = u->num_sets();

  Image<int> groupImage(width, height, NO_INIT);

  // If a group vector is provided, then let's resize it and fill it along
  // with the output image
  groups->resize(u->num_sets());
  
  // The group numbers created by the algorithm are more or less random. We
  // need to compress them so we can easily insert the group points into
  // vectors.
  std::map<int, int> groupLabels; 
  int labelCount = 0;
  
  for (int y = 0; y < height; y++) 
    for (int x = 0; x < width; x++) 
      {
        int groupUnorderedId = u->find(y * width + x);
        
        // If we haven't seen this group before, 
        // create a new ordered label for it
        if(groupLabels.find(groupUnorderedId) == groupLabels.end())
          groupLabels[groupUnorderedId] = labelCount++;
        
        int groupOrderedId = groupLabels[groupUnorderedId];
        
        if(groups != NULL)
          (*groups)[groupOrderedId].push_back(Point2D<int>(x,y));
        groupImage.setVal(x, y, groupOrderedId);
      }
  
  delete u;
  
  return groupImage;
}

// ######################################################################
Image<int> SuperPixelSegment
(Image<PixRGB<byte> > im, 
 float sigma, float c, int min_size, int &num_ccs, 
 std::vector<std::vector<Point2D<int> > > *groups)
{
  Image<byte> r, g, b; getComponents(im, r, g, b);

  std::vector<Image<float> > channels;
  channels.push_back(r);        
  channels.push_back(g);        
  channels.push_back(b);        

  return SuperPixelSegment
    (im,sigma,c,min_size,num_ccs,groups,channels);
}

// ######################################################################
namespace
{ std::vector<PixRGB<byte> > groupColors; }

// ######################################################################
Image<int> SuperPixelRegionSizeImage 
(std::vector<std::vector<Point2D<int> > > const& groups, Image<int> groupImage)
{
        Image<int> debugSizeImage(groupImage.getDims(), NO_INIT);

  for(size_t grpIdx=0; grpIdx < groups.size(); grpIdx++)
  {
    int regionSize =  (int) groups[grpIdx].size();
    for(size_t pntIdx=0; pntIdx<groups[grpIdx].size(); pntIdx++)
      debugSizeImage.setVal(groups[grpIdx][pntIdx], regionSize);
  }
  
  return debugSizeImage;
}

// ######################################################################
Image<PixRGB<byte> > SuperPixelDebugImage(Image<int> groupImage)
{
  // pick random colors for each component
  if(groupColors.size() == 0)
    {
      groupColors.resize(255);
      std::vector<PixRGB<byte> >::iterator 
        it = groupColors.begin(), 
        stop = groupColors.end();
      for (;it!=stop; ++it) *it = random_rgb();
    }
  
  Image<PixRGB<byte> > debugImage(groupImage.getDims(), NO_INIT);
  
  for(size_t i=0; i<groupImage.size(); ++i)
    debugImage.setVal
      (i,groupColors[groupImage.getVal(i)%groupColors.size()]);
  
  return debugImage;
}

// ######################################################################
Image<PixRGB<byte> > SuperPixelDebugImage
(std::vector<std::vector<Point2D<int> > > const& groups, 
 Image<PixRGB<byte> > originalImage)
{
  Image<PixRGB<byte> > debugImage(originalImage.getDims(), NO_INIT);
  
  for(size_t grpIdx=0; grpIdx < groups.size(); grpIdx++)
  {
    PixRGB<long> avgColor(0,0,0);
    for(size_t pntIdx=0; pntIdx<groups[grpIdx].size(); pntIdx++)
      avgColor += originalImage.getVal(groups[grpIdx][pntIdx]);
    avgColor /= groups[grpIdx].size();
    for(size_t pntIdx=0; pntIdx<groups[grpIdx].size(); pntIdx++)
      debugImage.setVal(groups[grpIdx][pntIdx], avgColor);
  }
  
  return debugImage;
}

/*
 * Segment an image
 *
 * Returns a color image representing the segmentation.
 *
 * im: image to segment.
 * sigma: to smooth the image.
 * c: constant for treshold function.
 * min_size: minimum component size (enforced by post-processing stage).
 * num_ccs: number of connected components in the segmentation.


 :::::NOTE::::: This method is now deprecated. 
 Please use SuperPixelSegment, and SuperPixelDebugImage instead.

 */
// ######################################################################
Image<PixRGB<byte> > segment_image
(Image<PixRGB<byte> > im, float sigma, float c, int min_size,
 int &num_ccs)
{
        LINFO("This method is now deprecated. "
              "Please use SuperPixelSegment "
              "and SuperPixelDebugImage instead.");
        std::vector<std::vector<Point2D<int> > > groups;
        Image<int> groupImage = 
          SuperPixelSegment
          (im, sigma, c, min_size, num_ccs, &groups);
        return SuperPixelDebugImage(groups,im);
}

#endif

// ######################################################################
/* So things look consistent in everyone's emacs... */
/* Local Variables: */
/* indent-tabs-mode: nil */
/* End: */