Ph.D. thesis available

[swain@cs.rochester.edu]

The following Ph.D. thesis now available:

	PARALLEL OBJECT RECOGNITION FROM STRUCTURE
		(THE TINKERTOY PROJECT)

	Paul R. Cooper
	Department of Computer Science
	University of Rochester

        Technical Report 301
	July 1989

Abstract:

This thesis examines the problem of recognizing structurally composed
objects. The task is the recognition of Tinkertoys --- objects whose
identity is defined solely by the spatial relationships between simple
parts. Ultimately, a massively parallel framework incorporating a
principled treatment of uncertainty and domain dependence is developed
to address the problem. 

The basic architecture of the solution is formed by posing structure
matching as a part-wise correspondence problem in a
labelling framework, then applying the unit/value principle.
The solution is developed incrementally. Complexity and correctness
analyses and implementation experiments are provided at each phase. 

In the first phase, a special purpose network implementing discrete
connectionist relaxation is used to topologically discriminate between
objects. In the second step, the algorithm is generalized to a
massively parallel formulation of constraint satisfaction, yielding an
arc consistency algorithm with the fastest known time complexity. At
this stage the formulation of the application problem is also
generalized, so geometric discrimination can be achieved. Developing an
implementation required defining a method for the domain specific
optimization of the parallel arc consistency algorithm. The
optimization method is applicable to arbitrary domains.

In the final phase, the solution is generalized to handle uncertain
input information and statistical domain dependence. Segmentation and
recognition are computed simultaneously by a coupled Markov Random
Field. Both problems are posed as labelling problems within a unified
high-level MRF architecture.  In the segmentation subnet, evidence from
the image is combined with clique potentials expressing both
qualitative {\em a priori} constraints and learnable domain dependent
knowledge. Matching constraints and coupling constraints complete the
definition of the field.  The effectiveness of the framework is
demonstrated in experiments involving the traditionally difficult
problems of occlusion and accidental alignment.

============

TO ORDER, send requests to tr at cs.rochester.edu or physical mail to:
Technical Reports Librarian, Department of Computer Science, 
University of Rochester, Rochester, NY 14627.  The cost is $7.25.
Make checks payable to the University of Rochester.