5.26. Lijnen en segmenten vinden

Sommige scènekenmerken zijn geen samenhangende kleurgebieden maar georiënteerde rechte randen: een geschilderde lijn op de vloer, de naad tussen twee oppervlakken, de zijkant van een gedrukte rechthoek, de rand van een deuropening. De blob-detector vragen om ze te vinden is de verkeerde vraag – de rand is één pixel breed, het blob-algoritme wil oppervlak-met-kleur, en het antwoord komt leeg of ruisrijk terug.

De juiste detector voor georiënteerde randen is de Hough-lijntransformatie. De image-module biedt deze in twee varianten: find_lines() geeft oneindige lijnen terug (elke lijn strekt zich over de hele afbeelding uit); find_line_segments() geeft eindige segmenten terug (elke lijn heeft eindpunten binnen het frame). Welke de applicatie nodig heeft hangt af van de vraag of de randen van belang continu over het hele frame lopen of slechts een deel ervan beslaan.

5.26.1. Hoe de Hough-transformatie werkt

Beide detectors delen hetzelfde kernidee, dus het loont de moeite het één keer te begrijpen. De image-module voert eerst een Sobel-achtig randfilter uit op de invoer om elke pixel te scoren op hoe waarschijnlijk het is dat hij op een georiënteerde rand ligt. Elke dergelijke randpixel stemt vervolgens op alle lijnen waarop hij zou kunnen liggen. De lijnen die de meeste stemmen verzamelen winnen.

Een lijn wordt in de Hough-ruimte geparametriseerd door twee getallen: theta, de hoek van de lijn (0 – 179 graden), en rho, de loodrechte afstand van de oorsprong van de afbeelding tot de lijn (met teken, in pixels). Elke lijn die de afbeelding bevat is één punt in de (theta, rho)-ruimte. Elke randpixel in de invoer draagt één stem bij aan elke (theta, rho)-combinatie die consistent is met zijn positie – conceptueel een kromme door de Hough-ruimte. Waar veel van dergelijke krommen elkaar kruisen, zijn veel randpixels het eens over dezelfde lijn, en die kruising is een detectie.

De detector geeft de lokale maxima in de Hough-ruimte terug waarvan de stemtotalen een drempelwaarde overschrijden. Elke teruggegeven Line draagt beide representaties: x1, y1, x2, y2 voor de eindpuntvorm (afgekapt op de afbeeldingsgrenzen voor het oneindige geval), theta, rho voor de Hough-vorm, en length en magnitude voor respectievelijk grootte en aantal stemmen.

5.26.2. Oneindige lijnen

find_lines() voert de Hough-transformatie uit en geeft de sterkste lijnen terug, elk uitgestrekt over de hele afbeelding:

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

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

De threshold is het minimale stemtotaal voordat een lijn wordt geaccepteerd. Het stemtotaal telt de Sobel-randgroottes van elke bijdragende pixel op, dus grotere threshold-waarden vereisen langere of sterkere randen om door te komen – wat de juiste waarde afhankelijk maakt van de afbeeldingsresolutie (een langere lijn bij een hogere resolutie verzamelt meer stemmen) en van de scène, zodat hij moet worden afgestemd op de specifieke applicatie. Als ruwe startpunten om vanaf af te stemmen: 1000 voor een bescheiden lijn in een heldere afbeelding, 500 of lager voor zwak contrast of korte lijnen, 2000 of meer voor drukke scènes waar valse-positieve lijnen ontstaan door clusters van randruis.

theta_margin en rho_margin bepalen het samenvoegen van nabijgelegen maxima. Eén fysieke rand produceert een klein cluster van bins met veel stemmen rond zijn werkelijke (theta, rho), en de detector reduceert elk cluster tot zijn piek voordat hij teruggeeft. theta_margin=25 (graden) voegt alle pieken samen binnen 25 graden oriëntatie; rho_margin=25 (pixels) voegt pieken samen binnen 25 pixels afstand. De standaardwaarden zijn redelijk; ze verhogen geeft minder, duidelijker onderscheiden lijnen terug en ze verlagen geeft meer, soms gedupliceerde lijnen terug.

x_stride en y_stride stappen tijdens het stemmen door de randpixels, op dezelfde manier waarop ze door de pixels stappen in find_blobs(). De standaardwaarden van 2 en 1 werken voor het gangbare geval; ze verhogen versnelt de zoekopdracht ten koste van resolutie. roi beperkt de zoekopdracht tot een gebied van het frame, wat zowel de teruggegeven lijnen versmalt als het werk vermindert.

Elke teruggegeven lijn is rechtstreeks tekenbaar: het Line-object gaat direct in draw_line(), dat de eindpuntvelden (x1, y1, x2, y2) aan de voorkant ervan uitleest. l.theta is de hoek in graden, die de lijn in één vergelijking classificeert als horizontaal, verticaal of diagonaal. l.magnitude is het stemtotaal, dat de teruggegeven lijnen van sterkste naar zwakste sorteert.

5.26.3. Lijnsegmenten

find_lines() is de juiste detector voor randen die het hele frame beslaan, maar veel echte randen – de linkerkant van een gedrukte barcode, de bovenrand van een label, de zichtbare kant van een liniaal – lopen slechts over een deel van de afbeelding. find_line_segments() geeft eindige segmenten terug waarvan de eindpunten binnen het frame liggen:

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

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

De segmentdetector volgt rechtstreeks de georiënteerde randpixels, in plaats van te stemmen in de Hough-ruimte, en het resultaat is een verzameling korte rechte stukken. merge_distance stelt de maximale pixelafstand in die twee collineaire korte stukken kunnen overbruggen en toch samengevoegd worden tot één teruggegeven segment; max_theta_difference stelt in hoeveel graden oriëntatie de samenvoeger tolereert tussen aangrenzende stukken. Een ruime samenvoeging (merge_distance=10, max_theta_difference=15) geeft een klein aantal lange segmenten terug ten koste van het soms overbruggen van werkelijk gescheiden randen; een strikte samenvoeging (merge_distance=0, max_theta_difference=5) geeft veel korte segmenten terug en laat de applicatie ze in Python uitsorteren.

De resultaatobjecten zijn van hetzelfde Line-type als find_lines() teruggeeft, met dezelfde eigenschappen, zodat een pijplijn beide soorten detecties via hetzelfde stroomafwaartse codepad kan verwerken. Het enige praktische verschil is dat de eindpunten van de segmenten de werkelijke uiteinden van de lijn in de afbeelding zijn, terwijl de eindpunten van de oneindige lijnen liggen waar de lijn de afbeeldingsrand kruist.

5.26.4. Wanneer welke te gebruiken

De keuze tussen de twee methoden komt neer op één enkele vraag: kan het de applicatie schelen waar de lijn stopt?

find_lines() is het juiste gereedschap wanneer het antwoord nee is. Een lijnvolgende robot moet weten welke kant de lijn op gaat en waar hij de onderkant van het frame kruist; de lijn zelf loopt tot aan de horizon en daarbuiten. Een horizondetector wil de sterkste georiënteerde rand in de afbeelding; hij hoeft niet te weten waar de horizon eindigt.

find_line_segments() is het juiste gereedschap wanneer het antwoord ja is. Het identificeren van de vier zijden van een gedrukte rechthoek vereist vier segmenten met bekende eindpunten. Het volgen van een vinger die naar een display wijst betekent het volgen van een kort segment waarvan de eindpunten de top en de basis van de vinger zijn. Het meten van de lengte van een zichtbare kras vereist de werkelijke omvang van het segment in pixels.

Beide detectors delen een gemeenschappelijke beperking: ze hebben contrast nodig. Het Sobel-randfilter waarop ze voortbouwen reageert op helderheidsgradiënten; een gekleurde rand tegen een even heldere achtergrond (een rode lijn op een groene muur met dezelfde luminantie) produceert geen gradiënt en geen detectie. Wanneer dat geval zich in de praktijk voordoet, is de oplossing om vóór het zoeken één LAB-kanaal te extraheren als een grijswaardenafbeelding met het juiste contrast – to_grayscale() met het b-kanaal geselecteerd isoleert rood tegen groen waar het luminantiekanaal alleen vlak is – en die kanaalafbeelding aan de lijndetector door te geven.