img164

12. METODY GRAFOWE

Jak wspomniano w rozdziale 9, gramatyki grafowe są mocniejszym narzędziem opisu obrazów, niż gramatyki ciągowe lub drzewowe. Dlatego też, użycie grafów do opisu dwu- lub trójwymiarowych obrazów jest powszechnie spotykane w literaturze [34], Natomiast wykorzystanie ich do rozpoznawania obrazów nie jest tak powszechne. Spowodowane jest to trudnościami związanymi z analizą syntaktyczną gramatyk grafowych, dokładniej mówiąc, ze złożonością obliczeniową problemu analizy syntaktycznej, który dla zdecydowanej większości klas gramatyk jest NP-zupełny [34].

W rozdziale przedstawimy dwie, znane z literatury, syntaktyczne metody grafowe rozpoznawania obrazów: metodę parsingu ekspansywnych języków grafowych [35] oraz metodę parsingu dla gramatyki grafowej klasy ETL( 1) [36,37],

12.1. Parsing ekspansywnych języków grafowych

Przyjmijmy, że zbiory składowych pierwotnych reprezentujących obiekty scen i relacje pomiędzy obiektami są zilustrowane rysunkiem 11.la. Rozważmy dwie sceny znajdujące się na rysunku 12.1. Sceny te możemy reprezentować w jednoznaczny sposób przez grafy klasy fl('). Zapiszmy oba grafy fi za pomocą ich opisów charakterystycznych.

I scena: 6i a₃ d₃ d_t a₅ 2    3    10    0

tr    tsp    r —    -

25    345    4    -    -

f¹) Pojęcia z teorii gramatyk grafowych używane w tym rozdziale zostały formalnie zdefiniowane w Dodatku 4.