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

Tetsuo ASANO; Revant KUMAR

doi:10.1587/transfun.E96.A.1044

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

Tetsuo ASANO, Revant KUMAR

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.6 pp.1044-1050

Publication Date: 2013/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E96.A.1044

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Tetsuo ASANO
JAIST
Revant KUMAR
Indian Institute of Technology (IIT) at Guwahati

Keyword

algorithm, binary image, connected component, image processing, small work space

Cite this

Copy

Tetsuo ASANO, Revant KUMAR, "A Small-Space Algorithm for Removing Small Connected Components from a Binary Image" in IEICE TRANSACTIONS on Fundamentals, vol. E96-A, no. 6, pp. 1044-1050, June 2013, doi: 10.1587/transfun.E96.A.1044.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.1044/_p

Copy

@ARTICLE{e96-a_6_1044,
author={Tetsuo ASANO, Revant KUMAR, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Small-Space Algorithm for Removing Small Connected Components from a Binary Image},
year={2013},
volume={E96-A},
number={6},
pages={1044-1050},
abstract={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.},
keywords={},
doi={10.1587/transfun.E96.A.1044},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - A Small-Space Algorithm for Removing Small Connected Components from a Binary Image
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1044
EP - 1050
AU - Tetsuo ASANO
AU - Revant KUMAR
PY - 2013
DO - 10.1587/transfun.E96.A.1044
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2013
AB - 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.
ER -