Exploring Syntactic Methods for Spatial and Semantic Analysis of Node‐Link Diagram Images

Diagram image interpretation involves analyzing images of visual representations to extract meaningful information. Since the visual arrangement of diagram elements infers certain semantic concepts specific to a domain, a complete interpretation requires using domain knowledge. Subsequently, a diagram interpretation system must handle the construction of meaning based on this knowledge. Literature from the graphics recognition field suggests grammars from the visual language theory field are useful for encoding domain knowledge and also for the spatial parsing of diagram images. However, previous works failed to suggest - with appraisal - appropriate grammar formalism for a diagram interpretation problem. By examining various characteristics of potential grammar formalisms, we established that Constraint Multiset Grammars (CMG) have sufficient features for handling the diagram analysis task and for constructing meaning from extracted diagram elements according to notational conventions. We also show the requirements of the interpretation task for node-link diagram images; in particular the spatial and semantic analysis stages, and highlight how CMG suffice for handling them.