Środowisko agentowe w syntaktycznym rozpoznawaniu obrazów

Abstract

A computational complexity of parsing is the major limitation of syntactic pattern recognition methods applicability. That complexity may be decreased only by using grammars having weaker expressive power. ETPL(k) graph grammars, having quadratic complexity, are a compromise between complexity and descriptive power. For problems having large sizes however it's necessary to parallelize computations by distributing them over a multiagent system. Effectiveness of a system may be additionally boosted by even knowledge distribution enabling a balanced workload of agents. The knowledge consists of given subgraphs and grammar productions.

Czynnikiem istotnie ograniczającym praktyczne zastosowanie metod syntaktycznych w zadaniach rozpoznawania obrazu jest złożoność obliczeniowa parsingu, którą można obniżyć tylko kosztem siły opisowej języka. Gramatyki klasy ETPL(k), posiadające złożoność $O(N^2)$, stanowią sprawdzony formalizm dla zadań rozpoznawania obrazu. W przypadku zadań o dużym rozmiarze istotna jest także możliwość zrównoleglenia obliczeń i rozproszenie ich w środowisku agentowym. Wiedzę agenta stanowi wówczas zarówno znajomość fragmentu struktury grafowej, jak i produkcji gramatyki. Równomierna inicjalna dystrybucja tej wiedzy w systemie agentowym pozwala dodatkowo poprawić efektywność systemu.