# Strukturální metody rozpoznávání

Otoč obrázek číslice o třicet stupňů a [příznakovému klasifikátoru](Priznakove-metody) postavenému na jasech pixelů se rozsype všechno. Vektor je úplně jiný, vzdálenosti k etalonům jsou jiné, klasifikace je jiná.

Přitom se nezměnilo nic podstatného. **Dvojka je pořád tvořená obloukem nahoře, šikmou čárou a vodorovnou čárou dole - v tomhle pořadí a v těchhle vztazích.** Kdybys objekt popsal takhle, otočení by nevadilo.

To je celá myšlenka strukturálních metod. Místo čísel popisují objekt **jeho stavbou**. Tahle stránka ukazuje, jak se takový popis staví, jaká pravidla platí pro volbu primitiv a jak se výsledek klasifikuje formálními gramatikami. Předpokládá to [klasifikaci a rozpoznávání](Klasifikace-a-rozpoznavani), zejména rozdíl mezi příznakovým a strukturálním popisem.

## Z čeho se strukturální popis skládá

Strukturální popis rozpoznávaného objektu sestává ze tří věcí:

- **primitiv** - základních strukturálních elementů,
- **vlastností primitiv** - unární relace,
- **relací mezi primitivy** - prostorové, časové, funkční, tedy binární a vyšší relace.

Vytvořený symbolický popis je **obrazem popisujícím strukturální vlastnosti objektu**.

Jako strukturální popis se dá použít:

- **řetězec symbolů** označujících primitiva,
- **relační struktura**,
- **graf** - obecný, speciální a další.

**A teď to nejdůležitější na celé stránce:** strukturální popisy objektů patřících do téže třídy tvoří **jazyk té třídy**. Rozpoznávání strukturně popsaného objektu tedy znamená rozhodnout, **jestli popis daného objektu (slovo) patří do jazyka příslušné třídy**.

Tím se úloha rozpoznávání převede na úlohu z teorie formálních jazyků. To je elegantní a je to důvod, proč tahle větev existuje.

## Proč to dělat

**Invariance na pozici a natočení obrazu.** Vztah „dotýká se" platí bez ohledu na to, kde v obrázku ty dva tvary jsou a jak jsou otočené.

**Méně složité popisy u složitých objektů.** Popis je hierarchický, ne pixelově-bodový. Obličej popíšeš jako oči, nos a ústa ve vzájemných vztazích, ne jako čtvrt milionu čísel.

## Postup vytváření popisu

Čtyři kroky, které se dělají v tomhle pořadí:

1. **Nalézt všechna primitiva** a přiřadit jim prvky nosiče struktury.
2. **Každému prvku struktury přiřadit vlastnost** (unární relaci) označenou jménem odpovídajícího primitiva.
3. **Určit vztahy mezi primitivy** (binární relace) - vznikne relační struktura.
4. **Doplnit případnou informaci číselné povahy** - vznikne sémantická informace, respektive sémantický vektor.

Ten čtvrtý krok je most zpátky k [příznakovým metodám](Priznakove-metody). **Strukturální a příznakový popis se nevylučují** - sémantický vektor je právě to místo, kde se do struktury dostanou čísla (délky, úhly, plochy).

### Příklad: dům

Mějme obraz domu s prvky `M ≡ {T, O, C1, C2}`.

- **Unární relace:** `T` je trojúhelník, `O` je obdélník, `C` je čtverec.
- **Binární relace:** *dotýká se* a *je uvnitř*.

Popis pak zní: trojúhelník `T` se dotýká obdélníku `O`, čtverce `C1` a `C2` jsou uvnitř obdélníku `O`. Střecha na zdi, okna ve zdi.

**Zkus si na tom, co všechno ten popis nezajímá.** Jak je dům velký, kde na obrázku leží, jestli je natočený, jakou má barvu. Zajímají ho čtyři tvary a tři vztahy. Přesně proto je invariantní.

## Tři pravidla pro extrakci primitiv

Tohle je ta část, která rozhoduje o použitelnosti celého přístupu.

1. **Počet typů primitiv i relací mezi nimi by měl být co nejmenší.** Každý typ navíc znamená větší gramatiku a víc věcí, které se můžou splést.
2. **Primitiva by měla odpovídat základním (přirozeným) strukturálním elementům objektu**, jimiž lze objekt vyčerpávajícím způsobem popsat. Musí být **snadno extrahovatelná a klasifikovatelná** - typicky některou příznakovou metodou.
3. **Nalezení primitiv a relací by mělo být algoritmicky co nejjednodušší.**

Všimni si závorky v druhém bodě. **Extrakce primitiv se dělá příznakovou metodou.** To je celý problém strukturálního přístupu v jedné větě: aby fungoval, musí nejdřív fungovat ten přístup, který má nahradit.

## Freemanův řetězový kód

Nejjednodušší strukturální popis tvaru, jaký existuje. Směrová „růžice" má osm směrů očíslovaných 0 až 7 a obrys objektu se zapíše jako posloupnost směrů, kterými se po něm jde.

Pro číslici **2** v kódovacím rastru vyjde:

```
10765556000
```

**Je to elegantní strukturální popis tvaru znaku invariantní vůči translaci.** Posuň číslici kamkoliv a kód zůstane stejný, protože se popisuje jen změna směru, ne poloha.

Invariantní vůči **rotaci** ale není - otočením se všechny číslice posunou. Řeší se to tím, že se kód normalizuje (cyklicky posune tak, aby začínal nejmenší hodnotou) nebo se použije **diference** sousedních směrů místo směrů samotných.

## Strukturální popisy číslic 2 a 6

Definuj primitiva - úsečky a oblouky v různých orientacích - označená písmeny `A` až `H`. Pak typický popis vypadá takhle:

| Číslice | Popis |
|---|---|
| **2** | `GAAC`, resp. `EFAAACC` |
| **6** | `BBHG` (nebo `BBGH`), resp. `BBBGHFE` |
| **6** složitější množinou primitiv | `DDDHEGF` nebo `DDDHAEGBF` |

Podívej se na tu tabulku pozorně, protože je z ní vidět zásadní problém celého přístupu. **Tatáž šestka má čtyři různé popisy.** Záleží na tom, jak jemná je množina primitiv a jak přesně se obrys segmentoval.

Jemnější popis lze udělat směrovou růžicí s osmi symboly (`k, h, n, l, p, m, d, o`) a primitivy `A` až `H` odpovídajícími jednotlivým možným tvarům úseček.

## Gramatiky a syntaktická analýza

Pro klasifikaci strukturálních popisů (slov) se s výhodou používají **formální gramatiky**. Každé třídě objektů odpovídá jedna gramatika `Gi`.

Vstupní obraz `x` se klasifikuje **paralelní syntaktickou analýzou** všemi analyzátory `L(G1), L(G2), ..., L(GR)` naráz a blok výběru rozhodne o výsledné třídě `ω`.

```mermaid
flowchart LR
    X["obraz x"] --> P[extrakce primitiv]
    P --> S["slovo (řetězec primitiv)"]
    S --> G1["analyzátor L(G1)"]
    S --> G2["analyzátor L(G2)"]
    S --> G3["analyzátor L(GR)"]
    G1 --> V[blok výběru]
    G2 --> V
    G3 --> V
    V --> W["třída ω"]
```

**Struktura je stejná jako u [diskriminačních funkcí](Klasifikace-a-rozpoznavani#diskriminační-funkce).** Každá třída má svůj „hodnotič" a vybere se ten, který uspěje. Rozdíl je jen v tom, že místo čísla vrací analyzátor odpověď ano/ne.

### Příklady gramatik pro geometrické objekty

Mějme primitiva: `a` je vodorovná úsečka, `b` je svislá, `c` je `/`, `d` je `\`, `e` je `(`, `f` je `)`.

Sedm jednoduchých gramatik `G1` až `G7` generuje sedm různých objektů: kruh, ovál, čtverec, obdélníky různé orientace, trojúhelník a dům. Například:

```
G2:  S2 → X2 Y2,  X2 → e Z,  Y2 → f Z,  Z → aZ | a
```

generuje `eafa`, `eaafaa`, tedy obecně `e(a)ⁿ f(a)ⁿ` - dvě svislé oblé strany a mezi nimi `n` vodorovných úseků, což je ovál.

```
G4  generuje  baabaa, baaabaaa, tedy b(a)ⁿ b(a)ⁿ
```

**To `n` na obou místech je klíčové.** Gramatika vynucuje, aby obě strany měly stejnou délku - a to je vlastnost, kterou by příznakový klasifikátor musel měřit číslem. Tady vyplývá přímo ze struktury.

Zároveň je to důvod, proč tyhle jazyky nejsou regulární. `a^n b^n` je klasický příklad bezkontextového jazyka, takže potřebuješ zásobníkový automat, ne konečný.

## Kde strukturální metody přestávají platit

**Extrakce primitiv je slabý článek.** Celý přístup stojí na tom, že se primitiva správně najdou. Jedna chybějící úsečka změní slovo a analyzátor ho odmítne. **Strukturální popis je binární - buď do jazyka patří, nebo ne** - takže drobná chyba v segmentaci není drobná chyba ve výsledku.

**Reálná data jsou zašuměná a gramatiky ne.** Řeší se to stochastickými gramatikami, kde má každé pravidlo pravděpodobnost, ale tím se přístup komplikuje a část elegance mizí.

**Návrh gramatiky je ruční práce.** Existuje gramatická inference, tedy odvození gramatiky z příkladů, ale je to těžká úloha a v praxi se používá zřídka.

**Proto to dnes potkáš vzácně.** Strukturální metody prohrály s [konvolučními sítěmi](Konvolucni-site), které se naučí hierarchický popis samy z dat - hrany, pak části objektů, pak objekty - a nepotřebují k tomu ani ručně navržená primitiva, ani gramatiku. **Myšlenka hierarchického popisu ale vyhrála**, jen se realizuje jinak.

Kde se strukturální přístup drží: rozpoznávání chemických struktur, analýza otisků prstů (markanty a jejich vztahy) a všude, kde je struktura zadaná exaktně a šum je malý.

## Co si odnést

**Objekt = primitiva + vlastnosti + relace.** Ne vektor čísel.

**Popisy jedné třídy tvoří jazyk, klasifikace je rozhodnutí o příslušnosti do jazyka.**

**Invariance na posun a rotaci je zdarma.** To je hlavní důvod, proč se to dělá.

**Primitiv a relací má být co nejmíň** a musí jít snadno najít - typicky příznakovou metodou.

**Freemanův kód je invariantní vůči posunu, ne vůči rotaci.**

**Slabý článek je extrakce primitiv.** Jedna chyba v segmentaci znamená odmítnuté slovo.

## Kam dál

- **[Příznakové metody](Priznakove-metody)** - druhá polovina rozpoznávání, na kterou se tady spoléhá při extrakci primitiv
- **[Klasifikace a rozpoznávání](Klasifikace-a-rozpoznavani)** - kam oba přístupy zapadají
- **[Konvoluční sítě](Konvolucni-site)** - metoda, která hierarchický popis vytvoří sama
- **[Jazykové modely](Jazykove-modely)** - jiné použití formálních jazyků v UI