EDT

EDT, drzewa EDT (Szablon:Ang.) – 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}=(\mathrm{\Sigma },r,\mathrm{\Gamma },\beta ,Z),$

gdzie:

$\beta$ – zbiór produkcji, np. $A\to b(vDtB),$

$\mathrm{\Sigma }={\mathrm{\Sigma }}_T\bigcup {\mathrm{\Sigma }}_N,$

${\mathrm{\Sigma }}_T$ – zbiór etykiet krawędziowych,

${\mathrm{\Sigma }}_N$ – Unknown,

$\mathrm{\Gamma }$ – zbiór etykiet krawędziowych,

$Z$ – Unknown.

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

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

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

${\mathrm{\Lambda }}_{DFEDT}=(Q,{\delta }_1,\dots ,{\delta }_n,f),$

gdzie:

$Q:=\mathrm{\Sigma }-{\mathrm{\Sigma }}_T,$

$F$ – Unknown,

${\delta }_a(r_1{A}_1,\dots ,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))),α) $\to$ (${\delta }_b$(vrp(d),trp(a(vd))),α) $\to$ (${\delta }_b$(v${\delta }_d,$t${\delta }_a$(rp(vd))),α) $\to$ (${\delta }_b$(v${\delta }_d,$t${\delta }_a$(vrp(d))),α) $\to$ (${\delta }_b$(v${\delta }_d,$t${\delta }_a$(v${\delta }_d$)),α) $\to$ (${\delta }_b$(v${\delta }_d,$t${\delta }_a$(vD)),2) $\to$ (${\delta }_b$(v${\delta }_d,$tB),24) $\to$ (${\delta }_b$(vD,tB),242) $\to$ (A,2421).

Zobacz też

• Edt