5.26. Hledání čar a úseček

Některé příznaky scény nejsou souvislé barevné oblasti, ale orientované přímé hrany: namalovaná čára na podlaze, švy mezi dvěma povrchy, strana vytištěného obdélníku, hrana dveřního otvoru. Žádat detektor blobů, aby je našel, je špatná otázka – hrana je široká jeden pixel, algoritmus blobů chce plochu s barvou a odpověď se vrací prázdná nebo zašuměná.

Správným detektorem pro orientované hrany je Houghova transformace čar. Modul image ji nabízí ve dvou variantách: find_lines() vrací nekonečné čáry (každá čára se táhne přes celý obraz); find_line_segments() vrací konečné úsečky (každá čára má koncové body uvnitř snímku). Kterou z nich aplikace potřebuje, závisí na tom, zda jsou hrany, o které jde, souvislé přes celý snímek, nebo zabírají jen jeho část.

5.26.1. Jak Houghova transformace funguje

Oba detektory sdílejí stejnou základní myšlenku, takže se vyplatí jí jednou porozumět. Modul image nejprve spustí na vstupu hranový filtr Sobelova typu, aby ohodnotil každý pixel podle toho, jak pravděpodobně leží na orientované hraně. Každý takový hranový pixel pak hlasuje pro všechny čáry, na nichž by mohl ležet. Vyhrávají čáry, které nasbírají nejvíce hlasů.

Čára je v Houghově prostoru parametrizována dvěma čísly: theta, úhlem čáry (0 – 179 stupňů), a rho, kolmou vzdáleností od počátku obrazu k čáře (se znaménkem, v pixelech). Každá čára, kterou obraz obsahuje, je jeden bod v prostoru (theta, rho). Každý hranový pixel na vstupu přispívá jedním hlasem ke každé kombinaci (theta, rho) konzistentní s jeho polohou – pojmově křivka procházející Houghovým prostorem. Tam, kde se mnoho takových křivek protíná, se mnoho hranových pixelů shoduje na téže čáře, a tento průsečík je detekcí.

Detektor vrací lokální maxima v Houghově prostoru, jejichž celkové počty hlasů překračují práh. Každá vrácená Line nese obě reprezentace: x1, y1, x2, y2 pro tvar s koncovými body (oříznutý na hranice obrazu v nekonečném případě), theta, rho pro Houghův tvar a length a magnitude pro velikost a počet hlasů.

5.26.2. Nekonečné čáry

find_lines() spouští Houghovu transformaci a vrací nejsilnější čáry, každou roztaženou přes celý obraz:

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 je minimální celkový počet hlasů, aby byla čára přijata. Celkový počet hlasů sčítá velikosti Sobelových hran každého přispívajícího pixelu, takže větší hodnoty threshold vyžadují k přijetí delší nebo silnější hrany – což činí vhodnou hodnotu závislou na rozlišení obrazu (delší čára při vyšším rozlišení nasbírá více hlasů) i na scéně, takže ji musíte vyladit pro konkrétní aplikaci. Jako hrubé výchozí body k ladění: 1000 pro běžnou čáru v čistém obraze, 500 nebo méně pro slabý kontrast či krátké čáry, 2000 nebo více pro rušné scény, kde se falešně pozitivní čáry tvoří shluky hranového šumu.

theta_margin a rho_margin řídí slučování blízkých maxim. Jediná fyzická hrana vytváří malý shluk binů s vysokým počtem hlasů kolem svého skutečného (theta, rho) a detektor každý shluk před vrácením sloučí na jeho vrchol. theta_margin=25 (stupňů) sloučí všechny vrcholy do 25 stupňů orientace; rho_margin=25 (pixelů) sloučí vrcholy do 25 pixelů vzdálenosti. Výchozí hodnoty jsou rozumné; jejich zvýšení vrací méně, výraznějších čar a jejich snížení vrací více, někdy duplicitních čar.

x_stride a y_stride procházejí hranové pixely během hlasování stejně, jako procházejí pixely v find_blobs(). Výchozí hodnoty 2 a 1 fungují pro běžný případ; jejich zvýšení urychlí hledání za cenu rozlišení. roi omezuje hledání na oblast snímku, což jednak zužuje vrácené čáry, jednak snižuje práci.

Každá vrácená čára je přímo vykreslitelná: objekt Line putuje rovnou do draw_line(), který z jeho začátku přečte pole koncových bodů (x1, y1, x2, y2). l.theta je úhel ve stupních, který čáru jediným porovnáním zařadí jako vodorovnou, svislou nebo šikmou. l.magnitude je celkový počet hlasů, který řadí vrácené čáry od nejsilnější po nejslabší.

5.26.3. Úsečky

find_lines() je správný detektor pro hrany, které zabírají celý snímek, ale mnoho reálných hran – levá strana vytištěného čárového kódu, horní hrana štítku, viditelná strana pravítka – se táhne jen přes část obrazu. find_line_segments() vrací konečné úsečky, jejichž koncové body jsou uvnitř snímku:

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

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

Detektor úseček sleduje orientované hranové pixely přímo, namísto hlasování v Houghově prostoru, a výsledkem je kolekce krátkých přímých úseků. merge_distance nastavuje maximální pixelovou mezeru, kterou mohou dva kolineární krátké úseky překlenout a přitom se ještě sloučit do jedné vrácené úsečky; max_theta_difference nastavuje, kolik stupňů orientace slučovač mezi sousedními úseky toleruje. Velkorysé slučování (merge_distance=10, max_theta_difference=15) vrací malý počet dlouhých úseček za cenu občasného přemostění skutečně oddělených hran; přísné slučování (merge_distance=0, max_theta_difference=5) vrací mnoho krátkých úseček a nechává aplikaci, aby si je vytřídila v Pythonu.

Výsledné objekty jsou téhož typu Line jako ty, které vrací find_lines(), se stejnými vlastnostmi, takže pipeline může zpracovávat oba druhy detekcí stejnou navazující cestou kódu. Jediným praktickým rozdílem je, že koncové body úseček jsou skutečnými konci čáry v obraze, zatímco koncové body nekonečných čar jsou tam, kde čára protíná okraj obrazu.

5.26.4. Kdy použít kterou

Volba mezi oběma metodami se scvrkává na jedinou otázku: záleží aplikaci na tom, kde čára končí?

find_lines() je správný nástroj, když je odpověď ne. Robot sledující čáru potřebuje vědět, kterým směrem čára vede a kde protíná spodní okraj snímku; samotná čára se táhne až k horizontu a dál. Detektor horizontu chce nejsilnější orientovanou hranu v obraze; nepotřebuje vědět, kde horizont končí.

find_line_segments() je správný nástroj, když je odpověď ano. Identifikace čtyř stran vytištěného obdélníku potřebuje čtyři úsečky se známými koncovými body. Sledování prstu ukazujícího na displej znamená sledovat krátkou úsečku, jejíž koncové body jsou špička a základna prstu. Měření délky viditelného škrábance potřebuje skutečný rozsah úsečky v pixelech.

Oba detektory sdílejí společné omezení: potřebují kontrast. Sobelův hranový filtr, na kterém staví, reaguje na gradienty jasu; barevná hrana proti stejně jasnému pozadí (červená čára na zelené stěně téže svítivosti) nevytváří žádný gradient a žádnou detekci. Když se takový případ v praxi objeví, řešením je před hledáním extrahovat jediný kanál LAB jako obraz ve stupních šedi se správným kontrastem – to_grayscale() s vybraným kanálem b izoluje červenou proti zelené tam, kde je samotný kanál svítivosti plochý – a předat tento obraz kanálu detektoru čar.