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:

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

gdzie:

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

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

$\Sigma _{T}$ – zbió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) $\to$ b(cDtB)-(2) $\to$ b(vdtB)-(4) $\to$ b(vdta(vD))-(2) $\to$ (2) $\to$ b(vdta(vd)).

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

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

gdzie:

$Q:=\Sigma -\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