For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Small-Space Algorithm for Removing Small Connected Components from a Binary Image
Tetsuo ASANO Revant KUMAR
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2013/06/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
algorithm, binary image, connected component, image processing, small work space,
Full Text: PDF(710.8KB)>>
Given a binary image I and a threshold t, the size-thresholded binary image I(t) defined by I and t is the binary image after removing all connected components consisting of at most t pixels. This paper presents space-efficient algorithms for computing a size-thresholded binary image for a binary image of n pixels, assuming that the image is stored in a read-only array with random-access. With regard to the problem, there are two cases depending on how large the threshold t is, namely, Relatively large threshold where t = Ω(), and Relatively small threshold where t = O(). In this paper, a new algorithmic framework for the problem is presented. From an algorithmic point of view, the problem can be solved in O() time and O() work space. We propose new algorithms for both the above cases which compute the size-threshold binary image for any binary image of n pixels in O(nlog n) time using only O() work space.