A New Graph Grammar Formalism for Robust Syntactic Pattern Recognition
This addresses the challenge of recognizing structured patterns in noisy or variable data for applications in fields like computer vision or image analysis, though it appears incremental as it builds on existing graph grammar concepts.
The paper tackles the problem of robust syntactic pattern recognition by introducing a new graph grammar formalism that avoids production rules and represents syntax directly as networks, enabling error-tolerant parsing of complex patterns with 50-1000 symbols under conditions like blurriness and clutter.
I introduce a formalism for representing the syntax of recursively structured graph-like patterns. It does not use production rules, like a conventional graph grammar, but represents the syntactic structure in a more direct and declarative way. The grammar and the pattern are both represented as networks, and parsing is seen as the construction of a homomorphism from the pattern to the grammar. The grammars can represent iterative, hierarchical and nested recursive structure in more than one dimension. This supports a highly parallel style of parsing, in which all aspects of pattern recognition (feature detection, segmentation, parsing, filling in missing symbols, top-down and bottom-up inference) are integrated into a single process, to exploit the synergy between them. The emphasis of this paper is on underlying theoretical issues, but I also give some example runs to illustrate the error-tolerant parsing of complex recursively structured patterns of 50-1000 symbols, involving variability in geometric relationships, blurry and indistinct symbols, overlapping symbols, cluttered images, and erased patches.