Reasoning in the presence of uncertainty via graph rewriting
Dorothea Blostein, Hoda Fahmy · 1995
In image analysis, low-level recognition of the primitives plays a very important role. Once the primitives of the image are recognized, depending on the application, many types of analyses can take place. It is unrealistic to assume that a low-level recognition process correctly identifies each primitive in an image. It is more likely that the output of a low-level recognition process is ambiguous in that each primitive is associated with a set of possible interpretations. Often, the ambiguity can be reduced by examining the context and satisfying the constraints associated with the application domain. This process is referred to as constraint satisfaction, labelling or discrete relaxation. Existing methods for such a process generally assume that which primitives constrain one another is known a priori. This thesis develops a graph-rewriting approach which does not make this assumption and applies it to the recognition of music notation; the result is MUBEENA, a graph-rewriting scheme consisting of approximately 180 rules. The graph-rewriting rules are used to express not only binary constraints, but also higher-order notational constraints. The proposed approach offers the flexibility to describe the primitives at different levels of abstraction which is also necessary to further reduce ambiguity.