Networks of constraints: fundamental properties and applications to picture processing

Networks of constraints: fundamental properties and applications to picture processing

January, 1971 | Ugo Montanari
This paper discusses the representation and handling of constraints in picture processing. The author proposes a systematic approach to represent and utilize constraints, which can significantly reduce the search space in picture recognition. Constraints are represented as binary relations and can be combined to form networks of simultaneous binary relations. A minimal equivalent network is shown to exist, which can be used to solve practical problems related to constraint handling. However, an exact solution for this central problem is not found. Instead, 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 proved exact in special cases, such as for tree-like and series-parallel networks and for classes of relations where a distributive property holds. The paper also discusses the approximation of the central problem using closed networks, which are equivalent to the original network and can be solved using an iterative algorithm. The paper concludes with a theorem proving the uniqueness of the closure of a network and provides an algorithm for computing the closure of a network.This paper discusses the representation and handling of constraints in picture processing. The author proposes a systematic approach to represent and utilize constraints, which can significantly reduce the search space in picture recognition. Constraints are represented as binary relations and can be combined to form networks of simultaneous binary relations. A minimal equivalent network is shown to exist, which can be used to solve practical problems related to constraint handling. However, an exact solution for this central problem is not found. Instead, 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 proved exact in special cases, such as for tree-like and series-parallel networks and for classes of relations where a distributive property holds. The paper also discusses the approximation of the central problem using closed networks, which are equivalent to the original network and can be solved using an iterative algorithm. The paper concludes with a theorem proving the uniqueness of the closure of a network and provides an algorithm for computing the closure of a network.
Reach us at info@study.space