img132

132

9. Wprowadzenie do syntaktycznego rozpoznawania obrazów

Rys. 9.11. Opis strukturalny scen z rys. 9.10 za pomocą grafów pozwala na wydobycie cech, które je różnią

parser) odpowiada procedurze rozpoznającej F jednym z dwóch następujących sposobów.

Niech zbiór obiektów D rozbija się na kolekcję L klas równoważności {£>' | i = 1, ... L] nazywanych - jak wszędzie dotychczas - obrazami. Zdefiniujmy zbiór stanów końcowych automatu (patrz Dodatek 3) - Fa = {/i, • ■ • ,/z,,err} tak, że dla każdego obiektu d G D\ automat po przeanalizowaniu reprezentacji z obiektu d przejdzie w stan Tak więc rozpoznanie i G / obiektu d G D będzie w tym przypadku ustalane na podstawie identyfikacji stanu końcowego automatu 21. Brak decyzji i„ odpowiada w automacie 21 stanowi błędu err.

Drugim sposobem jest konstrukcja automatu z wyjściem 2t„, (patrz definicja automatu LL{ 1) w Dodatku 3). Automat taki, dokonując analizy reprezentacji x obiektu d, wypisuje w kolejnych krokach numery tych produkcji ip gramatyki 0, których należałoby użyć, aby wygenerować reprezentację x. Zbiór stanów końcowych automatu jest w tym przypadku dwuelementowy F = {occ,err}, gdzie acc oznacza stan akceptacji przeanalizowanej reprezentacji (w sensie jej przynależności do języka rozpoznawalnego przez automat 2l_w), czyli stan rozpoznania obiektu d, natomiast err oznacza (jak poprzednio) brak decyzji. Identyfikacji i G I odpowiedniej klasy D' dokonujemy, przy tym podejściu, na podstawie otrzymanego na wyjściu ciągu numerów {/z,} produkcji p^ G V (z każdą klasą i G I związany jest zbiór ciągów numerów {/z;} produkcji ip gramatyki 0).

Podsumowując, główną ideą syntaktycznego rozpoznawania obrazów jest reprezentowanie obiektu d G D przez ciąg (sznur), drzewo lub graf