Abstract
An efficient algorithm for computing the medial axis transform of an an m by n binary image, that is, an image represented as a matrix of ones and zeros with m rows and n columns, is developed. The medial axis transform is, effectively, the set of all maximal square blocks of ones in the image where a square block is maximal if it is not contained by any other square blocks of ones. The algorithm presented requires O(mn) time and O(n) space and runs in a single pass through the image. This property makes it ideally suited to processing, in real time, images obtained from a linear array scanner since the memory requirements do not grow as the image is scanned and the medial axis is generated as the image is scanned.
The algorithm is not only efficient in theory but practical as well; the algorithm has been implemented in four pages of fully commented C code.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Blum, “A transformation for extracting new descriptors of shape”, in W. Wathen-Dunn, Ed., Models for the Perception of Speech and Visual Form, pp. 362–280, MIT Press, Cambridge, Mass. 1967.
A. Rosenfeld and A.C. Kak, Digital Picture Processing, Academic Press, 1982.
T. Wakayama, “A core-line tracing algorithm based on maximal square moving”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 4(1), pp.68–74, 1982.
L.J. Guibas, Editor, “Problems”, Journal of Algorithms, 3, pp. 362–380, 1982.
D. G. Kirkpatrick, “Efficient computation of continuous skeletons”, Proc. 20th Symposium on the Foundations of Computer Science, pp. 18–27, October 1979.
D.T. Lee, “Medial axis transformation of a planar shape”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 4(4), pp.363–369, 1982.
H. Breu, “An efficient digital medial axis transform under the L ∞ metric”, Hewlett Packard Labs Technical Report, in press, 1989.
R.E. Tarjan, “Amortized computational complexity”, SIAM J. Alg. Disc. Meth., 6(2), pp. 306–318, April 1985.
N. Ahuja and W. Hoff, “Augmented medial axis transform”, Seventh International Conference on Pattern Recognition, pp. 336–338, 1984.
A. Wu, S. Bhaskar, and A. Rosenfeld, “Computation of geometric properties from the medial axis transform in O(n log n) time”, Computer Vision, Graphics, and Image Processing, 34, pp. 76–92, 1982.
M. Garey and D. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness, page 232, W.H. Freeman and Company, San Francisco, 1979.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Breu, H. (1989). An efficient algorithm for finding all maximal square blocks in a matrix. In: Dehne, F., Sack, J.R., Santoro, N. (eds) Algorithms and Data Structures. WADS 1989. Lecture Notes in Computer Science, vol 382. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-51542-9_38
Download citation
DOI: https://doi.org/10.1007/3-540-51542-9_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51542-5
Online ISBN: 978-3-540-48237-6
eBook Packages: Springer Book Archive