Msys: A System For Reasoning About Scenes

Abstract

MSYS is a system for reasoning with uncertain information and inexact rules of inference. Its major application, to date, has been to the interpretation of visual features (such as regions) in scene analysis. In this application, features are assigned sets of possible interpretations with associated likelihoods based on local attributes (e.g., color, size, and shape). Interpretations are related by rules of inference that adjust the likelihoods up or down in accordance with interpretation likelihoods of related features. An asynchronous relaxation process repeatedly applies the rules until a consistent set of likelihood values is attained. At this point, several alternative interpretations still exist for each feature. One feature is chosen and the most likely of its alternatives is assumed. the rules are then used in this more precise context to determine likelihoods for the interpretations of remaining features by a further round of relaxation. The selection and relaxation steps are repeated until all features have been interpreted. Some interpretation typifies constraint optimization problems involving the assignment of values to a set of mutually constrained variables. For an interesting class of constraints, MSYS is guaranteed to find the optimal solution with less branching than conventional heuristic search methods. MSYS is implemented as a network of asynchronous parallel processes. The implementation provides an effective way of using data driven systems with distributed control for optimal stochastic search.