Strukturální metody rozpoznávání

Otoč obrázek číslice o třicet stupňů a příznakovému klasifikátoru 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í, 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í:

Nalézt všechna primitiva a přiřadit jim prvky nosiče struktury.
Každému prvku struktury přiřadit vlastnost (unární relaci) označenou jménem odpovídajícího primitiva.
Určit vztahy mezi primitivy (binární relace) - vznikne relační struktura.
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. 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.

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.
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.
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ě ω.

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í. 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, 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 - druhá polovina rozpoznávání, na kterou se tady spoléhá při extrakci primitiv
Klasifikace a rozpoznávání - kam oba přístupy zapadají
Konvoluční sítě - metoda, která hierarchický popis vytvoří sama
Jazykové modely - jiné použití formálních jazyků v UI