img155

11. METODY DRZEWOWE

Metody drzewowe rozpoznawania obrazów są konstruowane na bazie teorii języków drzewowych i automatów drzewowych. Teoria ta, będąca działem lingwistyki matematycznej, doczekała się wielu publikacji, a nawet opracowań monograficznych (przegląd tych prac Czytelnik może znaleźć w [19]). Automaty rozważane w teorii automatów drzewowych są bardziej skomplikowane niż automaty ciągowe (co jest rzeczą naturalną, zważywszy, że drzewo jest bardziej złożoną strukturą niż ciąg). W zastosowaniach do rozpoznawania obrazów używany jest najprostszy typ automatu drzewowego - deterministyczny automat czytający drzewo od brzegu (liści) do korzenia (ang. deterministic frontier-lo-root tret recognizer), czyli automat 21 df [30], który określany jest dla ekspansywnej gramatyki drzewowej [29].

W rozdziale przedstawimy dwie metody rozpoznawania oparte na wspomnianym automacie 2l_d. Pierwsza z nich jest metodą analizy syntaktycznej drzew o zaetykietowanych i skierowanych krawędziach, czyli drzew EDT (ang. Edge-labelled Direcłed Tret). Druga - to metoda analizy syntaktycznej drzew prostych, tzn. takich, których krawędzie nie są zaetykietowane ani skierowane, czyli drzew T. Metoda pierwsza może być wykorzystana do analizy sceny [32], druga - do analizy faktur [33] (oba problemy zostały zdefiniowane w rozdziale 9)(*).

11.1. Analiza syntaktyczna drzew EDT

Rozważmy trzy obrazy (sceny) znajdujące się na rysunku 11.1. Przyjmując zbiory składowych pierwotnych reprezentujących: obiekty scen i relacje pomiędzy obiektami jak na rysunku 1 l.la, możemy utworzyć reprezentacje

(¹) Definicje formalne: ekspansywnych gramatyk drzewowych i automatów DF znajdują sią w Dodatku 4.