5.26. Pronalaženje linija i segmenata

Neke značajke scene nisu povezana područja boje, već usmjereni ravni rubovi: oslikana linija na podu, spoj između dvije površine, stranica tiskanog pravokutnika, rub dovratka. Tražiti od detektora mrlja da ih pronađe pogrešno je pitanje – rub je širok jedan piksel, algoritam mrlja želi područje-s-bojom, a odgovor se vraća prazan ili šumovit.

Pravi detektor za usmjerene rubove je Houghova transformacija linija. Modul image nudi je u dvije izvedbe: find_lines() vraća beskonačne linije (svaka linija proteže se preko cijele slike); find_line_segments() vraća konačne segmente (svaka linija ima krajnje točke unutar sličice). Koja je od njih potrebna aplikaciji ovisi o tome jesu li rubovi od interesa neprekinuti preko cijele sličice ili obuhvaćaju samo njezin dio.

5.26.1. Kako Houghova transformacija radi

Oba detektora dijele istu temeljnu ideju, pa se isplati razumjeti je jednom. Modul image najprije pokreće rubni filtar Sobelovog tipa na ulazu kako bi svakom pikselu pridijelio ocjenu koliko je vjerojatno da leži na usmjerenom rubu. Svaki takav rubni piksel zatim glasa za sve linije na kojima bi mogao ležati. Pobjeđuju linije koje skupe najviše glasova.

Linija je parametrizirana u Houghovom prostoru dvama brojevima: theta, kut linije (0 – 179 stupnjeva), i rho, okomita udaljenost od ishodišta slike do linije (s predznakom, u pikselima). Svaka linija koju slika sadrži jedna je točka u prostoru (theta, rho). Svaki rubni piksel na ulazu doprinosi jedan glas svakoj kombinaciji (theta, rho) sukladnoj svom položaju – konceptualno, krivulja kroz Houghov prostor. Tamo gdje se mnoge takve krivulje sijeku, mnogi rubni pikseli slažu se o istoj liniji, a to sjecište je detekcija.

Detektor vraća lokalne maksimume u Houghovom prostoru čiji ukupni broj glasova prelazi prag. Svaka vraćena Line nosi obje reprezentacije: x1, y1, x2, y2 za oblik s krajnjim točkama (odrezan na granice slike u beskonačnom slučaju), theta, rho za Houghov oblik, te length i magnitude za veličinu odnosno broj glasova.

5.26.2. Beskonačne linije

find_lines() pokreće Houghovu transformaciju i vraća najjače linije, svaku proširenu preko cijele slike:

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 najmanji ukupni broj glasova da bi linija bila prihvaćena. Ukupni broj glasova zbraja Sobelove veličine rubova svakog doprinosećeg piksela, pa veće vrijednosti threshold zahtijevaju dulje ili jače rubove da bi prošli – zbog čega ispravna vrijednost ovisi o razlučivosti slike (dulja linija pri višoj razlučivosti skuplja više glasova) kao i o sceni, pa se mora podesiti za pojedinu aplikaciju. Kao grube polazne točke za podešavanje: 1000 za umjerenu liniju na jasnoj slici, 500 ili manje za slab kontrast ili kratke linije, 2000 ili više za užurbane scene gdje se lažno-pozitivne linije stvaraju kroz skupine rubnog šuma.

theta_margin i rho_margin upravljaju spajanjem obližnjih maksimuma. Jedan fizički rub stvara malu skupinu pretinaca s mnogo glasova oko svojeg pravog (theta, rho), a detektor svaku skupinu sažima na njezin vrhunac prije vraćanja. theta_margin=25 (stupnjeva) spaja sve vrhove unutar 25 stupnjeva orijentacije; rho_margin=25 (piksela) spaja vrhove unutar 25 piksela udaljenosti. Zadane vrijednosti su razumne; njihovo povećanje vraća manje, izrazitijih linija, a smanjenje vraća više, ponekad dupliciranih linija.

x_stride i y_stride koračaju kroz rubne piksele tijekom glasovanja, na isti način na koji koračaju kroz piksele u find_blobs(). Zadane vrijednosti 2 i 1 rade za uobičajeni slučaj; njihovo povećanje ubrzava pretragu po cijenu razlučivosti. roi ograničava pretragu na područje sličice, što i sužava vraćene linije i smanjuje posao.

Svaka vraćena linija izravno je iscrtljiva: objekt Line predaje se ravno metodi draw_line(), koja s njegovog početka čita polja krajnjih točaka (x1, y1, x2, y2). l.theta je kut u stupnjevima, koji jednom usporedbom svrstava liniju kao vodoravnu, okomitu ili dijagonalnu. l.magnitude je ukupni broj glasova, koji sortira vraćene linije od najjače do najslabije.

5.26.3. Segmenti linija

find_lines() pravi je detektor za rubove koji obuhvaćaju cijelu sličicu, no mnogi stvarni rubovi – lijeva strana tiskanog barkoda, gornji rub oznake, vidljiva strana ravnala – protežu se samo preko dijela slike. find_line_segments() vraća konačne segmente čije su krajnje točke unutar sličice:

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 segmenata prati izravno duž usmjerenih rubnih piksela, umjesto da glasa u Houghovom prostoru, a rezultat je zbirka kratkih ravnih nizova. merge_distance postavlja najveći razmak u pikselima koji dva kolinearna kratka niza mogu premostiti i još se spojiti u jedan vraćeni segment; max_theta_difference postavlja koliko stupnjeva orijentacije spajač tolerira između susjednih nizova. Velikodušno spajanje (merge_distance=10, max_theta_difference=15) vraća mali broj dugih segmenata po cijenu povremenog premošćivanja istinski odvojenih rubova; strogo spajanje (merge_distance=0, max_theta_difference=5) vraća mnogo kratkih segmenata i prepušta aplikaciji da ih razvrsta u Pythonu.

Objekti rezultata istog su tipa Line kakav vraća find_lines(), s istim svojstvima, pa protok može obraditi obje vrste detekcije kroz isti silazni put koda. Jedina praktična razlika je da su krajnje točke segmenata stvarni krajevi linije na slici, dok su krajnje točke beskonačnih linija ondje gdje linija prelazi rub slike.

5.26.4. Kada koristiti koju

Izbor između dviju metoda svodi se na jedno pitanje: zanima li aplikaciju gdje linija prestaje?

find_lines() pravi je alat kada je odgovor ne. Robotu koji prati liniju treba znati kojim smjerom linija ide i gdje prelazi dno sličice; sama linija proteže se do horizonta i dalje. Detektor horizonta želi najjači usmjereni rub na slici; ne treba mu znati gdje horizont završava.

find_line_segments() pravi je alat kada je odgovor da. Prepoznavanje četiriju stranica tiskanog pravokutnika treba četiri segmenta s poznatim krajnjim točkama. Praćenje prsta koji pokazuje na zaslon znači praćenje kratkog segmenta čije su krajnje točke vrh i baza prsta. Mjerenje duljine vidljive ogrebotine treba stvarni opseg segmenta u pikselima.

Oba detektora dijele zajedničko ograničenje: trebaju kontrast. Rubni filtar Sobelovog tipa na kojem se temelje reagira na gradijente svjetline; obojeni rub na jednako svijetloj podlozi (crvena linija na zelenom zidu iste luminancije) ne stvara nikakav gradijent ni detekciju. Kada se taj slučaj pojavi u praksi, rješenje je izdvojiti jedan LAB kanal kao sliku u sivim tonovima s ispravnim kontrastom prije pretrage – to_grayscale() s odabranim kanalom b izdvaja crvenu naspram zelene tamo gdje je sam kanal luminancije ravan – i predati tu sliku kanala detektoru linija.