# AZO 3. Digitální geometrie (30 %)
###### tags: `AZO`

:::warning
* Digitalizační modely
* Gauss
* Jordan
* průsečíky s mřížkou
* Odhad geometrických a topologických vlastnotí digitálních množin
* délkové a plošné míry
* Eulerova charakteristika
* Výpočet digitálních metrik a jejich aproximace
* Euklidovské
* geodetické
:::

## Digitalizační modely
Digitalizace je transformace ze spojitého prostoru do diskrétního. Pokud digitalizujeme kruh $D$ o průměru 1, plocha digitalizovaného kruhu se blíží reálné ploše spojitého kruhu se zjemňující se digitalizační mřížkou. Toto můžeme zapsat formálně následovně:
$$ \lim_{h \rightarrow \infty} A(dig_h(D)) = A(D) = \frac{\pi}{4} \,. $$
Mluvíme o konvergenci odhadu digitalizace. Na druhou stranu, obvod kruhu nekonverguje se zjemňující se digitalizační mřížkou a digitalizovaný kruh má stále obvod 4.

Neformálně lze říci, že digitalizace probíhá způsobem, že si zvolíme pro čtvereček mřížky množinu, která pokud má s digitalizovanou množinou neprázdný průnik (nebo výsledkem průniku jsou všechny body zvolené ve řtverečku mřížky) pak daný čtvereček je obsažen v digitalizované množině.

### Gaussova digitalizace
Gaussova digitalizace $G_h(S)$ je množina čtverců mřížky, jejichž střed je obsažen ve množině digitalizovaného tvaru $S \in \mathds{R}^2$.
Přesnost digitalizace je dána rozlišením (jemností) mřížky $h$. Zjemnění mřížky faktorem $1/h$ je to stejné jako zvětšení spojitho tvaru $S$ faktorem $h$.
$$hS$ = \{(hx, hy) : (x, y) \in S \}$$

#### Vlastnosti
* digitalizace nepřázdné množiny S je sjednocení konečného množství jednoduchých izotetických polygonů (polygony osově paralerní a jejich vrcholy jsou na celočíselné souřadnici)
* různé množiny můžou mít stejnou Gaussovu digitalizaci
* stejná množina po rigidní transofrmaci může mít různou digitalizaci

### Jordanova digitalizace
Jordanova vnitřní digitalizace $J_h^{-}(S)$ je množina čtverců mřížky, jejichž všechny body jsou obsaženy v množině digitalizovaného tvaru $S$.
Jordanova vnější digitalizace $J_h^{+}(S)$ je množina čtverců mřížky, jejichž všechny body mají nepázdnou množinu po průniku s množinou $S$.

#### Vlastnosti
* pokud hranice neprazdné množiny $S$ neobsahuje žádnou hranu mřížky nenulové délky, pak vnitřní hranice nikdy neprotíná vnější hranici. (???)
* vnější a vnitřní Jordanova digitalizace neprázdné množiny $S$ je sjednocení konečného množství jednoduchých izotetických polygonů
* vnější Jordanova digitalizace spojité množiny S je vždy jeden spojitý izotetický polygon nebo polyhedron. Nezanechává spojitost, může vytvořit díry.

### Jordanova vs. Gaussova digitalizace
* $J_h^{-}(\emptyset) = G_h(\emptyset) = J_h^{+}(\emptyset) = \emptyset$
* $J_h^{-}(R^2) = G_h(R^2) = J_h^{+}(R^2) = R^2$
* $J_h^{-}(S) \subseteq G_h(S) \subseteq J_h^{+}(S)$

### Průsečíky s mřížkou
Pro digitalizaci křivek není vhodná Gaussova ani Jordanova digitalizace. Pro křivky se používá digitalizace průsečíky s mřížkou $R_h(\gamma)$. Výsledek digitalizace průsečíku s mřížkou je množina obsahující mřížkové body, které jsou nejbližší (Euklidovskou vzdáleností) k prušečíkům s okraji mřížky (na obrázku červené čáry)
* pokud jsou dva body stejně vzdálené od průsečíku, vybereme pouze jeden nebo vezmeme oba dva.
* platí: $J_h^{-}(\gamma) = \emptyset \subseteq R_h(\gamma) \subseteq J_h^{+}(\gamma)$

Výsledná sekvence mřížkových bodů je nazývaná "digitized grid-intersection sequence" a může být reprezentována pomocí řetezového kódu (chain-code - sekvence čísel 0-8 reprezentující směr, kde se nachází další bod).
Bressenhamův algoritmus pro digitalizaci rovných čar je digitalizace průsečíky s mřížkou.


## Odhad geometrických a topologických vlastnotí digitálních množin
### Délkové a plošné míry
#### metrika (metric) a velikost (norm)
Metrika (nebo distance function) je funkce $d: S \times S \rightarrow R$, která splňuje následnující pravidla:
* nezáporná - pro všechny vstupy $p$ $q$ platí $d(p, q) >= 0$ a $d(p, q) = 0$ pokud $p = q$
* symetrická - pro všechny $p$ $q$ platí $d(p, q) = d(q, p)$
* trojúhelníková nerovnost - pro všechny body $p, q, r$ platí $d(p, r) \leq d(p, q) + d(q, r)$

Norm je funkce, která přiřazuje reálné nezáporné číslo vektoru z $n$-dimenzionálního vektorového prostoru, pro kterou platí následující pravidla:
* identita - $\parallel p \parallel = 0$ pokud $p = (0, \dots, 0)$
* homogenita - vynásobení skaláarem je jedno jestli před aplikováním normy nebo po, $\parallel a \cdot p \parallel = \vert a \vert \cdot \parallel p \parallel$
* trojůuhelníková nerovnost - $\parallel p + q \parallel \leq \parallel p \parallel + \parallel q \parallel$

Minkowski metriky $\parallel p \parallel_m$ pro $m \leq 1$ nebo $m = \infty$ jsou následnující:
$$L_m(p, q) = \sqrt[m]{\vert x_1 - y_1 \vert^m + \dots + \vert x_n - y_n \vert^m}$$
$$L_{\infty}(p, q) = max\{ \vert x_1 - y_1 \vert, \dots, \vert x_n - y_n \vert \}$$

Metriky na mřížce jsou:
* $d_4(p, q) = L_1(p, q)$
* $d_8(p, q) = L_2(p, q)$
* $d_e(p, q) = L_{\infty}(p, q)$ - není celočícelná metrika, může být převedena pomocí operací floor, ceil nebo round (POZOR - floor a ceil nejsou metriky v $Z^n$)

Dvě metriky mohou být zkombinovány pomocí:
* lineární kombinace dvou metrik $d'$ a $d''$ - $d(p, q) = a \cdot d'(p, q) + b \cdot d''(p, q)$ kde $a, b > 0$
* maxima z dvou metrik - $d(p, q) = max\{ d'(p, q), d''(p, q) \}$

POZOR! - vynásobení dvou metrik nebo minimum z dvou metrik nemusí být nutně metrika.

#### distance transform
Distance transform přiřazuje každému bodu z pozadí nejkratší vzdálenost k bodu z pozadí. Pro metriky $d_4$ a $d_8$ je pomocí dvou průchodové metody (dopředu a dozadu). Pro $d_e$ buď brute-force, fast marching algoritmus (PA166) nebo Danielssonův algoritmus