Tutorial: Gradient-based Circle Hough Transform

Introduction

The Circle Hough Transform (CHT) is an image processing algorithm that permits to detect circles in an image. We refer the interested reader to the Wikipedia page to have a better understanding on the principles of the algorithm.

The ViSP implementation relies on the Gradient-based implementation of the algorithm.

During the step where the algorithm votes for center candidates, we use the gradient information in order to reduce the dimensionality of the search space. Instead of voting in circular pattern, we vote along a straight line that follows the gradient.

Then, during the step where the algorithm votes for radius candidates for each center candidate, we check the colinearity between the gradient at a considered point and the line which links the point towards the center candidate. If they are "enough" colinear, we increment the corresponding radius bin vote by 1. (NB: instead of incrementing one bin by one, we increment two bins by a number between 0 and 1 in our implementation to be more robust against the limits min and max of the radius and the bin size). The "enough" characteristic is controlled by the circle perfectness parameter.

How to use the tutorial

It is possible to configure the vpCircleHoughTransform class using a JSON file. To do so, you need to install JSON for modern C++ and compile ViSP with it.

You can also configure the vpCircleHoughTransform class using command line arguments. To know what are the different command line arguments the software accept, please run:

$ cd tutorial/imgproc/hough-transform
$ ./tutorial-circle-hough --help

To run the software on an image like coins2.jpg provided with the tutorial and using a JSON configuration file, please run:

$ ./tutorial-circle-hough --input coins2.jpg --config config/detector_img.json

If you would rather use the command line arguments, please run:

$ ./tutorial-circle-hough --input coins2.jpg \
    --averaging-window-size 5 \
    --canny-backend opencv-backend \
    --filtering-type gaussianblur+scharr-filtering \
    --canny-thresh -1 -1 \
    --lower-canny-ratio 0.6 \
    --upper-canny-ratio 0.9 \
    --gaussian-kernel 5 \
    --gaussian-sigma 1 \
    --dilatation-kernel-size 5 \
    --center-thresh 70 \
    --circle-probability-thresh 0.725 \
    --radius-limits 34 75 \
    --merging-thresh 5 5 \
    --circle-perfectness 0.65 \
    --circle-probability-thresh 0.725 \
    --center-xlim 0 1920 \
    --center-ylim 0 1080 \
    --expected-nb-centers -1 \
    --edge-filter 3 \
    --gradient-kernel 3

Note

The configuration file config/detector_img.json has been tuned to detect circles in the image coins2.jpg. If the detections seem a bit off, you might need to change the parameters in config/detector_img.json or in the command line.

The default values of the program corresponds to these fine-tuned parameters. Running the program without any additional parameters should give the same result:

./tutorial-circle-hough

How to use a video

You can use the software to run circle detection on a video saved as a sequence of images that are named

${BASENAME}%d.png

For instance with ${BASENAME} = video_, you can have the following list of images: video_0001.png, video_0002.png and so on.

To run the software using a JSON configuration file, please run:

$ ./tutorial-circle-hough --input /path/to/video/${BASENAME}%d.png --config config/detector_img.json

To run the software using the command arguments, please run:

$ ./tutorial-circle-hough --input /path/to/video/${BASENAME}%d.png \
    --averaging-window-size 5 \
    --canny-backend opencv-backend \
    --filtering-type gaussianblur+scharr-filtering \
    --canny-thresh -1 -1 \
    --lower-canny-ratio 0.6 \
    --upper-canny-ratio 0.9 \
    --gaussian-kernel 5 \
    --gaussian-sigma 1 \
    --dilatation-kernel-size 5 \
    --center-thresh 70 \
    --circle-probability-thresh 0.725 \
    --radius-limits 34 75 \
    --merging-thresh 5 5 \
    --circle-perfectness 0.65 \
    --circle-probability-thresh 0.725 \
    --center-xlim 0 1920 \
    --center-ylim 0 1080 \
    --expected-nb-centers -1 \
    --edge-filter 3 \
    --gradient-kernel 3

Detailed explanations about the tutorial

If you decide to use a video as input, the relevant piece of code that permits to perform circle detection on the successive images of the video is the following:

  if (opt_input.find("%") != std::string::npos) {
    // The user wants to read a sequence of images from different files
    bool hasToContinue = true;
    vpVideoReader g;
    g.setFileName(opt_input);
    g.open(I_src);

    I_disp.resize(I_src.getHeight(), I_src.getWidth());
    I_dispCanny.resize(I_src.getHeight(), I_src.getWidth());
#if (VISP_CXX_STANDARD >= VISP_CXX_STANDARD_11)
    std::shared_ptr<vpDisplay> dColor = vpDisplayFactory::createDisplay(I_disp, -1, -1, "Input image");
    std::shared_ptr<vpDisplay> dCanny(nullptr);
    if (opt_displayCanny) {
      dCanny = vpDisplayFactory::createDisplay(I_dispCanny, I_src.getWidth() + 40, -1, "Edge-map");
    }
#else
    vpDisplay *dColor = vpDisplayFactory::allocateDisplay(I_disp, -1, -1, "Input image");
    vpDisplay *dCanny(nullptr);
    if (opt_displayCanny) {
      dCanny = vpDisplayFactory::allocateDisplay(I_dispCanny, I_src.getWidth() + 40, -1, "Edge-map");
    }
#endif
    while (!g.end() && hasToContinue) {
      g.acquire(I_src);
      hasToContinue = run_detection(I_src, I_disp, I_dispCanny, detector, opt_nbCirclesToDetect, false, opt_displayCanny);
      vpTime::wait(40);
    }
 
#if (VISP_CXX_STANDARD < VISP_CXX_STANDARD_11)
    delete dColor;
    if (dCanny != nullptr) {
      if (opt_displayCanny) {
        delete dCanny;
      }
    }
#endif
  }

If you decide to use a single image as input, the relevant piece of code that permits to perform circle detection on the image is the following:

    // Check if opt_input exists
    if (!vpIoTools::checkFilename(opt_input)) {
      throw(vpException(vpException::ioError, "Input file \"" + opt_input + "\" does not exist !"));
    }
    // Read the image and perform detection on it
    vpImageIo::read(I_src, opt_input);
 
    I_disp.resize(I_src.getHeight(), I_src.getWidth());
    I_dispCanny.resize(I_src.getHeight(), I_src.getWidth());
#if (VISP_CXX_STANDARD >= VISP_CXX_STANDARD_11)
    std::shared_ptr<vpDisplay> dColor = vpDisplayFactory::createDisplay(I_disp, -1, -1, "Input image");
    std::shared_ptr<vpDisplay> dCanny(nullptr);
    if (opt_displayCanny) {
      dCanny = vpDisplayFactory::createDisplay(I_dispCanny, I_src.getWidth() + 40, -1, "Edge-map");
    }
#else
    vpDisplay *dColor = vpDisplayFactory::allocateDisplay(I_disp, -1, -1, "Input image");
    vpDisplay *dCanny(nullptr);
    if (opt_displayCanny) {
      dCanny = vpDisplayFactory::allocateDisplay(I_dispCanny, I_src.getWidth() + 40, -1, "Edge-map");
    }
#endif
 
    run_detection(I_src, I_disp, I_dispCanny, detector, opt_nbCirclesToDetect, true, opt_displayCanny);
 
#if (VISP_CXX_STANDARD < VISP_CXX_STANDARD_11)
    delete dColor;
    if (dCanny != nullptr) {
      if (opt_displayCanny) {
        delete dCanny;
      }
    }
#endif

If you did not use a JSON file to configure the vpCircleHoughTransform detector, the following structure defines the parameters of the algorithm based on the command line arguments:

  vpCircleHoughTransform::vpCircleHoughTransformParams
    algoParams(opt_gaussianKernelSize
      , opt_gaussianSigma
      , opt_sobelKernelSize
      , opt_lowerCannyThresh
      , opt_upperCannyThresh
      , opt_nbEdgeFilteringIter
      , opt_centerXlimits
      , opt_centerYlimits
      , static_cast<float>(opt_minRadius)
      , static_cast<float>(opt_maxRadius)
      , opt_dilatationKerneSize
      , opt_averagingWindowSize
      , opt_centerThresh
      , opt_circleProbaThresh
      , opt_circlePerfectness
      , opt_centerDistanceThresh
      , opt_radiusDifferenceThresh
      , opt_filteringAndGradientType
      , opt_cannyBackendType
      , opt_lowerCannyThreshRatio
      , opt_upperCannyThreshRatio
      , opt_expectedNbCenters
      , opt_recordVotingPoints
      , opt_visibilityRatioThresh
    );

The initialization of the algorithm is performed in the following piece of code. If a JSON configuration file is given as input configuration, it will be preferred to the command line arguments:

  vpCircleHoughTransform detector;
  if (opt_jsonFilePath.empty()) {
    std::cout << "Initializing detector from the program arguments [...]" << std::endl;
    detector.init(algoParams);
  }
  else {
#ifdef VISP_HAVE_NLOHMANN_JSON
    std::cout << "Initializing detector from JSON file \"" << opt_jsonFilePath << "\", some of the program arguments will be ignored [...]" << std::endl;
    detector.initFromJSON(opt_jsonFilePath);
#else
    throw(vpException(vpException::functionNotImplementedError, "You must install nlohmann JSON library to use this feature, see https://visp-doc.inria.fr/doxygen/visp-daily/supported-third-parties.html#soft_tool_json for more information."));
#endif
  }

To run the circle detection, you must call the following method:

  std::vector<vpImageCircle> detectedCircles = detector.detect(I_src, nbCirclesToDetect);
  std::vector<float> probas = detector.getDetectionsProbabilities();

The call to vpCircleHoughTransform::getDetectionsProbabilities permits to know the confidence in each detection. It is sorted in the same way that are sorted the detections.

You could have also used the following method to get only the num_best best detections:

int num_best; // Set it to the number of circles you want to keep
std::vector<vpImageCircle> detections = detector.detect(I, num_best);

Then, you can iterate on the vector of detections using a synthax similar to the following:

  const unsigned int nbCircle = static_cast<unsigned int>(detectedCircles.size());
  for (unsigned int idCircle = 0; idCircle < nbCircle; ++idCircle) {
    const vpImageCircle &circleCandidate = detectedCircles[idCircle];
    vpImageDraw::drawCircle(I_disp, circleCandidate, v_colors[idColor], 2);
    std::cout << "Circle #" << id << ":" << std::endl;
    std::cout << "\tCenter: (" << circleCandidate.getCenter() << ")" << std::endl;
    std::cout << "\tRadius: (" << circleCandidate.getRadius() << ")" << std::endl;
    std::cout << "\tProba: " << probas[id] << std::endl;
    std::cout << "\tTheoretical arc length: " << circleCandidate.computeArcLengthInRoI(vpRect(0, 0, I_src.getWidth(), I_src.getHeight())) << std::endl;
    id++;
    idColor = (idColor + 1) % v_colors.size();
  }
#if (VISP_CXX_STANDARD >= VISP_CXX_STANDARD_17)
  std::optional<vpImage<bool>> opt_mask = std::nullopt;
  std::optional<std::vector<std::vector<std::pair<unsigned int, unsigned int> > > > opt_votingPoints = std::nullopt;
#else
  vpImage<bool> *opt_mask = nullptr;
  std::vector<std::vector<std::pair<unsigned int, unsigned int> > > *opt_votingPoints = nullptr;
  detector.computeVotingMask(I_src, detectedCircles, &opt_mask, &opt_votingPoints); // Get, if available, the voting points
#endif
 
#if (VISP_CXX_STANDARD >= VISP_CXX_STANDARD_17)
  if (opt_votingPoints)
#else
  if (opt_votingPoints != nullptr)
#endif
  {
    const unsigned int crossSize = 3;
    const unsigned int crossThickness = 1;
    unsigned int nbVotedCircles = static_cast<unsigned int>(opt_votingPoints->size());
    for (unsigned int idCircle = 0; idCircle < nbVotedCircles; ++idCircle) {
      // Get the voting points of a detected circle
      const std::vector<std::pair<unsigned int, unsigned int> > &votingPoints = (*opt_votingPoints)[idCircle];
      unsigned int nbVotingPoints = static_cast<unsigned int>(votingPoints.size());
      for (unsigned int idPoint = 0; idPoint < nbVotingPoints; ++idPoint) {
        // Draw the voting points
        const std::pair<unsigned int, unsigned int> &pt = votingPoints[idPoint];
        vpImageDraw::drawCross(I_disp, vpImagePoint(pt.first, pt.second), crossSize, vpColor::red, crossThickness);
      }
    }
  }
#if (VISP_CXX_STANDARD < VISP_CXX_STANDARD_17)
  if (opt_mask != nullptr) {
    delete opt_mask;
  }
  if (opt_votingPoints != nullptr) {
    delete opt_votingPoints;
  }
#endif