7. Rozpoznávanie obrazcov  

     Rozpoznávanie je posledným krokom pri spracovaní obrazu. Má za úlohu zaradiť objekty do tried. Trieda je podmnožina objektov, ktoré z hľadiska klasifikácie majú podobné vlastnosti. Zariadenie, ktoré rozhoduje o príslušnosti objektu do triedy sa nazýva klasifikátor.
   Poznáme dve základné metódy rozpoznávania:

• Príznakové rozpoznávanie
• Syntaktické rozpoznávanie

   Pred tým, ako sa pustíme do rozpoznávania, musíme určiť popis objektov. Cieľom popisu je určiť číselný vektor príznakov, alebo nečíselný syntaktický popis charakterizujúci tvar, alebo iné vlastnosti objektu.

7.1 Popis objektov

   Predpokladom popisu objektov je ich identifikácia v obraze. Na to slúžia rôzne algoritmy na farbenie oblastí. Po identifikácií objektu ho môžeme začať skúmať. Pri skúmaní charakteristických vlastností objektov môžeme vychádzať zo znalosti oblasti, alebo len z jeho hranice.  
   Metódy na popis objektov rozdeľujeme na:

• Matematické, napr.: Fourierova transformácia
• Heuristicke, napr.: pozdĺžnosť objektu.

   Metódy delíme aj podľa toho, aký typ popisu nám dávajú:

• Príznakový popis
• Syntaktický popis.

7.1.1 Identifikácia oblasti

   Jednou možnosťou identifikácie oblasti je farbenie. Princípom farbenia je, že každú oblasť označíme iným prirodzeným číslom. Predpokladajme, že proces segmentácie nám vrátil obraz skladajúci sa z 0 a 1. Kde 0 je pozadie a 1 označuje časť objektu v obraze.

Obr. 7.1 Masky určujúce susedov pre farbenie.  
a) 4-susednosť   b) 8-susednosť.

Algoritmus farbenia:

   Prvý prechod: Prechádzajme obraz po riadkoch. Každému nenulovému obrazovému elementu f(i,j) priradíme hodnotu podľa hodnoty jeho susedných elementov. Poloha susedov je daná na obr. 7.1, pričom všetky susedné elementy už boli algoritmom  ofarbené.

-         Ak všetky susedné elementy sú ofarbené farbou pozadia, potom f(i,j) priradíme doteraz nepoužitú farbu.

-         Ak práve jeden zo susedov má nenulovú hodnotu, potom priradíme f(i,j) farbu suseda.

-         Ak je viac susedných elementov nenulových, potom f(i,j) priradíme ľubovolnú z nich. Ak hodnoty susedov boli rôzne, nastane kolízia farieb a musíme označiť kolíziu farieb.

   Druhý prechod: Prejdeme znovu celý obraz a podľa informácie o ekvivalencie farieb prefarbíme obraz tak, aby každá oblasť bola ofarbená jednou farbou.

Algoritmus pre 4-susednosť použije masku z obr. 7.1 a) a algoritmus pre 8-susednosť masku z obr. 7.1 b).  

Simulácia farbenia.

7.1.2 Popis vychádzajúci z hranice oblasti  

   Hranicu oblasti najčastejšie zapisujeme pomocou reťazového kódu. Hranica je určená počiatočným bodom a postupnosťou čísiel, ktoré určujú smer hranice. Reťazový kód je znázornený na obr. 7.2.

 
Obr. 7.2 Reťazový kód.  

Reťazový kód môžeme získať algoritmom sledovania hranice (4.2).

   Popisy hranice:

• Dĺžka, základná vlastnosť hranice. Dĺžku môžeme určiť jednoducho pomocou reťazového kódu hranice. Vertikálny a horizontálny posun ohodnotíme dĺžkou 1, diagonálny posun dĺžkou Ö2.
• Zakrivenie hranice, je pomer medzi všetkými prvkami hranice a tými, kde dochádza k významnej zmene smeru.
• Postupnosť segmentov, ak poznáme typ každého segmentu, môžeme hranicu popísať postupnosťou typov segmentov. Tento popis je vhodný pre syntaktické rozpoznávanie.

 
Obr. 7.3  Segmenty hranice.

7.1.3 Popis vychádzajúci z oblasti objektu

   Jednoduchý objekt dokážeme ľahko popísať na základe jeho oblasti. Zložitejšie objekty najprv musíme rozdeliť na jednoduchšie časti, ktoré popíšeme samostatne. V takomto prípade objekt reprezentujeme rovinným grafom, ktorého vrcholy sú časti vzniknuté dekompozíciou pôvodného objektu. Objekt je teda popísaný vlastnosťami grafu a vlastnosťami vrcholov.

   Popis oblasti:

• Plocha oblasti, alebo veľkosť. Najjednoduchšia vlastnosť. Plocha oblasti je daná počtom obrazových elementov patriacich do oblasti.
• Eulerovo číslo, je topologickou vlastnosťou objektu, ktorá sa nemení s geometrickými transformáciami. Pre Eulerovo číslo platí:

                                                                                                    (1)

kde S e počet súvislých častí objektu a N je počet dier.

• Šírka a výška. Šírka resp. výška je maximálna hodnota horizontálnej resp. vertikálnej projekcie binárneho obrazu. Horizontálnu a vertikálnu projekciu definujeme ako:

                                                                                       (2)

                                                                                       (3)

• Excentricita, je pomer medzi maximálnou chrbticou A a maximálnou chrbticou kolmou na A (B).

 
Obr. 7.4  Excentricita a pozdĺžnosť.

• Pozdĺžnosť, je pomer medzi dĺžkou a šírkou opísaného pravouholníka s minimálnou plochou.
• Pravouhlosť. Nech F_k je pomer medzi plochou oblasti a plochou opísaného pravouholníka v smere k. Pravouhlosť je potom definovaná ako maximálna hodnota F_k.
• Smer, je to smer dlhšej strany minimálneho opísaného pravouholníka. O smeru má zmysel hovoriť pre pozdĺžne objekty.
• Kompaktnosť, je pomer medzi dĺžkou a plochou oblasti.
• Momenty. Momentový popis interpretuje jasovú funkciu obrazu ako hustotu pravdepodobnosti dvojrozmernej náhodnej veličiny.

Obecný moment je definovaný:

                                                               (4)

V diskrétnom prípade je moment definovaný ako:

                                                                   (5)

kde x,y a i,j sú súradnice bodov oblasti.

Centrálny moment je definovaný ako:

                                       (6)

a v diskrétnom prípade:

                                                     (7)

Centrálny moment je invariantný vzhľadom k posunutiu.

• Konvexný obal, je najmenší konvexný útvar obsahujúci celú oblasť.
• Kostra oblasti (skelet). Kostru oblasti tvoria všetky body, ktoré majú rovnakú minimálnu vzdialenosť od dvoch bodov hranice oblasti.

 
Obr. 7.5 Kostra oblasti.

7.2 Príznakové metódy rozpoznávania

     Príznakmi nazývame číselné popisy objektov a označujeme ich x₁, x₂, ..., x_n. Vektor príznakov X je n- rozmerný vektor a jeho súradnice sú jednotlivé príznaky. Množina všetkých vektorov príznakov vytvára príznakový priestor. Ak dobre zvolíme príznaky, potom podobnosť objektov je vyjadrená geometrickou blízkosťou príznakových vektorov v priestore príznakov. Priestor môžeme rozdeliť do k tried (w₁, ..., w_k). Tieto triedy sú oddelené nadplochami, ktoré určujeme diskriminačnými funkciami g₁(X), ..., g_n(X). Pre diskriminačné funkcie musí platiť pre každé X z w_r, že

                                                                     (8)

Potom oddeľujúca nadplocha medzi w_r a w_s má rovnicu

                                                                                                  (9)

   Triedy môžu byť:

• Separabilné
• Neseparabilné

Ak existuje nadplocha rozdeľujúca priestor príznakov na podpriestory, ktoré sa rovnajú triedam, potom hovoríme o probléme so separabilnými triedami. V opačnom prípade hovoríme o probléme s neseparabilnými triedami.

   Ako sme sa už v úvode dozvedeli, úlohu rozdeľovania objektov do tried vykonáva klasifikátor. Klasifikátor je zariadenie, ktoré má n vstupov a jeden výstup. Rozhoduje sa podľa rozhodovacieho pravidla d,

                                                                                                                  (10)

Klasifikátor zaradí objekt s príznakmi X do triedy w_r vtedy ak

                                                                (11)

Pre triedu w_r platí:

                                                                                           (12)

Klasifikátory rozdeľujeme na

• Lineárne
• Nelineárne

Lineárny klasifikátor pracuje s lineárnymi diskriminačnými funkciami, ktoré majú tvar:

                                       (13)

Nelineárny klasifikátor sa realizuje tak, že príznakový priestor zobrazíme vhodnou nelineárnou transformáciou F do nového príznakového priestoru v ktorom použijeme lineárny klasifikátor. Túto konštrukciu klasifikátoru nazývame F-prevodník. Diskriminačné funkcie F-prevodníka sú definované nasledovne:

                                    (14)

7.2.1 Kritérium minimálnej vzdialenosti  

   Táto metóda rozpoznávania predpokladá, že máme trénovaciu množinu, poznáme počet tried k a poznáme charakteristické prvky pre každú triedu, ktoré sa nazývajú etalonom triedy. Označme etalony jednotlivých tried v₁, v₂, ..., v_k. Rozhodovacie pravidlo zaradí vektor X do triedy r ak platí:

                                                                                   (15)

kde |.| je vzdialenosť.

 
Obr. 7.6 Klasifikácia na základe minimálnej vzdialenosti.

7.2.2 Kritérium minimálnej chyby

   V praxi často narazíme na problémy, keď nie sme schopní jednoznačne určiť, do ktorej triedy patrí vektor príznakov. Kritérium minimálnej chyby J(q) vyjadruje stratu z nesprávnej klasifikácie. Parametrizujme množinu pravidiel s parametrom q. Veľkosť J(q) potom závisí na použitom pravidle d(X,q)=w. Optimálne rozhodovacie pravidlo d(X,q^*)=w je také pravidlo, pri ktorom J(q) nadobudne minimum, teda

                                                                               (16)

7.2.3 Nastavenie klasifikátoru  

   Klasifikátor sa nastavuje učením. Učenie je proces optimalizácie systému, založený na postupnom predložení ukážkových príkladov. Cieľom učenia je minimalizovať chybnú klasifikáciu.

Existujú dva typy učenia:

• s učiteľom
• bez učiteľa

Proces učenia závisí aj od toho, aké informácie sú nám známe. Niekedy máme k dispozícii konečnú množinu objektov, pričom poznáme ich príslušnosť k triedam. Takáto množina sa nazýva trénovacia množina. Cieľom je nastaviť klasifikátor tak, aby bol optimálny pre celý príznakový priestor. Presnosť klasifikátoru priamo súvisí s veľkosťou trénovacej množiny. Inokedy máme len vstupnú množinu bez znalosti príslušnosti  k triedam. V takýchto prípadoch sa využívajú metódy zhlukovej analýzy.

7.2.4 Zhluková analýza  

   Zhluková analýza zahŕňa metódy rozpoznávania, ktoré nepotrebujú učiteľa, ani apriórne informácie o probléme. Ich vstupom je konečná množina príznakov, ktorá obsahuje neklasifikované prvky. Cieľom je nájsť vektory, ktoré sú vzájomne blízke. Metódy zhlukovej analýzy delia vstupnú množinu na podmnožiny, zhluky na základe blízkosti príznakových vektorov v priestore. Tieto zhluky potom vytvárajú jednotlivé triedy rozpoznávania.

   Metódy zhlukovej analýzy delíme na:

·        Hierarchické metódy

·        Nehierarchické metódy

Nehierarchické metódy na začiatku odhadnú počet tried a následne vypočítavajú zhluky. Ako príklad uvedieme MacQueenovu metódu:

1)      Určíme počet tried k, ako k bodov v priestore príznakov. To môžeme spraviť náhodným výberom zo vstupnej množiny. Tieto body budú začiatočné ťažiská tried.

2)      Postupne priradíme body zo vstupnej množiny do zhlukov, podľa najmenšej vzdialenosti k ťažiskám zhlukov. Vždy, keď je do zhluku priradený nový bod, prepočítame jeho ťažisko.

3)      Ťažiska zhlukov vypočítané v druhom kroku považujeme za výsledné. Ďalešie body priraďujeme podľa kritéria minimálnej vzdialenosti.

Metódy hierarchického zhlukovania sa ďalej delia na:

• Zhlukovanie zhora nadol. Vstupnú množinu rozdelíme na dve navzájom najmenej podobné množiny a každú z nich opäť rozdelíme.
• Zhlukovanie zdola nahor. Body vstupnej množiny pospájame do skupín podľa vzdialenosti, až kým nedosiahneme požadovaný počet množín.  

 
Simulácia metódy MacQueen.

7.3 Štrukturálne rozpoznávanie

   Metódy štrukturálneho rozpoznávania využívajú kvalitatívny charakter objektov. Syntaktický popis je používaný vtedy, keď príznakovým popisom nie sme schopný zachytiť všetky charakteristiky objektu. Elementárne vlastnosti štrukturálne popísaných objektov sa nazývajú primitíva. Tieto primitíva by mali byť ľahko segmentovatelné z obrazu a mali by odpovedať výrazným elementom spracovaného obrazu. Každé primitívum označíme symbolom a vzájomné vzťahy medzi primitívami popíšeme reláciami. Takto získame popis objektov relačnou štruktúrou. Túto konštrukciu vieme zapísať pomocou formálnych jazykov a automatov.

Množina všetkých primitív sa nazýva abeceda. Slovo nad abecedou je popis charakterizujúci objekt. Množina slov vytvára jazyk. Jazyk popisuje jednu triedu. Relačné vzťahy medzi primitívami sú zachytené gramatikou. Gramatika je množina pravidiel pomocou ktorých môžeme odvodiť slová z daného jazyka.

   Štrukturálne rozpoznávanie sa skladá z nasledujúcich krokov:

1)      Analýzou úlohy určíme množinu primitív a relácie medzi nimi.

2)      Vytvoríme gramatiky reprezentujúce jednotlivé triedy.

3)      Pri rozpoznávaní popíšeme objekt slovom nad abecedou a určíme, ktorou gramatikou ho vieme odvodiť.

4)      Objekt zaradíme do tej triedy, ktorej gramatika dané slovo vygenerovala.

Kroky (1) a (2) predstavujú fázu učenia a kroky (3) a (4) tvoria fázu rozpoznávania, pričom krok (3) nazývame syntaktickou analýzou.

7.3.1 Gramatiky a jazyky  

   Ako sme už spomínali, primitíva a vzťahy medzi nimi sa dajú zapísať formálnymi jazykmi. Terminálne symboly sú písmená – primitíva. Abeceda je množina symbolov. Množina slov nad abecedou vytvára formálny jazyk, ktorý je popísaný gramatikou.

Gramatika je štvorica G=(N,T,P,S), kde N a T sú disjunktné abecedy, N je množina neterminálnych symbolov, T je množina terminálov, S je počiatočný symbol – axióm a P je konečná množina pravidiel.

Jazyk generovaný gramatikou G je L(G)

                                                                                      (17)

Krok odvodenia v gramatike G je relácia Þ na (NÈT)^*.

Gramatiky delíme na

• Regulárne gramatiky, pre ich množinu pravidiel platí:

• Bezkontextové gramatiky

• Kontextové gramatiky. Kontextová gramatika je frázová gramatika, v ktorej pre každé pravidlo platí:

• Frázové gramatiky

Príklad:

 
Obr. 7.7 Generovanie štvoruholníkov.

Terminálne symboly:   {0, 1, 2, 3 }

Neterminálne symboly:   {S, a, b, c, d }

Pravidlá:

Pričom A, B, C, D sú reťazce ľubovoľnej dĺžky skladajúce sa z terminálnych symbolov.

Príklad odvodenia slova:

7.3.2 Fáza učenia  

Táto časť štrukturálneho rozpoznávania vo veľkej miere závisí od schopnosti programátora, ktorý musí určiť primitíva a relácie medzi nimi na základe zadania problému a množiny vzorových obrazov. Potom nasleduje určenie gramatiky pre jednotlivé triedy na základe vzorových slov. Toto sa nazýva inferencia gramatiky. Vstupom algoritmu inferencie gramatiky sú slová z jazyka – vzorové slová a slová nepatriace do jazyka, ktoré musí určiť učiteľ. Od inferenčného algoritmu očakávame, že vytvorí gramatiku, ktorá generuje vzorovú množinu a ďalšie slová, ktoré majú podobnú štruktúru ako vzorové. Tento problém je veľmi zložitý. Všeobecné algoritmy existujú len pre bezkontextové a regulárne gramatiky.

7.3.3 Syntaktická analýza  

   Úlohou klasifikátoru je rozhodnúť sa, že do ktorého gramatikou generovaného jazyka patrí skúmané slovo. Ako prvý krok môže klasifikátor overiť, či slovo je nad abecedou terminálnych slov gramatiky. Týmto spôsobom môžeme redukovať počet gramatík, ktoré treba otestovať.

Na zistenie príslušnosti slova do jazyku máme nasledujúce možnosti:

• Výpočty zhora nadol, tieto metódy sa snažia odvodiť slovo od počiatočného symbolu až k terminálnemu slovu pomocou pravidiel gramatiky. Prehľadávajú strom odvodenia od koreňa až po listy.
• Výpočty zdola nahor, tieto metódy sa snažia spätnou substitúciou odvodzovacích pravidiel určiť či slovo patrí do jazyka. V slove sa hľadajú časti, ktoré tvoria pravú stranu nejakého pravidla, ktoré sa nahradia ľavou stranou. Cieľom je dosiahnuť počiatočný symbol.