A new algorithmic framework for basic problems on binary images

Abstract This paper presents a new algorithmic framework for some basic problems on binary images. Algorithms for binary images such as one of extracting a connected component containing a query pixel and that of connected components labeling play basic roles in image processing. Those algorithms usually use linear work space for efficient implementation. In this paper we propose algorithms for several basic problems on binary images which are efficient in time and space, using space-efficient algorithms for grid graphs. More exactly, some of them run in O ( n log n ) time using O ( 1 ) work space and the others run in O ( n ) or O ( n log n ) time using O ( n ) work space for a binary image of n pixels stored in a read-only array.