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 metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00827181
Contributor : Lilian Buzer <>
Submitted on : Thursday, May 30, 2013 - 3:11:35 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, April 4, 2017 - 12:44:44 PM

File

IWCIA_2012.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

322

Files downloads

412