Houghova transformace

Pokud v obrazech potřebujeme detekovat jednoduché geometrické tvary - najčastěji přímky či kružnice (můžeme však chtít detekovat klidně i jinou křivku), nejspíš sáhneme po Houghově transformaci, u které využíváme znalosti rovnice hledaného útvaru. Mějme například rovnici přímky ve směrnicovém tvaru:

$$ y = kx + q $$

Při běžných úlohách většinou známe koeficienty $k$ a $q$. První z nich nám určuje směrnici, druhý pak posunutí na ose $y$. S takovou rovnicí pak běžně zacházíme tak, že za $x$ dosadíme nějakou konkrétní hodnotu $x_0$ a tím získáme hodnotu $y_0$ bodu, který na přímce leží. Co když se však na celý problém podíváme naopak? Řekněme, že známe souřadnice několika bodů v prostoru, které na této přímce pravděpodobně leží. Když tyto známé body dosadíme do rovnice výše, stanou se nám neznamými hodnoty koeficientů $k$ a $q$. V tento okamžik provedeme jednoduchou transformaci rovnice na tvar:

$$ -q = kx_0 - y_0\\ q = -kx_0 + y_0 $$

Nyní se můžeme pohodlně přenést do tzv. akumulačního prostoru. Je to diskrétní prostor (rozdělený na konečné úseky, buňky), který je při vytvoření naplněný samými nulami. Dalo by se jej snadno představi jako matici v paměti počítače o daných rozměrech. Tento prostor má svou souřadnou soustavu tvořenou osami, kde tentokrát pro změnu nemáme osy $x$ a $y$, ale $k$ a $q$. Rovnou si můžeme určit, že horizontální osa bude patřit nezvávislé proměnné $k$ a vertikální osa hodnotě $q$. Řekněme, že proměnná $k$ může nabývat hodnot na intervalu reálných čísel $(-10; 10\rangle$ a šířka matice bude 2000 buněk reprezentujících interval celých čísel $(-1000; 1000\rangle$. Nyní nezbývá nic jiného, než do proměnné $k$ dosazovat čísla z intervalu $(-1000; 1000\rangle$ jedno po druhém (reálně do proměnné $k$ nedosazujeme hodnoty -1000, -999, ..., ale tuto hodnotu podělíme 100, abychom se dostali na interval $(-10; 10\rangle$) a dopočítávat hodnoty $q$. Vypočtený bod o souřadnicích $[k, q]$ je souřadnice buňky v matici, jehož hodnotu inkrementujeme. Pokud dříve v buňce byla hodnota 0, zvýšíme ji na 1 atd. Tuto operaci provedeme pro všechny body v prostoru. Nakonec zjistíme, na kterých souřadnicích se nachází nejvyšší hodnota v matici a odtud vyčteme pravděpodobné koeficienty $k$ a $q$ přímky.

Jenže, přímka v tomhle tvaru má jednu zásadní nevýhodu - to, co bychom inkrementovali, je směrnice. V určitém okamžiku bychom se dostali na limit natočení a třeba přímku vodorovnou s osou $x$ bychom získali stěží, protože v takovém případě by musela být směrnice $k$ rovna nekonečnu. A nekonečno se přeci jen špatně zakresluje do grafu. V praxi proto využíváme jiný tvar přímky - normálový. Tento tvar vypadá následovně:

$$ 0 = x\cos(\theta)+y\sin(\theta)-r\\ y = \frac{r}{\sin(\theta)}-\frac{x\cos(\theta)}{\sin(\theta)} $$

Zde známe parametr $r$, což je vzdálenost přímky od počátku a $\theta$, což je velikost orientovaného úhlu od první osy. Při převodu do akumulačního prostoru budeme muset rovnici opět upravit tak, ať jsou hodnoty $x_0$ a $y_0$ známé a $\theta$ a $r$ neznámé:

$$ r = y\sin(\theta)-x\cos(\theta) $$

Do rovnice opět dosazujeme známé hodnoty $x_0$, $y_0$ a iterujeme hodnotu $\theta$ na intervalu $\langle0;\pi\rangle$. Do akumulačního prostoru se nám zakreslní vlnka. Celý tento proces si můžete vyzkoušet na interaktivním widgetu. [otevřít v novém okně]