Church-Rosser Picture Languages and Their Applications in Picture Recognition
Hartmut Messerschmidt, Martin Stommel · Universitätsbibliothek Gießen · 2011
In image processing, there is a need for efficient methods that complement statistical models by structural information about the spatial scene arrangement and compositional hierarchy. In order to recognise the structure of locally detected features, we propose a two-dimensional Church-Rosser picture language that facilitates the evaluation of local information compared to one-dimensional languages. Although Church-Rosser languages are able to represent certain types of context-sensitivity, the word problem is solvable in linear time. We describe how the concept of local replacements used in rewriting systems and restarting automata, helps in pattern and picture recognition. It is shown that the Church-Rosser picture language can be recognised by a deterministic shrinking two-dimensional restarting automaton. The practical application of the Church-Rosser picture language in object recognition is illustrated.