We study two classical connectivity-preserving parallel shrinking algorithms proposed to recognize and label two-dimensional connected components of binary images. The algorithms we consider were developed by Beyer [Recognition of topological invariants by iterative arrays, Ph.D. Thesis, MIT, 1969, p. 144] and Levialdi [Commun. ACM 15 (1) (1972) 7] independently for the purpose of shrinking 4-connected and 8-connected components of binary images in linear time, respectively. It is shown that those two independently developed algorithms are closely related and in a sense they are in a dual relation such that, for any initially given binary image and its inverted one, one algorithm produces, simultaneously, an image which is dual of the one produced by the other, step-by-step. (C) 2002 Elsevier Science B.V. All rights reserved.

Umeo, H., Mauri, G. (2002). A duality theorem for two connectivity-preserving parallel shrinking transformations. FUTURE GENERATION COMPUTER SYSTEMS, 18(7), 931-937 [10.1016/S0167-739X(02)00072-9].

A duality theorem for two connectivity-preserving parallel shrinking transformations

MAURI, GIANCARLO
2002

Abstract

We study two classical connectivity-preserving parallel shrinking algorithms proposed to recognize and label two-dimensional connected components of binary images. The algorithms we consider were developed by Beyer [Recognition of topological invariants by iterative arrays, Ph.D. Thesis, MIT, 1969, p. 144] and Levialdi [Commun. ACM 15 (1) (1972) 7] independently for the purpose of shrinking 4-connected and 8-connected components of binary images in linear time, respectively. It is shown that those two independently developed algorithms are closely related and in a sense they are in a dual relation such that, for any initially given binary image and its inverted one, one algorithm produces, simultaneously, an image which is dual of the one produced by the other, step-by-step. (C) 2002 Elsevier Science B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
binary image processing; shrinking algorithm; cellular automaton
English
ago-2002
18
7
931
937
none
Umeo, H., Mauri, G. (2002). A duality theorem for two connectivity-preserving parallel shrinking transformations. FUTURE GENERATION COMPUTER SYSTEMS, 18(7), 931-937 [10.1016/S0167-739X(02)00072-9].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/2548
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
Social impact