Threshold-free Hough transform

• Softwares
• / OpenCV
• / Image processing functions
• / Hough

The Hough transform

The Hough transform is a very popular method to detect geometric shapes in an image. We will describe here the line detection algorithm, as implemented in OpenCV, and the gradient-based, threshold-free variant.

Lines representation

A line in the plane can be represented in different ways, like for instance by the equation y = ax + b. However, this representation is not very practical, because the dynamic of the a coefficient can be very large: it can be zero for an horizontal line, but also infinite for a vertical one. That's why we rather use the polar representation (rho, theta), as illustrated in the figure below:

Rho is thus the distance (e.g. the minimum distance) between the line and the point (0,0), and theta is the orientation of the line (0 for an horizontal line, and 90 degrees for a vertical one). The values of rho and theta have well restricted dynamics: between 0 and the diagonal of the image for rho (the farthest distance from the origin), and from 0 to 2 pi for theta.

Parametric space

The Hough transform consists in matching the lines in the cartesian plane (x,y) with their representation in the parametric espace (rho,theta). It is not so easy, because to a given point (x,y) in the plane, can match an infinite number of lines (all lines going through this point), that is an infinite number of points in the parametric space (rho,theta).

To solve this problem, we start by discretize the parameter space: we will only consider a finite number of possible values for rho and theta, and we will sample them with a regular grid: rho_k = k drho, theta_k = k dtheta. This enables us to create a matric indexed with rho and theta, and which will serve to represente the lines in an image.

Algorithms to compute the parametric matrix

Then, different methods exist. The native algorithm in OpenCV (function HoughLine) makes first a countour extraction (Canny algorithm), then for each countour pixel, and for every possible line going through this pixel, increment the corresponding counter in the parametric space matrix. Thus, we obtain at the end a matrix which most important elements indicate the most probable lines in the image.

Yet, this method is not ideal, since for each pixel, a lot of artificial (not really present in the image) lines are taken into account. Moreover, it needs the tuning of several threshold, both for the contour detection (Canny detector) and for the line detection, which can be delicate if one needs a algorithm robust against changing noise or lighting conditions.

To solve these difficulities, the algorithm implemented here is different in the following ways:

• We can remark that locally the gradient is orthogonal to the image contours (it suffices thus to add 90 degrees to get the exact direction of each line). We can thus use the gradient direction to localize an unique line (point in the parametric space) to correspond to each contour pixel.
• Instead of using only contour pixels (Canny algorithm), we use every pixels of the image, but with a ponderation proportionnal to the gradient absolute value (because the gradient magnitude is higher on the contours). This avoids a thresholding operation.
• So as to localize the most probable lines, instead of thresholding the values in the parametric space (which introduce the diffulty of finding an appropriate threshold), we extract the local maxima (after band-pass filtering to limit noise).

C++ API

void HoughLinesWithGradientDir(const cv::Mat &img,
                               std::vector(cv::Vec2f) &lines,
                               float rho = 1.0,
                               float theta = 3.1415926 / 180,
                               float gamma = 0.6)

The parameters are almost identical to those of the native OpenCV function HouhgLines:

• img is the input image (attention: in the native HouhgLines function, it is the contour mask),
• lines is a vector where will be stored the detected lines,
• rho is the resolution in pixels of the Hough space (1 pixel by default),
• theta is the angular resolution in radians of the Hough space (1 degree by default).
• gamma is the exponential (Deriche) filter coefficient (Deriche filter), which is used to prefilter the image before gradient computing.

Also, for other applications besides lines detection (for instance, localization of rectangles, diamonds, etc.), you can also get directly the Hough accumulation matrix (parameter space), with the following function:

void HoughWithGradientDir(const cv::Mat &img,
                          cv::Mat &res,
                          float rho   = 1.0,
                          float theta = 2 * 3.1415926 / 360,
                          float gamma = 0.6);

Parameters are identical to the previous function.

Example

Let's suppose that we have to locate the playing card in the following image:

#include "hough.hpp"
#include "opencv2/highgui/highgui.hpp" // for imread

using namespace cv;

int main(void)
{
  // Read image
  auto img = imread("data/card.jpg");
  
  // Each line will be a (rho, theta) tuple
  std::vector lines; 
  
  // Line detection
  HoughLinesWithGradientDir(img, lines);
  
  // Plot the detected lines
  auto img2 = img.clone();
  plot_lines(img2, lines, cv::Scalar(0,255,0));
  cv::imwrite("./build/card-lines.jpg", img2);
  
  return 0;
}

where the function plot_lines is defined as indicated in this tutorial.

We get:

To display the Hough space, we can use the function HoughWithGradientDir instead:

#include "hough.hpp"
#include "opencv2/highgui/highgui.hpp" // for imread
#include "opencv2/contrib/contrib.hpp" // for colormap

using namespace cv;

int main(void)
{
  auto img = imread("data/card.jpg");

  // Hough transform
  Mat hough;
  HoughWithGradientDir(img, hough);
  
  // 8 bits conversion and colormap
  hough.convertTo(hough, CV_8U);
  applyColorMap(hough, hough, cv::COLORMAP_JET);
  
  // Save image
  imwrite("./build/card-hough.jpg", hough);
  
  return 0;
}

With / without threshold comparison

So as to illustrate why it can be interesting to have a threshold-free algorithm, we will see in the examples below some limitations of the native OpenCV algorithm, for which some thresholds have to be tuned differently for each image. We start with the default test image in OpenCV Hough tutorial (buildings), with Canny and Hough threshold set respectively to 150 and 100 for a good false positives / false negatives balance:

Now, if we try to apply the algorithm with the same thresholds on the following image, no line is detected:

To correct this, we have to lower the detection threshold to 120 (Canny) and 50 (Hough):

But if we use these last thresholds for the first image, we have really too much false positive (the image is not visible anymore behind the false positives):

In contrary, with the threshold-free algorithm (based on the gradient), the detection is correct with both images: