5.26. Linien und Segmente finden

Manche Szenenmerkmale sind keine zusammenhängenden Farbregionen, sondern orientierte gerade Kanten: eine auf den Boden gemalte Linie, die Naht zwischen zwei Oberflächen, die Seite eines gedruckten Rechtecks, die Kante einer Tür. Den Blob-Detektor zu bitten, sie zu finden, ist die falsche Fragestellung – die Kante ist ein Pixel breit, der Blob-Algorithmus möchte Fläche mit Farbe, und die Antwort kommt leer oder verrauscht zurück.

Der richtige Detektor für orientierte Kanten ist die Hough-Linientransformation. Das image-Modul stellt sie in zwei Varianten bereit: find_lines() gibt unendliche Linien zurück (jede Linie erstreckt sich über das gesamte Bild); find_line_segments() gibt endliche Segmente zurück (jede Linie hat Endpunkte innerhalb des Einzelbilds). Welche die Anwendung benötigt, hängt davon ab, ob die interessierenden Kanten durchgehend über das ganze Einzelbild verlaufen oder nur einen Teil davon überspannen.

5.26.1. Wie die Hough-Transformation funktioniert

Beide Detektoren teilen sich dieselbe Kernidee, daher lohnt es sich, sie einmal zu verstehen. Das image-Modul führt zunächst einen Sobel-artigen Kantenfilter auf der Eingabe aus, um jedes Pixel danach zu bewerten, wie wahrscheinlich es auf einer orientierten Kante liegt. Jedes solche Kantenpixel stimmt dann für alle Linien ab, auf denen es liegen könnte. Die Linien, die die meisten Stimmen sammeln, gewinnen.

Eine Linie wird im Hough-Raum durch zwei Zahlen parametrisiert: theta, den Winkel der Linie (0 – 179 Grad), und rho, den senkrechten Abstand vom Bildursprung zur Linie (vorzeichenbehaftet, in Pixeln). Jede Linie, die das Bild enthält, ist ein Punkt im (theta, rho)-Raum. Jedes Kantenpixel in der Eingabe trägt eine Stimme zu jeder (theta, rho)-Kombination bei, die mit seiner Position vereinbar ist – konzeptionell eine Kurve durch den Hough-Raum. Wo sich viele solcher Kurven kreuzen, stimmen viele Kantenpixel über dieselbe Linie überein, und diese Kreuzung ist eine Erkennung.

Der Detektor gibt die lokalen Maxima im Hough-Raum zurück, deren Stimmensummen einen Schwellenwert überschreiten. Jede zurückgegebene Line trägt beide Darstellungen: x1, y1, x2, y2 für die Endpunktform (im unendlichen Fall an die Bildgrenzen abgeschnitten), theta, rho für die Hough-Form sowie length und magnitude für Größe beziehungsweise Stimmenzahl.

5.26.2. Unendliche Linien

find_lines() führt die Hough-Transformation aus und gibt die stärksten Linien zurück, jeweils über das gesamte Bild erstreckt:

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

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

Der threshold ist die minimale Stimmensumme, damit eine Linie akzeptiert wird. Die Stimmensumme addiert die Sobel-Kantenstärken aller beitragenden Pixel, sodass größere threshold-Werte längere oder stärkere Kanten verlangen, um durchzukommen – was den richtigen Wert sowohl von der Bildauflösung abhängig macht (eine längere Linie bei höherer Auflösung sammelt mehr Stimmen) als auch von der Szene, sodass er für die jeweilige Anwendung abgestimmt werden muss. Als grobe Ausgangspunkte zum Abstimmen: 1000 für eine mäßige Linie in einem klaren Bild, 500 oder darunter für schwachen Kontrast oder kurze Linien, 2000 oder mehr für unruhige Szenen, in denen sich Fehlerkennungen durch Bündel von Kantenrauschen bilden.

theta_margin und rho_margin steuern das Zusammenführen benachbarter Maxima. Eine einzelne physische Kante erzeugt ein kleines Bündel von Bins mit hoher Stimmenzahl rund um ihr wahres (theta, rho), und der Detektor reduziert jedes Bündel auf seinen Höhepunkt, bevor er zurückgibt. theta_margin=25 (Grad) führt alle Spitzen innerhalb von 25 Grad Orientierung zusammen; rho_margin=25 (Pixel) führt Spitzen innerhalb von 25 Pixeln Abstand zusammen. Die Standardwerte sind vernünftig; sie zu erhöhen liefert weniger, dafür ausgeprägtere Linien, und sie zu senken liefert mehr, mitunter duplizierte Linien.

x_stride und y_stride schreiten beim Abstimmen durch die Kantenpixel, genauso wie sie in find_blobs() durch die Pixel schreiten. Die Standardwerte 2 und 1 funktionieren für den üblichen Fall; sie zu erhöhen beschleunigt die Suche auf Kosten der Auflösung. roi schränkt die Suche auf eine Region des Einzelbilds ein, was sowohl die zurückgegebenen Linien eingrenzt als auch den Aufwand reduziert.

Jede zurückgegebene Linie ist direkt zeichenbar: Das Line-Objekt wird direkt an draw_line() übergeben, die die (x1, y1, x2, y2)-Endpunktfelder von dessen Anfang ausliest. l.theta ist der Winkel in Grad, der die Linie in einem einzigen Vergleich als horizontal, vertikal oder diagonal einstuft. l.magnitude ist die Stimmensumme, die die zurückgegebenen Linien von der stärksten zur schwächsten sortiert.

5.26.3. Liniensegmente

find_lines() ist der richtige Detektor für Kanten, die das gesamte Einzelbild überspannen, doch viele reale Kanten – die linke Seite eines gedruckten Barcodes, die obere Kante eines Labels, die sichtbare Seite eines Lineals – verlaufen nur über einen Teil des Bildes. find_line_segments() gibt endliche Segmente zurück, deren Endpunkte innerhalb des Einzelbilds liegen:

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

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

Der Segmentdetektor folgt direkt orientierten Kantenpixeln, anstatt im Hough-Raum abzustimmen, und das Ergebnis ist eine Sammlung kurzer gerader Strecken. merge_distance legt die maximale Pixellücke fest, die zwei kollineare kurze Strecken überspannen können und dennoch zu einem zurückgegebenen Segment zusammengeführt werden; max_theta_difference legt fest, wie viele Grad Orientierungsunterschied der Zusammenführer zwischen benachbarten Strecken toleriert. Ein großzügiges Zusammenführen (merge_distance=10, max_theta_difference=15) liefert eine kleine Anzahl langer Segmente um den Preis, manchmal tatsächlich getrennte Kanten zu überbrücken; ein striktes Zusammenführen (merge_distance=0, max_theta_difference=5) liefert viele kurze Segmente und überlässt es der Anwendung, sie in Python zu sortieren.

Die Ergebnisobjekte sind vom selben Typ Line, den find_lines() zurückgibt, mit denselben Eigenschaften, sodass eine Pipeline beide Arten von Erkennung über denselben nachgelagerten Codepfad verarbeiten kann. Der einzige praktische Unterschied besteht darin, dass die Endpunkte der Segmente die tatsächlichen Enden der Linie im Bild sind, während die Endpunkte der unendlichen Linien dort liegen, wo die Linie den Bildrand kreuzt.

5.26.4. Wann man welche verwendet

Die Wahl zwischen den beiden Methoden läuft auf eine einzige Frage hinaus: Kümmert es die Anwendung, wo die Linie aufhört?

find_lines() ist das richtige Werkzeug, wenn die Antwort nein lautet. Ein linienfolgender Roboter muss wissen, in welche Richtung die Linie verläuft und wo sie den unteren Rand des Einzelbilds kreuzt; die Linie selbst läuft bis zum Horizont und darüber hinaus. Ein Horizontdetektor möchte die stärkste orientierte Kante im Bild; er muss nicht wissen, wo der Horizont endet.

find_line_segments() ist das richtige Werkzeug, wenn die Antwort ja lautet. Die vier Seiten eines gedruckten Rechtecks zu identifizieren erfordert vier Segmente mit bekannten Endpunkten. Einen auf ein Display zeigenden Finger zu verfolgen bedeutet, einem kurzen Segment zu folgen, dessen Endpunkte die Fingerspitze und die Fingerbasis sind. Die Länge eines sichtbaren Kratzers zu messen erfordert die tatsächliche Ausdehnung des Segments in Pixeln.

Beide Detektoren teilen eine gemeinsame Einschränkung: Sie benötigen Kontrast. Der Sobel-Kantenfilter, auf dem sie aufbauen, reagiert auf Helligkeitsgradienten; eine farbige Kante vor einem gleich hellen Hintergrund (eine rote Linie auf einer grünen Wand gleicher Leuchtdichte) erzeugt keinen Gradienten und keine Erkennung. Wenn dieser Fall in der Praxis auftritt, besteht die Lösung darin, vor der Suche einen einzelnen LAB-Kanal als Graustufenbild mit dem richtigen Kontrast zu extrahieren – to_grayscale() mit ausgewähltem b-Kanal isoliert Rot gegen Grün dort, wo der Leuchtdichtekanal allein flach ist – und dieses Kanalbild an den Linien-Detektor zu übergeben.