EDT

EDT, drzewa EDT (ang. 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:

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

gdzie:

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

${\displaystyle \Sigma =\Sigma _{T}\bigcup \Sigma _{N},}$

${\displaystyle \Sigma _{T}}$ – zbiór etykiet krawędziowych,

${\displaystyle \Sigma _{N}}$ – Unknown,

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

${\displaystyle Z}$ – Unknown.

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

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

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

${\displaystyle \Lambda _{DFEDT}=(Q,\delta _{1},\dots ,\delta _{n},f),}$

gdzie:

${\displaystyle Q:=\Sigma -\Sigma _{T},}$

${\displaystyle F}$ – Unknown,

${\displaystyle \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))),α) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(vrp(d),trp(a(vd))),α) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(v${\displaystyle \delta _{d},}$t${\displaystyle \delta _{a}}$(rp(vd))),α) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(v${\displaystyle \delta _{d},}$t${\displaystyle \delta _{a}}$(vrp(d))),α) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(v${\displaystyle \delta _{d},}$t${\displaystyle \delta _{a}}$(v${\displaystyle \delta _{d}}$)),α) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(v${\displaystyle \delta _{d},}$t${\displaystyle \delta _{a}}$(vD)),2) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(v${\displaystyle \delta _{d},}$tB),24) ${\displaystyle \to }$ (${\displaystyle \delta _{b}}$(vD,tB),242) ${\displaystyle \to }$ (A,2421).

• Edt