5.26. Détection de lignes et de segments

Certaines caractéristiques d’une scène ne sont pas des régions de couleur connexes mais des contours droits orientés : une ligne peinte au sol, la jointure entre deux surfaces, le côté d’un rectangle imprimé, le bord d’une embrasure de porte. Demander au détecteur de blobs de les trouver est une mauvaise approche : le contour fait un pixel de large, l’algorithme de blobs recherche une surface colorée, et la réponse revient vide ou bruitée.

Le bon détecteur pour les contours orientés est la transformée de Hough pour les lignes. Le module image l’expose sous deux formes : find_lines() renvoie des lignes infinies (chaque ligne s’étend sur toute l’image) ; find_line_segments() renvoie des segments finis (chaque ligne a des extrémités à l’intérieur de la trame). Le choix dépend de la question de savoir si les contours d’intérêt sont continus sur toute la trame ou n’en couvrent qu’une partie.

5.26.1. Fonctionnement de la transformée de Hough

Les deux détecteurs partagent la même idée fondamentale, qu’il vaut donc la peine de comprendre une bonne fois. Le module image applique d’abord un filtre de contour de type Sobel sur l’entrée afin d’attribuer à chaque pixel un score selon sa probabilité d’appartenir à un contour orienté. Chaque pixel de contour ainsi identifié vote ensuite pour toutes les lignes sur lesquelles il pourrait se trouver. Les lignes qui recueillent le plus de votes l’emportent.

Une ligne est paramétrée dans l”espace de Hough par deux nombres : theta, l’angle de la ligne (0 à 179 degrés), et rho, la distance perpendiculaire de l’origine de l’image à la ligne (signée, en pixels). Chaque ligne contenue dans l’image est un point dans l’espace (theta, rho). Chaque pixel de contour de l’entrée apporte un vote à chaque combinaison (theta, rho) cohérente avec sa position : conceptuellement, une courbe à travers l’espace de Hough. Là où de nombreuses courbes de ce type se croisent, de nombreux pixels de contour s’accordent sur la même ligne, et ce croisement constitue une détection.

Le détecteur renvoie les maxima locaux de l’espace de Hough dont le total des votes dépasse un seuil. Chaque Line renvoyée porte les deux représentations : x1, y1, x2, y2 pour la forme par extrémités (rognée aux limites de l’image dans le cas infini), theta, rho pour la forme de Hough, ainsi que length et magnitude pour la taille et le nombre de votes respectivement.

5.26.2. Lignes infinies

find_lines() exécute la transformée de Hough et renvoie les lignes les plus fortes, chacune étendue sur toute l’image :

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

threshold est le total minimal de votes pour qu’une ligne soit acceptée. Le total des votes additionne les amplitudes de contour de Sobel de chaque pixel contributeur ; ainsi, des valeurs de threshold plus grandes exigent des contours plus longs ou plus marqués pour être validés, ce qui fait que la bonne valeur dépend de la résolution de l’image (une ligne plus longue à une résolution plus élevée accumule plus de votes) tout autant que de la scène, et doit donc être réglée pour l’application précise. Comme points de départ approximatifs à affiner : 1000 pour une ligne modeste dans une image nette, 500 ou moins pour un faible contraste ou des lignes courtes, 2000 ou plus pour des scènes chargées où des lignes faussement positives se forment à partir de groupes de bruit de contour.

theta_margin et rho_margin contrôlent la fusion des maxima voisins. Un seul contour physique produit un petit groupe de cases à fort vote autour de ses véritables (theta, rho), et le détecteur réduit chaque groupe à son pic avant de renvoyer. theta_margin=25 (degrés) fusionne tous les pics situés à moins de 25 degrés d’orientation ; rho_margin=25 (pixels) fusionne les pics situés à moins de 25 pixels de distance. Les valeurs par défaut sont raisonnables ; les augmenter renvoie moins de lignes, plus distinctes, et les diminuer renvoie plus de lignes, parfois en double.

x_stride et y_stride parcourent les pixels de contour pendant le vote, de la même manière qu’ils parcourent les pixels dans find_blobs(). Les valeurs par défaut de 2 et 1 conviennent au cas courant ; les augmenter accélère la recherche au prix de la résolution. roi restreint la recherche à une région de la trame, ce qui à la fois réduit les lignes renvoyées et diminue le travail.

Chaque ligne renvoyée est directement traçable : l’objet Line se transmet tel quel à draw_line(), qui lit les champs d’extrémités (x1, y1, x2, y2) au début de celui-ci. l.theta est l’angle en degrés, qui classe la ligne comme horizontale, verticale ou diagonale en une seule comparaison. l.magnitude est le total des votes, qui trie les lignes renvoyées de la plus forte à la plus faible.

5.26.3. Segments de ligne

find_lines() est le bon détecteur pour les contours qui couvrent toute la trame, mais de nombreux contours réels (le côté gauche d’un code-barres imprimé, le bord supérieur d’une étiquette, le côté visible d’une règle) ne parcourent qu’une partie de l’image. find_line_segments() renvoie des segments finis dont les extrémités se trouvent à l’intérieur de la trame :

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

Le détecteur de segments suit directement les pixels de contour orientés, plutôt que de voter dans l’espace de Hough, et le résultat est un ensemble de courts tronçons droits. merge_distance définit l’écart maximal en pixels que deux courts tronçons colinéaires peuvent couvrir tout en fusionnant en un seul segment renvoyé ; max_theta_difference définit le nombre de degrés d’orientation que le fusionneur tolère entre des tronçons adjacents. Une fusion généreuse (merge_distance=10, max_theta_difference=15) renvoie un petit nombre de longs segments, au prix de relier parfois des contours réellement distincts ; une fusion stricte (merge_distance=0, max_theta_difference=5) renvoie de nombreux courts segments et laisse l’application les trier en Python.

Les objets de résultat sont du même type Line que celui renvoyé par find_lines(), avec les mêmes propriétés, de sorte qu’un pipeline peut traiter l’un ou l’autre type de détection par le même code en aval. La seule différence pratique est que les extrémités des segments sont les véritables extrémités de la ligne dans l’image, alors que les extrémités des lignes infinies se situent là où la ligne franchit le bord de l’image.

5.26.4. Quand utiliser chacun

Le choix entre les deux méthodes se résume à une seule question : l’application se soucie-t-elle de l’endroit où la ligne s’arrête ?

find_lines() est le bon outil lorsque la réponse est non. Un robot suiveur de ligne doit savoir dans quelle direction va la ligne et où elle franchit le bas de la trame ; la ligne elle-même court jusqu’à l’horizon et au-delà. Un détecteur d’horizon cherche le contour orienté le plus fort de l’image ; il n’a pas besoin de savoir où l’horizon se termine.

find_line_segments() est le bon outil lorsque la réponse est oui. Identifier les quatre côtés d’un rectangle imprimé nécessite quatre segments aux extrémités connues. Suivre un doigt pointé vers un écran revient à suivre un court segment dont les extrémités sont la pointe et la base du doigt. Mesurer la longueur d’une rayure visible nécessite l’étendue réelle du segment en pixels.

Les deux détecteurs partagent une limitation commune : ils ont besoin de contraste. Le filtre de contour de Sobel sur lequel ils s’appuient réagit aux gradients de luminosité ; un contour coloré sur un arrière-plan d’égale luminosité (une ligne rouge sur un mur vert de même luminance) ne produit aucun gradient et aucune détection. Lorsque ce cas se présente en pratique, la solution consiste à extraire un seul canal LAB sous forme d’image en niveaux de gris au bon contraste avant la recherche : to_grayscale() avec le canal b sélectionné isole le rouge du vert là où le seul canal de luminance est plat, puis à transmettre cette image de canal au détecteur de lignes.