Image interpretation using multi-relational grammars

An approach to computational vision that is based on multiple levels of interpretation is presented. The step between each level is seen as taking place in three stages-parsing (in which features and groups of features in an image are given labels), interpreting (in which several interpretations are built, assuring that each feature is given at most one explanation in terms of a higher-level label), and pruning (in which some interpretations are discarded because of global constraints). The parsing and pruning steps are guided by multirelational grammars, a generalization of ordinary attribute grammars and of graph grammars. A bottom-up parsing algorithm for this class of grammars is presented, and their usefulness in image interpretation is illustrated by examples using both synthetic and real-world data