Transformée de Hough sans seuillage

La transformée de Hough

La transformée de Hough est une méthode très utilisée pour la détection de formes géométriques dans une image. On va décrire ici en particulier la détection des lignes, telle qu'elle est implémentée dans OpenCV, ainsi que la variante utilisant le gradient de l'image et sans seuillage.

Représentation des lignes

Une ligne dans le plan peut être représentée de différentes manières, comme par exemple par l'équation y = ax + b. Cependant, cette représentation n'est pas très pratique, car le coefficient a a une dynamique très importante : il peut tout aussi bien être nul pour une ligne horizontale, qu'infini pour une ligne verticale. C'est pourquoi on utilise plutôt la représentation polaire (rho, theta), comme illustré dans la figure ci-dessous :

Rho est donc la distance (c'est-à-dire la distance minimale) entre la droite et l'origine, et theta indique l'orientation de la droite (0 pour une ligne horizontale, 90 degrés pour une ligne verticale). Les valeurs de rho et theta ont des dynamiques bien maitrisées : entre 0 et la diagonale de l'image pour rho (le point le plus éloigné de l'origine), et entre 0 et 2 pi pour theta.

Espace paramétrique

La transformée de Hough consiste à mettre en correspondance les lignes représentées dans le plan cartésien (x,y) avec leur représentation dans l'espace paramétrique (rho,theta). Ce n'est pas si facile, car à un même point (x,y) dans le plan cartésien, peut correspondre une infinité de droites (toutes les droites qui passent par ce point), c'est-à-dire une infinité de points dans l'espace paramètrique (rho,theta).

Pour résoudre ce problème, on commence par discrétiser l'espace des paramètres : on va considérer uniquement un nombre fini de valeurs possibles pour rho et theta, et on va échantillonner de manière régulière : rho_k = k drho, theta_k = k dtheta. Cela nous permet de créer une matrice indexée suivant rho et theta, qui va nous servir pour représenter les droites présentes dans une image.

Algorithmes pour passer dans l'espace paramétrique

Ensuite, différentes méthodes existent. L'algorithme natif dans OpenCV (fonction HoughLine) effectue tout d'abord une extraction de contour (algorithme de Canny), puis pour chaque pixel de contour, considère toutes les droites possibles qui passent par ce pixel : pour chacune des ces droites, le compteur associé dans la matrice de l'espace paramétrique est incrémenté. Ainsi, on obtient à la fin une matrice dont les éléments les plus importants correspondent aux paramètres des droites les plus probables.

Cependant, cette méthode n'est pas forcément idéale, car pour chaque pixel, on prends en compte toutes les droites qui passent par ce point : la plupart de celles-ci ne correspondent à aucune droite présente réellement dans l'image. Par ailleurs, cette méthode nécessite le réglage de plusieurs seuils, à la fois pour la détection de contour (détecteur de Canny) et la détection des lignes, ce qui peut être délicat si on a besoin d'un algorithme robuste par rapport aux conditions d'éclairage ou de bruit.

Pour résoudre ces problèmes, l'algorithme alternatif qui vous est proposé ici diffère sur les points suivants :

On peut remarquer que localement le gradient est perpendiculaire aux contours de l'image (il suffit donc d'ajouter 90 degrés pour avoir la direction exacte de chaque ligne). On peut donc utiliser la direction du gradient pour déterminer une unique ligne (point dans l'espace paramétrique) à associer à chaque pixel de contour.
Au lieu d'extraire les pixels de contour (algorithme de Canny), on utilise tout les pixels de l'image d'origine, mais le vote correspondant dans l'espace paramétrique est pondéré par la valeur absolue du gradient (car le gradient est plus important sur les contours). Cela permet d'éviter un seuillage.
Afin de déterminer les lignes les plus probables, au lieu de seuiller les valeurs dans l'espace paramétrique (ce qui introduit la difficulté de trouver le bon seuil), on extrait les maxima locaux (après filtrage passe-bas pour diminuer le bruit).

API C++

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

Les paramètres sont presque identiques à ceux de la fonction native HouhgLines de OpenCV :

img est l'image d'entrée (attention : dans la fonction native HouhgLines, c'est le masque de contour qui est passé),
lines est un vecteur qui contiendra les lignes détectées,
rho est la résolution en pixels de l'espace de Hough (par défaut 1 pixel),
theta est la résolution angulaire en radians de l'espace de Hough (par défaut 1 degré).
gamma est le coefficient pour le pré-filtrage exponentiel (filtre de Deriche) de l'image avant calcul de gradient

Par ailleurs, pour d'autres applications que la recherche de lignes (par exemple, recherche de rectangles, losanges, etc.), vous avez aussi la possibilité de récupérer directement la matrice d'accumulation dans l'espace paramétrique, avec la fonction suivante :

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

Les paramètres sont identiques à la fonction précédente.

Exemple

Supposons que l'on cherche à localiser la carte sur l'image suivante :


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

Comparaison avec / sans seuillage

Afin d'illustrer l'intérêt d'avoir à disposition un algorithme sans seuillage, nous allons voir avec les exemples ci-dessous que l'algorithme natif de OpenCV n'est pas robuste dans l'absolu, et que les seuils doivent être réglés au cas par cas en fonction du type d'image. On considére pour commencer l'image de test utilisée dans l'exemple OpenCV (bâtiments), pour laquelle les seuils de détections Canny et Hough ont été réglé à 150 et 100 pour un bon compromis faux positifs / faux négatifs :

Maintenant, si on essaye d'appliquer l'algorithme avec les mêmes réglages sur l'image suivante, aucune ligne n'est détectée :

Pour détecter correctement sur cet image, il faut baisser les seuils de détection. En descendant à 120 (seuil pour Canny) et 50 (seuil pour Hough), le décodage réussi :

Mais alors en applicant les mêmes paramètres sur la première image, on obtient un nombre considérable de faux positifs (l'image n'est même plus visible) :

Au contraire, avec l'algorithme sans seuillage (fondé sur le gradient), la détection est satisfaisante pour les deux images :