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 a3 d3 dt a5 2 3 10 0
f1) Pojęcia z teorii gramatyk grafowych używane w tym rozdziale zostały formalnie zdefiniowane w Dodatku 4.
Wyszukiwarka
Podobne podstrony:
img164 12. METODY GRAFOWE Jak wspomniano w rozdziale 9, gramatyki grafowe są mocniejszym narzędziem
img172 172 12. Metody grafowe12.2. Parsing dla gramatyki grafowej klasy ETL() Metodę tą zilustrujemy
img172 172 12. Metody grafowe12.2. Parsing dla gramatyki grafowej klasy ETL() Metodę tą zilustrujemy
img170 170 12. Metody grafowe i wtedy dopiero na zwolnionych wcześniejszych miejscach wektora tt zap
img176 176 12. Metody grafowe Rozważmy teraz następujący problem związany z analizą języków generowa
img166 166 12. Metody grafoweE = {a,M}, T = {r,t,p,ti,s},$}:(1) S->btDrA , (2)
img170 170 12. Metody grafowe i wtedy dopiero na zwolnionych wcześniejszych miejscach wektora tt zap
img174 174 12. Metody grafowe Zbiór produkcji tp, którego lewe i prawe strony są p
img176 176 12. Metody grafowe Rozważmy teraz następujący problem związany z analizą języków generowa
img178 178 12. Metody grafowe Wierzchołki ij, j = 1,,p nazywamy wierzchołkami potencjalnie konteksto
img180 180 12. Metody grafowe rzędu 0(n2). Jakkolwiek obie metody zostały zdefiniowane dla potrzeb a
321 (25) 524 Jak wspomniano w rozdziale XII.11, w stopniu regulacyjnym luk zasilania jest zmienny za
img174 174 12. Metody grafowe Zbiór produkcji tp, którego lewe i prawe strony są p
16 2.2. Algorytmy detekcji artefaktów2.2. Algorytmy detekcji artefaktów Jak wspomniano w rozdziale 2
skanuj0007 42 2.5. Metoda klasyczna Jak już wspomniano w rozdziale 2.1, przedmiotem rozważań są stan
więcej podobnych podstron