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⁴) time, and Dietz and Kosaraju showed that it could be solved in Θ(n²) 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-2024 Quentin F. Stout