Skip to Main content Skip to Navigation
Conference papers

Small Work Space Algorithms for Some Basic Problems on Binary Images

Abstract : 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.
Complete list of metadata
Contributor : Lilian Buzer Connect in order to contact the contributor
Submitted on : Thursday, May 30, 2013 - 3:11:35 PM
Last modification on : Wednesday, April 13, 2022 - 5:54:02 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 12:44:44 PM


Files produced by the author(s)



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⟩



Record views


Files downloads