EDT

EDT, Drzewa EDT (Edge-labelled Directed Tree) drzewa o zaetykietowanych i skierowanych krawędziach. To jedna z metod rozpoznawania obrazów oparta na bazie metod drzewowych. Gramatykę drzew EDT stanowi piątka:

$B_{EDT}=(\Sigma, r, \Gamma, \beta, Z)$

gdzie:

$\beta$ jest zbiorem produkcji np. $A\rightarrow b(vDtB)$

$\Sigma =\Sigma_{T} \bigcup \Sigma_{N}$ $\Sigma_{T}$-zbriór etykiet krawędziowych, $\Sigma_{N}$-Unknown

$\Gamma$-zbiór etykiet krawędziowych

Z-Unknown

Przykładowa generacja sceny wygląda następująco:

A-(i)$\rightarrow$b(cDtB)-(2)$\rightarrow$b(vdtB)-(4)$\rightarrow$b(vdta(vD))-(2)$\rightarrow$(2)$\rightarrow$b(vdta(vd))

Automat $\Lambda_{DFEDT}$ rozpoznający sceny w gramatyce $B_{EDT}$ zbudowany jest następująco:

$\Lambda_{DFEDT}=(Q,\delta_{1} ,...,\delta_{n} ,f)$

gdzie:

Q:=$\Sigma - \Sigma_{T}$

F-Unknown

$\delta_{a} (r_{1} A_{1} ,...,r_{r(a)} A_{r(a)} )=(A,i)$ - funkcje przejścia

Rozpoznanie powyższej sceny będzie wyglądać następująco:

(rp(b(vdta(vd))),α)$\rightarrow$($\delta_{b}$(vrp(d),trp(a(vd))),α)$\rightarrow$ ($\delta_{b}$(v$\delta_{d}$,t$\delta_{a}$(rp(vd))),α)$\rightarrow$($\delta_{b}$(v$\delta_{d}$,t$\delta_{a}$(vrp(d))),α)$\rightarrow$($\delta_{b}$(v$\delta_{d}$,t$\delta_{a}$(v$\delta_{d}$)),α)$\rightarrow$($\delta_{b}$(v$\delta_{d}$,t$\delta_{a}$(vD)),2)$\rightarrow$($\delta_{b}$(v$\delta_{d}$,tB),24)$\rightarrow$($\delta_{b}$(vD,tB),242)$\rightarrow$(A,2421)