Michael J. Swain

IJCAI Conference 1995 Conference Paper

An Architecture for Vision and Action

• R. James Firby
• Roger E. Kahn
• Peter N. Prokopowicz
• Michael J. Swain

Vision systems that have successfully supported nontrivial tasks have invariably taken advantage of constraints derived from the task and environment to increase reliability and lower the complexity of perception. We propose that it is possible to build a general purpose vision system, that is, one that can support a wide variety of tasks, and take advantage of such constraints. The central idea within our proposed architecture is the reactive skill. Skills are concurrent control routines assembled at run time using instructions from a symbolic execution system. Visual modules are used as resources in the construction of these skills. Skills control the agent as continuous feedback loops but are constructed using discrete, symbolic instructions. The key to general-purpose vision is the ability to parametrize the primitive elements of the vision system and to compose visual and control routines in a variety of ways. We demonstrate the architecture in the context of an implemented example task of a robot collecting trash off a floor and depositing it in a garbage can.

AIJ Journal 1992 Journal Article

Arc consistency: parallelism and domain dependence

• Paul R. Cooper
• Michael J. Swain

This paper discusses how better arc consistency algorithms for constraint satisfaction can be developed by exploiting parallelism and domain-specific problem characteristics. A massively parallel algorithm for arc consistency is given, expressed as a digital circuit. For a constraint satisfaction problem with n variables and a labels, this algorithm has a worst-case time complexity of O(na), significantly better than that of the optimal uniprocessor algorithm. An algorithm of intermediate parallelism suitable for implementation on a SIMD machine is also given. Analyses and implementation experiments are shown for both algorithms. A method for exploiting characteristics of a problem domain to achieve arc consistency algorithms with better time and space complexity is also discussed. A general technique for expressing domain knowledge and using it to develop optimized arc consistency algorithms is described. The domain-specific optimizations can be applied analogously to any of the arc consistency algorithms along the sequential/parallel spectrum.

IJCAI Conference 1989 Conference Paper

Domain Dependence in Parallel Constraint Satisfaction

• Paul R. Cooper
• Michael J. Swain

We describe a general technique for expressing domain knowledge in constraint satisfaction problems, and using it to develop optimized parallel arc consistency algorithms for the solution of problems in the domain. The technique is applied to reduce the space complexity of the the massively parallel AC Chip algorithm. Results of the optimizations are shown for an object recognition domain in which they reduce the complexity of the chip by many orders of magnitude. The technique can be applied analogously to reduce the time complexity of the uniprocessor arc consistency algorithm AC-4.

UAI Conference 1989 Conference Paper

Efficient Parallel Estimation for Markov Random Fields

• Michael J. Swain
• Lambert E. Wixson
• Paul B. Chou

We present a new, deterministic, distributed MAP estimation algorithm for Markov Random Fields called Local Highest Confidence First (Local HCF). The algorithm has been applied to segmentation problems in computer vision and its performance compared with stochastic algorithms. The experiments show that Local HCF finds better estimates than stochastic algorithms with much less computation.

AAAI Conference 1988 Conference Paper

Parallel Hardware for Constraint Satisfaction

• Michael J. Swain

A parallel implementation of constraint satisfaction by arc consistency is presented. The implementation is constructed of standard digital hardware elements, used in a very fine-grained, massively parallel style. As an example of how to specialize the design, a parallel implementation for solving graph isomorphism with arc consistency is also given. Complexity analyses are given for both circuits. Worst case running time for the algorithms turns out to be linear in the number of variables n and labels a, O(an), and if the I/O must be serial, it will dominate the computation time. Finegrained parallelism trades off time complexity for space complexity, but the number of gates required is only O(a2n2).

ICRA Conference 1986 Conference Paper

Experiments in using a theorem prover to prove and develop geometrical theorems in computer vision

• Michael J. Swain
• Joseph L. Mundy

A geometrical theorem prover based on algebraic techniques has been used to prove and derive theorems in computer vision. The results show that theorems relevant to persepective viewing and the properties of shadows can be proven, including some which contain inequalities. Deriving theorems by stating incomplete hypotheses and letting the prover suggest the missing constraints can provide valuable new insights into vision probiems. However, there is no guarantee that the suggestions made by the proof algorithm are interpretable in terms of primitive geometric concepts.

IJCAI Conference 1985 Conference Paper

Shape from Texture

• John Aliomonos
• Michael J. Swain