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 Θ(n4) time, and Dietz and Kosaraju showed that it could be solved in Θ(n2) 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 Θ(e1/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.
|Copyright © 2005-2017 Quentin F. Stout|