Quentin F. Stout

EECS Department, University of Michigan

**Abstract:**
Given two black/white images, the problem of *topological matching* is to
decide if it is possible to deform each image into the other.
By deforming we mean ``rubber sheet'' deformation where stretching and warping are allowed, but not tearing. When the
images are *n x n* and they are stored in a 2-dimensional *n x 2n*
mesh-connected cellular automaton (a simple form of parallel computer),
Beyer showed that the topological
matching problem could be solved in
Θ(n^{4}) time, and Dietz
and Kosaraju showed that it could be solved in
Θ(n^{2}) time.
Even for the far more powerful mesh computer model
(in which processors can perform operations on words of logarithmic
length in constant time) no faster algorithm was known.

This paper gives an optimal algorithm, taking Θ(n) time.
An algorithm is first derived for the mesh computer, and
then self-organizing structures called
*clerks* are used to perform a stepwise simulation of the
mesh computer on the cellular array.

The mesh computer algorithm transforms the images into rooted trees,
where each node represents a connected component of the image. Alternating
levels of the tree represent alternating colors. These
trees are isomorphic if and only if the images can be deformed into each
other, so a tree isomorphism algorithm is developed.
Given two arbitrary trees represented as an unordered collection of
*e* edges, stored one per processor in a square mesh computer of
*e* processors, the algorithm decides isomorphism in optimal
Θ(e^{1/2}) time.

Note that the tree isomorphism approach will not work in 3 or higher dimensions, because it could not distinguish between two interlocking rings versus 2 seperated rings.

**Keywords:** parallel algorithm,
image processing, homotopy, rubber sheet deformation,
cellular automaton (array), cellular array, iterative arrays,
self-organizing cellular automata,
Hilbert space-filling curve,
mesh computer, tree isomorphism

**Complete paper.**
This paper appears in
*Proc. 15th ACM Symposium on Theory of Computing* (1983),
pp. 24-31.
ACM later digitized it.

**Related work:**

- Here is the paper introducing clerks. There each clerk is a small linear cellular automata (embedded in a 2-dimensional cellular automaton), while here each clerk is 2-dimensional, formed by using a space-filling curve for the entire cellular automaton. In this paper the curve is called a proximity ordering, but a more common term is Hilbert space-filling curve.
- My papers in parallel computing, and an overview of my research
- An explanation of parallel computing, Parallel Computing 101, a tutorial, and a list of parallel computing resources.

Copyright © 2005-2016 Quentin F. Stout |