Small Work Space Algorithms for Some Basic Problems on Binary Images

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(\sqrt{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(\sqrt{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.