
Accession Number : AD0718994
Title : Networks of Constraints: Fundamental Properties and Applications to Picture Processing,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Montanari,Ugo
Report Date : JAN 1971
Pagination or Media Count : 57
Abstract : The problem of representation and handling of constraints is here considered, mainly for picture processing purposes. A systematic specification and utilization of the available constraints could significantly reduce the amount of search in picture recognition. On the other hand, formally stated constraints can be embedded in the syntactic productions of picture languages. Only binary constraints are treated here, but they are represented in full generality as binary relations. Constraints among more than two variables are then represented as networks of simultaneous binary relations. In general, more than one equivalent (i.e., representing the same constraint) network can be found: a minimal equivalent network is shown to exist, and its computation is shown to solve most practical problems about constraint handling. No exact solution for this central problem was found. Anyway, constraints are treated algebraically, and the solution of a system of linear equations in this algebra provides an approximation of the minimal network. This solution is then proved exact in special cases, e.g., for treelike and series parallel networks and for classes of relations for which a distributive property holds. This latter condition is satisfied in cases of practical interest. (Author)
Descriptors : (*COMPUTER PROGRAMMING, *PATTERN RECOGNITION), MATHEMATICAL MODELS, DATA PROCESSING, COMPUTER LOGIC, BINARY ARITHMETIC, ALGORITHMS, GRAPHICS, THEOREMS
Subject Categories : Computer Programming and Software
Computer Hardware
Bionics
Distribution Statement : APPROVED FOR PUBLIC RELEASE