Houghova transformace pro detekci přímek na obrázku

Moje diplomová práce v poslední době tak trochu stagnovala — nebylo moc času, naopak přebytek práce. V práci se budu věnovat moderním metodám ve zpracování obrazu. Jako první větší část je lehce se poohlédnout po možnostech využití Houghovy transformace. Houghova transformace je velice zajímavý nástroj pro hledání některých jednoduchých geometrických útvarů na obrázcích. Mezi ty jednoduché řadíme přímky a kuželosečky, jako kružnice, elipsy a další. V tomto krátkém článku se podíváme na základní princip Houghovy transformace na příkladě hledání přímky v obraze.

Houghova transformace (HT) se používá velmi často při počítačovém vidění a rozpoznávání obrazů na snímku. ůPřímka ve dvourozměrném prostoru je definována několika způsoby, přičemž nejznámější je směrnicový tvar rovnice přímky y = kx + q, kde k je směrnice přímky a q je posun v ose y. Pro Houghovu transformaci je ovšem výhodnější užít normálový tvar

y = \frac{ x \cdot \cos (\psi)}{\sin (\psi)} + \frac{r}{\sin(\psi)}

přičemž parametr r je vzdálenost bodu [x,y] od počátku O a \psi je velikost orientovaného úhlu, jehož první rameno je první kladná poloosa a druhé rameno je polopřímka s počátečním bode O vedená kolmo k přímce. Použití tohoto normálového tvaru rovnice přímky má tu výhodu, že je nezávislá na orientaci os.

Nyní každý pixel na obrázku převedeme z prostoru souřadnic (x,y) do souřadnic (\psi, r) a daným bodem povedeme všechny myslitelné přímky:

Jediný bod v obrázku o rozměrech 100×100pixelů na souřadnici x=5, y=85
Jediný bod v obrázku o rozměrech 100×100pixelů na souřadnici x=5, y=85
...a jeho projekce všech přímek procházející tímto bodem do prostoru parametrů r a psi s užitím Houghovy transformace
...a jeho projekce všech přímek procházející tímto bodem do prostoru parametrů r a psi s užitím Houghovy transformace

Jak je vidět na obrázcích výše, tak v prostoru souřadnic (\psi,r) vykreslíme všechny myslitelné přímky, které bodem X mohou procházet — tímto nám vznikne sinusoida. Při troše zamyšlení je zřejmé, že budou-li body dva, budou i dvě křivky v HT prostoru (každá pro každý bod — pamatujme, že každá křivka v Houghově prostoru reprezentuje hodnoty (\psi,r) všech přímek, které mohou procházet bodem, ke kterému se vztahují.

Jak se tedy projeví přímka, která bude procházet dvěma body zároveň? Uvažme, že musí mít stejné parametry — je to jedna a tatáž přímka. V houghově prostoru se bude jednat o jeden konkrétní bod: parametry (\psi,r) dané přímky. Pokud přímka prochází oběma body zároveň, tak se dvě sinusoidy (každá pro jeden ze dvou bodů) protnou právě v jednom místě: v bodě určujícím, že daný bod je právě onou hledanou sestavou parametrů přímky. Podívejme se na obrázky representující dva body:

Dva body v obrázku o rozměrech 100×100 na souřadnicích A(20;50) a B(70;50)
Dva body v obrázku o rozměrech 100×100 na souřadnicích A(20;50) a B(70;50)
...jejich převedení do prostoru parametrů r a psi s užitím Houghovy transformace
...jejich převedení do prostoru parametrů r a psi s užitím Houghovy transformace

Jaká jsou omezení metody? Co se například stane, bude-li na obrázku přímek více? Jak se projeví přímka, jejíž směrnice je přesně 1? Neboli přímo svislá (úhel zde je zároveň 0 i 180, že…?). No, co to zkusit zároveň, uvidíme:

Dvě kolmé přímky; a: x = 49; b: y = 49
Dvě kolmé přímky; a: x = 49; b: y = 49
Dvě přímky v Houghově prostoru. U přímky b je vidět, že má dvě možná řešení -- (0,180) a (180,90)
Dvě přímky v Houghově prostoru. U přímky b je vidět, že má dvě možná řešení -- (0,180) a (180,90)

Nabízí se myšlenka, že HT je pro tyto svislé přímky zcela nevhodná: U přímky b je vidět, že má dvě možná řešení — (0,180) a (180,90). Ovšem dosaďte si výsledné hodnoty — nezobrazí obě stejnou přímku? Na pravém obrázku je navíc poměrně jasně vidět, jak vypadá řešení kompletní přímky — více sinusoid pouze „zvýší“ četnost ve správném řešení.

Pro úvod to bude snad stačit. Příště (zase za čas… 😉 ) napíšu, jak se HT dá použít pro detekci kružnic na snímku.

1 komentář u „Houghova transformace pro detekci přímek na obrázku“

  1. Ahoj,
    myslis, ze se da Houghova transformace pouzit i na detekci 3D objektu (napr. koule resp. jejiho stredu) z mnoziny namerenych dat na kulove plose.

    Dik.

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *