A Small-Space Algorithm for Removing Small Connected Components from a Binary Image

概要

論文の詳細を見る
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=Ω(√n), and Relatively small threshold where t=O(√n). 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(n) time and O(n) 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(n log n) time using only O(√n) work space.