examples/radon_transform2d.cpp

/*
 #
 #  File        : radon_transform2d.cpp
 #                ( C++ source file )
 #
 #  Description : An implementation of the Radon Transform.
 #                This file is a part of the CImg Library project.
 #                ( http://cimg.eu )
 #
 #  Copyright   : David G. Starkweather
 #                ( starkdg@sourceforge.net - starkweatherd@cox.net )
 #
 #  License     : CeCILL v2.0
 #                ( http://www.cecill.info/licences/Licence_CeCILL_V2-en.html )
 #
 #  This software is governed by the CeCILL  license under French law and
 #  abiding by the rules of distribution of free software.  You can  use,
 #  modify and/ or redistribute the software under the terms of the CeCILL
 #  license as circulated by CEA, CNRS and INRIA at the following URL
 #  "http://www.cecill.info".
 #
 #  As a counterpart to the access to the source code and  rights to copy,
 #  modify and redistribute granted by the license, users are provided only
 #  with a limited warranty  and the software's author,  the holder of the
 #  economic rights,  and the successive licensors  have only  limited
 #  liability.
 #
 #  In this respect, the user's attention is drawn to the risks associated
 #  with loading,  using,  modifying and/or developing or reproducing the
 #  software by the user in light of its specific status of free software,
 #  that may mean  that it is complicated to manipulate,  and  that  also
 #  therefore means  that it is reserved for developers  and  experienced
 #  professionals having in-depth computer knowledge. Users are therefore
 #  encouraged to load and test the software's suitability as regards their
 #  requirements in conditions enabling the security of their systems and/or
 #  data to be ensured and,  more generally, to use and operate it in the
 #  same conditions as regards security.
 #
 #  The fact that you are presently reading this means that you have had
 #  knowledge of the CeCILL license and that you accept its terms.
 #
*/

#include "CImg.h"
using namespace cimg_library;
#ifndef cimg_imagepath
#define cimg_imagepath "img/"
#endif

#define ROUNDING_FACTOR(x) (((x) >= 0) ? 0.5 : -0.5)

CImg<double> GaussianKernel(double rho);
CImg<float> ApplyGaussian(CImg<unsigned char> im,double rho);
CImg<unsigned char> RGBtoGrayScale(CImg<unsigned char> &im);
int GetAngle(int dy,int dx);
CImg<unsigned char> CannyEdges(CImg<float> im, double T1, double T2,bool doHysteresis);
CImg<> RadonTransform(CImg<unsigned char> im,int N);

// Main procedure
//----------------
int main(int argc,char **argv) {
  cimg_usage("Illustration of the Radon Transform");

  const char *file = cimg_option("-f",cimg_imagepath "parrot.ppm","path and file name");
  const double sigma = cimg_option("-r",1.0,"blur coefficient for gaussian low pass filter (lpf)"),
    thresh1 = cimg_option("-t1",0.50,"lower threshold for canny edge detector"),
    thresh2 = cimg_option("-t2",1.25,"upper threshold for canny edge detector");;
  const int N = cimg_option("-n",64,"number of angles to consider in the Radon transform - should be a power of 2");

  //color to draw lines
  const unsigned char green[] = {0,255,0};
  CImg<unsigned char> src(file);

  int rhomax = (int)std::sqrt((double)(src.width()*src.width() + src.height()*src.height()))/2;

  if (cimg::dialog(cimg::basename(argv[0]),
                   "Instructions:\n"
                   "Click on space bar or Enter key to display Radon transform of given image\n"
                   "Click on anywhere in the transform window to display a \n"
                   "corresponding green line in the original image\n",
                   "Start", "Quit",0,0,0,0,
                   src.get_resize(100,100,1,3),true)) std::exit(0);

  //retrieve a grayscale from the image
  CImg<unsigned char> grayScaleIm;
  if ((src.spectrum() == 3) && (src.width() > 0) && (src.height() > 0) && (src.depth() == 1))
    grayScaleIm = (CImg<unsigned char>)src.get_norm(0).quantize(255,false);
  else if ((src.spectrum() == 1)&&(src.width() > 0) && (src.height() > 0) && (src.depth() == 1))
    grayScaleIm = src;
  else { // image in wrong format
    if (cimg::dialog(cimg::basename("wrong file format"),
                     "Incorrect file format\n","OK",0,0,0,0,0,
                     src.get_resize(100,100,1,3),true)) std::exit(0);
  }

  //blur the image with a Gaussian lpf to remove spurious edges (e.g. noise)
  CImg<float> blurredIm = ApplyGaussian(grayScaleIm,sigma);

  //use canny edge detection algorithm to get edge map of the image
  //- the threshold values are used to perform hysteresis in the edge detection process
  CImg<unsigned char> cannyEdgeMap = CannyEdges(blurredIm,thresh1,thresh2,false);
  CImg<unsigned char> radonImage = *(new CImg<unsigned char>(500,400,1,1,0));

  //display the two windows
  CImgDisplay dispImage(src,"original image");
  dispImage.move(CImgDisplay::screen_width()/8,CImgDisplay::screen_height()/8);
  CImgDisplay dispRadon(radonImage,"Radon Transform");
  dispRadon.move(CImgDisplay::screen_width()/4,CImgDisplay::screen_height()/4);
  CImgDisplay dispCanny(cannyEdgeMap,"canny edges");
  //start main display loop
  while (!dispImage.is_closed() && !dispRadon.is_closed() &&
         !dispImage.is_keyQ() && !dispRadon.is_keyQ() &&
         !dispImage.is_keyESC() && !dispRadon.is_keyESC()) {

    CImgDisplay::wait(dispImage,dispRadon);

    if (dispImage.is_keySPACE() || dispRadon.is_keySPACE()) {
      radonImage = (CImg<unsigned char>)RadonTransform(cannyEdgeMap,N).quantize(255,false).resize(500,400);
      radonImage.display(dispRadon);
    }

    //when clicking on dispRadon window, draw line in original image window
    if (dispRadon.button())
      {
        const double rho = dispRadon.mouse_y()*rhomax/dispRadon.height(),
          theta = (dispRadon.mouse_x()*N/dispRadon.width())*2*cimg::PI/N,
          x = src.width()/2 + rho*std::cos(theta),
          y = src.height()/2 + rho*std::sin(theta);
        const int x0 = (int)(x + 1000*std::cos(theta + cimg::PI/2)),
          y0 = (int)(y + 1000*std::sin(theta + cimg::PI/2)),
          x1 = (int)(x - 1000*std::cos(theta + cimg::PI/2)),
          y1 = (int)(y - 1000*std::sin(theta + cimg::PI/2));
        src.draw_line(x0,y0,x1,y1,green,1.0f,0xF0F0F0F0).display(dispImage);
      }
  }
  return 0;
}
/**
 * PURPOSE: create a 5x5 gaussian kernel matrix
 * PARAM rho - gaussiam equation parameter (default = 1.0)
 * RETURN CImg<double> the gaussian kernel
 **/

CImg<double> GaussianKernel(double sigma = 1.0)
{
  CImg<double> resultIm(5,5,1,1,0);
  int midX = 3, midY = 3;
  cimg_forXY(resultIm,X,Y) {
    resultIm(X,Y) = std::ceil(256.0*(std::exp(-(midX*midX + midY*midY)/(2*sigma*sigma)))/(2*cimg::PI*sigma*sigma));
  }
  return resultIm;
}
/*
 * PURPOSE: convolve a given image with the gaussian kernel
 * PARAM CImg<unsigned char> im - image to be convolved upon
 * PARAM double sigma - gaussian equation parameter
 * RETURN CImg<float> image resulting from the convolution
 * */
CImg<float> ApplyGaussian(CImg<unsigned char> im,double sigma)
{
  CImg<float> smoothIm(im.width(),im.height(),1,1,0);

  //make gaussian kernel
  CImg<float> gk = GaussianKernel(sigma);
  //apply gaussian

  CImg_5x5(I,int);
  cimg_for5x5(im,X,Y,0,0,I,int) {
    float sum = 0;
    sum += gk(0,0)*Ibb + gk(0,1)*Ibp + gk(0,2)*Ibc + gk(0,3)*Ibn + gk(0,4)*Iba;
    sum += gk(1,0)*Ipb + gk(1,1)*Ipp + gk(1,2)*Ipc + gk(1,3)*Ipn + gk(1,4)*Ipa;
    sum += gk(2,0)*Icb + gk(2,1)*Icp + gk(2,2)*Icc + gk(2,3)*Icn + gk(2,4)*Ica;
    sum += gk(3,0)*Inb + gk(3,1)*Inp + gk(3,2)*Inc + gk(3,3)*Inn + gk(3,4)*Ina;
    sum += gk(4,0)*Iab + gk(4,1)*Iap + gk(4,2)*Iac + gk(4,3)*Ian + gk(4,4)*Iaa;
    smoothIm(X,Y) = sum/256;
  }
  return smoothIm;
}
/**
 * PURPOSE: convert a given rgb image to a MxNX1 single vector grayscale image
 * PARAM: CImg<unsigned char> im - rgb image to convert
 * RETURN: CImg<unsigned char> grayscale image with MxNx1x1 dimensions
 **/

CImg<unsigned char> RGBtoGrayScale(CImg<unsigned char> &im)
{
  CImg<unsigned char> grayImage(im.width(),im.height(),im.depth(),1,0);
  if (im.spectrum() == 3) {
    cimg_forXYZ(im,X,Y,Z) {
      grayImage(X,Y,Z,0) = (unsigned char)(0.299*im(X,Y,Z,0) + 0.587*im(X,Y,Z,1) + 0.114*im(X,Y,Z,2));
    }
  }
  grayImage.quantize(255,false);
  return grayImage;
}
/**
 * PURPOSE: aux. function used by CannyEdges to quantize an angle theta given by gradients, dx and dy
 *  into 0 - 7
 * PARAM: dx,dy - gradient magnitudes
 * RETURN int value between 0 and 7
 **/
int GetAngle(int dy,int dx)
{
  double angle = cimg::abs(std::atan2((double)dy,(double)dx));
  if ((angle >= -cimg::PI/8)&&(angle <= cimg::PI/8))//-pi/8 to pi/8 => 0
    return 0;
  else if ((angle >= cimg::PI/8)&&(angle <= 3*cimg::PI/8))//pi/8 to 3pi/8 => pi/4
    return 1;
  else if ((angle > 3*cimg::PI/8)&&(angle <= 5*cimg::PI/8))//3pi/8 to 5pi/8 => pi/2
    return 2;
  else if ((angle > 5*cimg::PI/8)&&(angle <= 7*cimg::PI/8))//5pi/8 to 7pi/8 => 3pi/4
    return 3;
  else if (((angle > 7*cimg::PI/8) && (angle <= cimg::PI)) ||
           ((angle <= -7*cimg::PI/8)&&(angle >= -cimg::PI))) //-7pi/8 to -pi OR 7pi/8 to pi => pi
    return 4;
  else return 0;
}
/**
 * PURPOSE: create an edge map of the given image with hysteresis using thresholds T1 and T2
 * PARAMS: CImg<float> im the image to perform edge detection on
 * 		   T1 lower threshold
 *         T2 upper threshold
 * RETURN CImg<unsigned char> edge map
 **/
CImg<unsigned char> CannyEdges(CImg<float> im, double T1, double T2, bool doHysteresis=false)
{
  CImg<unsigned char> edges(im);
  CImg<float> secDerivs(im);
  secDerivs.fill(0);
  edges.fill(0);
  CImgList<float> gradients = im.get_gradient("xy",1);
  int image_width = im.width();
  int image_height = im.height();

  cimg_forXY(im,X,Y) {
    double Gr = std::sqrt(std::pow((double)gradients[0](X,Y),2.0) + std::pow((double)gradients[1](X,Y),2.0));
    double theta = GetAngle(Y,X);
    //if Gradient magnitude is positive and X,Y within the image
    //take the 2nd deriv in the appropriate direction
    if ((Gr > 0)&&(X < image_width - 2)&&(Y < image_height - 2)) {
      if (theta == 0)
        secDerivs(X,Y) = im(X + 2,Y) - 2*im(X + 1,Y) + im(X,Y);
      else if (theta == 1)
        secDerivs(X,Y) = im(X + 2,Y + 2) - 2*im(X + 1,Y + 1) + im(X,Y);
      else if (theta == 2)
        secDerivs(X,Y) = im(X,Y + 2) - 2*im(X,Y + 1) + im(X,Y);
      else if (theta == 3)
        secDerivs(X,Y) = im(X + 2,Y + 2) - 2*im(X + 1,Y + 1) + im(X,Y);
      else if (theta == 4)
        secDerivs(X,Y) = im(X + 2,Y) - 2*im(X + 1,Y) + im(X,Y);
    }
  }
  //for each 2nd deriv that crosses a zero point and magnitude passes the upper threshold.
  //Perform hysteresis in the direction of the gradient, rechecking the gradient
  //angle for each pixel that meets the threshold requirement.  Stop checking when
  //the lower threshold is not reached.
  CImg_5x5(I,float);
  cimg_for5x5(secDerivs,X,Y,0,0,I,float) {
    if (   (Ipp*Ibb < 0) ||
           (Ipc*Ibc < 0)||
           (Icp*Icb < 0)   ) {
      double Gr = std::sqrt(std::pow((double)gradients[0](X,Y),2.0) + std::pow((double)gradients[1](X,Y),2.0));
      int dir = GetAngle(Y,X);
      int Xt = X, Yt = Y, delta_x = 0, delta_y=0;
      double GRt = Gr;
      if (Gr >= T2)
        edges(X,Y) = 255;
      //work along the gradient in one direction
      if (doHysteresis) {
        while ((Xt > 0) && (Xt < image_width - 1) && (Yt > 0) && (Yt < image_height - 1)) {
          switch (dir){
          case 0 : delta_x=0;delta_y=1;break;
          case 1 : delta_x=1;delta_y=1;break;
          case 2 : delta_x=1;delta_y=0;break;
          case 3 : delta_x=1;delta_y=-1;break;
          case 4 : delta_x=0;delta_y=1;break;
          }
          Xt += delta_x;
          Yt += delta_y;
          GRt = std::sqrt(std::pow((double)gradients[0](Xt,Yt),2.0) + std::pow((double)gradients[1](Xt,Yt),2.0));
          dir = GetAngle(Yt,Xt);
          if (GRt >= T1)
            edges(Xt,Yt) = 255;
        }
        //work along gradient in other direction
        Xt = X; Yt = Y;
        while ((Xt > 0) && (Xt < image_width - 1) && (Yt > 0) && (Yt < image_height - 1)) {
          switch (dir){
          case 0 : delta_x=0;delta_y=1;break;
          case 1 : delta_x=1;delta_y=1;break;
          case 2 : delta_x=1;delta_y=0;break;
          case 3 : delta_x=1;delta_y=-1;break;
          case 4 : delta_x=0;delta_y=1;break;
          }
          Xt -= delta_x;
          Yt -= delta_y;
          GRt = std::sqrt(std::pow((double)gradients[0](Xt,Yt),2.0) + std::pow((double)gradients[1](Xt,Yt),2.0));
          dir = GetAngle(Yt,Xt);
          if (GRt >= T1)
            edges(Xt,Yt) = 255;
        }
      }
    }
  }
  return edges;
}
/**
 * PURPOSE: perform radon transform of given image
 * PARAM: CImg<unsigned char> im - image to detect lines
 * 		  int N - number of angles to consider (should be a power of 2)
 *                (the values of N will be spread over 0 to 2PI)
 * RETURN CImg<unsigned char> - transform of given image of size, N x D
 *                              D = rhomax = sqrt(dimx*dimx + dimy*dimy)/2
 **/
CImg<> RadonTransform(CImg<unsigned char> im,int N) {
  int image_width = im.width();
  int image_height = im.height();

  //calc offsets to center the image
  float xofftemp = image_width/2.0f - 1;
  float yofftemp = image_height/2.0f - 1;
  int xoffset = (int)std::floor(xofftemp + ROUNDING_FACTOR(xofftemp));
  int yoffset = (int)std::floor(yofftemp + ROUNDING_FACTOR(yofftemp));
  float dtemp = (float)std::sqrt((double)(xoffset*xoffset + yoffset*yoffset));
  int D = (int)std::floor(dtemp + ROUNDING_FACTOR(dtemp));

  CImg<> imRadon(N,D,1,1,0);

  //for each angle k to consider
  for (int k= 0 ; k < N; k++) {
    //only consider from PI/8 to 3PI/8 and 5PI/8 to 7PI/8
    //to avoid computational complexity of a steep angle
    if (k == 0){k = N/8;continue;}
    else if (k == (3*N/8 + 1)){	k = 5*N/8;continue;}
    else if (k == 7*N/8 + 1){k = N;	continue;}

    //for each rho length, determine linear equation and sum the line
    //sum is to sum the values along the line at angle k2pi/N
    //sum2 is to sum the values along the line at angle k2pi/N + N/4
    //The sum2 is performed merely by swapping the x,y axis as if the image were rotated 90 degrees.
    for (int d=0; d < D; d++) {
      double theta = 2*k*cimg::PI/N;//calculate actual theta
      double alpha = std::tan(theta + cimg::PI/2);//calculate the slope
      double beta_temp = -alpha*d*std::cos(theta) + d*std::sin(theta);//y-axis intercept for the line
      int beta = (int)std::floor(beta_temp + ROUNDING_FACTOR(beta_temp));
      //for each value of m along x-axis, calculate y
      //if the x,y location is within the boundary for the respective image orientations, add to the sum
      unsigned int sum1 = 0,
        sum2 = 0;
      int M = (image_width >= image_height) ? image_width : image_height;
      for (int m=0;m < M; m++) {
        //interpolate in-between values using nearest-neighbor approximation
        //using m,n as x,y indices into image
        double n_temp = alpha*(m - xoffset) + beta;
        int n = (int)std::floor(n_temp + ROUNDING_FACTOR(n_temp));
        if ((m < image_width) && (n + yoffset >= 0) && (n + yoffset < image_height))
          {
            sum1 += im(m, n + yoffset);
          }
        n_temp = alpha*(m - yoffset) + beta;
        n = (int)std::floor(n_temp + ROUNDING_FACTOR(n_temp));
        if ((m < image_height)&&(n + xoffset >= 0)&&(n + xoffset < image_width))
          {
            sum2 += im(-(n + xoffset) + image_width - 1, m);
          }
      }
      //assign the sums into the result matrix
      imRadon(k,d) = (float)sum1;
      //assign sum2 to angle position for theta + PI/4
      imRadon(((k + N/4)%N),d) = (float)sum2;
    }
  }
  return imRadon;
}
/* references:
 * 1. See Peter Toft's thesis on the Radon transform: http://petertoft.dk/PhD/index.html
 * While I changed his basic algorithm, the main idea is still the same and provides an excellent explanation.
 *
 * */