# Threshold-free Hough transform

## 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;
}

où la fonction `plot_lines`

est définie comme indiqué dans ce tutorial.

On obtient :

Pour afficher le plan de Hough, il suffit d'utiliser la fonction
`HoughWithGradientDir`

à la place :

```
#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: