Small Work Space Algorithms for Some Basic Problems on Binary Images

Tetsuo Asano (1) , Sergey Bereg (2) , Lilian Buzer (3)

1 Japan Advanced Institute of Science and Technology
2 University of Texas at Dallas - Department of Computer Science [Dallas]
3 LIGM - Laboratoire d'Informatique Gaspard-Monge

This paper presents space-efficient algorithms for some basic tasks (or problems) on a binary image of n pixels, assuming that an input binary image is stored in a read-only array with random-access. Although efficient algorithms are available for those tasks if O(n) work space (of O(n logn) bits) is available, we aim to propose efficient algorithms using only limited work space, i.e., O(1) or O(√n) space. Tasks to be considered are (1) CCC to count the number of connected components, (2) MERR to report the minimum enclosing rectangle of every connected component, and (3) LCCR to report a largest connected component. We show that we can solve each of CCC, MERR, and LCCR in O(n logn) time using only O(1) space. If we can use O(√n) work space, we can solve them in O(n), O(n), and O(n + m logm) time, respectively, where m is the number of pixels in the largest connected component.

Mots clés: Connected component; Minimum enclosing rectangle; Largest connected component; Space-efficient algorithms

Domaines: Mathématique discrète [cs.DM]; Traitement des images [eess.IV]

Tetsuo Asano, Sergey Bereg, Lilian Buzer. Small Work Space Algorithms for Some Basic Problems on Binary Images. 15th International Workshop Combinatorial Image Analysis, IWCIA 2012, Nov 2012, Austin, United States. pp.103-114, ⟨10.1007/978-3-642-34732-0_8⟩. ⟨hal-00827181⟩