EDT

Drzewa EDT w rozpoznawaniu obrazów

Drzewa EDT to struktury z zaetykietowanymi i skierowanymi krawędziami, wykorzystywane w metodach rozpoznawania obrazów. Ich system oparty jest na pięciu elementach, które tworzą gramatykę drzew EDT, oznaczoną jako $B\_\{EDT\}\; =\; (\backslash Sigma,\; r,\; \backslash Gamma,\; \backslash beta,\; Z)$.

Elementy gramatyki drzew EDT

Gramatyka składa się z następujących komponentów:

• $\backslash Sigma$ – zbiór etykiet krawędziowych, dzielący się na:
• $\backslash Sigma\_T$ – zbiór etykiet krawędziowych (terminalnych),
• $\backslash Sigma\_N$ – zbiór etykiet nieznanych.
• $\backslash beta$ – zbiór produkcji, na przykład $A\; \backslash to\; b(vDtB)$,
• $\backslash Gamma$ – zbiór etykiet krawędziowych,
• $Z$ – element nieznany.

Przykład generacji sceny

Proces generacji sceny w drzewach EDT można zobrazować przykładem:

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

Automat rozpoznający sceny

Automat rozpoznawania scen w gramatyce $B\_\{EDT\}$, oznaczony jako $\backslash Lambda\_\{DFEDT\}$, definiowany jest jako:

$\backslash Lambda\_\{DFEDT\}\; =\; (Q,\; \backslash delta\_1,\; \backslash dots,\; \backslash delta\_n,\; f),$
gdzie:

• $Q\; :=\; \backslash Sigma\; –\; \backslash Sigma\_T$ – zbiór stanów,
• $F$ – element nieznany,
• $\backslash delta\_a(r\_1\; A\_1,\; \backslash dots,\; r\_\{r(a)\}\; A\_\{r(a)\})\; =\; (A,\; i)$ – funkcje przejścia.

Proces rozpoznawania sceny

Rozpoznawanie sceny przy użyciu automatu wygląda następująco:

$(rp(b(vdta(vd))),\; \backslash alpha)\; \backslash to\; (\backslash delta\_b(vrp(d),\; trp(a(vd))),\; \backslash alpha)\; \backslash to\; \dots \; \backslash to\; (A,\; 2421).$

W powyższym ciągu następuje seria przejść, które prowadzą do końcowego rozpoznania stanu.