Houghova transformácia

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

Houghova transformácia (angl. Hough transform) je technika spracovania obrazu, ktorá sa používa na detekciu jednoduchých objektov v obraze ako sú priamky, kružnice, elipsy atď. Pri implementácii je nutné poznať analytický popis tvaru hľadaného objektu. Používa sa predovšetkým na segmentáciu objektov, ktorých hranice sa dajú popísať jednoduchými krivkami. Hlavnou výhodou tejto metódy je robustnosť voči nepravidelnostiam a porušeniu hľadanej krivky.[1]

Teória[upraviť | upraviť zdroj]

Normálový tvar priamky

Základný koncept ktorý je pri Houghovej transformácii využívaný pri hľadaní priamok je princíp duality. Bod môže byť definovaný 2 koordinátmi (x, y) alebo priamkami, ktoré cez neho prechádzajú. Množina kolineárnych bodov (body, ktoré ležia na jednej priamke), potom môže byť určená množinou priamok, ale existuje len 1, ktorá obsahuje všetky body . Môžeme teda povedať že bod môže byť definovaný množinou priamok a priamka definovaná množinou bodov.[2] Houghova transformácia využíva normálový tvar priamky. Normálovú rovnicu priamky je možné zapísať ako:

kde predstavuje vzdialenosť priamky od počiatku súradnicovej sústavy a je veľkosť uhlu medzi normálou a osou x.

Hodnoty a sú v tomto prípade známe a a sú neznáme. Ak dosadíme známe hodnoty , a iterujeme hodnotu na intervale , v súradnicovej sústave sa nám zakreslí krivka. Bod je teda možné v priestore parametrov  (inak aj Houghovom priestore) reprezentovať ako krivku.[3] Na nasledujúcom obrázku môžeme vidieť ako sa bod (vľavo) zobrazí na krivku v Houghovom prisetore (vpravo).

Houghova transformacia1.png

Pri zobrazení kolineárnych bodov v Houghovom priestore vidíme že, krivky sa pretínajú v jednom bode. Tento bod svojimi koordinátmi určuje priamku v priestore bodov.

Houghova transformacia2.png

Implementácia[upraviť | upraviť zdroj]

Houghova transformácia je implementovaná kvantizáciou Houghovho priestoru do konečných intervalov.[4] Ide o rozdelenie diskrétneho priestoru na úseky alebo bunky, ktoré tvoria akumulátor. Akumulátor si môžeme predstaviť ako maticu, ktorej počet rozmerov sa rovná počtu hľadaných parametrov. V prípade priamky sú to 2. Akumulátor je na začiatku naplnený samými nulami.[3] Pre každý bod z priestoru (x, y) sa potom inkrementuje hodnota v bunkách akumulátoru, ktoré predstavujú priamky prechádzajúce daným bodom. V akumulátore sa následne hľadajú lokálne maximá, ktoré veľmi pravdepodobne predstavujú hľadané priamky. Existuje viacero metód, ktorými je možné maximá hľadať.[4]

Algoritmus na detegovanie čiar môžeme rozdeliť do týchto krokov:[5]

  1. Na obrázok sa aplikuje detekcia hrán, napr. použitím Cannyho detektoru
  2. Hranové body sa mapujú do Houghovho priestoru a akumulátoru.
  3. Nájdenie priamok – nájdu sa maximá v akumulátore.
  4. Konverzia priamok (nekonečne dlhé) na úsečky (konečne dlhé).
Houghova transformácia: (a) pôvodný obrázok, (b) výstup Cannyho hranového detektoru, (c) Houghov priestor, (d) nájdené priamky.

Príklad[upraviť | upraviť zdroj]

Hough transform diagram.svg

Pre každý z 3 bodov sa vytvoria priamky pod rôznymi uhlami. V prípade tohto príkladu je to pre jednoduchosť len 5 uhlov. Pre každú priamku sa vypočíta jej vzdialenosť od počiatku . Pre daný uhol a vzdialenosť sa následne zvýši hodnota o 1 v prislúchajúcej bunke akumulátoru.

Akumulátor by mohol vyzerať takto (vypočítané hodnoty r sú zaokrúhlené k najbližšej hodnote v akumulátore):

\ r 180 200 220 240 260 280 300 320 340 360 380 400 420 440
15 1 0 0 0 0 0 0 1 0 0 0 0 1 0
30 0 0 0 0 0 1 0 0 0 0 1 0 0 1
45 0 0 0 0 0 0 0 0 0 1 0 1 0 1
60 0 0 0 0 0 0 0 0 0 0 0 3 0 0
75 0 0 0 0 0 0 0 0 1 0 1 0 1 0

Vidíme že maximum (3) sa nachádza v bunke (400,60). Našli sme priamku, ktorá leží najbližšie všetkým trom bodom. Priamka má uhol = 60° a vzdialenosť od počiatku r = 400. (Akumulátor pre jednoduchosť obsahuje široké intervaly uhlov a vzdialeností, pre nájdenie presnejšej priamky je potrebný väčší akumulátor s malými intervalmi.)

Referencie[upraviť | upraviť zdroj]

  1. Hledání parametrického popisu objektů pomocí Houghovy transformace [online]. 2008, [cit. 2020-11-06]. Dostupné online.
  2. DAVIES, E. R. (E. ROY),. Computer and machine vision : theory, algorithms, practicalities. Waltham, Mass. : Elsevier, 2012. (4th ed.) Dostupné online. ISBN 978-0-12-386991-3.
  3. a b KUPKA, Jiří. Houghova transformace [online]. 2018, [cit. 2020-11-06]. Dostupné online.
  4. a b Hough Transform [online]. 2003, [cit. 2020-11-06]. Dostupné online.
  5. Line Detection by Hough transformation [online]. 20.4.2009, [cit. 2020-11-06]. Dostupné online.